[求助]关于二路归并排序的问题 - 数据结构与算法

楼主

问题点数：0 回复次数：5

[求助]关于二路归并排序的问题

自己按照书上算法编的，可以运行，不过结果好象不对，请大家帮忙看下问题出在哪里

/* 二路归并排序*/
/*最后修改2007-1-1*/
#include<stdio.h>

#define MAXNUM 20
#define TRUE 1
#define FALSE 0

typedef int KeyType;

typedef struct
{
KeyType key;
}RedType;

typedef struct
{
int n;
RedType record[MAXNUM];
} SqList;

void Merge(RedType SR[], RedType TR[], int i, int m, int n)
{

int j,k;

for ( j = m + 1,k=i;i <= m && j <=n;++k )/*将SR中记录由小到大地并入TR*/
{
if (SR[i].key <= SR[j].key)
TR[k] = SR[i++];
else TR[k] = SR[j++];
}
if(i <= m) TR[k++] = SR[i++]; /*将剩余的SR[i..m]复制到TR*/
if(j <= n) TR[k++] = SR[j++]; /*将剩余的SR[j..n]复制到TR*/

}/*将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]*/

void MSort(RedType SR[], RedType TR1[], int s, int t)
{

int m;
RedType TR2[MAXNUM];
if(s==t) TR1[s]=SR[s];
else
{
m=(s+t)/2; /*将SR[s..t]平分为SR[s..m]和SR[m+1..t]*/
MSort(SR,TR2,s,m); /*递归地将SR[s..m]归并为有序的TR2[s..m]*/
MSort(SR,TR2,m+1,t); /*递归地将SR[m+1..t]归并为有序的TR2[m+1..t]*/
Merge(TR2,TR1,s,m,t);/*将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]*/
}

}/*将SR[s..t]归并排序为TR1[s..t]*/

void MergeSort(SqList L)
{

MSort(L.record,L.record,1,L.n);
}/*对顺序表L作归并排序*/

int main(){
int i;
SqList List = {7,5,3,2,6,8,9,4,1};
MergeSort(List);
for(i = 0; i < 8; i++)
printf("%d ", List.record[i]);
getchar();
return 0;
}

搜索更多相关主题的帖子: int　RedType　typedef　define　KeyType　

第 2 楼

得分:0

算法没问题，
对List的初始化是错的，
List.record[1].key=7;...
List.n=?;
应该这样初始化，还有，你把
SqList定义成结构体后，List只是一个变量，而不是数组。在调用MergeSort()时，应该传址，而不是传这个变量过去，
或者你在函数定义上加个取址符，即void MergeSort(SqList＆ L)

对不礼貌的女生收钱......

第 3 楼

得分:0

多谢斑竹,按你的提示我改了一下,不过List的初始化应该没有问题吧,改后的程序还有一个小问题
我的 SqList List = {8,5,3,2,6,7,9,4,1};
按道理应该输出
8 5 3 2 6 7 9 4 1
1 2 3 4 5 6 7 8 9
不过我的输出是
5 3 2 6 7 9 4 1
1 2 3 4 5 6 7 9
第一个8不知道为什么不见了,改了好长时间了,还没看出问题在哪,调试我不太会,所以不太好找问题在哪,麻烦了

/* 二路归并排序*/
/*最后修改2007-1-2*/
#include<stdio.h>

#define MAXNUM 20
#define TRUE 1
#define FALSE 0

typedef int KeyType;

typedef struct
{
KeyType key;
}RedType;

typedef struct
{
int n;
RedType record[MAXNUM];
} SqList;

void Merge(RedType SR[], RedType TR[], int i, int m, int n)
{

int j,k;

for ( j = m + 1,k=i;i <= m && j <=n;++k )/*将SR中记录由小到大地并入TR*/
{
if (SR[i].key <= SR[j].key)
TR[k] = SR[i++];
else TR[k] = SR[j++];
}
while(i <= m) TR[k++] = SR[i++]; /*将剩余的SR[i..m]复制到TR*/
while(j <= n) TR[k++] = SR[j++]; /*将剩余的SR[j..n]复制到TR*/

}/*将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]*/

void MergeSort(SqList *L)
{

MSort(L->record,L->record,0,L->n);
}/*对顺序表L作归并排序*/

void main(){
int i;
SqList List = { 7, 5,3,2,6,8,9,4,1 };

for(i = 0; i < 8; i++)
printf("%d ", List.record[i]);
putchar( '\n' );

MergeSort(&List);
for(i = 0; i < 8; i++)
printf("%d ", List.record[i]);
getchar();
}

[此贴子已经被作者于2007-1-2 22:25:14编辑过]

第 4 楼

得分:0

汗,想通了,算法没有看得太明白,第一个8是需要排序的个数,根本不需要参加排序
下面一个程序可以实现了，谢谢斑竹了

/* 二路归并排序*/
/*最后修改2007-1-2*/
#include<stdio.h>

#define MAXNUM 20
#define TRUE 1
#define FALSE 0

typedef int KeyType;

typedef struct
{
KeyType key;
}RedType;

typedef struct
{
int n;
RedType record[MAXNUM];
} SqList;

void Merge(RedType SR[], RedType TR[], int i, int m, int n)
{

int j,k;

for ( j = m + 1,k=i;i <= m && j <=n;++k )/*将SR中记录由小到大地并入TR*/
{
if (SR[i].key <= SR[j].key)
TR[k] = SR[i++];
else TR[k] = SR[j++];
}
while(i <= m) TR[k++] = SR[i++]; /*将剩余的SR[i..m]复制到TR*/
while(j <= n) TR[k++] = SR[j++]; /*将剩余的SR[j..n]复制到TR*/

}/*将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]*/

void MergeSort(SqList *L)
{

MSort(L->record,L->record,0,L->n-1);
}/*对顺序表L作归并排序*/

void main(){
int i;
SqList List = {8,5,3,2,6,7,8,4,1};

for(i = 0; i < 8; i++)
printf("%d ", List.record[i]);
putchar( '\n' );

MergeSort(&List);
for(i = 0; i < 8; i++)
printf("%d ", List.record[i]);
getchar();

}

第 5 楼

得分:0

你这样初始化编译的时候竟然没错，晕，我自己从没这样初始化，倒是我少见多怪了，
对于这句SqList List = {8,5,3,2,6,7,9,4,1};
默认把8赋给了List.n，而后面的依次给List.record[i]，给出初始的数组不够长，后面的为０来补足．
调用的时候，就对前０－８（共９个数，比８多１）个数进行排序了，所以你给的初始化的第一个数８看起来是不见了．

对不礼貌的女生收钱......

第 6 楼

得分:0

这种方法我也是从别人那里看到的，理解还不是很透彻
所以看了半天都没看懂，后来一下子想通了，程序改起来就方便多了
主要是两个地方没有理解好：一个初始化，一个＆Ｌist
前面的现在想通了，后面的还要好好看看书了，书上算法本来是有那个＆的，由于看不懂，我就给扔了，原来还是有用的啊．．．好在现在程序没问题了，呵呵