Chinaunix首页 | 论坛 | 博客
  • 博客访问: 76100
  • 博文数量: 57
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 10
  • 用 户 组: 普通用户
  • 注册时间: 2013-08-11 08:58
文章分类
文章存档

2013年(57)

我的朋友

分类: C/C++

2013-08-11 09:01:46

原文地址:数据结构之队列 作者:Bean_lee

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

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语言实现




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