- 注册时间
- 2004-10-13
- 最后登录
- 2019-5-15
⑧专业
*永恒国度*
- 积分
- 14145
|
- /**设个有序关键字表s1=(18,25,37,42),s2=(20,33,40).同时将s1,s2存储在数组r[1...7]中
- **s1放r[1..4],s2放[5..7],现要归并到一维数组r2[1..7]中,只要依次比较这两个有序
- **表中相应记录关键字,按取小原则复制到r2中
- **/
- #include<stdio.h>
- #define MAXITEM 100
- typedef struct rec
- {
- int key;
- char data[20];
- }elemnode[MAXITEM];
- void merge(elemnode r,elemnode r1,int l,int m,int h)
- { // i,j是r的指示器,i的取值从l到m, j的取值从m+1到h,k是r1的指示器
- int i = l,j = m+1,k = l;
- while(i<=m && j<=h)
- {
- if(r[i].key<=r[j].key)
- {
- r1[k] = r[i];
- i++;
- }
- else
- {
- r1[k] = r[j];j++;
- }
- k++;
- }
- if(i>m)
- while(j<=h)
- {
- r1[k] = r[j];
- j++;
- k++;
- }
- else
- while(i<=m)
- {
- r1[k] = r[i];
- i++;
- k++;
- }
- }
- 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;
- }
- }
- void disp(elemnode r,int n)
- {
- int i;
- for(i=1;i<=n;i++)
- printf("%6d",r[i].key);
- printf("\n");
- for(i=1;i<=n;i++)
- printf("%6s",r[i].data);
- printf("\n");
- }
- void main()
- {
- elemnode s = {{0," "},{75,"王华"},{87,"李英"},{68,"张萍"},{92,"陈涛"},{88,"刘丽"},{61,"章强"},
- {77,"孙军"},{96,"朱斌"},{80,"许伟"},{72,"曾亚"}};
- elemnode s1;
- int n = 10;
- mergesort(s,s1,n);
- disp(s,n);
- }
复制代码 void merge()這個函數基本理解了,但是void mergepass()這個函數就不怎麼看得懂,應該怎麼理解呢? |
|