数据结构复习资料.doc

数据结构的定义
数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。
数据结构：是指数据以及数据元素相互之间的联系,可以看作是相互之间存在着某种特定关系的数据元素的集合。
对数据结构的内容包括以下几个方面：
① 数据的逻辑结构，指数据元素之间的逻辑关系。
② 数据的存储结构，指数据元素及其关系在计算机存储器中的存储方式，也称为数据的物理结构。
③ 数据运算，指施加在数据上的操作。
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中，每一条指令表示一个或多个操作。
粗略地说，算法是为了求解问题而给出的一个指令序列，程序是算法的一种具体实现。
一个算法必须满足以下五个重要特性：
1. 有穷性 2. 确定性 3. 可行性 4. 有输入 5. 有输出
算法的重要特征
(1) 有穷性: 算法在有穷步之后结束，每一步在有穷时间内完成。
(2) 确定性: 算法中的每一条指令有明确的含义，无二义性。
(3) 可行性: 可通过已经实现的基本运算执行有限次来实现算法中的所有操作。
算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度。算法的执行时间主要与问题的规模有关。问题规模是一个与输入有关的量。
　　语句频度是指算法中该语句被重复执行的次数。算法中所有语句的频度之和记作Ｔ(n)，是该算法所求解问题规模的函数。当问题规模趋向无穷大时，Ｔ(n)的数量级称为渐进时间复杂度，简称时间复杂度，记作Ｔ(n)=O(f(n))。
通常采用算法中表示基本运算的语句的频度来分析算法的时间复杂度。
例题：
1. 数据结构中的逻辑结构是指(　)，物理结构是指（　）。
2. 算法的基本特征包括有穷性、( )、( )、有输入和输出 。
3. 算法的有穷性是指（　）。
4. 算法的确定性是指（　）。
5. 算法的可行性是指（　）。
6. 算法分析的两个主要方面是分析算法的（　）和空间复杂度。
7. 语句频度是指（ 算法中该语句被重复执行的次数 ）。
8. 设n为正整数，对下面的程序段，写出语句①、②、③的频度及该程序段的时间复杂度。
for (i=1; i <=n; i++)
{
s=0; ① n
for (j=1; j <=n; j++)
s=s+i×j; ② n2
if (s%2) ③ n
print(s);
}
第二章 线性表
本章内容：
2.1 线性表的基本概念
F 一个线性表是有n个数据元素的有限序列：
(a1，a2，…，ai，…，an)
2.2 线性表的顺序存储结构
F 线性表的顺序存储指用一组地址连续的存储单元依次存储线性表的数据元素。这称为顺序表。
特点：
Ø 存储单元地址连续（需要一段连续空间）
Ø 逻辑上相邻的数据元素其物理位置也相邻
Ø 存储密度大（100%）
Ø 随机存取，元素的存储位置存在如下关系：
Loc(ai) = Loc(a1) + (i - 1) * d (1≤i≤n)
2.3 线性表的链式存储结构
F 线性表的链式存储指用任意的存储单元存放线性表中的元素，每个元素与其直接前驱和（或）直接后继之间的关系用指针来表示。这称为链表。

F 头指针是指向链表第一个结点的指针。
F 头结点是链表中的第一个结点但是头结点中不存放数据元素。
单链表、循环链表的类型定义
typedef struct LNode {
ElemType data; /*存储数据元素*/
struct LNode *next; /*指向后继结点*/
}SLink,*LinkList;
LinkList head,tail;
例题
1. 顺序表中，逻辑上相邻的数据元素在物理位置上( 也相邻 ) 。线性表L=(a1,a2,...,an)采用顺序存储，假定在不同的n+1个位置上的插入概率相同，则插入一个新元素平均需要移动的元素个数是( n/2 ) 。
2. 在一个长度为n的顺序表中, 在第i个元素(1 £ i £n)之前插入一个新元素时, 需向后移动( n-i+1 )个元素。
3. 在表长为n的单链表中, 取得第i (1£ i £ n)个数据元素必须从( 头指针 )出发开始寻找。
4. 在一个具有n个结点的有序单链表中，插入一个新结点并保持链表有序的算法时间复杂度为( O(n) ) 。
5. 解释头指针和头结点。
6. 请对线性表进行顺序存储和链式存储的特点作比较。
基于空间的考虑：顺序表的存储空间是静态分配的，而链表的存储空间是动态分配的。因此，当线性表的长度变化较大，难以估计其存储空间规模时，宜采用动态链表作为存储结构。反之，则采用顺序表作为存储结构。另外，存储密度越大，则存储空间的利用率越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。因此，当线性表的长度变化不大，易于事先确定其大小时，为了节省空间，采用顺序表为宜。
基于时间的考虑：顺序表是由向量实现的，它是一种随机存取结构，而链表是一种顺序存储结构。因此，若线性表的操作主要是进行查找，很少进行插入和删除操作时，采用顺序表作存储结构为宜。反之，则采用链表作为存储结构。
7. 编写算法，将一个带头结点的单链表就地逆置。（请先说明算法思路，再用类高级语言编写算法。 ）
F 将原链表看成由两部分组成：已经完成逆置的部分和未完成逆置的部分。
F 设置两个指针p和s，p指向已完成逆置部分链表的第一个结点，s指向未逆置部分的第一个结点。
F 初始时令指针p指向第一个元素结点，s指向p所指结点的后继。将第一个元素结点的指针域置为空。
F 将未逆置部分的结点逐个插入到头结点之后。

p = head->next;
if (p)
s = p->next;
p->next = NULL;

p = s;
s = s ->next;
p->next =
head -> next;
head -> next = p;

p = s;
s = s ->next;
p->next =
head -> next;
head -> next = p;

F 将原链表看成由两部分组成：已经完成逆置的部分和未完成逆置的部分。
F 设置两个指针p和s，p指向已完成逆置部分链表的第一个结点，s指向未逆置部分的第一个结点。
F 初始时令指针p指向第一个元素结点，s指向p所指结点的后继。将第一个元素结点的指针域置为空。
F 将未逆置部分的结点逐个插入到头结点之后。

算法：
void reverse(LinkList head)
{ //带头结点的单链表逆置
p = head->next; if (!p) return;
s = p->next; p->next = NULL;
while (s) {
p = s; s = s -> next; p -> next = head -> next; head->next = p;
}
}
第三章 栈和队列
F 栈是后进先出的线性表，队列是先进先出的线性表；
F 在应用中，栈和队列都是容器，因此需要判断是否“栈空”或“队空”；
F 采用顺序存储结构时，栈和队列都可能存在“溢出”问题，分别称为“栈满”、“队满”；
F 采用顺序结构的队列常见形式是循环队列。

F 栈的运算演示
(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA 。
例题
1. 用S、X分别表示入栈、出栈操作，若元素入栈顺序为1、2、3、4，为得到出栈序列1、3、4、2，则相应的S和X操作串是（ SXSSXSXX ）。
2. 若push、pop分别表示入栈、出栈操作，初始栈为空且元素a、b、c依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为( b a c )。
3. 如果进栈的序列为1、2、3, 则不能得到的出栈序列为（ 3 1 2 ）。

¯ 令队列空间中的一个单元闲置，使得在任何时刻，保持Q.rear和Q.front之间至少间隔一个空闲单元
MAXSIZE=8
F 队列满(full)：
(Q.rear+1)%MAXSIZE == Q.front
F 队列空：
Q.rear==Q.front
F 队列长度：
(Q.rear - Q.front+ MAXSIZE)% MAXSIZE
例题
1. 在循环队列结构中（队列空间容量为M），Ｑ.rear指向队尾元素所在位置，Ｑ.front指向队头元素所在位置，则队列的长度为( (Q.rear - Q.front + 1 + M) % M )。
2. 用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（ O(1) ）和（O(n)）；若只设尾指针，则出队和入队的时间复杂度分别是（O(1)）和（O(1)）。

1. 若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请完善下面的入队列和出队列的算法。
#define MAXSIZE 100 //最大队列长度
typedef struct {
Qelemtype *base; //base为队列所在存储区域的首地址
int length; //队列长度
int rear; //队尾元素位置
}SqQueue；

1. 若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请完善下面的入队列和出队列的算法。
#define MAXSIZE 100 //最大队列长度
typedef struct {
Qelemtype *base; //base为队列所在存储区域的首地址
int length,rear; //队列长度和队尾元素位置
}SqQueue；
Status EnQueue（SqQueue &Q, Qelemtype e）
｛//将元素e插入队列Q
if（ （1） ） return ERROR；//队列满，无法插入
Q.rear ＝ （2） ; //计算元素e的插入位置
（3） ＝ e; //在队尾加入新的元素
Q.length++； //队列长度加1
return OK;
｝
// (1) Q.length > ＝ MAXSIZE (2) （Q .rear + 1）％ MAXSIZE (3) Q.base[Q .rear]

第四章 串
1. 了解串的基本运算
2. 了解串的模式匹配算法
第六章 树和二叉树
二叉树或者是一棵空树；或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成
满二叉树中所有分支结点都有左孩子和右孩子， 叶结点都集中在二叉树的最后一层。满二叉树结点的编号：从树根为1开始,按照层数从小到大、同一层从左到右的次序进行。
完全二叉树中，最多只有最下面两层的结点的度数可以小于2，最下面一层的叶结点都排列在该层最左边的位置上。完全二叉树结点的编号：从树根为1开始,按照层数从小到大、同一层从左到右的次序进行。
例题
1. 一棵满二叉树中共有n个结点，其中有m个叶子结点，则n和m的关系为（ n=2m-1 ）。
2. 在完全二叉树中，若一个结点没有左孩子子结点，则它一定没有( B )。
    A．父结点 B．右孩子结点　
C．左兄弟结点 D．右兄弟结点

性质1 非空二叉树上第i层上至多有2i-1个结点i≥1。
性质2 高度为h的二叉树至多有2h-1个结点(h≥1)。
性质3 非空二叉树上叶结点数(度为0)等于双分支结点数(度为2)加1。
性质4 对完全二叉树中编号为i的结点(1≤i≤n，n≥1，n为结点数)，可以算出其左孩子结点、右孩子结点和父结点的编号（若这些结点存在）。
性质5 具有n个(n＞0)结点的完全二叉树的高度为élog2 (n+1)ù 或 ëlog2nû+1。

F 二叉树的顺序存储指的是用元素在数组中的下标表示一个结点与其孩子和父结点的关系.

F 一般用二叉链表存储二叉树(每个结点有两个指针域)

F 树的遍历是访问树中每个结点仅一次的过程。可以认为遍历是把所有的结点放在一条线上，或者将一棵树进行线性化的处理。
F 先序遍历DLR、中序遍历LDR、后序遍历LRD
F 层序遍历
F 先序遍历DLR：访问根结点、先序遍历左子树、先序遍历右子树
F 中序遍历LDR：中序遍历左子树、访问根结点、中序遍历右子树
F 后序遍历LRD：后序遍历左子树、后序遍历右子树、访问根结点

F 先序遍历：访问根结点、先序遍历左子树、先序遍历右子树。下图的先序遍历序列为A B D E G C F。
F 中序遍历：中序遍历左子树、访问根结点、中序遍历右子树。下图的中序遍历序列为D B G E A C F。
F 后序遍历：后序遍历左子树、后序遍历右子树、访问根结点。下图的后序遍历序列为D G E B F C A。
F 层序遍历：先根后子树、先左子树后右子树。下图的层序遍历序列为A B C D E F G。

例题
1. 在有n个结点的二叉树的二叉链表中必定存在（n+1）个空链域。
2. 前序遍历序列与中序遍历序列相同的二叉树为（ D ）。
A. 根结点无左子树的二叉树
B. 根结点无右子树的二叉树
C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树
D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树
3. 已知一棵二叉树的先序遍历序列为ABDGCEF，中序遍历序列为DGBAECF，画出此二叉树。

树（森林）采用孩子兄弟链存储结构。可以将一棵树或一个森林转换为一棵二叉树，反之亦然。
树的孩子兄弟链存储结构是指在一个结点中既指出当前结点的第一个孩子，也指示出当前结点的兄弟。下图(a)的树对应的孩子兄弟链存储结构如图(b)所示。
森林转换为二叉树的过程：左指针：父子关系 右指针：兄弟关系
线索二叉树
F 对于具有n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有2n个指针域，又由于只有n-1个结点被有效指针所指向（n个结点中只有树根结点没有被有效指针域所指向），则共有2n-(n-1)=n+1个空链域。
遍历二叉树的结果是一个结点的线性序列。可以利用这些空链域存放指向结点的前驱和后继结点的指针。这些指向结点在某种遍历序列中的“前驱”和“后继”的指针，称作线索

哈夫曼树
F 哈夫曼树（或最优二叉树）是一类带权路径长度最短的树，这种树的叶子结点带有权值。
F 路径和路径长度
¯ 从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。
F 结点的带权路径长度
¯ 从根到该结点的路径长度与该结点权的乘积称为结点的带权路径长度
F 树的带权路径长度
¯ 树中所有叶子的带权路径长度之和称为树的带权路径长度，记作

树的带权路径长度
WPL = 7*2+5*2+2*2+4*2 = 36
WPL= 4*2 + 7*3 +5*3 + 2*1 = 46
F 设有四个叶子a、b、c和d的二叉树中，对应的权值分别为7、5、2和4，构造哈夫曼树。

练习题
1. 设n为某棵哈夫曼树的叶子结点数目，则该哈夫曼树共有（ 2n-1 ）个结点。
2. 已知组成电文的字符集D及其概率分布W 为：
D=｛a,b,c,d,e｝
W=｛0.25, 0.30, 0.12, 0.25，0.08｝
用哈夫曼算法为该字符集中的字符编码，画出哈夫曼树。

1. 二叉树第i层上的结点数目最多为（ 2i-1 ）。
2. 在n个结点的线索二叉树中，线索的数目是（ n+1 ）。
3. 假设二叉树中所有非叶子结点都有左、右子树，则对有m个叶子结点的此类二叉树，结点总数为（ 2m-1 ）。
4. 已知二叉树T的后序遍历序列和中序遍历序列分别为H C D F I G B A E和D H C E F B G I A。
（1）试画出二叉树T；
（2）画出与二叉树T对应的中序线索二叉树；
（3）画出与该二叉树对应的树（森林）。

第七章图
存储
1. 邻接矩阵
顶点之间相邻关系用矩阵表示。

1. 邻接矩阵
顶点之间相邻关系用矩阵表示。

2. 邻接链表
顶点：通常按编号顺序将顶点数据存储在一维数组中
关联同一顶点的边：用线性链表存储

F 从图的某个顶点出发，访问图中的所有顶点，且使每个顶点仅被访问一次。这一过程叫做图的遍历。
F 遍历方法:深度优先遍历和广度优先遍历

F 生成树
Ø 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。

F 生成树的代价等于其边上的权值之和，我们把具有权值最小的生成树称为最小生成树。
F 普里姆算法和克鲁斯卡尔算法是两种常用的构造最小生成树的方法。

q 拓扑排序方法：
1) 在有向图中选一个无前趋的顶点v，输出之；
2) 从有向图中删除v及以v为尾的弧；
3) 重复1)、2)，直接全部输出全部顶点或有向图中不存在无前趋的结点时为止。

最短路径问题
1. 单源点最短路径问题：从一个顶点到其余各顶点的最短路径(迪杰斯特拉算法)
2. 每一对顶点间的最短路径问题(弗洛伊德算法)
问题：给定一个带权有向图G与源点v，求从v到G中其他顶点的最短路径，并限定各边上的权值大于或等于0。 迪杰斯特拉算法以路径长度递增的方式解单源点最短路径问题。

例题
1. 对于有n个顶点的完全无向图，其边数e等于（ n(n-1)/2 ）。
2. 一个连通图的生成树是一个（ 极小 ）连通子图，n个顶点的生成树有（ n-1 ）条边。
3. 假设含n个结点的无向图形成一个环，则它的生成树为（n）个。
4. 单源最短路径的Dijkstra算法是按路径长度（路经长度递增的次序）依次求解的。
5. 在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是（ m/2 ）条。
6. 已知一赋权有向图如下：
1. 写出该图的邻接矩阵表示并据此给出从顶点v1出发的深度优先遍历序列；
2. 说明该有向图是否强连通；
3. 给出该图的两个拓扑序列；
4. 若将该图视为无向图，用克鲁斯卡尔算法求最小生成树
l 已知一赋权有向图如下：
1. 写出该图的邻接矩阵表示并据此给出从顶点v1出发的深度优先遍历序列；
2. 说明该有向图是否强连通；

深度优先遍历序列：v1 v2 v3 v5 v7 v4 v6
该图不是强连通图，例如，存在v1至v2的路径，反之则没有。

第9章 查找
二分查找(折半查找)
q 折半查找判定树是描述折半查找过程的二叉树
若有序顺序表为：a1<a2<a3<a4<a5<a6<a7<a8
则其判定树（(low+high)/2）如下：

q 二分查找判定树:描述二分查找过程的二叉树

F 若有序顺序表为：a1<a2<a3<a4<a5<a6<a7<a8
则其判定树（(low+high)/2）如下：

二叉排序树
F 二叉排序树(二叉检索树、二叉查找树)定义
Ø 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
Ø 若其左子树不空，则左子树上所有结点的值均小于它的根结点的值；
Ø 若其右子树不空，则右子树上所有结点的值均大于它的根结点的值
Ø 其左、右子树也分别为二叉排序树
F 查找：查找键值等于key的记录
Ø 若二叉排序树为空树，则查找失败，返回；若根结点的键值等于key，则查找成功，返回；若根结点的键值大于key，则到根的左子树上继续查找；否则，到根的右子树上继续查找；

BSTNode *BSTSearch (BSTNode *bt, KeyType key) {
//在T指向根的二叉排序树中递归地查找关键字等于key的数据元素
//若找到，返回指向该结点的指针，否则返回NULL
if (bt==NULL) return NULL;
else if (bt->key==key) return bt;
else if (key < bt->key)
return BSTSearch (bt->lchild, key);
else
return BSTSearch (bt->rchild, key);
}//BSTSearch

二叉排序树的查找性能分析
F 若查找成功，则走了一条从根结点到某结点的路径，若查找失败，则走到一棵空的子树时为止。因此，最坏情况下，其平均查找长度不会超过树的高度。

二叉排序树的构造

平衡二叉树

四种平衡处理
F 在平衡二叉排序树上插入结点时，其祖先结点的平衡因子可能发生变化，离插入结点最近且平衡因子变为2或-2的祖先结点作为根的子树称为最小不平衡子树。
F 一般情况下，假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a，则失去平衡后进行调整的规律可归纳为以下四种情况：
RR型左旋平衡处理
LL型右旋平衡处理
LR型先左后右旋转平衡处理
RL型先右后左旋转平衡处理
哈希表查找
F 一个散列结构是一块地址连续的存储空间，它与一个称为散列（哈希）函数的函数相关联，该函数是数据记录的关键字到地址空间的映射。
Hash：关键字→ 哈希地址
F 这种存储空间的使用方式，使得
(1) 存储记录时，通过散列函数计算出记录的存储位置并按此存储位置存储记录
记录位置 ＝ Hash(记录的关键字)
(2)访问记录时，同样利用散列函数计算存储位置，然后根据所计算出的存储位置访问记录

F 散列技术中的主要问题
表面上看，设置了散列函数后，只需作简单的函数计算就可以实现元素的定位及查找操作，但事实上没有这么简单，概括起来，主要有以下两个问题：
(1) 冲突及解决
一般情况下，设计出的散列函数很难是单射的，即不同的关键字会对应到同一个存储位置，这样就造成了冲突(碰撞)。此时，发生冲突的关键字互为同义词。
(2)散列函数的设计
设计一个简单、均匀、存储空间利用率高、冲突少的散列函数是关键。
构造哈希函数的常用方法
1．直接定址法
2．数字分析法
3．平方取中法
4．折叠法
5．除留余数法 该方法的散列函数形式为：
Hash(key) = key % p
其中，p为不大于散列表表长m的整数
6. 随机法
常用的冲突解决方法
1． 开放地址法
开放定址法利用下列公式求“下一个”空地址
Hi = (H(key)+di) MOD m i=1,2,…K(K<=m-1)
其中H(key)为散列函数，m为散列表长度，di为增量序列
根据di的取法，解决冲突时常使用下面一些方法：
(1) 线性探测再散列
(2) 二次探测再散列
(3) 伪随机探测再散列
假设哈希表的地址为0~m-1，则哈希表的长度为m。
若一个关键字在地址d处发生冲突，则依次探查d+1，d+2，…，当达到表尾m-1时，又从0，1，2，….开始探查，直到找到一个空闲位置来存储冲突的关键字，将这一种方法称为线性探测再散列。
Hi = (H(key)+di) MOD m i = 1,2,…,k (k≤m-1)
其中，H(key)为关键字key的哈希函数值，di=1,2,3,…,m-1
例如: 给定关键字序列如下，散列函数为H(k)=k%13
19，14，23，1，68，20，84，27，55，11，10，79
试用线性探测再散列法建立散列表。

2． 链地址法

例题
1. 对于查找算法来说, 通常以（ 平均查找长度 ）作为衡量查找算法好坏的依据.
2. 在关键字序列为（5 , 10, 19 , 21 , 28 , 34 , 41，53 , 58 ,65）的顺序表中，用折半法查找关键字为5的记录（mid＝（low＋high）DIV 2），需要经过（ 3 ）次比较。
3. 对二叉排序树进行（中序）遍历，可将树中结点按关键字值进行升序排列。
4. 在平衡二叉树中，任意结点的左、右子树的高度之差为（ -1、0、1 ）。

第十章 排序
例题
1. 排序方法的稳定性是指（ ）。
2. 对于直接插入排序, 当待排序列中记录按关键字（ 有序 ）排列时, 所需进行关键字间比较的次数达最小值n-1, 记录不需移动。
3. 将两个长度分别为m和n的有序表归并成一个有序表（ m£ n），需要的元素比较次数最少为（ m ）。
4. 快速排序在（ 元素有序 ）的情况下排序性能最差。
5. 每趟排序都是从未排序的子序列中依次取出元素与已经排好序的序列中元素进行比较，然后将其放在已经排好序的序列的合适位置。这种排序法称为（直接插入）排序法。
6. 希尔排序、快速排序、堆排序和二路归并排序法中，要求辅助空间最多的是（二路归并排序）。
7. 在希尔排序、冒泡排序、选择排序、直接插入排序、快速排序、基数排序等方法中，关键字比较的次数与记录的初始排列次序无关的排序方法是（选择排序、基数排序）。
8. 设有序列（503，87，512，61，908，170，897）
（1）写出增量为3时进行一趟希尔排序的结果；
（2）建成一个小顶堆；
（3）给出执行一趟快速排序的结果；
（4）写出进行3路归并排序的过程。

术语解释
数据结构 逻辑结构 存储结构
头结点 头指针 单链表
栈 队列
哈夫曼树
最小生成树 AOV网 拓扑排序 AOE网 关键路径
平均查找长度 二叉排序树 哈希表