Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3234012
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8557
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: C/C++

2012-12-08 23:41:40

    不多说了功力深厚的筒子就无情地鄙视我吧。基本的数据结构,很多地方可能会用到。比如按层遍历二叉树,就需要用到队列的东西。反倒是那写比较高深的数据结构不太常用,比如伸展树,我在工作中真没碰到。这两天无法静心学习其他的东西,就写写数据结构的代码吧。

queue.h   
  1. #ifndef __QUEUE_H__
  2. #define __QUEUE_H__

  3. typedef struct Queue_node
  4. {
  5.     void *data;
  6.     struct Queue_node* next;
  7. }Queue_node;

  8. typedef struct Queue
  9. {
  10.     struct Queue_node * head;
  11.     struct Queue_node *tail;
  12. }Queue;


  13. int queue_init(struct Queue* self);
  14. int queue_empty(struct Queue* self);
  15. int queue_put(struct Queue* self, void* data);
  16. void* queue_get(struct Queue* self);

  17. #endif

queue.c
  1. #include "queue.h"
  2. #include <stdlib.h>
  3. #include <assert.h>
  4. int queue_init(struct Queue* self)
  5. {
  6.     if(self == NULL)
  7.         return -1;
  8.     else
  9.     {
  10.         self->head = NULL;
  11.         self->tail = NULL;
  12.     }
  13.     return 0;
  14. }

  15. int queue_empty(struct Queue* self)
  16. {
  17.     return self->head == NULL;
  18. }

  19. int queue_put(struct Queue* self, void* data)
  20. {
  21.     assert(self != NULL && data != NULL);
  22.     struct Queue_node *newnode = (struct Queue_node*)malloc(sizeof(Queue_node));
  23.     if(newnode == NULL)
  24.         return -1;
  25.     else
  26.     {
  27.         newnode->data = data;
  28.         newnode->next = NULL;
  29.         if(self->head == NULL)
  30.         {
  31.             self->head = newnode;
  32.             self->tail = newnode;
  33.         }
  34.         else
  35.         {
  36.             self->tail->next = newnode;
  37.             self->tail = newnode;
  38.         }
  39.         return 0;
  40.     }

  41. }

  42. void* queue_get(struct Queue* self)
  43. {
  44.     void* data = NULL;
  45.     if(queue_empty(self) == 1)
  46.         return NULL;
  47.     else
  48.     {
  49.         data = self->head->data;
  50.         struct Queue_node* next = self->head->next;
  51.         free(self->head);
  52.         self->head=next;
  53.         return data;
  54.     }
  55. }

queue_test.c
  1. #include "queue.h"
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <time.h>

  5. int test_queue()
  6. {
  7.     struct Queue queue;
  8.     int ret = queue_init(&queue);
  9.     if(ret < 0)
  10.     {
  11.         fprintf(stderr,"queue init failed\n");
  12.         return -1;
  13.     }
  14.     int data_array[10] = {0};
  15.     int i = 0;
  16.     srand(time(NULL));
  17.     while(i<10)
  18.     {
  19.         data_array[i] = rand()%100;
  20.         fprintf(stdout,"%d\t",data_array[i]);
  21.         ret = queue_put(&queue,&data_array[i]);
  22.         if(ret < 0)
  23.         {
  24.             fprintf(stderr,"put failed\n");
  25.             return -2;
  26.         }
  27.         i++;
  28.     }
  29.     fprintf(stdout,"\n");

  30.     int *p;
  31.     while(queue_empty(&queue)==0)
  32.     {
  33.         p =(int*) queue_get(&queue);
  34.         fprintf(stdout,"%d\t" ,*p);
  35.     }
  36.     fprintf(stdout,"\n");
  37.     return 0;
  38. }

  39. int main()
  40. {
  41.     test_queue();
  42.     return 0;
  43. }


输出:

  1. root@manu:~/code/c/self/queue# ./test
  2. 81 88 66 10 69 97 67 6 37 7
  3. 81 88 66 10 69 97 67 6 37 7

参考文献:
1 算法:C语言实现




阅读(3631) | 评论(7) | 转发(4) |
给主人留下些什么吧!~~

Bean_lee2012-12-11 19:36:06

靠,我就在项目中听说过一次八叉树,你小子来了个256叉树,这个我真没听说过。

wjlkoorey2582012-12-11 19:34:28

Bean_lee兄能不能帮我解释一下256叉树一般适用的情形,优劣啊。前段时间被项目上的256叉树搞晕了,现在还没回过神来

Bean_lee2012-12-10 22:29:14

egmkang: 其实,如果是lock free的queue,用link list还是有一定道理,否则就太不合适了.
link list的优点,跟queue需要的操作都没啥关系,list是快速删除插入,queue要快速pus.....
说的非常对,queue的list 实现会引起cache missing。而数组实现会好很多。
AVL 树是出现比较早的平衡二叉树,而且它提出的旋转来达到平衡的思想启发了很多后来者。所以很多教材都选AVL树来讲平衡二叉树。

egmkang2012-12-10 21:39:15

其实,如果是lock free的queue,用link list还是有一定道理,否则就太不合适了.
link list的优点,跟queue需要的操作都没啥关系,list是快速删除插入,queue要快速push/pop.而且list的cache missing要比array高.

egmkang2012-12-10 21:36:36

Bean_lee: 你说的对,还有数组形式的stack。
呵呵其实基本的应用的多,反而高深的应用的少,我不愿意写AVL树的原因就在于此,没人用这种树,有类似需求的都直接红黑树了。.....
红黑树的效率比AVL树高,但是大学课本上只讲AVL...