《《数据结构（C++版）（第二版）》-李根强-电子教案 第04章》由会员分享，可在线阅读，更多相关《《数据结构（C++版）（第二版）》-李根强-电子教案 第04章（27页珍藏版）》请在金锄头文库上搜索。
1、2019年5月24日,1,第4章 串,本章学习内容,4.1 串的定义及运算,4.2 串的存储结构,4.3 串运算的实现,4.4 串操作应用举例,2019年5月24日,2,4.1 串的定义及运算,4.1.1 基本概念,1串的定义,串（string）是由零个或多个字符组成的有限序列，记作s=“a1a2an”，其中s为串的名字，用成对的双引号括起来的字符序列为串的值，但两边的双引号不算串值，不包含在串中。ai（1in）可以是字母、数字或其他字符。n为串中字符的个数，称为串的长度。 串s=“a1a2an”，也可以表示为s=(a1,a2,an)，即线性表的形式。因此，串也是一种线性表，是一种数据类型受到
2、限制（只能为字符型）的线性表。,2空串,不含任何字符的串称为空串，它的长度n=0，记为s=“”。,3空白串,含有一个空格的串，称为空白串，它的长度n=1，记为s=“ ” 或s=“”。,2019年5月24日,3,4子串、主串,若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。例如，串s1=“abcdefg”，s2=“fabcdefghxyz”，则s1为s2的子串，s2相对于s1为主串。,另外，空串是任意串的子串，任意串是自身的子串。 若一个串的长度为n，则它的子串数目为 ，真子串个数为 （除串本身以外的子串都称为真子串）。,4.1.2 串的运算,为描述方便
3、，假定用大写字母表示串名，小写字母表示组成串的字符。,1赋值assign(&S,T) 表示将T串的值赋给S串。,2联接concat(&S,T) 表示将S串和T串联接起来，使T串接入S串的后面。,3求串长度length(T) 求T串的长度。,2019年5月24日,4,4子串substr(S,i,j,&T) 表示截取S串中从第i个字符开始连续j个字符，作为S的一个子串，存入T串。,5串比较大小strcmp(S,T) 比较S串和T串的大小，若ST，函数值为正。,6串插入insert(&S,i,T) 在S串的第i个位置插入T串。,7串删除del(&S,i,j) 删除串S中从第i个字符开始连续j个字符。
4、,8求子串位置index(S,T) 求T子串在S主串中首次出现的位置，若T串不是S串的子串，则得到的位置为-1（若在顺序存储中，数组的下标从1开始，则T串不是S串的子串时，得到的位置为0）。,9串替换replace(&S,i,j,T) 将S串中从第i个位置开始连续j个字符，用T串替换。,2019年5月24日,5,4.1.3 串的抽象数据类型描述,串的抽象数据类型可描述为：,ADT strings IS Data:含有n个字符a1,a2,a3,an Operation: void assign(&S,T) /表示将T串的值赋给S串 void concat(&S,T) /表示将S串和T串联接起来，
5、使T串接入S串的后面 int length(T) /求T串的长度 void substr(S,i,j,&T) /表示截取S串中从第i个字符开始连续j个字符，作为S的一个子串，存入T串中 int strcmp(S,T) /比较S串和T串的大小，若ST，函数值为正 void insert(&S,i,T) /在S串的第i个位置插入T串 void del(&S,i,j) /删除串S中从第i个字符开始连续j个字符 int index(S,T) /求T子串在S主串中首次出现的位置，若T串不是S串的子串，则位置为零 void replace(&S,i,j,T) /将S串中从第i个位置开始连续j个字符，用T串
6、替换 End strings,2019年5月24日,6,4.2 串的存储结构,4.2.1 顺序存储,串的顺序存储结构，也称为顺序串，与第2章介绍的顺序表（线性表的顺序存储）类似。但由于串中的元素全部为字符，故顺序串的存放形式与顺序表有所区别。,1串的非紧缩存储,一个存储单元中只存储一个字符，和顺序表中一个元素占用一个存储单元类似。具体形式见图4-1，设串S=“How do you do”。,2串的紧缩存储,根据各机器字的长度，尽可能将多个字符存放在一个字中。假设一个字可存储4个字符，则紧缩存储具体形式见图4-2。,2019年5月24日,7,图4-1 S串的非紧缩存储,图4-2 S串的紧缩存储（
7、设一个字 有4个字符位置）,2019年5月24日,8,从上面介绍的两种存储方式可知，紧缩存储能够节省大量存储单元，但对串的单个字符操作很不方便，需要花费较多的处理时间。而非紧缩存储的特点刚好相反，操作方便，但将占用较多的内存单元。,3串的字节存储 前两种存储方法都是以字编址形式进行的，而字节编址方式是一个字符占用一个字节，具体形式见图4-3。,图4-3 S串的字节编址存储（一个字符占一个字节）,2019年5月24日,9,4顺序串的数据类型描述,const int maxsize=maxlen; /maxlen表示串的最大容量 class seqstring public: char chmax
8、size; /存放串的值的一维数组 int curlen; /当前串的长度 void assign(&S,T) /类中的成员函数 void concat(&S,T) int length(T) void substr(S,i,j,&T) int strcmp(S,T) void insert(&S,i,T) void del(&S,i,j) int index(S,T) void replace(&S,i,j,T) ；,2019年5月24日,10,4.2.2 链式存储,串的链式存储结构，也称为链串，与第2章介绍的链表（线性表的链式存储）类似，但链串的特点是链表中的结点数据域只能是字符型。,1结
9、点大小为1的链式存储 和前面介绍的单链表一样，每个结点为一个字符，链表也可以带头结点。例如 S=“abcdef ”的存储结构具体形式见图4-4。,图4-4 S串的链式存储示意图,2019年5月24日,11,2结点大小为K的链式存储 和紧缩存储类似，假设一个字中可以存储K个字符，则一个结点有K个数据域和一个指针域，若一个结点中数据域少于K个，用代替。例如，串S=“abcdef ”的存储结构具体形式如图4-5所示。假设K=4，并且链表带头结点。,图4-5 S串的结点大小为4的链式存储,2019年5月24日,12,3链串的数据类型描述,（1）结点大小为1的链串 与第2章单链表的定义类似，只需将dat
10、a域的类型由元素类型elemtype改为字符类型char即可。,class link public: char data ; link *next ; /类中的成员函数 ,2019年5月24日,13,（2）结点大小为k(k=4)的链串,具体描述形式见图4-5。数据类型描述为： class link 4 public: char data 5; / 仅使用data1 到data4存储空间 link4 * next ; ;,2019年5月24日,14,4.2.3 索引存储,该方法是用串变量的名字作为关键字组织名字表（索引表），该表中存储的是串名和串值之间的对应关系。名字表中包含的项目根据不同的需要
11、来设置，只要为存取串值提供足够的信息即可。如果串值是以链接方式存储的，则名字表中只要存入串名及其串值的链表的头指针即可。若串值是以顺序方式存放的，则表中除了存入指示串值存放的起始地址首指针外，还必须有信息指出串值存放的末地址。末地址的表示方法有几种：给出串长、在串值末尾设置结束符、设置尾指针直接指向串值末地址等。具体介绍下面两种：,1带长度的名字表 在表中给出串名、串存放的起始位置及串长度，具体形式见图4-6。,图4-6 带长度的名字表,2019年5月24日,15,从图4-6可知，S1的长度为7，起始位置从a开始，故S1=“abcdefg”，而S2的长度为3，起始位置从g开始，故S2=“gbc
12、”。,2带末指针的名字表 在表中给出串的名字、头指针及末指针，具体形式见图4-7。,图4-7 带末指针的名字表,从图4-7可知，两个串的名字分别为S1和S2，而S1的头指针指向a，末指针指向g，故有S1=“abcdefg”，而S2的头指针指向g，末指针指向c，故有S2=“gbc”。,2019年5月24日,16,4.3 串运算的实现,4.3.1 串插入,1顺序串上的插入insert(&S,i,T) 要将T串插入到S串中第i个位置，则S串中第i个位置开始，一直到最后的字符，每个都要向后移动若干位，移动的位数为T串长度。算法描述如下：,void seqstring :Insert (seqstrin
13、g /表长度增加 ,设n为S串长度，m为T串长度，则该算法的时间复杂度为O(n+m)。,2019年5月24日,17,2链串的插入insert(&S,i,T),仅考虑结点大小为1的链串，要在第i个位置插入，先用一个指针指向S串的第i-1个位置，然后在T串中用另一个指针指向最后，算法描述如下：,void link:Insert (link *S, int i , link *T ) link *P , *Q ; int j=0 ; P=S ; while (P!=NULL) /去掉T串的头结点 else cout “error!“ /找不到插入位置 ,该算法花费的时间主要在查找上，时间复杂度为O(
14、n+m)。,2019年5月24日,18,4.3.2 串删除,1顺序串的删除del(&S,i,j) 删除S串中从第i个位置开始连续j个字符，可以分成三种情形讨论：（1）若i值不在串长度范围内，不能删除；（2）从i位置开始到最后的字符数目不足j个，删除时，不需移动元素，只需修改串长度即可；（3）i和j都可以满足需求。算法描述如下：,void seqstring: delete (seqstring /表长度减j ,该算法的时间复杂度为O(n)。,2019年5月24日,19,2链串的删除del(&S,i,j) 和顺序串的删除一样，也可以分三种情形来讨论。算法描述如下：,void link:delet
15、e (link *S , int i, int j ) link *P, *Q; int k=0; P=S; while (P!=NULL) ,该算法的时间复杂度为O(n)。,2019年5月24日,20,4.3.3 子串定位,1顺序串上的子串定位运算index(S,T),子串的定位运算通常称为串的模式匹配，是串处理中最重要的运算之一。设串s=“a1a2an”，串T=“b1b2bm”（mn），子串定位是要在主串S中找出一个与子串T相同的子串。通常把主串S称为目标，把子串T称为模式，把从目标S中查找模式为T的子串的过程称为“模式匹配”。匹配有两种结果出现：若S中有模式为T的子串，就返回该子串在S中的位置，当S中有多个模式为T的子串，通常只要找出第一个子串即可，这种情况称为匹配成功，若S中无模式为T的子串，返回值为-1（若数组下标从1开始，返回值为0），称为匹配失败。,模式匹配过程如下图所示，假设S=“abababac”，T=“abac”。,2019年5月24日,21,（a）第一趟匹配s3t3 （b）第二趟匹配s1t0,（c）第三趟匹配s5t3 （d）第四趟匹配s3t0,（e
