Chinaunix首页 | 论坛 | 博客
  • 博客访问: 7513399
  • 博文数量: 961
  • 博客积分: 15795
  • 博客等级: 上将
  • 技术积分: 16612
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-07 14:23
文章分类

全部博文(961)

文章存档

2016年(1)

2015年(61)

2014年(41)

2013年(51)

2012年(235)

2011年(391)

2010年(181)

分类: 嵌入式

2011-02-28 08:54:32

  1. /*链式存储结构体类型定义*/
  2. typedef struct node {
  3.     int data;
  4.     struct node *left;
  5.     struct node *right;
  6. } BTree;

  7. /*链式存储二叉树构建函数*/
  8. int BTreeCreate(BTree *tp)
  9. {
  10.     int x;
  11.     scanf("%d",&x);
  12.     if(x<0)
  13.     {
  14.         tp = NULL;
  15.         return 0;
  16.     }
  17.     tp = (BTree *)malloc(sizeof(BTree));
  18.     if(tp == NULL)
  19.         return FALSE;
  20.     tp->data = x;
  21.     BTreeCreate(tp->letf);
  22.     BTreeCreate(tp->right);
  23.     return OK:
  24. }

  25. /*前序遍历 非递归函数*/
  26. void PreOrder(BTree *tp)
  27. {
  28.     BTree *p;
  29.     BTree *stack[MAXIZE];
  30.     int top = -1;
  31.     if(tp == NULL)
  32.         return ;
  33.     else
  34.     {
  35.         top++;
  36.         stack[top] = tp;
  37.         while(top>-1)
  38.         {
  39.             p = stack(top);
  40.             top--;
  41.             printf("%d\t",p->data);
  42.             if(p->right!=NULL)
  43.             {
  44.                 top++;
  45.                 stack[top] = p->right;
  46.             }
  47.             if(p->left!=NULL)
  48.             {
  49.                 top++;
  50.                 stack[top] = p->left;
  51.             }        
  52.         }
  53.         printf("\n")
  54.     }
  55. }

  56. /*前序遍历 递归函数*/
  57. void PreOrder(BTree *tp)
  58. {
  59.     if(tp == NULL)
  60.         return ;
  61.     else
  62.     {
  63.         printf("%d\t",tp->data);
  64.         PreOrder(tp->left);
  65.         PreOrder(tp->right);
  66.     }
  67. }

  68. /*中序遍历 递归函数*/
  69. void MidOrder(BTree *tp)
  70. {
  71.     if(tp == NULL)
  72.         return ;
  73.     else
  74.     {        
  75.         PreOrder(tp->left);
  76.         printf("%d\t",tp->data);
  77.         PreOrder(tp->right);
  78.     }
  79. }

  80. /*后序遍历 递归函数*/
  81. void MidOrder(BTree *tp)
  82. {
  83.     if(tp == NULL)
  84.         return ;
  85.     else
  86.     {        
  87.         PreOrder(tp->left);
  88.         PreOrder(tp->right);
  89.         printf("%d\t",tp->data);        
  90.     }
  91. }


  92. /* 顺序查找*/
  93. #include <stdlib.h>
  94. #include <stdio.h>
  95. #define N 10

  96. typedef struct node {                        /* 定义线性表的类型 */
  97.   int data[N];
  98.   int length;
  99. } SeqList;
  100. int sq_search(SeqList *p, int k);                /* 声明顺序查找函数 */

  101. int main()
  102. {
  103.   SeqList sl;                             /* 定义线性表 */
  104.   int i, j;
  105.   int k;
  106.   printf("input the elements:\n");
  107.   for(i=0; i<N; i++)
  108.   {
  109.     scanf("%d", &(sl.data[i]));                /* 初始化线性表的各数据元素 */
  110.   }
  111.   sl.length = N;                         /* 初始化线性表的长度 */
  112.   printf("input the key:\n");
  113.   scanf("%d", &k);                         /* 输入要查找的关键字 */
  114.   j = sq_search(&sl, k);                     /* 调用顺序查找函数 */
  115.   printf("-------------------\n");
  116.   if(j >= 0)
  117.   {
  118.     printf("found : data[%d]\n", j);             /* 查找成功 */
  119.   }
  120.   else
  121.   {
  122.     printf("%d is not been found.\n", k);         /* 查找失败 */
  123.   }
  124.   return 0;
  125. }

  126. int sq_search(SeqList *p, int k)             /* 定义顺序查找函数 */
  127. {
  128.   int i = 0;
  129.   int j = -1;
  130.   while(i < N)                            /* 逐个扫描线性表中的所有数据元素 */
  131.   {
  132.     if(p->data[i] == k)
  133.     {
  134.       j = i;                            /* 如果找到,将数据元素所在的位置赋给变量j */
  135.       break;
  136.     }
  137.     i++;
  138.   }
  139.   return j;
  140. }


  141. /* 二分查找 */
  142. #include <stdlib.h>
  143. #include <stdio.h>
  144. #define N 9
  145. typedef struct node {                        /* 定义线性表的类型 */
  146.   int data[N];
  147.   int length;
  148. } SeqList;
  149. int bi_search(SeqList *p, int k);                /* 声明二分查找函数 */

  150. int main()
  151. {
  152.   SeqList sl;                             /* 定义线性表 */
  153.   int i, j, k, t;
  154.   printf("input the elements in ascendant order:\n");
  155.   i = 0;
  156.   scanf("%d", &(sl.data[i]));
  157.   while(i < N-1)                         /* 初始化线性表的各数据元素 */
  158.   {
  159.     scanf("%d", &t);                     /* 输入数据元素的值 */
  160.     if(t > sl.data[i])                         /* 检查输入的数据元素是否满足升序排列要求 */
  161.     {
  162.       i++;
  163.       sl.data[i] = t;                        /* 如果满足要求,进行赋值操作 */
  164.     }
  165.     else
  166.     {
  167.       printf("errer, must bigger than %d\n ", sl.data[i]);        /* 如果不满足要求,输出错误提示信息 */
  168.     }
  169.   }
  170.   sl.length = N;                         /* 初始化线性表的长度 */
  171.   printf("input the key:\n");
  172.   scanf("%d", &k);                         /* 输入要查找的关键字 */
  173.   j = bi_search(&sl, k);                     /* 调用二分查找函数 */
  174.   printf("-------------------\n");
  175.   if(j >= 0)
  176.   {
  177.     printf("found : data[%d]\n", j);             /* 查找成功 */
  178.   }
  179.   else
  180.   {
  181.     printf("%d is not been found.\n", k);         /* 查找失败 */
  182.   }
  183.   return 0;
  184. }

  185. int bi_search(SeqList *p, int k)                 /* 定义二分查找函数 */
  186. {
  187.   int low = 0;
  188.   int high = p-> length;
  189.   int mid;
  190.   while(low <= high)
  191.   {
  192.     mid = (low+high)/2;
  193.     if(p->data[mid] == k)                    /* 查找成功 */
  194.       return mid;
  195.     else if(p->data[mid] > k)                /* 中间位置的数据元素大于关键字 */
  196.       high = mid-1;
  197.     else                                /* 中间位置的数据元素小于关键字 */
  198.       low = mid+1;
  199.   }
  200.   return -1;
  201. }
阅读(1839) | 评论(0) | 转发(2) |
0

上一篇:冒泡排序

下一篇:队列

给主人留下些什么吧!~~