《大话数据结构》知识结构图
2022-04-18 16:36:48 举报
AI智能生成
登录查看完整内容
相似推荐
查看更多
复合结构图
数据结构
数据结构·栈
java知识结构
数据结构
数据结构
数据结构图
系统功能结构图
数据结构图__1
JAVA基础知识结构图
程杰的《大话数据结构》知识体系图
作者其他创作
大纲/内容
集合结构(非线性结构)
数组
优点:无需为表示表中元素之间的逻辑关系而增加额外的存储空间可以快速的存取表中任意位置的元素,时间复杂度为O(1)
缺点:插入和删除操作需要移动大量元素当线性表成都变化较大时,难以确定存储空间的容量造成存储空间的\"碎片\"
顺序存储结构,用一段地址连续的存储单元一次存储线性表的数据元素。比如数组
顺序存储结构
优点:单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制插入和删除更快,时间复杂度为O(n),在给出某位置的指针后,复杂度仅为O(1)
缺点:查找效率比顺序存储结构差,时间复杂度为O(n)
链表中每个结点可以包含若干个数据域和若干个指针域。如果每个结点中只包含一个指针域,则称其为单链表。
单链表
优点:插入和删除只需要修改游标,无需移动元素从而改进了在顺序存储结构中的插入,删除许移动大量元素的缺点
缺点:没有解决连续存储分配带来的表长难以确认的问题失去了顺序存储结构随机存取的特性
用数组描述的链表叫静态链表(用数组代替指针)
静态链表
将单链表中终端结点的指针段由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表就称为单循环链表,简称循环链表
循环链表
在单链表的每个结点中,再设置一个指向其前驱结点的指针域(就意味着双向链表的结点都有俩个指针域,一个指向直接后继,一个指向直接前驱)
双向链表
链式存储结构
存储结构
适合数量不固定,读取操作少,增删改多的场景。比如C#中的LinkedList
线性表
顺序存储结构(顺序栈)
链式存储结构(链栈)
限定仅在表尾进行插入和删除操作的线性表,又称后进先出(LIFO)的线性表(允许插入和删除的一端称为栈顶,另一端称为栈底)
栈(特殊的线性表)
循环队列
顺序存储结构(顺序队列)
链式存储结构(链队列)
只允许在一端进行插入操作,而另一端进行删除操作的线性表先进先出(FIFO)
队列(特殊的线性表)
效率很低,复杂度为O((n-m+1)*m) n是总的字符串,m是需要匹配的字符串
朴素的描述匹配(从头开始一个个字符匹配)
KMP模式匹配算法
KMP模式匹配算法改进
模式匹配
有0个或多个字符组成的有限序列
串(字符串)
线性结构是一个有序数据元素的集合
线性结构
每个结点最多有俩棵子树左右子树是顺序的,次序不能颠倒即使树中只有一棵子树,也要区分左右
特点
空二叉树只有一个根结点根结点只有左子树根结点只有右子树根结点既有左子树,又有右子树
五种形态
在二叉树的第i层上之多有2i-1(i-1是上标)个结点
...
性质
所有结点都只有左子树的二叉树叫左斜树所有结点都只有右子树的二叉树叫右斜树
斜树
一个二叉树中,所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,称为满二叉树
满二叉树
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
完全二叉树
每个二叉树左右俩个指针域,如果为空,放着也浪费空间。所以第一次遍历二叉树时,如果左指针域为空就存前驱地址,右指针域为空就存后继地址。但是左侧需要一个tag来标识左指针域存的是左孩子结点还是前驱,右侧也同样需要。
线索二叉树
特殊二叉树
只用于完全二叉树(因为完全二叉树定义的严格,可以用顺序结构表示出二叉树的结构,很有优越性。详情参考P172)该结构不太通用,通用的见二叉链表
二叉树每个结点最多有俩个孩子,所以可以用一个数据域+俩个指针域这样的结构存储二叉树
二叉链表
从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次
概念
根结点=>左子树=>右子树(切记:是先把所有左子树遍历完了,再遍历右子树)
前序遍历
从根结点开始(并不是先访问根结点),遍历根结点的左子树=>根结点=>右子树
中序遍历
从根结点开始(并不是先访问根结点),遍历根结点的左子树=>右子树=>根结点
后序遍历
根结点一层层从上而下遍历
层序遍历(BFS常用)
遍历方法(限定了从左到右的习惯)
遍历
二叉树
带权路径长度WPL最小的二叉树称作哈夫曼树
原理:先构造哈夫曼树,然后对字符串再次编码,二进制的长度会明显缩小,所以达到了压缩的效果。解压缩也要用哈夫曼树,才能知道哪几个二进制对应哪个字符
哈夫曼编码实现压缩,解压缩
哈夫曼编码
哈夫曼树(也叫最优二叉树)
数据元素之间存在一对多的层次关系
树形结构(非线性结构)
特点:图中数据元素称为顶点,图中不允许没有顶点
图中数据元素称为顶点,图中不允许没有顶点
顶点
顶点Vi到Vj(i和j是下标)之间的边没有方向,则称这条边为无向边,用无序偶对(ViVj)来表示
无向边
顶点Vi到Vj之间的边有方向,则称这条边为有向边,也称为弧
有向边
概念:从顶点V导顶点V'有路径,称V和V'是连通的。如果对于图中任意俩个顶点都是连通的则称为连通图(能连通就行,不一定要相邻)
要是子图
子图要是连通的
连通子图还有极大顶点数
具有极大顶点数的连通子图包含依附于这些顶点的所有边
连通分量
一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边(p221)
生成树
连通图
图中任意俩个顶点之间的边都是无向边
无向图
概念:如果对于图中任意俩个顶点都是连通的则称为连通图(能连通就行,不一定要相邻)
参考连通分量定义
强连通分量
强连通图
概念:一个有向图恰有一个顶点的入口为0(根节点),其余顶点的入度均为1,则是一颗有向树
有向树
图中任意俩个顶点之间的边都是有向边
有向图
不存在顶点到其自身的边(自己到自己),且同一条边不重复出现
简单图
在无向图中,任意俩个顶点之间都存在边
无向完全图
在有向图中,任意俩个顶点之间都存在方向互为相反的俩条弧
有向完全图
有的图的边或弧具有与它相关的数字,这叫做权。权可以表示一个顶点到另一个顶点的距离或者耗费,这种带权的图称为网
网
术语
对于边数相对于顶点较少(顶点多,边数少)的图,这种结构存在存储空间的浪费
缺点
用俩个数组来表示图,一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息
邻接矩阵
图中顶点用一个一维数组存储
每个顶点的所有邻接点构成一个新线性表,
如果是有向图,还可以建立有向图的逆邻接表,即对每个顶点vi都建立一个链接为vi为弧头的表。(可以很容易得到顶点的入度或以顶点为弧头的弧)
想了解入度就必须遍历整个图才知道,反之,逆邻接链表解决了入度却不了解出度的情况。俩者不可兼得
优缺点
数组和链表相结合的存储方法称为邻接表
邻接表
把邻接表和逆邻接表结合起来
十字链表
主要优化无向图
邻接多重表
俩个一维数组构成,一个存储顶点的信息,一个存储边的信息。这个边数组每个数据元素由一条边的起点下标,终点下标和权重组成
边集数组
约定原则:在没有碰到重复顶点的情况下,始终向右手边走。走回到顶点之后,还要按原路一步步返回,在一步步验证是否都都走过了
深度优先(DFS)
图需要变形下,改造成类似树那样有明显的层级关系的样式
广度优先(BFS)
概念:我们把构造连通网的最小代价生成树称为最小生成树
以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树
普里姆(Prim)算法
以最小权值边开始构建
克鲁斯卡尔(Kruskal)算法
算法
最小生成树
一步步求出与顶点的最短路径,过程中都是基于已经求出的最大路径的基础上
迪杰斯特拉(Dijkstra)算法
佛洛伊德(Floyd)算法
拓扑排序算法
最短路径
数据元素是多对多的关系
图形结构(非线性结构)
逻辑结构(分为线性结构和非线性结构)
数据元素存放在地址连续的存储单元里,数据间的逻辑关系和物理关系是一致的(不方便插入,删除)
数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的(很灵活,给个指针就能找到。需要一个指针存放数据元素的地址)
为了方便查找,整体无序,但索引块之间有序,需要额外空间,存储索引表。优点:对顺序查找的一种改进,查找效率高缺点:需额外空间存储索引
索引存储结构
选取某个函数,数据元素根据函数计算存储位置可能存在多个数据元素存储在同一位置,引起地址冲优点:查找基于数据本身即可找到,查找效率高,存取效率高。缺点:存取随机,不便于顺序查找。
散列存储结构
物理结构(存储结构)
从表中第一个(或最后一个)记录开始,逐个进行记录的的关键字和给定值比较。
顺序查找(线性查找)
顺序表查找
切记:表必须是有序的。mid=(low+high)/2。复杂度是0(logn)
可以优化的地方:每次都从1/2处查找,对于有些场景还是不太适合的,比如查找am单词,很显然从字典的前面查找效率更高,所以优化点是从哪里开始折半
折半查找(二分查找)
公式:mid=low+(key-a[low])*(high-low)/a[high]-a[low] ;low和high是数组的下标
表长较大,而关键字分配又比较均匀的查找表,性能比折半查找要好得多。复杂度也是0(logn)
适合场景:
插值查找
构造另外一个斐波那契数列用于辅助
公式:mid=low+F[K-1]-1 ;F是斐波那契数列
比较:平均效率优于折半查找,最坏情况下,效率低于折半
斐波那契查找
有序表查找
索引项一定要按照关键码有序的排列
稠密索引
块内无序
块间有序
把数据集的记录分成了若干块,满足俩个条件
分块索引
概念:记录号表存储具有相同次关键字的所有记录的记录号(可以指向记录的指针或者该记录的主关键字)
搜索引擎最基础的搜索技术
倒排索引(P312)
若左子树不为空,则左子树上所有结点值均小于根结点的值
若右子树不为空,则右子树上所有结点的值均大于它的根结点的值
它的左右子树也分别为二叉排序树
特点:
是一个既使得插入和删除效率不错,又可以比较高效率的实现查找的算法
优点:
极端情况下,会退化成链表。时间复杂度为O(n)
缺点:
二叉搜索树(又称二叉查找树/排序数)
概念:是一种二叉排序树,其中每一个节点的左子树和右子树的高度差绝对值不超过1
维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树。
优缺点:
平衡二叉搜索树(AVL树) P(329)
概念:每一个结点的孩子树可以多余俩个,且每一个结点处可以存储多个元素
每一个结点都具有俩个孩子(称为2结点),或三个孩子(称为3结点)
2-3树
2-3树的扩展,最多四个孩子
2-3-4树
一种平衡的多路查找树
所有叶子结点都位于同一层次
B树
应文件系统那个所需而出的一种B树的变形树
出现在分支节点中的元素会在叶子结点中再次列出,每一个叶子结点都会保存一个指向后一叶子结点的指针
B+树
4种形式
多路查找树(B树)
概念:一种自平衡二叉查找树,和AVL树类似(并不是真正的平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。
适合:适合搜索,插入,删除较多的情况
每个结点要么是红色,要么是黑色
根结点永远是黑色
所有的叶节点都是空结点(即null),并且是黑色的
每个红色结点的俩个子结点都是黑色(从每个叶子到跟的路径上不会有俩个连续的红色结点)
从任一结点到其子树中每个叶子结点的路径都包含相同数量的黑色结点
性质:
这些性质强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。主要原因在于,性质4导致了路径不能有两个毗连的红色节点,最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点,根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长
关键性质:
红黑树
概念:散列技术是在记录的存储位置和它的关键字之间建立一个稳定的对于关系f,使得每个关键字key对于一个存储位置f(key),f称为散列函数,又称为哈希(Hash)函数
在存储时,通过散列函数计算记录的散列地址,并按此散列地址存储该记录
查找记录时,我们通过同样的散列函数计算记录的散列地址,按此散列地址访问该记录
有时候俩个关键字不同,但是算出来的地址相同,称为冲突
直接定址法
数字分析法
平方取中法
折叠法
除留余数法
随机数法
散列函数构造方法
一个冲突,就去寻找下一空的散列函数
开放定址法
准备多个散列函数,有冲突就换一个
再散列函数法
链地址法
冲突的都单独存储到溢出表中
公共溢出区法
散列冲突的解决方法
散列表查找(哈希表)
线性索引查找
所以说,散列技术既是一种存储方法,也是一种查找方法
查找运算
索引项有序也就意味着,查找关键字时,可以用到折半,插值,斐波那契等有序查找算法,所以快
内排序是在排序整个过程中,待排序的所有记录都放置在内存中。外排序是由于排序的记录太多,不能同时放置在内存,整个排序过程需要在内外存之间多次交换数据才能进行
内排序与外排序
复杂度O(n2) 2是上标
正宗的冒泡排序是相邻元素俩俩比较
冒泡排序
加个flag,如果后面后面已经是有序的了,就不需要再继续后面的循环判断了
冒泡排序优化
每个元素依次和后面所有的元素比较大小
简单选择排序
将一个记录插入到已经排好序的有序表中,从而得到一个新的记录数+1的有序表
直接插入排序
把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;虽则增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组
希尔排序
利用堆这种数据结构所设计的一种排序算法
堆排序
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序
归并排序
通过一次排序将待排序记录分割称独立的俩部分,其中一部分记录的关键字均比另一部分小,则可分别堆这俩部分记录继续进行排序,以达到整个序列有序的目的
快速排序 P471
排序种类
排序运算
数据运算
数据结构
1. 用常数1取代运行时间汇总的所有加法常数
2. 在修改后的运行次数函数中,只保留最高阶
3. 如果最高阶项存在且不是1,则去除与这个项相乘的常数,得到的结果就是大O阶
推导方法
常数阶 => O(1)
线性阶 => O(n)
对数阶 => O(log2n,缩写为logn)
平方阶 => O(n2)
常见的复杂度
时间复杂度(大O表示法)
大话数据结构
0 条评论
回复 删除
下一页