数据结构与算法基础课件章节4.pptx
《数据结构与算法基础课件章节4.pptx》由会员分享,可在线阅读,更多相关《数据结构与算法基础课件章节4.pptx(20页珍藏版)》请在三一文库上搜索。
1、第4章 串4.1 串4.1.1 串的基本概念 串(string)是由零个或多个字符组成的有限序列。记作:S=a1a2a3an,其中S是串名,ai(1 i n)是单个,可以是字母、数字或其它字符。串中所包含的字符个数为该串的长度。长度为零的串称为空串,它不包含任何字符。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的相应地称为主串。通常,把子串在主串中第一次出现时,子串的第一次字符在主串中的序号,定义为子串在主串中的序号。如果两个串的串值相等(相同),称这两个串相等。换言之,只有当两个串的长度相等,且各个对应位置的字符都相同时才相等。需要注意的是,由一个空格或多个空格组成的串并不是空串
2、,而称为空格串,其长度为串中空格字符的个数。4.1.2 串的顺序存储结构1串的顺序存储 串的顺序存储结构类似于线性表的顺序存储结构,但它们的逻辑结构一致,均可用列表来存储数据元素。顺序存储表示的串描述如下:2顺序串的基本操作1)插入操作 插入操作insert(self,pos,substr)是在长度为n的顺序串的第pos个元素之前插入串substr,其中0 pos n。插入操作的主要步骤为:(1)判断参数pos是否满足0posn,不满足则抛出异常。(2)扩充顺序串的长度为n+m,其中m为插入子串substr的长度。(3)将第pos个及之后的数据元素向后移动m个位置。(4)将子串substr插入
3、到从pos开始的位置。(5)更新顺序串长度curLen。插入操作的算法如下:2)删除操作 删除操作delete(self,begin,end)是将长度为n的顺序串中的位序号为begin到end 1的元素删除,其中begin满足0 pos curLen 1,end满足begin end curLen。删除操作的主要步骤为:(1)判断参数begin和end是否满足0 pos curLen 1,begin end curLen,若不满足则抛出异常。(2)将顺序串位序为end的数据元素及其之后的数据元素向前移动到从begin开始的位置。(3)更新顺序串长度curLen。删除操作的算法如下:3)取子串操
4、作 取子串操作get_substring(self,begin,end)是返回长度为n的顺序串中位序号为begin到end 1的字符序列,其中0 begin n 1,begin end n。取子串操作的主要步骤为:(1)判断参数begin和end是否满足0 begin n 1,begin end n,若不满足则抛出异常。(2)返回位序号为begin到end 1的字符序列。取字串操作的算法如下:4)拼接操作 拼接操作是将串substr拼接到顺序串的尾部,即相当于将串substr插入到顺序串的尾部。该操作调用insert(self,curLen,str)方法即可实现。5)比较操作 比较操作comp
5、are(self,other)是将顺序串与串other按照字典序比较。如果顺序串较大,则返回1;如果顺序串较小,则返回-1;如果两串相等,则返回0。字典序的比较规则如下:(1)字典序是基于字符顺序排列的。(2)不同排列的先后关系是从左到右逐个比较对应的字符顺序的先后来决定的。(3)如果比较完某一字符串时,则字符串较长的字典序会较大;如果一样长,则表示两串相等。比较操作的算法如下:4.1.3 串的链式存储结构 串的链式存储结构和线性表的串的链式存储结构类似,采用单链表来存储串,结点的构成如下:1)data域:存放字符,data域可存放的字符个数称为结点的大小;2)next域:存放指向下一结点的指
6、针。若每个结点仅存放一个字符,这种结构称为单字符链表。但这种结点的指针域就非常多,造成系统空间浪费,为节省存储空间,考虑串结构的特殊性,使每个结点存放若干个字符,这种结构称为块链表,如图所示。在这种存储结构下,结点的分配总是完整的结点为单位,因此,为使一个串能存放在整数个结点中,在串的末尾填上不属于串值的特殊字符,以表示串的终结。当一个块(结点)内存放多个字符时,往往会使操作过程变得较为复杂,如在串中插入或删除字符操作时通常需要在块间移动字符。4.2 串的模式匹配 子串在主串中的定位称为模式匹配或串匹配(字符串匹配)。模式匹配成功是指在主串S中能够找到模式串T,否则,称模式串T在主串S中不存在
7、。模式匹配的应用在非常广泛。例如,在文本编辑程序中,我们经常要查找某一特定单词在文本中出现的位置。显然,解此问题的有效算法能极大地提高文本编辑程序的响应性能。模式匹配是一个较为复杂的串操作过程。迄今为止,人们对串的模式匹配提出了许多思想和效率各不相同的计算机算法。4.2.1 暴力模式匹配算法 理解模式匹配的定义后,最容易想到的一种方法就是将模式串在主串中一一匹配。首先从主串S的第一个字符起,与模式串第一个字符比较,假若相等,则继续向后逐个比较字符;否则从该次匹配中主串S的起始字符的下一个字符起,重新和模式串匹配;以此类推,直至模式串T中的每一个字符依次和主串S中的一个连续的字符序列相等,则匹配
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 基础 课件 章节
链接地址:https://www.31doc.com/p-21712637.html