注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

饥民2011

一直在搬砖

 
 
 

日志

 
 
 
 

数据结构 - 队列简介 及 1个简单的c语言链式队列代码实现  

2013-04-16 21:24:03|  分类: Data structure |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1. 队列的定义

                 所谓队列(queue)就是一种能实现"先进先出"的一种线性存储结构.

                 跟栈有点类似,  例如栈只有1个出入口, 任何元素进入或者离开栈都必须经过同1个出入口(栈顶), 所以栈能实现"先入后出"的效果.

               

                  队列同样有出入口, 只不过出入口分别位于队列的两端, 元素只能从入口进入队列,  而且只能从另一端的出口离开队列, 在队列中间里的元素是不允许插入或删除操作的, 所以先进入队列的元素肯定会比后进入的元素先离开队列, 就是所谓的"先进先出"了.


                  举个例子, 例如现实中排队买票就是1个队列,  1个人只能从队伍的尾部进入队列, 从队伍的前部(买票窗口)买票离开队列, 中间插队是不允许的.


2. 队列的分类

                   就如栈可以分成动态栈和静态栈一样.

                   队列也可以分成静态队列和链式队列.

               

                   所谓静态队列就是用数组(连续内存) 作为内核的队列.

                   而链式队列就是以链表为内核的队列了.

 

                   下面会简介链式队列, 而且是单链表的链式队列.


3. 链式队列(单链表)的大概结构

 画个图便于理解:



如上图,  我们会将1个单链表的首节点作为队列的前端(front), 就是队列的出口啦.    而会将单链表的尾节点作为队列的尾端(Rear), 就是队列的入口.


而我们会定义两个指针,  Front指针来存放队列出口元素的地址,   Rear指针来存放队列入口元素的地址.


之所以这样设定是为了方便出列操作,  如上图,  当节点0 要出列时, 0 作为1个首节点,  出列后Front指针就必须指向出列元素的下1个节点地址(节点1),  而这个地址恰好保存于节点0的尾部指针中啊.     假如在单链表的尾部出列, 如上图, 加入节点4出列后, Front就必须指向节点3,  但是节点3的尾部指针指向节点4,  而根据节点4是找不到节点4上1个元素的地址的, 只能遍历链表啊.


而在尾节点入列同样方便, 如上图,  当节点4入列时, 只需要将队列原来的入口元素(Rear指针)的尾部地址指向入列节点, 然后 Rear指针指向这个新的入口元素!


上面就是1个最基本的链式队列结构, 但是有1个弊端, 就是当这个队列为空(所有元素出列后), 这个链表就消失了, 再入列时就无从下手!


所以实际操作我们会给在队列的前部(出口)加上1个不存放实际数据的头节点, 做为列表的出口, 这个头节点指向队列的真正的出口元素(pHead->pnext). 这样当队列所有元素出列后, 队列的Rear指针就手动指向不存放实际数据的头节点, 这样的话我们会认为这个队列是空队列.(pHead == pRear)


如下图:


4. 一个简单的链式队列的C语言代码实现

4.1 首先就是编写1个头文件

在这个头文件里我们会定义两个结构体, 
1个是对应于队列的元素的, 所以这个结构体具有1个pNext 指针成员。
另1个结构体是对应于链式队列的,  具有4个成员, 分别是:
pHead  头结点地址
pRear   存放入口元素的地址
len         存放链表的长度信息
is_inited 用于判断链表结构体是否被初始化(里面的指针成员是否野指针)


此外, 这个头文件也会生命一些算法函数, 别的文件引用这个头文件, 就可以使用这些函数了。

代码如下:
  1. /*  
  2.  * linkqueue1.h  
  3.  *  
  4.  *  Created on: 2013-4-15  
  5.  *      Author: gateman  
  6.  */  
  7. #include <bool_me.h>  
  8. #ifndef __LINKQUEUE1_H_  
  9. #define __LINKQUEUE1_H_  
  10.   
  11.     struct person_linkqueue1{  
  12.         int id;  
  13.         char name[16];  
  14.         struct person_linkqueue1 * pNext;  
  15.     };  
  16.   
  17.     typedef struct person_linkqueue1 PERSON_LQ;  
  18.   
  19.     struct linkqueue1_person{  
  20.         PERSON_LQ * pHead;  
  21.         PERSON_LQ * pRear;  
  22.         int len;  
  23.         BOOL is_inited;  
  24.     };  
  25.   
  26.     typedef struct linkqueue1_person LQPERSON;  
  27.   
  28.     //create a new node with dynamic memory assigned  
  29.     PERSON_LQ * person_lq_new(int id, char * pname);  
  30.   
  31.     //print the information of a node  
  32.     void person_lq_print(PERSON_LQ * pnode);  
  33.   
  34.     //create a stuck with dynamic linklist  
  35.     LQPERSON * lqperson_new(void);  
  36.   
  37.     //judge whether the link_queue is empty  
  38.     BOOL lq_is_empty(LQPERSON * pLq);  
  39.   
  40.     //add an element into the queue  
  41.     void lq_Enqueue(LQPERSON * pLq, PERSON_LQ * pnode);  
  42.   
  43.     //remove an element from the queue, and get the element  
  44.     BOOL lq_Dequeue(LQPERSON * pLq, PERSON_LQ ** pOutput);  
  45.   
  46.     //traverse the queue to print all the elements  
  47.     void lq_print(LQPERSON * pLq);  
  48.   
  49.     //put out and free all the elements from the queue  
  50.     void lq_clear(LQPERSON * pLq);  
  51.   
  52.     //free all the elements, and free the queue  
  53.     void lq_free(LQPERSON * pLq);  
  54.   
  55. #endif /* LINKQUEUE1_H_ */  


下面会用列出上面声明的函数定义代码.



4.2 建立1个新节点(元素)函数 PERSON_LQ * person_lq_new(int id, char * pname)

这个函数作用就是动态分配1个新的内存给1个节点结构体, 既然是动态分配的, 那么这个节点很容易被其他函数访问。 
而且必要时也可以手动释放。

逻辑步骤如下:
1. 新建1个节点类型指针.  并动态分配一段内存.
2. 如果分配不成功,  退出程序
3. 设置参数传入的成员值(id, name)
4. 尾部指针设成NULL
5. 返回这个指针



代码如下:
  1. PERSON_LQ * person_lq_new(int id, char * pname){  
  2.     PERSON_LQ * pnode = (PERSON_LQ *)malloc(sizeof(PERSON_LQ));  
  3.     if (NULL == pnode){  
  4.         base_error("fail to assign memory to a new node!");  
  5.     }  
  6.   
  7.     pnode->id = id;  
  8.     strncpy(pnode->name, pname+0, 15);  
  9.     pnode->pNext=NULL;  
  10.     return pnode;  
  11. }  



4.3 打印1个节点的信息 void person_lq_print(PERSON_LQ * pnode)

这个不讲解了, 很简单

代码如下:

  1. //print the information of a node  
  2. void person_lq_print(PERSON_LQ * pnode){  
  3.     printf("id is %d, name is %s\n",pnode->id, pnode->name);  
  4. }  


4.4 新建并初始化1个链式队列 LQPERSON * lqperson_new(void)

这个函数就是动态分配1段内存给1个链式队列, 并执行初始化, 最后返回这个结构体指针


步骤:

1. 新建1个链式队列结构体指针, 并动态分配1个内存

2. 若分配内存失败, 退出程序

3. 初始化链式队列的 pHead 头节点成员( 利用上面的 person_lq_new函数)

4. pRear 成员指向 pHead (代表空队列)

5. len长度设为0

6. is_inited 成员设为TRUE

7. 返回链式队列结构体指针


代码如下:

  1. //create a stuck with dynamic linklist  
  2. LQPERSON * lqperson_new(void){  
  3.     LQPERSON * pLq = (LQPERSON *)malloc(sizeof(LQPERSON));  
  4.     if (NULL == pLq){  
  5.         base_error("fail to assign memory to a linkqueue!");  
  6.     }  
  7.   
  8.     pLq->pHead = person_lq_new(-1,"Head");  
  9.     pLq->pRear = pLq->pHead; //empty queue;  
  10.     pLq->len=0;  
  11.     pLq->is_inited = TRUE;  
  12.     return pLq;  
  13. }  

4.5 判断链式队列是否为空  BOOL lq_is_empty(LQPERSON * pLq)

这个很简单, 判断 pRear 是否指向 pHead就ok了, 当然判断len ==0 也可以..

代码如下:

  1. //judge whether the link_queue is empty  
  2. BOOL lq_is_empty(LQPERSON * pLq){  
  3.     if (TRUE != pLq->is_inited){  
  4.         base_error("the linkqueue is not initailed yet!");  
  5.     }  
  6.   
  7.     if (pLq->pRear == pLq->pHead){  
  8.         return TRUE;  
  9.     }  
  10.   
  11.     return FALSE;  
  12. }  


4.6 入列函数 void lq_Enqueue(LQPERSON * pLq, PERSON_LQ * pnode)

作用就是把1个节点元素放入队列, 逻辑并不复杂. 上面图解过了嘛

步骤:

1.入口元素地址 pRear的尾部指针指向这个入列元素

2,pRear 指向 这个入列元素, 这个入列元素就成为新的入口元素了

3. 这个入列元素的尾部指针指向NULL

4. 链表长度len+1


代码如下:

  1. //add an element into the queue  
  2. void lq_Enqueue(LQPERSON * pLq, PERSON_LQ * pnode){  
  3.     if (TRUE != pLq->is_inited){  
  4.         base_error("the linkqueue is not initailed yet!");  
  5.     }  
  6.   
  7.     pLq->pRear->pNext = pnode;  
  8.     pLq->pRear = pnode;  
  9.     pnode->pNext=NULL;  
  10.   
  11.     pLq->len++;  
  12. }  


4.7 出列函数 BOOL lq_Dequeue(LQPERSON * pLQ, PERSON_LQ ** pOutput)

注意这个函数, 返回值是BOOL 也就是出列函数有可能失败, 因为如果1个空队列, 出列就肯定失败嘛

而且接受1个以地址传递的指针, 也就是指针的指针了,  用于接受出列元素的地址.


逻辑如下:

1. 判断是否为空队列, 否则返回FALSE

2.  pOutput 指向出列元素(pHead 下1个元素)

3. pHead 头节点的尾部指针指向出列元素的下1个元素,  那个就是新的出口元素, 也就是说下次出列就轮到它啊

4. 如果出列元素是最后1个元素, 出列后 pRear 指向pHead, 代表成为1个空队列了

5. 队列长度len -1

6. 返回TRUE


代码如下:

  1. //remove an element from the queue, and get the element  
  2. BOOL lq_Dequeue(LQPERSON * pLq, PERSON_LQ ** pOutput){  
  3.     if (TRUE != pLq->is_inited){  
  4.         base_error("the linkqueue is not initailed yet!");  
  5.     }  
  6.   
  7.     if (TRUE == lq_is_empty(pLq)){  
  8.         printf("the linkqueue is empty!\n");  
  9.         return FALSE;  
  10.     }  
  11.   
  12.     *pOutput = pLq->pHead->pNext;  
  13.     pLq->pHead->pNext = (*pOutput)->pNext;  
  14.   
  15.     //if it's the last one  
  16.     if(pLq->pRear == *pOutput){  
  17.         pLq->pRear = pLq->pHead; //empty  
  18.     }  
  19.   
  20.     pLq->len--;  
  21.     return TRUE;  
  22. }  

4.8 打印1个队列函数 lq_print(LQPERSON * pLq)

这个函数作用就是从出口开始打印队列的存放有效数据的函数,  就是从Front 到 Rear啦.

相当于1个遍历,

代码如下:

  1. //traverse the queue to print all the elements  
  2. void lq_print(LQPERSON * pLq){  
  3.     if (TRUE != pLq->is_inited){  
  4.         base_error("the linkqueue is not initailed yet!");  
  5.     }  
  6.   
  7.     if (TRUE == lq_is_empty(pLq)){  
  8.         printf("the linkqueue is empty!\n");  
  9.     }  
  10.   
  11.     PERSON_LQ * pnode = pLq->pHead;  
  12.     while(NULL != pnode->pNext){  
  13.         pnode=pnode->pNext;  
  14.         person_lq_print(pnode);  
  15.     }  
  16. }  


4.9 删除所有队列元素函数 lq_clear

当然, pRear 指向 pHead, 这样这个队列马上就是1个空队列, 但是这样里面的节点就容易丢失, 也就是内存泄露啊

所以我们要逐个地释放里面节点的内存, 然后才把 pRear 指向 pHead

  1. //put out and free all the elements from the queue  
  2. void lq_clear(LQPERSON * pLq){  
  3.     if (TRUE != pLq->is_inited){  
  4.         base_error("the linkqueue is not initailed yet!");  
  5.     }  
  6.   
  7.     PERSON_LQ * pnode = pLq->pHead;  
  8.     PERSON_LQ * pnext = pnode->pNext;  
  9.     while(NULL != pnext){  
  10.         pnode = pnext;  
  11.         pnext = pnode->pNext;  
  12.         free(pnode);  
  13.     }  
  14.   
  15.     pLq->pHead->pNext=NULL;  
  16.     pLq->pRear = pLq->pHead;  
  17.     pLq->len=0;  
  18. }  

4.9 销毁队列函数 lq_free

这个更简单, 首先执行清空.

然后把头节点的内存释放

最后把队列结构体释放

代码如下:

  1. //free all the elements, and free the queue  
  2. void lq_free(LQPERSON * pLq){  
  3.     lq_clear(pLq);  
  4.     free(pLq->pHead);  
  5.     free(pLq);  
  6. }  



4.10 写个程序测试上面的函数

纯粹测试下啦:

代码如下:

  1. int linkqueue1(){  
  2.     PERSON_LQ * pnode = person_lq_new(1,"JasonPoon111212121212");  
  3.     person_lq_print(pnode);  
  4.     free(pnode);  
  5.   
  6.     LQPERSON * plq1 = lqperson_new();  
  7.     lq_Enqueue(plq1, person_lq_new(1,"Jason"));  
  8.     lq_Enqueue(plq1, person_lq_new(2,"Cindy"));  
  9.     lq_Enqueue(plq1, person_lq_new(3,"Fiana"));  
  10.     lq_Enqueue(plq1, person_lq_new(4,"Gateman"));  
  11.   
  12.     lq_print(plq1);  
  13.   
  14.     int i=0;  
  15.     int j=plq1->len-1;  
  16.     for (i=0; i < j; i++){  
  17.         lq_Dequeue(plq1,&pnode);  
  18.         printf("the out node is\n");  
  19.         person_lq_print(pnode);  
  20.         printf("\n");  
  21.         free(pnode);  
  22.     }  
  23.   
  24.     lq_print(plq1);  
  25.     lq_Dequeue(plq1,&pnode);  
  26.     printf("the out node is\n");  
  27.     person_lq_print(pnode);  
  28.     printf("\n");  
  29.     free(pnode);  
  30.   
  31.     lq_print(plq1);  
  32.     lq_Enqueue(plq1, person_lq_new(1,"Jason"));  
  33.     lq_Enqueue(plq1, person_lq_new(2,"Cindy"));  
  34.     lq_Enqueue(plq1, person_lq_new(3,"Fiana"));  
  35.     lq_Enqueue(plq1, person_lq_new(4,"Gateman"));  
  36.   
  37.   
  38.     lq_print(plq1);  
  39.   
  40.     printf("now clear the linkqueuei!\n");  
  41.     lq_clear(plq1);  
  42.     lq_print(plq1);  
  43.   
  44.     lq_free(plq1);  
  45.   
  46.     printf("linkq1 done\n");  
  47.     return 0;  
  48. }  


输出:




  评论这张
 
阅读(448)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017