数据结构与算法 期末备考重点总结

数据结构与算法 期末备考重点总结

引用

CSDN

1.

https://m.blog.csdn.net/2301_78902861/article/details/143574622

本文是针对数据结构与算法课程的期末备考重点总结，涵盖了绪论、线性表、堆栈和队列、数组和字符串、树和二叉树、集合、哈希表、图以及排序算法等多个重要主题。文章对每个主题进行了详细的分类和提炼，适合用于复习和备考。

总体分为九个部分：

1. 绪论
2. 线性表
3. 堆栈和队列
4. 数组和字符串
5. 树、二叉树和搜索树
6. 集合
7. 图
8. 哈希表
9. 排序

第一部分：绪论

1. 基本概念

• 数据 (Data)：是信息的载体，可被计算机识别并加工处理的对象。
• 数据元素(Element)：组成数据的基本单位，具有一定意义。
• 数据项 (Item)：是组成数据元素的、不可分割的最小单位。

数据元素的逻辑结构可以分为线性结构和非线性结构（集合，图形，树）两类。数据元素的存储结构可以分为顺序，链式，索引和散列四种存储结构。数据的运算主要包含搜索，插入，删除，更新四种运算。同一逻辑结构可以对应多种存储结构。同样的运算，在不同的存储结构中，其实现过程是不同的。

2. ADT（抽象数据类型）

用来表示类似于C++中的模板概念，便于泛型分析。

3. 算法复杂度分析

主要关注时间复杂度，同数据的规模，方法的执行次数成正相关，用O（x）来表示起主要影响力的数量级（Ps：如果你高数还没忘光的话应该还记得这和佩亚诺余项长的非常相似）。

第二部分：线性表

1. 顺序存储结构

• 可以近似的视为一维数组。在C++内以std::vector的实现形式居多，C语言则主要以一维数组为主。

2. 链式存储结构

• 普通单链表和带表头结点的单链表：使用指针来记录链表，链表的每个节点均包含一个值节点和一个next指针，指针类型为本节点名指针。头节点可以用于代表该链表，头节点一般不存放数据。
• 单循环链表：将单链表中最后一个结点的指针域存储头结点的地址，使得整个单链表形成一个环，这种头尾相接的单链表称为单循环链表。
• 双向链表：在普通链表的基础上增加一个前驱指针。

第三部分：堆栈和队列

1. 堆栈Stack

• 后进先出
• 主要结构为栈顶元素top
• C实现如下：建栈Create、销毁和清除Destory/Clear、判满和判空Full/Empty、获取栈顶top、入栈Push、出栈Pop
• 栈同样可以进行链式存储，这里不做赘述
• 在C++中，可以通过使用STL容器std::stack来执行上述操作

2. 队列Queue

• 先进先出
• 主要元素为队头front和队尾rear
• 假溢出解决方案（循环队列）
• C实现如下：建队Crate、销毁和清除Destory/Clear、判满和判空Full/Empty、获取队头Front、入队Enqueue、出队Dequeue
• 队列也可以采用链式存储实现
• 在C++中，可以使用std::queue来使用队列

3. 中缀表达式和后缀表达式

• 在力扣上有逆波兰表达式求值的题目，可以去训练一下
• 中缀表达式向后缀表达式转化
• 至于分治，递归和非递归，建议实操感受，没有硬性知识点，只要能顺利理解汉诺塔问题的解决，这一部分就不会有问题

第四部分：数组和字符串

1. 数组Array

• 一维数组同普通数组
• 行优先存储下地址的计算
• 列优先存储下地址的计算

2. 矩阵Matrix

• 对称矩阵
• 稀疏矩阵
• 稀疏矩阵的快速转置算法：难点，建议有时间单独细啃

3. 字符串String

• 本质上就是字符数组
• C++内可以使用std::string来实现字符串

核心 第五部分：树和二叉树，搜索树

1. 树Tree

• 直接定义
• 递归定义
• 基本术语

2. 二叉树Binary Tree

• 特殊二叉树
• 二叉树的存储表示
• 二叉树的运算
• C实现
• 二叉树的遍历：中序遍历（LVR）、后序遍历（VRL）、先序遍历（VLR）、层序遍历

3. 森林Forest

4. 堆Heap

5. 优先队列PriorityQueue

• 创建Create
• 销毁Destroy
• 判空Empty
• 判满Full
• 获取元素数量Size
• 追加Append
• 移出Serve
• 特别提示，在C++ 11以上版本中，可以使用STL提供的std::priority_queue来直接使用优先队列

6. 哈夫曼树Haffman Tree

7. 二叉搜索树Binary Search Tree(BST)

• 查找思想为二分查找
• 二叉搜索树的插入Insert
• 二叉搜索树的删除Erase

8. 二叉平衡树（AVL树）

• 有关具体的单旋转和双旋转的过程可以参照该文章AVL树旋转详解

9. m叉平衡树 m-Tree

10. B-树 B-Tree

11. B+树 B+Tree

• 拓展内容，考试不做要求，可看B+树真的不难，楼下菜大爷都能学得会的B+树！（数据结构可视化神器推荐）_数据结构b+树可视化-CSDN博客

第六部分：集合

1. 集合Set

• C++11后，可以使用封装好的STL容器std::set和std::multiset来表示集合和可重复集合

2. 线性查找Linear Search

• 无序表Unordered List
• 有序表Ordered List：哨兵在成功之后会截断搜索

3. 二分查找Binary Search

• 通常情况下在算法题里的二分查找形式

4. 平均搜索长度ASL

第七部分：哈希表（散列技术）

1. 哈希表HashMap

• 在C++11后，可以使用封装好的STL容器std::unordered_mapstd::pair来表示哈希表了，而std::unordered_set可以用于表示哈希集合

2. 哈希函数Hash Function

• 将函数体中的key采用线性表达式修正后能改进一些不足

3. 哈希冲突Hash Collision

• 拉链法
• 线性探查法

• 二次探查法
• 双散列法

第八部分：图

1. 图Map

2. 邻接矩阵Adjacency matrix

3. 邻接表Adjacency List

4. 深度优先搜索Depth First Search(DFS)

5. 广度优先搜索Breadth First Search(BFS)

6. 拓扑排序和AOV网

7. 关键路径和AOE网

8. 最小生成树Minimu Spanning Tree（MST）

9. 普利姆算法Prim's Algorithm

10. 克鲁斯卡尔算法Kruskal's Algorithm

11. 单源最短路径Single-Source Shortest Path(SSSP)

• 由于教学PPT的内容不尽详细，关于单源最短路径具体可参考单源最短路径（Dijkstra算法）_单元最短路径算法-CSDN博客

12. 所有顶点的最短路径All-Pairs Shortest Paths

• 学校的教学PPT上没有关于Floyd算法的详细内容，但课本上仍然有这方面的内容，若要具体了解可参考该篇博文
• 图的所有顶点间的最短路径（Floyd算法）_走完所有点的最短路径算法-CSDN博客

第九部分：排序Sort

1. 选择排序Selection Sort

2. 插入排序Insertion Sort

3. 冒泡排序Bubble Sort

4. 快速排序Quick Sort

5. 归并排序Merge Sort

6. 堆排序Heap Sort

• 教学PPT没有给出完整的堆排序示例，不过追溯到之前第五章的堆部分，可以使用其建堆算法和调整算法完成具体的堆排序。
• 个人建议，在C++11后，可以使用封装好的STL容器std::priority_queue来作为优先队列辅助执行堆排序，个人亲自尝试，在Leetcode的部分追求性能的算法题里，用该辅助容器执行的堆排序要快于内置是std::sort（通常是快排）

7. 外排序External Sort

• 教学PPT上没有，书上也只提了一嘴，不需要掌握，只作了解即可
• 可以参考数据结构——外部排序-CSDN博客

此外，还有一种著名的排序算法，希尔排序，但是未被列入教学PPT中，可供参考数据结构——希尔排序（详解）-CSDN博客

祝各位期末考试顺利通关！