数据结构串1.ppt

第四章 串 * * * 第一节 串的定义和抽象数据类型 定义：串是由零个或多个字符组成的有限序列。 记为：S=‘a1a2......an ’(n≥0) n为串长度。 ADT string { 数据对象: D 数据关系:R 基本操作: Strassign (S,chars); Strcopy (S,S1); Strempty(S); Strcompare(S1,S2); Strlength(S); Clearstring(S); Concat(S,S1,S2) Substring(Sub,S,pos,len); Index(S,Sub,pos); Replace(S,Sub,T); Strinsert(S,pos,Sub); Strdelete(S,pos,len); Destroystring(S); }ADT String 第二节 串的 存储表示与实现 串的定长顺序存储表示; 串的不定长堆存储表示; 串的不定长块链存储表示。 一 串的定长顺序存储表示 a1 a2 ...... an a1 a2 ...... an a1 a2 ...... an 当前串长度 Maxlength+1 a1 a2 ...... an \0 Maxlength+1 串结束符 方式1： 方式2： #define Maxstrlen 255 typedef unsingned char Sstring[Maxstrlen+1] Status substring(sub,s,pos,len) { if(pos1 ‖ poss[0] ‖len0 ‖lens[0]-pos+1) return ERROR; sub[1..len]=s[pos..pos+len-1]; sub[0]=len; return OK; } Status Index(s,sub,pos) { if(pos0) { n=strlength(s); m=strlength(sub); i=pos; while(i=n-m+1) { substring(sub1,s,i,m); if (strcompare(sub,sub1)!=0) ++i else return i } } return 0; } Status concat(t,s1,s2) { len1=s1[0];len2=s2[0]; if (len1+len2=Maxstrlen) { t[1..len1]=s1[1..len1]; t[len1+1..len1+len2]=s2[1..len2]; t[0]=len1+len2; uncut=TRUE; }else if (len1Maxstrlen) { t[1..len1]=s1[1..len1]; t[len1+1 .. Maxstrlen]=s2[1.. Maxstrlen-len1]; t[0]=Maxstrlen;uncut=FALSE; } else { t[0 .. Maxstrlen]=s1[0.. Maxstrlen]; uncut=FALSE; } return uncut } 二 串的不定长堆分配存储表示 a1 a2 ...... an a1 a2 ...... an ch len Hstring 0 n-1 通过动态存储分配为ch分配 相应长度的串空间。 typedef struct { char *ch; int length; } Hstring ; int strlength(s); { return s.length } status strassign(T,*chars) { if (T.ch) free(t.ch); for (i=0,c=chars; c; ++i, ++c); if ( ! i ) {T.ch=NULL;T.length=0;} else { if ( ! (T.ch=(char*) malloc(i*sizeof(ch