数据结构课件第四章串.ppt

1、2020/8/6,1,数据结构,第四章 串,院(系) : 计算机科学与技术学院 教研室: 计算机软件与理论(602) 教 师: 王红滨,2020/8/6,2,【学习目标】1.理解“串”类型定义中各基本操作的特点,并能正确利用它们进行串的其它操作。2.理解串类型的各种存储表示方法。 【重点和难点】相对于其它各个知识点而言,本章非整个课程的重点,鉴于串已是多数高级语言中已经实现的数据类型,因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法,并学会利用这些基本操作来实现串的其它操作。,第四章 串,2020/8/6,3,【知识点】串的类型定义、串的存储表示及操作实现 【学习指南】虽然目

2、前各常用的高级语言中都已经实现了串类型,但由于它是通过软件实现的,因此作为一个软件工作者还是应该了解串的实现方法。,第四章 串,2020/8/6,4,第四章 串,在计算机的各方面应用中,非数值处理问题的应用越来越多。如在汇编程序和编译程序中,源程序和目标程序都是作为一种字符串数据进行处理的。在事务处理系统中,用户的姓名和地址及货物的名称、规格等也是字符串数据。 字符串一般简称为串,可以将它看作是一种特殊的线性表,这种线性表的数据元素的类型总是字符型的,字符串的数据对象约束为字符集。在一般线性表的基本操作中,大多以“单个元素”作为操作对象,而在串中,则是以“串的整体”或一部分作为操作对象。一般线

3、性表和串的操作有很大的不同。本章主要讨论串的如下内容:,2020/8/6,5,主要内容,4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例,2020/8/6,6,4.1 串类型的定义,4.1.1 串的定义 串:或字符串,是由零个或多个字符组成的有限序列。一般记为 s=a1a2a3an (n0) 单引号本身不属于串 其中:s为串的名字,ai(1in)可以是字母、数字或其它字符; 串的值:用单引号括起来的字符序列; 串的长度:串中字符的数目n称为串的长度; 空串:零个字符的串,其长度为零,用符号“”或来表示。 空格串:由一个或多个空格组成的串。 子串:串

4、中任意个连续的字符组成的子序列称为该串的子串。 主串:包含子串的串相应地称为主串。 位置:称字符在序列中序号为该字符在串中的位置。 子串在主串中的位置则以子串的第一个字符在主串中的位置来表示,第一位置为1,2020/8/6,7,4.1串类型的定义(续),例如下串:a=BEIb=JINGc=BEIJINGd=BEI JING 长度分别为 a和b都是c和d的 a在c和d中的位置都是 b在c中的位置是 ,b在d中的位置是 a、b、c、d彼此不相等。 相等:当且仅当这两个串的值相等。 串变量与其它变量的区别是:串值用一对单引号括起来。 例如:x=123(是串变量)与x=123是不同的。,3、4、7、8

5、,子串,1,4,5,2020/8/6,8,4.1串类型的定义(续),串的操作:以串的整体为操作对象。 1. 串赋值 2. 串判等 3. 求串长 4. 串联接 5. 求子串 6. 定位函数 7. 置换操作 8. 串比较 例:定位函数Index的实现:(用判等、求串长、求子串操作)P72算法4.1。,2020/8/6,9,定位函数Index,实现Index(S,T,pos)算法的基本思想为: 从主串S中取第 i 个字符起、长度和串T相等的子串和串T比较,若相等,则求得函数值为 i,否则 i 值增1直至找到和串T相等的子串或者串S中不存在和T相等的子串为止。即求使下列等式: SubString (s

6、ub, S, i, StrLength(T); StrCompare(sub,T)=0成立的 i 值。i 的初值应为 pos,在找不到的情况下,i 的终值应该是 n-m+1,其中,n 为S串的长度,m 为T串的长度。,2020/8/6,10,算法4.1(定位函数Index),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;whil

7、e ( i = n-m+1) SubString (sub, S, i, m); /取得从第i个字符起长 /度为m的子串if (StrCompare(sub,T) != 0) +i ;else return i ; / 找到和 T 相等的子串 / while / ifreturn 0;/S中不存在满足条件的子串或pos值不对 / Index,2020/8/6,11,“置换”操作,实现“置换”操作的基本思想为： 由S和V生成一个新的串 news。首先将它初始化为一个空串,然后重复下列两步直至“查找不成功”为止：1) 自 pos 位置起在串S中查找和T相同的子串；2) 将S中不被置换的子串（即从

8、pos 起到和T相同子串在S中的位置之前的字符序列）和V相继联接到news 串上。最后尚需将S中不被置换的字符序列联接到 news 串中,并将所得的新串赋给串 S。 这里要注意的是,语句 Concat(news,news,V)的前提是不破坏V串。即在利用高级语言实现此算法时应注意看请语言使用手册中的说明。,2020/8/6,12,“置换”操作算法,void replace(String /联接剩余子串并将新的串赋给S ,2020/8/6,13,串和线性表的基本操作,串的基本操作和线性表一样,无非也就是查找、插入和删除等,那么它们能否用线性表的操作来替代呢？ 串的基本操作和线性表有很大的区别,同

9、样是查找、插入和删除,但对线性表言操作对象是数据元素,如在线性表中查找某一个特定的数据元素,或者插入/删除一个数据元素。而对串言,是以整个串作为操作对象,如将两个串联接在一起,在串中查找一个子串,插入/删除一个串等等。由此你可体会串类型不能和线性表类型混为一谈。,2020/8/6,14,4.2 串的表示和实现,4.2.1 定长顺序存储表示 1表示:用一组地址连续的存储单元存储串值的字符序列。为每个串变量分配一个固定长度的存储区,可用定长数组描述。(例最大串长为255)Pascal中:数组0存放串的长度。C语言中以”0”表示串值的终结。 #define MAXSTRLEN 255 typedef

10、 unsigned char SStringMAXSTRLEN+1; /0号单元存放串的长度,顺序存储,链式存储,2020/8/6,15,4.2 串的表示和实现(续),2串操作的实现: 截断:串的长度超过了最大长度的串值被舍去。 (1)串联接操作:设串变量的最大串长度为10。 S1=ABCDEFS2=GHIJ S3=KLMNOPS4=QRSTUVWXYZ 则:T1=S1联接S2=ABCDEFGHIJ(将S1、S2串值复制到T1) T2=S1联接S3=ABCDEFKLMN(S3的OP部分截断) T3=S4联接S1=QRSTUVWXYZ(S1被全部截去) 这种截断处理的情况,在插入、置换等到操作中

11、也可能发生。克服这个弊病唯有不限定串长的最大长度,即采用动态存贮结构。,2020/8/6,16,4.2 串的表示和实现(续),(2)求子串:P75算法4.3 特点: 实现串操作的原操作为“字符序列的复制”。操作的时间复杂度基于复制字符序列的长度; 在操作中不会出现结果超长的情况。,2020/8/6,17,4.2 串的表示和实现(续),4.2.2 堆分配存储表示 1表示:以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行的过程中动态分配而得。 系统开辟一个地址连续的串值存贮空间(串值可利用空间); 建立一个新串时,就在可利用空间分配,存贮串值; 同时,建立一个符号表; 建立一

12、个新串时,在符号表中纪录下串变量名,串值在可利用空间的位置、串长度等信息。,2020/8/6,18,4.2 串的表示和实现(续),例如:a=BEIb=JINGc=SHANGHAId=HARBIN,符号表 串值存贮空间,串变量存贮映像,1,2,3,4,5,6,7,8,9,10,2020/8/6,19,4.2 串的表示和实现(续),2串操作的实现:也是基于字符序列的复制。 对串进行操作时,先为串重新分配空间,以前占有的空间释放,然后进行串复制。因此,“移动”是不可避免的。 例:串复制、串插入、及串的基本操作。 (1)串的插入,P75算法4.4 (2)串的基本操作函数,P76 堆分配存储结构有顺序顺

13、序存储结构的特点,处理方便,且操作中对串长又没有限制,更显灵活,所以该串处理在应用程序中常被选用。,2020/8/6,20,4.2 串的表示和实现(续),4.2.3 串的块链存储表示 (1)链表存贮方式: 用链表方式存储串值,每个结点可以存放一个字符,也可以存放多个字符。每个结点有两个域:data域放字符,next域指向下一结点,结点的大小即指data域字符的个数。 例如:结点大小为1的链表:(每个结点只存放1个字符),head 例如,结点大小为4的链表:,head 分配是以完整的的一个结点为单位的,若最后一个结点没被串值占满,则以“#”补满。(为便于操作,还可附设一个尾指针指出最后结点,并给

14、出串的长度。),2020/8/6,21,4.2 串的表示和实现(续),结点大小的选择和顺序存储方式的格式选择很重要,它直接影响着串处理的效率。要考虑串值的存储密度:,存储密度小,运算处理方便,但占存储量大;密度大,则运算处理不方便。,2020/8/6,22,4.4 串操作应用举例,4.4.1 文本编辑 所谓文本编辑是一组对一批数据进行增删改的程序,其实质是修改字符数据的形式或格式。例,见P85。 编辑时,若要插入或删除一行,则需要对行表进行插入或删除 若在某行内插入或删除,则相应地修改行表中的“长度”,如果该行长度超出了原分配给它的空间,那么要为该行重新分配空间,并修改“起始位置”。,2020

15、/8/6,23,4.4 串操作应用举例(续),例如有下列一段源程序: main() int a,b,c; scanf(“%d,%d”, 我们把这个源程序看成是一个文本,为了编辑的方便,总是利用换行符把文本划分为若干行,还可以利用换页符将文本组成若干页,这样整个文本就是一个字符串,简称为文本串,其中的页为文本串的子串,行又是页的子串。将它们按顺序方式存入计算机内存中,如表4-2所示(图中表回车符)。,2020/8/6,24,4.4 串操作应用举例(续),main() int a,b,c; scanf(“%d,%d”, ,图4.7 文本格式示例,2020/8/6,25,4.4 串操作应用举例(续)

16、,在输入程序的同时,文本编辑程序先为文本串建立相应的页表和行表,即建立各子串的存储映象。串值存放在文本工作区,而将页号和该页中的起始行号存放在页表中,行号、串值的存储起始地址和串的长度记录在行表,由于使用了行表和页表,因此新的一页或一行可存放在文本工作区的任何一个自由区中,页表中的页号和行表中的行号是按递增的顺序排列的,如表4-3所示。设程序的行号从110开始。,图4.8 图4.7所示文本串的行表,2020/8/6,26,4.4 串操作应用举例(续),下面我们就来讨论文本的编辑。 (1)插入一行时,首先在文本末尾的空闲工作区写入该行的串值,然后,在行表中建立该行的信息,插入后,必须保证行表中行

17、号从小到大的顺序。若插入行145,则行表中从150开始的各行信息必须向下平移一行。 (2)删除一行时,则只要在行表中删除该行的行号,后面的行号向前平移。若删除的行是页的起始行,则还要修改相应页的起始行号(改为下一行)。 (3)修改文本时,在文本编辑程序中设立了页指针,行指针和字符指针,分别指示当前操作的页、行和字符。若在当前行内插入或删除若干字符,则要修改行表中当前行的长度。如果该行的长度超出了分配给它的存储空间,则应为该行重新分配存储空间,同时还要修改该行的起始位置。 对页表的维护与行表类似,在此不再叙述,有兴趣的同学可设计其中的算法。,2020/8/6,27,本章小结,本章主要介绍了串类型

18、的定义及其实现方法,串的两个显著特点是: 其一、它的数据元素都是字符,因此它的存储结构和线性表有很大不同,例如多数情况下,实现串类型采用的是堆分配的存储结构,而当用链表存储串值时,结点中数据域的类型不是字符,而是串,这种块链结构通常只在应用程序中使用; 其二、串的基本操作通常以串的整体作为操作对象,而不像线性表是以数据元素作为操作对象。 本章还介绍了一些基本概念: 串:串(或字符串)是由零个或多个字符组成的有限序列。 主串和子串:一个串的任意个连续的字符组成的子序列称为该串的子串,包含该子串的串称为主串。,2020/8/6,28,本章小结(续),串的顺序存储结构:类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列的存储方式称为串的顺序存储结构。 堆存储结构:用一组空间足够大的、地址连续的存储单元存放串值字符序列,但其存储空间在程序执行过程中能动态分配的存储方式称为堆存储结构。 串的链式存储结构:类似于线性表的链式存储结构,采用链表方式。 除上述基本概念以外,学生还应该了解串的基本运算(字符串拷贝(赋值、字符串的联接、求字符串的长度、子串的查询、字符串的比较)、串的顺序存储结构的表示、串的链式存储结构的表示、串的堆存储结构的表示,能在各种存储结构方式中求字符串的长度、能在各种存储结构方式