数据结构（C语言版）.ppt

*北京林业大学信息学院时间复杂度：O(n2)/*―开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集―*/for(i=1;in;++i){ //对其余n?1个顶点，依次进行计算min=MaxInt;for(w=0;wn;++w)if(!S[w]D[w]min){v=w;min=D[w];} //选择一条当前的最短路径，终点为vS[v]=true; //将v加入Sfor(w=0;wn;++w) //更新从v0出发到集合V?S上所有顶点的最短路径长度if(!S[w](D[v]+G.arcs[v][w]D[w])){D[w]=D[v]+G.arcs[v][w]; //更新D[w]Path[w]=v; //更改w的前驱为v}//if}//for}//ShortestPath_DIJ【算法描述】*北京林业大学信息学院图存储结构遍历邻接矩阵邻接表深度优先搜索DFS广度优先搜索BFS无向图的应用应用最小生成树Prim算法Kruskal算法有向图的应用活动网络AOV：拓扑排序算法AOE：关键路径最短路径Dijkstra算法Floyd算法小结*北京林业大学信息学院1.掌握：图的基本概念及相关术语和性质2.熟练掌握：图的邻接矩阵和邻接表两种存储表示方法3.熟练掌握：图的两种遍历方法DFS和BFS4.熟练掌握：最短路算法（Dijkstra算法）5.掌握：最小生成树的两种算法的思想及拓扑排序算法的思想小结*北京林业大学信息学院李冬梅数据结构*北京林业大学信息学院*北京林业大学信息学院第7章查找7.1查找的基本概念7.2线性表的查找7.3树表的查找7.4哈希表的查找教学内容*北京林业大学信息学院1.熟练掌握顺序表和有序表（折半查找）的查找算法及其性能分析方法；2.熟练掌握二叉排序树的构造和查找算法及其性能分析方法；3.掌握二叉排序树的插入算法，了解二叉排序树的删除算法；4.熟练掌握哈希函数（除留余数法）的构造5.熟练掌握哈希函数解决冲突的方法及其特点教学目标*北京林业大学信息学院7.1查找的基本概念查找表: 由同一类型的数据元素（或记录）构成的集合静态查找表： 对查找表没有修改操作动态查找表： 对查找表具有修改操作关键字 记录中某个数据项的值，可用来识别一个记录主关键字： 唯一标识数据元素次关键字： 可以标识若干个数据元素是一种数据结构*北京林业大学信息学院关键字的平均比较次数，也称平均搜索长度ASL(AverageSearchLength)n：记录的个数pi：查找第i个记录的概率(通常认为pi=1/n)ci：找到第i个记录所需的比较次数查找算法的评价指标*北京林业大学信息学院7.2线性表的查找一、顺序查找（线性查找）二、折半查找（二分或对分查找）*北京林业大学信息学院顺序查找应用范围：顺序表或线性链表表示的静态查找表表内元素之间无序typedefstruct{ElemType*R;//表基址intlength;//表长}SSTable;顺序表的表示*北京林业大学信息学院intLocateELem(SqListL,ElemTypee