数据结构学习，串篇 (链式串）
作者：IC00
- 2022-10-17 湖南
本文字数：6900 字
阅读完需：约 1 分钟
前言
上一篇文章，博主写了顺序串的一些简单操作，串和之前我们学过的栈，队列，都是有链式的存储结构，因为顺序的存储总是有限的，而链式的存储是不需要我们定义大小的，要用多少就生成多少，不用就释放掉，确实在存储方面，链式存储有着很大的优点，这篇文章是需要和上一篇文章结合看的，因为里面有许多的逻辑，博主都是说看上一篇文章，哈哈哈偷个懒，接下来让我们来学习吧！！！😁😁😁
每日一遍，要努力！！
1.理解链式串的逻辑，认识链式串的核心代码
串的链表存储结构与顺序存储结构类似也有紧缩和非紧缩存储结构的区别。插入、删除操作效率高；存储空间的利用率低；
链式串的建立的逻辑图
核心代码：
没什么难的代码，只是一些基础代码，只要链表学的好，看这个没什么问题
typedef struct Node//结构体{ char data; //字符域 struct Node *next; //指针域，存放下一个结点的地址}*LinkString;//指针结构体类型名LinkString s1;//定义串指针 s=(LinkString)malloc(sizeof(Node));//分配内存 s->next=NULL;//最后一个指向NULL q->data=p->data;//串结点之间的赋值 free(q);//释放结点
复制代码
2.链式串的初始化和一些基本操作
链式串的最基本的初始化，判断空串，求长度。
LinkString CreateNullString() //链式串初始化操作{ LinkString s;//定义第一个结点 s=(LinkString)malloc(sizeof(Node));//分配内存 if(s!=NULL) //判断是否分配成功，成功了就把指针域赋值NULL s->next=NULL; return s;}//判断链式串是否为空串int iEmpty(LinkString s)//判断链式串s为空串{ if(s->next==NULL)//s的指针域为空 return 1; else return 0;}//求链式串的长度lengthint length(LinkString s)//求链式串的长度{ LinkString p; int n=0; p=s->next; while(p!=NULL)//遍历链式串 { n++;//累加返回 p=p->next;//往下位移 } return n;//返回计数变量的值 }//输出操作void print(LinkString s)//打印输出{ LinkString p=s->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}
复制代码
3.链式串的赋值操作
这个赋值操作就相当于单链表的尾插法，不是很难，博主也写了详细的注解
void Stringassign(LinkString s,char t[])//链式串尾插法赋值操作{ LinkString p,q,r; r=s; //r始终表示的是尾结点（最后一个非空节点，而不是最后一个NULL节点）。 q=s->next; int i; for(i=0;t[i]!='\0';i++)//遍历我们要赋值的数组 if(q!=NULL)//判断s的这个这个结点是不是不为空 {//初始化时给头结点分配了存储空间或者有其他情况 q->data=t[i];//赋值直接覆盖 r=q;//记录尾结点 q=q->next;//指向一个 } else { p=(LinkString)malloc(sizeof(Node)); //分配新结点 p->data=t[i];//赋值 r->next=p;//尾结点连接新结点 r=p;//记录新的尾结点 } r->next=NULL;//最后一个结点指向空 while(q!=NULL) //假设s串中并非空串，我们要把s中原来多余的空间释放掉 { p=p->next;//指向下一个 free(q);//释放 q=p;//把未释放的赋值给q }}
复制代码
4.链式串的复制操作
链式串的复制操作逻辑和顺序串的一致，不懂的可以看博主上一篇文章。真的没什么东西逻辑基本一致导致博主连逻辑图都不想画，博主会在下面放上一篇文章
void assign(LinkString s,LinkString t)//链式串复制操作 ，将t串的值复制给s串{ LinkString p,q,r,str; p=t->next; q=s->next; r=s; while(p!=NULL) //遍历t串 { if(q!=NULL)//判断s串是否为空，为空代表s串没有内存了 { q->data=p->data;//复制 r=q;//用来记录s串每次遍历的值 q=q->next;//s串往后移 } else//s串为空需要划分内存给s保存值 { str=(LinkString)malloc(sizeof(Node));//创建新结点来保存值 str->data=p->data;//复制 r->next=str;//最后一个连接新的结点 r=str;//改变尾指针的指向 } p=p->next;//t串往后走 } while(q!=NULL)//如果s串够长，比t串还长就释放 { p=p->next; free(q);//释放多余s的结点 q=p; } r->next=NULL;}
复制代码
5.链式串两个串之间的连接
连接的逻辑也是和顺序串一样的，都需要创建一个新的串，然后再连接
//串的连接操作void contact(LinkString s,LinkString s1,LinkString s2){ LinkString p,q,r,t; r=s; p=s1->next; q=s->next; while(p!=NULL)//遍历S1赋值给s { if(q!=NULL)//表示s已经分配了结点 ,和复制差不多 { q->data=p->data; q=q->next; r=q; } else { t=(LinkString)malloc(sizeof(Node)); //s没有分配内存需要分配 t->data=p->data; r->next=t; r=t; } p=p->next; } p=s2->next;//重新赋值p遍历s2 while(p!=NULL)//遍历s2赋值 { if(q!=NULL)//和s1是一样的道理 { q->data=p->data; q=q->next; r=q; } else { //串s原来没有分配存储空间，需要申请空间 t=(LinkString)malloc(sizeof(Node)); t->data=p->data; r->next=t; r=t; } p=p->next; } while(q!=NULL) //遍历将串s的多余的空间清除掉，可能s串很长 { p=q->next; free(q); q=p; } r->next=NULL; //最后一个指向NULL }
复制代码
6.链式串获取子串操作
用顺序串的图来表示一下逻辑，逻辑是一样的只是，赋值之间不同而已
//截取子串int substr(LinkString s,int i,int len,LinkString t){ LinkString p,q,r,u; if(i<=0 || i>length(s) || i+len-1>length(s) )//判断i和len的有效性 return 0; //指针指向s的第i-1个位置 int j,k; for(j=0,p=s;j<i;j++)//遍历到我们要取子串的位置 p=p->next; for(k=0,r=t,q=t->next;k<len;k++) { if(q!=NULL)//判断t是否划分了内存 { q->data=p->data;//赋值 r=q;//用来记录在串t没有内存的时候，r代表尾 q=q->next; } else { u=(LinkString)malloc(sizeof(Node));//划分新内存 u->data=p->data;//赋值 r->next=u;//连接新结点 r=u;//改变尾指针的位置 } p=p->next;//s串的位移到下一个 } while(q!=NULL)//遍历串t多余的结点，释放 { p=q->next; free(q); q=p; } r->next=NULL; return 1;}
复制代码
7.链式串的插入操作
梅开二度一下，用单链表的图表示插入操作，真的是一样的逻辑，没什么区别，删除也是一样的逻辑。
//插入操作int insert(LinkString s,int i,LinkString t)//s代表要被插入的串，i代表在s串的什么位置，t代表要插入进去的值{ LinkString p,q,r; if(i<=0 || i>length(s)+1)//判断i的有效性 return 0; //指向第i-1个位置 int j; for(j=0,p=s;j<i-1;j++)//遍历s到第i个 p=p->next; q=t->next; while(q!=NULL)//遍历t插入串 { r=(LinkString)malloc(sizeof(Node));//分配结点 r->data=q->data;//保存t串的值，q是指向t的 r->next=p->next;//新结点指向p的下一个结点建立连接，连接p之后的结点，p代表第i个结点 p->next=r;//s串中第i个是p，p的下一个是我们的插入结点，形成新的链 q=q->next;//t串位移到下一个结点 p=r;//代表位移到新结点的位置，打算插入新的值 } return 1;}
复制代码
8.链式串的删除操作
//删除操作int deleteString(LinkString s,int i,int len){//s代表字符串，i表示起始位置，len表示i之后多少个 LinkString p,q,r; if(i<=0 || i>length(s) || i+len-1>length(s) )//和顺序串逻辑一致，可以看博主上一篇文章 return 0; int j; for(j=0,p=s;j<i-1;j++)//遍历到我们要删除的位置 p=p->next; for(j=0;j<len;j++)//遍历删除，和链表的删除一致，可以看博主之前的文章 { q=p->next;//记住被删除的上一个位置 p->next=q->next;//把上一个位置的指针域指向下一个 free(q); } return 1; }
复制代码
9.效果演示和整体代码
整体代码：（可以直接跑）
#include <iostream>#include<stdio.h>#include<stdlib.h>typedef struct Node{ char data; //字符域 struct Node *next; //指针域，存放下一个结点的地址}*LinkString;LinkString CreateNullString() //链式串初始化操作{ LinkString s;//定义第一个结点 s=(LinkString)malloc(sizeof(Node));//分配内存 if(s!=NULL) //判断是否分配成功，成功了就把指针域赋值NULL s->next=NULL; return s;}int iEmpty(LinkString s)//判断链式串s为空串{ if(s->next==NULL)//s的指针域为空 return 1; else return 0;}void Stringassign(LinkString s,char t[])//链式串尾插法赋值操作{ LinkString p,q,r; r=s; //r始终表示的是尾结点（最后一个非空节点，而不是最后一个NULL节点）。 q=s->next; int i; for(i=0;t[i]!='\0';i++)//遍历我们要赋值的数组 if(q!=NULL)//判断s的这个这个结点是不是不为空 {//初始化时给头结点分配了存储空间或者有其他情况 q->data=t[i];//赋值直接覆盖 r=q;//记录尾结点 q=q->next;//指向一个 } else { p=(LinkString)malloc(sizeof(Node)); //分配新结点 p->data=t[i];//赋值 r->next=p;//尾结点连接新结点 r=p;//记录新的尾结点 } r->next=NULL;//最后一个结点指向空 while(q!=NULL) //假设s串中并非空串，我们要把s中原来多余的空间释放掉 { p=p->next;//指向下一个 free(q);//释放 q=p;//把未释放的赋值给q }} void assign(LinkString s,LinkString t)//链式串复制操作 ，将t串的值复制给s串{ LinkString p,q,r,str; p=t->next; q=s->next; r=s; while(p!=NULL) //遍历t串 { if(q!=NULL)//判断s串是否为空，为空代表s串没有内存了 { q->data=p->data;//复制 r=q;//用来记录s串每次遍历的值 q=q->next;//s串往后移 } else//s串为空需要划分内存给s保存值 { str=(LinkString)malloc(sizeof(Node));//创建新结点来保存值 str->data=p->data;//复制 r->next=str;//最后一个连接新的结点 r=str;//改变尾指针的指向 } p=p->next;//t串往后走 } while(q!=NULL)//如果s串够长，比t串还长就释放 { p=p->next; free(q);//释放多余s的结点 q=p; } r->next=NULL;}
int length(LinkString s)//求链式串的长度{ LinkString p; int n=0; p=s->next; while(p!=NULL)//遍历链式串 { n++;//累加返回 p=p->next;//往下位移 } return n;//返回计数变量的值 } //串的连接操作void contact(LinkString s,LinkString s1,LinkString s2){ LinkString p,q,r,t; r=s; p=s1->next; q=s->next; while(p!=NULL)//遍历S1赋值给s { if(q!=NULL)//表示s已经分配了结点 ,和复制差不多 { q->data=p->data; q=q->next; r=q; } else { t=(LinkString)malloc(sizeof(Node)); //s没有分配内存需要分配 t->data=p->data; r->next=t; r=t; } p=p->next; } p=s2->next;//重新赋值p遍历s2 while(p!=NULL)//遍历s2赋值 { if(q!=NULL)//和s1是一样的道理 { q->data=p->data; q=q->next; r=q; } else { //串s原来没有分配存储空间，需要申请空间 t=(LinkString)malloc(sizeof(Node)); t->data=p->data; r->next=t; r=t; } p=p->next; } while(q!=NULL) //遍历将串s的多余的空间清除掉，可能s串很长 { p=q->next; free(q); q=p; } r->next=NULL; //最后一个指向NULL } //截取子串int substr(LinkString s,int i,int len,LinkString t){ LinkString p,q,r,u; if(i<=0 || i>length(s) || i+len-1>length(s) ) return 0; //指针指向s的第i-1个位置 int j,k; for(j=0,p=s;j<i;j++) p=p->next; for(k=0,r=t,q=t->next;k<len;k++) { if(q!=NULL) { q->data=p->data; r=q; q=q->next; } else { u=(LinkString)malloc(sizeof(Node)); u->data=p->data; r->next=u; r=u; } p=p->next; } while(q!=NULL) { p=q->next; free(q); q=p; } r->next=NULL; return 1;} //插入操作int insert(LinkString s,int i,LinkString t){ LinkString p,q,r; if(i<=0 || i>length(s)+1) return 0; //指向第i-1个位置 int j; for(j=0,p=s;j<i-1;j++) p=p->next; q=t->next; while(q!=NULL) { r=(LinkString)malloc(sizeof(Node)); r->data=q->data; r->next=p->next; p->next=r; q=q->next; p=r; } return 1;} //删除操作int deleteString(LinkString s,int i,int len){ LinkString p,q,r; if(i<=0 || i>length(s) || i+len-1>length(s) ) return 0; int j; for(j=0,p=s;j<i-1;j++) p=p->next; for(j=0;j<len;j++) { q=p->next; p->next=q->next; free(q); } return 1; } //打印输出void print(LinkString s){ LinkString p=s->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}int main(int argc, char** argv) { LinkString s1; LinkString s2; LinkString s3; s1=CreateNullString(); s2=CreateNullString(); s3=CreateNullString(); char str[100]; printf("请输入字符串：\n"); gets(str); Stringassign(s1,str); printf("链式串s1："); print(s1); printf("链式串s1的长度为：%d\n",length(s1)); assign(s2,s1); printf("链式串s2："); print(s2); printf("链式串s2删除操作(第2个位置的三个字符删除 ："); deleteString(s2,2,3); print(s2); printf("链式串连接操作连接s1和s2生成s3："); contact(s3,s1,s2); print(s3); printf("链式串插入操作(从s1的第6个位置插入s3)："); insert(s1,6,s3); print(s1); printf("链式串截取子串的功能s2（截取s3的第四个位置长度为4的字符串："); substr(s3,4,4,s2); print(s2); return 0;}
复制代码
总结：
链式串真的不是很难，都是我们之前学过的东西，换汤不换药，逻辑基本一致，现在博主觉得，线性表存储结构为什么链表要最先学，因为后面的栈，队列，串，基本上是在链表的基础上完成的，不怎么难，没有什么技术上面的问题，接下来，我就要学数组啦，关注后面的文章哦，创作不易点赞，评论，收藏哦！！❤❤❤
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【IC00】的原创文章。
原文链接:【http://xie.infoq.cn/article/f6e969b7f974e8786f75a4d86】。文章转载请联系作者。
IC00
关注
一个热爱生活，喜欢拍照的热血青年 2022-07-14 加入
一个想学习技术的小盆友，想努力更文，争取今年发100篇
评论