数据结构课件第5章

《数据结构课件第5章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章串5.1串的应用实例及概念5.2串的存储结构5.3串的基本操作5.4串的ADT定义及类定义5.5实习五：串的演示程序5.1串的应用实例及概念在各种高级语言的编译程序中，源程序和目标程序都被处理成字符串数据，各源程序编辑器的功能强弱有差异，但其基本操作是一致的，一般都包括串的查找、插入及删除等。例如，在Delphi中创建一个新的源程序文件，并在其中输入以下内容：typeTstring=classprivate{privatedeclaration}public{publicdeclaration}end;这一段程序可看作一个字符串：“typeTstring=cl

2、assprivate{privatedeclaration}public{publicdeclaration}end;”，其中“”表示换行符。Delphi的源程序编辑器提供了字符串的查找与替换功能。选择“Search”菜单中的“Replace”项，在对话框中输入要查找字符串‘private’及替代串‘protected’，如图5.1所示，则执行命令后以上程序中的关键字‘private’被‘protected’替代。图5.1Delphi中源程序编辑器提供的字符串替换功能一般地，串（字符串）被定义为由零个或多个字符组成的有限序列。记为：s=‘a1a2…an’(n≥0)其

3、中，s是串的名，也称为串变量。单引号内的字符序列为串值。ai(1≤i≤n)可以是字母、数字或其他字符。串中字符的数目n称为串的长度。零个字符的串称为空串(nullstring)，长度为零。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置可以用子串的第一个字符在主串中的位置来表示。例如,假设a、b、c、d为如下的四个串：a=‘Data’b=‘Structure’c=‘DataStructure’d=‘DataStructure’则它们的长度分别为4、9、13和14，并且a和b都是c和d的

4、子串，a在c和d中的位置都是1。而b在c中的位置是5，在d中的位置则是6。5.2串的存储结构5.2.1顺序存储结构和线性表的顺序存储结构相类似，串的存储结构可以用一组地址连续的存储单元存储串的字符序列。利用数组，可将这种数据类型描述如下：constmaxlen=允许的串最大长度;typestrtp=recordcurlen:0..maxlen;ch:array［1..maxlen］ofchar;end;图5.2串的顺序存储结构(a)非紧缩方式；(b)紧缩方式5.2.2链式存储结构和线性表的链式存储结构相类似，串的存储结构也可采用链式存储结构，即用线性链表来存储串

5、值。在这种存储结构下，存储空间被分成一系列大小相同的结点，每个结点用data域存放字符，link域存放指向下一个结点的指针。这样，一个串就可以用一个线性链表来表示。由于串结构的特殊性，在串的链表结构中常常涉及到结点的大小问题，即如何确定结点的data域存放字符的个数问题。通常情况下，结点的大小为4或1，如图5.3所示。当结点的大小为4时,串所占用的结点中最后一个结点的data域不一定全被串值占满，这时通常补上“＃”或其他的非串值字符。图5.3串的链式存储结构(a)节点大小为4的链表；(b)节点大小为1的链表串的链式存储结构可定义如下：constnodesize=定义的结点大

6、小;typelink=^node;node=recordch:array［1..nodesize］ofchar;next:link;end;linkerstring=recordhead:link;length:integer;end;图5.4串存储的堆结构示例(a)存储空间；(b)映像空间1.求子串操作设源串为s，则求子串操作为将源串s的一部分复制到新串sub内。假设源串s:strtp已在外部进行了说明，截取的子串位置为pos:integer，截取长度为len:integer，并且取出的子串被复制入串sub:strtp中，则子串操作过程如下：proced

7、uresubstring(pos,len:integer;varsub:strtp);功能：在源串s中截取从pos开始的长len的子串，并将其复制到字符串sub中。5.3串的基本操作处理过程：(1)若截取子串的位置或长度超出合法值，即当pos>s.curlen或pos,len<1时，显示出错信息并终止。(2)若截取子串的位置在串长范围以内，且截取长度未超出最大可供截取长度，即当1≤pos≤s.curlen且1≤len≤s.curlen-pos+1时，将源串s中从pos开始