冷月手撕408之数据结构(1)-导论

在408中，其中数据结构和组成原理各占45分,操作系统占35分,计算机网络占25分。其中数据结构占的分最多，也是最难的一科。

数据结构可以算是计算机专业最核心的一科，它具有很强的抽象性和逻辑性。很多人刚刚开始学数据结构的时候都很难受。但是它从知识点来说，其实并不是很难。难的是融会贯通。

其实，在408中数据结构考的更多的还是概念题，算法题更多的只是线性表中的基本操作，以及查找排序中的知识。而树、图更多的只是在选择题中考察概念的理解。

今天冷月开始了数据结构的知识点整理，数据结构的主要构架如下图（pdf版或xmind源文件请关注公众号：学长冷月，回复数据结构）。

冷月点睛

在绪论中，理解算法的评价标准。时间复杂度和空间复杂度。时间复杂度要知道怎么计算的。

线性表分为顺序表和链表。

顺序表其实就可以理解为数组。逻辑上相邻的元素物理上也相邻。

链表分为单链表、双链表、循环链表、静态链表；

重要掌握链表的分类和插入、删除方法。逻辑上相邻的元素物理不一定上也相邻。

只能在一端进行插入和删除的线性表。重点掌握顺序栈的结构

只能在一端进行插入和另一端删除的线性表。重点掌握静态队列的结构

树重点掌握二叉树的性质，和二叉树的顺序存储和链式存储。以及线索二叉树。树的三种遍历也是经常考。在树的应用中，掌握二叉树排序树、二叉树平衡树、哈夫曼树。

图中，一定要搞清楚图的基本术语，因为图的术语有很多。无向图和有向图都不一样。

其中掌握图的顺序存储和链式存储；图的遍历经常考，DFS、BFS；

图的应用一定要会手动的模拟，写不出算法没有关系。最小生成树、最短路径、拓扑排序、关键路径。

查找是基于排序的，有些乱序的序列需要先排好序后再查找。其中折半查找和查找树以及散列查找，hash函数经常考。

KMP算法明白原理即可。

排序的算法很多，408要求主要掌握内部排序。重点搞清楚交换排序和选择排序，要明白各种排序的优势在哪儿和时间复杂度。