数据结构-堆分配存储表示与动态内存管理

"堆分配存储表示-清华大学严蔚敏数据结构" 在计算机科学中，数据结构是组织和存储数据的方式，以便高效地访问和修改。在【标题】"堆分配存储表示-清华大学严蔚敏数据结构"中，主要讨论的是动态内存分配在数据结构中的应用，特别是针对字符串类型的存储。【描述】指出，这种存储方法允许在程序执行期间动态地分配和释放存储空间，以适应数据需求的变化。在C语言中，通常使用`malloc`和`free`这样的函数来实现动态内存管理。 在C语言中定义的字符串类型有两种形式： 1. `typedef char *string;` 这种定义方式将字符串视为字符指针，其中指针指向存储字符序列的起始位置。 2. `typedef struct{ char *ch; int length; }hsring;` 这是一种结构体定义，包含一个字符指针`ch`用于存储字符串的起始地址，以及一个整型变量`length`来记录字符串的长度。这种结构提供了更丰富的信息，不仅有字符序列的地址，还有长度信息，便于操作。 数据结构的学习通常涵盖以下几个方面： 1. **抽象数据类型（Abstract Data Type, ADT）**：这是一种逻辑上的数据类型，它定义了一组数据和操作这些数据的方法。例如，栈、队列、链表、树等都是抽象数据类型。 2. **数据结构的逻辑结构**：数据的逻辑结构不考虑存储细节，只关注数据之间的关系。常见的逻辑结构包括线性结构（如数组、链表）、树形结构（如二叉树、树）、图结构等。 3. **数据结构的物理结构**：物理结构是指数据在计算机内存中的实际布局，包括顺序存储（如数组）和链式存储（如链表）。 4. **数据结构的操作**：每个数据结构都有与其相关的操作，比如插入、删除、查找等，这些操作的效率直接影响了程序的性能。 5. **算法**：数据结构和算法是密切相关的，算法是解决问题的具体步骤，而数据结构是算法操作的对象。算法设计需要考虑效率，通常用时间复杂性和空间复杂性来衡量。 6. **算法效率的度量**：时间复杂性通常用大O符号表示，描述算法运行时间随输入数据规模的增长趋势；空间复杂性则关注算法在执行过程中所需的内存空间。 在【部分内容】中，提到了数据结构在实际问题中的应用，如电话号码查询系统、图书馆书目检索、教师资料档案管理和交通灯管理系统。这些例子强调了数据结构在解决实际问题中的重要性，不同的数据结构会对应不同的算法选择和效率。 堆分配存储表示是动态内存管理的一种方式，它在数据结构中扮演着关键角色，特别是在处理字符串和其他需要动态扩展的数据类型时。同时，数据结构和算法是计算机科学的基础，它们决定了程序的效率和可维护性。学习和理解这些概念对于编写高效代码至关重要。