动态分配的顺序表：堆存储表示与C语言实现

在清华大学严蔚敏的数据结构课程中，4.2.2节主要探讨了堆分配存储表示的概念。堆存储是一种动态存储分配的方法，与传统的顺序存储不同，它允许程序在运行时根据需要动态地分配和释放内存空间，以存储数据结构如字符串。在C语言中，这通常通过`malloc()`和`free()`这样的动态内存管理函数来实现。例如，`typedef char *string`定义了C语言中的一种字符串类型，类似于字符串库中使用的表示方法。另一种形式是使用结构体，如`typedef struct{char *ch; int length;}`定义了一个包含字符指针和长度的字符串结构体，这被称为链式存储的顺序表。 堆分配的优势在于可以根据实际需求调整存储空间，灵活性高，但同时也需要程序员自行管理内存，防止内存泄漏或碎片化。在数据结构的学习中，堆存储与数据结构的选择密切相关，因为不同的数据结构适合不同的存储方式，比如二维数组、表结构或向量（在这种情况下，可以表示为N元向量，每个元素是包含姓名和电话号码的数对）。 堆存储中的数据结构设计不仅包括数据的逻辑结构（如电话簿中名字和电话号码的关系），还涉及物理结构即数据在内存中的布局，以及这些结构上的操作，如查询、检索和管理。例如，电话号码查询系统的算法设计就依赖于名字和电话号码的存储方式，选择适当的结构（如数组、链表或树）可以显著提高查找效率。 在基本概念和术语部分，数据被定义为具有特定意义的信息，它可以是数字、文本或其他形式。数据结构则关注数据如何组织和存储，以及如何通过定义和实现特定的运算（如搜索、插入和删除）来处理这些数据。术语如逻辑结构和物理结构强调了数据在计算机内部表示和实际存储之间的区别。此外，课程还会介绍算法设计的基本原则，如效率度量（如时间复杂度和空间复杂度）和算法所需的存储空间需求。 总结来说，堆分配存储表示是数据结构中一个关键概念，它扩展了顺序存储的灵活性，并在实际应用中发挥着重要作用，尤其是在处理大量或动态变化的数据时。通过学习和理解堆存储，学生能更好地设计和优化程序性能，满足不同类型数据结构的需求。