链串实现串基本运算的算法详解

"这篇资料主要讨论了如何在链串上实现串的基本运算，特别是通过一个名为StrAssign的函数，将字符串常量赋值给链串。资料还提到了串的基本概念，包括串的定义、相等性判断、子串的概念以及串的一些基本运算。此外，还介绍了线性表和串的异同以及串的各种操作，如复制、比较、求长度、连接、插入、删除和替换。" 在《数据结构》第四章中，我们关注的是串这一数据结构，它是由零个或多个字符组成的有限序列。串可以表示为"a1a2…an"的形式，其中每个ai代表一个字符，双引号用于区分串与其他标识符。串的长度是指包含的字符数，空串用Ф表示。两个串相等的条件是长度相同且对应位置的字符相同。 串的基本运算包括多种操作： 1. **StrAssign**: 这个函数用于将字符串常量cstr赋值给链串s。通过尾插法创建链串，遍历cstr中的每个字符，动态分配内存并创建新的链串节点，直到遇到字符串结束符'\0'。 链串的节点类型定义为`LiString`，包含一个字符`data`和指向下一个节点的指针`next`。StrAssign函数首先为链串的头节点分配内存，然后使用指针`r`始终追踪当前链串的尾部，依次添加字符节点。 2. **其他基本运算**：除了StrAssign，串还有其他基本运算，如StrCopy(复制)，StrEqual(比较)，StrLength(求长度)，Concat(连接)，SubStr(求子串)，InsStr(插入)，DelStr(删除)和RepStr(替换)。这些运算提供了对串进行各种操作的能力，如修改、组合和检索特定部分。 3. **串和线性表的异同**：串可以看作是一种特殊的线性表，其中的元素是字符。两者都是线性结构，但串有其特定的操作和特性，如串的长度和子串的概念，这些都是线性表不具备的。 4. **模式匹配**：虽然未在摘要中详细展开，但模式匹配是串处理中的一个重要话题，涉及到在主串中查找子串出现的位置。 5. **顺序存储与基本操作的实现**：串可以使用顺序存储结构，如数组，也可以使用链式存储结构，如链串。顺序存储在实现基本操作时有其优势，如访问元素快速，但插入和删除操作可能涉及大量元素的移动。 在链式存储中，像StrAssign这样的操作更为灵活，因为插入和删除只需要改变相邻节点的指针。然而，顺序存储在某些情况下，如求串长度和遍历所有字符时可能更快。串的存储选择取决于具体的应用需求和性能考虑。