算法与程序设计上机报告.doc

《算法与程序设计上机报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、上机实验一一、实验题目用分治法进行归并分类二、算法介绍将A(1),......,A(n)均分成两个集合，在对每个集合单独分类，然后将已分类的两个序列归并成一个含n个元素的分好类的序列；merge（）函数负责把两个已分类集合归并在一起，mergesort（）函数通过使用递归和调用merge（）函数完成该处理过程三、程序流程图：说明：A[N]、B[N]是全程数组，A[]存放待分类的元素，B[]是辅助数组归并分类算法mergesort（递归算法）的具体扩展：说明：入口参数：待分类集合A(low:high)的头和尾元素位置low、highmerge函数的具体扩展：//使

2、用辅助数组归并两个已分类的集合说明：入口参数：集合A(low:high)的头和尾元素位置low、high及该集合的分割点（二分）四、源程序及实验结果程序代码如下：#include#include#defineN1024intA[N],B[N];//A[N]、B[N]是全程数组，A[]存放待分类的元素，B[]是辅助数组voidmerge(intlow,intmid,inthigh)//使用辅助数组归并两个已分类的集合/*数组A（low：high）包含两个放在A(low:mid)和A(mid+1:high)中的已分类的子集合*此函数

3、是使用一个辅助数组B（low：high）将这两个已分类的集合归并成一个集合，并存放到A（low：high）中*/{inth,k,i,j;h=low;i=low;j=mid+1;while(h<=mid&&j<=high)//当两个集合都没取尽时{if(A[h]<=A[j]){B[i]=A[h];h++;}else{B[i]=A[j];j++;}i++;}//处理剩余的元素if(h>mid)/*A(low:mid)数组取完时，将A(mid+1:high)中剩余元素依次复制到数组B(low：high)尾部*/{for(k=j;k<=high;k++){B[i]=A[

4、k];i++;}}elsefor(k=h;k<=mid;k++)/*A(mid+1:high)数组取完时，将A(low:mid)中剩余元素依次复制到数组B(low：high)尾部*/{B[i]=A[k];i++;}for(k=low;k<=high;k++)//将已归并的集合复制到A中{A[k]=B[k];}}voidmergesort(intlow,inthigh)//归并分类/*将本集合二分为两个集合，再递归调用merge（）函数对每个集合单独分类并将已分类的*两个序列归并为一个分好类的序列*/{intmid;if(low

5、oor((low+high)/2);//求这个集合的分割点mergesort(low,mid);//将一个子集合分类mergesort(mid+1,high);//将另一个子集合分类merge(low,mid,high);//归并两个已分类的子集合}}voidmain(){inti=1,cx;//cx中存放待排序元素的个数printf("inputdata'snumber:");//显示提示信息scanf("%d",&cx);//输入待排序元素的个数printf("inputdatas:");for(i=1;i<=cx;i++)//输入待排序的各个元素的值，

6、并存放到集合A中{scanf("%d",&A[i]);}mergesort(1,i-1);//调用归并分类算法对数组A（1：i-1）进行归并排序printf("outputdatas:");for(i=1;i<=cx;i++)//输出进行归并排序后的集合A{printf("%d,",A[i]);}getch();}运行结果如下图：(运行结果与理论结果一致)五、结果分析运行源程序后，先输入待排序元素的个数，回车。再分别输入打乱的元素的值序列，回车，显示按升序排列的元素值序列。最坏情况：输入数据按非增次序排列,每次内层while循环执行j次（j=2,3,…,n)

7、。则有，Ω(n(n+1)/2-1)=Ω(n2);最好情况：输入数据已按非降序排列，不进入while循环，则最好情况下计算时间为Ω(n)。上机实验二一、实验题目用分治法进行快速分类二、算法介绍在集合A(1:n)中选一元素t=A[s]，然后将其它元素重新排列，使A(1:n)中所有在t以前出现的元素都小于或等于t，而在t后出现的元素都不小于t,元素t为划分元素，快速分类就是通过反复对产生的集合进行划分来实现的。三、程序流程图说明：A[1024]是全程数组，其中存放待分类的元素快速分类算法quicksort（递归算法）的具体扩展如下：说明：入口参数:集合A（p:q）的p

8、、qpartition函