408数据结构考研大纲详解

本文根据计算机专业考研408数据结构大纲，系统地整理了数据结构的核心知识点，包括基本概念、线性表、栈与队列、树与二叉树、图、查找和排序等内容。每个部分都包含了定义、性质、基本操作及其算法实现、时间复杂度分析和典型应用场景，帮助考生全面掌握数据结构的重要知识点。

一、绪论

1. 基本概念

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

基本术语：

  • 数据：描述客观事物的符号，是计算机中可以操作的对象
  • 数据元素：数据的基本单位
  • 数据项：构成数据元素的不可分割的最小单位
  • 数据对象：性质相同的数据元素的集合
  • 数据类型：一组性质相同的值的集合及定义在此集合上的一组操作
  • 抽象数据类型(ADT)：一个数学模型及定义在该模型上的一组操作

2. 算法与算法评价

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列。

算法特性：

  • 有穷性：算法必须在有限步骤内结束
  • 确定性：每一步骤都有明确的定义
  • 可行性：每一步都必须是可行的
  • 输入：有零个或多个输入
  • 输出：有一个或多个输出

算法评价：

  • 时间复杂度：算法执行所需的时间
  • 空间复杂度：算法执行所需的存储空间

常见的时间复杂度：

  • O(1)：常数阶
  • O(log n)：对数阶
  • O(n)：线性阶
  • O(n log n)：线性对数阶
  • O(n²)：平方阶
  • O(n³)：立方阶
  • O(2ⁿ)：指数阶

二、线性表

1. 线性表的定义与基本操作

线性表是具有相同数据类型的n个数据元素的有限序列，其中n≥0。

基本操作：

  • InitList(&L)：初始化线性表
  • Length(L)：返回线性表长度
  • LocateElem(L, e)：查找元素
  • GetElem(L, i)：获取指定位置的元素
  • ListInsert(&L, i, e)：插入元素
  • ListDelete(&L, i, &e)：删除元素
  • PrintList(L)：输出线性表
  • Empty(L)：判断线性表是否为空
  • DestroyList(&L)：销毁线性表

2. 线性表的顺序存储

顺序表是用一段地址连续的存储单元依次存储线性表的数据元素。

特点：

  • 随机访问，时间复杂度O(1)
  • 插入和删除需要移动元素，时间复杂度O(n)
  • 存储密度高

基本操作实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 顺序表的结构定义
typedef struct {
    ElemType *elem;  // 存储空间基址
    int length;      // 当前长度
    int size;        // 总容量
} SqList;

// 初始化顺序表
Status InitList(SqList &L) {
    L.elem = new ElemType[MAXSIZE];
    if (!L.elem) return ERROR;
    L.length = 0;
    L.size = MAXSIZE;
    return OK;
}

// 插入操作
Status ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return ERROR;
    if (L.length >= L.size) return ERROR;
    
    for (int j = L.length; j >= i; j--)
        L.elem[j] = L.elem[j-1];
    
    L.elem[i-1] = e;
    L.length++;
    return OK;
}

// 删除操作
Status ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return ERROR;
    
    e = L.elem[i-1];
    for (int j = i; j < L.length; j++)
        L.elem[j-1] = L.elem[j];
    
    L.length--;
    return OK;
}

3. 线性表的链式存储

链表是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。

单链表：

  • 每个节点包含数据域和指针域
  • 节点的存储地址是任意的
  • 查找元素需要遍历，时间复杂度O(n)
  • 插入和删除操作简单，时间复杂度O(1)（不考虑查找时间）

基本操作实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 单链表节点定义
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

// 初始化单链表（带头结点）
Status InitList(LinkList &L) {
    L = new LNode;
    L->next = NULL;
    return OK;
}

// 插入操作
Status ListInsert(LinkList &L, int i, ElemType e) {
    LNode *p = L;
    int j = 0;
    
    while (p && j < i-1) {
        p = p->next;
        j++;
    }
    
    if (!p || j > i-1) return ERROR;
    
    LNode *s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    
    return OK;
}

// 删除操作
Status ListDelete(LinkList &L, int i, ElemType &e) {
    LNode *p = L;
    int j = 0;
    
    while (p->next && j < i-1) {
        p = p->next;
        j++;
    }
    
    if (!p->next || j > i-1) return ERROR;
    
    LNode *q = p->next;
    p->next = q->next;
    e = q->data;
    delete q;
    
    return OK;
}

双链表：

  • 每个节点有两个指针域，分别指向前驱和后继节点
  • 可以双向遍历
  • 删除和插入操作更加灵活

循环链表：

  • 尾节点的指针指向头节点，形成一个环
  • 可以从任意节点出发遍历整个链表

三、栈与队列

1. 栈

栈是一种只允许在一端（栈顶）进行插入和删除操作的线性表，遵循后进先出(LIFO)原则。

基本操作：

  • InitStack(&S)：初始化栈
  • Push(&S, e)：入栈
  • Pop(&S, &e)：出栈
  • GetTop(S, &e)：获取栈顶元素
  • StackEmpty(S)：判断栈是否为空

顺序栈实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 顺序栈结构定义
typedef struct {
    ElemType *base;
    ElemType *top;
    int stacksize;
} SqStack;

// 初始化顺序栈
Status InitStack(SqStack &S) {
    S.base = new ElemType[MAXSIZE];
    if (!S.base) return ERROR;
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

// 入栈操作
Status Push(SqStack &S, ElemType e) {
    if (S.top - S.base >= S.stacksize) return ERROR;
    *S.top++ = e;
    return OK;
}

// 出栈操作
Status Pop(SqStack &S, ElemType &e) {
    if (S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
}

链栈实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 链栈节点定义
typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
} StackNode, *LinkStack;

// 初始化链栈
Status InitStack(LinkStack &S) {
    S = NULL;
    return OK;
}

// 入栈操作
Status Push(LinkStack &S, ElemType e) {
    StackNode *p = new StackNode;
    p->data = e;
    p->next = S;
    S = p;
    return OK;
}

// 出栈操作
Status Pop(LinkStack &S, ElemType &e) {
    if (S == NULL) return ERROR;
    e = S->data;
    StackNode *p = S;
    S = S->next;
    delete p;
    return OK;
}

栈的应用：

  • 表达式求值
  • 括号匹配
  • 函数调用
  • 递归实现
  • 中缀表达式转后缀表达式

2. 队列

队列是一种只允许在一端（队尾）进行插入操作，在另一端（队头）进行删除操作的线性表，遵循先进先出(FIFO)原则。

基本操作：

  • InitQueue(&Q)：初始化队列
  • EnQueue(&Q, e)：入队
  • DeQueue(&Q, &e)：出队
  • GetHead(Q, &e)：获取队头元素
  • QueueEmpty(Q)：判断队列是否为空

循环队列实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 循环队列结构定义
typedef struct {
    ElemType *base;
    int front;
    int rear;
} SqQueue;

// 初始化循环队列
Status InitQueue(SqQueue &Q) {
    Q.base = new ElemType[MAXSIZE];
    if (!Q.base) return ERROR;
    Q.front = Q.rear = 0;
    return OK;
}

// 入队操作
Status EnQueue(SqQueue &Q, ElemType e) {
    if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    return OK;
}

// 出队操作
Status DeQueue(SqQueue &Q, ElemType &e) {
    if (Q.front == Q.rear) return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    return OK;
}

链队列实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 链队列节点定义
typedef struct QNode {
    ElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

// 链队列结构定义
typedef struct {
    QueuePtr front;
    QueuePtr rear;
} LinkQueue;

// 初始化链队列
Status InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = new QNode;
    Q.front->next = NULL;
    return OK;
}

// 入队操作
Status EnQueue(LinkQueue &Q, ElemType e) {
    QNode *p = new QNode;
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

// 出队操作
Status DeQueue(LinkQueue &Q, ElemType &e) {
    if (Q.front == Q.rear) return ERROR;
    QNode *p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) Q.rear = Q.front;
    delete p;
    return OK;
}

队列的应用：

  • 广度优先搜索
  • 操作系统中的作业调度
  • 打印机任务队列
  • 消息缓冲区

四、树与二叉树

1. 树的基本概念

树是n(n≥0)个结点的有限集合，当n=0时称为空树，否则树满足：有且仅有一个特定的称为根的结点，其余结点可分为m(m≥0)个互不相交的有限集，每个集合本身又是一棵树，称为根的子树。

基本术语：

  • 结点的度：结点拥有的子树数
  • 树的度：树中结点的最大度数
  • 叶子结点：度为0的结点
  • 分支结点：度不为0的结点
  • 结点的层次：根结点为第1层，其子结点为第2层，以此类推
  • 树的高度：树中结点的最大层次
  • 森林：m(m≥0)棵互不相交的树的集合

2. 二叉树的定义与性质

二叉树是n(n≥0)个结点的有限集合，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的分别称为左子树和右子树的二叉树组成。

二叉树的性质：

  • 第i层上至多有2^(i-1)个结点
  • 高度为h的二叉树至多有2^h-1个结点
  • 对任何一棵二叉树，若叶子结点数为n0，度为2的结点数为n2，则n0=n2+1

满二叉树：一棵高度为h且含有2^h-1个结点的二叉树

完全二叉树：一棵高度为h的二叉树，其第1层到第h-1层的结点都达到最大个数，第h层的结点都连续集中在最左边

3. 二叉树的存储结构

顺序存储：

  • 适用于完全二叉树
  • 按层次顺序存储
  • 对于结点i，其左孩子为2i，右孩子为2i+1，父结点为⌊i/2⌋

链式存储：

1
2
3
4
5
// 二叉树结点定义
typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

4. 二叉树的遍历

先序遍历：根->左->右

1
2
3
4
5
6
7
void PreOrder(BiTree T) {
    if (T != NULL) {
        Visit(T);           // 访问根结点
        PreOrder(T->lchild); // 先序遍历左子树
        PreOrder(T->rchild); // 先序遍历右子树
    }
}

中序遍历：左->根->右

1
2
3
4
5
6
7
void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);  // 中序遍历左子树
        Visit(T);            // 访问根结点
        InOrder(T->rchild);  // 中序遍历右子树
    }
}

后序遍历：左->右->根

1
2
3
4
5
6
7
void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild); // 后序遍历左子树
        PostOrder(T->rchild); // 后序遍历右子树
        Visit(T);             // 访问根结点
    }
}

层次遍历：按层次从上到下，从左到右访问所有结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void LevelOrder(BiTree T) {
    InitQueue(Q);       // 初始化辅助队列
    BiTree p;
    EnQueue(Q, T);     // 根结点入队
    
    while (!QueueEmpty(Q)) {
        DeQueue(Q, p);  // 队头结点出队
        Visit(p);      // 访问出队结点
        
        if (p->lchild != NULL)
            EnQueue(Q, p->lchild); // 左子树根结点入队
        if (p->rchild != NULL)
            EnQueue(Q, p->rchild); // 右子树根结点入队
    }
}

5. 线索二叉树

线索二叉树是一种利用二叉树中空指针域的存储结构，将二叉树中的结点按某种遍历方式的前驱和后继关系记录在空指针域中。

结点结构：

1
2
3
4
5
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;  // 标志位，0表示指针指向孩子，1表示指针是线索
} ThreadNode, *ThreadTree;

6. 树与森林

树的存储结构：

  • 双亲表示法：每个结点中保存其双亲结点的位置
  • 孩子表示法：每个结点中保存其所有孩子结点的指针
  • 孩子兄弟表示法：每个结点保存指向第一个孩子和下一个兄弟的指针

树与二叉树的转换：

  • 树转换为二叉树：每个结点的左指针指向第一个孩子，右指针指向下一个兄弟
  • 森林转换为二叉树：先将森林中每棵树转换为二叉树，然后将每棵二叉树的根结点看作兄弟，用右指针连接

7. 哈夫曼树与哈夫曼编码

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。

构造方法：

  1. 将所有结点看作独立的树，构成森林
  2. 选择森林中权值最小的两棵树，作为新树的左右子树，新树的权值为两棵子树权值之和
  3. 从森林中删除这两棵树，将新树加入森林
  4. 重复步骤2和3，直到森林中只剩一棵树

哈夫曼编码是一种前缀编码，用于数据压缩，具有最优性。

五、图

1. 图的基本概念

图是由顶点集V和边集E组成的，记为G=(V,E)，其中V是非空集合，E是V中顶点的有序对或无序对集合。

基本术语：

  • 有向图：边有方向
  • 无向图：边无方向
  • 完全图：任意两个顶点之间都有边
  • 连通图：任意两个顶点之间都有路径
  • 连通分量：无向图的极大连通子图
  • 强连通图：有向图中任意两个顶点之间都有路径
  • 强连通分量：有向图的极大强连通子图
  • 生成树：包含图中所有顶点的一棵树
  • 生成森林：非连通图的生成树集合

2. 图的存储结构

邻接矩阵：

1
2
3
4
5
typedef struct {
    VertexType vex[MAX_VERTEX_NUM];      // 顶点表
    EdgeType arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vexnum, arcnum;                  // 顶点数和边数
} MGraph;

邻接表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct ArcNode {    // 边表结点
    int adjvex;             // 该边所指向的顶点的位置
    struct ArcNode *next;   // 指向下一条边的指针
    InfoType *info;         // 边权值等信息
} ArcNode;

typedef struct VNode {      // 顶点表结点
    VertexType data;        // 顶点信息
    ArcNode *first;         // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;       // 邻接表
    int vexnum, arcnum;     // 顶点数和边数
} ALGraph;

3. 图的遍历

深度优先搜索(DFS)：

1
2
3
4
5
6
7
8
void DFS(Graph G, int v) {
    visited[v] = TRUE;       // 标记v已访问
    Visit(v);               // 访问顶点v
    
    for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
        if (!visited[w])
            DFS(G, w);      // 递归访问v的未访问邻接点
}

广度优先搜索(BFS)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BFS(Graph G, int v) {
    visited[v] = TRUE;       // 标记v已访问
    Visit(v);               // 访问顶点v
    InitQueue(Q);           // 初始化辅助队列
    EnQueue(Q, v);          // v入队
    
    while (!QueueEmpty(Q)) {
        DeQueue(Q, v);       // 队头元素出队
        
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
            if (!visited[w]) {
                visited[w] = TRUE;
                Visit(w);
                EnQueue(Q, w);
            }
    }
}

4. 最小生成树

Prim算法：

  1. 从图中任选一个顶点加入树T
  2. 在所有与树T中顶点相邻的边中，选择权值最小的边(u,v)，其中u在T中，v不在T中
  3. 将顶点v和边(u,v)加入树T
  4. 重复步骤2和3，直到所有顶点都在T中

Kruskal算法：

  1. 将图中所有边按权值从小到大排序
  2. 从权值最小的边开始，如果该边不会与已选边构成回路，则选择该边
  3. 重复步骤2，直到选择了n-1条边（n为顶点数）

5. 最短路径

Dijkstra算法：求单源最短路径

  1. 初始化：S={源点s}，对所有顶点v，若v与s直接相邻，则dist[v]=边(s,v)的权值，否则dist[v]=∞
  2. 从未标记的顶点中选择dist值最小的顶点u，标记u
  3. 更新所有与u相邻的未标记顶点v的dist值：dist[v]=min{dist[v], dist[u]+边(u,v)的权值}
  4. 重复步骤2和3，直到所有顶点都被标记

Floyd算法：求所有顶点对之间的最短路径

1
2
3
4
5
6
7
8
9
10
11
void Floyd(Graph G) {
    for (int i = 0; i < G.vexnum; i++)
        for (int j = 0; j < G.vexnum; j++)
            D[i][j] = G.arc[i][j];    // 初始化D矩阵
    
    for (int k = 0; k < G.vexnum; k++)
        for (int i = 0; i < G.vexnum; i++)
            for (int j = 0; j < G.vexnum; j++)
                if (D[i][j] > D[i][k] + D[k][j])
                    D[i][j] = D[i][k] + D[k][j];  // 更新最短路径
}

6. 拓扑排序

拓扑排序是将有向无环图中的顶点排成一个线性序列，使得图中任意一对顶点u和v，若存在边<u,v>，则u在线性序列中出现在v之前。

算法步骤：

  1. 从图中选择一个没有前驱的顶点并输出
  2. 从图中删除该顶点和所有以它为起点的边
  3. 重复步骤1和2，直到图为空或图中不存在无前驱的顶点

7. 关键路径

关键路径是指在带权有向无环图中，从源点到汇点的路径中，具有最大路径长度的路径，这条路径上的活动称为关键活动。

算法步骤：

  1. 求各顶点的最早发生时间ve
  2. 求各顶点的最迟发生时间vl
  3. 求各活动的最早开始时间e
  4. 求各活动的最迟开始时间l
  5. 求各活动的时间余量l-e，时间余量为0的活动即为关键活动

六、查找

1. 查找的基本概念

查找是在数据集合中寻找满足条件的特定数据元素的过程。

查找的衡量指标：

  • 平均查找长度（ASL）：需要比较的关键字次数的期望值

2. 顺序查找

顺序查找是从表的一端开始，逐个检查关键字是否匹配。

算法实现：

1
2
3
4
5
6
int SeqSearch(int a[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (a[i] == key)
            return i;  // 查找成功，返回位置
    return -1;         // 查找失败
}

平均查找长度：

  • 查找成功：(n+1)/2
  • 查找失败：n

3. 二分查找

二分查找适用于有序表，每次将查找区间缩小一半。

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
int BinarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] == key)
            return mid;      // 查找成功
        else if (a[mid] > key)
            high = mid - 1;  // 在左半区间查找
        else
            low = mid + 1;   // 在右半区间查找
    }
    return -1;              // 查找失败
}

平均查找长度：O(log₂n)

4. 二叉排序树

二叉排序树（二叉搜索树）是一种特殊的二叉树，满足以下性质：

  • 若左子树不为空，则左子树上所有结点的值均小于根结点的值
  • 若右子树不为空，则右子树上所有结点的值均大于根结点的值
  • 左、右子树也分别为二叉排序树

查找操作：

1
2
3
4
5
6
7
8
BiTree SearchBST(BiTree T, KeyType key) {
    if (!T || key == T->data.key)
        return T;
    if (key < T->data.key)
        return SearchBST(T->lchild, key);  // 在左子树中查找
    else
        return SearchBST(T->rchild, key);  // 在右子树中查找
}

插入操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status InsertBST(BiTree &T, ElemType e) {
    if (!T) {  // 树为空，创建新结点
        T = new BiTNode;
        T->data = e;
        T->lchild = T->rchild = NULL;
        return TRUE;
    }
    if (e.key == T->data.key)  // 关键字已存在
        return FALSE;
    if (e.key < T->data.key)
        return InsertBST(T->lchild, e);  // 在左子树中插入
    else
        return InsertBST(T->rchild, e);  // 在右子树中插入
}

删除操作：

  1. 若被删结点是叶子结点，直接删除
  2. 若被删结点只有左子树或右子树，用子树替代被删结点
  3. 若被删结点有左右子树，用直接后继（右子树中最小的结点）或直接前驱（左子树中最大的结点）替代被删结点

5. 平衡二叉树

平衡二叉树（AVL树）是一种特殊的二叉排序树，任意结点的左右子树高度差不超过1。

平衡因子：结点的左子树高度减去右子树高度

旋转操作：

  • LL型：右旋
  • RR型：左旋
  • LR型：先左旋后右旋
  • RL型：先右旋后左旋

6. B树和B+树

B树是一种多路平衡查找树，常用于文件系统和数据库索引。

B树的性质：

  • 每个结点最多有m个子树
  • 除根结点和叶子结点外，其他结点至少有⌈m/2⌉个子树
  • 所有叶子结点都在同一层

B+树是B树的变种，有以下特点：

  • 非叶子结点只存储索引，不存储数据
  • 所有数据都存储在叶子结点中
  • 叶子结点之间用指针连接，形成有序链表

7. 散列表

散列表（哈希表）是一种根据关键字直接访问数据的数据结构。

散列函数：将关键字映射到散列表地址的函数

处理冲突的方法：

  • 开放定址法：线性探测、二次探测、双散列
  • 链地址法：将同一地址的冲突元素用链表连接
  • 再散列法：使用另一个散列函数
  • 建立公共溢出区

散列查找的平均查找长度：与装填因子α有关，α越大，平均查找长度越长

七、排序

1. 排序的基本概念

排序是将一组数据按照特定的顺序重新排列的过程。

排序的稳定性：相同关键字的元素在排序前后相对位置不变，则称排序算法是稳定的

内部排序：数据全部存放在内存中进行排序

外部排序：数据太大，无法全部放入内存，需要借助外存进行排序

2. 插入排序

直接插入排序：将一个元素插入到已排序的序列中的适当位置

1
2
3
4
5
6
7
8
9
10
11
void InsertSort(int a[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {
        if (a[i] < a[i-1]) {  // 若第i个元素小于前一个元素
            temp = a[i];      // 暂存a[i]
            for (j = i-1; j >= 0 && a[j] > temp; j--)
                a[j+1] = a[j];  // 后移元素
            a[j+1] = temp;      // 插入到正确位置
        }
    }
}

时间复杂度：O(n²)

空间复杂度：O(1)

稳定性：稳定

希尔排序：将序列分成若干子序列，对每个子序列进行直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void ShellSort(int a[], int n) {
    int i, j, d, temp;
    for (d = n/2; d >= 1; d = d/2) {  // 步长序列
        for (i = d; i < n; i++) {
            if (a[i] < a[i-d]) {
                temp = a[i];
                for (j = i-d; j >= 0 && a[j] > temp; j -= d)
                    a[j+d] = a[j];
                a[j+d] = temp;
            }
        }
    }
}

时间复杂度：与步长序列有关，平均为O(n^1.3)

空间复杂度：O(1)

稳定性：不稳定

3. 交换排序

冒泡排序：相邻元素两两比较，将最大的元素逐渐”冒”到序列的末尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void BubbleSort(int a[], int n) {
    int i, j, temp, flag;
    for (i = 0; i < n-1; i++) {
        flag = 0;  // 标记本轮是否发生交换
        for (j = 0; j < n-1-i; j++) {
            if (a[j] > a[j+1]) {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                flag = 1;  // 发生了交换
            }
        }
        if (flag == 0)  // 如果没有发生交换，说明已经有序
            break;
    }
}

时间复杂度：O(n²)

空间复杂度：O(1)

稳定性：稳定

快速排序：选择一个基准元素，将序列分为两部分，一部分小于基准，一部分大于基准

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int Partition(int a[], int low, int high) {
    int pivot = a[low];  // 选择第一个元素作为基准
    while (low < high) {
        while (low < high && a[high] >= pivot)
            high--;
        a[low] = a[high];  // 将比基准小的元素移到左边
        while (low < high && a[low] <= pivot)
            low++;
        a[high] = a[low];  // 将比基准大的元素移到右边
    }
    a[low] = pivot;  // 基准元素放到最终位置
    return low;       // 返回基准元素的位置
}

void QuickSort(int a[], int low, int high) {
    if (low < high) {
        int pivotpos = Partition(a, low, high);
        QuickSort(a, low, pivotpos-1);   // 排序左子序列
        QuickSort(a, pivotpos+1, high);  // 排序右子序列
    }
}

时间复杂度：平均O(n log n)，最坏O(n²)

空间复杂度：O(log n)

稳定性：不稳定

4. 选择排序

简单选择排序：每次从未排序序列中选择最小的元素放到已排序序列的末尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void SelectSort(int a[], int n) {
    int i, j, min, temp;
    for (i = 0; i < n-1; i++) {
        min = i;  // 记录最小元素位置
        for (j = i+1; j < n; j++)
            if (a[j] < a[min])
                min = j;  // 更新最小元素位置
        if (min != i) {   // 交换a[i]和a[min]
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
}

时间复杂度：O(n²)

空间复杂度：O(1)

稳定性：不稳定

堆排序：利用堆的性质进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 调整以k为根的子树为大根堆
void HeapAdjust(int a[], int k, int n) {
    int i, temp = a[k];
    for (i = 2*k+1; i < n; i = 2*i+1) {  // i为k的左孩子
        if (i+1 < n && a[i] < a[i+1])    // 取左右孩子中较大者
            i++;
        if (temp >= a[i])  // 根结点已是最大
            break;
        a[k] = a[i];       // 将较大的孩子上移
        k = i;             // 继续向下调整
    }
    a[k] = temp;          // 放入最终位置
}

void HeapSort(int a[], int n) {
    int i, temp;
    // 建立大根堆
    for (i = n/2-1; i >= 0; i--)
        HeapAdjust(a, i, n);
    // 排序
    for (i = n-1; i > 0; i--) {
        temp = a[0];       // 堆顶元素与最后一个元素交换
        a[0] = a[i];
        a[i] = temp;
        HeapAdjust(a, 0, i);  // 重新调整堆
    }
}

时间复杂度：O(n log n)

空间复杂度：O(1)

稳定性：不稳定

5. 归并排序

归并排序：将两个或多个有序序列合并成一个有序序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 合并两个有序序列
void Merge(int a[], int low, int mid, int high) {
    int *temp = new int[high-low+1];  // 辅助数组
    int i = low, j = mid + 1, k = 0;
    
    while (i <= mid && j <= high) {  // 比较两个子序列的元素
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    
    while (i <= mid)   // 复制剩余元素
        temp[k++] = a[i++];
    while (j <= high)
        temp[k++] = a[j++];
    
    for (i = 0; i < k; i++)  // 将temp中的元素复制回a
        a[low+i] = temp[i];
    
    delete[] temp;
}

void MergeSort(int a[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(a, low, mid);      // 排序左半部分
        MergeSort(a, mid+1, high);   // 排序右半部分
        Merge(a, low, mid, high);    // 合并两部分
    }
}

时间复杂度：O(n log n)

空间复杂度：O(n)

稳定性：稳定

6. 基数排序

基数排序：按照关键字的位数进行排序，从低位到高位或从高位到低位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void RadixSort(int a[], int n, int d) {  // d为最大位数
    int *temp = new int[n];
    int *count = new int[10];  // 计数器
    int i, j, k;
    int radix = 1;
    
    for (i = 1; i <= d; i++) {  // 从低位到高位
        for (j = 0; j < 10; j++)
            count[j] = 0;  // 计数器清零
        
        for (j = 0; j < n; j++) {
            k = (a[j] / radix) % 10;  // 获取当前位的数字
            count[k]++;  // 统计每个数字出现的次数
        }
        
        for (j = 1; j < 10; j++)
            count[j] += count[j-1];  // 将count转换为位置索引
        
        for (j = n-1; j >= 0; j--) {  // 从后向前遍历，保证稳定性
            k = (a[j] / radix) % 10;
            temp[count[k]-1] = a[j];  // 放入对应位置
            count[k]--;
        }
        
        for (j = 0; j < n; j++)
            a[j] = temp[j];  // 将临时数组复制回原数组
        
        radix *= 10;  // 处理下一位
    }
    
    delete[] temp;
    delete[] count;
}

时间复杂度：O(d(n+r))，其中d为位数，r为基数（这里为10）

空间复杂度：O(n+r)

稳定性：稳定

7. 各种排序算法的比较

排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性
直接插入排序 O(n²) O(n²) O(1) 稳定
希尔排序 O(n^1.3) O(n²) O(1) 不稳定
冒泡排序 O(n²) O(n²) O(1) 稳定
快速排序 O(n log n) O(n²) O(log n) 不稳定
简单选择排序 O(n²) O(n²) O(1) 不稳定
堆排序 O(n log n) O(n log n) O(1) 不稳定
归并排序 O(n log n) O(n log n) O(n) 稳定
基数排序 O(d(n+r)) O(d(n+r)) O(n+r) 稳定

总结

本文系统地整理了408数据结构考研大纲的核心知识点，包括基本概念、线性表、栈与队列、树与二叉树、图、查找和排序等内容。每个部分都包含了定义、性质、基本操作及其算法实现、时间复杂度分析和典型应用场景，帮助考生全面掌握数据结构的重要知识点。

数据结构是计算机科学的基础，也是408考研的重点科目之一。掌握好数据结构不仅对考研有帮助，对未来的学习和工作也有很大的益处。希望本文能够帮助考生系统地复习数据结构，取得好成绩。