数据结构-严蔚敏《串的基本操作》解析

"串的基本操作-清华大学严蔚敏数据结构" 在计算机科学中，数据结构是组织和存储数据的方式，以便高效地访问和修改。串，也称为字符串，是数据结构的一种，由一个或多个字符组成。在本资源中，重点讨论的是串的基本操作，特别是在C语言中的实现。 一、串的基本操作 1. 求串长(length) 在C语言中，`strlen()`函数用于计算字符串的长度，不包括结束符'\0'。例如，对于字符串`s1="dirtreeformat"`，`strlen(s1)`会返回13，因为该字符串有13个字符，不包括末尾的空字符。 ```c #include <string.h> int main() { char s1[] = "dirtreeformat"; printf("%d", strlen(s1)); // 输出13 return 0; } ``` 二、其他串操作 除了求长度之外，常见的串操作还包括： - **赋值（Assignment）**: 使用`=`, `strcpy()` 或 `strncpy()` 将一个字符串赋值给另一个字符串。 - **连接（ Concatenation）**: 使用`strcat()` 或 `strncat()` 连接两个字符串。 - **比较（Comparison）**: 使用`strcmp()` 或 `strncmp()` 对字符串进行比较。 - **查找（Search）**: 使用`strstr()` 在一个字符串中查找子串。 - **复制（Copy）**: 使用`strcpy()` 或 `strncpy()` 复制字符串。 - **插入（Insertion）** 和 **删除（Deletion）**: 这些操作通常需要自定义函数来实现，因为C语言的标准库没有提供直接的函数支持。 三、数据结构的重要性 数据结构的选择对算法的效率至关重要。例如，在电话号码查询系统中，可以使用数组、链表、哈希表等不同的数据结构来存储名字和电话号码。不同的结构会影响查找速度，例如，哈希表可能提供近乎常数时间的查找，而数组和链表则可能需要线性时间。 四、抽象数据类型（Abstract Data Type, ADT） ADT是一种高级编程概念，它定义了数据类型的逻辑结构和相关的操作集合。在C语言中，虽然没有内置的ADT，但可以通过结构体和函数来模拟ADT。例如，我们可以定义一个`String` ADT来封装字符串的操作： ```c typedef struct { char* str; int length; } String; void init_String(String* s, const char* value) { s->str = malloc((strlen(value) + 1) * sizeof(char)); strcpy(s->str, value); s->length = strlen(value); } void free_String(String* s) { free(s->str); s->str = NULL; s->length = 0; } ``` 五、算法和算法分析 在处理数据结构时，算法设计和分析是非常关键的。良好的算法设计应该满足正确性、可读性和效率。算法效率通常通过时间复杂度和空间复杂度来衡量，如O(n)、O(log n)等，这些表示算法运行时间和所需存储空间与输入数据规模的关系。 例如，`strlen()` 函数的时间复杂度为O(n)，因为它需要遍历整个字符串以计算长度。理解这些复杂度可以帮助优化代码，选择更适合特定应用的数据结构和算法。 总结，数据结构是编程中不可或缺的一部分，串作为常用的数据结构之一，其基本操作的理解和熟练使用对编写高效的程序至关重要。同时，结合抽象数据类型和算法分析，可以更好地设计和实现复杂的软件系统。