还剩26页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构-串》ppt课件目录•串的基本概念•串的顺序存储结构CONTENT•串的链式存储结构•串的常用操作•串的模式匹配算法01串的基本概念串的定义总结词详细描述串的长度定义为串中字符的个数,通定义了串的基本概念常用大写的L表示详细描述总结词在数据结构中,串是一种特殊的线定义了串的字符集性表,由零个或多个字符组成的有序字符序列总结词详细描述定义了串的长度串的字符集是串中可能出现的字符的集合,通常用小写的Σ表示串的表示第二季度第一季度第三季度第四季度总结词详细描述总结词详细描述介绍了字符串的存储表字符串通常有两种存储介绍了字符串的抽象表字符串的抽象表示方式示表示方式,顺序存储和示是指仅考虑字符串的基链接存储顺序存储方本操作,而不考虑其具式使用一维数组来存储体的实现方式在抽象字符串中的字符,而链表示中,我们只关心字接存储方式使用结点来符串的长度、连接、插存储字符串中的字符入、删除等基本操作串的基本操作总结词介绍了字符串的连接操作详细描述字符串的连接操作是将两个字符串合并成一个新的字符串在具体实现中,可以采用顺序存储和链接存储两种方式,但无论采用哪种方式,都需要考虑如何处理字符串中的结束符0串的基本操作总结词介绍了字符串的比较操作详细描述字符串的比较操作是比较两个字符串的大小比较时,从两个字符串的第一个字符开始逐个比较,直到出现不同的字符或遇到结束符0为止如果两个字符串相等,则它们的长度一定相等;反之,如果两个字符串的长度相等,则它们的值不一定相等02串的顺序存储结构顺序存储结构的定义顺序存储结构01将串的字符序列按照一定的顺序存储在一片连续的存储单元中,每个字符占用一个固定长度的存储单元存储单元02用于存储字符的物理空间,可以是字节、字或其他数据单位地址03每个字符在存储单元中的位置标识顺序存储结构的实现初始化删除字符为串分配一片连续的存储空间,删除串中的某个字符时,需要并设置相应的指针指向串的首将该位置后的字符向前移动一字符位,覆盖被删除字符的位置插入字符查找字符在串的末尾插入新字符时,需通过指针遍历存储单元,逐个要移动已有的字符,为新字符比较每个字符,直到找到目标腾出空间字符或遍历完整个串顺序存储结构的优缺点空间利用率高连续的存储空间便于管理,可以充分利用存储空间存取速度快由于字符在内存中是连续存储的,因此访问某个字符的速度较快顺序存储结构的优缺点•易于实现字符串的基本操作如插入、删除、查找等操作顺序存储结构的优缺点动态调整困难插入和删除操作效率低顺序存储结构的空间是预先分配的,如在顺序存储结构中,插入和删除操作需要果实际使用的空间远小于预分配的空间,移动已有的字符,时间复杂度较高会造成浪费;反之,如果实际使用的空VS间超出预分配的空间,则无法再添加新的字符03串的链式存储结构链式存储结构的定义链式存储结构使用一组地址任意的存储单元来依次存放字符串中的字符这组地址任意的存储单元称为链表链表中的每个元素称为节点,每个节点包含两部分数据域和指针域数据域用于存放字符数据,指针域用于指向下一个节点链式存储结构的实现创建节点定义一个结构体,包含数据域和指针域两个成员变量数据域用于存放字符数据,指针域用于指向下一个节点插入节点在链表中插入一个新的节点,需要找到插入位置的前一个节点,修改其指针域,使其指向新节点,然后将新节点的指针域指向原插入位置的节点删除节点找到需要删除的节点的前一个节点,修改其指针域,使其指向需要删除节点的下一个节点,然后释放需要删除节点的内存空间链式存储结构的优缺点优点缺点可以动态地分配和回收内存空间,空间利用访问某个字符时需要从头节点开始遍历链表,率较高;可以方便地插入和删除节点,便于时间复杂度为On,访问效率较低;需要维修改字符串护指针域,增加了编程的复杂性04串的常用操作插入操作插入操作是指将一个或多插入操作的时间复杂度取个字符插入到串的指定位决于插入的位置和插入的置字符数量如果在串的开头插入字符,如果在串的末尾插入字符,时间复杂度为On,其中时间复杂度为O1n为串的长度删除操作0102删除操作是指从串中删除一个或删除操作的时间复杂度取决于删多个字符除的字符数量和删除的位置如果删除一个字符,时间复杂度如果删除多个字符或删除位置不为O1在末尾,时间复杂度为On,其中n为串的长度0304替换操作0103替换操作是指将串中的某个字符如果替换一个字符,时间复杂度或子串替换为另一个字符或子串为O10204替换操作的时间复杂度取决于替如果替换多个字符或替换位置不换的字符数量和替换的位置在末尾,时间复杂度为On,其中n为串的长度4102比较操作对于等长的两个串,比较比较操作是指比较两个串操作的时间复杂度为On,是否相等其中n为串的长度A BC D对于不等长的两个串,比比较操作的时间复杂度取较操作的时间复杂度也为决于串的长度On,其中n为较长的串的长度05串的模式匹配算法朴素模式匹配算法时间复杂度适用场景On*m,其中n为主串长度,m为模式串长适用于模式串较短且主串长度较小的情况度KMP算法要点一要点二时间复杂度适用场景On+m,其中n为主串长度,m为模式串长度适用于模式串较长且主串长度较大的情况BM算法时间复杂度On/m,其中n为主串长度,m为模式串长度适用场景适用于模式串较长且主串长度较大的情况,通常比KMP算法更高效Boyer-Moore算法时间复杂度适用场景On/m,其中n为主串长度,m为模式串长度适用于模式串较长且主串长度较大的情况,通常比BM算法更高效感谢您的观看THANKS。