资源描述：
《数据结构第四章串》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第4章串4.1串的基本概念4.2串的基本运算和存储结构4.3串的模式匹配算法4.1串的基本概念串是由多个或零个字符组成的有限序列，记作S=“a1a2a3…an”(n>=0)其中，S是串名字，“a1a2a3…an”是串值ai是串中字符，n是串的长度，表示串中字符的数目。空串：长度为零的串称为空串记作“”子串：串中任意个连续的字符组成的子序列主串：包含子串的串。字符在串中的位置：字符在序列中的序号子串在串中的位置：子串的第一个字符在主串中的位置4.2串的基本运算和存储结构4.2.1串的基本运算4.2.2串的存储结构1.顺序存储每个串预先分配一个固定长度的存储区域。Chars[m
2、axsize];thisisastring …实际串长可在所分配的固定长度区域内变动在串值后加入” ”表示结束，此时串长为隐含值用定长数组描述：#definemaxsize32Typedefsturct{charch[maxsize];intcurlen;}seqstring;012345678910111213141516…maxsize-12.链接存储Typedefstructlinknode{chardata;structlinknode*next;}linkstring;linkstring*s;[注]：存储密度3.索引存储带长度的名字表带末指针的名字表带特征位
3、的名字表带位移量的名字表带长度的名字表Typedefsturct{charname[maxsize];intlength;char*stadr;}lnode;S17S23.........NameLengthstadr…abcdefgbcd…例：S1=“abcdefg”S2=“bcd”带末指针的名字表Typedefsturct{charname[maxsize];char*stadr,*enadr;}enode;S1S2.........Nameenadrstadr…abcdefgbcd…带特征位的名字表Typedefsturct{charname[maxsize];int
4、tag;union{char*stadr;charvalue[4];}uval;}tagnode;S10S21bcd .........NametagStadr/value…abcdefg …带位移量的名字表Typedefsturct{charname[maxsize];char*stadr,*enadr;intoffset1,offset2;}onode;S100S2-31………………abcdefg…nameenadroffset2stadroffset1串的基本运算串赋值：＝例：S=“abc”S1=SS=“”串联接：strcat(ST1,ST2)例：ST1=“abc
5、”ST2=“efg”strcat(ST1,ST2)则ST1=“abcdefg”求串长：strlen(S)例：ST1=“abc”则strlen(ST1)=3strlen(“”)=0求子串：substr(S,i,j)1<=i<=strlen(S),j>=0例：substr(“abcd”,2,2)=“bc”substr(“abcd”,3,3)=“cd”串比较：strcmp(S,T)串插入：insert(S1,i,S2)S1=“ABCD”insert(S1,2,”abc”)则S1=“ABabcCD”strcmp(“this”,”there”)>0strcmp(“the”,”ther
6、e”)<0Strmp(“this”,”this”)=0串删除：delete(S1,i,j)S1=“ABCD”delete(S1,2,2)则S1=“AD”子串定位：index(S1,S2)index(“abcdbc”,”bc”)=2index(“abcdbc”,”ac”)=0置换：replace(S1,i,j,S2)S1=“ABCDE”,S2=“abc”replace(S1,2,1,S2)S1=“AabcCDE”StatusStrInsert(HString&S,intpos,HStringT)//在串S的第pos个位置前插入串S{inti;if(pos<1
7、
8、pos>S.l
9、ength+1)returnERROR;if(T.length){if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char))))exit(OVERFLOW);for(i=S.length-1;i>=pos-1;--i){S.ch[i+T.length]=S.ch[i];}for(i=0;i<=T.length-1;i++)S.ch[pos-1+i]=T.ch[i];S.length+=T.length;}returnOK;}StatusStrAss
