Chinaunix首页 | 论坛 | 博客
  • 博客访问: 563877
  • 博文数量: 136
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1669
  • 用 户 组: 普通用户
  • 注册时间: 2013-07-09 16:16
个人简介

围城

文章分类

全部博文(136)

文章存档

2019年(3)

2018年(7)

2017年(14)

2016年(15)

2015年(35)

2014年(9)

2013年(53)

我的朋友

分类: C/C++

2014-06-15 15:49:47

队列是一种先进先出的线性表,也是一种操作受限的线性表,只允许在表的头部删除元素和尾部添加元素。队列有链式表示和顺序表示。队列的链式表示由于在表头和表尾操作,需要两个指针分别指向对头和队尾。空的链式队列判决条件为对头指针和队尾指针是否指向同一个结点(头节点)。
  • 链式队列的存储结构
  1. #define OK           1  
  2. #define NULL_QUEUE       0  
  3. #define ERROR           -1  
  4.   
  5. typedef struct qnode{  
  6.     elemtype        data;  
  7.     struct qnode        *next;  
  8. }lqnode, *linkq;  
  9.   
  10. typedef struct {  
  11.     linkq       front;  
  12.     linkq       rear;  
  13. }linkqueue;  
  • 初始化链式队列
  1. int init_linkqueue(linkqueue *lq)  
  2. {  
  3.     lq->front = (linkq)malloc(sizeof(lqnode));  
  4.     if (!lq->front)  
  5.         return ERROR;  
  6.   
  7.     lq->rear = lq->front;  
  8.     lq->front->next = NULL;  
  9.   
  10.     return OK;  
  11. }  
申请一个头结点,将地址赋给头指针和尾指针,next域置空,类似于链表初始化。
  • 元素进队列
  1. int in_linkqueue(linkqueue *lq, elemtype e)  
  2. {  
  3.     linkq       p;  
  4.   
  5.     p = (linkq)malloc(sizeof(lqnode));  
  6.     if (!p)  
  7.         return ERROR;  
  8.   
  9.     p->data = e;  
  10.     p->next = NULL;  
  11.     lq->rear->next = p;  
  12.     lq->rear = p;  
  13.   
  14.     return OK;  
  15. }  
链队列元素进队将元素添加在队列的尾部,类似于线性表尾插法添加元素。
  • 元素出队列
  1. int out_linkqueue(linkqueue *lq, elemtype *e)  
  2. {  
  3.     linkq       p;  
  4.   
  5.     if (lq->front == lq->rear)  
  6.         return NULL_QUEUE;  
  7.   
  8.     p = lq->front->next;  
  9.     *e = p->data;  
  10.     lq->front->next = p->next;  
  11.     if (lq->rear == p)  
  12.         lq->rear = lq->front;  
  13.     free(p);  
  14.   
  15.     return OK;  
  16. }  
链队列元素出队列将队首元素删除,此时需注意一点,在删除最后一元素是队尾指针也被删除了,应当重新为队尾指针赋值。
  • 取得队列长度
  1. int get_queue_len(linkqueue lq)  
  2. {  
  3.     int     i = 0;  
  4.     linkq       p = lq.front;  
  5.   
  6.     while (p != lq.rear) {  
  7.         ++i;  
  8.         p = p->next;  
  9.     }  
  10.   
  11.     return i;  
  12. }  
  • 总结
链队列的操作即是单链表操作的特殊情况,只需修改头指针和尾指针即可。
阅读(2706) | 评论(0) | 转发(0) |
0

上一篇:领导成长心得

下一篇:linux source命令

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册