【数据结构】数组和字符串(十三):链式字符串的基本操作(串长统计、查找、复制、插入、删除、串拼接)

文章目录

  • 4.3 字符串
    • 4.3.1 字符串的定义与存储
    • 4.3.2 字符串的基本操作(链式存储)
      • 1. 结构体
      • 2. 初始化
      • 3. 判空
      • 4. 串尾添加
      • 5. 打印
      • 6. 串长统计
      • 7. 查找
      • 8. 复制
      • 9. 插入
      • 10. 删除
      • 11. 串拼接
      • 12. 销毁
      • 13. 主函数
      • 14. 代码整合

4.3 字符串

  字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列,简称为串。例如 “good morning”就是由12个字符构成的一个字符串。一般把字符串记作:

S = ′ ′ a 0 a 1 … a n − 1 ′ ′ S=''a_{0} a_{1}…a_{n-1}'' S=′′a0a1an1′′

  其中S是串名,引号中的字符序列是串值。字符个数是串的长度,长度为0的串被称为空串,因为它不包含任何字符。需要注意的是,空格字符(" ")并不是空串,因为它包含一个字符——空格。
  若把某个串称为主串,则主串中任意个连续的字符组成的子序列被称为子串。子串在主串中第一次出现时,其首字符在主串中的序号被称为该子串在主串中的位置。
  关于字符串的基础知识亦可参考前文:
【重拾C语言】六、批量数据组织(三)数组初值;字符串、字符数组、字符串数组;类型定义 typedef
【重拾C语言】七、指针(三)指针与字符串(字符串与字符串数组;指针与字符串的遍历、拷贝、比较;反转字符串

4.3.1 字符串的定义与存储

  字符串在许多非数值计算问题中扮演着重要的角色,并在模式匹配、程序编译和数据处理等领域得到广泛应用。在高级程序设计语言中,字符串通常被定义为以特殊字符’\0’(称为空字符或字符串结束符)结尾的字符序列。这个约定使得在处理字符串时可以方便地确定字符串的结束位置。关于字符串的存储方式,主要有两种常见的方式:

  • 顺序存储:字符串的字符按照顺序依次存储在连续的内存空间中。这种方式使得字符串的访问和操作效率较高,可以通过索引直接访问任意位置的字符。在顺序存储方式中,字符串的长度可以通过计算字符个数或者遇到’\0’结束符来确定。

  • 链式存储:字符串的字符通过链表的方式进行存储。每个节点包含一个字符和指向下一个节点的指针。链式存储方式可以动态地分配内存,适用于长度可变的字符串。但是相比于顺序存储,链式存储方式需要更多的内存空间,并且访问字符需要遍历链表。

  选择何种存储方式取决于具体的应用场景和需求。顺序存储适合于需要频繁访问和操作字符串的情况,而链式存储适合于长度可变的字符串或者对内存空间要求较高的情况。具体C语言实现可参照前文:
  【数据结构】数组和字符串(十一):字符串的定义与存储(顺序存储、链式存储及其C语言实现)

4.3.2 字符串的基本操作(链式存储)

  • 串长统计返回串s的长度;
  • 串定位返回字符或子串在母串s中首次出现的位置的指针;
  • 串复制将一个串s2复制到另一个串s1中;
  • 串插入在指定位置后面插入字符串;
  • 串删除是删除一个子串;
  • 串拼接将串s2拼接到串s1的尾部;
  • ……

  【数据结构】线性表(二)单链表及其基本操作(创建、插入、删除、修改、遍历打印)

1. 结构体

typedef struct Node {
    char data;
    struct Node* next;
} Node;

typedef struct {
    Node* head;
    Node* tail;
} LinkedList;

  • Node:表示链表的节点,包含一个字符数据和一个指向下一个节点的指针。
  • LinkedList:表示链表,包含链表的头节点和尾节点。

2. 初始化

  initLinkedList函数:用于初始化链表,将头节点和尾节点都设置为NULL

void initLinkedList(LinkedList* list) {
    list->head = NULL;
    list->tail = NULL;
}

3. 判空

  isEmpty函数:判断链表是否为空,即头节点是否为NULL

bool isEmpty(const LinkedList* list) {
    return list->head == NULL;
}

4. 串尾添加

   append函数:向链表末尾添加一个字符节点。

void append(LinkedList* list, char data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (isEmpty(list)) {
        list->head = newNode;
        list->tail = newNode;
    } else {
        list->tail->next = newNode;
        list->tail = newNode;
    }
}

  • 如果链表为空,即头节点为NULL,则将新节点设置为头节点和尾节点。
  • 如果链表不为空,即头节点不为NULL,则将新节点链接到尾节点的后面,并将尾节点更新为新节点。

5. 打印

   display函数:遍历链表并打印出所有字符节点的数据。

void display(const LinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        printf("%c", current->data);
        current = current->next;
    }
    printf("\n");
}

  • 函数接受一个指向LinkedList结构体的指针作为参数,然后从头节点开始遍历链表,打印每个节点的数据。

6. 串长统计

   length函数:计算链表的长度,即字符节点的个数。

int length(const LinkedList* list) {
    int count = 0;
    Node* current = list->head;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

  • 函数接受一个指向LinkedList结构体的指针作为参数,然后从头节点开始遍历链表,每遍历一个节点,计数器加1,最后返回计数器的值。

7. 查找

   search函数:在链表中搜索目标字符串。

int search(const LinkedList* list, const char* target) {
    int targetLength = strlen(target);
    int listLength = length(list);
    if (targetLength > listLength) {
        printf("Error: Target string is longer than the source string.\n");
        return -1;
    }
    Node* current = list->head;
    int index = 0;
    while (current != NULL) {
        if (current->data == target[0]) {
            Node* temp = current;
            int i = 0;
            while (temp != NULL && temp->data == target[i]) {
                temp = temp->next;
                i++;
                if (i == targetLength) {
                    return index;
                }
            }
        }
        current = current->next;
        index++;
    }
    printf("Error: Target string not found in the source string.\n");
    return -1;
}

  • 首先比较目标字符串的长度和链表的长度,如果目标字符串比链表长,说明无法找到目标字符串,函数返回错误。
  • 然后从头节点开始遍历链表,找到第一个与目标字符串首字符相同的节点,
    • 然后从该节点开始逐个比较字符,直到找到完全匹配的目标字符串或链表遍历结束。
    • 如果找到目标字符串,函数返回目标字符串在链表中的起始位置的索引;
    • 如果未找到目标字符串,函数返回错误。

8. 复制

  copy函数:将源链表中的字符复制到目标链表中。

bool copy(LinkedList* dest, const LinkedList* src) {
    Node* current = src->head;
    while (current != NULL) {
        append(dest, current->data);
        current = current->next;
    }
    return true;
}

  • 函数接受两个指向LinkedList结构体的指针,分别表示源链表和目标链表。
  • 通过遍历源链表的每个节点,创建一个新节点并将数据复制过去,然后将新节点添加到目标链表的末尾。

9. 插入

   insert函数:在链表的指定位置插入一个字符串。

bool insert(LinkedList* list, const char* insertStr, int pos) {
    int listLength = length(list);
    int insertStrLength = strlen(insertStr);
    if (pos < 0 || pos > listLength) {
        printf("Error: Invalid insertion position.\n");
        return false;
    }
    Node* current = list->head;
    int index = 0;
    while (current != NULL) {
        if (index == pos) {
            for (int i = 0; i < insertStrLength; i++) {
                Node* newNode = (Node*)malloc(sizeof(Node));
                newNode->data = insertStr[i];
                newNode->next = current->next;
                current->next = newNode;
                current = newNode;
            }
            return true;
        }
        current = current->next;
        index++;
    }
    return false;
}

  • 首先判断插入位置是否合法,即索引是否在有效范围内。然后遍历链表找到插入位置的节点,然后逐个创建新节点并插入到链表中。

10. 删除

  delete函数:从链表中删除指定位置和长度的字符。

bool delete(LinkedList* list, int pos, int len) {
    int listLength = length(list);
    if (pos < 0 || pos >= listLength) {
        printf("Error: Invalid deletion position.\n");
        return false;
    }
    if (pos + len > listLength) {
        printf("Error: Deletion length exceeds the length of the string.\n");
        return false;
    }
    Node* current = list->head;
    int index = 0;
    while (current != NULL) {
        if (index == pos) {
            Node* prev = current;
            Node* temp = current;
            for (int i = 0; i < len; i++) {
                temp = temp->next;
                free(prev);
                prev = temp;
            }
            current->next = temp;
            return true;
        }
        current = current->next;
        index++;
    }
    return false;
}

  • 首先判断删除位置是否合法,然后找到删除位置的节点,逐个删除指定长度的节点。

11. 串拼接

  concat函数:将第二个链表中的字符追加到第一个链表的末尾。的末尾。

bool concat(LinkedList* list1, const LinkedList* list2) {
    Node* current = list2->head;
    while (current != NULL) {
        append(list1, current->data);
        current = current->next;
    }
    return true;
}

  • 遍历第二个链表的每个节点,将节点的数据追加到第一个链表。

12. 销毁

  destroy函数:释放链表占用的内存。遍历链表的每个节点,释放节点的内存,并将头节点和尾节点设置为NULL

void destroy(LinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    list->head = NULL;
    list->tail = NULL;
}
  • 函数遍历链表的每个节点,释放节点的内存,并将头节点和尾节点设置为NULL

13. 主函数


int main() {
    LinkedList S;
    initLinkedList(&S);
    const char target[] = "H";
    LinkedList copyStr;
    initLinkedList(&copyStr);
    const char insertStr[] = "H";
    int pos = 3;

    append(&S, 'q');
    append(&S, 'o');
    append(&S, 'm');
    append(&S, 'o');
    append(&S, 'l');
    append(&S, 'a');
    append(&S, 'n');
    append(&S, 'g');
    append(&S, 'm');
    append(&S, 'a');

    display(&S);

    int searchIndex = search(&S, target);
    if (searchIndex != -1) {
        printf("Target string found at index: %d\n", searchIndex);
    }

    copy(&copyStr, &S);
    display(&copyStr);

    insert(&S, insertStr, pos);
    display(&S);

    delete(&S, pos, strlen(insertStr));
    display(&S);

    concat(&S, &copyStr);
    display(&S);

    destroy(&S);
    destroy(&copyStr);

    return 0;
}

在这里插入图片描述

14. 代码整合

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    char data;
    struct Node* next;
} Node;

typedef struct {
    Node* head;
    Node* tail;
} LinkedList;

void initLinkedList(LinkedList* list) {
    list->head = NULL;
    list->tail = NULL;
}

bool isEmpty(const LinkedList* list) {
    return list->head == NULL;
}

void append(LinkedList* list, char data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (isEmpty(list)) {
        list->head = newNode;
        list->tail = newNode;
    } else {
        list->tail->next = newNode;
        list->tail = newNode;
    }
}

void display(const LinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        printf("%c", current->data);
        current = current->next;
    }
    printf("\n");
}

int length(const LinkedList* list) {
    int count = 0;
    Node* current = list->head;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

int search(const LinkedList* list, const char* target) {
    int targetLength = strlen(target);
    int listLength = length(list);
    if (targetLength > listLength) {
        printf("Error: Target string is longer than the source string.\n");
        return -1;
    }
    Node* current = list->head;
    int index = 0;
    while (current != NULL) {
        if (current->data == target[0]) {
            Node* temp = current;
            int i = 0;
            while (temp != NULL && temp->data == target[i]) {
                temp = temp->next;
                i++;
                if (i == targetLength) {
                    return index;
                }
            }
        }
        current = current->next;
        index++;
    }
    printf("Error: Target string not found in the source string.\n");
    return -1;
}

bool copy(LinkedList* dest, const LinkedList* src) {
    Node* current = src->head;
    while (current != NULL) {
        append(dest, current->data);
        current = current->next;
    }
    return true;
}

bool insert(LinkedList* list, const char* insertStr, int pos) {
    int listLength = length(list);
    int insertStrLength = strlen(insertStr);
    if (pos < 0 || pos > listLength) {
        printf("Error: Invalid insertion position.\n");
        return false;
    }
    Node* current = list->head;
    int index = 0;
    while (current != NULL) {
        if (index == pos) {
            for (int i = 0; i < insertStrLength; i++) {
                Node* newNode = (Node*)malloc(sizeof(Node));
                newNode->data = insertStr[i];
                newNode->next = current->next;
                current->next = newNode;
                current = newNode;
            }
            return true;
        }
        current = current->next;
        index++;
    }
    return false;
}

bool delete(LinkedList* list, int pos, int len) {
    int listLength = length(list);
    if (pos < 0 || pos >= listLength) {
        printf("Error: Invalid deletion position.\n");
        return false;
    }
    if (pos + len > listLength) {
        printf("Error: Deletion length exceeds the length of the string.\n");
        return false;
    }
    Node* current = list->head;
    int index = 0;
    while (current != NULL) {
        if (index == pos) {
            Node* prev = current;
            Node* temp = current;
            for (int i = 0; i < len; i++) {
                temp = temp->next;
                free(prev);
                prev = temp;
            }
            current->next = temp;
            return true;
        }
        current = current->next;
        index++;
    }
    return false;
}

bool concat(LinkedList* list1, const LinkedList* list2) {
    Node* current = list2->head;
    while (current != NULL) {
        append(list1, current->data);
        current = current->next;
    }
    return true;
}

void destroy(LinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    list->head = NULL;
    list->tail = NULL;
}

int main() {
    LinkedList S;
    initLinkedList(&S);
    const char target[] = "H";
    LinkedList copyStr;
    initLinkedList(&copyStr);
    const char insertStr[] = "H";
    int pos = 3;

    append(&S, 'q');
    append(&S, 'o');
    append(&S, 'm');
    append(&S, 'o');
    append(&S, 'l');
    append(&S, 'a');
    append(&S, 'n');
    append(&S, 'g');
    append(&S, 'm');
    append(&S, 'a');

    display(&S);

    int searchIndex = search(&S, target);
    if (searchIndex != -1) {
        printf("Target string found at index: %d\n", searchIndex);
    }

    copy(&copyStr, &S);
    display(&copyStr);

    insert(&S, insertStr, pos);
    display(&S);

    delete(&S, pos, strlen(insertStr));
    display(&S);

    concat(&S, &copyStr);
    display(&S);

    destroy(&S);
    destroy(&copyStr);

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/112374.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2023年CCF中国开源大会“大模型时代的智能化软件工程新范式”分论坛成功举行...

2023年CCF中国开源大会“大模型时代的智能化软件工程新范式”分论坛于10月21日在湖南长沙成功举行。本次论坛聚焦大模型时代的智能化软件新生态以及相应的软件工程新范式&#xff0c;邀请了多位来自学术界和工业界的专家进行分享和交流&#xff0c;共设置了5个主题报告和1个Pan…

K8S删除资源后一直处于Terminating状态无法删除解决方法

原因 使用kubectl delete 删除某命名空间是一直处于Terminating状态无法删除&#xff0c;首先排查了该命名空间下是否还存在deployment pod等资源发现没有后&#xff0c;等了很久还是无法删除后发现是因为该名称空间的“finalizers”字段有值导致 Finalizer&#xff08;终结器…

【OpenCV实现图像梯度,Canny边缘检测】

文章目录 概要图像梯度Canny边缘检测小结 概要 OpenCV中&#xff0c;可以使用各种函数实现图像梯度和Canny边缘检测&#xff0c;这些操作对于图像处理和分析非常重要。 图像梯度通常用于寻找图像中的边缘和轮廓。在OpenCV中&#xff0c;可以使用cv2.Sobel()函数计算图像的梯度…

JVM虚拟机:如何调整堆空间的大小?

对内存的调优 如上所示,从物理角度来说呢,堆内存就是蓝色的区域,从逻辑角度来说,堆内存包含这个红色的部分,调优肯定是条物理的大小了,我们先来看一下物理内存的大小是多少? 如上所示,我们通过maxMemory获取到java虚拟机试图使用的最大内存量,默认为物理内存的1/4,比我…

百度富文本上传图片后样式崩塌

&#x1f525;博客主页&#xff1a; 破浪前进 &#x1f516;系列专栏&#xff1a; Vue、React、PHP ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 问题描述&#xff1a;上传图片后&#xff0c;图片会变得很大&#xff0c;当点击的时候更是会顶开整个的容器的高跟宽 原因&#…

windows版本redis如何设置后踢启动和重启计算机之后自动重启redis

1. 进入redis安装目录 D:\softwarePackage\redis\Redis-x64-3.2.100 2. 打开dos窗口 使用以下命令来启动 Redis 服务器&#xff0c;并使其在后台运行 redis-server --service-start 3. 设置重启自启动 打开服务界面 &#xff08;windowsr 输入 services.msc&#xff09; 找…

第57篇-某钩招聘网站加密参数分析【2023-10-31】

声明:该专栏涉及的所有案例均为学习使用,严禁用于商业用途和非法用途,否则由此产生的一切后果均与作者无关!如有侵权,请私信联系本人删帖! 文章目录 一、前言二、网站分析1.X-S-HEADER参数2.请求参数data3.响应机密值data一、前言 网址: aHR0cHM6Ly93d3cubGFnb3UuY29t…

色彩校正及OpenCV mcc模块介绍

一、术语 1.光&#xff1a;是电磁波&#xff0c;可见光是可被人眼感知的电磁波。可见光大约在400-700nm波段。光子携带的能量与波长成反比&#xff0c;400nm--700nm之间的单色光的颜色从紫色渐变成红色。 2.光谱&#xff1a;除了太阳光源外&#xff0c;LED灯、白炽灯等各种照明…

k8s-调度约束

目录 工作机制 调度过程 指定调度节点 Kubernetes 是通过 List-Watch 的机制进行每个组件的协作&#xff0c;保持数据同步的&#xff0c;每个组件之间的设计实现了解耦。 用户是通过 kubectl 根据配置文件&#xff0c;向 APIServer 发送命令&#xff0c;在 Node 节点上面…

项目管理之项目质量管理MoSCoW(莫斯科)优先级排序法

项目质量管理是项目管理中至关重要的一环&#xff0c;它贯穿于项目的整个生命周期&#xff0c;包括项目启动、规划、执行、监控和控制。为了确保项目工作的质量&#xff0c;我们需要从多个方面入手&#xff0c;以下是一些关于如何保障项目工作质量管理的内容。 项目产品质量检…

兴业银行养老金拉新项目上线啦,地推百搭项目

兴业银行养老金就在 ”聚量推客“ 申请开通 今年最火的银行拉新项目就是养老金的 单价高 数据好 目前开通养老金的银行有 兴业银行养老金拉新 交通银行养老金拉新 工商银行养老金拉新 招商银行养老金拉新 浦发银行养老金拉新 广发银行养老金拉新等。。还有很多都开通了…

206. 反转链表、Leetcode的Python实现

博客主页&#xff1a;&#x1f3c6;看看是李XX还是李歘歘 &#x1f3c6; &#x1f33a;每天分享一些包括但不限于计算机基础、算法等相关的知识点&#x1f33a; &#x1f497;点关注不迷路&#xff0c;总有一些&#x1f4d6;知识点&#x1f4d6;是你想要的&#x1f497; ⛽️今…

leetcode:374. 猜数字大小(二分查找)

一、题目 函数原型&#xff1a;int guessNumber(int n) 二、思路 本题其实就是从 1 - n 中找出所要的答案。利用guess函数来判断数字是否符合答案。 答案小于当前数字&#xff0c;guess函数返回-1 答案等于当前数字&#xff0c;guess函数返回0 答案大于当前数字&#xff0c;gue…

第07章_InnoDB数据存储结构

第07章_InnoDB数据存储结构 1.数据库的存储结构:页 ​ 1.1磁盘与内存交互基本单位:页 ​ 1.2页结构概述 ​ 1.3页的大小 ​ 1.4页的上层结构 2.页的内部结构 ​ 第1部分:File Header(文件头部&#xff09;和File Trailer (文件尾部) 1.数据库的存储结构:页 索引结构给…

SMTP邮件发送图片-如何在github中存储图片并访问

之前写了一篇文章 Go&#xff1a;实现SMTP邮件发送订阅功能&#xff08;包含163邮箱、163企业邮箱、谷歌gmail邮箱&#xff09;&#xff0c;实现了通过邮箱服务来发送邮件&#xff0c;但都是文字内容&#xff0c;要是想实现邮件发送图片&#xff0c;就需要将图片放到公网可访问…

Android开发知识学习——HTTPS

文章目录 定义HTTPS连接HTTPS 连接建立的过程课后题 定义 HTTP Secure / HTTP over SSL / HTTP over TLS SSL&#xff1a;Secure Socket Layer -> TLS Transport Layer Security 定义&#xff1a;在HTTP之下增加的一个安全层&#xff0c;用于保障HTTP的加密传输 本质&…

JavaScript的高级概述

还记得我们刚刚开始的时候给JavaScript的定义吗&#xff1f; JavaScript是一种高级的&#xff0c;面向对象的&#xff0c;多范式变成语言&#xff01; 这种定义JavaScript只是冰山一角&#xff01; JavaScript的高级定义 JavaScript是一种高级的、基于原型的、面向对象、多范…

高效文件整理:按数量划分自动建立文件夹,轻松管理海量文件

在日常生活和工作中&#xff0c;我们经常需要处理大量的文件。然而&#xff0c;如何高效地整理这些文件却是一个棘手的问题。有时候&#xff0c;我们可能需要按照特定的规则来建立文件夹&#xff0c;以便更高效地整理文件。例如&#xff0c;您可以按照日期、时间或者特定的标签…

CSS3媒体查询与页面自适应

2017年9月&#xff0c;W3C发布媒体查询(Media Query Level 4)候选推荐标准规范&#xff0c;它扩展了已经发布的媒体查询的功能。该规范用于CSS的media规则&#xff0c;可以为文档设定特定条件的样式&#xff0c;也可以用于HTML、JavaScript等语言。 1、媒体查询基础 媒体查询…

【Linux】centOS7安装配置及Linux的常用命令---超详细

一&#xff0c;centOS 1.1 centOS的概念 CentOS&#xff08;Community Enterprise Operating System&#xff09;是一个由社区支持的企业级操作系统&#xff0c;它是以Red Hat Enterprise Linux&#xff08;RHEL&#xff09;源代码为基础构建的。CentOS提供了一个稳定、可靠且…