华科算法实验报告.doc

1 课课 程程 实实 验验 报报 告告 课程名称 课程名称 算法设计与分析算法设计与分析 专业班级 专业班级 计算机科学与技术计算机科学与技术 13xx13xx 班班 学学 号 号 姓姓 名 名 指导老师 指导老师 报告日期 报告日期 2015 11 292015 11 29 计算机科学与技术学院计算机科学与技术学院 2 目录目录 一 实验一一 实验一 3 1 1 实验题目 实验题目 3 2 2 设计思路 设计思路 3 3 3 程序源代码 程序源代码 4 4 4 运行演示 运行演示 7 二 实验二二 实验二 8 1 1 实验题目 实验题目 8 2 2 设计思路 设计思路 8 3 3 程序源代码 程序源代码 9 4 4 运行演示 运行演示 12 3 一 实验一 实验一一 1 1 实验题目 实验题目 单源最短路径问题 已知一个 n 结点有向图 G V E 和边的权函数 c e 求由 G 中某指定结 点 v0 到其它各结点的最短路径 假定边的权值为正 2 2 设计思路 设计思路 贪心算法流程图如图 1 图 1 生成最短路径算法流程 设计总方法 使用贪心算法求解 贪心方法 1 度量标准 生成的所有路径长度之和作为度量标准 为了使这一量度达到最小 其单 4 独的每一条路径都必须具有最小长度 2 算法 按照路径长度的非降次序生成这些路径 首先 生成一条到最近结点的最 短路径 然后 生成一条到第二近结点的最短路径 等等 即只用求出从路径 v0开始到 G 中其他所有结点的最短路径长度 假定 G 中 n 个结点被标记上 1 到 n 集合 S 作为一个数组存放 如果结点 i 不在 S 中 则 S i 0 如果在 S 中 则 S i 1 若 COST i j 是 i j 的权 则在边 i j 不在成本邻接矩阵时 就被置某个大数 这里用 N 表示 当 i j 时 COST i j 被置以 0 3 3 程序源代码 程序源代码 include include define N 1000 void shortestPaths int v int COST int DIST int n 最短路径生成函数 void output2 int arr int row int col 输出成本的邻接矩阵 void outArray1 int arr int n 输出更新后其它结点到起始结点的路径长度 int main int COST 7 7 0 20 50 30 N N N N 0 25 N N 70 N N N 0 40 25 50 N N N N 0 55 N N N N N N 0 10 70 N N N N N 0 50 N N N N N N 0 int DIST 7 int v 0 printf 成本邻接矩阵 n output2 生成 0 号结点到 1 至 6 号结点的最短路径 shortestPaths v return 0 void shortestPaths int v int COST int DIST int n G 是一个 n 结点有向图 它由其成本邻接矩阵 COST n n 表示 DIST j 被置以结点 v 到 结点 j 的最短路径长度 这里 1 j n DIST v 被置成 0 int S n int pre n p w 记录起始结点到结点 w 的最短路径中的 w 前一结点 5 int u num i w int tv td 0 初始化 结点 v 以外的结点未被选中 并更新路径长度为 v 到其它结点的初始成本 for i 0 i n i S i 0 DIST i COST v n i pre i 0 S v 1 DIST v 0 更新路径长度 for num 1 num n num 选择距离结点 v 最近的结点 w for w 1 w n w if S w 0 td DIST w tv w break for w wDIST w td DIST w tv w u tv S u 1 DIST u td 更新路径 for w 1 w DIST u COST u n w 6 DIST w DIST u COST u n w pre w u 更新结点 w 最短路径并记录 w 结点的上一结点 输出第 num 次更新后的路径长度 printf n 第 d 次路径 num output1 DIST n printf n n 输出路径 for i 1 i n i printf 从 0 到 d 最短的路径是 n i w i printf d w while pre w v w pre w printf d w printf d n v void output2 int a int row int col int i j for i 0 i row i for j 0 j col j if a i row j N printf N t else printf 3d t a i row j puts n void output1 int arr int n int i for i 0 i n i 7 if arr i N printf N t else printf 3d t arr i 4 4 运行演示 运行演示 我用了书上的一个例子 它的成本邻接矩阵已直接存入程序中 它的带权有向图如下 V0 V1 V2 V3 V5 V6 V4 20 70 25 50 30 40 55 50 2510 50 70 图 2 带权有向图 运行结果如下所示 8 图 3 运行结果图 二 实验二二 实验二 1 1 实验题目 实验题目 k 路归并 每次同时归并 k 个文件且使移动次数最少 2 2 设计思路 设计思路 1 流程图 总流程图如图 1 所示 9 图 1 归并文件流程图 2 设计方法 贪心算法 3 度量标准 每次选出 k 个最小的文件归并 将归并后的结果作为新的文件加入待归并的文件序列中 直到归并完成 值得注意的是 由于所有的内部点的度数必须为 k 因此 对于 n 取某些值 就不和 k 元 归并树相对应 所以有必要引进一定量的虚结点 每个虚结点赋值 0 这个虚结点的虚值 不会影响所产生度数为 k 的带权外部路径长度 3 3 程序源代码 程序源代码 include include 10 include include define MAX 100 typedef int ElemType typedef struct Table ElemType elem struct Table next T void outTable T head void func T head int k int main int num k r T head cur head T malloc sizeof T head elem 0 获取文件数 do printf 请输入文件的个数 1 scanf d while num1 d num scanf d while knum 生成随机序列 srand time NULL cur T malloc sizeof T head next cur head elem cur elem rand MAX 1 while head elemnext T malloc sizeof T cur cur next cur elem rand MAX 1 head elem printf 随机生成的文件序列为 11 outTable head 补充虚结点 r k 1 num 1 k 1 k 1 while head elemelem 0 cur next head next head next cur head elem if r 0 printf 不用补充虚结点 n else printf 补充 d 个虚结点 r outTable head 归并 func head k return 0 void func T head int k T min k mpre cur cpre int i 0 j 1 times head elem 1 k 1 t times while times 0 当 K 小于等于待归并文件数时 取 K 个最小的文件归并 if kelem i 1 取 k 个最小的文件 while inext j 0 while jelem if min i elem cur elem mpre cpre min i cur 12 cpre cur cur cur next j mpre next min i next head elem 输出归并的 K 个文件的大小 printf 第 d 次归并 t times i 0 while ielem i i 1 归并 K 个文件 while ielem min i elem free min j i 将归并 K 个文件得到的新文件加入节点中 min 0 next head next head next min 0 head elem 输出归并后的文件 printf t 归并后的文件为 cur head next i head elem while i 0 printf 4d cur elem cur cur next printf n void outTable T he