Mergersort问题！
取一段随机数字，发现结果遗漏部分数字，看了好长时间，不知道哪里有错，帮忙看下，谢谢了！代码如下：
#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
typedef struct node* LIST;
struct node{
int value;
LIST next;
};
void Print_list(LIST l)
{
LIST Temp_Ptr;
for(Temp_Ptr = l;Temp_Ptr != NULL; Temp_Ptr = Temp_Ptr->next)
{
cout << Temp_Ptr->value << " ";
}
}
LIST create_list(int n){
if(n==0)return NULL;
LIST l = new node;
l->value = rand() % 10000;
l->next = create_list(n-1);
return l;
}
LIST merge(LIST List_1, LIST List_2){
// merge two sorted lists and return the result
LIST l;
if(List_1==NULL)return List_2;
if(List_2==NULL)return List_1;
if (List_1->value >= List_2->value)
{
l = List_2;
l->next = merge(List_1,List_2->next);
}
else
{
l = List_1;
l->next = merge(List_1->next,List_2);
}
return l;
}
LIST SplitList(LIST l,LIST& List_1,LIST& List_2,int index)
{
if (l != NULL)
{
index++;
if (index%2 == 0)
{
List_1 = l;
SplitList(l->next,List_1->next,List_2,index );
}
else
{
List_2 = l;
SplitList(l->next,List_1,List_2->next,index );
}
}
else
{
List_1 = NULL;
List_2 = NULL;
}
}
LIST mergesort(LIST l){
if (l->next != NULL)
{
LIST List_1 = NULL;
LIST List_2 = NULL;
SplitList(l,List_1,List_2,0);
mergesort(List_1);
mergesort(List_2);
merge(List_1,List_2);
}//else there is only one item;
// check for base case, i.e. the stopping condition
// split the list into two halves
// mergesort each half
// merge the two sorted halves and return the result
}
int main(int argc, char** argv){
srand(time(NULL));
int n;
cout << "How many items you want to test?";
cin >> n;
LIST l = create_list(n);
cout<< "Original list is:\n";
Print_list(l);
cout << endl;
l = mergesort(l);
cout << "Sorted list is :\n";
Print_list(l);
system ("pause");
return 0;
}
问题点数：100、回复次数：4Top
1 楼cxjddd（又是花开时）回复于 2004-05-02 22:54:46 得分 0
怎么都用递归实现啊？
感觉结构有点复杂，难懂啊：（Top
2 楼alcla（冰淇淋真好吃，哈哈~~~）回复于 2004-05-03 06:21:12 得分 0
哎，我哭！是递归实现MERGESORT而且对象不是ARRAY，有人指点下吗？呵呵Top
3 楼nobush（）回复于 2004-05-03 11:20:06 得分 100
#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
typedef struct node* LIST;
struct node{
int value;
LIST next;
};
void Print_list(LIST lp)
{
LIST Temp_Ptr;
for(Temp_Ptr = lp;Temp_Ptr != NULL; Temp_Ptr = Temp_Ptr->next)
{
cout << Temp_Ptr->value << " ";
}
}
LIST create_list(int n){
if(n==0)return NULL;
LIST lp = new node;
lp->value = rand() % 10000;
lp->next = create_list(n-1);
return lp;
}
LIST merge(LIST List_1, LIST List_2){
// merge two sorted lists and return the result
LIST lp;
if(List_1==NULL)return List_2;
if(List_2==NULL)return List_1;
if (List_1->value >= List_2->value)
{
lp = List_2;
lp->next = merge(List_1,List_2->next);
}
else
{
lp = List_1;
lp->next = merge(List_1->next,List_2);
}
return lp;
}
LIST SplitList(LIST lp,LIST& List_1,LIST& List_2,int index)
{
if (lp != NULL)
{
if (index%2 == 0)
{
List_1 = lp;
SplitList(lp->next,List_1->next,List_2,++index );
}
else
{
List_2 = lp;
SplitList(lp->next,List_1,List_2->next,++index );
}
}
else
{
List_1 = NULL;
List_2 = NULL;
}
return lp;
}
LIST mergesort(LIST lp){
if (lp->next != NULL)
{
LIST List_1 = NULL;
LIST List_2 = NULL;
SplitList(lp,List_1,List_2,0);
List_1=mergesort(List_1);
List_2=mergesort(List_2);
lp=merge(List_1,List_2);
}//else there is only one item;
// check for base case, i.e. the stopping condition
// split the list into two halves
// mergesort each half
// merge the two sorted halves and return the result
return lp;
}
int main(int argc, char** argv){
srand(time(NULL));
int n;
cout << "How many items you want to test?";
cin >> n;
LIST lp = create_list(n);
cout<< "Original list is:\n";
Print_list(lp);
cout << endl;
lp = mergesort(lp);
cout << "Sorted list is :\n";
Print_list(lp);
system ("pause");
return 0;
}
建议楼主，注意代码书写规范，特别是不要以l作变量——会眼花的Top
4 楼alcla（冰淇淋真好吃，哈哈~~~）回复于 2004-05-03 12:23:17 得分 0
恩，感谢一下先！呵呵，下次注意。Top
