数据结构笔记

第一章

1. 什么是数据结构

数据结构是一种存储、组织和管理数据的方式，以便能高效地访问和修改数据。

什么是算法： 算法是用于解决或完成某个问题的一组明确指令，是数据结构操作的方法与步骤。

2. 人用计算机解决问题的五个步骤

① 明确问题
② 分析问题
③ 设计解决方案
④ 编程实现
⑤ 测试与改进

3. 程序与算法的区别

算法是程序的核心，程序是算法的具体实现。
算法独立于编程语言和计算机，而程序必须依赖编程语言和计算机才能运行。

4. 算法的特征

① 有穷性
② 确定性
③ 可行性
④ 输入/输出性

5. 数据结构基本术语

数据元素、数据项、数据对象。

6. 渐近符号及其意义

① 渐近上界 $O(n)$ : $0 \le f(n) \le cn$
② 渐近下界 $\Omega(n)$ : $0 \le cn \le f(n)$
③ 紧渐近界 $\Theta(n)$ : $cn \le f(n) \le C_2n$
④ 非紧上界 $o(n)$ : $0 \le f(n) < cn$
⑤ 非紧下界 $\omega(n)$ : $0 \le cn < f(n)$

第二章

1. 线性表的逻辑存储结构

① 元素之间存在一对一的顺序关系（前驱和后继）。
② 顺序、链式。

2. 线性表的顺序与链式存储结构

3. 顺序与链式插入和删除

头插法
序列反转

4. 循环链表与双向循环链表

① 循环链表从任意结点出发均可找到其它结点。
② 双向链表为空表时，头结点的前驱和后继同时指向自己。
③ 带尾指针的循环链表：查找开端与终端都方便。

5. 查找算法

① 顺序查找：适用于顺序或链式表 $ASL = \frac{(1+n)n}{2n} = \frac{n+1}{2}$ 时间复杂度 $O(1) - O(n)$ ；空间复杂度 $O(1)$
② 索引查找：适用于分块有序的顺序或链式表 $ASL = ASL(\text{索引}) + ASL(\text{块内})$ 分块 $\to$ 建立索引项（关键字项+指针项） $\to$ 组合成索引表

③ 折半查找：适用于有序的顺序表 $ASL = \log_2^{n+1} - 1$ 代码实现：

int binarySearch(int r[], int aim, int start, int end){
    if(start > end) return -1;
    int mid = (start + end) / 2;
    if(r[mid] == aim) return mid;
    else if(r[mid] < aim) binarySearch(r, aim, mid+1, end);
    else if(r[mid] > aim) binarySearch(r, aim, start, mid-1);
}

④ 哈希查找：适用于顺序或链式表，分割相加，舍弃进位。
- 哈希函数：直接哈希、数字分析、平方取中、折叠、除留取余、随机数法。
- 冲突解决：开放地址法（线性、平方、随机探测再散列）、再哈希法、链地址法、公共溢出区法。

6. 排序算法

折半查找主位 $\to$ 折半插入排序

① (直接)插入排序：顺序查找定位 $\to$ 挤空 $\to$ 插入

时间复杂度： $O(n) - O(n^2) - O(n^2)$
空间复杂度： $O(1)$
稳定排序

代码实现：

void insertSort(int r[], int n){
    for(int i=1; i<n; i++){
        int temp = r[i];
        int j = i-1;
        while(r[j] > temp && j >= 0){
            r[j+1] = r[j];
            j--;
        }
        r[j+1] = temp;
    }
}

② 希尔排序：分为若干个子序列，分别进行插入排序

时间复杂度： $O(n \log n) \sim O(n^2)$
空间复杂度： $O(1)$
不稳定排序

代码实现：

void shellSort(int r[], int n, int d[], int m){
    int k = 0;
    while(k < m){
        int c = d[k];
        for(int i = c; i < n; i += c){
            int temp = r[i];
            int j = i - c;
            while(r[j] > temp && j >= 0){
                r[j + c] = r[j];
                j -= c;
            }
            r[j + c] = temp;
        }
        k++;
    }
}

③ 选择排序：每次将无序序列中的最大/小值加入有序序列

时间复杂度： $O(n^2) - O(n^2)$
空间复杂度： $O(1)$
不稳定排序

代码实现：

void selectSort(int r[], int n){
    for(int i = 0; i < n; i++){
        int min_index = i;
        for(int j = i + 1; j < n; j++){
            if(r[j] < r[min_index]){
                min_index = j;
            }
        }
        swap(r[i], r[min_index]);
    }
}

④ 冒泡排序：每次将最大元素冒到序列末尾

时间复杂度： $O(n) - O(n^2) - O(n^2)$
空间复杂度： $O(1)$
稳定排序

⑤ 快速排序：递归地交换元素，比基准值小的放左边，大的放右边

时间复杂度： $O(n \log n) - O(n \log n) - O(n^2)$
空间复杂度： $O(\log n) \sim O(n)$
不稳定排序

代码实现：

void quickSort(int r[], int s, int e) {
    if (s < e) {
        int edge = partion(r, s, e);
        quickSort(r, s, edge-1);
        quickSort(r, edge+1, e);
    }
}

⑥ 归并排序：递归地将数组拆分并合并

时间复杂度： $O(n \log n) - O(n \log n) - O(n \log n)$
空间复杂度： $O(n)$
稳定排序

第四章

1. 二叉树、满二叉树、完全二叉树的定义

① 二叉树：每个结点最多有两个子结点（称为左右孩子）的树。
② 满二叉树：只有度数为2和度数为0（叶子结点）结点的树。
③ 完全二叉树：除了最后一层外其它层的结点都被填满，并且最后一层的节点从左到右依次排列的树。

2. 二叉树的遍历方法

① 先序遍历
② 中序遍历：栈实现（初始化，根节点入栈；若栈不空则访问栈顶元素并将其左孩子入栈直至左孩子为空；出栈并将右孩子入栈转步骤二）
③ 后序遍历
④ 层次遍历：队列实现（初始化，根节点入队；若队非空，出队并访问出队结点，将其左右孩子入队；若队空，则结束遍历）

递归实现：

void preOrder(BiTree bt){
    if (bt){
        printf("%d \t", bt->data);
        preOrder(bt->lchild);
        preOrder(bt->rchild);
    }
}

3. 遍历结果恢复二叉树

BiTree recoverTree(char* preorder, char* inorder, int s, int e, int* index){
    TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));
    node->data = preorder[*index];
    (*index)++;
    if (s <= e){
        int midpos = seekPos(inorder, s, e, node->data);
        node->lchild = recoverTree(preorder, inorder, s, midpos-1, index);
        node->rchild = recoverTree(preorder, inorder, midpos+1, e, index);
    }
    return node;
}

4. 森林 ↔ 树 ↔ 二叉树

① 森林 → 二叉树: A. 兄弟结点依次用右指针相连 B. 子树用左指针相连 C. 左子树是其第一棵子树，右子树是其兄弟结点

② 二叉树 → 森林: A. 从根节点开始断开所有右子树 B. 右子树的每个根节点作为一棵新的树

5. 森林和树的存储方式

树：链式森林：顺序/链式

第五章

1. 深度优先搜索与广度优先搜索

① DFS: A. 访问指定的某顶点 $v_0$ ，作为当前顶点 B. 访问顶点的下一个未被访问的邻接点，作为当前顶点 C. 直至顶点的所有邻接点都被访问，回退到尚有邻接点尚未被访问的结点，重复 B

void DFS(Graph g, int v0, int visited[]) {
    visited[v0] = 1;
    w = firstadj(g, v0);
    while (w != 0) {
        if (visited[w] == 0) DFS(g, w, visited);
        w = nextadj(g, v0, w);
    }
}

→ 可用栈实现

② BFS: A. 访问 $v_0$ ，将 $v_0$ 作为顶点 B. 访问所有未被访问的邻接点，依次将这些点作为顶点 C. 重复 B → 队列实现

Linked Notes

No outgoing note links.

Referenced By

No backlinks yet.