注:编程语言C。对此课程进行了全面总结。在最后附加了更多的应用实例,需要做更多的题目来领会数据结构的思想。
“此文内容来源于=>中国大学MOOC=>数据结构(浙江大学:陈越、何钦铭)”
“https://www.icourse163.org/learn/ZJU-93001#/learn/content”
注:总体来说,细节很多,需要刨根问底,数据结构是一门科学,并不仅仅应用于计算机科学体系中。
第一讲概念偏多,虽然不易理解,但是为其他章节/入门数据结构与算法做了很好的引子,其中的demo务必领会。
第二讲以线性结构为基础,线性结构是数据结构里面最基础、也是最简单的一种数据结构类型。
堆栈在计算机中有广泛用途,比如函数调用、递归、表达式求值。堆栈跟队列一样,也是一种受限制的线性表,比如日常排队。通过多项式案例的解决思路来总结线性结构的一系列特性。
第三讲到第五讲为树,树是数据结构的基石,重中之重,后续章节以树为开展点学习,必须打牢此部分!静态查找:顺序、二分、黄金分割。二叉树类型:完全、完美、斜二叉树。顺序存储:数组与链表。遍历:先序、中序、后续、层次。插入删除查找。AVL平衡二叉树:高度、斐波那契序列、翻转:RR、LL、RL、LR。堆:最大最小堆、建立插入删除、哈夫曼树与哈夫曼编码、集合与运算。
第六讲到第八讲为图,图是十分强大的数据结构!存储:邻接矩阵(有向图、无向图)(结构初始化、建立、边的插入和删除)(无向图元素位置计算、邻接点、度、稀疏图与稠密图/完全图)、邻接表(结构初始化、建立、边的插入和删除)。遍历:深度优先搜索DFS、广度优先搜索BFS。图的连通:无向图(连通、路径、回路、连通图、连通分量)、有向图(强连通、强连通图、强连通分量)。最短路径:单源最短路经(有向无权图-BFS-邻接表存储,有向有权图-Dijkstra-邻接矩阵存储),多源最短路径(无向有权图-Floyd-邻接矩阵存储)。最小生成树:贪心prim算法那(无向稠密图-无回路计算-O(|V|^2))、贪心Kruskal算法(无向稀疏图-有回路计算-最小堆并查集-O(|E|Log|E|))。
第九讲到第十讲为排序,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。大批量数据的排序算法效率十分重要,内部和外部排序、排序的稳定性、没有任何一种算法在任何一种情况下都是最快最好的。简单排序(插入、冒泡、时间复杂度下界、逆序对)、希尔排序(间隔排序、增量序列-Sedgewick)、堆排序(堆调整、性能低于希尔排序-Sedgewick)、归并排序(有序子列合并-递归合并与非递归合并)。快速排序:分而治之(递归、选主元与子集)。表排序:间接输出、顺序输出、物理排序(O(mN))。基数排序:先桶排序、后基数排序。
桶排序之前的算法一个共同特点:仅仅基于比较大小来决定元素位置的,这些算法的最坏/下界时间复杂度是O(NLogN),不管运行多坏,总能制造出一个最坏的情况,让算法以最快的方法跑,也只能跑到O(NLogN),有没有可能更快呢?也就是除了比较之外,还能干点别的事,这就是基数排序,在基数排序之前,需要先学习桶排序。多关键字排序:次位优先LSD快于主位优先MSD。
第十一讲为散列/哈希查找,目的更快地查找。查找的本质:已知对象找位置。散列主要内容:计算位置(构造散列函数确定关键词存储位置)、解决冲突(应用某种策略解决多个关键词位置相同的问题)。散列函数构造方法:直接定址发、除留余数法(常用)、数字分析法、折叠法、平方取中法。冲突处理方法:开放定址法(线性/一次探测)、平方/二次探测、双散列探测、再散列,链地址法/分离链接法。性能分析:装填因子(不能超过0.85)、空间换时间、成功平均查找长度ASLs、失败平均查找长度ASLu、期望值与实际值。