返回信息流#include<iostream.h>
using namespace std ;
const int DefaultSize = 12 ; //排序表的最大容量
template<class Type>
class dataList //排序表类
{
public:
dataList(int MaxSz = DefaultSize):MaxSize(MaxSz) //构造函数
{key = new Type[MaxSize] ;}
~dataList(){delete []key ;} //析构函数
void Swap(Type &x , Type &y)
{Type temp = x ; x = y ; y = temp ;} //两变量值对换函数
void input(); //用户输入界面函数
void output(); //输出排序表数组
void merge(dataList<Type>&mergedList , int left , int mid , int right) ;
void MergePass(dataList<Type>&mergedList , int len); //将原始表分成长度为len的子表，两两归并
void MergeSort(int way); //两路归并排序（主算法）
//函数功能：将一个表分成两路，归并排序后存入一个新表中
private:
Type *key ; //指向待排序表的指针
int MaxSize ; //排序表的容量
};
template<class Type>
void dataList<Type>::input() //用户输入界面函数
{
int num , countI = 0 , choose , way ;
cout << "Please input "<< MaxSize << " positive integers(-1 to end):" << endl ; //默认所排序的数值是正整数
cin >> num ;
while(num != -1)
{
key[countI] = num ;
countI ++ ;
cin >> num ;
}
cout << "The data is inputed successfully！" << endl ;
cout << "The initial list is:" << endl ;
output();
MergeSort();
cout << "The sorted list is:" << endl ;
output();
}
template<class Type> //输出排序表数组
void dataList<Type>::output()
{
for(int countI = 0 ; countI < MaxSize ; countI++)
cout << key[countI] << " " ;
cout << endl << endl ;
}
template<class Type>
void dataList<Type>::merge(dataList<Type>&mergedList , const int left , const int mid , const int right)
//函数功能：将一个表分成两路，归并排序后存入一个新表中
{
int i = left , j = mid + 1 , k = left ;
while(i <= mid && j <= right)
{
if(key[i] < key[j])
{
mergedList.key[k] = key[i] ;
i++ ; k++ ;
}
else
{
mergedList.key[k] = key[j] ;
j++ ; k++ ;
}
}
if(i < mid)
for(int n1 = k , n2 = i ; n2 <= mid ; n1++ , n2++)
mergedList.key[n1] = key[n2] ;
else
for(int n1 = k , n2 = j ; n2 <= right ; n1++ , n2++)
mergedList.key[n1] = key[n2] ;
}
template<class Type>
void dataList<Type>::MergePass(dataList<Type>&mergedList , const int len) //将原始表分成长度为len的子表，两两归并
{
int i = 0 ;
while(i + 2 * len <= MaxSize -1)
{
merge(mergedList , i , i + len - 1 , i + 2 * len - 1) ;
i += 2 * len ;
}
if(i + len <= MaxSize - 1)
merge(mergedList , i , i + len - 1 , MaxSize - 1);
else
{
for(int j = i ; j <= MaxSize - 1 ; j ++)
mergedList.key[j] = key[j] ;
}
}
template<class Type>
void dataList<Type>::MergeSort(int Way) //两路归并排序（主算法）
{
dataList<Type>&tempList(MaxSize);
int len = 1 ;
while(len < MaxSize)
{
MergePass(tempList , len) ; len *= 2 ;
tempList.MergePass(this , len) ; len *= 2 ;
}
delete []tempList ;
cout << "The sorted increasing list is:" << endl ;
output();
}
int main()
{
dataList<int> list(DefaultSize) ;
list.input();
system("pause");
}
这是一条镜像帖。来源：北邮人论坛 / cpp / #33096同步于 2009/12/8
CPP机器人发帖
求助：用c++类编写的归并函数总是编译报错，请求高人指点
kkxhx
2009/12/8镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。