《数据结构（C++版）（第二版）》课件第04章

2023年11月28日1第4章串本章学习内容4.1串的定义及运算

4.2串的存储结构

4.3串运算的实现

4.4串操作应用举例2023年11月28日24.1串的定义及运算

4.1.1基本概念1．串的定义串（string）是由零个或多个字符组成的有限序列，记作s=“a1a2…an”，其中s为串的名字，用成对的双引号括起来的字符序列为串的值，但两边的双引号不算串值，不包含在串中。ai（1≤i≤n）可以是字母、数字或其他字符。n为串中字符的个数，称为串的长度。串s=“a1a2…an”，也可以表示为s=(a1,a2,…,an)，即线性表的形式。因此，串也是一种线性表，是一种数据类型受到限制（只能为字符型）的线性表。2．空串不含任何字符的串称为空串，它的长度n=0，记为s=“”。3．空白串含有一个空格的串，称为空白串，它的长度n=1，记为s=“”或s=“ø”。2023年11月28日34．子串、主串若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。例如，串s1=“abcdefg”，s2=“fabcdefghxyz”，则s1为s2的子串，s2相对于s1为主串。另外，空串是任意串的子串，任意串是自身的子串。若一个串的长度为n，则它的子串数目为，真子串个数为（除串本身以外的子串都称为真子串）。4.1.2串的运算为描述方便，假定用大写字母表示串名，小写字母表示组成串的字符。1．赋值assign(&S,T)表示将T串的值赋给S串。2．联接concat(&S,T)表示将S串和T串联接起来，使T串接入S串的后面。3．求串长度length(T)求T串的长度。2023年11月28日44．子串substr(S,i,j,&T)表示截取S串中从第i个字符开始连续j个字符，作为S的一个子串，存入T串。5．串比较大小strcmp(S,T)比较S串和T串的大小，若S<T，函数值为负；若S=T，函数值为零；若S>T，函数值为正。6．串插入insert(&S,i,T)在S串的第i个位置插入T串。7．串删除del(&S,i,j)删除串S中从第i个字符开始连续j个字符。8．求子串位置index(S,T)求T子串在S主串中首次出现的位置，若T串不是S串的子串，则得到的位置为-1（若在顺序存储中，数组的下标从1开始，则T串不是S串的子串时，得到的位置为0）。9．串替换replace(&S,i,j,T)将S串中从第i个位置开始连续j个字符，用T串替换。2023年11月28日54.1.3串的抽象数据类型描述串的抽象数据类型可描述为：ADTstringsISData:含有n个字符a1,a2,a3,…,anOperation:voidassign(&S,T) //表示将T串的值赋给S串voidconcat(&S,T) //表示将S串和T串联接起来，使T串接入S串的后面intlength(T) //求T串的长度voidsubstr(S,i,j,&T) //表示截取S串中从第i个字符开始连续j个字符，作为S的一个子串，存入T串中intstrcmp(S,T) //比较S串和T串的大小，若S<T，函数值为负，S=T，函数值为零，S>T，函数值为正voidinsert(&S,i,T) //在S串的第i个位置插入T串voiddel(&S,i,j) //删除串S中从第i个字符开始连续j个字符intindex(S,T) //求T子串在S主串中首次出现的位置，若T串不是S串的子串，则位置为零voidreplace(&S,i,j,T) //将S串中从第i个位置开始连续j个字符，用T串替换Endstrings2023年11月28日64.2串的存储结构4.2.1顺序存储串的顺序存储结构，也称为顺序串，与第2章介绍的顺序表（线性表的顺序存储）类似。但由于串中的元素全部为字符，故顺序串的存放形式与顺序表有所区别。1．串的非紧缩存储一个存储单元中只存储一个字符，和顺序表中一个元素占用一个存储单元类似。具体形式见图4-1，设串S=“Howdoyoudo”。2．串的紧缩存储根据各机器字的长度，尽可能将多个字符存放在一个字中。假设一个字可存储4个字符，则紧缩存储具体形式见图4-2。2023年11月28日7图4-1S串的非紧缩存储图4-2S串的紧缩存储（设一个字有4个字符位置）2023年11月28日8从上面介绍的两种存储方式可知，紧缩存储能够节省大量存储单元，但对串的单个字符操作很不方便，需要花费较多的处理时间。而非紧缩存储的特点刚好相反，操作方便，但将占用较多的内存单元。3．串的字节存储前两种存储方法都是以字编址形式进行的，而字节编址方式是一个字符占用一个字节，具体形式见图4-3。图4-3S串的字节编址存储（一个字符占一个字节）2023年11月28日94．顺序串的数据类型描述constintmaxsize=maxlen; //maxlen表示串的最大容量classseqstring{public:charch[maxsize]; //存放串的值的一维数组intcurlen; //当前串的长度voidassign(&S,T) //类中的成员函数voidconcat(&S,T) intlength(T) voidsubstr(S,i,j,&T) intstrcmp(S,T) voidinsert(&S,i,T) voiddel(&S,i,j) intindex(S,T) voidreplace(&S,i,j,T) }；2023年11月28日104.2.2链式存储串的链式存储结构，也称为链串，与第2章介绍的链表（线性表的链式存储）类似，但链串的特点是链表中的结点数据域只能是字符型。1．结点大小为1的链式存储和前面介绍的单链表一样，每个结点为一个字符，链表也可以带头结点。例如S=“abcdef”的存储结构具体形式见图4-4。图4-4S串的链式存储示意图2023年11月28日112．结点大小为K的链式存储和紧缩存储类似，假设一个字中可以存储K个字符，则一个结点有K个数据域和一个指针域，若一个结点中数据域少于K个，用ø代替。例如，串S=“abcdef”的存储结构具体形式如图4-5所示。假设K=4，并且链表带头结点。图4-5S串的结点大小为4的链式存储2023年11月28日123．链串的数据类型描述（1）结点大小为1的链串与第2章单链表的定义类似，只需将data域的类型由元素类型elemtype改为字符类型char即可。classlink{public:chardata;link*next;……//类中的成员函数}2023年11月28日13（2）结点大小为k(k=4)的链串具体描述形式见图4-5。数据类型描述为：classlink4{public:chardata[5];//仅使用data[1]到data[4]存储空间

link4*next;};2023年11月28日144.2.3索引存储该方法是用串变量的名字作为关键字组织名字表（索引表），该表中存储的是串名和串值之间的对应关系。名字表中包含的项目根据不同的需要来设置，只要为存取串值提供足够的信息即可。如果串值是以链接方式存储的，则名字表中只要存入串名及其串值的链表的头指针即可。若串值是以顺序方式存放的，则表中除了存入指示串值存放的起始地址首指针外，还必须有信息指出串值存放的末地址。末地址的表示方法有几种：给出串长、在串值末尾设置结束符、设置尾指针直接指向串值末地址等。具体介绍下面两种：1．带长度的名字表在表中给出串名、串存放的起始位置及串长度，具体形式见图4-6。图4-6带长度的名字表2023年11月28日15从图4-6可知，S1的长度为7，起始位置从a开始，故S1=“abcdefg”，而S2的长度为3，起始位置从g开始，故S2=“gbc”。2．带末指针的名字表在表中给出串的名字、头指针及末指针，具体形式见图4-7。图4-7带末指针的名字表从图4-7可知，两个串的名字分别为S1和S2，而S1的头指针指向a，末指针指向g，故有S1=“abcdefg”，而S2的头指针指向g，末指针指向c，故有S2=“gbc”。2023年11月28日164.3串运算的实现4.3.1串插入1．顺序串上的插入insert(&S,i,T)要将T串插入到S串中第i个位置，则S串中第i个位置开始，一直到最后的字符，每个都要向后移动若干位，移动的位数为T串长度。算法描述如下：voidseqstring::Insert(seqstring&S,inti,seqstringT){if(S.curlen+T.curlen>=maxsize)cout<<"overflow";else{for(intj=S.curlen-1;j>=i;j--)S.ch[j+T.curlen]=s.ch[j]; //元素后移T.curlen位

for(j=0;j<T.curlen;j++)S.ch[j+i]=T.ch[j]; //插入元素T到S中

S.curlen=S.curlen+T.curlen; //表长度增加

}}设n为S串长度，m为T串长度，则该算法的时间复杂度为O(n+m)。2023年11月28日172．链串的插入insert(&S,i,T)仅考虑结点大小为1的链串，要在第i个位置插入，先用一个指针指向S串的第i-1个位置，然后在T串中用另一个指针指向最后，算法描述如下：voidlink::Insert(link*S,inti,link*T){link*P,*Q;intj=0;P=S;while(P!=NULL)&&(j<i-1) //查找S中第i-1个结点位置{j++;P=P->next;}Q=T;while(Q->next!=NULL)Q=Q->next; //查找T串最后一个元素if(P!=NULL) //插入{Q->next=P->next;P->next=T->next; //去掉T串的头结点}elsecout<<"error!" //找不到插入位置}该算法花费的时间主要在查找上，时间复杂度为O(n+m)。2023年11月28日184.3.2串删除1．顺序串的删除del(&S,i,j)删除S串中从第i个位置开始连续j个字符，可以分成三种情形讨论：（1）若i值不在串长度范围内，不能删除；（2）从i位置开始到最后的字符数目不足j个，删除时，不需移动元素，只需修改串长度即可；（3）i和j都可以满足需求。算法描述如下：voidseqstring::delete(seqstring&s,inti,intj){if((i<0)||(i>=s.curlen))cout<<"error"; //i值不在串值范围内，不能删除

elseif(s.curlen-i+1<j)s.curlen=i-1; //从i位置开始到最后的字符数目不足j个，删除时

//不需移动元素，只修改串长度即可else{for(intk=i+j;k<=s.curlen;k++)s.ch[k-j]=s.ch[k]; //元素前移j位

s.curlen=s.curlen–j; //表长度减j}}该算法的时间复杂度为O(n)。2023年11月28日192．链串的删除del(&S,i,j)和顺序串的删除一样，也可以分三种情形来讨论。算法描述如下：voidlink::delete(link*S,inti,intj){link*P,*Q;intk=0;P=S;while(P!=NULL)&&(k<i-1) //查找第i-1位置

{k++;P=P->next;}Q=P;while(Q!=NULL)&&(k<i+j) //查找第i+j位置{k++;Q=Q->next;}if(P!=NULL) //保证i合法{if(Q!=NULL)P->next=Q;elseP->next=NULL;}elsecout<<"error";}该算法的时间复杂度为O(n)。2023年11月28日204.3.3子串定位1．顺序串上的子串定位运算index(S,T)子串的定位运算通常称为串的模式匹配，是串处理中最重要的运算之一。设串s=“a1a2…an”，串T=“b1b2…bm”（m≤n），子串定位是要在主串S中找出一个与子串T相同的子串。通常把主串S称为目标，把子串T称为模式，把从目标S中查找模式为T的子串的过程称为“模式匹配”。匹配有两种结果出现：若S中有模式为T的子串，就返回该子串在S中的位置，当S中有多个模式为T的子串，通常只要找出第一个子串即可，这种情况称为匹配成功，若S中无模式为T的子串，返回值为-1（若数组下标从1开始，返回值为0），称为匹配失败。模式匹配过程如下图所示，假设S=“abababac”，T=“abac”。2023年11月28日21（a）第一趟匹配s3

t3（b）第二趟匹配s1

t0（c）第三趟匹配s5

t3（d）第四趟匹配s3

t0（e）第五趟匹配成功2023年11月28日22模式匹配算法如下：intseqstring::INDEX(seqstringS,seqstringT){inti=0,j=0;while((i<S.curlen)&&(j<T.curlen))if(S.ch[i]==T.ch[j]){i++;j++;}else{i=i-j+1; //将i指针回溯

j=0;}if(j>=T.curlen)return(i-T.curlen);elsereturn(-1); } //匹配失败}该算法的最好时间复杂度为O(n+m)，最坏时间复杂度为O(n

m)。2023年11月28日232．链串上的子串定位运算index(S,T)链串上的子串定位运和顺序串上的子串定位运算类似，但返回的值不是位置，而是位置指针。若匹配成功，则返回T串在S串中的地址（指针），若匹配不成功，则返回空指针。算法描述如下：link*link::index(link*S,link*T) //假设两个链串都带头结点{link*P,*Q,*R;P=S->next;Q=T->next;R=P;while(P!=NULL)&&(Q!=NULL)if(P->data==Q->data){P=P->next;Q=Q->next;}else{R=R->next; //指针回溯

P=R;Q=T->next;}if(Q==NULL) //匹配成功

rerurnR;elsereturnNULL; //匹配失败}该算法的时间复杂度与顺序串上的运算相同。2023年11月28日244.4串操作应用举例4.4.1文本编辑文本编辑程序是一个面向用户的系统服务程序，广泛用于源程序的输入和修改，甚至用于报刊和书籍的编辑排版，以及办公室的公文书信起草和润色。文本编辑的实质是修改字符数据的形式或格式。虽然各种文本编辑程序的功能强弱不同，但是其基本操作是一致的，一般都包括串的查找、插入和删除等。为了编辑的方便，用户可以利用换页符和换行符把文件划分为若干页