数据结构(C语言版) 课件第4章.pptx

《数据结构(C语言版) 课件第4章.pptx》由会员分享，可在线阅读，更多相关《数据结构(C语言版) 课件第4章.pptx（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课前导学4.1 串类型的定义 4.2 串的表示和实现4.3*串的模式匹配算法4.4 串操作应用举例4.4.1 文本编辑4.4.2*建立词索引表第1页/共39页学习目标了解串的相关概念。掌握串的3种机内表示方法和实现，即定长顺序存储、堆分配存储和块链存储。熟悉串的操作应用。第2页/共39页4.1 串类型的定义串（string，或称字符串）：是由零个或多个字符组成的有限序列。通常记作 s=a1a2a3an(n0)其中，S是串的名，用单引号括起来的字符序列是串的值。串中字符的数目n称为串的长度。含零个字符的串称为空串(null string)，它的长度为零。第3页/共39页串的相关概念 在各种应用中

2、，空格通常是串的字符集合中的一个元素，可以出现在其他字符之间。由一个或多个空格组成的串称为空格串(blank string)，例如:和 ,它的长度为串中空格字符的个数。注意：空串和空格串的不同，例如 和分别表示长度为1的空格串和长度为0的空串。第4页/共39页串的相关概念子串：指串中任意个连续的字符组成的子序列。相应的包含子串的串称为主串。位置：对字符而言是指字符在串中的序号；对子串而言是指子串第一个字符在主串中的序号。相等：当且仅当两个串的值相等。即串长相等，且对应位置的字符相等。下面来看看对于串的抽象数据类型定义:第5页/共39页串的抽象数据类型ADT String 数据对象：Dai|ai

3、CharacterSet,i=1,2,.,n,n0 数据关系：R1|ai-1,ai D,i=2,.,n 基本操作：StrAssign(&T,chars)初始条件：chars 是串常量。操作结果：赋于串T的值为 chars。StrCopy(&T,S)初始条件：串 S 存在。操作结果：由串 S 复制得串 T。第6页/共39页串的抽象数据类型 DestroyString(&S)初始条件：串 S 存在。操作结果：串 S 被销毁。StrEmpty(S)初始条件：串 S 存在。操作结果：若 S 为空串，则返回 TRUE，否则返回 FALSE。StrCompare(S,T)初始条件：串 S 和 T 存在。操

4、作结果：若ST，则返回值0；若S=T，则返回值=0；若ST，则返回值0。串值大小是按词典次序进行比较的，如：StrCompare(data,stru)0 显然，只有在两个串的长度相等且每个字符一一对等的情况下称两个串相等。第7页/共39页串的抽象数据类型StrLength(S)初始条件：串 S 存在。操作结果：返回串 S 序列中的字符个数，即串的长度。ClearString(&S)初始条件：串 S 存在。操作结果：将 S 清为空串。Concat(&T,S1,S2)初始条件：串 S1 和 S2 存在。操作结果：用 T 返回由 S1 和 S2 联接而成的新串。“串联接”操作的结果是生成一个新的串，

5、其值是“将第二的串的第一个字符紧接在第一个串的最后一个字符之后“得到的字符序列。如操作Concat(T,man,kind)得到的结果是：T=mankind。第8页/共39页串的抽象数据类型SubString(&Sub,S,pos,len)初始条件：串S存在,1posStrLength(S)且 0lenStrLength(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。“子串”指串中任意个连续的字符组成的子序列。如：操作SubString(Sub,“commander”,4,3)得到的结果是Sub=“man”。显然必须在满足初始条件中规定的“起始位置”和“长度”

6、之间的约束关系时才能求得一个合法的子串。允许len的下限为0是由于空串也是合法串，但实际上求长度为0的子串是没有意义的。第9页/共39页串的抽象数据类型Index(S,T,pos)初始条件:串S和T存在,T 是非空串，1posStrLength(S)。操作结果:若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。包含子串的串相应地称为主串。“子串在主串中的位置”指的是子串中的第1个字符在主串中的位序。如子串man在主串commander中的位置为4。Index 操作类似于线性表的Locate操作，在S中查询和T值相同的子串，pos为查询的起始

7、位置。如：Index(This is a pen,is,pos)，若pos=1，则查询得结果为3，若 pos=4，则得结果为6，若pos=6，则得查询结果为0。第10页/共39页串的抽象数据类型Replace(&S,T,V)初始条件：串 S，T 和 V 存在，T 是非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。假设S=“abcacabcaca”，T=“abca”和V=“x”，则置换之后的S=“xcxca”。注意定义中“不重叠”三个字，若上例中的V=“ab”时，则置换后的结果应该是:S=“abcabca”，而不是“abbca”。StrInsert(&S,pos,T)初始条件

8、:串S和T存在,1posStrLength(S)1。操作结果：在串S的第pos个字符之前插入串T。例如:S=chater，T=rac，pos=4，则插入后的结果为 S=character。StrDelete(&S,pos,len)初始条件:串S存在,1posStrLength(S)-len+1。操作结果:从串S中删除第pos个字符起长度为len的子串。ADT String第11页/共39页最小操作子集 对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。但在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串复制StrCopy、串比

9、较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等6种操作构成串类型的最小操作子集:这些操作不可以利用其它操作的组合来实现,但是其它操作都可以利用这些操作的组合来实现.换句话说，如果在高级程序设计语言中设有串类型的话，提供的基本操作不能没有这6种操作，因为它们不能通过其它串操作实现。第12页/共39页最小操作子集在C中,对字符串的操作提供了以下函数,可直接使用:Strcat 把字符串str2接到str1后面.Strchr 找处str指向的字符串中第一次出现字符串ch的位置.Strcmp 比较两个字符串str1、str2的大小Strcpy 把字符串

10、str2拷贝到str1中。Strlen 统计字符串中字符个数。Strstr 找出str2字符串在str1字符串中第一次出现的位置。C还提供了更多对于字符和字符串操作的函数。第13页/共39页最小操作子集如，可利用判等、求串长和求子串等操作实现串的定位函数 Index(S,T,pos)实现Index(S,T,pos)算法的基本思想为：从主串S中取第i个字符起、长度和串T相等的子串和串T比较，若相等，则求得函数值为i，否则i值增1直至找到和串T相等的子串或者串S中不存在和T相等的子串为止。即求使下列等式StrCompare(SubString(S,i,StrLength(T),T)=0成立的i值.

11、i的初值应为pos，在找不到的情况下,i的终值应该是n-m+1,其中，n为S串的长度,m为T串的长度。算法演示第14页/共39页最小操作子集int Index(String S,String T,int pos)/T为非空串。若主串S中第 pos 个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0。if(pos 0)n=StrLength(S);m=StrLength(T);/求得串长i=pos;while(i=n-m+1)SubString(sub,S,i,m);/取得从第 i 个字符起长度为 m 的子串if(StrCompare(sub,T)!=0)+i;else

12、 return i;/找到和 T 相等的子串/while/ifreturn 0;/S 中不存在满足条件的子串/Index第15页/共39页4.2 串的表示和实现 我们说，串是一种特殊的线性表。那么，对应于线性表的存储方式，在串中也依然有顺序存储和链式存储之分。只是在串里面，将顺序存储又分为两种情况：定长顺序存储和堆分配存储。串有三种机内表示方法。4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示4.2.3 串的块链存储表示第16页/共39页4.2.1 定长顺序存储表示比之于线性表的顺序存储结构，同样用一组地址连续的存储单元存储串值的字符序列。为每一个串变量，预先分配一个固定长度的存储区域

13、，用定长数组描述如下：#define MAXSTRLEN 255 /串的最大长度为255Typedef unsigned char SStringMAXSTRLEN+1;/0号单元存放串的长度超过预定义长度的串值被舍去，称之为“截断”。第17页/共39页4.2.1 定长顺序存储表示对串的长度有两种表示方法：1、如上定义描述，以下标为0的数组分量存放串的实际长度，PASCAL语言使用这种方法。2、在串值后面加一个不计入串长的结束符号，在C中使用0表示一个串结束，当遇到0时，我们就知道这个串只有这么长了，到这里结束。但此时串长是一个隐含的值，需要我们求，不直观。在下面的讨论中我们使用第一中方式来表

14、示串的长度。我们来看看在定长的顺序存储中,怎样描述串的联接和求子串操作。第18页/共39页4.2.1 定长顺序存储表示1、串联接假设S1，S2，T都是Sstring型的串变量，且串T是由串S1、S2联结得到，即T的值前一段是S1，后一段和S2相等，则只要进行相应的“串值复制”操作即可，只是遇到超长部分需要“截取”。基于S1、S2的长度不同情况，可以分为三种：（1）S10+S20=MAXSTRLEN（2）S10 MAXSTRLEN（3）S10 MAXSTRLEN想想看为什么没有S10 MAXSTRLEN出现？第19页/共39页4.2.1 定长顺序存储表示Status Concat(Sstring

15、&T,Sstring S1,Sstring S2)if(S10+S20 MAXSTRLEN)T1S10=S1.1 S10;TS10+1S10+S20=S21s20;T0=S10+S20;uncut=TRUE;else if(S10 MAXSTRLEN)T1S10=S11S10;TS10+1 MAXSTRLEN=S21 MAXSTRLEN-S10;T0=MAXSTRLEN;uncut=FALSE;else T0 MAXSTRLEN=S10 MAXSTRLEN;uncut=FALSE;第20页/共39页4.2.1 定长顺序存储表示2、求子串求子串的过程，即为复制字符序列的过程，将串S中从第pos个

16、字符起长度为len的字符序列复制到Sub中。显然，操作中不会出现截断的情况。只要注意用户给定的位置是否越界即可。Status SubString(Sstring&Sub,Sstring S,int pos,int len)/用Sub返回串S的第pos个字符起长度为len的子串if(posS0|lenS0-pos+1)return flase;Sub1len=Spospos+len-1;Sub0=len;return ok;第21页/共39页4.2.1 定长顺序存储表示从上面两个例子可以看出，在顺序存储结构中，实现串操作其实就是“字符序列的复制”。另外还要注意“截尾法”的使用。使用截尾法的时候，

17、就有可能无法达到我们要求的将S1和S2完整联结的效果。为了解决这一问题，我们就要求串的长度时可以变的，即当当前长度不够时，可以再申请。这就是对串顺序存储的改进方法，称为“堆分配存储”。第22页/共39页4.2.2 堆分配存储表示这种存储的特点时，仍然以一组地址连续的存储单元存放字符序列，只是存储空间是在程序执行的过程中动态分配的。使用C中的malloc和realloc及free函数来处理。串的堆分配的存储表示：Typedef struct char*ch;int length;我们下面具体来看看串的插入算法在这种存储结构中是怎样实现的：第23页/共39页4.2.2 堆分配存储表示Status

18、StrInsert(Hstring&S,int pos,Hstring T)/在第pos个字符之前插入字符串Tif(posS.length+1)return error;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)/pos1后T.lengh个长度后移 S.chi+T.length=S.chi;S.chpos-1pos+T.lengh-2=T.ch0T.length-1;/插入T S.length+=T.len

19、gth;Return ok;第24页/共39页4.2.2 堆分配存储表示堆分配的抽象数据类型见P76。基本操作描述：1、生成一个值等于串常量chars的串TStrAssign(Hstring&T,char*chars)if(T.ch)free(T.ch)/确保T.ch为空，后面好给它分配空间for(i=0,c=chars;c;+i,+c)/求chars的长度，用i表示if(！i)T.ch=NULL;T.length=0;/S.ch为空else if(!(T.ch=(char*)malloc(i*sizeof(char)exit(overflow);T.ch0i-1=chars0i-1;T.le

20、ngth=i;Return ok;第25页/共39页4.2.2 堆分配存储表示2、返回S中元素个数，即串长int StrLength(Hstring S)return S.length;3、比较串的大小int StrCompare(Hstring S,Hstring T)for(i=0;iS.length&iT.length;i+)if(S.chi!=T.chi)return S.chi-T.chi;Return S.length-T.length;第26页/共39页4.2.2 堆分配存储表示4、清空串Status ClearString(Hstring&S)if(S.ch)free(S.ch

21、);S.ch=NULL;S.length=0;return ok;第27页/共39页4.2.2 堆分配存储表示5、将S1,S2联结，用T返回Concat(Hstring&T.Hstring S1,Hstring S2)if(T.ch)free(T.ch);if(!(T.ch=(char*)malloc(S1.length+S2.length)*sizeof(char)exit(overflow);T.ch0S1.length-1=S1.ch0 S1.length-1;T.length=S1.length+S2.length;T.chS1.lengthT.length-1=S2.ch0 S2.l

22、ength-1;Return ok;第28页/共39页4.2.2 堆分配存储表示6、用Sub返回串S的第pos个字符起长度为len的子串。其中1pos=SteLength(S)&0=len=StrLength(S)-pos+1;SubString(Hstring&Sub,Hstring S,int pos,int len)if(posS.length|len S.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*sizeo

23、f(char);Sub.ch0len-1=S.chpos-1pos+len-2;Sub.;ength=len;Return ok;第29页/共39页4.2.3 串的块链存储表示和线性表的链式存储结构类似，也可用链表来存储串值。但由于串结构的特殊性，串中每个数据元素是一个字符，则用链表存储时，可以像标准的单链表一样，每个节点存放一个字符，也可以每个节点存放一个固定长度的字符。如下图：从我们对于线性表的理解上来说，哪一种存储方式看起来比较明显且便于实现操作？答案是显而易见的，第一种方式符合一般线性表的表示习惯。但是，在使用的时候我们却是使用第二种比较多。这又是为什么？ABIAD#CF G H#IE

24、B#headhead第30页/共39页4.2.3 串的块链存储表示 对于这个问题我们要从存储空间利用率的角度去解答。我们引入存储密度这个概念来说明问题：在上面两种单链表结构中，串存储位就是字符所占的存储位，单个字符为8个二进制位。实际分配给每个节点的存储位是多少呢？应该是分配给字符的存储位加上分配给指针的存储位，我们知道指针里面存放的是内存单元的地址，这个地址值至少是16为，甚至更高。那么带单个字符的节点的存储密度是多少？8/(8+16)=1/3,就是说分配了3个空间，只有一个是用来存放有用的数据的，极大浪费了空间。第二种情况大家可以自己算算看，是多少？存储密度（单个节点实际分配存储位）（单个

25、节点中串值所占的存储位）第31页/共39页4.2.3 串的块链存储表示 在存储这样的“块链”（多个字符组成一个节点的数据域）时，我们通常设立两个指针，一个是我们熟悉的头指针，另一个是尾指针，这里设立尾指针的目的只是为了方便对串进行联结，没有设立双链表的意思。联结是注意去掉S1后的多余字符。#define CHUNKSIZE 80Typedef struct Chunk char chCHUNKSIZE;struct Chunk*next;Chunk;Typedef struct Chunk*head,*tail;int curlen;Lstring;由于用单链表来表示串，占用空间大，并且操作不

26、如前两种灵活，我们就不做要求。大家只要知道有这个概念就行，并且它的操作和单链表类似的，实现起来也不复杂，所以就不再详细讨论。第32页/共39页4.4 串操作应用举例4.4.1 文本编辑 正文编辑程序是一个面向用户的系统服务程序，广泛用于源程序的输入和修改，甚至用于报刊和书籍的编辑排版以及办公室的公文书信的起草和润色等。正文编辑的实质是修改字符数据的形式或格式。无论是 Microsoft word 还是 WPS，其工作的基础原理都是正文编辑。虽然各种正文编辑程序的功能强弱不同，但其基本功能大致相同，一般都包括串的查找、插入、删除和修改等基本操作。为了编辑方便起见，用户可以通过换页符和换行符将正文

27、划分为若干页和若干行(或直接划分为若干行)。在编辑程序中，则可将整个正文看成是一个正文串，页是正文串的子串，而行则是页的子串。对于下面一段C程序：第33页/共39页4.4.1 文本编辑假设有下列一段C的源程序main()float a,b,max;scanf(“%f,%f”,&a,&b);if ab max=a;else max=b;我们将此源程序看成是一个正文串，输入内存后如图所示，图中为换行符。201/当前页的起始地址第34页/共39页4.4.1 文本编辑为了管理正文串中的页和行，在进入正文编辑时，编辑程序先为正文串建立相应的页表和行表，页表的每一项列出页号和该页的起始行号，行表的每一项则

28、指示每一行的行号、起始地址和该行子串的长度。假设此例正文串只占一页，起始行号为100，则该正文串的行表如图所示。行号行号起始地址起始地址长度长度1002018101209171022262410325017104267151052823第35页/共39页4.4.1 文本编辑在正文编辑程序中设立页指针、行指针和字符指针，分别指示当前操作的页、行和字符。如果在某行内插入或删除若干字符，则要修改行表中该行的长度，若该行长度因插入而超出了原分配给它的存储空间，则要为该行重新分配存储空间，并修改该行的起始位置。例如，对上述源程序进行编辑后，其中的103行修改成：if(ab)max=a;105行修改成修改

29、后的行表如右所示。行号行号起始地址起始地址长度长度1002018101209171022262410328519104267151052822第36页/共39页4.4.1 文本编辑当插入或删除一行时必须同时对行表也进行插入和删除，若被删除的行是所在页的起始行，则还要修改页表中相应页的起始行号（应修改成下一行的行号）。为了查找方便，行表是按行号递增的顺序安排的，因此对行表进行插入或删除时需移动操作之后的全部表项。页表的维护与行表类似，在此不再赘述。由于对正文的访问是以页表和行表作为索引的，因此在删除一页或一行时，可以只对页表或行表作相应修改，不必删除所涉及的字符，这可以节省不少时间。第37页/共39页本章小结在这一章向读者介绍了串类型的定义及其实现方法。串的两个显著特点是，其一、它的数据元素都是字符，因此它的存储结构和线性表有很大不同，例如多数情况下，实现串类型采用的是“堆分配”的存储结构，而当用链表存储串值时，结点中数据域的类型不是“字符”，而是“串”，这种块链结构通常只在应用程序中使用；其二、串的基本操作通常以“串的整体”作为操作对象，而不像线性表是以“数据元素”作为操作对象。此外读者应学会善于利用高级语言中提供的串操作（如C语言中的串函数库和C+语言中的串类）进行编程，只是在应用前必须详细阅读语言所提供的使用手册。第38页/共39页谢谢您的观看！第39页/共39页