10_8.c

数据结构中查询遍历算法等的实例

/* ======================================== */
/*    程序实例: 10_8.c                      */
/*    堆排序法                            */
/* ======================================== */
#include <stdlib.h>

/* ---------------------------------------- */
/*  建立堆                                */
/* ---------------------------------------- */
void adjust_heap(int *heap,int root,int len)
{
   int done;                      /* 是否可结束的变量     */
   int j;
   int temp;

   j = 2 * root;                  /* 子结点指针           */
   temp = heap[root];             /* 堆的根值           */
   done = 0;                      /* 建立变量             */
   while ( j <= len && !done )    /* 主循环              */
   {
         if ( j < len )           /* 找最大的子结点       */
            if ( heap[j] < heap[j+1] )
               j++;               /* 下一结点             */
         if ( temp >= heap[j] )   /* 比较树根值           */
            done = 1;             /* 结束                 */
         else
         {
            heap[j/2] = heap[j];  /* 父结点是目前结点     */
            j = 2 * j;            /* 其子结点             */
         }
   }
   heap[j/2] = temp;              /* 父结点为根值         */
}

/* ---------------------------------------- */
/*  堆排序                                */
/* ---------------------------------------- */
void heap(int *heap,int len)
{
   int i,j,temp;

   for ( i = ( len / 2 ); i >= 1; i-- ) /*将二叉树转成堆*/
      adjust_heap(heap,i,len);
   printf("\n堆中数据: ");
   for ( j = 1; j < 10; j++ )     /* 输出堆的内容       */
      printf("[%d]",heap[j]);
   printf("\n");                  /* 换行                 */
   for ( i = len - 1; i >= 1; i-- )   /* 堆排序主循环   */
   {
      temp = heap[i+1];           /* 交换最后元素         */
      heap[i+1] = heap[1];
      heap[1] = temp;
      adjust_heap(heap,1,i);      /* 重建堆             */
      printf("\n处理内容: ");
      for ( j = 1; j < 10; j++ )  /* 输出处理内容         */
         printf("[%d]",heap[j]);
   }
}

/* ---------------------------------------- */
/*  主程序: 将数组数据用堆排序法来排序.   */
/* ---------------------------------------- */
void main()
{
   /* 二叉树结点数据 */
   int data[10] = { 0, 5, 6, 4, 8, 2, 3, 7, 1, 9 };
   int i;

   printf("二叉树的内容: ");
   for ( i = 1; i < 10; i++ )     /* 输出二叉树内容       */
      printf("[%d]",data[i]);
   heap(data,9);                  /* 堆排序法           */
   printf("\n\n输出排序结果: ");
   for ( i = 1; i < 10; i++ )     /* 输出最后内容         */
      printf("[%d]",data[i]);
   printf("\n");                  /* 换行                 */
}