还剩23页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构ch4串》ppt课件•串的定义与表示contents•串的基本操作•串的存储结构目录•串的模式匹配算法•串的应用01串的定义与表示串的基本概念串是由零个或多个字空串是指长度为零的符组成的有限序列串串的长度是指串中字符的个数串的表示方法顺序存储表示法将串中的字符依次存储在数组中,通过下标访问链式存储表示法为每个字符分配一个节点,节点包含字符信息和指向下一个节点的指针串的抽象数据类型定义抽象数据类型(ADT)是一种数据结构的抽象描述,它定义了一组操作来操作该数据结构拼接初始化将两个串连接起来创建一个空串比较赋值比较两个串是否相等将一个已有的串复制给另一个串02串的基本操作初始化串初始化串初始化方式初始化过程创建一个空串,为串的存储空间分配通过C语言中的malloc函数为串分配在程序中创建一个字符数组,并使用内存,并设置初始值内存空间,并使用空字符0作为初始malloc函数为其分配内存空间,然后值将其初始值设置为空字符0连接操作连接操作连接过程将两个串的地址和长度作为参数传递给strcat函数,该函数将第一个串的将两个串拼接在一起形成一个新的串内容复制到第二个串的末尾,形成一个新的串连接方式通过C语言中的strcat函数实现串的拼接比较操作比较操作比较两个串是否相等比较方式通过C语言中的strcmp函数实现串的比较比较过程将两个串的地址作为参数传递给strcmp函数,该函数比较两个串的内容,如果相等则返回0,否则返回非零值替换操作替换方式通过C语言中的strstr函数和strcpy函数实现串的替替换操作换将一个串中的指定子串替换为另一个子串替换过程使用strstr函数查找指定子串在原串中的位置,然后使用strcpy函数将替换子串复制到该位置,覆盖原子串03串的存储结构静态存储结构优点空间利用率高,可以避免频繁的内存申请和释放1操作缺点浪费存储空间,如果实际字符串长度小于预分配2的长度,就会造成存储空间的浪费应用场景适用于长度已知或变化不大的字符串3动态存储结构优点节省存储空间,只分配实际需要的存储空间缺点应用场景需要频繁的内存申请和释放操作,增加了系适用于长度变化较大或无法预知的字符串统开销顺序存储结构优点01便于字符串的随机访问和修改缺点02需要预先分配连续的存储空间,可能会导致空间的浪费或不足应用场景03适用于长度变化不大且需要频繁访问和修改的字符串04串的模式匹配算法朴素模式匹配算法时间复杂度On*m,其中n是主串的长度,m是模式串的长度适用场景适用于较短的字符串匹配KMP算法时间复杂度On+m,其中n是主串的长度,m是模式串的长度适用场景适用于较长的字符串匹配BM算法时间复杂度On/m,其中n是主串的长度,m是模式串的长度适用场景适用于较长的字符串匹配,且对模式串有较好的预处理Boyer-Moore算法时间复杂度On/m,其中n是主串的长度,m是模式串的长度适用场景适用于较长的字符串匹配,且对模式串有较好的预处理05串的应用文本编辑器中的串处理文本编辑器中的串文本编辑器中的串文本编辑器中的串处理处理处理在文本编辑器中,字符串是常见文本编辑器中的字符串处理通常为了提高字符串处理的效率,文的处理对象例如,查找、替换、涉及到字符串的长度、子串的提本编辑器通常会使用一些数据结删除、插入等操作都是基于字符取、字符串的拼接、字符串的分构,如哈希表、树等来存储和索串进行的割等操作引字符串数据库中的字符串处理010203数据库中的字符串数据库中的字符串数据库中的字符串处理处理处理在数据库中,字符串是重要的数数据库中的字符串处理涉及到字为了提高查询效率,数据库系统据类型之一,用于存储和检索数符串的查询、匹配、排序等操作通常会使用索引、全文检索等技据术来处理字符串自然语言处理中的字符串处理自然语言处理中的字符串处理在自然语言处理中,字符串是基本的数据单元,用于表示文本信息自然语言处理中的字符串处理自然语言处理中的字符串处理涉及到分词、词性标注、句法分析等操作自然语言处理中的字符串处理为了提高处理的准确性和效率,自然语言处理系统通常会使用各种算法和技术,如隐马尔可夫模型、条件随机场等THANKS FORWATCHING感谢您的观看。