数据结构（C语言描述）教学课件斯庆巴拉第4章串.ppt

《数据结构（C语言描述）教学课件斯庆巴拉第4章串.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章串学习重点：串的基本概念及串的特点串的顺序存储方式及基本操作的实现算法串的链式存储方式及基本操作的实现算法串的索引存储方式串的模式匹配的主要算法第4章串4.1串类型的定义4.2串的存储结构4.3串的操作本章总结：4.1串类型的定义串（或称字符串），是由零个或多个字符组成的有穷序列。一般记作：s=＂a0a1a2…an-1＂（n≥0）。用双引号括起来的字符序列是串值，双引号是串标志，串中所含字符个数n称为该串的长度（或串长）。含零个字符的串称为空串，用Φ表示。字符在序列中的序号为该字符在串中的位置。串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地被称

2、为主串。C语言中，存储串时，每个字符在内存占用一个字节，并用特殊字符“”标记串结束。注意：空格串与空串是不相同的。空串的长度为0，空格串的长度为串中空格字符的个数。4.2串的存储结构4.2.1串的顺序存储4.2.2串的链式存储4.2.3串的索引存储4.2.1串的顺序存储顺序存储实现：在顺序串中，每个字符依次存放在一组连续的存储单元中。串的顺序存储有两种方法：一种是每个存储单元只存一个字符，称为非紧缩格式。第二种，在每个存储单元中存放多个字符，称为紧缩格式。处理字符的速度高，空间利用率低节省存储空间，处理字符速度低顺序串的类型定义描述如下：#definemaxlen

3、maxsize//maxsize为给定的最大长度structstring{charch[maxlen];//maxlen为数组中存储空间的最大数量intlen;};4.2.2串的链式存储链串与一般的链表类似，链串中的一个结点可以存储一个或多个字符。链串结点大小的选择将直接影响到串处理的效率。存储密度=串值所占存储容量/实际分配存储容量链串的类型定义如下：typedefstructLnode{chardata;//存放字符structLnode*next;}*Linkstring;4.2.3串的索引存储索引存储实现：用一个表组织每个串的首地址和串长即可实现对这个串的引用

4、，这个表被称为串记录的索引表（符号表）。结构定义如下：structHSstring{intstr;//串在所分配存储区间的首地址intlength;//串的长度}strindex[maxlen]；//strindex为记录串信息的索引表。4.3串的操作注意：串操作主要以“串整体”为操作对象。4.3.1串常用操作的实现4.3.2模式匹配操作4.3.1串常用操作的实现基本操作在顺序结构上的实现基本操作在链式结构上的实现基本操作在顺序结构上的实现操作一：strcopy（s，t）操作二：strequal（s，t）操作三：strlength（s）操作四：strconcat（s，

5、t）操作五：strsub（s，i，j）操作六：strdelsub（s，i，j）操作七：strins（s1，i，s2）操作八：strrep（s，i，j，t）操作一：strcopy（s，t）串拷贝分析：将t所指串中的内容拷贝到s串中。实现算法：voidstrcopy(string&s,stringt){inti;for(i=0;i

6、如果串长相等且串中的各个字符对应相等则两个串相等，返回标志1；如果有字符不相等，则表明两字符串不相等，返回标志0。实现算法：（略）操作三：strlength（s）分析：求串长度，直接返回s.len的值。实现算法：（略）操作四：strconcat（s，t）分析：进行串连接时，由于存储空间有限，连接后的串的长度不确定，所以存在三种情况：（1）两个串的长度之和小于最大存储量：将两个串进行连接。（2）两个串的长度之和大于最大存储值，但第一个串的长度比最大存储值要小：将第二个串的部分进行连接，长出的部分采用截尾法处理。（3）连接时第一个串就已将存储空间用完：不进行连接。实现算法

7、：（略）操作五：strsub（s，i，j）分析：求s中从第i个字符开始长度为j的子串。需判定所给的i(i>=1&&i<=s.len)、j(j>=0&&j<=s.len-i+1)范围是否合法。实现算法：(略)操作六：strdelsub（s，i，j）分析：串s中的字符是连续存储的，所以当删除从i到j的子串后要求将后面的字符全部前移j个单元，在删除之前需要判断i(i>=1&&i<=s.len)、j(j>=0&&j<=s.len-i+1)是否合法。实现算法：(略)操作七：strins（s1，i，s2）分析：向s1中第i个位置插入s2，当两个串的长度之和小于存