数据结构C语言版 串的块链存储表示和实现

1、/*数据结构C语言版 串的块链存储表示和实现P78编译环境：Dev-C+ 4.9.9.2日期：2011年2月12日 */ #include #include #include #include / LString.h 串的块链存储表示 #define CHUNKSIZE 4 / 可由用户定义的块大小 typedef struct Chunkchar chCHUNKSIZE;/块的数据域struct Chunk *next;/块的指针域Chunk;typedef structChunk *head,/ 串的头指针 *tail;/ 串的尾指针 int curlen;/ 串的当前长度 LString

2、;char blank = #;/ 全局变量,用于填补空余 / 初始化(产生空串)字符串T。void InitString(LString *T)(*T).curlen=0;(*T).head=NULL;(*T).tail=NULL;/ 生成一个其值等于chars的串T(要求chars中不包含填补空余的字符) / 成功返回1，否则返回0 int StrAssign(LString *T,char *chars)int i,j,k,l;Chunk *p,*q;i=strlen(chars); / i为串的长度 if(!i|strchr(chars,blank) / 串长为0或chars中包含填补

3、空余的字符 return 0;(*T).curlen=i;j=i/CHUNKSIZE;/ j为块链的结点数，块的个数 if(i%CHUNKSIZE)/不足一个块的，当成一个块即块数加1j+;for(k=0;knext=p;q=p;for(l=0;lch+l)=*chars+;if(!*chars) / 最后一个链块 (*T).tail=q;q-next=NULL;for(;lch+l)=blank;return 1;/ 由串S复制得串T(连填补空余的字符一块拷贝) int StrCopy(LString *T,LString S)Chunk *h=S.head,*p,*q;(*T).curle

4、n=S.curlen;if(h)p=(*T).head=(Chunk*)malloc(sizeof(Chunk);*p=*h; / 复制1个结点 h=h-next;while(h)/没到队尾，继续复制块q=p;p=(Chunk*)malloc(sizeof(Chunk);q-next=p;*p=*h;h=h-next;p-next=NULL;(*T).tail=p;return 1;elsereturn 0;/ 若S为空串,则返回1,否则返回0int StrEmpty(LString S)if(S.curlen) / 非空 return 0;elsereturn 1;/ 若ST,则返回值0;若

5、S=T,则返回值=0;若ST,则返回值0 int StrCompare(LString S,LString T)int i=0; / i为当前待比较字符在S,T串中的位置 Chunk *ps=S.head,*pt=T.head; / ps,pt分别指向S和T的待比较块 int js=0,jt=0; / js,jt分别指示S和T的待比较字符在块中的位序 while(iS.curlen&ich+js)=blank) / 跳过填补空余的字符 js+;if(js=CHUNKSIZE)ps=ps-next;js=0; / *(ps-ch+js)为S的第i个有效字符 while(*(pt-ch+jt)=b

6、lank) / 跳过填补空余的字符 jt+;if(jt=CHUNKSIZE)pt=pt-next;jt=0; / *(pt-ch+jt)为T的第i个有效字符 if(*(ps-ch+js)!=*(pt-ch+jt)return *(ps-ch+js)-*(pt-ch+jt);else / 继续比较下一个字符 js+;if(js=CHUNKSIZE)ps=ps-next;js=0;jt+;if(jt=CHUNKSIZE)pt=pt-next;jt=0;return S.curlen-T.curlen;/ 返回S的元素个数,称为串的长度int StrLength(LString S)return S

7、.curlen;/ 将S清为空串int ClearString(LString *S)Chunk *p,*q;/释放空间，并置空p=(*S).head;while(p)q=p-next;free(p);p=q;(*S).head=NULL;(*S).tail=NULL;(*S).curlen=0;return 1;/ 用T返回由S1和S2联接而成的新串int Concat(LString *T,LString S1,LString S2)LString a1,a2;InitString(&a1);InitString(&a2);StrCopy(&a1,S1);StrCopy(&a2,S2);(

8、*T).curlen=S1.curlen+S2.curlen;(*T).head=a1.head;a1.tail-next=a2.head;(*T).tail=a2.tail;return 1;/ 用Sub返回串S的第pos个字符起长度为len的子串。 int SubString(LString *Sub, LString S,int pos,int len)Chunk *p,*q;int i,k,n,flag=1;/用来标志复制是否完成，1完成，0未完成if(posS.curlen|lenS.curlen-pos+1)return 0;n=len/CHUNKSIZE; if(len%CHUN

9、KSIZE)n+; / n为块的个数 p=(Chunk*)malloc(sizeof(Chunk);(*Sub).head=p;/ 生成空的Sub串 for(i=1;inext=q;p=q;p-next=NULL;(*Sub).tail=p;(*Sub).curlen=len;for(i=len%CHUNKSIZE; ich+i)=blank; / 填充Sub尾部的多余空间 q=(*Sub).head; / q指向Sub串即将复制的块 i=0;/ i指示即将复制的字符在块中的位置 p=S.head;/ p指向S串的当前块 n=0;/ n指示当前字符在串中的序号 while(flag)for(k

10、=0; kch+k)!=blank)n+;if(n=pos&nnext;i=0;*(q-ch+i)=*(p-ch+k);i+;if(n=pos+len-1) / 复制结束 flag=0;break;p=p-next;return 1;/ T为非空串。若主串S中第pos个字符之后存在与T相等的子串, / 则返回第一个这样的子串在S中的位置,否则返回0 int Index(LString S,LString T,int pos) int i,n,m;LString sub;if(pos=1 & pos=StrLength(S) / pos满足条件 n=StrLength(S); / 主串长度 m=

11、StrLength(T); / T串长度 i=pos; while(i=n-m+1)SubString(&sub,S,i,m); / sub为从S的第i个字符起,长度为m的子串 if(StrCompare(sub,T)!=0) / sub不等于T +i;elsereturn i;return 0;/ 压缩串(清除块中不必要的填补空余的字符)。void Zip(LString *S)int j,n=0;Chunk *h=(*S).head;char *q;q=(char*)malloc(*S).curlen+1)*sizeof(char);while(h) / 将LString类型的字符串转换为

12、char类型的字符串 for(j=0; jch+j)!=blank)*(q+n)=*(h-ch+j);n+;h=h-next;/h指向下一个块*(q+n)=0;/ 串结束符 ClearString(S);/ 清空S StrAssign(S,q); / 重新生成S / 在串S的第pos个字符之前插入串T int StrInsert(LString *S,int pos,LString T)int i,j,k;Chunk *p,*q;LString t;if(posStrLength(*S)+1) / pos超出范围 return 0;StrCopy(&t,T); / 复制T为t Zip(S);

13、/ 去掉S中多余的填补空余的字符 i=(pos-1)/CHUNKSIZE; / 到达插入点要移动的块数 j=(pos-1)%CHUNKSIZE; / 到达插入点在最后一块上要移动的字符数 p=(*S).head;if(pos=1) / 插在S串前 t.tail-next=(*S).head;(*S).head=t.head;else if(j=0) / 插在块之间 for(k=1;knext; / p指向插入点的左块 q=p-next; / q指向插入点的右块 p-next=t.head; / 插入t t.tail-next=q;if(q=NULL) / 插在S串后 (*S).tail=t.t

14、ail; / 改变尾指针 else / 插在一块内的两个字符之间 for(k=1;knext; / p指向插入点所在块 q=(Chunk*)malloc(sizeof(Chunk); / 生成新块 for(i=0;ich+i)=blank; / 块q的前j个字符为填补空余的字符 for(i=j;ich+i)=*(p-ch+i); / 复制插入点后的字符到q *(p-ch+i)=blank; / p的该字符为填补空余的字符 q-next=p-next;p-next=t.head;t.tail-next=q;(*S).curlen+=t.curlen;Zip(S);/进行压缩return 1;/

15、从串S中删除第pos个字符起长度为len的子串int StrDelete(LString *S,int pos,int len)int i=1; / 当前字符是S串的第i个字符(1S.curlen) Chunk *p=(*S).head; / p指向S的当前块 int j=0; / 当前字符在当前块中的位序(0CHUNKSIZE-1) if(pos(*S).curlen-len+1|len0) / pos,len的值超出范围 return 0;while(ich+j)=blank) / 跳过填补空余的字符 j+;if(j=CHUNKSIZE) / 应转向下一块 p=p-next;j=0;i+;

16、 / 当前字符是S的第i个字符 j+;if(j=CHUNKSIZE) / 应转向下一块 p=p-next;j=0; / i=pos,*(p-ch+j)为S的第pos个有效字符 while(ich+j)=blank) / 跳过填补空余的字符 j+;if(j=CHUNKSIZE) / 应转向下一块 p=p-next;j=0;*(p-ch+j)=blank; / 把字符改成填补空余的字符来删除第i个字符 i+; / 到下一个字符 j+;if(j=CHUNKSIZE) / 应转向下一块 p=p-next;j=0;(*S).curlen-=len; / 串的当前长度 return 1;/ 用V替换主串S

17、中出现的所有与T相等的不重叠的子串int Replace(LString *S,LString T,LString V)int i=1; / 从串S的第一个字符起查找串T if(StrEmpty(T) / T是空串 return 0;doi=Index(*S,T,i); / 结果i为从上一个i之后找到的子串T的位置 if(i) / 串S中存在串T StrDelete(S,i,StrLength(T); / 删除该串T StrInsert(S,i,V); / 在原串T的位置插入串V i+=StrLength(V); / 在插入的串V后面继续查找串T while(i);return 1;/ 输出字

18、符串T。void StrPrint(LString T)int i=0,j;Chunk *h;h=T.head;while(iT.curlen)for(j=0;jch+j)!=blank) / 不是填补空余的字符 printf(%c,*(h-ch+j);i+;h=h-next;printf(n);void DestroyString()/ 块链类型的字符串无法销毁 int main()char *s1=ABCDEFGHI,*s2=12345,*s3=,*s4=asd#tr,*s5=ABCD;int k;int pos,len;LString t1,t2,t3,t4;InitString(&t1

19、);InitString(&t2);printf(初始化串t1后，串t1空否？%d(1:空 0:否) 串长=%dn,StrEmpty(t1),StrLength(t1);k=StrAssign(&t1,s3);if(k=1)printf(串t1为: );StrPrint(t1);elseprintf(出错n); / 不能生成空串 k=StrAssign(&t1,s4);if(k=1)printf(串t1为: );StrPrint(t1);elseprintf(出错n); / 不能生成含有变量blank所代表的字符的串 k=StrAssign(&t1,s1);if(k=1)printf(串t1为

20、: );StrPrint(t1);elseprintf(出错n);printf(串t1空否？%d(1:空 0:否) 串长=%dn,StrEmpty(t1),StrLength(t1);StrAssign(&t2,s2);printf(串t2为: );StrPrint(t2);StrCopy(&t3,t1); printf(由串t1拷贝得到串t3,串t3为: );StrPrint(t3);InitString(&t4);StrAssign(&t4,s5);printf(串t4为: );StrPrint(t4);Replace(&t3,t4,t2);printf(用t2取代串t3中的t4串后，串t

21、3为: );StrPrint(t3);ClearString(&t1);printf(清空串t1后，串t1空否？%d(1:空 0:否) 串长=%dn,StrEmpty(t1),StrLength(t1);Concat(&t1,t2,t3);printf(串t1(=t2+t3)为: );StrPrint(t1);Zip(&t1);printf(去除不必要的占位符后，串t1为: );StrPrint(t1); pos=Index(t1,t3,1);printf(pos=%dn,pos);printf(在串t1的第pos个字符之前插入串t2，请输入pos: );scanf(%d,&pos);k=StrInsert(&t1,pos,t2);if(k)printf(插入串t2后，串t1为: );StrPrint(t1);elseprintf(插入失败！n);printf(求从t1的第pos个字符起,长度为len的子串t2,请输入pos,len: );scanf(%d,%d,&pos,&len);SubString(&t2,t1,pos,len);printf