算法与数据结构基本知识ppt课件

.,1,NOIPCourse3,ByPengKejingSCAU-GIS,.,2,SECTIONA.算法与数据结构基本知识,.,3,什么是数据结构,一种存在于计算机内存或文件中的数组组织方法。根据一定的功能抽象出来的。仅存在于人的思维之中，是一种抽象的结构。人们研究这些抽象的结构如何在计算机之上进行实现。,.,4,线性表,能够实现如下功能的结构：维护一个列表。可以插入节点，删除节点，查找节点实现方法：数组链表复杂度分析,.,5,一种特殊的链表实现方法,用巨型数组模拟内存省去申请内存的步骤省去使用指针的步骤,.,6,特殊的线性表,栈Stack特点：先进后出队列Queue特点：先进先出,.,7,树,定义：特殊的形态：二叉树。二叉树的三种普通遍历和一种特殊遍历前序中序后序层次一些扩展问题：使用前序/后序和中序遍历恢复树的结构,.,8,树,表达式与树三种遍历的实现方法，一般二叉树的存储结构前序遍历的非递归实现树作为一种存储结构二叉排序树平衡二叉树旋转理想的平衡情况下，树作为存储结构，每次查找、插入、删除的复杂度为O(logn),.,9,图,图上的一些问题遍历最短路最小生成树最大流匹配关节点,.,10,最小生成树,.,11,最大流问题,.,12,二分图匹配,.,13,图的存储方法,邻接矩阵注意有向图和无向图的存储缺点：存储空间耗费为O(n2)，存储的点的数目一般不超过3000个遍历图时耗时邻接表使用数组模拟链表可以应对10万个以上的点,.,14,最小生成树的算法,Prim算法一开始有一个顶点v0每次找连接“未添加到最小生成树的顶点”与“已添加到临时最小生成树的顶点”的最短边Kruskal算法*对边进行排序（从小到大）按顺序选取边，每添加一条边，就会连接一个新的节点需要一个结构来判断某些点是否已经连在一起,.,15,Prim算法,原图，准备在此图上求最小生成树,.,16,Prim算法,顶点D被任意选为起始点。顶点A、B、E和F通过单条边与D相连。A是距离D最近的顶点，因此将A及对应边AD以高亮表示。,.,17,Prim算法,下一个顶点为距离D或A最近的顶点。B距D为9，距A为7，E为15，F为6。因此，F距D或A最近，因此将顶点F与相应边DF以高亮表示。,.,18,Prim算法,算法继续重复上面的步骤。距离A为7的顶点B被高亮表示。,.,19,Prim算法,在当前情况下，可以在C、E与G间进行选择。C距B为8，E距B为7，G距F为11。E最近，因此将顶点E与相应边BE高亮表示。,.,20,Prim算法,这里，可供选择的顶点只有C和G。C距E为5，G据E为9，故选取C，并与边EC一同高亮表示。,.,21,Prim算法,顶点G是唯一剩下的顶点，它距F为11，距E为9，E最近，故高亮表示G及相应边EG。,.,22,Prim算法,现在，所有顶点均已被选取，图中绿色部分即为连通图的最小生成树。在此例中，最小生成树的权值之和为39。,.,23,Kruskal算法,.,24,Kruskal算法,.,25,Kruskal算法,.,26,Kruskal算法,.,27,Kruskal算法,.,28,Kruskal算法,Thenext-shortestarcsareABandBE,bothwithlength7.ABischosenarbitrarily,andishighlighted.ThearcBDhasbeenhighlightedinred,becausetherealreadyexistsapath(ingreen)betweenBandD,soitwouldformacycle(ABD)ifitwerechosen.,.,29,Kruskal算法,.,30,Kruskal算法,.,31,最短路算法Dijkstrasalgorithm,NOIP原题有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为_。,.,32,最短路算法Dijkstrasalgorithm,.,33,Dijkstra,.,34,Dijkstra,.,35,Dijkstra,.,36,Dijkstra,.,37,Dijkstra,.,38,Dijkstra,.,39,图的遍历,遍历的意思就是按照一定的顺序，访问整个图的所有顶点深度遍历DFS广度遍历BFS,.,40,SECTIONC.一些Pascal语言的知识,.,41,控制语句,Break语句Continue语句Exit函数或过程,.,42,指针，NOIP原题,看程序，写代码：vara,b:integer;x,y:integer;procedurefun(a,b:integer);vark:integer;begink:=a;a:=b;b:=k;end;begina:=3;b:=6;x:=a;y:=b;fun(x,y);writeln(a,b);end.,.,43,指针,typepint=integer;vara,b:integer;x,y:pint;procedurefun(a,b:pint);vark:integer;begink:=a;a:=b;b:=k;end;begina:=3;b:=6;x:=a;y:=b;fun(x,y);writeln(a,b)