第四章：串的数据结构与基本操作

"数据结构与算法(4)ppt课件.ppt" 这篇内容主要讨论了数据结构中的一个重要概念——串（字符串），以及其相关的操作和存储结构。 串，或者称作字符串，是字符的线性集合，可以是零个或多个字符组成的序列。它的长度是指串中字符的数量。一个空串是没有字符的串。子串是串中的一个连续字符子序列，而主串是包含子串的串。串的大小比较通常基于字符的顺序，如果第一个字符相同，则比较第二个，直到找到不同的字符或者一个串结束。当两串的长度和对应位置的字符都相等时，我们认为它们相等。 串的基本操作包括： 1. Assign（赋值）：将一个值赋给串。 2. Create（创建）：创建一个新的串。 3. Delete（删除）：从串中移除字符或子串。 4. Length（长度）：获取串的长度。 5. Concat（连接）：将两个或多个串合并成一个新的串。 6. Substr（子串提取）：从串中提取指定位置的子串。 7. Index（索引）：查找特定字符在串中的位置。 8. Replace（替换）：替换串中的某个字符或子串。 9. Insert（插入）：在串的指定位置插入字符或子串。 10. Equal（比较）：判断两个串是否相等。 接下来，内容详细介绍了串的两种主要存储结构： 1. 顺序存储结构：使用数组来存储串，如`typedef struct{ char str[MAXLEN]; int curlen; }string;`，其中`MAXLEN`是预设的最大长度，`curlen`表示当前串的实际长度。另一种表示方式是`typedef char lstring[MAXLEN+1];`，这里`lstring[0]`用于存储字符串的当前长度，最大长度不超过255。 2. 动态存储结构： - 链表结构（块链结构）：使用链表节点存储字符，每个节点包含一个字符和指向下一个节点的指针，如`typedef struct node{ char ch; struct node*next; }node, *pointer;`。 - 堆结构：一种灵活的内存管理方式，可以动态调整大小。例如，`sstring`结构包含一个指向字符串的指针和长度，而`hstring`结构则包含一个字符串数组、长度和起始地址，用于在内存堆中存储串。 此外，还提到了存储密度的概念，它是指串值占用的存储位与实际分配的存储位之间的比率，这在评估不同存储结构效率时很重要。 最后，作业部分提到的问题要求找到所有包含在字符串`s`中但不包含在字符串`t`中的子串。 这些内容对于理解数据结构中的字符串处理和存储方法非常重要，特别是在进行字符串操作、搜索、排序和内存管理时。掌握这些知识对于编程和算法设计尤其关键。