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

文章目录

  • 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=′′a0​a1​…an−1′′​

  其中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;
}

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Docker compose容器编排

Docker compose容器编排

Docker compose容器编排 1、Docker compose简介 docker-compose是docker的编排工具&#xff0c;用于定义和运行一个项目&#xff0c;该项目包含多个docker容器&#xff0c;在如今的微服务时代&#xff0c;一个项目会存在多个服务&#xff0c;使用docker一个个部署操作的话就会…
阅读更多...
计算机网络-应用层

计算机网络-应用层

文章目录 应用层协议原理万维网和HTTP协议万维网概述统一资源定位符HTML文档 超文本传输协议&#xff08;HTTP&#xff09;HTTP报文格式请求报文响应报文cookie 万维网缓存与代理服务器 DNS系统域名空间域名服务器和资源记录域名解析过程递归查询迭代查询 动态主机配置协议&…
阅读更多...
硬件工程师到底可以从哪些方面提升自己？

硬件工程师到底可以从哪些方面提升自己？

大家好，这里是大话硬件。 最近在大话硬件群里，聊得比较多的就是讨论怎么提升自己的能力，怎么拿到更高的工资。我想，这可能并不是只在大话硬件群才有的话题，其实在每一位工作的人心里应该都在想的两个问题。 因此，这篇文章简单分享一下，作为一名硬件工程师，可以在做哪…
阅读更多...
1220*2440mm建筑模板木工板：桥梁工程中的覆膜板选择

1220*2440mm建筑模板木工板：桥梁工程中的覆膜板选择

在桥梁工程中&#xff0c;选择合适的建筑模板木工板至关重要。其中&#xff0c;1220*2440mm规格的建筑模板木工板作为一种常见的选择&#xff0c;特别适用于混凝土工程和桥梁建设。本文将重点介绍这种规格的木工板作为覆膜板在桥梁工程中的应用。 1220*2440mm建筑模板木工板是一…
阅读更多...
基于 golang 从零到一实现时间轮算法 (一)

基于 golang 从零到一实现时间轮算法 (一)

前言 时间轮是用来解决海量百万级定时器&#xff08;或延时&#xff09;任务的最佳方案&#xff0c;linux 的内核定时器就是采用该数据结构实现。 应用场景 自动删除缓存中过期的 Key&#xff1a;缓存中设置了 TTL 的 kv&#xff0c;通过把该 key 对应的 TTL 以及回调方法注册…
阅读更多...
第六讲:VBA与ACCESS的ADO连接中，所涉及的对象

第六讲:VBA与ACCESS的ADO连接中，所涉及的对象

《VBA数据库解决方案》教程&#xff08;10090845&#xff09;是我推出的第二套教程&#xff0c;目前已经是第二版修订了。这套教程定位于中级&#xff0c;是学完字典后的另一个专题讲解。数据库是数据处理的利器&#xff0c;教程中详细介绍了利用ADO连接ACCDB和EXCEL的方法和实…
阅读更多...
vue 获取上一周和获取下一周的日期时间

vue 获取上一周和获取下一周的日期时间

效果图&#xff1a; 代码&#xff1a; <template><div><div style"padding: 20px 0;"><div style"margin-left: 10px; border-left: 5px solid #0079fe; font-size: 22px; font-weight: 600; padding-left: 10px">工作计划</…
阅读更多...
uni-app离线打包在android studio创建的.jks证书，签名文件获取MD5问题

uni-app离线打包在android studio创建的.jks证书，签名文件获取MD5问题

获取证书信息 keytool -list -v -keystore test.keystore 获取的信息中没有md5信息 可以使用以下方式获取md5. 先创建签名文件&#xff0c;放到项目目录下 配置build.gradle文件 在android studio 打开终端输入以下命令 ./gradlew signingReport 等待生成签名。 生成的内容…
阅读更多...
uniapp subNvue 写的视频播放

uniapp subNvue 写的视频播放

文件下载地址 https://download.csdn.net/download/weixin_47517731/88500016https://download.csdn.net/download/weixin_47517731/88500016 1:在pages.json中配置视频播放页面 {/* 视频详情页面 */"path": "pages/detail-video/detail","style&q…
阅读更多...
Android ConstraintLayout分组堆叠圆角ShapeableImageView

Android ConstraintLayout分组堆叠圆角ShapeableImageView

Android ConstraintLayout分组堆叠圆角ShapeableImageView <?xml version"1.0" encoding"utf-8"?> <androidx.constraintlayout.widget.ConstraintLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:app"…
阅读更多...
【凡人修仙传】定档曝光，最新更新时间有所调整，期待值暴涨

【凡人修仙传】定档曝光，最新更新时间有所调整，期待值暴涨

Hello,小伙伴们&#xff0c;我是小郑继续为大家深度解析国漫资讯。 深度爆料&#xff0c;备受瞩目的动漫作品《凡人修仙传》终于在新年之际宣布定档了&#xff01;这个消息让广大动漫爱好者们激动不已。在某知名视频网站上&#xff0c;这部作品的官方发布了一个名为“新年番定…
阅读更多...
Shell变量

Shell变量

Shell变量 本地变量变量定义取出变量值 特殊参数变量⾯试题分享 特殊状态变量脚本控制返回值获取上⼀次后台进程的PID再来分享一道面试题&#xff1a; 获取当前脚本的PID获取上次命令的最后一个参数 本地变量 定义Shell变量&#xff0c;变量名不需要加美元符 $ 本地变量只在⽤…
阅读更多...
JS异常处理——throw和try、catch以及debugger

JS异常处理——throw和try、catch以及debugger

让我为大家介绍一下异常处理吧&#xff01; 异常处理是指预估代码执行过程中可能发生的错误&#xff0c;然后最大程度的避免错误的发生导致整个程序无法继续运行 throw 抛异常 第一种写法 function fun(x, y) {// undefined是false 但取反就是trueif (!x || !y) {// 第一种写…
阅读更多...
【ChatGPT瀑布到水母】AI 在驱动软件研发的革新与实践

【ChatGPT瀑布到水母】AI 在驱动软件研发的革新与实践

这里写目录标题 前言内容简介作者简介专家推荐读者对象目录直播预告 前言 计算机技术的发展和互联网的普及&#xff0c;使信息处理和传输变得更加高效&#xff0c;极大地改变了金融、商业、教育、娱乐等领域的运作方式。数据分析、人工智能和云计算等新兴技术&#xff0c;也在不…
阅读更多...
VM虚拟机逆向 --- [NCTF 2018]wcyvm 复现

VM虚拟机逆向 --- [NCTF 2018]wcyvm 复现

文章目录 前言题目分析 前言 第四题了&#xff0c;搞定&#xff0c;算是独立完成比较多的一题&#xff0c;虽然在还原汇编的时候还是很多问题。 题目分析 代码很简单&#xff0c;就是指令很多。 opcode在unk_6021C0处&#xff0c;解密的数据在dword_6020A0处 opcode [0x08, …
阅读更多...
众佰诚：新手如何在抖音电商中脱颖而出

众佰诚：新手如何在抖音电商中脱颖而出

在这个信息爆炸的时代&#xff0c;短视频平台抖音已经成为了人们获取信息、娱乐和购物的重要渠道。越来越多的商家开始在抖音上开设店铺&#xff0c;希望通过这个平台实现销售增长。然而&#xff0c;对于新手来说&#xff0c;如何在众多的竞争对手中脱颖而出&#xff0c;成为了…
阅读更多...
人工智能与卫星：颠覆性技术融合开启太空新时代

人工智能与卫星：颠覆性技术融合开启太空新时代

人工智能与卫星&#xff1a;颠覆性技术融合开启太空新时代 摘要&#xff1a;本文将探讨人工智能与卫星技术的融合&#xff0c;并介绍其应用、发展和挑战。通过深入了解这一领域的前沿动态&#xff0c;我们将展望一个由智能卫星驱动的未来太空时代。 一、引言 近年来&#xf…
阅读更多...
时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测

时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测

时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测 目录 时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 时序预测 …
阅读更多...
汽车标定技术（一）：XCP概述

汽车标定技术（一）：XCP概述

目录 1.汽车标定概述 2.XCP协议由来及版本介绍 3.XCP技术通览 3.1 XCP上下机通信模型 3.2 XCP指令集 3.2.1 XCP帧结构定义 3.2.2 标准指令集 3.2.3 标定指令集 3.2.4 页切换指令集 3.2.5 数据采集指令集 3.2.6 刷写指令集 3.3 ECU描述文件(A2L)概述 3.3.1 标定上位…
阅读更多...
无声的世界，精神科用药并结合临床的一些分析及笔记（十）

无声的世界，精神科用药并结合临床的一些分析及笔记（十）

目录 回 “ 家 ” 克服恐惧 奥沙西泮 除夕 酒与药 警告 离别 回 “ 家 ” 她的锥切手术进行的很顺利&#xff0c;按计划继续返回安定医院调节心理状态&#xff0c;病友们都盼着我们回“家”。当我俩跨入病区&#xff0c;大家都涌过来帮我们大包小包的拎着行李&#xff0…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023