数据结构-严蔚敏-串的基本操作与算法分析

"串的基本操作-清华大学严蔚敏数据结构" 在计算机科学中，数据结构是组织和存储数据的方式，以便高效地访问和修改。串（String）作为一种基本的数据结构，通常指的是由字符序列组成的字符串。在处理文本信息时，串的操作至关重要。在描述的文件中，我们关注的是在C语言中串的基本操作。 1. **串的定义**： 在C语言中，串是由零个或多个字符组成的序列，通常以空字符'\0'作为结束标记。例如，`char s1[20]="dirtreeformat"`定义了一个包含13个字符的串`s1`，最后的空字符占用了第14个位置。 2. **串的操作**： - **求串长（length）**：`int strlen(char s)` 函数用于计算串`s`的长度，不包括结束的空字符。例如，`printf("%d", strlen(s1))`会输出13，因为`s1`中包含13个可见字符。 除了上述的求串长操作，C语言还提供了其他串操作，如： - **复制串**：`strcpy(char *dest, char *src)` 将源串`src`复制到目标串`dest`。 - **连接串**：`strcat(char *dest, char *src)` 将源串`src`追加到目标串`dest`的末尾。 - **比较串**：`strcmp(char *s1, char *s2)` 比较两个串`s1`和`s2`，返回值表示它们的相对顺序。 - **查找子串**：`strstr(char *haystack, char *needle)` 在主串`haystack`中查找子串`needle`，并返回子串的首地址，若找不到则返回`NULL`。 3. **抽象数据类型（ADT）和实现**： 抽象数据类型是数据结构的理论基础，它定义了数据的逻辑结构和相关的操作集合，但不涉及具体的实现细节。例如，我们可以定义一个名为`String`的ADT，包含上述的串操作。在C语言中，可以使用数组或指针来实现串的存储。 4. **算法和算法分析**： 数据结构和算法密切相关。一个良好的算法不仅应解决特定问题，还需考虑其效率，包括时间和空间复杂度。例如，串的某些操作（如查找）可以用线性时间复杂度实现，而其他操作（如排序）可能需要更复杂的算法。 5. **数据结构的重要性**： 数据结构的选择直接影响到程序的效率和可维护性。在电话号码查询系统、图书馆书目检索系统、教师资料档案管理系统等实际应用中，合理选择和设计数据结构能显著提高系统的性能。 总结，串的基本操作是数据结构学习中的重要内容，理解和掌握这些操作对于编写高效的文本处理程序至关重要。同时，数据结构的整体概念，包括逻辑结构、物理结构以及运算定义，是理解和设计复杂程序的基础。