數據結構c語言串的堆分配存儲源程序.doc

#include#include#include#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef structchar *ch;int length;HString;/初始化操作void InitString(HString *T) T-length=0; T-ch=NULL; /賦值操作Status StrAssign(HString *T,char *chars)/生成一個其值等于串常量chars的串Tint i,j;/char *c;if(T-ch)free(T-ch); /釋放T原有空間/for(i=0,c=chars; *c;+i,+c); /求chars的長度i，*c表*c!=NULLi=strlen(chars);if(!i)T-ch=NULL;T-length=0;elseT-ch=(char*)malloc(i*sizeof(char);if(!T-ch)exit(OVERFLOW);for(j=0;jchj=charsj;T-length=i;return OK;/StrAssign/串復制操作Status StrCopy(HString *T,HString S)int i;if(T-ch)free(T-ch);T-ch=(char*)malloc(S.length*sizeof(char);if(!T-ch)exit(OVERFLOW);for(i=0;ichi=S.chi;T-length=S.length;return OK;/StrCopy/判空操作Status StrEmpty(HString S)if(S.length=0&S.ch=NULL)return OK;elsereturn ERROR;/StrEmpty/求長度操作int StrLength(HString S)return S.length;/Strlength/串比較操作int StrCompare(HString S,HString T)int i;for(i=0;iS.length&ich)free(S-ch);S-ch=NULL;S-length=0;return OK;/ClearString/串連接操作Status Concat(HString *T,HString S1,HString S2)int i;if(T-ch)free(T-ch); /釋放舊空間T-ch=(char*)malloc(S1.length+S2.length)*sizeof(char);if(!T-ch)exit(OVERFLOW);for(i=0;ichi=S1.chi;T-length=S1.length+S2.length;for(i=0;ichS1.length+i=S2.chi;return OK;/Concat/求子串操作Status SubString(HString *Sub,HString S,int pos,int len) int i;if(posS.length|lenS.length-pos+1)return ERROR; 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(OVERFLOW); for(i=0;ichi=S.chpos-1+i; Sub-length=len; return OK;/SubString/求子串位置操作int Index(HString S,HString T,int pos)/ T為非空串。若主串S中第pos個字符之后存在與T相等的子串, / 則返回第一個這樣的子串在S中的位置,否則返回0 int i,m,n;HString Sub;InitString(&Sub); /一定要初始化Sub!if(pos0)n=StrLength(S);m=StrLength(T);i=pos;while(in-m+1,則找不出長度為m的子串SubString(&Sub,S,i,m); if(StrCompare(Sub,T)!=0)i+; /從位置i起取子串與T作比較else return i;/while/ifreturn 0;/Index/插入操作 Status StrInsert(HString *S,int pos,HString T)/ 1posStrLength(S)+1。在串S的第pos個字符之前插入串Tint i;if(posS-length+1)return ERROR;if(T.length)S-ch=(char*)realloc(S-ch,(S-length+T.length)*sizeof(char);if(!S-ch) exit(OVERFLOW);for(i=S-length;i=pos-1;-i) / 為插入T而騰出位置S-chi+T.length=S-chi;for(i=0;ichpos-1+i=T.chi; /插入TS-length+=T.length;return OK;/StrInsert/刪除操作Status StrDelete(HString *S,int pos,int len)int i;if(S-lengthpos+len-1)return ERROR;for(i=pos-1;ilength-len;i+)S-chi=S-chi+len;S-length-=len;S-ch=(char*)realloc(S-ch,S-length*sizeof(char);return OK;/StrDelete/輸出操作void StrPrint(HString T)int i;for(i=0;i0)printf(S1S2n);else if(StrCompare(S1,S2)0)printf(S1S2n);elseprintf(S1=S2n);printf(n連接串S1,S2得串S3：);if(Concat(&S3,S1,S2)StrPrint(S3);elseprintf(串連接失?。?;printf(串S3的長度為%d：n,StrLength(S3);printf(n用Sub返回串S3中第pos個字符起長度為len的字符：n);printf(輸入pos,len的值：n);scanf(%d%d,&pos,&len);if(SubString(&Sub,S3,pos,len)=1)printf(輸出串Sub：);StrPrint(Sub);elseprintf(序號不合法，取子串失??！n);printf(n求串Sub在串S3中的位置：n);if(Index(S3,Sub,pos)=0)printf(pos值不合法！n);elseprintf(pos值為%dn,Index(S3,Sub,pos);printf(n在串S1的第pos位置插入串S2n);printf(輸入pos的值：n);scanf(%d,&pos);if(StrInsert(&S1,pos,S2)=1)printf(輸出串S1：);StrPrint(S1);elseprint