实验三归并排序的分治策略设计(4学时)
[实验目的]
1.熟悉二分检索问题的线性结构表示和二分检索树表示;
2.熟悉不同存储表示下求解二分检索问题的递归算法设计;
3.通过实例转换, 掌握将递归算法转换成迭代算法的方法;
4.掌握应用递归或迭代程序设计实现分治法求解问题的抽象控制策略.
[预习要求]
1.认真阅读算法设计教材和数据结构教材内容, 熟悉不同存储表示下求解二分检索问题的原理或方法;
2.针对线性结构表示和二分检索树表示设计递归算法;
3.参考教材和课堂教学内容, 根据将递归算法转换成迭代算法的一般步骤将二分检索递归算法转换成相应的迭代算法.
[实验步骤]
1. 调试线性结构表示下的快速分类与二分检索递归程序, 直至正确为止;
2. 调试线性结构表示下的快速分类与二分检索迭代程序, 直至正确为止;
3. 待各功能子程序调试完毕, 去掉测试程序, 将程序整理成功能模块存盘备用.
1.归并排序
(备注:语言C++;编译器:MS VS2008;共2个文件)
head.h文件
#include
#include
using namespace std;
void mergeSort(int *a,int left,int right);
void merge(int *a,int left,int i,int right);
main.cpp文件
#include "head.h"
void main()
{
int test[]={0,12,45,3,6,29,4,16,77};
cout<<"before:";
for(int i=0;i<=8;i++)
{