数据结构复习表

*章节*	*概念*	*简答计算*	*操作*	*算法设计*
绪论	数据结构逻辑结构和存储结构算法时间复杂度	能对给定的算法分析时间复杂度、空间复杂度
线性表	顺序表单链表	顺序表和链表的优缺点对比P48表2.2熟记已知数据元素大小，对顺序表中第i个元素的地址进行推导计算由数据元素在内存的存储推导数据元素之间的后继关系	单链表的删除、插入，不写算法	顺序表、单链表根据指定复杂度的要求设计算法，没给出复杂度要求的，自行设计
栈和队列	栈和队列	入栈、出栈序列，入队、出队序列的合法性判断，循环队列有关的队空、队满的条件判断、出入队操作		循环队列的实现双栈的实现
串、数组和广义表	广义表	模式串的next函数值（考研）数组的行为主、列为主存储时元素地址计算特殊矩阵的存储，计算地址广义表取表头表尾
树和二叉树	二叉树满二叉树，完全二叉树线索线索二叉树和线索化哈夫曼树，哈夫曼编码，前缀编码WPL	基于二叉树5条性质的、基于二叉树5条性质+某种形态（比如满，完全，哈夫曼）推导计算顶点个数、树的层数等。二叉树有哪些不同形态WPL的计算P140习题	写出二叉树的遍历序列，或由遍历序列恢复二叉树二叉树与森林的转换P129给二叉树加线索哈夫曼树构造、存储终态P133例5.2哈夫曼编码的形成	二叉树的遍历算法有关二叉树的一些统计、判断
图	强连通图和强连通分量 AOE，AOV连通图的生成树最小生成树关键路径，关键活动，	P181习题计算图中结点的出入度计算图中路径长度计算活动的最早、最迟开始时间计算时间的最早、最迟发生时间	图的邻接矩阵、邻接表存储表示图的深度、广度优先遍历得到的顶点访问序列、生成树P156会用图的两种算法画出最小生成树P160， P162Dijkstra算法求最短路径P167例6.2拓扑排序用途、过程P170-171关键路径解决了哪两个问题P173，会找关键活动P174-176例6.4
查找	查找表，静态查找表，动态查找表ASL，BST, AVL二叉排序树	计算查找成功时平均查找长度计算查找失败时平均查找长度	画出决策树P189二叉排序树的构建过程P196图7.8（注意输入序列中关键字的顺序不变）二叉排序树的插入、查找、删除某元素的过程平衡二叉树的调整、B+和B-树的调整（考研要会）选择某种解决冲突方法后的散列表的创建P218图7.30、P220例7.3，学习散列表的样子以及比较次数的计算散列表创建后查找某元素在不在的过程	顺序查找算法实现（可否递归）折半查找算法实现（可否递归）二叉排序树的查找、插入、创建算法的实现
排序	排序稳定的排序方法和不稳定的排序方法堆	P253的8.7.1中的计算要会（考研）P260页表8.2排序方法比较熟记	希尔排序直接插入排序、折半插入排序快速排序、冒泡排序堆排序、简单选择排序二路归并排序	选择排序冒泡排序直接插入排序

概念

1,数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

2,存储结构：数据对象在计算机中的存储表示。（物理结构）

（1）顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系的，通常借助程序设计语言的数组类型来描述。（2）链式存储结构：无需占用一整块空间，但为了表示结点间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。

3,逻辑结构：逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

4,算法的定义及特性：

（1）有穷之：一个算法必须总是在执行又穷步后结束，且每一步都必须在有穷时间内完成。

（2）确定性：对于每种情况下所应执行的操作，在算法中都有确定的规定，不会产生二义性，算法的执行者或阅读者都能明确其含义及然后执行。

（3）可行性：算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。

（1）输入：一个算法有0个或多个输入。

（2）输出：一个算法有一个或多个输出。

5,数据元素的四种关系：

集合结构：数据元素之间除了“属于同一集合”关系外，别无其它关系。

线性结构：数据结构之间存在一对一的关系。

树结构：数据元素之间存在一对多的关系。

图结构或网状结构：数据结构之间存在多对多的关系。

6,时间复杂度：T(n)=O(f(n))随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。

7,线性表：由n（n>=0）个数据特性相同的元素构成的有限序列。（n=0时为空表）
8,顺序表

线性表的顺序表示又被称为顺序存储结构或顺序映像

9,单链表

结点只有一个指针域的链表

10,栈：限定仅在表尾进行插入或删除操作的、后进先出的线性表，

11,队列：只允许在表的一端插入，在另一端删除元素，先进先出的线性表。

12,广义表(Lists，又称列表)是一种非连续性的数据结构，是线性表的一种推广。

13, 二叉树：n(n>=0)个结点所构成的集合（或为空树，或为非空树）。

14,满二叉树：深度为k且含有2^k-1个结点的二叉树。

15,完全二叉树：深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应的二叉树。

16,若结点有左子树，则其LChild域指向其左孩子，否则LChild域指向其前驱结点；若结点有右子树，则其RChild域指向其右孩子，否则RChild域指向其后继结点。

——这种改变指向的指针称为“线索”

17,加上了线索的二叉树称为线索二叉树

18,对二叉树按某种遍历次序使其变为线索二叉树的过程叫做线索化

19,哈夫曼树是一种带权路径长度最短的二叉树，通常用于构建哈夫曼编码。在哈夫曼树中，权值较小的节点离根较远，权值较大的节点离根较近。

** 哈夫曼树（最优树）：假设有m个权值{w1，w2,...,wm},可以构造一棵含n个叶子结点的二叉树，每个叶子结点的权值为wi，则其中带权路径WPL最小的二叉树称为哈夫曼树。**

20,哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，对每个右分支赋予1，则从根到每个叶子的路径上，各分支的赋值分别构成一个二进制串，该二进制串称为哈夫曼编码。

21,长短不等的编码，必须是任一字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码

22,带权路径长度(WPL)：在AOE-网中，一条路径各弧上的权值之和。

23,强连通图：在有向图G=（V，{A}）中，若对于每对顶点vi、vj∈V且vi≠vj，从vi到vj和vj到vi都有路径，则称该有向图为强连通图。

23,强连通分量:有向图中的极大强连通子图

24,AOV-网: 无环的有向图

25,AOE-网: 带权的有向图

26,连通图的生成树:**生成树：**包含无向图G所有顶点的极小连通子图。它含有图中的全部顶点，但只有足已构成一棵树的n-1条边。

27,关键路径：一条源点到汇点的带权路径长度最长的路径。

28,关键活动：关键路径上的活动。

29,查找表：同一类型的数据元素（或记录）构成的集合。

30,静态查找表：只查找，不改变集合内的数据元素。

31,动态查找表：既查找，又改变（增减）集合内的数据元素。

32,ASL:在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数称为平均查找长度。

33,BST:二叉排序树：或者是一棵空树，或者是（1）若它的左子树不空，则左子树上所有节点上的值小于它根节点的值（2）若它的右子树不空，则右子树上所有节点上的值大于它根节点的值（3）他的左右子树分别是二叉排序树。
34, 平衡二叉树：一棵二叉排序树，左子树和右子树的深度差的绝对值不超过1，且左子树和右子树也是平衡二叉树。

35,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列

36, 排序稳定、不稳定：假设关键字Ki=Kj(1<=i<=n,1<=j<=n,i!=j),且在排序前的序列中Ri领先于Rj，而在排序后Ri仍然领先于Rj，则稳定，反之不稳定。

37,堆:n个元素的序列{k1,k2,k3,k4…}称之为堆,当且仅当满足下面条件时

ki>=k2i且ki>=k2i+1

ki<=k2i且ki<=k2i+1(1<=i<=n/2)

简答计算

时间复杂度

常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

线性阶O(n)

这个在最开始的代码示例中就讲解过了，如：

for(i=1; i<=n; ++i){
  j = i;
  j++;
}

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

对数阶O(logN)

还是先来看代码：

int i = 1;
while(i<n){
  i = i * 2;
}

从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n
也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：*O(logn)*

线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

就拿上面的代码加一点修改来举例：

for(m=1; m<n; m++){
  i = 1;
  while(i<n){
    i = i * 2;
  }
}

1. *平方阶O(n²)*

平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。
举例：

for(x=1; i<=n; x++){
	for(i=1; i<=n; i++){
    j = i;
    j++;
      }
  }
}

这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²)
如果将其中一层循环的n改成m，即：

for(x=1; i<=m; x++){
    for(i=1; i<=n; i++){
  	   j = i;
	   j++;
  }
}

那它的时间复杂度就变成了 O(m*n)

1. *立方阶O(n³)*、*K次方阶O(n^k)*

参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。

除此之外，其实还有平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度的分析方法，有点复杂，这里就不展开了。

空间复杂度

既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：

空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
举例：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

空间复杂度 O(n)

我们先看一个代码：

int[] m = new int[n]
for(i=1; i<=n; ++i){
  j = i;
  j++;
}

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

顺序表和链表的优缺点对比(熟记)

已知数据元素大小，对顺序表中第i个元素的地址进行推导计算

由数据元素在内存的存储推导数据元素之间的后继关系

栈和队列

下图为栈的入栈出栈序列合法性判断

挺简单枚举一下就行

初始状态（队空条件）：Q->front == Q->rear == 0。
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
出队操作：队不空时，先取队头元素值，再将队头指针加1。

队首内存位置比队尾小

内存

1 2 3 4 5 6

队首队尾

左首右尾尾进首出

2、循环队列

解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

当队首指针Q->front = MAXSIZE-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。

初始时：Q->front = Q->rear=0。

队首指针进1：Q->front = (Q->front + 1) % MAXSIZE。

队尾指针进1：Q->rear = (Q->rear + 1) % MAXSIZE。

队列长度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE。

那么，循环队列队空和队满的判断条件是什么呢？

显然，队空的条件是 Q->front == Q->rear 。若入队元素的速度快于出队元素的速度，则队尾指针很快就会赶上队首指针，如图( d1 ）所示，此时可以看出队满时也有 Q ->front == Q -> rear 。

为了区分队空还是队满的情况，有三种处理方式

1）牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”，如图 ( d2 ）所示。

队满条件： (Q->rear + 1)%Maxsize == Q->front

队空条件仍： Q->front == Q->rear

队列中元素的个数： (Q->rear - Q ->front + Maxsize)% Maxsize

（2）类型中增设表示元素个数的数据成员。这样，队空的条件为 Q->size == O ；队满的条件为 Q->size == Maxsize 。这两种情况都有 Q->front == Q->rear

（3）类型中增设tag 数据成员，以区分是队满还是队空。tag 等于0时，若因删除导致 Q->front == Q->rear ，则为队空；tag 等于 1 时，若因插入导致 Q ->front == Q->rear ，则为队满。

这是从零开始的情况

现行现列是第一行到目标行之前的行数

视情况改变

以行为主序存储（现行×总列+现列）*字节

那么通用公式就是，对于数组 a[ m ][ n ] 中的元素 a[ i ][ j ] 有：

ADDRESS（ a[ i ][ j ] ）= A + （ i * n + j ）* sizeof（int）

以列为主序存储（现列×总行+现列）*字节

ADDRESS（ a[ i ][ j ] ）= A + （ j * m + i ）* sizeof（int）

例题：

压缩存储对称矩阵的方法有两种：压缩列存储法（Column-wise Compression）和压缩行存储法（Row-wise Compression）。下面我将分别介绍这两种方法以及地址计算的具体步骤。

压缩列存储法

对于一个n×n的对称矩阵，只需存储上三角部分的元素。存储时，按列的顺序一个一个存储，从第一列开始，逐列存储该列中主对角线以下的元素。

地址计算公式

：如果i <= j，则元素A[i][j]存储在****A_comp[j*(j+1)/2+i]****的位置。

*例子：* 考虑对称矩阵：

1
2
3

A = | 1 2 3 |
	| 2 4 5 | 
	| 3 5 6 |

注意：主对角线的上三角

使用压缩列存储法，只存储****上三角部分****的元素：

1	A_comp = [1, 2, 4, 3, 5, 6]

对于元素A[2][1] = 2，由于2 <= 1，所以该元素存储在****A_comp[1*(1+1)/2+2] = A_comp[3]****的位置。

压缩行

则可类比

广义表取表头表尾

GetHead是取广义表的第一个元素，要去掉一个"()“，而GetTail是除掉第一个元素剩下的元素组成的广义表，也就是除掉第一个元素，再把剩余的元素”()"。

基于二叉树5条性质

1.在二叉树的第i层上至多有2i−1个结点（i>=1）。

2.深度为k的二叉树至多有2k−1个结点（k>=1）。

3.对于任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

4.具有n个节点的完全二叉树深度为⌊log2n⌋+1。

5.如果对一颗有n个结点的完全二叉树（其深度为⌊log2n⌋+1）的结点按层序编号（从第一层到⌊log2n⌋+1层，每层从左到右），对任一结点i（1<=i<=n）有：

如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点⌊i/2⌋。
如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

基于二叉树5条性质+某种形态（比如满，完全，哈夫曼）推导计算顶点个数、树的层数等。

二叉树有哪些不同形态

1.空树
2.只有一个根结点
3.根结点只有左子树
4.根结点只有右子树
5.根结点既有左子树又有右子树

1.完全二叉树
2.满二叉树
3.二叉排序数
4.平衡二叉树
5.红黑树
6.哈夫曼树
B树，B+树，B*树

WPL的计算

带权路径长度(WPL)：在AOE-网中，一条路径各弧上的权值之和。

P181习题

计算图中结点的出入度

对无向图而言，顶点v 的度是指和v相关联的边的数目，记作TD(v)
对有向图而言，顶点v的度是其入度和出度之和
- 入度(Indegree): 以v为终点的有向边的条数，记作ID(v)
- 出度(Outdegree): 以v为始点的有向边的条数，记作OD(v)

顶点的出度=第i行元素之和顶点的入度=第i列元素之和

计算图中路径长度

路径长度: 路径上边或弧的数目/权值之和

计算活动的最早、最迟开始时间

图D-P18

计算时间的最早、最迟发生时间

图D

计算查找成功时平均查找长度

计算查找失败时平均查找长度

常见的平均查找长度总结-CSDN博客

在这里插入图片描述

依次累加计算所有叶结点的带权路径长度

从上面构造的哈夫曼树可知所有结点的路径长度，例如结点”16“的路径长度为2。所以WPL=(16+21+30)*2+(10+12)*3=200

排序方法比较熟记

复习

数据结构手写
1, #include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

// 邻接矩阵存储结构
typedef struct {
    int vertexCount;
    int matrix[MAX_VERTICES][MAX_VERTICES];
} GraphMatrix;

// 初始化图
void initGraphMatrix(GraphMatrix* G) {
    G->vertexCount = 0;
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            G->matrix[i][j] = 0;
        }
    }
}

// 插入顶点
void InsertVertex(GraphMatrix* G, int v) {
    if (G->vertexCount < MAX_VERTICES) {
        G->vertexCount++;
    }
}

// 插入边
void InsertArc(GraphMatrix* G, int v, int w) {
    if (v >= 0 && v < G->vertexCount && w >= 0 && w < G->vertexCount) {
        G->matrix[v][w] = 1;
        G->matrix[w][v] = 1;
    }
}

// 删除顶点
void DeleteVertex(GraphMatrix* G, int v) {
    if (v >= 0 && v < G->vertexCount) {
        for (int i = 0; i < G->vertexCount; i++) {
            G->matrix[v][i] = 0;
            G->matrix[i][v] = 0;
        }
        G->vertexCount--;
    }
}

// 删除边
void DeleteArc(GraphMatrix* G, int v, int w) {
    if (v >= 0 && v < G->vertexCount && w >= 0 && w < G->vertexCount) {
        G->matrix[v][w] = 0;
        G->matrix[w][v] = 0;
    }
}
2,#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

// 邻接表存储结构
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct {
    int vertexCount;
    Node* adjLists[MAX_VERTICES];
} GraphList;

// 初始化图
void initGraphList(GraphList* G) {
    G->vertexCount = 0;
    for (int i = 0; i < MAX_VERTICES; i++) {
        G->adjLists[i] = NULL;
    }
}

// 插入边
void InsertArc(GraphList* G, int v, int w) {
    if (v >= 0 && v < G->vertexCount && w >= 0 && w < G->vertexCount) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->vertex = w;
        newNode->next = G->adjLists[v];
        G->adjLists[v] = newNode;
    }
}

// 判断是否存在路径 - 深度优先搜索
int hasPathDFS(GraphList* G, int start, int end, int visited[]) {
    if (start == end) {
        return 1; // 找到路径
    }

    visited[start] = 1;

    Node* current = G->adjLists[start];
    while (current != NULL) {
        if (!visited[current->vertex] && hasPathDFS(G, current->vertex, end, visited)) {
            return 1; // 递归找到路径
        }
        current = current->next;
    }

    return 0; // 未找到路径
}

// 判断是否存在路径 - 广度优先搜索
int hasPathBFS(GraphList* G, int start, int end) {
    int visited[MAX_VERTICES] = {0};
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;

    visited[start] = 1;
    queue[rear++] = start;

    while (front < rear) {
        int currentVertex = queue[front++];
        Node* current = G->adjLists[currentVertex];
        while (current != NULL) {
            int neighbor = current->vertex;
            if (neighbor == end) {
                return 1; // 找到路径
            }
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                queue[rear++] = neighbor;
            }
            current = current->next;
        }
    }

    return 0; // 未找到路径
}

int main() {
    GraphList G;
    initGraphList(&G);
    
    // 插入边
    InsertArc(&G, 0, 1);
    InsertArc(&G, 1, 2);
    InsertArc(&G, 2, 3);
    
    int start = 0;
    int end = 3;
    
    int visited[MAX_VERTICES] = {0};
    
    // 深度优先搜索
    if (hasPathDFS(&G, start, end, visited)) {
        printf("Path exists (DFS).\n");
    } else {
        printf("Path does not exist (DFS).\n");
    }
    
    // 重置 visited 数组
    for (int i = 0; i < G.vertexCount; i++) {
        visited[i] = 0;
    }
    
    // 广度优先搜索
    if (hasPathBFS(&G, start, end)) {
        printf("Path exists (BFS).\n");
    } else {
        printf("Path does not exist (BFS).\n");
    }

    return 0;
}