算法设计与分析实验报告 - 模板.doc

精品文档实 验 报 告（2016/2017学年 第一学期）课程名称算法分析与设计实验名称分治策略实验时间2016年10月18日指导单位计算机学院软件教学中心指导教师季一木学生姓名周文超班级学号B14041527学院(系)计算机学院、软件学院专 业软件工程.实 验 报 告实验名称分治策略指导教师季一木实验类型验证实验学时2实验时间2016.10.18一、 实验目的和任务1.理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程序，加深对分治法的算法原理及实现过程的理解。 2.用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理，编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。 二、 实验环境(实验设备)算法设计与分析课本笔记本电脑 VC+6.0三、实验原理及内容（包括操作过程、结果分析等）实验原理运用分治法 ：无序-部分有序-整体有序归并排序中“分”与“合”的过程是结合在一起的，即每一趟都在做“分” 与“合”的工作，并不是先“分”完再“合” 基本程序（一） 两路合并排序#includeclass SortableListpublic:SortableList(int mSize) /构造函数maxSize = mSize;l = new intmaxSize;n = 0;SortableList()deletel; /析构函数void Input();void Merge(int left,int mid,int right);void MergeSort();void MergeSort(int left,int right);void Output();private:int *l; /动态生成一维数组int maxSize; /线性表的最大表长int n; /线性表的实际长度;void SortableList:Input()for(int i = 0;ili;n+;void SortableList:Merge(int left,int mid,int right)int *temp = new intright-left+1;int i = left,j = mid +1,k = 0;while(i=mid)&(j=right)if(li=lj)tempk+=li+;elsetempk+=lj+;while(i=mid)tempk+=li+;while(j=right)tempk+=lj+;for(i = 0,k=left;k=right;)lk+=tempi+;void SortableList:MergeSort()MergeSort(0,n-1);void SortableList: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(int i = 0;imaxSize;i+)coutli ;void main()SortableList l(10);cout请输入10个数：endl;l.Input();l.MergeSort();cout排序后是：endl;l.Output();（二）快速排序#includeclass SortableListpublic:SortableList(int mSize) /构造函数maxSize = mSize;l = new intmaxSize;n = 0;SortableList()deletel; /析构函数void Input();void Swap(int i,int j);int Partition(int left,int right);void QuickSort(int left,int right);void QuickSort();void Output();private:int *l; /动态生成一维数组int maxSize; /线性表的最大表长int n; /线性表的实际长度;void SortableList:Input()for(int i = 0;ili;n+;void SortableList:Swap(int i,int j)int c = li;li = lj;lj = c;int SortableList:Partition(int left,int right)/前置条件：left=rightint i = left,j = right + 1; dodo i+;while(lilleft);if(ij)Swap(i,j);while(ij);Swap(left,j);return j;void SortableList:QuickSort()QuickSort(0,n-1);void SortableList:QuickSort(int left,int right)if(leftright) /当序列长度大于1时，需进行分割int j = Partition(left,right);/对left,right范围内的序列进行分划QuickSort(left,j-1);/对左子序列实施快速排序QuickSort(j+1,right);/对右子序列实施快速排序void SortableList:Output()for(int i = 0;imaxSize;i+)coutli ;void main()SortableList l(10);cout请输入10个数：endl;l.Input();l.QuickSort();cout排序后是：endl;l.Output();实验结果两路合并排序快速排序 六、实验小结（包括问题和解决方法、心得体会等） 合并排序的基本运算是把两