算法设计 实验 报告 K路归并 2路归并 单源点最短路径.doc

《算法设计》实验报告 姓 名： xxx 学 号： 班 级： 0 9 1 1 专 业：计算机科学与技术 报告日期：2011/11/10 实验一（k路归并） 问题描述及分析：给定k值和n个文件内的记录（即长度）q1,q2,q3,..qn，每次归并k个文件，找出最优归并模式。由于归并一个具有x个记录的文件和一个具有y个文件时间复杂度为O（x+y）,因此对于度量标准的一种明显选择是：每一步归并权值最小的k个文件。 算法思想：由最优二路归并树的思想，可以导出K路归并的贪心算法，即在每一步归并时，都选择k棵具有最小长度的子树（权值分别为q1,q2,q3,..qk）用于归并,用权值为q1+q2+q3+..+qk的新结点取代前K个结点，再与其它结点一起按此方法继续归并。在此情况下，相应的归并树是一棵K元树。由于所有的内部结点的度必须为K，因此对于n的某些值，就不与K元归并树相对应。所以，有必要引入一定量的虚外部结点，且为不影响所产生k元树的带权外部路径长度，因此需将每个虚结点的权值赋0。这样，最后得到的归并树一定是满k元树。 程序设计：分两种情况，若k=2即二路归并时，不需要引入“虚”外部结点，每次只需将权值最小的结点两两归并。若k≠2，根据满k元树的性质可知，仅当n mod(k-1)=1时，不需要引入“虚”外部结点；当n mod(k-1)=0时，需引入1个“虚”外部结点；其他情况需引入”虚”外部结点个数为k-(n mod(k-1))。添加虚外部结点后，外部结点与内结点数的有如下关系关系：inner_node=(outer_node-1)/(k-1)。在本程序中，各文件的长度即权值，而且由于每次归并前，结点已经按权值递增的次序排列，所以每次归并仅需要将前K个元素归并即可。 源代码（见源代码merge.c）： #includestdio.h /*按照文件长度由小到大排序并显示*/ void sort_show(int start,int end,int k,int *s) { /*start、end分别为数组首末元素的小标*/ int i,j,cur,temp; for(i=start;iend;i++) { cur=i; for(j=i+1;j=end;j++) { if(s[j]s[cur]) cur=j; } if(cur!=i) { temp=s[cur]; s[cur]=s[i]; s[i]=temp; } } if(0!=(end-start)) { for(i=start;i=end;i++) { /*将前k个元素用括号括起来*/ if(i==start) printf((%d\t,s[i]); else if(i==start+k-1) printf(%d)\t,s[i]); else printf(%d\t,s[i]); } } else printf(%d,s[start]); } main() { /*文件个数file_num,k路归并,内部结点数即归并次数inner_node,需要引入的“虚”外部结点数unreal_node，总的外部结点数（包括虚结点）outer_node*/ int file_num,k,x,inner_node,outer_node,unreal_node; int i,j,count,sum,*list; printf(input the number of files: ); scanf(%d,file_num); printf(input k: ); scanf(%d,k); /*若k=2即二路归并时，不需要引入“虚”外部结点*/ if(2==k) unreal_node=0; else { /*若k!=2时，仅当file_num mod(k-1)=1时，不需要引入“虚”外部 结点*/ x=file_num%(k-1); if(0==x) unre