数据结构 #01

本文参考《数据结构（C语言版）》（严蔚敏、吴伟民著，清华大学出版社）

绪论 ​

基本概念和术语 ​

• 数据(data)是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称。
• 数据元素(data element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项(data item)组成，例如一本书的书目信息为一个数据元素，而书目信息中的每一项（如书名、作者名等）作为一个数据项。数据项是数据不可分割的最小单位。
• 数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合 $N = \{0, \pm 1, \pm 2, \cdots\}$，字母字符数据对象是集合 $C = \{\prime A \prime, \prime B \prime,\cdots, \prime Z \prime\}$。
• 数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构(structure)。根据数据元素之间的不同特性，通常有下列4中基本结构：
  • (1) 集合 结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系；
  • (2) 线性结构 结构中的数据元素之间存在一个对一个的关系；
  • (3) 树形结构 结构中的数据元素存在一个对多个的关系；
  • (4) 图状结构或网络结构 结构中的数据元素存在多个对多个的关系。
• 数据结构的形式定义为：数据结构是一个二元组

  $$Data\_Structre = (D,S)$$

  其中：$D$是数据元素的有限集，$S$是$D$上关系的有限集。
• 结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。
• 数据结构在计算机中的表示（又称映像）称为数据的物理结构，又称存储结构。
• 在计算机中表示信息的最小单位是二进制数的一位，叫做位(bit)。在计算机中，我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素（如用一个字长的位串表示一个整数，用8位二进制数表示一个字符等），通常称这个位串为元素(element)或结点(node)。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域(data filed)。因此，元素或结点可看成是数据元素在计算机中的映像。
• 数据元素之间的关系在计算机有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序映像的特点是借助元素存储地址的指针(pointer)表示数据元素之间的逻辑关系。
• 数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。

• 数据类型(data type)是一个值的集合和定义在这个值集上的一组操作的总称。按“值”的不同特性，高级程序语言中的数据类型可分为两类：一类是非结构的原子类型。原子类型的值是不可分解的。另一类是结构类型。结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。在某种意义上，数据结构可以看成是“一组具有相同结构的值”，则结构类型可以看成由一种数据结构和定义在其上的一组操作组成。
• 抽象数据类型(Abstract Data Type，简称ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。
• 一个含抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。若按其值的不同特性，可细分为以下3种类型：
  • 原子类型(atomic date type)
  • 固定聚合类型(fixed-aggregate data type)
  • 可变聚合类型(variable-aggregate date type)
• 后两种类型可统称为结构类型。
• 和数据结构的形式定义相对应，抽象数据类型可用以下三元组表示:

$$(D, S, P)$$

其中，$D$是数据对象，$S$是$D$上的关系集，$P$是对$D$的基本操作集。可采用以下格式定义抽象数据类型：

ADT 抽象数据类型名 {
  数据对象: <数据对象的定义>
  数据关系: <数据关系的定义>
  基本操作: <基本操作的定义>
}

其中，数据对象和数据关系的定义用伪代码描述，基本操作的定义格式为：

基本操作名(参数表)
  初始条件: <初始条件描述>
  操作结果: <操作结果描述>

基本操作有两种参数：赋值参数和引用参数。赋值参数是指在调用基本操作时，传入的参数值不会被改变；引用参数是指在调用基本操作时，传入的参数值可能会被改变。

抽象数据类型的表示与实现 ​

本文参考《数据结构（C语言版）》（严蔚敏、吴伟民著，清华大学出版社）中的抽象数据类型的表示与实现部分。采用C语言来描述抽象数据类型的表示与实现。以下对其作简要说明：

(1) 预定义常量和类型

// 函数结构状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
// Status 是函数的类型，其值是函数结果状态代码
typedef int Status;

(2) 数据结构的表示（存储结构）用类型定义(typedef)描述

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

算法与算法分析 ​

线性表 ​

线性表的类型定义 ​

• 线性表(linear list)是最常用且最简单的一种数据结构。简言之，一个线性表是$n$个数据元素的有限序列。
• 在稍复杂的线性表中，一个数据元素可以由若干个数据项(item)组成。在这种情况下，常把数据元素称为记录(record)，含有大量记录的线性表又称文件(file)。
• 线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除等。
• 抽象数据类型线性表的定义如下:

ADT List {
  数据对象: D = { a_i | a_i \in ElemSet, i = 1,2,\cdots，n >= 0}
  数据关系: R1 = {<a_{i-1},a_i> | a_{i-1}, a_i \in D, i = 2,\cdots,n}
  基本操作:
    InitList(&L)
      操作结果: 构造一个空的线性表L
    DestroyList(&L)
    ClearList(&L)
    ListEmpty(L)
    ListLength(L)
    GetElem(L, i, &e)
    LocateElem(L ,e, compare())
    PriorElem(L, cur_e, &pre_e)
    NextElem(L, cur_e, &netx_e)
    ListInsert(&L, i, e)
    ListDelete(&L, i, &e)
    ListTraverse(L, visit())
} ADT List

线性表的顺序表示和实现 ​

//-------线性表的动态分配顺序存储结构--------//
#define LIST_INIT_SIZE 100 //线性表的初始分配空间
#define LISTINCREMENT 10 //线性表的分配增量
typedef struct {
  ElemType *elem; //存储空间基址
  int length; //当前长度
  int listsize; //当前分配的存储容量(以 sizeof(ElemType) 为单位)
} SqList;

Status InitList_Sq(SqList &L) {
  // 构造一个空的线性表L
  L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
  if(!L.elem) exit(OVERFLOW); // 存储分配失败
  L.length = 0; // 空表长度为0
  L.listsize = LIST_INIT_SIZE; // 初始分配空间
  return OK;
}

线性表的链式表示和实现 ​

线性链表 ​

循环链表 ​

双向链表 ​

一元多项式的表示及相加 ​

栈和队列 ​

栈 ​

抽象数据类型栈的定义 ​

栈的表示和实现 ​

栈的应用举例 ​

数制转换 ​

括号匹配的检验 ​

行编辑程序 ​

迷宫求解 ​

表达式求值 ​

栈与递归的实现 ​

队列 ​

抽象数据类型队列的定义 ​

链队列——队列的链式表示和实现 ​

循环队列——队列的顺序表示和实现 ​

离散事件模拟 ​

串 ​

串类型的定义 ​

串的表示和实现 ​

定长顺序存储表示 ​

堆分配存储表示 ​

串的块链存储表示 ​

串的模式匹配算法 ​

求子串位置的定位函数 Index(S, T, pos) ​

模式匹配的一种改进算法 ​

串操作应用举例 ​

文本编辑 ​

建立词索引表 ​

数组和广义表 ​

数据的定义 ​

数据的顺序表示和实现 ​

矩阵的压缩存储 ​

特殊矩阵 ​

稀疏矩阵 ​

广义表的定义 ​

广义表的存储结构 ​

m元多项式的表示 ​

广义表的递归算法 ​

求广义表的深度 ​

复制广义表 ​

建广义表的存储结构 ​

树和二叉树 ​

树的定义和基本术语 ​

二叉树 ​

二叉树的定义 ​

二叉树的性质 ​

二叉树的存储结构 ​

遍历二叉树和线索二叉树 ​

遍历二叉树 ​

线索二叉树 ​

树和森林 ​

树的存储结构 ​

森林与二叉树的转换 ​

树和森林的遍历 ​

树与等价问题 ​

赫夫曼树及其应用 ​

最优二叉树(赫夫曼树) ​

赫夫曼编码 ​

回溯法与树的遍历 ​

树的计数 ​

图 ​

图的定语和术语 ​

图的存储结构 ​

数组表示法 ​

邻接表 ​

十字链表 ​

邻接多重表 ​

图的遍历 ​

深度优先搜索 ​

广度优先搜索 ​

图的连通性问题 ​

无向图的连通分量和生成树 ​

有向图的强连通分量 ​

最小生成树 ​

关节点和重连通分量 ​

有向无环图以及应用 ​

拓扑排序 ​

关键路径 ​

最短路径 ​

从某个顶点到其余各顶点的最短路径 ​

每一对顶点之间的最短路径 ​

动态存储管理 ​

概述 ​

可利用空间表及分配方法 ​

边界标识法 ​

可利用空间表的结构 ​

分配算法 ​

回收算法 ​

伙伴系统 ​

可利用空间表的结构_ ​

分配算法_ ​

回收算法_ ​

无用单元收集 ​

存储紧缩 ​

查找 ​

静态查找表 ​

顺序表的查找 ​

有序表的查找 ​

静态树表的查找 ​

索引顺序表的查找 ​

动态查找表 ​

二叉排序树和平衡二叉树 ​

$B_-$树和$B^+$树 ​

键树 ​

哈希表 ​

什么是哈希表 ​

哈希函数的构造方法 ​

处理冲突的方法 ​

哈希表的查找及其分析 ​

内部排序 ​

概述_ ​

插入排序 ​

直接插入排序 ​

其他插入排序 ​

希尔排序 ​

快速排序 ​

选择排序 ​

简单选择排序 ​

树形选择排序 ​

堆排序 ​

归并排序 ​

基数排序 ​

多关键字的排序 ​

链式基数排序 ​

外部排序 ​

外存信息的存取 ​

外部排序的方法 ​

多路平衡归并的实现 ​

置换-选择排序 ​

最佳归并树 ​

文件 ​

有关文件的基本概念 ​

顺序文件 ​

索引文件 ​

ISAM 文件和 VSAM 文件 ​

ISAM 文件 ​

VSAM 文件 ​

直接存取文件(散列文件) ​

多关键字文件 ​

多重表文件 ​

倒排文件 ​