| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 342 人关注过本帖
标题:归并排序出现问题,请教高手,谢谢
只看楼主 加入收藏
yourcandy
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2010-6-1
结帖率:50%
收藏
已结贴  问题点数:20 回复次数:4 
归并排序出现问题,请教高手,谢谢
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define M (30)
 int array[M] = {0};
int* Malloc(int beg,int end)
{
    int* p = NULL;
    p = (int*)malloc(end-beg+1);

    if(NULL == p)
    {
        perror("malloc");
        exit (-1);
    }
    return p;
}
//升序函数
/**************************************************

 归并操作的工作原理如下:
   1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
   2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
   3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
   4. 重复步骤3直到某一指针达到序列尾
   5. 将另一序列剩下的所有元素直接复制到合并序列尾
 ******************************************/
void merge(int beg,int mid,int end)
{
    int k = 0;
    int *temp = Malloc(beg,end);
    printf("malloc size =%d\n",end-beg+1);
    int first1 = beg;
    int first2 = mid+1;
    while(first1 <= mid && first2 <= end)
    {
        if(array[first1] < array[first2])
            temp[k++] = array[first1++];
        else
            temp[k++] = array[first2++];
    }
    while(first1 <= mid)
        temp[k++] = array[first1++];
    while(first2 <= end)
        temp[k++] = array[first2++];
    for(k=0;k<(end-beg+1);++k)
        array[beg+k] = temp[k];
    free(temp);
}
/*********************************************
 * 函数名称:void merge_sort(int *array,int beg,int end)
 * 函数作用:使数组array从beg开始到end使升序的
 * 函数作者:
 * 完成日期:2010.11.2
 * ************************************************/
void merge_sort(int beg,int end)
{
    int mid = 0;
    if(beg == end)
        return;
    else
    {
        mid = (beg + end)/2;
        merge_sort(beg,mid);
        merge_sort(mid+1,end);
        merge(beg,mid,end);       //升序函数
    }
}
void print(int *array)
{
    int i=0;
    for(i=0;i<M;++i)
    {
        printf("%d\n",array[i]);
    }
}
int main()
{
    srand((int)time(0));
     int i = 0 ;
    for(i=0;i<M;++i)
    {
        array[i] = rand()%1000;
    }
   
    merge_sort(0,M-1);
    print(array);
}

如果M值小一点,输出是正确的,但是一旦M值较大,则输出出错,望懂得人能告诉小弟,不胜感激
2010-11-03 15:37
yourcandy
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2010-6-1
收藏
得分:0 
???
2010-11-03 15:39
yourcandy
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2010-6-1
收藏
得分:0 
哦,我自己知道了,原来是malloc函数出错,malloc申请得内存大小应该是(end-beg+1)*sizeof(int)
哎,这么简单得问题想这么久,下次要吸取教训,希望其他新手也要注意一下,这个malloc函数
2010-11-03 15:47
hahayezhe
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖南张家界
等 级:贵宾
威 望:24
帖 子:1386
专家分:6999
注 册:2010-3-8
收藏
得分:20 
嗯 可以结贴 给我分了 哈哈!
2010-11-03 15:48
yourcandy
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2010-6-1
收藏
得分:0 
回复 4楼 hahayezhe
太水了,您有什么更好的方法吗?关于归并排序的,小弟不胜感激
2010-11-03 15:52
快速回复:归并排序出现问题,请教高手,谢谢
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028689 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved