串的链式存储： 顺序串的插入和删除操作不方便，需要移动大量的字符。因此，可采用单链表方式存储串。由于串结构的特殊性一结构中的每个数据元素是 一个字符，则在用链表存储申值时，存在个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。例如，图中(a)所示为结点大小为4 (即每个结点存放4个字符)的链表，图中(b)所示为结点大小为1的链表。当结点大小大于1时，由于串长不一定是结点大小的整倍数， 则链表中的最后一个结点不一定全被串值占满，此时通常补上“#”或其他的非串值字符(通常“#”不属于串的字符集，是一个特殊的符号)。 和单链表的操作只是多了个这个 “#define MaxSize 4”，其中的4表示图中的（a）表图。可以自行增加。
总的来说，太 难 难 难 了，可能是对我来说难。 而且还没做完整，链式串中的找子串函数写不出来**(T_T)**
我写的代码如下：
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MaxSize 4 //链表中一个结点的最大容纳值 typedef struct Chunk { char ch[MaxSize];//结点数据域 struct Chunk* next;//指针域 }Chunk; typedef struct { Chunk* head; int length;//串长度 }SString; void InitString(SString &S)//串的初始化 { S.head = (Chunk*)malloc(sizeof(Chunk));//使S.head申请一个结点空间 if(S.head == NULL)//判断是否申请到 exit(1); S.head->next = NULL;//头结点表示法（链表） S.length = 0;//长度至为0 } int StrAssign(SString &S,char chars[])//串的赋值，使数组chars[]中的数据元素填入串S中 { int i=0,j=0; Chunk* p = (Chunk*)malloc(sizeof(Chunk));//创建一个野结点，并为其申请一个结点空间 S.head->next = p;//链表尾插法，S.head为链表的头结点 p->next = NULL; while(chars[j])//利用循环，使对串中的每一个值进行一对一赋值，当chars[i]等于空时，循环结束 { if(i == MaxSize)//判断i的值是否超出或等于最大值，如果等于，对结点最大值求余 { i = i%MaxSize; Chunk* s = (Chunk*)malloc(sizeof(Chunk));//重新申请一个结点空间 p->next = s;//类似于链表尾插法 s->next = NULL; p = s; } p->ch[i] = chars[j];//赋值，i的值是在0~MaxSize之间，而j的值是总的循环次数 i++; j++; } S.length = j;//串长赋值 if(i != MaxSize)//如果链表的最后一个结点没有存满，使其剩余部分填入‘#’ for(;i<MaxSize;i++) p->ch[i] = '#'; return 0; } int IsEmpty(SString S)//判断串是否为空，如果为空返回1，否则返回0 { if(S.length == 0) return 1; return 0; } void OutputStr(SString S)//打印串 { if(IsEmpty(S))//判断是否为空串 { printf("ERROR!\n"); exit(1); } int i=0; Chunk* p = S.head->next;//创建一个指针，并指向头结点的下一个结点 while(1)//进入死循环 { if(i == MaxSize)//判断i的值是否超出或等于最大值，如果等于，对结点最大值求余 { i = i%MaxSize; p = p->next;//这里类似于链表的遍历 } if(p->next == NULL)//循环终止条件，首先先判断是否为最后一个结点 { for(;i<MaxSize;i++)//利用循环打印出最后一个结点的数据 { if(p->ch[i] == '#')//如果数据中出现“#”，跳出循环 break; printf("%c ",p->ch[i]); } break;//跳出死循环 } printf("%c ",p->ch[i]);//打印最后一个结点之前的所有结点数据 i++; } printf("\n"); } int StrCopy(SString &T,SString S)//串S的copy(复制)，使串S中的数据复制到空串T中 { if(IsEmpty(T) == 0)//判断串T是否为空 { printf("ERROR!\n"); return 0; } int i=0; S.head = S.head->next;//链的遍历，由于S链不用返回，故直接是头结点往后移进行遍历 Chunk *p = (Chunk*)malloc(sizeof(Chunk)); T.head->next = p;//创建个野结点，链T的头结点指向该结点，类似于链表的尾插法 p->next = NULL; while(1)//进入死循环 { if(i == MaxSize)//判断i的值是否超出或等于最大值，如果等于，对结点最大值求余 { i = i%MaxSize; Chunk *s = (Chunk*)malloc(sizeof(Chunk)); p->next = s;//这里创建个野结点s，类似于对链表T的尾插法 s->next = NULL; p = s; S.head = S.head->next;//这里链S类似于链表的遍历 } if(S.head->next == NULL)//判断是否到达链表S的尾端 { for(;i<MaxSize;i++)//到达链S尾结点，使尾结点数据进行赋值，并破坏死循环 p->ch[i] = S.head->ch[i]; break; } p->ch[i] = S.head->ch[i];//使链S结点上的数据赋值到链T上 i++; } T.length = S.length;//链长 return 0; } int StrCompare(SString S,SString T)//串的比较， { S.head = S.head->next;//均利用头结点进行遍历 T.head = T.head->next; int i=0,j=1; while(j<=S.length && j<=T.length)//利用循环找出 从第一个元素开始，出现不相同元素的位置 ，循环终止条件是出现一个串比较到最后， { if(i == MaxSize)//判断i的值是否超出或等于最大值，如果等于，对结点最大值求余 { i = i%MaxSize; S.head = S.head->next; T.head = T.head->next; } if(S.head->ch[i] != T.head->ch[i]) return S.head->ch[i] - T.head->ch[i];//出现不同位置，直接返回其相减的值，其值时ASCII码对应数相减 i++; j++; } return S.length - T.length;//如果没出现，直接输出串长相减 } int SubString(SString &T,SString S,int i,int len)//求子串，将串S中的从第i个位置长度为len的子串复制到空串T中 { if(IsEmpty(T) == 0)//判断串T是否为空，如果不为空结束此函数 { printf("ERROR!\n"); return 0; } if(i<1||i>S.length)//判断位置是否错误 { printf("ERROR!\n"); return 0; } if(i+len > S.length+1)//判断所求子串是否在串S的范围内 { printf("ERROR!\n"); return 0; } S.head = S.head->next; Chunk* p = (Chunk*)malloc(sizeof(Chunk)); T.head->next = p; p->next = NULL; int j=0,k=0,a; a = i; for(;j<i-1;j++)//利用循环找到串S的第i个位置 { if(k == MaxSize)//判断k的值是否超出或等于最大值，如果等于，对结点最大值求余 { k = k%MaxSize; S.head = S.head->next;//类似于链表的遍历 } k++; } for(j=0;i<a+len;i++)//将第i个位置长度为len的子串赋值给空串T { if(k == MaxSize) { k = k%MaxSize; S.head = S.head->next; } if(j == MaxSize) { j = j%MaxSize; Chunk *s = (Chunk*)malloc(sizeof(Chunk)); p->next = s; s->next = NULL; p = p->next; } p->ch[j] = S.head->ch[k]; k++; j++; } T.length = len;//串T长度为len if(j != MaxSize)//判断串T的尾结点是否存满，如果没存满，用‘#’进行填充 for(;j<MaxSize;j++) p->ch[j] = '#'; return 0; } SString StrInset(SString S,SString T,int i)//串的插入，使串T插入到串S的第i个位置，返回串S和串T组合的新串 { if(IsEmpty(T))//判断串T是否为空，如果为空结束此函数，直接返回串S { printf("ERROR!\n"); exit(1); } if(i<1||i>S.length+1)//判断插入位置i是否合理 { printf("ERROR!\n"); exit(1); } S.head = S.head->next; SString L; InitString(L);//重新申请一个串，并初始化 L.length = S.length+T.length;//合并后的串长为两串长相加 Chunk* p = (Chunk*)malloc(sizeof(Chunk));//创建一个野结点，进行串L数据的插入，类似于链表尾插法 L.head->next = p; p->next = NULL; int j=0,k=0; for( ;j<i-1;j++)//首先使串S的第i个位置之前的数据都插入到新串L中 { if(k == MaxSize) { k = k%MaxSize; S.head = S.head->next; Chunk *s = (Chunk*)malloc(sizeof(Chunk)); p->next = s; s->next = NULL; p = p->next; } p->ch[k] = S.head->ch[k]; k++; } int a=k,b=i;i=0; T.head = T.head->next; for(j=0;j<T.length;j++) //其次使串T整个插入到新串L中 { if(i == MaxSize) { i = i%MaxSize; T.head = T.head->next; } if(k == MaxSize) { k = k%MaxSize; Chunk *s = (Chunk*)malloc(sizeof(Chunk)); p->next = s; s->next = NULL; p = p->next; } p->ch[k] = T.head->ch[i]; k++; i++; } for(j=T.length+b-1;j<L.length;j++)//最后使串S剩余的部分插入新串L中 { if(a == MaxSize) { a = a%MaxSize; S.head = S.head->next; } if(k == MaxSize) { k = k%MaxSize; Chunk *s = (Chunk*)malloc(sizeof(Chunk)); p->next = s; s->next = NULL; p = p->next; } p->ch[k] = S.head->ch[a]; a++; k++; } if(k != MaxSize)//判断串L尾结点是否存满，没存满用#填充 for(;k<MaxSize;k++) p->ch[k] = '#'; //free(T.head); return L; } int StrDelete(SString &S,int i,int len)//串S的删除，删除串S从第i位开始长度为len的子串，并返回S { if(IsEmpty(S))//判断S是否为空 { printf("ERROR!\n"); return 0; } if(i<1||i>S.length)//判断删除位置i是否合理 { printf("ERROR!\n"); return 0; } if(i+len > S.length+1)//判断所删除子串是否在串S的范围内 { printf("ERROR!\n"); return 0; } int j=0,k=0; Chunk *p = S.head->next; for( ;j<i-1;j++)//找到串S的第i个位置 { if(k == MaxSize) { k = k%MaxSize; p = p->next; } k++; } Chunk *s=p; int a=k,b=i; for(i=0;i<len;i++)//其次是找到串S的第i+len的位置 { if(k == MaxSize) { k = k%MaxSize; s = s->next; } k++; } for(i=0;i<S.length-b-len+1;i++)//最后使删除部分的后端填充删除部分，数据往前挪， { if(k == MaxSize) { k = k%MaxSize; s = s->next; } if(a == MaxSize) { a = a%MaxSize; p = p->next; } p->ch[a] = s->ch[k]; a++; k++; } if(a != MaxSize)//判断串S尾结点是否存满，没存满用#填充 for(;a<MaxSize;a++) p->ch[a] = '#'; p->next = s; p->next = NULL;//当数据填充完后，释放后面的空链结点 free(s); return 0; } int main() { char a[] = "ihdhdgfidpfop"; char b[] = "djihsdgz"; SString S,T,L; InitString(S); InitString(T); //初始化 StrAssign(S,a); //将数组a的数据赋值给链串S StrAssign(T,b); //将数组b的数据赋值给链串T OutputStr(S); //打印链S printf("%d\n",S.length); //打印串S的长度 //下面的函数中的常数都是为了方便验证代码结果，可以定义为变量 //SubString(T,S,15,8); //使串S中从第i个位置开始长度为len的子串，填入到空串T中 ，其中的常数是用于测试运行结果的 //StrCopy(T,S); //使串S中的数据填入空串T中 OutputStr(T); //打印串T printf("%d\n",T.length); //打印串T的长度 StrDelete(S,2,8); //删除串S的从第i个位置开始长度为len的子串 //OutputStr(S); // L=StrInset(S,T,10); //使串T插入到串S的第i个位置 OutputStr(S); printf("%d\n",StrCompare(S,T)); //比较串T和串S的大小 free(S.head); //释放空间 free(L.head); free(T.head); return 0; }