动态存储分配的顺序表-数据结构讲义

"堆分配存储表示-tsinghua严版教材讲义" 在计算机科学中，数据结构是组织和管理大量数据的方式，它对于高效地存储和检索数据至关重要。本讲义主要探讨了堆分配存储表示这一特定的数据结构概念，特别是在C语言环境下的应用。 堆分配存储表示是指在程序执行过程中动态分配的、地址连续的存储单元来存放字符序列，这种存储方式被称为动态存储分配的顺序表。不同于静态分配，其中内存是在编译时就确定的，堆分配允许程序在运行时根据需要请求和释放内存。C语言提供了`malloc`和`free`等动态内存管理函数，用于在堆上分配和释放字符数组空间。 在C语言中，字符串通常是由字符数组表示的，但为了方便管理和操作，可以使用两种形式的抽象数据类型（ADT）来定义顺序串类型： 1. `typedef char *string;` 这种定义将字符串视为指向字符的指针，因此字符串实际上是一个字符数组的地址。通过这种方式，我们可以方便地通过指针操作字符串，例如通过指针的加减操作访问和修改字符。 2. `typedef struct{ char *ch; int length; }hsring;` 这种定义更进一步，除了包含指向字符数组的指针外，还包含了字符串的长度信息。这种结构体类型的变量可以提供更丰富的信息，比如字符串的精确长度，这对于某些操作（如字符串比较或复制）非常有用。 数据结构的选择和设计直接影响到算法的效率和程序的性能。在上述电话号码查询系统的例子中，数据可以被组织成二维数组、链表或者向量等形式。不同的数据结构将决定查找特定电话号码的算法和其执行速度。例如，使用数组可以实现快速的随机访问，但插入和删除操作可能较慢；而使用链表则可能在插入和删除时更快，但访问速度相对较慢。 在讨论数据结构时，我们还需要理解一些基本概念和术语，如逻辑结构和物理结构。逻辑结构是指数据元素之间的抽象关系，如线性结构、树形结构、图结构等；而物理结构则关注数据在内存中的实际布局和组织方式，这可能因操作系统和编程语言的不同而有所差异。 数据结构不仅涉及数据的组织，还包括定义在这些结构上的操作集合，以及这些操作的时间和空间复杂度分析。例如，对于链表，我们可能关心插入、删除、查找等操作的时间复杂度，这些分析对于优化代码和提高程序性能至关重要。 在设计和实现算法时，我们不仅要考虑其功能，还要考虑其效率。算法设计的要求包括正确性、可读性、可维护性以及效率。而算法效率的度量通常通过时间复杂度（如大O符号表示法）和空间复杂度来评估。理解这些概念对于编写高效且实用的程序至关重要。 堆分配存储表示是动态管理内存的一种方式，特别适用于需要在运行时改变大小的数据结构。在C语言中，借助`malloc`和`free`等函数，我们可以灵活地处理字符串和其他动态数据结构。同时，数据结构和算法的选择是软件开发中的关键因素，它们直接影响程序的性能和可维护性。