数据结构 方风波 王巧莲 主编 黄鹤鸣 副主编 第四章 串新.pptVIP

数据结构 第四章 串 第四章 串 知 识 点 串的有关概念和术语 串的基本运算功能 串的顺序存储方法（包括紧缩格式和非紧缩格式）和链接存储方法 串的匹配运算 难 点 串的匹配运算算法 要 求 熟练掌握串的逻辑结构、存储结构及串上的基本运算，并能设计简单算法 了解串的匹配运算算法的基本思想 第四章目录 4.1 串的定义及其基本运算 4.2 串的存储结构 4.3 串的匹配运算 4.4 应用实例及分析 小 结 习题与练习 4.1.1 串的定义 串(string)是由有限个字符组成的序列，又称为字符串(character string)，一般记为: s=ˊa1 a2 a3…anˊ 其中s是串名，用单引号括起来的字符序列是串的值。ai(1=i=n)可以是字母、数字或其他字符；n为串中字符的个数，称为串的长度。 一个长度为零的串称为空串，表示为s =ˊˊ。 空格也是合法字符，它可以出现在较长的字符串中，也可以单独出现 。例如A=ˊabc def ˊ就是长度为7的字符串，因为abc和def中间有一个空格字符。 4.1.2 串的基本运算 1. 求串的长度len(s)； 2. 判断两个串是否相等equal(s,t)； 3. 两个串的连接concat(s，t)； 4. 求某串的子串sub(s，start，ln，t)； 5. 插入子串insert(s1，i，s2)； 6. 删除子串delete(s，i，j)； 7. 置换replace(s，t，r)。 4.2.1 串的顺序存储结构 串的顺序存储结构就是采用与其逻辑结构相对应的存储结构，即将串的各个字符按顺序存入连续的存储单元中去，逻辑上相邻的字符在内存中也是相邻的，有时称为顺序串。 串的最简单顺序存储是采用非紧缩格式，既每个存储单元中存放一个字符，所占存储单元数目即为串的长度。 这种存储结构，随机读写串中指定的第i个字符最为方便，存取的速度最快。但一般每个存储单元本可以放得下多个字符，只放一个字符不能充分利用存储空间。 为了充分利用存储空间，也可以采用紧缩格式的顺序存储结构，既根据存储单元的容量给每个单元存入多个字符，最末一个单元如果没有占满，可填充空格符。 这种存储结构从所占存储单元的数目不能求出准确的串长度(因末尾单元可能空余空间)，故需要将串的长度在串前面显式给出。 类型定义 串的顺序存储结构一般采用与顺序线性表类似的结构来定义串的类型: const maxlen=串的最大长度 typedef struct { char vec[maxlen]; int len; }orderstring; 其中，vec域用来存储字符串，len域用来存储字符串的当前长度。 4.2.2 串的链接存储结构 串的链接存储结构有时称为链串。 链串的存储形式与一般的链表类似，是将存储区分成许多结点，每个结点有一个存放字符的域和一个存放指向下一个结点的指针域。 链串中的一个存储结点可以存储1个或多个字符，通常将链串中每个存储结点所存储的字符个数称为结点大小 单字符结点的串的链式存储结构 多字符结点的串的链式存储结构 链串的类型定义 const nodesize=定义的结点大小 typedef struct node { char ch(nodesize); struct node *link; } linkstring; 当结点大小为1时，可将ch域简单定义为： char　ch; 4.3 串的匹配运算 串的匹配运算，就是判断某串是否是另一个已知串的子串，如是其子串，则给出该子串的起始点（即从已知串的哪个字符开始），故此运算又称为子串定位运算。 设已知串r1和r2，要求判断r2是否是r1的子串，如果是其子串则给出起始点。显然r2是r1的子串的一个必要条件是，r2的长度Lr2一定要小于或等于r1的长度Lr1，即Lr2≤Lr1。 假定串r1或r2都采用每结点存一个字符的链接存储结构。 一种最简单的匹配算法 首先将r2的第1个字符与r1的第1个字符比较，如二者匹配，则将r2的第二个字符与r1的第二个字符比较，这样比较下去，若直至r2的末尾一个字符都与r1的相应字符匹配，则整个运算结束，返回子串的起始位置为1； 当进行中遇到两串的相应字符不匹配时，则返回来将r2的第一个字符与r1的第二个比较，将r2的第二个字符与r1的第三个字符进行比较……，若整个r2的各个字符都与r1的相应字符匹配，则运算结束，返回子串的起始位置为2； 以此类推，如出现不匹配，再返回来将r2的第一个字符与r1的第三个字符比较。 如此逐轮做下去，直至匹配成功，给