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

《算法设计与分析实验报告---模板.pdf》由会员分享，可在线阅读，更多相关《算法设计与分析实验报告---模板.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、;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+; 4void S

4、ortableList: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

5、);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() Sorta

6、bleList l(10); cout请输入 10 个数：endl; l.Input(); l.MergeSort();5 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 Q

7、uickSort(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;6li = lj;lj = c;int SortableList:Partition(int left,int right)/前置条件：left=rightint i

8、= 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);/对左子序列实施快速

9、排序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();7实验结果实验结果两路合并排序快速排序8六、实验小结六、实验小结包括问题和解决方法、心得体会等合并排序的基本运算是把两个或多个有序序列合并成一个有序序列。快速排序又称分划交换排序，分别将两个子序列拍成有序序列，则整个序列也就成了有序序列。首先要掌握基本的排序思想，然后把逻辑语言转化成程序语言，参考网上的各种答案优化自己的算法程序结合所学知识。七、指导教师评语七、指导教师评语成成绩绩批阅人批阅人日日期期9