《數據結構C語言版 串的塊鏈存儲表示和實現》由會員分享，可在線閱讀，更多相關《數據結構C語言版 串的塊鏈存儲表示和實現(13頁珍藏版)》請在人人文庫網上搜索。

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).curlen。

4、=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;若S。

5、=T,則返回值=0;若Sch+js)=blank) / 跳過填補空余的字符 js+;if(js=CHUNKSIZE)ps=ps-next;js=0; / *(ps-ch+js)為S的第i個有效字符 while(*(pt-ch+jt)=blank) / 跳過填補空余的字符 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-ne。

6、xt;js=0;jt+;if(jt=CHUNKSIZE)pt=pt-next;jt=0;return S.curlen-T.curlen;/ 返回S的元素個數,稱為串的長度int StrLength(LString S)return S.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 C。

7、oncat(LString *T,LString S1,LString S2)LString a1,a2;InitString(&a1);InitString(&a2);StrCopy(&a1,S1);StrCopy(&a2,S2);(*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)C。

8、hunk *p,*q;int i,k,n,flag=1;/用來標志復制是否完成，1完成，0未完成if(posS.curlen|lenS.curlen-pos+1)return 0;n=len/CHUNKSIZE; if(len%CHUNKSIZE)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尾。

9、部的多余空間 q=(*Sub).head; / q指向Sub串即將復制的塊 i=0;/ i指示即將復制的字符在塊中的位置 p=S.head;/ p指向S串的當前塊 n=0;/ n指示當前字符在串中的序號 while(flag)for(k=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 In。

10、dex(LString S,LString T,int pos) int i,n,m;LString sub;if(pos=1 & posch+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) / 。

11、pos超出范圍 return 0;StrCopy(&t,T); / 復制T為t Zip(S); / 去掉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; / 插入。

12、t t.tail-next=q;if(q=NULL) / 插在S串后 (*S).tail=t.tail; / 改變尾指針 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。

13、=q;(*S).curlen+=t.curlen;Zip(S);/進行壓縮return 1;/ 從串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|lench+j)=blank) / 跳過填補空余的字符 j+;if(j=CHUNKSIZE) / 應轉向下一塊 p=p。

14、-next;j=0;i+; / 當前字符是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; / 串的當前長度 retur。

15、n 1;/ 用V替換主串S中出現的所有與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);r。

16、eturn 1;/ 輸出字符串T。void StrPrint(LString T)int i=0,j;Chunk *h;h=T.head;while(ich+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);Ini。

17、tString(&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為: );S。

18、trPrint(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串后，串t3為: )。

19、;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=StrInse。

20、rt(&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(串t2為: );StrPrint(t2);printf(StrCompare(t1,t2)=%dn,StrCompare(t1,t2);printf(刪除串t1中的子字符串：從第pos個字符起刪除len個字符。請輸入pos,len：);scanf。

21、(%d,%d,&pos,&len);k=StrDelete(&t1,pos,len);if(k)printf(從第%d位置起刪除%d個元素后串t1為:,pos,len);StrPrint(t1);system(pause);return 0;/*輸出效果：初始化串t1后，串t1空否？1(1:空 0:否) 串長=0出錯出錯串t1為: ABCDEFGHI串t1空否？0(1:空 0:否) 串長=9串t2為: 12345由串t1拷貝得到串t3,串t3為: ABCDEFGHI串t4為: ABCD用t2取代串t3中的t4串后，串t3為: 12345EFGHI清空串t1后，串t1空否？1(1:空 0:否) 串長=0串t1(=t2+t3)為: 1234512345EFGHI去除不必要的占位符后，串t1為: 1234512345EFGHIpos=6在串t1的第pos個字符之前插入串t2，請輸入pos: 3插入串t2后，串t1為: 121234534512345EFGHI求從t1的第pos個字符起,長度為len的子串t2,請輸入pos,len: 2,2串t2為: 21StrCompare(t1,t2)=-1刪除串t1中的子字符串：從第pos個字符起刪除len個字符。請輸入pos,len：2,2從第2位置起刪除2個元素后串t1為:1234534512345EFGHI請按任意鍵繼續. . . */。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的以串结构存储c语言版,数据结构C语言版 串的块链存储表示和实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。