Skip to content
The Chat Archive
gpt-3.5-turbo-0301· OpenAI WildChat-4.8M (AI2)

#include <stdio.h> #include<stdlib.h> #include<time.h> void input(int &a,int & n); void…

  1. 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 **********/问题是什么?

  2. Assistant

    代码中的HeapAdjust函数只是将堆调整为大根堆,但是没有完成整个堆排序的过程,缺少将根节点和末尾节点调换再重新调整的步骤。同时,代码中也没有调用output函数输出排序后的结果。

  3. User

    怎么改?

  4. 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);
        }
    }
    

    这样,就完成了堆排序算法的实现,并且能够输出排序后的结果。