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

实 验 报 告

（2016/2017学年 第一学期）

课程名称 实验名称 实验时间 指导单位 指导教师 学生姓名 周文超 2016 算法分析与设计 分治策略 年 10 月 18 日 计算机学院软件教学中心 季一木 班级学号 B 软件工程 学院(系) 计算机学院、专 业 软件学院 实 验 报 告

实验名称 实验类型 验证 分治策略 实验学时 2 指导教师 实验时间 季一木 一、 实验目的和任务 1.理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程序，加深对分治法的算法原理及实现过程的理解。 2.用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理，编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。 二、 实验环境(实验设备) 算法设计与分析课本 笔记本电脑 VC++ 三、实验原理及内容（包括操作过程、结果分析等） 实验原理 运用分治法 ：无序->部分有序->整体有序 归并排序中“分”与“合”的过程是结合在一起的，即每一趟都在做“分” 与“合”的工作，并不是先“分”完再“合” 基本程序 （一）两路合并排序 #include<> class SortableList{ public: SortableList(int mSize) //构造函数 { maxSize = mSize; l = new int[maxSize]; n = 0; } ~SortableList(){delete[]l;} //析构函数 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;i>l[i]; n++; } } void SortableList::Merge(int left,int mid,int right){ int *temp = new int[right-left+1]; int i = left,j = mid +1,k = 0; while((i<=mid)&&(j<=right)) if(l[i]<=l[j]) temp[k++]=l[i++]; else temp[k++]=l[j++]; while(i<=mid) temp[k++]=l[i++]; while(j<=right) temp[k++]=l[j++]; for(i = 0,k=left;k<=right;) l[k++]=temp[i++]; } void SortableList::MergeSort(){ MergeSort(0,n-1); } void SortableList::MergeSort(int left,int right){ if(left