09年自考《数据结构》各章要点二[5]

构造最小生成树的算法

·Prim算法的时间复杂度为O(n^)与边数无关适于稠密图

·Kruskal算法的时间复杂度为O(lge)主要取决于边数较适合于稀疏图

最短路径的算法

·Dijkstra算法时间复杂度为O(n^)

·类似于prim算法

拓扑排序是将有向无环图G中所有顶点排成一个线性序列若∈E(G)则在线性序列u在v之前这种线性序列称为拓扑序列

拓扑排序也有两种方法

·无前趋的顶点优先每次输出一个无前趋的结点并删去此结点及其出边最后得到的序列即拓扑序列

·无后继的结点优先每次输出一个无后继的结点并删去此结点及其入边最后得到的序列是逆拓扑序列

第八章 排序

记录中可用某一项来标识一个记录则称为关键字项该数据项的值称为关键字

排序是使文件中的记录按关键字递增(或递减)次序排列起来

·基本操作比较关键字大小改变指向记录的指针或移动记录

·存储结构顺序结构链表结构索引结构

[] [] [] [] [] [] [] [] [] [] [] []