数据结构C语言动态顺序串，相比于静态顺序串只是多了能增加最大容纳量函数的操作。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define StrSize 20 //动态顺序串当前最大长度 typedef struct { char *ch;//数据域 int length;//串长 int MaxSize;//最大容量 }SString; void InitString(SString &S)//初始化串 { S.ch = (char *)malloc(sizeof(char )*StrSize+1);//申请一个长度为StrSize+1的连续空间 if(S.ch == NULL)//判断是否分配到 printf("EROOR!\n"); else { S.length = 0;//串长为0 S.MaxSize = StrSize;//最大容纳量为当前最大长度 } } int StrAssign(SString &S,char chars[])//串的赋值，使数组chars[]中的数据元素填入串S中 { int i=0; while(chars[i])//利用循环，使对串中的每一个值进行一对一赋值，当chars[i]等于空时，循环结束 { if(i>=S.MaxSize)//如果超出最大容纳量，跳出循环 { printf("ERROR!\n"); break; } S.ch[i+1] = chars[i];//串的存储是从1开始的，而数组元素的存储是从0开始的 i++; } S.length = i;//长度便是i return 0; } int IsEmpty(SString S)//判断串是否为空，如果为空返回1，否则返回0 { if(S.length) return 0; return 1; } void OutputStr(SString S)//打印串 { if(IsEmpty(S))//判断是否为空串 { printf("ERROR!\n"); exit(1); } int i; for(i=1;i<=S.length;i++)//利用循环一个一个输出，串时从1开始的 printf("%c ",S.ch[i]); printf("\n"); } int Strcopy(SString &T,SString S)//串S的copy(复制)，使串S中的数据复制到串T中 { if(IsEmpty(T)==0)//判断串T是否为空 { printf("ERROR!\n");//如果非空，结束此函数，并打印ERROR return 0; } int i; for(i=1;i<=S.length;i++)//利用循环对空串T赋值 { T.ch[i] = S.ch[i]; } T.length = S.length;//因为是拷贝，所以串T长度等于串S长 return 0; } int StrCompare(SString S,SString T)//比较串S和串T的大小， { int i; for(i=1;i<=S.length&&i<=T.length;i++)//利用循环找出 从第一个元素开始，出现不相同元素的位置 ，循环终止条件是出现一个串比较到最后， if(S.ch[i] != T.ch[i]) return S.ch[i]-T.ch[i];//出现不同位置，直接返回其相减的值，其值时ASCII码对应数相减 return S.length - T.length;//如果没出现，直接输出串长相减 } int SubString(SString &T,SString S,int i,int len)//求子串 { if(IsEmpty(T)==0)//判断串T是否为空 { printf("ERROR!\n");//如果非空，结束此函数，并打印ERROR return 0; } if(i<1||i>S.length)//判断位置是否错误 { printf("位置错误！\n"); return 0; } if(i+len > S.length+1)//判断所求子串是否在串S的范围内 { printf("ERROR!\n"); return 0; } int j=1,a=i; for( ;i<a+len;i++)//利用循环赋值 { T.ch[j] = S.ch[i]; j++; } T.length = len;//子串长为len return 0; } int StrInset(SString &S,SString T,int i)//串的插入，使串T插入到串S的第i个位置 { if(S.length+T.length>S.MaxSize)//判断两个串插入到一个串时是否超出最大值 { printf("ERROR!\n"); return 0; } if(i<1||i>S.length+1)//判断插入位置i是否合理 { printf("ERROR!\n"); return 0; } SString L; InitString(L);//重新申请一个串 L.length = S.length+T.length;//使串S和串T都插入到重新申请的串L中 int j=1; for( ;j<i;j++)//在串S的第i位之前的数据导入串L L.ch[j] = S.ch[j]; for( j=1;j<=T.length;j++)//串L第i位开始，导入串T L.ch[i+j-1] = T.ch[j]; for( j=i+T.length;j<=L.length;j++)//使未导入串L的串S剩余部分导入 L.ch[j] = S.ch[j-T.length]; S = L;//输出S return 0; } int StrDelete(SString &S,int i,int len)//串S的删除，删除串S从第i位开始长度为len的子串，并返回S { if(i<1||i>S.length)//判断删除位置i是否合理 { printf("ERROR!\n"); return 0; } if(i+len>S.length+1)//判断所删除子串是否在串S的范围内 { printf("ERROR!\n"); return 0; } for( ;i<S.length-len+1;i++) S.ch[i] = S.ch[i+len]; S.length = S.length-len;//长度变为删除之后的长度 return 0; } void Nextval(SString T,int nextval[])//求nextval值函数 { int i=1,j=0; nextval[1]=0; while(i<T.length) { if(j==0||T.ch[i]==T.ch[j]) { i++; j++; if(T.ch[i]!=T.ch[j]) nextval[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; } } int KMP(SString S,SString T)//求子串位置，KMP算法 { int i=1, j=1;//初始化 int nextval[T.length+1];//nextval数组是从1开始存数的，所以长度加1 Nextval(T,nextval);//调用 next函数修正值函数 while(i<=S.length&&j<=T.length)//两个串均为比较到串尾 { if(S.ch[i]!=T.ch[j])//指针后退重新开始匹配 { if(j == 1)//避开死循环 i++; else j = nextval[j]; } else//继续比较后继字符 { j++; i++; } } if(j<=T.length)//匹配失败 return 0; return i-j+1;//匹配成功，并返回其值 } int IncreaseStr(SString &S,int len)//增加串的最大容纳量，使其增大len（和静态顺序串的唯一区别） { int i, a = S.length;//使串S的长度固定为a char* p;//创建一个指针 p = S.ch;//使其指向串S的基地址 S.ch = (char*)malloc(sizeof(char)*(StrSize+len+1));//重新对串S进行初始化，并使申请的空间变大 S.MaxSize = StrSize+len;//最大容纳量增加 S.length = a;//使串S的长度回到最开始的长度 for(i=1;i<=a;i++)//利用循环使旧的串中的数据赋值给新串中 S.ch[i] = p[i]; free(p); //释放旧串的空间 return 0; } int main() { char a[] = "jdigohsdiofghhsa"; char b[] = "gohsdi"; //定义数组a[],b[],并赋值 SString S; SString T; //创建串T和串S InitString(S); InitString(T); //初始化串T和串S StrAssign(S,a); //使数组a[]中的数据填入串s中 StrAssign(T,b); //使数组b[]中的数据填入串T中 OutputStr(S); //打印串S //Strcopy(T,S); //使串S中的数据填入空串T中 //SubString(T,S,10,4); //使串S中从第i个位置开始长度为len的子串，填入到空串T中 OutputStr(T); //打印串T printf("%d\n",StrCompare(S,T)); //比较串T和串S的大小 IncreaseStr(S,19); //增加串S的最大容量，增加了len StrInset(S,T,8); //使串T插入到串S的第i个位置 OutputStr(S); StrDelete(S,14,6); //删除串S的从第i个位置开始长度为len的子串 OutputStr(S); printf("%d\n",KMP(S,T)); //查找子串位置，输出的是子串T在主串S中的位置 free(S.ch);//释放空间 return 0; }（完）
