// c4-3.h 串的塊鏈存儲結構(見圖4.7) #define CHUNK_SIZE 4 // 可由用戶定義的塊大小 struct Chunk {char ch[CHUNK_SIZE];Chunk *next; }; struct LString {Chunk *head,*tail; // 串的頭和尾指針int curlen; // 串的當前長度 };

圖48 是根據c4-3.h 定義的串“ABCDEFGHI”的一種可能的存儲形式(“#”作為
填補空余的字符，不計為串的字符)。

// bo4-3.cpp 串采用塊鏈存儲結構(由c4-3.h定義)的基本操作(15個) #define DestroyString ClearString // DestroyString()與ClearString()作用相同 void InitString(LString &T) { // 初始化(產生空串)字符串T。另加(見圖4.9)T.curlen=0;T.head= T.tail=NULL; } Status StrAssign(LString &T,char *chars) { // 生成一個其值等于chars的串T(要求chars中不包含填補空余的字符)。成功返回OK；否則返回ERRORint i,j,k,m;Chunk *p,*q;i=strlen(chars); // i為串的長度if(!i||strchr(chars,blank)) // 串長為0或chars中包含填補空余的字符return ERROR;T.curlen=i;j=i/CHUNK_SIZE; // j為塊鏈的結點數if(i%CHUNK_SIZE)j++;for(k=0;k<j;k++){p=(Chunk*)malloc(sizeof(Chunk)); // 生成塊結點if(!p) // 生成塊結點失敗return ERROR;for(m=0;m<CHUNK_SIZE&&*chars;m++) // 給塊結點的數據域賦值*(p->ch+m)=*chars++;if(k==0) // 第一個鏈塊T.head=q=p; // 頭指針指向第一個鏈塊else{q->next=p;q=p;}if(!*chars) // 最后一個鏈塊{T.tail=q;q->next=NULL;for(;m<CHUNK_SIZE;m++) // 用填補空余的字符填滿鏈表*(q->ch+m)=blank;}}return OK; } Status ToChars(LString T,char* &chars) { // 將串T的內容轉換為字符串，chars為其頭指針。成功返回OK；否則返回ERROR。另加Chunk *p=T.head; // p指向第1個塊結點int i;char *q;chars=(char*)malloc((T.curlen+1)*sizeof(char));if(!chars||!T.curlen) // 生成字符串數組失敗或串T長為0return ERROR;q=chars; // q指向chars的第1個字符while(p) // 塊鏈沒結束{for(i=0;i<CHUNK_SIZE;i++)if(p->ch[i]!=blank) // 當前字符不是填補空余的字符*q++=(p->ch[i]); // 賦給q所指字符空間p=p->next;}chars[T.curlen]=0; // 串結束符return OK; } Status StrCopy(LString &T,LString S) { // 初始條件：串S存在// 操作結果：由串S復制得串T，去掉填補空余的字符。成功返回OK；否則返回ERRORchar *c;Status i;if(!ToChars(S,c)) // c為串S的內容return ERROR;i=StrAssign(T,c); // 將串S的內容賦給Tfree(c); // 釋放c的空間return i; } Status StrEmpty(LString S) { // 初始條件：串S存在。操作結果：若S為空串，則返回TRUE；否則返回FALSEif(S.curlen) // 非空return FALSE;elsereturn TRUE; } int StrCompare(LString S,LString T) { // 若S>T，則返回值>0；若S=T，則返回值=0；若S<T，則返回值<0char *s,*t;Status i;if(!ToChars(S,s)) // s為串S的內容return ERROR;if(!ToChars(T,t)) // t為串T的內容return ERROR;i=strcmp(s,t); // 利用C的庫函數free(s); // 釋放s，t的空間free(t);return i; } int StrLength(LString S) { // 返回S的元素個數，稱為串的長度return S.curlen; } void ClearString(LString &S) { // 初始條件：串S存在。操作結果：將S清為空串Chunk *p,*q;p=S.head;while(p){q=p->next;free(p);p=q;}S.head=S.tail=NULL;S.curlen=0; } Status Concat(LString &T,LString S1,LString S2) { // 用T返回由S1和S2聯接而成的新串(中間可能有填補空余的字符)LString a1,a2;Status i,j;InitString(a1);InitString(a2);i=StrCopy(a1,S1);j=StrCopy(a2,S2);if(!i||!j) // 至少有1個串拷貝不成功return ERROR;T.curlen=S1.curlen+S2.curlen; // 生成串TT.head=a1.head;a1.tail->next=a2.head; // a1,a2兩串首尾相連T.tail=a2.tail;return OK; } Status SubString(LString &Sub, LString S,int pos,int len) { // 用Sub返回串S的第pos個字符起長度為len的子串。// 其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1char *b,*c;Status i;if(pos<1||pos>S.curlen||len<0||len>S.curlen-pos+1) // pos或len值不合法return ERROR;if(!ToChars(S,c)) // c為串S的內容return ERROR;b=c+pos-1; // b指向串c中串Sub內容的首地址b[len]=0; // Sub結束處賦0(字符串結束符)i=StrAssign(Sub,b); // 將串b的內容賦給Subfree(c);return i; } int Index(LString S,LString T,int pos) { // T為非空串。若主串S中第pos個字符之后存在與T相等的子串，// 則返回第一個這樣的子串在S中的位置，否則返回0int i,n,m;LString sub;if(pos>=1&&pos<=StrLength(S)) // pos滿足條件{n=StrLength(S); // 主串長度m=StrLength(T); // 串T長度i=pos;while(i<=n-m+1){SubString(sub,S,i,m); // sub為從S的第i個字符起，長度為m的子串if(StrCompare(sub,T)) // sub不等于T++i;elsereturn i;}}return 0; } Status StrInsert(LString &S, int pos,LString T) { // 1≤pos≤StrLength(S)+1。在串S的第pos個字符之前插入串Tchar *b,*c;int i,j;Status k;if(pos<1||pos>S.curlen+1) // pos的值超出范圍return ERROR;if(!ToChars(S,c)) // c為串S的內容return ERROR;if(!ToChars(T,b)) // b為串T的內容return ERROR;j=(int)strlen(c); // j為串S的最初長度c=(char*)realloc(c,(j+strlen(b)+1)*sizeof(char)); // 增加c的存儲空間for(i=j;i>=pos-1;i--)c[i+strlen(b)]=c[i]; // 為插入串b騰出空間for(i=0;i<(int)strlen(b);i++) // 在串c中插入串bc[pos+i-1]=b[i];InitString(S); // 釋放S的原有存儲空間k=StrAssign(S,c); // 由c生成新的串Sfree(b);free(c);return k; } Status StrDelete(LString &S,int pos,int len) { // 從串S中刪除第pos個字符起長度為len的子串char *c;int i;Status k;if(pos<1||pos>S.curlen-len+1||len<0) // pos，len的值超出范圍return ERROR;if(!ToChars(S,c)) // c為串S的內容return ERROR;for(i=pos+len-1;i<=(int)strlen(c);i++)c[i-len]=c[i]; // c為刪除后串S的內容InitString(S); // 釋放S的原有存儲空間k=StrAssign(S,c); // 由c生成新的串Sfree(c);return k; } Status Replace(LString &S,LString T,LString V) // 此函數與串的存儲結構無關 { // 初始條件：串S，T和V存在，T是非空串// 操作結果：用V替換主串S中出現的所有與T相等的不重疊的子串int i=1; // 從串S的第一個字符起查找串Tif(StrEmpty(T)) // T是空串return ERROR;do{i=Index(S,T,i); // 結果i為從上一個i之后找到的子串T的位置if(i) // 串S中存在串T{StrDelete(S,i,StrLength(T)); // 刪除該串TStrInsert(S,i,V); // 在原串T的位置插入串Vi+=StrLength(V); // 在插入的串V后面繼續查找串T}}while(i);return OK; } void StrPrint(LString T) { // 輸出字符串T。另加int i=0,j;Chunk *h;h=T.head;while(i<T.curlen){for(j=0;j<CHUNK_SIZE;j++)if(*(h->ch+j)!=blank) // 不是填補空余的字符{printf("%c",*(h->ch+j));i++;}h=h->next;}printf("\n"); }

// main4-3.cpp 檢驗bo4-3.cpp的主程序 char blank='#'; // 全局變量，用于填補空余 #include"c1.h" #include"c4-3.h" #include"bo4-3.cpp" void main() {char *s1="ABCDEFGHI",*s2="12345",*s3="",*s4="asd#tr",*s5="ABCD";Status k;int pos,len;LString t1,t2,t3,t4;InitString(t1);InitString(t2);printf("初始化串t1后，串t1空否？%d(1:空0:否) 串長=%d\n",StrEmpty(t1),StrLength(t1));k=StrAssign(t1,s3);if(k==ERROR)printf("出錯\n"); // 不能生成空串k=StrAssign(t1,s4);if(k==ERROR)printf("出錯\n"); // 不能生成含有變量blank所代表的字符的串k=StrAssign(t1,s1);if(k==OK){printf("串t1為");StrPrint(t1);}elseprintf("出錯\n");printf("串t1空否？%d(1:空0:否) 串長=%d\n",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為");StrPrint(t3);ClearString(t1);printf("清空串t1后，串t1空否？%d(1:空0:否) 串長=%d\n",StrEmpty(t1),StrLength(t1));Concat(t1,t2,t3);printf("串t1(=t2+t3)為");StrPrint(t1);pos=Index(t1,t3,1);printf("pos=%d\n",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("串t2為");StrPrint(t2);printf("StrCompare(t1,t2)=%d\n",StrCompare(t1,t2));printf("刪除串t1中的子字符串：從第pos個字符起刪除len個字符。請輸入pos,len：");scanf("%d,%d",&pos,&len);k=StrDelete(t1,pos,len);if(k){printf("從第%d位置起刪除%d個元素后串t1為",pos,len);StrPrint(t1);}DestroyString(t1); // 銷毀操作同清空 }
代碼的運行結果如下：

/* 初始化串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 pos=6 在串t1的第pos個字符之前插入串t2，請輸入pos: 1 插入串t2后，串t1為123451234512345EFGHI 求從t1的第pos個字符起,長度為len的子串t2,請輸入pos,len: 3,2 串t2為34 StrCompare(t1,t2)=-1 刪除串t1中的子字符串：從第pos個字符起刪除len個字符。請輸入pos,len：6,15 從第6位置起刪除15個元素后串t1為12345 Press any key to continue*/
由bo4-3.cpp 可見，串的塊鏈存儲結構優勢很少，一般不用。

轉載于:https://www.cnblogs.com/KongkOngL/p/3945955.html

總結

以上是生活随笔為你收集整理的串的块链存储结构的全部內容，希望文章能夠幫你解決所遇到的問題。

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