动态堆分配的顺序表：数据结构实现

在《严蔚敏数据结构教程》的4.2.2节中，讨论了堆分配存储表示在数据结构中的应用。堆存储表示是一种特殊的顺序表，其特点是存储空间不是预先固定，而是程序运行期间动态分配的。C语言中，可以利用`malloc()`和`free()`这样的动态内存管理函数来动态创建和释放字符数组，以适应不同大小的字符串需求。这种存储方式下的顺序串有两种形式： 1. `typedef char *string;` - 在C语言的内置库中，这种定义类似于C语言中的字符串类型，它是一个指向字符的指针，允许在程序运行时动态分配存储空间。 2. `typedef struct{ char *ch; int length; }hstring;` - 这是一个自定义的结构体，其中`ch`是一个字符指针，用于存放字符串内容，`length`表示字符串长度，这种结构体提供了更丰富的数据结构特性。 数据结构的核心概念在本节中得到了强调，即数据结构是计算机科学中的重要组成部分，它关注的是信息的组织方式，包括逻辑结构（如数组、表、向量等）和物理结构（存储在内存中的实际布局），以及这些结构之间的关系。例如，电话号码查询系统的数据结构设计选择（如二维数组、表或向量）直接影响算法的实现和效率。数据结构还定义了针对特定结构的操作，如查找、插入和删除等。 算法设计时，数据结构的选择至关重要，因为不同的数据结构决定了不同的操作性能。例如，对于大规模数据，使用哈希表可能比线性搜索更快。此外，算法的效率通常通过时间复杂度和空间复杂度来衡量，而动态分配的存储表示则使得空间需求可以根据实际需要灵活调整。 总结来说，堆分配存储表示是数据结构中一种灵活且高效的方法，它允许程序在运行时动态管理内存，这对于处理需要动态增长或收缩的数据集合特别有用。通过理解并掌握这种存储表示，程序员可以更好地设计和优化他们的算法，以适应各种复杂的计算机应用需求。