数据结构 ch04学习.pptx

《数据结构 ch04学习.pptx》由会员分享，可在线阅读，更多相关《数据结构 ch04学习.pptx（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/171 在计算机的应用中，非数值处理问题的应用越来越多。如在汇编程序和编译程序中，源程序和目标程序都是作为一种字符串数据进行处理的。在事务处理系统中，用户的姓名和地址及货物的名称、规格等也是字符串数据。字符串一般简称为串，可以将它看作是一种特殊的线性表，这种线性表的数据元素的类型总是字符型的，字符串的数据对象约束为字符集。在线性表的基本操作中，大多以“单个元素”作为操作对象，而在串中，则是以“串的整体”或一部分作为操作对象。因此，线性表和串的操作有很大的不同。本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。本章学习导读本章学习导读第1页/共36页2023/3/172 串

2、是一种特殊的线性表，它的数据对象是字符字符字符字符集合。4.1.1 4.1.1 串的定义 串（或字符串）是由零个或多个字符组成的有限序列。一般记作：s=c0c1c2cn-1 (n0)其中：s为串名，用双引号括起来的字符序列是串的值；ci(0in-1)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；字符串字符的数目n称为串的长度。零个字符的串称为空串，通常以两个相邻的双引号来表示空串 如：s=，它的长度为零；仅由空格组成的的串称为空格串 如：s=；4.1 串及其运算第2页/共36页2023/3/173 若串中含有空格，在计算串长时，空格应计入串的长度中 如：s=Im a stu

3、dent的长度为13。注意：在C语言中，用单引号引起来的单个字符与单个字符的串是不同的，如s1=a与s2=a两者是不同的，s1表示字符，s2表示字符串。当两个串的长度相等且各对应位置上的字符都相同时，这两个串是相等的。串中任意个连续字符组成的序列称为该串的子串。包含子串的串被称为主串。例如，comcom、omom、aa和 manman都是 comcommandermander的子串。子串在主串中的位置是指子串中第一个字符在主串中的位置序号。如子串 manman在主串 comcommanmanderder中的位置为4 4。第3页/共36页2023/3/174 串是一种简单的数据结构，它的逻辑结构

4、与线性表十分相似，区别仅在于串的数据对象是字符集。串的基本运算与线性表的基本运算有很大差别。通常在串的基本运算中，以“串的整体”作为操作对象；而在线性表的基本运算中，大多以“单个元素”作为操作对象。4.1.2 串的基本运算 串的常用基本运算主要有：1Strassign(s,chars)功能：赋值运算 将串常量charschars的值赋给串变量s s。例如：执行strassign(sstrassign(s，abcd)abcd)运算之后，s s的值为 abcdabcd。第4页/共36页2023/3/1752Assign(s,t)功能：赋值运算。将串变量t t的值赋给串变量s s。例如：t=t=ab

5、cdabcd，则执行Assign(s,t)运算之后，s s的值为abcdabcd。3Equal(s,t)功能：判相等运算。若s s与t t的值相等则运算结果为1 1，否则为0 0。4Length(s)功能：求串长运算。求串 s s序列中字符的个数，即串的长度。5Concat(s,t)功能：联接运算。将串t的第一个字符紧接在串 s的最后一个字符之后，联接得到一个新串。例如s=s=man,t=,t=kind，则执行Concat(s,t)运算后得到的新串为mankind。第5页/共36页2023/3/176 6 6Insert(s,pos,t)Insert(s,pos,t)功能：插入运算，当1 1p

6、os pos Length Length(s)+1(s)+1时，在串 s s的第 pos pos 个字符之前插入串 t t。7 7Delete(s,pos,len)Delete(s,pos,len)功能：删除运算。当1 1posposLength(s)Length(s)且0 0lenlenLength Length(s)-(s)-pos+1pos+1时，从串s s中删去从第pospos个字符起长度为lenlen的子串。8 8Replace(s,pos,len,t)Replace(s,pos,len,t)功能：置换运算。当11posLength posLength(s)(s)且00lenLeng

7、th(s)-lenLength(s)-pos+1pos+1时，用串t t替换串s s中从第 pos pos 个字符起长度为lenlen的子串。对对于于串串的的基基本本操操作作，许许多多高高级级语语言言均均提提供供了了相相应应的的运运算算或或标标准库函数来实现。准库函数来实现。下下面面仅仅介介绍绍几几种种在在C C语语言言中中常常用用的的串串运运算算，其其它它的的串串操操作作见见文文件。件。第6页/共36页2023/3/177 定义下列几个变量：定义下列几个变量：char s120=“dirtreeformat”,s220=“file.mem”;char s330,*p;int result;(

8、1)求串长求串长(length)int strlen(char s);/求串的长度求串的长度 例如：例如：printf(“%d”,strlen(s1);输出输出13 （2）串复制）串复制(copy)char*strcpy(char to,char from);该函数将串该函数将串from复制到串复制到串to中，并且返回一个指向串中，并且返回一个指向串to的开始处的指针。的开始处的指针。例如：例如：strcpy(s3,s1);/s3=“dirtreeformat”第7页/共36页2023/3/178 (3)联接联接(concatenation)char strcat(char to,char f

9、rom)该函数将串该函数将串from复制到串复制到串to的末尾，并且返回一个指向串的末尾，并且返回一个指向串to的开始处的指针。的开始处的指针。例例1、求子串、求子串 求子串的过程即为复制字符序列的过程，将串求子串的过程即为复制字符序列的过程，将串S中的第中的第pos个字符开始长度为个字符开始长度为len的字符复制到串的字符复制到串T中。中。void substr(string sub,string s,int pos,int len)if(posstrlen(s)-1|len0)n=strlen(s);m=strlen(t);i=pos;while(in-m+1)substr(sub,s,i

10、,m);if(strcmp(sub,t)!=0)+i;else return(i);return(0);第9页/共36页2023/3/17104.2 串的存储结构 串是一种特殊的线性表，其存储结构与线性表的存储结构类似，只只不不过过组组成成串串的的结结点点是是单单个个字字符符。串的存储结构表示有两种方法：静态存储和动态存储 静态存储采用顺序存储结构，动态存储采用的是链式存储和堆存储结构。4.2.1 4.2.1 串的顺序存储结构及其基本运算的实现 1 1顺序存储结构顺序存储结构（静态）串的顺序存储结构是采用与其逻辑结构相对应的存储结构，将串中的各个字符按顺序依次存放在一组地址连续的存储单元里，逻

11、辑上相邻的字符在内存中也相邻。第10页/共36页2023/3/1711 类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。这是一种静态存储结构，串值的存储分配是在编译时完成的。因此，需要预先定义串的存储空间大小。如果定义的空间过大，则会造成空间浪费；如果定义的空间过小，则会限制串的某些运算，如联接、置换运算等。2基本运算在基本运算在顺序存储结构上顺序存储结构上的实现的实现在顺序存储结构中，串的类型定义描述如下：#define MaxLen;/定义能处理的最大的串长度 typedef struct char strMaxLen;/定义可容纳MaxLen个字符的字符数组 in

12、t curlen;/定义当前实际串长度 string;第11页/共36页2023/3/1712以下给出采用顺序存储结构时串的联接运算。（1）Concat(s,t)string Concat(string s,string t)/将串t的第一个字符紧接在串 s 的最后一个字符之后 string ch;int i;ch.curlen=s.curlen+t.curlen;/将s.str0s.strs.curlen-1复制到ch for(i=0;is.curlen;i+)ch.stri=s.stri;/将t.str0t.strt.curlen-1复制到ch for(i=0;it，则输出正数；如果st，

13、则输出负数。算法如下：int strcmp(string s,string t)int i,st_len;if(s.cur1en t.cur1en)/求取s和t长度短者 st_len=s.cur1en;else 第13页/共36页2023/3/1714else st_len=t.cur1en;for(i=0;(ist_len)&(s.stri=t.stri);i+);if(i=st_len)if(s.cur1en=t.cur1en)/s=t return 0;else if(s.cur1ent.cur1en)/st return 1;else return s.stri-t.stri;/st或

14、st第14页/共36页2023/3/17154.2.2 串的链式存储结构及其基本运算的实现 1链式存储结构 顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。用单链表存放串，每个结点仅存储一个字符，如图4-1所示，因此，每个结点的指针域所占空间比字符域所占空间要大得多。为了提高空间的利用率，我们可以使每个结点存放多个字符，称为块链结构，如图4-2所示每个结点存放4个字符。第15页/共36页2023/3/1716图4-1 结点大小为1的链式存储结构 图4-2 结点大小为4的链式存储结构第16页/共36页2023/3/1717

15、2 2基本运算在链式存储结构上的实现 链式存储结构的C C语言定义如下：#define CHUNKSIZE ;/定义结点的大小 typedef struct Chunk /结点结构 char strCHUNKSIZE;struct Chunk *next;Lstring;一个链串由头指针唯一确定。一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。这种结构便于进行插入和删除运算，但存储空间利用率太低。为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于 1 1时，串的长度不一定正好是结点的整数倍，因此要用特

16、殊字符来填充最后一个结点，以表示串的终结。第17页/共36页2023/3/1718 对于结点大小不为1 1的链串，其类型定为义只需对上述的结点类型做简单的修改即可，如结点大小为4 4的定义为：#define nodesize 80define nodesize 80 typedef struct node typedef struct node char data4;char data4;struct node*next;struct node*next;lstring;lstring;采用链式存储结构（结点大小为1），实现串的联接、求子串以及串的置换基本运算见教科书 P83 P83。第18页

17、/共36页2023/3/1719 4.2.3 串的堆分配存储结构及其基本运算的实现 1 1堆分配存储结构堆分配存储结构 堆存储结构的特点是，仍以一组空间足够大的、地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。所以也称为动态存储分配的顺序表。每当产生一个新串时，系统就从剩余空间的起始处为串值分配一个长度和串值长度相等的存储空间。在C语言中，存在一个称为“堆”的自由空间，由动态分配函数malloc()分配一块实际串长所需的存储空间，如果分配成功，则返回这段空间的起始地址，作为串的基址。由free()释放串不再需要的空间。第19页/共36页2023/3/1720

18、2基本运算在基本运算在堆分配存储结构上堆分配存储结构上的实现的实现 在C C和C+C+语言中可利用mallocmalloc和freefree两个函数实现动态存储分配。函数mallocmalloc为每个新产生的串分配一块实际所需大小的空间，若分配成功，则返回一个指向该空间起始地址的指针，作为新串的基址。另外为了便于串的运算，在存储结构中包含串的长度。C C语言对堆分配存储结构的定义如下：typedef struct char*str;int curlen;Hstring;第20页/共36页2023/3/1721堆分配存储中求子串和串的联接运算：（1）SubStr(s,pos,len)Hstrin

19、g SubStr(Hstring&sub,Hstring s,int pos,int len)/用sub返回串s的第pos个字符起长度为len的子串 int i;if(poss.curlen-1|lens.curlen)return error;/参数不正确时返回错误提示 if(sub.str)free(sub.str);/释放旧空间 if(!len)/空子串 sub.str=NULL;sub.curlen=0;else sub.str=(char*)malloc(len*sizeof(char);for(i=0;ilen;i+)/非空子串 sub.stri=s.strpos+i;sub.cu

20、rlen=len;return ok;第21页/共36页2023/3/1722 （2）Concat(s,t)Hstring Concat(HString&s，HString s1，HString s2)/联接串s1和串s2形成新串s,并返回 int i;if(s.str)free(s.str);/释放旧空间 if(!(s.str=(char*)malloc(s1.curlen+s2.curlen)*sizeof(char)exit(overflow);for(i=0;is1.curlen;i+)/非空子串 s.stri=s1.stri;for(i=0;is2.curlen;i+)/非空子串 s

21、.strs1.curlen+i=s2.stri；s.curlen=s1.curlen+s2.curlen;return ok;第22页/共36页2023/3/17234.3 串的模式匹配 模式匹配：子串定位运算称为模式匹配(Pattern Matching)Pattern Matching)或串匹配(String Matching)String Matching)。模式匹配成功是指在目标串s s中找到一个模式串t t；模式匹配不成功则指目标串s s中不存在模式串t t。此运算的应用非常广泛。例如，在文本编辑程序中，经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文

22、本编辑程序的响应性能。本节主要讨论两种串的模式匹配算法，都采用顺序存储结构。在串匹配中，一般将主串称为目标串，子串称之为模式串。设S S为目标串，T T为模式串，设：S=S=“s s0 0s s1 1s s2 2s sn-1n-1”T=T=“t t0 0t t1 1t tm-1m-1”第23页/共36页2023/3/1724 4.3.1 Brute-Force算法算法 Brute-Force算法的基本思想是：从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s 的第二个字符起再重新和串t进行比较。依此类推，直至串t 中的每个字符依次和串s的一个连

23、续的字符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功。假设s=s=“cddcdccddcdc”，t=t=“cdccdc”，则模式匹配过程下图所示：第24页/共36页2023/3/1725Brute-Force算法的C语言描述如下：int Index(string s,string t)int i,j;i=0;/指向串s的第1个字符j=0;/指向串t的第1个字符while(is.curlen)&(j=t.curlen)return(i-t.curlen);/匹配成功，返回模式串t在串s中的起始位置 else return 0;/匹配失败

24、返回0 第25页/共36页2023/3/1726 一般情况下，上述算法的实际执行效率与字符 t.str0在串s中是否频繁出现有密切关系，例如，s 是一般的英文文稿，t=“hello”，s中有5%的字母是“h”，则在上述算法执行过程中，对于95%的情况可以只进行一次对应位的比较就将t向右移动一位，时间复杂度下降为O(s.curlen)，这时算法接近最好情况。然而，在有些情况下，该算法效率却很低。如当 s=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab s=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab，t

25、=t=“aaaaaabaaaaaab“每次都是在模式串的最后位置上字符不匹配 即 t.curlen s.curlent.curlen s.curlen时，该算法效率却很低。由于通常有t.curlen s.curlent.curlen s.curlen，因此最坏情况的时间复杂度为O(s.curlen*t.curlen)O(s.curlen*t.curlen)。第26页/共36页2023/3/1727 4.3.2 KMP 算法算法 由D.E.D.E.K Knuthnuth、J.H.J.H.M Morrisorris和V.R.V.R.P Prattratt共同提出了一个改进算法，消除了Brute-F

26、orceBrute-Force算法中串s s指针的回溯，完成串的模式匹配。时间复杂度为O(s.curlen+t.curlen)O(s.curlen+t.curlen)，这就是Knuth-Morris-PrattKnuth-Morris-Pratt算法，简称KMP KMP 算法。为了进一步讨论KMPKMP算法，让我们首先讨论一个例子。假设s=s=“abacabababacabab”，t=t=“abababab”，第一次匹配过程如下图所示：第27页/共36页2023/3/1728 此时不必从i=l，j=0重新开始第二次匹配。因为t.str0t.str1，s.str1=t.str1，必有s.str1

27、t.str0，又因t.str0=t.str2，s.str2=t.str2，所以必有s.str2=t.str0。因此，第二次匹配可直接从i=3，j=1开始。进一步分析，t.str1=t.str3，s.str3 t.str3，必定s.str3 t.str1，所以第二次匹配也不必进行，可以直接进行第三次匹配，即i=3，j=0。由此可见，当s.stri和t.strj比较不相等时，串s的指针i不必回溯。第28页/共36页2023/3/1729KMP算法的基本思想：设目标串为s，模式串为t i、j 分别为指示s和t的指针，i、j的初值均为0。若有 si=tj，则i和j分别增1；否则，i不变，j退回至j=n

28、extj的位置 (也可理解为串s不动，模式串t向右移动到si与tnextj对齐 )；比较 si 和 tj。若相等则指针各增1；否则 j 再退回到下一个j=nextj 的位置(即模式串继续向右移动 )，再比较 si 和 tj。依次类推，直到下列两种情况之一：1)1)j 退回到某个j=nextj时有 si=tj，则指针各增1，继续匹配；2)2)j 退回至 j=-1，此时令指针各增l，即下一次比较 si+1和 t0。第29页/共36页2023/3/1730 KMP算法的描述如下：#define MaxLen /定义最大串存储空间int Index_KPM(string s,string t)int

29、i,j,nextMaxLen;GetNext(t，next);/先求得模式串的next函数值i=0;/指向串s的第1个字符j=0;/指向串t的第1个字符while(is.curlen)&(j=t.curlen)return(i-t.curlen);/匹配成功 else return(0);/匹配失败 第30页/共36页2023/3/17314.4 串的应用 文本编辑是串的一个很典型的应用。它被广泛用于各种源程序的输入和修改，也被应用于信函、报刊、公文、书籍的输入、修改和排版。文本编辑的实质就是修改字符数据的形式或格式。在各种文本编辑程序中，它们把用户输入的所有文本都作为一个字符串。尽管各种文本

30、编辑程序的功能可能有强有弱，但是它们的基本的操作都是一致的，一般包括串串的的输输入入、查查找找、修修改改、删删除除、输出输出等。为了编辑方便起见，用户可以通过换页符和换行符将文本划分为若干页或将每页划分为若干行。可将整个文本看成是一个文本串，页是文本串的子串，而行则是页的子串。第31页/共36页2023/3/1732假设有下列一段C C源程序：main()float a,b,max;scanf(%f,%f,&a,&b);if(ab)max=a;else max=b;若用n表示换行符，该文本串在内存中的存储映像如下表所示：文本串的内存存储映像 第32页/共36页2023/3/1733 为了管理文

31、本串中的页和行，在进入文本编辑时，编辑程序先为文本串建立相应的页表和行表，即建立各子串的存储映像。页表的每一项列出页号和该页的起始行号，行表的每一项则指示每一行的行号、起始地址和该行子串的长度。以表4-2为例，假设文本串只占一页，起始行号为100，起始地址为200，则该文本串的行表如下所示。行表 第33页/共36页2023/3/1734下面来讨论文本的编辑。（1）插入一行时，首先在文本末尾的空闲工作区写入该行的串值，然后，在行表中建立该行的信息，插入后，必须保证行表中行号从小到大的顺序。若插入行145，则行表中从150开始的各行信息必须向下平移一行。（2）删除一行时，则只要在行表中删除该行的行

32、号，后面的行号向前平移。若删除的行是页的起始行，则还要修改相应页的起始行号（改为下一行）。（3）修改文本时，在文本编辑程序中设立了页指针，行指针和字符指针，分别指示当前操作的页、行和字符。若在当前行内插入或删除若干字符，则要修改行表中当前行的长度。如果该行的长度超出了分配给它的存储空间，则应为该行重新分配存储空间，同时还要修改该行的起始位置。对页表的维护与行表类似，在此不再叙述，有兴趣的同学可自行设计其中的算法。第34页/共36页2023/3/1735 串串是是一一种种特特殊殊的的线线性性表表，其其元元素素为为字字符符。本本章章讨讨论论了了串串的的顺顺序序存存储储结结构构、链链式式存存储储结结

33、构构和和堆堆分分配配存存储储结结构构。基基于于串串的的存存储储结结构构，可可以以实实现现串串的的各各种种基基本本运运算算，完完成成对对串串的的处处理理。采采用用不不同同的存储结构，串的运算效率不同。的存储结构，串的运算效率不同。串串的的模模式式匹匹配配是是一一种种较较复复杂杂的的串串运运算算，是是模模式式串串在在目目标标串串中中的的定定位位运运算算。Brute-ForceBrute-Force算算法法简简单单易易懂懂，但但效效率率较较低低。KMPKMP算算法法对对它它进进行行了了改改进进，消消除除了了目目标标串串指指针针的的回回溯溯，提提高高了了算法的效率。算法的效率。本章小结本章小结本章小结本章小结第35页/共36页2023/3/1736感谢您的观看。第36页/共36页