數(shù)據(jù)結(jié)構(gòu)C語言版 串的堆分配存儲(chǔ)表示與實(shí)現(xiàn).doc

數(shù)據(jù)結(jié)構(gòu)C語言版 串的堆分配存儲(chǔ)表示與實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)C語言版 串的堆分配存儲(chǔ)表示與實(shí)現(xiàn).txt一個(gè)人一盒煙一臺(tái)電腦過一天一個(gè)人一瓶酒一盤蠶豆過一宿。永遠(yuǎn)扛不住女人的小脾氣，女人永遠(yuǎn)抵不住男人的花言巧語。/*數(shù)據(jù)結(jié)構(gòu)C語言版 串的堆分配存儲(chǔ)表示與實(shí)現(xiàn)P76編譯環(huán)境：Dev-C+ 4.9.9.2日期：2011年2月8日 */ #include #include #include typedef structchar *ch;/ 若是非空串,則按串長(zhǎng)分配存儲(chǔ)區(qū),否則ch為NULL int length; / 串長(zhǎng)度 HString;/ 初始化(產(chǎn)生空串)字符串Tvoid InitString(HString *T)(*T).length=0;(*T).ch=NULL;/ 生成一個(gè)其值等于串常量chars的串T int StrAssign(HString *T, char *chars)int i,j;if(*T).ch)free(*T).ch); / 釋放T原有空間 i = strlen(chars); / 求chars的長(zhǎng)度i if(!i) / chars的長(zhǎng)度為0 (*T).ch = NULL;(*T).length = 0;else/ chars的長(zhǎng)度不為0 (*T).ch = (char*)malloc(i*sizeof(char); / 分配串空間 if(!(*T).ch) / 分配串空間失敗 exit(0);for(j = 0; j i; j+) / 拷貝串 (*T).chj = charsj;(*T).length = i;return 1;/ 由串S復(fù)制得串Tint StrCopy(HString *T,HString S)int i; if(*T).ch)free(*T).ch); / 釋放T原有空間 (*T).ch=(char*)malloc(S.length*sizeof(char); / 分配串空間 if(!(*T).ch) / 分配串空間失敗 exit(0);for(i=0;iT,則返回值0;若S=T,則返回值=0;若ST,則返回值0int StrCompare(HString S,HString T)int i;for(i=0;iS.length & iT.length;+i)if(S.chi != T.chi)return S.chi-T.chi;return S.length-T.length;/ 返回S的元素個(gè)數(shù),稱為串的長(zhǎng)度 int StrLength(HString S)return S.length;/ 將S清為空串 int ClearString(HString *S)if(*S).ch)free(*S).ch);(*S).ch=NULL;(*S).length=0;return 1;/ 用T返回由S1和S2聯(lián)接而成的新串int Concat(HString *T,HString S1,HString S2)int i;if(*T).ch)free(*T).ch); / 釋放舊空間 (*T).length=S1.length+S2.length;(*T).ch=(char *)malloc(*T).length*sizeof(char);/分配新串的長(zhǎng)度if(!(*T).ch)exit(0);for(i=0;iS1.length;i+)/將S1接到新串T的后面(*T).chi=S1.chi;for(i=0;iS2.length;i+)/將S2接到新串T的后面(*T).chS1.length+i=S2.chi;return 1;/ 用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串。int SubString(HString *Sub, HString S,int pos,int len)int i;if(posS.length|lenS.length-pos+1)return 0;if(*Sub).ch)free(*Sub).ch); / 釋放舊空間 if(!len) / 空子串 (*Sub).ch=NULL;(*Sub).length=0;else / 完整子串 (*Sub).ch=(char*)malloc(len*sizeof(char);if(!(*Sub).ch)exit(0);for(i=0;i0)n=StrLength(S);m=StrLength(T);i=pos;while(i=n-m+1)/從第i個(gè)位置開始求與T等長(zhǎng)的子串，循環(huán)直到找到SubString(&sub,S,i,m);/從第i個(gè)位置開始求得子串if(StrCompare(sub,T)!=0)/將求得的子串與T對(duì)比，若不等則i+i;elsereturn i;return 0;/ 算法4.4/ 在串S的第pos個(gè)字符之前插入串Tsint StrInsert(HString *S,int pos,HString T) int i;if(pos(*S).length+1) / pos不合法 return 0;if(T.length) / T非空,則重新分配空間,插入T (*S).ch = (char*)realloc(*S).ch, (*S).length+T.length)*sizeof(char);if(!(*S).ch)exit(0);for(i=(*S).length-1;i=pos-1;-i) / 為插入T而騰出位置 (*S).chi+T.length=(*S).chi; for(i=0;iT.length;i+)(*S).chpos-1+i=T.chi; / 插入T (*S).length+=T.length;return 1;/ 從串S中刪除第pos個(gè)字符起長(zhǎng)度為len的子串int StrDelete(HString *S,int pos,int len)int i;if(*S).lengthpos+len-1)exit(0);for(i=pos-1;i=(*S).length-len;i+)(*S).chi=(*S).chi+len;(*S).length-=len;(*S).ch=(char*)realloc(*S).ch,(*S).length*sizeof(char);return 1;/ 用V替換主串S中出現(xiàn)的所有與T相等的不重疊的子串int Replace(HString *S,HString T,HString V)int i=1; / 從串S的第一個(gè)字符起查找串T if(StrEmpty(T) / T是空串 return 0;doi=Index(*S,T,i); / 結(jié)果i為從上一個(gè)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;void DestroyString()/ 堆分配類型的字符串無法銷毀 / 輸出T字符串void StrPrint(HString T)int i;for(i=0;iT.length;i+)printf(%c,T.chi);printf(n);int main()int i;char c,*p=God bye!,*q=God luck!;HString t,s,r;/ HString類型必需初始化InitString(&t); InitString(&s);InitString(&r);StrAssign(&t,p);printf(串t為: );StrPrint(t);printf(串長(zhǎng)為%d 串空否？%d(1:空 0:否)n,StrLength(t),StrEmpty(t);StrAssign(&s,q);printf(串s為: );StrPrint(s);i=StrCompare(s,t);if(i0)c=;printf(串s%c串tn,c);Concat(&r,t,s);printf(串t聯(lián)接串s產(chǎn)生的串r為: );StrPrint(r);StrAssign(&s,oo);printf(串s為: );StrPrint(s);StrAssign(&t,o);printf(串t為: );StrPrint(t);Replace(&r,t,s);printf(把串r中和串t相同的子串用串s代替后，串r為:n);StrPrint(r);ClearString(&s);printf(串s清空后，串長(zhǎng)為%d 空否？%d(1:空 0:否)n,StrLength(s),StrEmpty(s);SubString(&s,r,6,4);printf(串s為從串r的第6個(gè)字符起的4個(gè)字符，長(zhǎng)度為%d 串s為: ,s.length);StrPrint(s);StrCopy(&t,r);printf(復(fù)制串t為串r,串t為: );StrPrint(t);StrInsert(&t,6,s);printf(在串t的第6個(gè)字符前插入串s后，串t為: );StrPrint(t);StrDelete(&t,1,5);printf(從串t的第1個(gè)字符起刪除5個(gè)字符后,串t為: );StrPrint(t);printf(%d是從串t的第1個(gè)字符起，和串s相同的第1個(gè)子串的位置n,Index(t,s,1);printf(%d是從串t的第2個(gè)字符起，和串s相同的第1個(gè)子串的位置n,Index(t,s,2);system(pause);return 0;/*輸出效果： 串t為: God bye!串長(zhǎng)為8 串空否？0(1:空 0:否)串s為: God luck!串s串t串t聯(lián)接串s產(chǎn)生的串r為: God bye!God luck!串s為: oo串t為: o把串r中和串t相同的子串用串s代替后，串r為:Good bye!Good luck!串s清空后，串長(zhǎng)為0 空否？1(1:空 0:否)