算法设计与分析报告实验报告材料 - 实用模板

《算法设计与分析报告实验报告材料 - 实用模板》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验报告（2016/2017学年第一学期）课程名称算法分析与设计实验名称分治策略实验时间2016年10月18日指导单位计算机学院软件教学中心指导教师季一木学生姓名周文超班级学号B14041527学院(系)计算机学院、软件学院专业软件工程9实验报告实验名称分治策略指导教师季一木实验类型验证实验学时2实验时间2016.10.18一、实验目的和任务1.理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程序，加深对分治法的算法原理及实现过程的理解。2.用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及

2、快速排序的基本原理，编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。9一、实验环境(实验设备)算法设计与分析课本笔记本电脑VC++6.09三、实验原理及内容（包括操作过程、结果分析等）实验原理运用分治法：无序->部分有序->整体有序归并排序中“分”与“合”的过程是结合在一起的，即每一趟都在做“分”与“合”的工作，并不是先“分”完再“合”基本程序（一）两路合并排序#includeclassSortableList{public:SortableList(intmSize)//构造

3、函数{maxSize=mSize;l=newint[maxSize];n=0;}~SortableList(){delete[]l;}//析构函数voidInput();voidMerge(intleft,intmid,intright);voidMergeSort();voidMergeSort(intleft,intright);voidOutput();private:int*l;//动态生成一维数组intmaxSize;//线性表的最大表长intn;//线性表的实际长度};voidSortableList::I

4、nput(){for(inti=0;i>l[i];n++;}}9voidSortableList::Merge(intleft,intmid,intright){int*temp=newint[right-left+1];inti=left,j=mid+1,k=0;while((i<=mid)&&(j<=right))if(l[i]<=l[j])temp[k++]=l[i++];elsetemp[k++]=l[j++];while(i<=mid)temp[k++]=l[i++];wh

5、ile(j<=right)temp[k++]=l[j++];for(i=0,k=left;k<=right;)l[k++]=temp[i++];}voidSortableList::MergeSort(){MergeSort(0,n-1);}voidSortableList::MergeSort(intleft,intright){if(left

6、序列排序MergeSort(mid+1,right);//对右序列排序Merge(left,mid,right);//将两个有序子序列合并成一个有序序列}}voidSortableList::Output(){for(inti=0;i

7、排序#includeclassSortableList{public:SortableList(intmSize)//构造函数{maxSize=mSize;l=newint[maxSize];n=0;}~SortableList(){delete[]l;}//析构函数voidInput();voidSwap(inti,intj);intPartition(intleft,intright);voidQuickSort(intleft,intright);voidQuickSort();voidO

8、utput();private:int*l;//动态生成一维数组intmaxSize;//线性表的最大表长intn;//线性表的实际长度};voidSortableList::Input(){for(inti=0;i>l[i];n++;}}voidSortableList::Swap(inti,