《算法设计与分析报告实验报告材料-实用模板.doc》由会员分享，可在线阅读，更多相关《算法设计与分析报告实验报告材料-实用模板.doc（16页珍藏版）》请在三一文库上搜索。
1、AU瑯唸Z磬实验报告（2016/2017 学年 第一学期）课程名称算法分析与设计实验名称分治策略实验时间2016年 10 月 18 日指导单位计算机学院软件教学中心指导教师季一木学生姓名周文超班级学号B14041527学院（系）计算机学院、软件学院专业软件工程实验报告实验名称分治策略指导教师季一木实验类型验证实验学时2实验时间2016.10.18实验目的和任务1理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程 加深对分治法的算法原理及实现过程的理解。iBM：2用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理，编程实现分别用这两种方法将输入的一组
2、 无序序列排序为有序序列后输出实验环境（实验设备）算法设计与分析课本 笔记本电脑VC+6.0三、实验原理及内容（包括操作过程、结果分析等）实验原理运用分治法：无序- 部分有序- 整体有序SM MH MV MB MBBM HH BM BT MB BBMH! MM MM MH MB!归并排序中“分”与“合”的过程是结合在一起的，即每一趟都在做“分” 与“合”的工作，并不是先“分”完再“合”基本程序(一)两路合并排序#in cludeclass SortableListpublic:SortableList(i nt mSize) / 构造函数maxSize = mSize;l = new in t
3、maxSize;n = 0;SortableList()deletel; / 析构函数void In put();void Merge(i nt left,i nt mid,i nt right);void MergeSort();void MergeSort(int left,int right);void Output();private:int *l;/动态生成一维数组int maxSize; /线性表的最大表长int n; /线性表的实际长度;void SortableList:l nput()for(i nt i = O;i li;n+;void SortableList:Merge
4、(i nt left,i nt mid,i nt right)int *temp = new in tright-left+1;int i = left,j = mid +1,k = 0;while(i=mid)&(j=right)if(li=lj)tempk+=li+;elsetempk+=l j+;while(i=mid) tempk+=li+;while( j=right)tempk+=l j+;for(i = O,k=left;k=right;)lk+=tempi+;void SortableList:MergeSort()MergeSort(0, n-1);void Sortable
5、List:MergeSort(int left,int right)if(leftright)/若序列的长度超过1，则划分成两个子序列int mid = (left+right)/2;将待排序的序列一分为二MergeSort(left,mid);/对左序列排序对右序列排序MergeSort(mid+1,right);/Merge(left,mid,right);/将两个有序子序列合并成一个有序序列void SortableList:Output()for(i nt i = O;imaxSize;i+) coutli;void mai n()SortableList l(10);cout 请输入
6、 10 个数：endl;l.I nput();l.MergeSort();cout排序后是：e ndl; l.Output();(二)快速排序#in cludeclass SortableListpublic:SortableList(i nt mSize) /构造函数maxSize = mSize;l = new in tmaxSize;n = 0;SortableList()deletel; /析构函数void In put();void Swap(i nt i,i nt j);int Partiti on (i nt left,i nt right);void QuickSort(int
7、 left,int right);void QuickSort();void Output();private:int *1;/动态生成一维数组int maxSize; /线性表的最大表长int n; /线性表的实际长度； void SortableList:l nput()for(i nt i = O;i li;n+; void SortableList:Swap(i nt i,i nt j)int c = li;li = l j;lj = c;int SortableList:Partition(int left,int right)/ 前置条件：left=rightint i = lef
8、t,j = right + 1;dodo i+;while(lilleft);if(ij)Swap(i,j);while(ij);Swap(left,j);return j;void SortableList:QuickSort()Quicksort n-1);void SortableList:QuickSort(int left,int right)if(leftright) /当序列长度大于1时，需进行分割int j = Partitio n(left,right);对left,right 范围内的序列进行分划QuickSort(left,j-1);/对左子序列实施快速排序QuickSo
9、rt(j+1,right);/对右子序列实施快速排序void SortableList:Output()for(i nt i = O;imaxSize;i+)coutli;void mai n()SortableList l(10);cout 请输入 10 个数：endl;l.I nput();I.QuickSort();cout排序后是：e ndl;I.Output();实验结果两路合并排序六、实验小结（包括问题和解决方法、心得体会等）合并排序的基本运算是把两个或多个有序序列合并成一个有序序列。快速排序又称分划交换排序，分别将两个子序列拍成有序序列，则整个序列也就成了 有序序列。首先要掌握基本的排序思想，然后把逻辑语言转化成程序语言，参考网上的各种答案 优化自己的算法程序结合所学知识。七、指导教师评语成绩批阅人日期14