Computer Science

WangMC Blog

数据结构期末复习

发表于 更新于 分类于
本文字数： 8.7k 阅读时长 ≈ 8 分钟

数据结构的期末复习考纲

数据结构期末考纲

顺序表和链表的类型定义

  • **顺序表:**用一组地址连续的存储单元依次存放线性表中的所有元素, 元素的存储位置与逻辑位置是一一对应关系

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T,size_t N>
struct SeqList{
    T data[N];
    int length;
    SeqList():length(0) {};
    
    size_t getCapacity() const {
        return N;
    }
};

using IntSeqList = SeqList<int,100>;

  • 链表: 用一组地址非连续的存储单元依次存放线性表中的所有元素, 元素间的先后关系利用指针来表示

1
2
3
4
5
6
7
template<typename T>
struct Node {
    T data;
    Node* next;
    Node<T>() : next(nullptr) {};
};
using LinkList = Node<int>*;

将两个有序的顺序表(链表)合并为一个有序的顺序表(链表) 分析合并操作的复杂度

  • 顺序表

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
IntSeqList mergeSeqList(IntSeqList& s1, IntSeqList& s2){
    if(s1 == NULL){
        s1 = s2;
        return s1;
    }
    if(s2 == NULL) return s1;
    
	int size1 = s1.length;
    int size2 = s2.length;
    int total_size = size1 + size2;

    IntSeqList new_seqlist;
    new_seqlist.length = total_size;
    
	int index1 = 0;int index2 = 0;
    int k = 0;
    while(index1 < size1 && index2 < size2){
		if(s1.data[index1]<s2.data[index2])  { new_seqlist.data[k] = s1.data[index1]; index1++;}
        else  { new_seqlist.data[k] = s2.data[index2]; index2++; }
        k++;         
    }
    
    if(index1 < size1 && index2 == size2){
       	while(index1 < size1){
            new_seqlist.data[k] = s1.data[index1];
            k++;
            index1++;
		}
    }
    else if(index1 == size1 && index2 < size2){
        while(index2 < size2){
            new_seqlist.data[k] = s2.data[index2];
            k++;
            index2++;
		}
	}
   return new_seqlist;
}

**时间复杂度：**O(n + m)

**空间复杂度：**O(n + m)

  • 链表

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
Node<int>* mergeLinkedList(LinkList& l1, LinkList& l2) {
    if (l1 == nullptr) {
        l1 = l2;
        return l1;
    }

    if (l2 == nullptr) return l1;

    LinkList cur = l1;

    LinkList temp1 = l1->next; LinkList temp2 = l2->next;
    while (temp1 && temp2) {
        if (temp1->data < temp2->data) {
            cur->next = temp1;
            temp1 = temp1->next;
        }
        else {
            cur->next = temp2;
            temp2 = temp2->next;
        }
        cur = cur->next;
    }

    cur->next = temp1 ? temp1 : temp2;
    delete l2;

    return l1;
}

**时间复杂度：**O(n + m)

**空间复杂度：**O(1)

在链表(顺序表)的某个节点后插入一个节点

链表

1
2
3
4
5
6
7
8
9
10
void insertNode(LinkList l, int index, T data) {
    LinkList cur = l;
    while (index--) {
        cur = cur->next;
    }
    Node<T>* new_node = new Node<T>;
    new_node->data = data;
    new_node->next = cur->next;
    cur->next = new_node;
}

顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<typename T>
void insertNode(IntSeqList& s, int index, T data) {
    if (index > s.length && s.length + 1 > s.getCapacity()) return;

    if (index <= 0) {
        for (int i = s.length - 1; i >= 0; i--) {
            s.data[i + 1] = s.data[i];
        }
        s.data[0] = data;
        s.length++;
        return;
    }

    for (int i = s.length - 1; i >= index; i--) {
        s.data[i + 1] = s.data[i];
    }
    s.data[index] = data;
    s.length++;
    return;
}

将一个链表(顺序表)进行倒置 并分析倒置操作的复杂度

链表

1
2
3
4
5
6
7
8
9
10
11
12
void reverseLL(LinkList l){
    LinkList pre = nullptr;
    LinkList cur = l;
    
    while(cur){
        LinkList temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    l = pre;
}

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

**空间复杂度：**O(1)

顺序表

1
2
3
4
5
6
7
8
9
10
void reverseSeq(IntSeqList& s){
	int i = 0; int j = s.length-1;
    while(i<j){
        int temp  = s.data[j];
        s.data[j] = s.data[i];
        s.data[i] = temp;
        i++;
        j--;
    }
}

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

**空间复杂度：**O(1)

无向图的链接表表示法和邻接矩阵表示法

邻接矩阵表示法: 利用二维数组来表示一个图,二维数组中的每一个元素表示相应的两个顶点之间的关系

​ 无向图的邻接矩阵为对称矩阵

链接表表示法: 将图的每一个顶点的邻接点存放在一个链表中 每个顶点对应一条链表,所有的头节点存放在一个数组中

利用DFS或BFS求一个图的连通分量数

DFS

递归版(图利用邻接矩阵来表示)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void DFS(vector<vector<int>>& isConnected,vector<int>& visited,int row){
     for(int i = 0;i<isConnected.size();i++){
         if(isConnected[row][i]&&!visited[i]){
            visited[i] = 1;
            DFS(isConnected,visited,i);
         }
     }
}

int findCircleNum(vector<vector<int>>& isConnected) {
    int num = 0;
    vector<int> visited(isConnected.size(),0);
    for(int i = 0;i<isConnected.size();i++){
     	if(!visited[i]){
            DFS(isConnected,visited,i);
            num++;
         }
     }
    return num;
}

栈实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int findCircleNum(vector<vector<int>>& isConnected) {
    int num = 0;
    vector<int> visited(isConnected.size(), 0);
    stack<int> s;

    for(int i = 0; i < isConnected.size(); i++) {
        if(!visited[i]) {
            s.push(i);
            while(!s.empty()) {
                int temp = s.top();
                s.pop();
                visited[temp] = 1;
                for(int j = 0; j < isConnected.size(); j++) {
                    if(isConnected[temp][j] && !visited[j]) {
                        s.push(j);
                    }
                }
            }
            num++;
        }
    }
    return num;
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int findCircleNum(vector<vector<int>>& isConnected) {
    int num = 0;
    vector<int> visited(isConnected.size(), 0);
    queue<int> q;

    for (int i = 0; i < isConnected.size(); i++) {
        if (!visited[i]) {
            q.push(i);
            while (!q.empty()) {
                int temp = q.front();
                q.pop();
                visited[temp] = 1;
                for (int j = 0; j < isConnected.size(); j++) {
                   if (isConnected[temp][j] && !visited[j]) {
                       q.push(j);
                    }
                }
            }
            num++;
        }
    }
    return num;
}

利用Floyd算法求图的任意两点的最短距离，图的传递闭包(Floyd-Warshall)

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
//最短距离
void floyd(vector<vector<int>>& matrix,vector<vector<int>>& grid)
{
    grid = matrix;
    int n = grid.size();
    for(int k = 0; k < n;K++){
		for(int i = 0; i < n;i++){
            for(int j = 0; j < n;j++){
                grid[i][j]=min(grid[i][j],grid[i][k]+grid[k][j]);
            }
        }
    }
}

//传递闭包(使用前需将矩阵转换为使用0和1表达的矩阵)
void floydWarshall(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] |= matrix[i][k] & matrix[k][j];
            }
        }
    }
}

判断两个左右链表表示的二叉树是否等价 并分析时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

bool isSameTree(TreeNode* p, TreeNode* q) {
    if(p == nullptr && q == nullptr) return true;
    if(p == nullptr || q == nullptr) return false;
    if(p->val != q->val) return false;

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

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

将一个整数序列转化为大顶堆(小顶堆)的过程描述

大顶堆

  • 将此整数序列看作一棵完全二叉树的数组形式

  • 从最后一个非叶节点开始进行下沉操作,保证父节点大于子节点,使其堆化

  • 倒序遍历每个节点,重复上述操作 直至根节点

删除堆顶(大顶堆或小顶堆)的过程描述

  • 将堆顶元素与堆中最后一个元素互换

  • 删除最后一个元素

  • 从堆顶元素开始,从顶至底进行下沉操作使其堆化

构建哈夫曼树的过程, 并计算带权路径长度

假设给了n个元素

  • 将这n个元素看作n棵只有一个节点的二叉树,他们构成了森林F

  • 从森林F中选择两个权值最小的节点(树)构成一个新树, 新树的根节点的权值为这两个节点权值的和

  • 将这颗新树加入到森林F中 并删除F中的那两个被合并的节点

  • 重复上述过程 直至森林中只剩下一个树 该树即为哈夫曼树

**带权路径长度:**每个叶节点的权值与其到根节点的路径长度的乘积之和

利用栈求逆波兰表达式的值

假设该逆波兰表达式符合规范

  • 将该表达式中的元素依次遍历

  • 如果该元素是操作数 那么压入栈中 继续遍历下一个元素

  • 如果该元素是操作符 那么从栈中弹出所需数量的元素进行计算 并将计算结果压入栈中

  • 重复上述操作 直至遍历玩表达式中所有元素 栈顶元素即为该表达式的结果

最小生成树的构建方法

Prim

  • 构造一个名为minDist的数组,用来记录每个节点距离生成树的最短距离,长度为n,n为顶点的数量

  • 构造一个名为visited的数组,用来记录哪些节点已经被添加到最小生成树中,长度为n

  • 随机选择一个节点作为第一个节点加入到最小生成树中并将其在visited数组中标记为true

  • 更新minDist数组 即更新未被visited数组标记的节点到生成树的距离

  • 选择minDist数组中值最小且未被visited数组标记的节点加入生成树 并将该节点标记为true

  • 重复上述过程n-1次即可完成构建

Kruskal

  • 将图中的边按照权值由小到大进行排序

  • 初始化并查集,使每个顶点自成一个集合

  • 对排序后的边进行遍历

  • 利用并查集判断该边的两个顶点是否在同一个集合中

  • 如果在 则不能将此边加入生成树 否则会形成环

  • 如果不在 则将此边加入生成树 并将这两个顶点所在的集合合并

  • 重复上述过程 直至生成树中有n-1条边(n为顶点数目) 或遍历结束

利用Dijkstra求单源最短距离和最短路径,了解U d和p的含义;如何根据p求到每一个顶点到源点的最短路径

**U:**已经求出与源点的最短距离的顶点的集合

**d:**用来存放顶点到源点最短距离的数组,d[i]代表顶点i到源点的最短距离

**p:**用来存放最短路径树中每个节点的父节点的数组,p[i]代表最短路径树中节点i的父节点

1
2
3
4
5
6
7
8
void getPath(int p[N],int v){
	if(v==p[v]){
        cout<<v<<" ";
        return;
    }
    getPath(p,p[v]);
    cout<<v<<" ";
}

拓扑排序和关键路径的求法

拓扑排序

  • 定义一个队列q,统计图中每一个顶点的入度,将入度为零的顶点加入队列q中

  • 从队列q中取出一个顶点u,将其加入到拓扑序列中

  • 遍历顶点u的所有出边,将这些相邻点的入度减一,若其入度变为零,则将其加入到队列q中

  • 重复上述步骤,直至队列q为空

  • 如果队列q为空时 仍有顶点未加入到拓扑序列中 说明该图存在环 不存在拓扑序列

关键路径

  • 对图中各顶点进行拓扑排序，得到拓扑序列

  • 按照拓扑序列的顺序 依次计算每个事件的最早发生时间

  • 再根据每个事件的最早发生时间 求出每个活动的最早发生时间

  • 按照逆拓扑序 依次计算每个事件的最晚发生时间

  • 遍历每一个活动，计算其最早发生时间与最晚发生时间之差 若为零 则将该活动加入关键路径

二分查找及其复杂度分析

主要部分与插值查找相同 不同点为 mid = left+0.5*(right-left)

时间复杂度为 O(log n)

空间复杂度为 O(1)

插值查找

  • 确定被查找目标所在的范围边界,左边界记为left,右边界记为right

  • 设置查找点下标为 $mid=left+ (key-array[left]/array[right]-array[left])*(right-left)$

  • 开始循环 保证left不大于right

  • 判断以mid为下标的数组元素是否等于目标值

  • 如果等于 则找到目标 退出循环

  • 如果大于目标元素 则令right = mid - 1

  • 如果小于目标元素 则另left = mid + 1

  • 按照以上描述进行循环直至找到目标值 或不满足循环条件时退出循环

时间复杂度是O(loglogN)

当有序序列中的元素呈均匀分布时插值查找优于二分查找

KMP算法

令模式串为t 主串为s

  • 定义两个整数i，j 分别表示主串和模式串的下标，初始值设置为0

  • 当j == -1 或 t[j] == s[i]时 i和j同时加一 即同时向后移动一位

  • 如果t[j] != s[i]时 令j=next[j]

  • 重复上述过程直至遍历完i主串或j遍历完模式串

next数组

  • 使用整数j作为下标来遍历模式串

  • 令next[j] = 第j位的公共最长真前后缀的长度 特别规定next[0]=-1

优化next数组

  • 在上一个方法求next数组的基础之上 在j遍历模式串s的过程中添加如下判断

  • 判断 t[j]是否等于t[next[j]]

  • 如果等于 则令next[j] = next[next[j]]

二叉查找树

特点

  • 对于根节点，若它的左右子树不为空, 则左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值

  • 若它的左右子树都不为空, 则它的左右子树也分别为二叉查找树

构建二叉查找树

  • 将序列的第一个元素作为二叉查找树的根节点

  • 接着依次遍历序列中的剩余元素,并将该元素作为新节点

  • 如果新节点的值小于当前节点的值，则新节点应插入到左子树中

  • 如果新节点的值大于当前节点的值，则新节点应插入到右子树中

  • 重复上两个步骤，直到找到合适的叶子位置, 将其插入树中

  • 对序列中的每个元素进行如上操作直至遍历结束 至此二叉查找树构建完成

AVL树

四种基本形式及对应变形操作

  • LL旋转

    假设节点A是失衡的节点，节点B是A的左子节点，节点C是B的右子节点

    • B变为新的根节点。

    • A成为B的右子节点。

    • C（如果存在）成为A的左子节点

    image-20250108161439866

  • RR旋转

​ 与LL操作反之

  • LR旋转

​ 假设节点A是失衡的节点，节点B是A的左子节点

​ 首先对A的左子节点B进行RR旋转，然后对A进行LL旋转

image-20250108161749530

  • RL旋转

​ 与LR反之

构建AVL树

  • 将给定数据集的第一个元素作为AVL树的根节点

  • 按照二叉查找树的方式插入新的节点

  • 每次插入新节点后，更新该节点及其祖先节点的高度

  • 在每次插入操作后，计算当前节点及其祖先节点的平衡因子（左子树高度减去右子树高度）。

  • 如果平衡因子的绝对值大于1，则该节点失衡, 根据失衡节点的具体情况进行对应的旋转操作

  • 重复上述过程 直至所有元素被添加到AVL树中