d07-数据结构讲解.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 第 * 页 思考题6 求稀疏矩阵的和。若稀疏矩阵采用带行指针向量的链式存储形式。若结点定义为： struct triplenode // 定义三元组结点 { int col; // 列值 elemtype val; // 非0元素值 struct node * next; // 指针域 } 带行指针向量的链式存储结构定义为： #define MAXROW 整型常量（行最大长度） struct L_SMatrix { int m, n, t // 矩阵行数，列数，非0元素数 struct triplenode * Heads[MAXROW+1] // 0不用 } 第 * 页 思考题6 求稀疏矩阵的和。 例如：有 6×5 的稀疏矩阵如下。 col val 1 2 ^ 3 4 5 ^ 6 1 2 2 0 0 3 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 8 0 0 0 0 0 0 1 0 4 0 0 4 3 ^ 1 -1 ^ 4 8 ^ 1 1 3 4 ^ 第 * 页 7.6 最短路径 求从源点到其余各点的最短路径的算法的基本思想 依最短路径的长度递增的次序求得各条路径。 源点 v1 … 其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。 v2 第 * 页 7.6 最短路径 迪杰斯特拉(Dijkstra)算法 设置辅助数组Dist，其中每个分量Dist[k] 表示 当前所求得的从源点到其余各顶点 k 的最短路径。 一般情况下， Dist[k] = 源点到顶点 k 的弧上的权值 或者 = 源点到其它顶点的路径长度+ 其它顶点到顶点 k 的弧上的权值 1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。 2）修改其它各顶点的Dist[k]值。假设求得最短路径的顶点为u，若 Dist[u]+G.arcs[u][k]Dist[k]，则将 Dist[k] 改为Dist[u]+G.arcs[u][k]。 V0和k之间存在弧 V0和k之间不存在弧 其中的最小值即为最短路径的长度。 * * 左侧流程保证对于非连通的图也可以遍历所有的结点。Vi=1是定义遍历的起始点。 右侧是递归的深度遍历算法。 * * * 左侧流程保证对于非连通的图页可以遍历所有的结点。 右侧是递归的深度遍历算法。 * 左侧流程保证对于非连通的图页可以遍历所有的结点。 右侧是递归的深度遍历算法。 * * * * * * * * * * * * * * * * * * * * * * 第 * 页 7.5 有向无环图——拓扑排序 拓扑排序 0 1 1 1 in link 5 5 4 3 ^ ^ ^ vex next 1 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 输出序列：6 3 2 1 0 4 5 0 0 top 1 0 0 3 P=NULL 2 4 第 * 页 7.5 有向无环图——拓扑排序 拓扑排序 0 1 1 1 in link 5 5 4 3 ^ ^ ^ vex next 1 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 输出序列：6 3 2 1 0 4 0 0 top 1 0 0 3 P=NULL 2 4 5 第 * 页 7.5 有向无环图——关键路径 问题提出： 1）工程能否顺序进行，即工程流程是否“合理”2）完成整项工程至少需要多少时间，哪些任务是影响工程进度的关键任务？ V3 V1 V4 V6 V5 V2 a4=3 a1=3 a2=2 a6=3 a5=4 a3=2 a7=2 a8=1 顶点表示事件 边表示活动 事件Vj发生 表示 ak已结束 ak Vj Vi 事件Vi发生表示 ak可以开始 AOE网 第 * 页 7.5 有向无环图——关键路径 AOE网 AOE：用边表示活动的网。它是有一个带权的有向无环图。 顶点：表示事件，弧——表示活动， 权值：活动持续的时间。 路径长度：路径上各活动持续时间之和。 关键路径：路径长度最长的路径叫关键路径。 第 * 页 7.5 有向无环图——关键路径 AOV网和AOE网的区别 都能用来表示工程中的各子工程的流程： 一个用顶点表示活动，