YAZONG 我的开源

数据结构汇总 置顶!

  , ,
0 评论0 浏览

:编程语言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、期望值与实际值。

第一讲:基本概念(陈越)

1.1什么是数据结构

1.2什么是算法

1.3应用实例:最大子列和问题

第二讲:线性结构(何钦铭)

2.1线性表及其实现-多项式与表达式求值

2.2堆栈-顺序存储、链式存储与表达式求值

2.3队列-顺序存储与链式存储

2.4应用实例:多项式-搭建、读入、乘除、输出

第三讲:树(上)(何钦铭)

3.1树与树的表示

3.2二叉树及存储结构

3.3二叉树的遍历

第四讲:树(中)(何钦铭)

4.1二叉搜索树-比线性效率高

4.2平衡二叉树/搜索树AVL

第五讲:树(下)(何钦铭)

5.1 堆-建立插入删除

5.2 哈夫曼树/最优二叉树与哈夫曼编码

5.3 集合及运算

第六讲:图(上)(陈越)

6.1什么是图

6.2图的遍历

6.3如何建立图

第七讲:图(中)(陈越)

7.1 最短路径问题

第八讲:图(下)(陈越)

8.1最小生成树问题

8.2拓扑排序

第九讲:排序(上)(陈越)

9.1 简单排序(冒泡、插入)

9.2 希尔排序

9.3 堆排序

9.4 归并排序

第十讲:排序(下)(陈越)

10.1 快速排序

10.2 表排序

10.3 基数排序

10.4 排序算法的比较

第十一讲:散列查找(何钦铭)

11.1 散列表介绍

11.2 散列函数的构造方法

11.3 冲突处理方法

11.4 散列表的性能分析

11.5 应用实例:词频统计

11.6 应用实例:通话记录

案例分析

数据结构与算法-案例汇总


标题:数据结构汇总
作者:yazong
地址:https://blog.llyweb.com/articles/2023/06/01/1685575202758.html