#include <stdio.h> #include<stdlib.h> #include<time.h> void input(int &a,int & n); void…
- User
#include <stdio.h> #include<stdlib.h> #include<time.h> void input(int &a,int & n); void output(int a,int n); void HeapAdjust(int a,int s,int m) ; void HeapSort(int a,int n); int main () { int i,n,m; int a = NULL; input (a,n); HeapSort (a,n) ; free(a); return 0; }void input(int &a,int & n) { int i; scanf("%d",&n); if((a=(int ) malloc (nsizeof(int)))==NULL) { printf("不能成功分配内存单元\n"); exit(0); } for(i=0;i<n;i++) { scanf("%d",&a[i]); } } void output(int a,int n) { int i; for(i=0;i<n;i++) { printf("%d ",a[i]); } printf("\n"); }void swap(int &a, int &b) { int t; t=a;a=b;b=t; } /定义函数/ /***** Begin / void HeapAdjust(int a,int s,int m){ int j,rc=a[s]; for(j=2s;j<=m;j=2) { if(j<m&&a[j]<a[j+1]) ++j; if(rc>=a[j]) break; a[s]=a[j]; s=j; } a[s]=rc; for(j=0;j<m;j++){ printf("%d ",a[j]); } printf("\n"); }void HeapSort(int a,int n){ int i; for(i=n/2;i>0;--i){ HeapAdjust(a,i,n); }}/** End **********/问题是什么?
- Assistant
代码中的HeapAdjust函数只是将堆调整为大根堆,但是没有完成整个堆排序的过程,缺少将根节点和末尾节点调换再重新调整的步骤。同时,代码中也没有调用output函数输出排序后的结果。
- User
怎么改?
- Assistant
可以将HeapAdjust函数中的for循环和a[s]=rc;这段代码放到一个while循环中,完整完成堆的调整过程,并将堆排序和输出的代码加入main函数中,如下所示:
#include <stdio.h> #include <stdlib.h> #include <time.h> void input(int *&a, int &n); void output(int *a, int n); void HeapAdjust(int *a, int s, int m); void HeapSort(int *a, int n); int main() { int i, n, m; int *a = NULL; input(a, n); HeapSort(a, n); output(a, n); free(a); return 0; } void input(int *&a, int &n) { int i; scanf("%d", &n); if ((a = (int *)malloc(n * sizeof(int))) == NULL) { printf("不能成功分配内存单元\n"); exit(0); } for (i = 0; i < n; i++) { scanf("%d", &a[i]); } } void output(int *a, int n) { int i; for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } void swap(int &a, int &b) { int t; t = a; a = b; b = t; } void HeapAdjust(int *a, int s, int m) { int j, rc = a[s]; while (2 * s <= m) { j = 2 * s; if (j < m && a[j] < a[j + 1]) j++; if (rc >= a[j]) break; a[s] = a[j]; s = j; } a[s] = rc; } void HeapSort(int *a, int n) { int i; for (i = n / 2; i > 0; --i) { HeapAdjust(a, i, n); } for (i = n - 1; i > 0; --i) { swap(a[0], a[i]); HeapAdjust(a, 0, i - 1); } }这样,就完成了堆排序算法的实现,并且能够输出排序后的结果。