《《数据结构（C语言描述）》-斯庆巴拉-电子教案 第4章串》由会员分享，可在线阅读，更多相关《《数据结构（C语言描述）》-斯庆巴拉-电子教案 第4章串（26页珍藏版）》请在金锄头文库上搜索。
1、第4章 串,学习重点： 串的基本概念及串的特点 串的顺序存储方式及基本操作的实现算法 串的链式存储方式及基本操作的实现算法 串的索引存储方式 串的模式匹配的主要算法,第4章 串,4.1 串类型的定义 4.2 串的存储结构 4.3 串的操作 本章总结：,4.1 串类型的定义,串（或称字符串），是由零个或多个字符组成的有穷序列。一般记作：s=a0 a1 a2a n-1 （n0）。 用双引号括起来的字符序列是串值，双引号是串标志，串中所含字符个数n称为该串的长度（或串长）。含零个字符的串称为空串，用表示。字符在序列中的序号为该字符在串中的位置。 串中任意个连续字符组成的子序列称为该串的子串。包含子串
2、的串相应地被称为主串。 C语言中，存储串时，每个字符在内存占用一个字节，并用特殊字符“0”标记串结束。 注意：空格串与空串是不相同的。空串的长度为0，空格串的长度为串中空格字符的个数。,4.2 串的存储结构,4.2.1 串的顺序存储 4.2.2 串的链式存储 4.2.3 串的索引存储,4.2.1 串的顺序存储,顺序存储实现：在顺序串中，每个字符依次存放在一组连续的存储单元中。 串的顺序存储有两种方法：一种是每个存储单元只存一个字符，称为非紧缩格式。第二种，在每个存储单元中存放多个字符，称为紧缩格式。,处理字符的速度高，空间利用率低,节省存储空间，处理字符速度低,顺序串的类型定义描述如下： #
3、define maxlen maxsize /maxsize为给定的最大长度 struct string char ch maxlen ; /maxlen为数组中存储空间的最大数量 int len ; ;,4.2.2 串的链式存储,链串与一般的链表类似，链串中的一个结点可以存储一个或多个字符。 链串结点大小的选择将直接影响到串处理的效率。 存储密度=串值所占存储容量 / 实际分配存储容量 链串的类型定义如下： typedef struct Lnode char data ; /存放字符 struct Lnode * next ; *Linkstring ;,4.2.3 串的索引存储,索引存储实
4、现：用一个表组织每个串的首地址和串长即可实现对这个串的引用，这个表被称为串记录的索引表（符号表）。 结构定义如下： struct HSstring int str; /串在所分配存储区间的首地址 int length; /串的长度 strindexmaxlen； /strindex为记录串信息的索引表。,4.3 串的操作,注意：串操作主要以“串整体”为操作对象。 4.3.1 串常用操作的实现 4.3.2 模式匹配操作,4.3.1 串常用操作的实现,基本操作在顺序结构上的实现 基本操作在链式结构上的实现,基本操作在顺序结构上的实现,操作一：strcopy（s，t） 操作二：strequal（s，
5、t） 操作三：strlength（s） 操作四：strconcat（s，t） 操作五：strsub（s，i，j） 操作六：strdelsub（s，i，j） 操作七：strins（s1，i，s2） 操作八：strrep（s，i，j，t）,操作一：strcopy（s，t）串拷贝 分析：将t所指串中的内容拷贝到s串中。 实现算法： void strcopy(string / 0表示串的结束 ,操作二：strequal（s，t） 分析：判断s和t两个串是否相等，如果串长不相等则两个串不相等，返回标志0，如果串长相等且串中的各个字符对应相等则两个串相等，返回标志1；如果有字符不相等，则表明两字符串不相等
6、，返回标志0。 实现算法：（略） 操作三：strlength（s） 分析：求串长度，直接返回s.len 的值。 实现算法：（略）,操作四：strconcat（s，t） 分析：进行串连接时，由于存储空间有限，连接后的串的长度不确定，所以存在三种情况： （1）两个串的长度之和小于最大存储量：将两个串进行连接。 （2）两个串的长度之和大于最大存储值，但第一个串的长度比最大存储值要小：将第二个串的部分进行连接，长出的部分采用截尾法处理。 （3）连接时第一个串就已将存储空间用完：不进行连接。 实现算法：（略）,操作五：strsub（s，i，j） 分析：求s中从第i个字符开始长度为j的子串。需判定所给的i
7、 (i=1&i=0&j=1&i=0&j=s.len-i+1)是否合法。 实现算法： (略),操作七：strins（s1，i，s2） 分析：向s1中第i个位置插入s2，当两个串的长度之和小于存储总长度时，需要将s1串中第i个字符后的所有字符全部向后移动strlength（s2）个单元。 实现算法：（略） 操作八：strrep（s，i，j，t） 分析：s串中从第i个字符开始的j个连续字符将被t字符串替换，这时s串中被替换部分后面的所有字符要相应的移动连接在替换部分的后面，保证替换后的字符串仍然是连续存储。 实现算法： （略）,基本操作在链式结构上的实现,操作一：strcopy（s，t） 操作二：s
8、trequal（s，t） 操作三：strlength（s） 操作四：strconcat（s，t） 操作五：strsub（s，i，j） 操作六：strdelsub（s，i，j） 操作七：strins（s1，i，s2） 操作八：strrep（s，i，j，t）,操作一：strcopy（s，t） 分析：对于串的链接存储结构，其操作结果和顺序存储一样，使s串和t串内容相同。 实现算法：（略） 操作二：strequal（s，t） 分析：判定两个串是否从第一个字符到最后一个字符都相同，如果相同则两个串相等，返回标志1，如果有不相同的字符或一个串比较结束而另一个串还有字符没被比较，则s和t不相等，返回标志0。
9、 实现算法： （略）,操作三：strlength(s) 分析：遍历单链表，得到结点个数，即串的长度。 实现算法：（略） 操作四：strconcat（s，t） 分析：链式存储的串只需将两个链表的首尾相连，不需要判断合并后存储空间的容量。 实现算法：（略）,操作五：strsub（s，i，j） 分析：返回s串中从第i个结点开始，长度为j的一个子串。 实现算法：（略） 操作六：strdelsub（s，i，j） 分析：删除s串中从第i个结点开始的连续j个结点。 实现算法： （略）,操作七：strins（s1，i，s2） 分析：只需将s2链表插入到s1的第i个结点的位置。 实现算法：（略） 操作八：str
10、rep（s，i，j，t） 分析：先删除s串中从第i个字符开始的连续j个结点，再将t串插入到第i个结点的位置。 实现算法： （略）,4.3.2 模式匹配操作,模式匹配操作就是在主串s中定位子串t的操作，即在主串s中找到第一个与子串t相等的子串，通常把主串s称为目标串，把子串t称为模式串。模式匹配成功是指在s中找到一个；不成功则指s中不存在t。 模式匹配操作的实现算法： BruteForce算法 Knuth-Morris-Pratt算法（KMP算法）,BruteForce算法： 思想：从目标串s=“s0s1sn1”的第一个字符开始和模式串t=“t0t1t m1”中的第一个字符比较，若相等，则继续比
11、较后面的字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推，若存在一个每个字符依次与目标串中的对应字符相等的连续字符序列，则匹配成功，函数返回t中的第一个字符在s中的位置；否则，匹配失败，函数返回0。,KMP算法 思想：设s为目标串，t为模式串，并设i指针和j指针分别指示目标串和模式串中正待比较的字符，令i和j的初值均为0。若有si=tj，则i和j分别增1；否则，i不变，j退回到j=nextj的位置（即模式串右滑），比较si和tj，若相等则指针各增1，否则j再退回到下一个j=nextj的位置（即模式串继续右滑），再比较si和tj。依次类推，直到下列两种情况之一：第
12、一种情况是j退回到某个j=nextj时有si=tj，则指针各增1后继续匹配；另一种情况是j退回到j=-1时，此时令指针各增1，即下一次比较si+1和t0。,BruteForce算法 和KMP算法的比较： KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才显得比Brute-Force算法快。 Brute-Force算法的时间复杂度为O（nm），但在一般情况下，实际的执行时间近似于O（n+m），因此至今仍被采用。 KMP算法的最大特点是指示主串的指针不需回溯，。,本章总结：,串是由零个或多个字符组成的有穷序列。由串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 串有三种存储结构：顺序存储结构、链式存储结构和索引存储结构。比较：顺序存储结构简单，操作方便但存储的串的长度受到限制；串的链式存储操作方便，存储时串长不受限制，为了提高空间利用率需要考虑存储密度；串的索引存储结构是以上两种结构的折中实现。 串的模式匹配的Brute-Force算法原理简单，但是出现多个 “部分匹配” 时，算法的效率将会变低。KMP算法中无需回溯主串指针，适用于外部数据输入时的模式匹配。,
