华科算法实验报告

1、 . .页脚. 课课 程程 实实 验验 报报 告告 课程名称：课程名称： 算法设计与分析算法设计与分析 专业班级：专业班级：计算机科学与技术计算机科学与技术 13xx13xx 班班学学 号：号： 姓姓 名：名： 指导老师：指导老师： 报告日期：报告日期： 2015-11-292015-11-29 计算机科学与技术学院计算机科学与技术学院 . .页脚. 目录目录一实验一一实验一 .3 31 1实验题目实验题目.3 32 2设计思路设计思路.3 33 3程序源代码程序源代码.4 44 4运行演示运行演示.7 7二实验二二实验二 .8 81 1实验题目实验题目.8 82 2设计思路设计思路.8 83

2、 3程序源代码程序源代码.9 94 4运行演示运行演示.1212 . .页脚. 一实验一实验一一1 1实验题目实验题目单源最短路径问题： 已知一个 n 结点有向图 G=(V,E)和边的权函数 c(e)，求由 G 中某指定结点 v0 到其它各结点的最短路径。假定边的权值为正。2 2设计思路设计思路 贪心算法流程图如图 1：图 1 生成最短路径算法流程设计总方法：使用贪心算法求解。贪心方法：1) 度量标准生成的所有路径长度之和作为度量标准。为了使这一量度达到最小，其单 . .页脚. 独的每一条路径都必须具有最小长度。2) 算法按照路径长度的非降次序生成这些路径。首先，生成一条到最近结点的最短路径，

3、然后，生成一条到第二近结点的最短路径，等等。即只用求出从路径 v0开始到 G 中其他所有结点的最短路径长度。假定 G 中n 个结点被标记上 1 到 n,集合 S 作为一个数组存放，如果结点 i 不在 S 中，则Si=0，如果在 S 中，则 Si=1，若 COST（i,j）是（i,j）的权，则在边（i，j）不在成本邻接矩阵时，就被置某个大数，这里用 N 表示，当 i=j 时，COST（i,j）被置以 0。3 3程序源代码程序源代码#include #include #define N 1000void shortestPaths(int v,int *COST,int *DIST,int n);

4、/最短路径生成函数void output2(int *arr,int row,int col);/输出成本的邻接矩阵void outArray1(int *arr,int n);/输出更新后其它结点到起始结点的路径长度int main() int COST77= 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 DIST7; int v=0;

5、/* printf(成本邻接矩阵：n); output2(&COST00,7,7); */ /生成 0 号结点到 1 至 6 号结点的最短路径 shortestPaths(v,&COST00,DIST,7); return 0;void shortestPaths(int v,int *COST,int *DIST,int n)/G 是一个 n 结点有向图，它由其成本邻接矩阵 COSTnn表示，DISTj被置以结点 v到 /结点 j 的最短路径长度，这里 1=j=n;DISTv被置成 0 int Sn; . .页脚. int pren;/pw记录起始结点到结点 w 的最短路径中

6、的 w 前一结点 int u,num,i,w; int tv,td=0; /初始化：结点 v 以外的结点未被选中，并更新路径长度为 v 到其它结点的初始成本 for(i=0;in;i+) Si=0; *(DIST+i)=*(COST+v*n+i); prei=0; Sv=1; DISTv=0; /更新路径长度 for(num=1;numn;num+) /选择距离结点 v 最近的结点 w for(w=1;wn;w+) if(Sw=0) td=DISTw; tv=w; break; for(w+;wDISTw) td=DISTw; tv=w; u=tv; Su=1; DISTu=td; /更新路径

7、 for(w=1;w(DISTu+*(COST+u*n+w) . .页脚. DISTw=(DISTu+*(COST+u*n+w); prew=u;/更新结点 w 最短路径并记录 w 结点的上一结点 /输出第 num 次更新后的路径长度 printf(n 第%d 次路径:,num); output1(DIST,n); printf(nn); /输出路径 for(i=1;in;i+) printf(从 0 到%d,最短的路径是：n,i); w=i; printf(%d-,w); while(prew!=v) w=prew; printf(%d-,w); printf(%dn,v); void ou

8、tput2(int *a,int row,int col) int i,j; for(i=0;irow;i+) for(j=0;jcol;j+) if(*(a+i*row)+j)=N) printf( Nt); else printf(%3dt,*(a+i*row)+j); puts(n); void output1(int *arr,int n) int i; for(i=0;in;i+) . .页脚. if(*(arr+i)=N) printf( Nt); else printf(%3dt,*(arr+i); 4 4运行演示运行演示我用了书上的一个例子，它的成本邻接矩阵已直接存入程序中，它

9、的带权有向图如下： 图 2 带权有向图运行结果如下所示：V0V1V2V3V5V6V4207025503040555025105070 . .页脚. 图 3 运行结果图二实验二二实验二1 1实验题目实验题目k 路归并：每次同时归并 k 个文件且使移动次数最少。2 2设计思路设计思路1、流程图总流程图如图 1 所示。 . .页脚. 图 1 归并文件流程图2、设计方法贪心算法3、度量标准每次选出 k 个最小的文件归并，将归并后的结果作为新的文件加入待归并的文件序列中，直到归并完成。值得注意的是，由于所有的内部点的度数必须为 k，因此，对于 n 取某些值，就不和 k 元归并树相对应。所以有必要引进一定

10、量的虚结点，每个虚结点赋值 0，这个虚结点的虚值，不会影响所产生度数为 k 的带权外部路径长度。3 3程序源代码程序源代码#include#include . .页脚. #include#include#define MAX 100typedef 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(siz

11、eof(T); head-elem=0; /获取文件数 do printf(请输入文件的个数(1):); scanf(%d,&num); while(num1,=%d):,num); scanf(%d,&k); 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=(r

12、and()%MAX+1); head-elem+; printf(随机生成的文件序列为：); . .页脚. 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 *

13、mink,*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(mini-elemcur-elem) mpre=cpre; mini=cur; . .页脚. cpre=cur; cur=cur-next; j+; mpre-next=mini-next; head-elem-; /输出归并的 K 个文件的大小

14、 printf(第%d 次归并:,t-times); i=0; while(ielem); i+; i=1; /归并 K 个文件 while(ielem+=mini-elem; free(minj); i+; /将归并 K 个文件得到的新文件加入节点中 min0-next=head-next; head-next=min0; 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 *h