当前位置:   article > 正文

数据结构与算法知识梳理_数据结构与算法知识点总结

数据结构与算法知识点总结

⼀、基础知识

1、数据结构

逻辑结构:数据对象中数据元素之间的相互关系。

物理结构:数据的逻辑结构在计算机中的存储形式。

四⼤逻辑结构:集成结构、线性结构、树形结构、图形结构。

顺序存储结构:数据元素存放在地址连续的存储单元,数据间的逻辑关系和物理关系是⼀致的。

链式存储结构:数据元素存放在任意的存储单元,

2、算法效率

1. 算法采⽤的策略、⽅案;

2. 编译产⽣的代码质量;

3. 问题的输⼊模块;

4. 机器执⾏命令的速度;

⼆、线性表

1、链表

单链表,只有⼀个存放指针的模块,存放地址可以不连续,访问是⽅便访问当前节点的后继节点;

双链表,⼀个数据元素单元有两个存放指针的模块,⼀个指针指向前继节点,⼀个指针指向后继节点。

链表中因为头结点也会有所不同,可以循环链表或者其他,主要注意链表中指针的操作,属于细节问题且必须掌握,不赘述。

2、栈、队列

栈:先进后出。

队列:先进先出。

三、树

1、基础知识

树:是n个节点的有限集。

⼆叉树:除叶⼦结点外,每个节点的⼦节点数最多为2,空树也是⼆叉树。

满⼆叉树:⾮叶⼦节点的⼦结点数都为2,。

完全⼆叉树:叶⼦结点只能出现最下两层,可以⾮叶⼦结点可以只有左结点,但不可以有只有右结点。

⼆叉树性质:

1. 在⼆叉树的第i层⾄多有2^i-1个结点。

2. 深度为k的⼆叉树⾄多有2^k-1个结点。

3. 对于任何⼀个⼆叉树,叶⼦结点数为n0,度为2的结点数为n2,则n0=n2+1

4. 具有n个结点的完全⼆叉树的深度为log2n+1(向下取整)。

2、树的遍历

前序遍历:先访问根节点,再访问左结点,最后访问右结点。

中序遍历:先访问左结点,再访问根节点,最后访问右结点。

后序遍历:先访问左节点,再访问右结点,最后访问根节点。

层序遍历:⼀层⼀层的访问树的结点。

备注:构建树代码编写时常常使⽤递归(其他有关树操作也是)。

3、线索⼆叉树

线索⼆叉树中存放⼀个结点时分为五块,从左⾄右分别为:lchild,ltag,data,rtag,rchild。(构造时以中序遍历基础)

1. ltag为0时,lchild指向该结点的左孩⼦;为1时,lchild指向该结点的前驱;

2. rtag为0时,rchild指向该结点的右孩⼦;为1时,rchild指向该结点的后继;

4、⼆叉树、树、森林

树转⼆叉树:①在树中所有的兄弟之间加⼀条连线;②对每⼀个结点,除了保留与其左孩⼦(长⼦)的连线外,去掉该结点与其他孩⼦的连线。

森林转⼆叉树:①先将森林的每棵树变为⼆叉树;②再将各个⼆叉树的根节点视为兄弟似的从左⾄右的连在⼀起(第⼀个树转为⼆叉树的右⼦树)。

⼆叉树转树:①若结点x是其双亲y的结点,则把x的右孩⼦,右孩⼦的右孩⼦,,,,都与y连在⼀起;②去掉所有双亲到右孩⼦的连线。备注:树的前序遍历对应树的⼆叉树的前序的遍历,后序遍历对应⼆叉树的中序遍历。

四、图

1、基础知识

图(Graph)是由顶点的有穷⾮空集合和顶点之间的边的集合组成,通常为G(V,E)其中G表⽰⼀个图,V是图G中顶点的集合,E是图中边的集合。

顶点:为图中数据元素。

⽆向边:顶点之间的边没有⽅向。

有向边:顶点之间的边有⽅向(出度:为指向其他顶点的边数,⼊度:为指向本顶点的边数)。

⽆向完全图:在⽆向图中,如果任意两个顶点之间都存在边,则称改图为⽆向图,含有n个顶点的⽆向图有n*(n-1)/2条边。

有向完全图:如果任意两个顶点之间都存在⽅向互为相反的两条弧,则称该图为有向图。

G1(V1,E1),G2(V2,E2),若V2包含于V1,E2包含于E1,则G2为G1的⼦图。

备注:每条带有权重的图就叫⽹

2、图的存储

领接矩阵:适合稠密图

⽤两个数组表⽰图,顶点放在⼀位数组,边放在⼆维数组。⽆向图为对称矩阵,有向图则不是。

邻接表:适合稀疏图

顶点⽤⼀维数组存储,图中每个顶点Vi的所有领接点构成⼀个线性表。

备注:其他存储⽅式有⼗字链表(适合有向图),领接多重表(⽅便删除)。

3、图的遍历

深度优先遍历:在没有碰到重复顶点的情况下,分叉路⼝始终是向右⼿边⾛,每路过⼀个顶点就做⼀个记号。

⼴度优先遍历:以某个顶点开始先访问其所有连接顶点。

4、拓展知识

最⼩⽣成树(图中没有环路)

普⾥姆(Prim)算法:每次顶点连接权值最⼩边,若⼀个顶点与多个顶点连接,考虑选择权值最⼩的边。适合稠密图。

克鲁斯卡尔算法:将图中边按照权值从⼩到⼤排列,然后从最⼩的边开始,如果该边并⼊不构成回路的话,则将该边并⼊当前⽣成树,直到所有的边都检测完为⽌。适合稀疏图。

最短路径

⽹图:边上权值之和最少的路径。

⾮⽹图:两点之间经过边数最少的路径。

迪杰斯特拉算法:⼀步步求出⼀个顶点到所以顶点之间的最短路径。O(n^2)

佛洛依德算法:求出所有顶点到所有顶点的最短路径。O(n^3)

拓扑排序

⽆环图DAG(⽆环有向图)

AOW ⽹不存在回路

拓扑序列:设G(V,E)是⼀个具有n个结点的有向图,V中所有顶点序列满⾜若从顶点Vi-Vj有⼀条路径,则在顶点序列中Vi必在Vj之前。称这样的顶点序列为⼀个拓扑序列。

拓扑排序:对⼀个有向图构造拓扑序列的过程。

关键路径

AOE带权有向图,顶点为事件,边权值表⽰活动持续时间。

关键路径:事件完成时间最长的路径。

五、查找

1、普通查找⽅法

顺序查找、插值查找、斐波那契查找(黄⾦⽐例查找)、线性索引查找(稠密查找、分块查找、倒排查找)。

重点

⼆叉排序树:左⼦树上的值均⼩于它的根结点值,右⼦树上的值均⼤于根结点的值。

平衡⼆叉树:具有⼆叉排序树性质的同时,任意⼦树的左右⼦树的层数差值最多为1。

2、其他查找⽅法

B树:多路查找树的每个结点都具有两个孩⼦或多个孩⼦,所有叶⼦结点都在同⼀层次。

注意:插⼊需拆解应从⼩往上拆,先插⼊上⼀层,再在下⼀层分裂。

平衡多路查找树

1、把结点最⼤的孩⼦数⽬称为B树的阶;

2、根结点不是叶节点时,⾄少有两个⼦树;

3、⾮根结点的分⽀结点都有K-1个元素,K-1个孩⼦,K⼤于等于m+1向下取整,⼩于等于m;

散列表(Hash表)

在记录的存储位置和它的关键字之间建⽴⼀个确定的对应关系F,使得每个关键字key对应⼀个存储位置F(key),存储在⼀块连续的存储空间。

F:Hash函数,经典构造⽅法:除留余数法。

解决冲突

开放定址法:F(key)=F(key)+di,修改di值;

再hash法:再⼀次使⽤hash函数;

链地址法:数组存放地址,链表存放在此地址的关键字。

公共溢出法:开辟新的表格存放溢出的关键字。

六、排序

排序:线性表的⼀种操作。

冒泡排序:两两相邻的关键字⽐较,反序则交换位置。时间:O(n^2) ,空间O(1),稳定

快速排序:选取基准点,⼀边放⼩于基准点的数,另⼀边放⼤于基准点的数;再对左右区间重复该步骤,直到各区间只有⼀个数最初基准点左右两边的数进⾏交换。时间空间O(nlogn)-O(n^2), 不稳定

选择排序:通过n-i次⽐较,从n-i+1个记录中选出关键字最⼩的记录,并和第i个记录交换,直⾄序列有序。O(n^2) O(1) 稳定

堆排序:①待排序列构造⼤⼩根堆;②将根节点与末尾元素交换;③将剩余n-1个序列重新构造⼀个堆;④反复执⾏直⾄序列有序。

O(nlogn) O(1) 不稳定

插⼊排序:讲⼀个记录插⼊到已经拍好的序的有序表中。O(n^2) O(1) 稳定

希尔排序:分成两组进⾏插⼊排序。O(n^2) O(1) 不稳定

归并排序,先左边排序,后右边排序,合并。O(nlogn) O(n) 稳定

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/620184
推荐阅读
相关标签
  

闽ICP备14008679号