菜鸟请教高人一个问题!
本人学习数据结构得到一个设计在链式存储结构上合并排序的算法:
void mergelklist(lklist *ha,lklist *hb,lklist *&hc)
{
lklist *s=hc=0;
while(ha!=0 && hb!=0)
if(ha-> data <hb-> data){if(s==0) hc=s=ha; else {s-> next=ha; s=ha;};ha=ha-> next;}
else {if(s==0) hc=s=hb; else {s-> next=hb; s=hb;};hb=hb-> next;}
if(ha==0) s-> next=hb; else s-> next=ha;
}
现在请教如何能把这个算法添加完整使其能在VC++编译器中执行,例如输入两组序列数,按回车就能将其合并排序了,不甚感激。
[解决办法]
合并排序 本来就是需要有序的序列
如果是无序的话,你得先对两个数组进行排序,然后再进行归并
[解决办法]
贴一个归并排序的例子做参考!
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <ctime>
using namespace std;
const int TOTAL_NUMBER = 100;
//两路归并排序
template <typename T>
void merage(T * a, int al, int am, int ar)
{
T * b = new T[ar - al +1];
int i = al, j = am + 1;
for(int k=0; k < ar - al + 1; ++k)
{
if(i > am) { b[k] = a[j++]; continue; }
if(j > ar) { b[k] = a[i++]; continue; }
b[k] = (a[i] < a[j]) ? a[i++]: a[j++];
}
for(int m=0; m < ar - al + 1; ++m)
a[m+al] = b[m];
delete [] b;
}
//归并排序算法
template <typename T>
void mergesort(T *R, int L, int H)
{
int M;
if(L < H)
{
M = (H + L)/2 ;
mergesort(R, L, M);
mergesort(R, M+1, H);
merage <T> (R, L, M, H);
}
}
void main()
{
clock_t start, finish;
srand((unsigned)time(NULL)); //以时间作随机数生成的种子
int *pa = new int[TOTAL_NUMBER+1];
for(int i=0; i <= TOTAL_NUMBER; i++ )
{
pa[i] = rand()%1000;
}
copy( pa, pa + TOTAL_NUMBER,
ostream_iterator <int> (cout, " "));
start= clock();
mergesort <int> (pa, 0, TOTAL_NUMBER-1); //调用归并排序算法
finish=clock();
cout < <endl;
copy( pa, pa + TOTAL_NUMBER,
ostream_iterator <int> (cout, " "));
cout < < "\nthe cost of times: " < <finish-start < <endl;
delete [] pa;
}