• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C~链式队列与循环队列

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

      此处的链式与循环队列可以应用于BFS和树的层序遍历。下面是对其结构和基本操作的程序描述。

1、循环队列

    解决循环队列的队空和队满的方法:

    [1].增加一个参数count,用来记录数组中当前元素的个数;

    [2].为避免队空和满两状态混淆,少用一个存储空间,也就是数组最后一个存数空间不用,(rear+1)% QSIZE= front 时, 队满;

       a)判断是否为空队列:front==rearb)判断队列是否已满:front=(rear+1)%size 

 1 typedef struct{      //队列结构定义
 2     int front;
 3     int rear;
 4     int count;  //队列元素计数
 5     int key[QSIZE];
 6 }BFSQueue;
 7 
 8 void InitBFSQueue(BFSQueue *BFSQ)  //队列初始化
 9 {
10     BFSQ->front=0;  //front指向队列第一个元素
11     BFSQ->rear=0;   //rear指向队列中下一个空位
12     BFSQ->count=0;
13 }
14 int EmptyBFSQueue(BFSQueue *BFSQ) //
15 {
16     return BFSQ->count==0;
17 }
18 int FullBFSQueue(BFSQueue *BFSQ)  //
19 {
20     return BFSQ->count==QSIZE;
21 }
22 
23 void AddBFSQueue(BFSQueue *BFSQ,int num)  //插入
24 {
25     if(!FullBFSQueue(BFSQ))
26     {
27         BFSQ->count++;
28         BFSQ->key[BFSQ->rear]=num;
29         BFSQ->rear=(BFSQ->rear+1) % QSIZE;
30     }
31 }
32 
33 int DelBFSQueue(BFSQueue *BFSQ)  //删除
34 {
35     int temp;
36     if(!EmptyBFSQueue(BFSQ))
37     {
38         BFSQ->count--;
39         temp=BFSQ->key[BFSQ->front];
40         BFSQ->front=(BFSQ->front+1) % QSIZE;
41         return temp;
42     }
43     else
44         return NULL;
45 }
46 /******************************************************************/

2、链式队列


 1 typedef struct QNode{  // 队列元素结构  
 2     int key;
 3     struct QNode *next;
 4 }QNode;
 5 typedef struct{  // 队列结构 
 6     QNode *front;
 7     QNode *rear;
 8     int count;
 9 }BFSQueue;
10 
11 void InitBFSQueue(BFSQueue *BFSQ)  //队列初始化
12 {
13     BFSQ->front=NULL;  
14     BFSQ->rear=NULL; 
15     BFSQ->count=0;
16 }
17 int EmptyBFSQueue(BFSQueue *BFSQ) //
18 {
19     return BFSQ->count==0;
20 }
21 
22 void AddBFSQueue(BFSQueue *BFSQ,int num)  //插入
23 {
24     QNode *np=(QNode *)malloc(sizeof(QNode));
25     np->key=num;
26     np->next=NULL;
27       //BFSQ->count++;
28 
29     if(!EmptyBFSQueue(BFSQ))  // 队列非空
30     {        
31         BFSQ->rear->next=np;
32         BFSQ->rear=np;
33     }
34     else                      // 队列空
35     {
36         BFSQ->rear=np;
37         BFSQ->front=np;
38     }
39     BFSQ->count++;
40 }
41 int DelBFSQueue(BFSQueue *BFSQ)  //删除
42 {
43     int temp;
44     QNode *tp=(QNode *)malloc(sizeof(QNode));
45     if(!EmptyBFSQueue(BFSQ)) //队列非空
46     {
47           //BFSQ->count--;  //////注意,必须在队列判定之后增加或减小count的值///////
48         tp=BFSQ->front;
49         temp=tp->key;
50         if(BFSQ->count==1)  //出队后队列为空
51         {
52             BFSQ->rear=NULL;
53             BFSQ->front=NULL;
54         }
55         else  //出队后队列非空
56         {
57             BFSQ->front=tp->next;
58         }        
59         BFSQ->count--;
60         free(tp);  //释放暂存指针
61 
62         return temp;
63     }
64     else
65         return NULL;
66 }

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap