第4章串数据结构课件

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

1、4.1串的基本概念4.2串的存储实现4.3串的模式匹配算法第4章串问题的提出查毒程序搜索引擎串又称字符串，是一种特殊的线性表，是数据元素类型为字符的线性表，其应用非常广泛，是许多软件系统（如字符编辑、情报检索、词法分析、符号处理、自然语言翻译等系统）的操作对象。本章介绍串的概念和各种存储结构，并讨论串的联接、求子串、串的插入、删除和置换以及串的模式匹配等运算。第4章串4.1串的基本概念串：由零个或多个任意字符组成的有限序列。串长度：串中所包含的字符个数。空串：长度为0的串，记为：""。非空串通常记为：S=“a1a2…an”其中：S是串名

2、，双引号是定界符，双引号引起来的部分是串值，ai（1≤i≤n）是一个任意字符。两个串相等：如果两个串的长度相等且对应字符都相等。子串：串中任意连续的字符组成的子序列称为该串。主串：包含子串的串。子串的第一个字符在主串中的序号称为子串的位置。串的逻辑结构与线性表的区别仅在于串的数据对象约束为字符集。串结构的形式化定义为：String=(D，R)其中，D={ai︱ai∈character，i=1，2…n，n≥0}，R={︱ai-1，ai∈D，i=1，2，…n}串的基本运算有：（1）初始化ClearString（s）：初始化串

3、s。（2）StrAssign（s，ch）：串赋值。（3）StrCopy(s，t)：串复制。（4）StrConcat（t，s1，s2）：串联接。（5）求串长StrLen（s）：返回s串的元素个数，即s串的长度。（6）串比较StrCom（s，t）（7）求子串SubStr（t，s，pos，len）：返回s串的第pos个字符起始的长度为len的子串。（8）插入运算StrInsert（s，pos，t）：把串t的值插入到串s的第pos个字符之后。（9）删除运算StrDel（s，pos，len）：将串s中从第pos字符起始的长度为len的子串删除。（

4、10）子串定位StrIndex（s，t，pos）：从主串s的第pos个字符起定位串s中是否存在和串t值相等的子串，若存在，则返回子串t在主串s中第一次出现的位置，否则，返回函数值0。例如，StrIndex（“Beijing”，“jin”，1）=4；StrIndex（“Beijing”，“jng”，2）=0（11）置换运算StrReplace（s，pos，len，t）：用t串置换s串中第pos字符开始的连续的len个字符。例如，s=“Thatфisфaфbag！”，则StrReplace（s，3，2，“is”）＝“Thisфisфaфba

5、g！”有时用另一种置换运算StrReplace（s，t，v）表示用v串置换所有在s串中出现的与t串相等的子串。例如，s=“if（j

6、一个不会在串中出现的特殊字符作为串的终结符。串的存储结构——顺序串如何表示串的长度？顺序串：用数组来存储串中的字符序列。（3）用数组的0号单元存放串的长度，串值从1号单元开始存放。串的存储结构——顺序串如何表示串的长度？在C语言中，按字节寻址。C语言中的串有字符串常量和字符串变量两种。用双引号括起来的字符序列为字符串常量，可以用宏定义#define来定义字符串常量的标识符。例如，#defineCITYBeijing对字符串变量而言，C语言将其类型说明为字符型一维数组。例如，charch[100]；其中，数组ch是一个一维数组，这里的字符

7、串的最大长度是由其变量说明时决定并且固定不变。通常，在字符串的最后一个字符的后面存放一个结束标志‘’。为了更好地讨论字符串的运算，可将顺序串类型定义如下：#defineMAXLEN81typedefstructstring{charch[MAXLEN]；intlen；}SeqString；2.定长顺序串的基本运算实现（1）求串长intStrLen(SeqString*s){return((*s).len);}（2）串的联接两个串的联接就是将一个串紧接着存放在另一个串的后面而得到一个新串。voidStrConcat(SeqSt

8、ring*t，SeqString*s1，SeqString*s2){inti，j;if((*s1).len+(*s2).len<=MAXLEN){for(i=0；i<(*s1).len；i++)(*t