算法实验报告第二次华科

1、 课 程 实 验 报 告 课程名称： 计算机算法基础 专业班级：计算机科学与技术1209班学 号： 指导老师： 何 琨 报告日期： 2012-12-28 计算机科学与技术学院目录一实验一31实验题目32设计思路33程序源代码34运行演示6二实验二81实验题目82设计思路83程序源代码84运行演示12一实验一1实验题目单源最短路径问题： 已知一个n结点有向图G=(V,E)和边的权函数c(e)，求由G中某指定结点v0到其它各结点的最短路径。假定边的权值为正。2设计思路应用贪心算法求解。1) 度量标准生成的所有路径长度之和作为度量标准。为了使这一量度达到最小，其单独的每一条路径都必须具有最小长度。2

2、) 贪心算法 按照路径长度的非降次序生成这些路径。首先，生成一条到最近结点的最短路径，然后，生成一条到第二近结点的最短路径，等等。3程序源代码#include <stdio.h>#include <stdlib.h>#define N 1000void shortestPaths(int v,int *COST,int *DIST,int n);/最短路径生成函数int min(int x,int y);void outArray2(int *arr,int row,int col);/输出成本的邻接矩阵void outArray1(int *arr,int n);/输

3、出更新后其它结点到起始结点的路径长度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; printf("成本邻接矩阵：n"); outArray2(&COST00,7,7); /生成0号结点到1至6号结点的最短路径 shortestPaths

4、(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的最短路径中的w前一结点 int u,num,i,w; int tv,td=0; /初始化：结点v以外的结点未被选中，并更新路径长度为v到其它结点的初始成本 for(i=0;i<n;i+) Si=0; *

5、(DIST+i)=*(COST+v*n+i); prei=0; Sv=1; DISTv=0; /更新路径长度 for(num=1;num<n;num+) /选择距离结点 v 最近的结点 w for(w=1;w<n;w+) if(Sw=0) td=DISTw; tv=w; break; for(w+;w<n;w+) if(Sw=0&&td>DISTw) td=DISTw; tv=w; u=tv; Su=1; DISTu=td; /更新路径 for(w=1;w<n;w+) if(Sw=0) /DISTw=min(DISTw,DISTu+*(COST+u

6、*n+w); if(DISTw>(DISTu+*(COST+u*n+w) DISTw=(DISTu+*(COST+u*n+w); prew=u;/更新结点w最短路径并记录w结点的上一结点 /输出第num次更新后的路径长度 printf("n第%d次更新:",num); outArray1(DIST,n); printf("nn"); /输出路径 for(i=1;i<n;i+) printf("from 0 to %d,the shortest length is %3dthe way is：n",i,DISTi); w=i

7、; printf("%d<-",w); while(prew!=v) w=prew; printf("%d<-",w); printf("%dn",v); void outArray2(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(" Nt"); else printf("%3dt",*(a+i*row)+j); puts(&q

8、uot;n"); int min(int x,int y) return x<y?x:y;void outArray1(int *arr,int n) int i; for(i=0;i<n;i+) if(*(arr+i)=N) printf(" Nt"); else printf("%3dt",*(arr+i); 4运行演示我用了书上的一个例子，它的成本邻接矩阵已直接存入程序中，它的带权有向图如下：V0V1V2V3V5V6V4207025503040555025105070运行结果如下所示：图1-1 成本邻接矩阵图1-2更新最短路径

9、长度图1-3 最短路径二实验二1实验题目k路归并：每次同时归并k个文件且使移动次数最少。2设计思路每次选出k个最小的文件归并，将归并后的结果作为新的文件加入待归并的文件序列中，直到归并完成。3程序源代码#include <stdio.h>#include <stdlib.h>#include <time.h>#include <windows.h>#define MAX 100typedef int ElemType;typedef struct Table ElemType elem; struct Table * next;T;void ou

10、tTable(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",&num); while(num<=1); /获取k 值 do printf("请输入k值（大于1，小于等于%d)：",num); scanf("%d",&k)

11、; while(k<=1|k>num); /生成随机文件序列 srand(time(NULL); cur=(T *)malloc(sizeof(T); head->next=cur; head->elem+; cur->elem=(rand()%MAX+1); while(head->elem<num) cur->next=(T *)malloc(sizeof(T); cur=cur->next; cur->elem=(rand()%MAX+1); head->elem+; printf("随机文件序列：")

12、; outTable(head); /补充虚结点 r=(k-1)-(num-1)%(k-1)%(k-1); while(head->elem<num+r) cur=(T*)malloc(sizeof(T); cur->elem=0; cur->next=head->next; head->next=cur; head->elem+; if(r=0) printf("不用补充虚节点n"); else printf("补充%d个虚节点：",r); outTable(head); /归并 func(head,k); r

13、eturn 0;void func(T *head,int k) T*mink,*mpre,*cur,*cpre; int i=0,j=1,times=(head->elem-1)/(k-1),t=times; while(times->0) /当k 小于等于待归并文件数时，取k 个最小的文件归并 if(k<=head->elem) i=-1; /取k 个最小的文件 while(+i<k) mpre=cpre=head; mini=cur=head->next; j=0; while(j<head->elem) if(mini->elem&

14、gt;cur->elem) mpre=cpre; mini=cur; cpre=cur; cur=cur->next; j+; mpre->next=mini->next; head->elem-; /* else cur=head->next; i=-1; while(+i<head->elem) mini->elem=cur->elem; cur=cur->next; */ /输出归并的k 个文件的大小 printf("第%d次归并：n",t-times); i=0; while(i<k) prin

15、tf("%4d",mini->elem); i+; i=1; /归并k个文件 while(i<k) min0->elem+=mini->elem; free(mini); i+; /将归并k个文件得到的新文件加入结点中 min0->next=head->next; head->next=min0; head->elem+; /输出归并后的文件 printf(" | "); cur=head->next; i=head->elem; while(i->0) printf("%4d",cur->elem);