Chinaunix首页 | 论坛 | 博客

mrkeywang的ChinaUnix博客

首页　| 　博文目录　| 　关于我

mrkeywang

  • 博客访问： 12934
  • 博文数量： 16
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 170
  • 用 户 组： 普通用户
  • 注册时间： 2013-05-08 11:44
文章分类

全部博文（16）

文章存档

2014年（16）

我的朋友
最近访客
推荐博文
相关博文
置换选择

分类： C/C++

2014-09-06 22:18:51


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <stdbool.h>
  4. #include <stdlib.h>
  5. #include <limits.h>

  7. #include <unistd.h>
  8. #define ENDF INT_MIN
  9. #define BUF_LEN 20
  10. #define SUM 100
  11. /*模拟输出*/
  12. int gettop(int *a)
  13. {
  14.         printf("%d ", a[1]);
  15.         return a[1];
  16. }
  17. /*模拟输入*/
  18. int getnext()
  19. {
  20.         static int next = 0;
  21.         if (next < SUM) {
  22.                 next ++;
  23.                 return rand() % 100;
  24.         } else
  25.                 return ENDF;
  26. }
  27. /*调堆*/
  28. void adjust(int a[], int n, int i)
  29. {
  30.         int tn = n / 2;
  31.         while (i <= tn) {
  32.                 int next = i * 2;
  33.                 if (next + 1 <= n && a[next+1] < a[next])
  34.                         next ++;
  35.                 if (a[next] < a[i]) {
  36.                         int tmp = a[next];
  37.                         a[next] = a[i];
  38.                         a[i] = tmp;

  40.                         i = next;
  41.                 } else
  42.                         break;
  43.         }
  44. }
  45. /*建堆*/
  46. void buildheap(int a[], int n)
  47. {
  48.         for (int i = n/2; i >= 1; i--)
  49.                 adjust(a, n, i);
  50. }
  51. int main()
  52. {
  53.         int b[21];
  54.         int count = 0;
  55.         for (int i=1; i<=20; i++) {
  56.                 b[i] = rand() % 100;
  57.         }
  58.         srand(time(NULL));


  61.         buildheap(b, BUF_LEN);
  62.         int index = BUF_LEN;
  63.         int last = INT_MIN;
  64.         while (true) {
  65.                 last = gettop(b);
  66.                 count++;
  67.                 int next = getnext();
  68.                 if (next == ENDF) {
  69.                         break;
  70.                 } else if (next < last) {
  71.                         if (index == 1) {
  72.                                 /*产生一个顺串*/
  73.                                 printf("\n");
  74.                                 b[1] = next;
  75.                                 buildheap(b, BUF_LEN);
  76.                                 index = BUF_LEN;
  77.                                 last = INT_MIN;
  78.                         } else {
  79.                                 b[1] = b[index];
  80.                                 b[index] = next;
  81.                                 index--;
  82.                                 adjust(b, index, 1);
  83.                         }
  84.                 } else {
  85.                         b[1] = next;
  86.                         adjust(b, index, 1);
  87.                 }
  88.         }
  89.  b[1] = b[index];
  90.         int i = index - 1;
  91.         while (i>0) {
  92.                 gettop(b);
  93.                 count++;
  94.                 b[1] = b[i];
  95.                 i--;
  96.                 adjust(b, i, 1);
  97.         }
  98.         /*最后一个顺串*/
  99.         putchar('\n');
  100.         int *tmp = b + index;
  101.         i = BUF_LEN - index;
  102.         buildheap(tmp, i);
  103.         while (i>0) {
  104.                 gettop(tmp);
  105.                 count++;
  106.                 tmp[1] = tmp[i];
  107.                 i--;
  108.                 adjust(tmp, i, 1);
  109.         }
  110.         printf("\n%d", count);
  111.         return 0;
  112. }

阅读(142) | 评论(0) | 转发(0) |
0

上一篇：avl2

下一篇：二项树

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6