《数据结构Ch4串》课件.pptx

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