1、/*數據結構C語言版 串的塊鏈存儲表示和實現P78編譯環(huán)境：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)/沒到隊尾，繼續(xù)復制塊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 / 繼續(xù)比較下一個字符 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后面繼續(xù)查找串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