幻想森林

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 2614|回复: 5

[通用编程] 問個 歸並排序的問題

[复制链接]

313

主题

1574

帖子

1万

积分

⑧专业

*永恒国度*

积分
14145
QQ
发表于 2008-6-13 09:36:33 | 显示全部楼层 |阅读模式
  1. /**设个有序关键字表s1=(18,25,37,42),s2=(20,33,40).同时将s1,s2存储在数组r[1...7]中
  2. **s1放r[1..4],s2放[5..7],现要归并到一维数组r2[1..7]中,只要依次比较这两个有序
  3. **表中相应记录关键字,按取小原则复制到r2中
  4. **/
  5. #include<stdio.h>
  6. #define MAXITEM 100
  7. typedef struct rec
  8. {
  9.         int key;
  10.         char data[20];
  11. }elemnode[MAXITEM];
  12. void merge(elemnode r,elemnode r1,int l,int m,int h)
  13. {  // i,j是r的指示器,i的取值从l到m, j的取值从m+1到h,k是r1的指示器
  14.         int i = l,j = m+1,k = l;
  15.         while(i<=m && j<=h)
  16.         {
  17.                 if(r[i].key<=r[j].key)
  18.                 {
  19.                         r1[k] = r[i];
  20.                         i++;
  21.                 }
  22.                 else
  23.                 {
  24.                         r1[k] = r[j];j++;
  25.                 }
  26.                 k++;
  27.         }
  28.         if(i>m)
  29.                 while(j<=h)
  30.                 {
  31.                         r1[k] = r[j];
  32.                         j++;
  33.                         k++;
  34.                 }
  35.         else
  36.                 while(i<=m)
  37.                 {
  38.                         r1[k] = r[i];
  39.                         i++;
  40.                         k++;
  41.                 }
  42. }
  43. void mergepass(elemnode r,elemnode r1,int n,int l)
  44. {   
  45.         //将r中长度为L的两个部分合并,第一部分从p到期(p+l-1)
  46.         //第二部分从 p+1到(p+2*l-1)
  47.         int p = 1;
  48.         while(n-p+1>2*l)
  49.         {
  50.                 merge(r,r1,p,p+l-1,p+2*l-1);
  51.                 p+=2*l;    //p向后移动2*l,准备下一次合并
  52.         }
  53.         if(n-p+1>l)    //一个长度为l的部分与一个长度小于l的部分合并
  54.                 merge(r,r1,p,p+l-1,n);
  55.         else           //只剩下一个长度不大于l的部分,将其复制到r1
  56.                 for(;p<=n;p++) r1[p] = r[p];
  57. }
  58. void mergesort(elemnode r,elemnode r1,int n)
  59. {//对r中数据元素进行归并,结果仍放在r 中
  60.         int l = 1;
  61.         while(l<n)
  62.         {
  63.                 mergepass(r,r1,n,l);l*=2;
  64.                 mergepass(r1,r,n,l);l*=2;
  65.         }
  66. }
  67. void disp(elemnode r,int n)
  68. {
  69.         int i;
  70.         for(i=1;i<=n;i++)
  71.                 printf("%6d",r[i].key);
  72.         printf("\n");
  73.         for(i=1;i<=n;i++)
  74.                 printf("%6s",r[i].data);
  75.         printf("\n");
  76. }
  77. void main()
  78. {
  79.         elemnode s = {{0," "},{75,"王华"},{87,"李英"},{68,"张萍"},{92,"陈涛"},{88,"刘丽"},{61,"章强"},
  80.         {77,"孙军"},{96,"朱斌"},{80,"许伟"},{72,"曾亚"}};
  81.         elemnode s1;
  82.         int n = 10;
  83.         mergesort(s,s1,n);
  84.         disp(s,n);
  85. }
复制代码
void merge()這個函數基本理解了,但是void mergepass()這個函數就不怎麼看得懂,應該怎麼理解呢?
[img][/img] http://shop33698673.taobao.com被别人嫉妒,证明你优秀,嫉妒别人说明你无能
回复

使用道具 举报

7

主题

63

帖子

550

积分

⑤进阶

积分
550
发表于 2008-6-13 14:05:01 | 显示全部楼层
我是这么理解的不知道对不对

void mergepass(elemnode r,elemnode r1,int n,int l)
{  
        //将r中长度为L的两个部分合并,第一部分从p到期(p+l-1)
        //第二部分从 p+1到(p+2*l-1)
        int p = 1;
        while(n-p+1>2*l)
        {
                merge(r,r1,p,p+l-1,p+2*l-1);
                p+=2*l;    //p向后移动2*l,准备下一次合并
        }
        if(n-p+1>l)    //一个长度为l的部分与一个长度小于l的部分合并
                merge(r,r1,p,p+l-1,n);
        else          //只剩下一个长度不大于l的部分,将其复制到r1
                for(;p<=n;p++) r1[p] = r[p];
}

void mergesort(elemnode r,elemnode r1,int n)
{//对r中数据元素进行归并,结果仍放在r 中
        int l = 1;
        while(l<n)
        {
                mergepass(r,r1,n,l);l*=2;
                mergepass(r1,r,n,l);l*=2;
        }
}



R中比如最大是N,在N里存在很多个L长度,从1开始,取L长度,只要2L个长度不超N,然后取L长度和后L个长度进行比较结果存到R1里,这个参考第一个函数就知道了,做好后P移动到2L长度后的位置,然后其他情况就是只剩一个L的长度和一个未满L的长度,同样再用第一函数合并,或者最后剩下不到一个L的长度直接全部到R1,然后主要看下下面一个函数mergepass(r,r1,n,l);l*=2; mergepass(r1,r,n,l);l*=2;
回复 支持 反对

使用道具 举报

7

主题

63

帖子

550

积分

⑤进阶

积分
550
发表于 2008-6-13 14:17:18 | 显示全部楼层
时,L为1时就是一个元素一个元素比较比如1和2比较好,3和4比较,一直比到最后所有结果进R1,然后L双倍后,在R1里就是两个两个元素进行比较,比如12和34,56和78比好后在回到R里,这样循环
回复 支持 反对

使用道具 举报

7

主题

63

帖子

550

积分

⑤进阶

积分
550
发表于 2008-6-13 14:34:00 | 显示全部楼层
具体设了个R和R1
R :0 4 6 2 3 1 8  第一次L=1时排列
R1 变成:40 26 13 8 随后L变为2 把R1倒回R
R变成:0246 138 这时L变为4用情况2做
R1变成:0123468 L变为8了情况3直接复制回R
所以最后R排好
回复 支持 反对

使用道具 举报

313

主题

1574

帖子

1万

积分

⑧专业

*永恒国度*

积分
14145
QQ
 楼主| 发表于 2008-6-13 14:34:34 | 显示全部楼层
还没细看,看不懂。。。
[img][/img] http://shop33698673.taobao.com被别人嫉妒,证明你优秀,嫉妒别人说明你无能
回复 支持 反对

使用道具 举报

7

主题

63

帖子

550

积分

⑤进阶

积分
550
发表于 2008-6-13 14:38:15 | 显示全部楼层
引用第4楼august于2008-06-13 14:34发表的  :
还没细看,看不懂。。。

这个例子应该看的懂吧

具体设了个R和R1
R :0 4 6 2 3 1 8  第一次L=1时排列
R1 变成:40 26 13 8 随后L变为2 把R1倒回R
R变成:0246 138 这时L变为4用情况2做
R1变成:0123468 L变为8了情况3直接复制回R
所以最后R排好
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|幻想森林

GMT+8, 2024-3-29 19:38 , Processed in 0.025225 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表