欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

第 17 章 高级数据表示(测试队列)

程序员文章站 2022-05-19 08:24:41
1 /* 2 queue.h -- Queue接口 3 */ 4 5 #ifndef QUEUE_H 6 #define QUEUE_H 7 8 #define MAXQUEUE 10 9 10 typedef int Item; 11 12 typedef struct node 13 { 14 ......
第 17 章 高级数据表示(测试队列)
 1 /*------------------------
 2     queue.h -- Queue接口
 3 ------------------------*/
 4 
 5 #ifndef QUEUE_H
 6 #define QUEUE_H
 7 
 8 #define MAXQUEUE 10
 9 
10 typedef int Item;
11 
12 typedef struct node
13 {
14     Item item;
15     struct node *next;
16 } Node;
17 
18 typedef struct queue
19 {
20     Node *front;    //指向队列首项的指针
21     Node *rear;        //指向队列尾项的指针
22     int items;        //队列中的项数
23 } Queue;
24 
25 //初始化队列为空
26 void InitializeQueue(Queue *pq);
27 
28 //检查队列是否已满,已满返回true,否则返回false
29 bool QueueIsFull(const Queue *pq);
30 
31 //检查队列是否为空,为空返回true,否则返回false
32 bool QueueIsEmpty(const Queue *pq);
33 
34 //确定队列的项数
35 int QueueItemCount(const Queue *pq);
36 
37 //在队列末尾添加项:item是被添加在队列末尾的项
38 bool EnQueue(Item item, Queue *pq);
39 
40 //在队列开头删除项:队列不为空,队列首位item将被拷贝到*pitem中
41 bool DeQueue(Item *pitem, Queue *pq);
42 
43 //清空队列
44 void EmptyTheQueue(Queue *pq);
45 
46 #endif
queue.h
第 17 章 高级数据表示(测试队列)
 1 /*----------------------------
 2     queue.c -- Queue 实现
 3 ----------------------------*/
 4 
 5 #include <stdio.h>
 6 #include <stdlib.h>
 7 #include "queue.h"
 8 
 9 static void CopyToNode(const Item *pi, Node *pn)
10 {
11     pn->item = *pi;
12 }
13 
14 static void CopyToItem(const Node *pn, Item *pi)
15 {
16     *pi = pn->item;
17 }
18 
19 void InitializeQueue(Queue *pq)
20 {
21     pq->front = pq->rear = NULL;
22     pq->items = 0;
23 }
24 
25 bool QueueIsFull(const Queue *pq)
26 {
27     return pq->items == MAXQUEUE;
28 }
29 
30 bool QueueIsEmpty(const Queue *pq)
31 {
32     return pq->items == 0;
33 }
34 
35 int QueueItemCount(const Queue *pq)
36 {
37     return pq->items;
38 }
39 
40 bool EnQueue(Item item, Queue *pq)
41 {
42     if (QueueIsFull(pq)) return false;
43 
44     Node *pnew = (Node*)malloc(sizeof(Node));
45     if (pnew == NULL)
46     {
47         fprintf(stderr, "Unable to allocate memory!\n");
48         exit(EXIT_FAILURE);
49     }
50 
51     CopyToNode(&item, pnew);
52     pnew->next = NULL;
53 
54     if (QueueIsEmpty(pq))
55         pq->front = pnew;                //新添项位于队列头端
56     else
57         pq->rear->next = pnew;          //新添项链接到队列尾端
58 
59     pq->rear = pnew;                    //记录队列尾端的位置
60     ++(pq->items);                      //队列项数加1
61 
62     return true;
63 }
64 
65 bool DeQueue(Item *pitem, Queue *pq)
66 {
67     if (QueueIsEmpty(pq)) return false;
68 
69     CopyToItem(pq->front, pitem);
70 
71     Node *pt = pq->front;
72     pq->front = pt->next;
73     free(pt);
74     --(pq->items);
75 
76     if (QueueIsEmpty(pq)) pq->rear = NULL;
77 
78     return true;
79 }
80 
81 void EmptyTheQueue(Queue *pq)
82 {
83     Item dummy;
84     while (!QueueIsEmpty(pq)) DeQueue(&dummy, pq);
85 }
queue.c
第 17 章 高级数据表示(测试队列)
 1 /*---------------------------------------
 2     use_q.c -- 驱动程序测试 Queue 接口
 3 ---------------------------------------*/
 4 
 5 #include <stdio.h>
 6 #include "queue.h"
 7 
 8 int main()
 9 {
10     Queue line;
11     Item temp;
12     char ch;
13 
14     InitializeQueue(&line);
15 
16     puts("Testing the Queue interface. Type \"a\" to add a value, ");
17     puts("type \"d\" to delete a value, and type \"q\" to quit.");
18 
19     while ((ch = getchar()) != 'q')
20     {
21         if (ch != 'a' && ch != 'd') continue;    //忽略其他输出
22 
23         if (ch == 'a')        //add
24         {
25             printf("Integer to add: ");
26             scanf("%d", &temp);
27             
28             if (!QueueIsFull(&line))
29             {
30                 printf("Putting %d into queue\n", temp);
31                 EnQueue(temp, &line);
32             }
33             else
34                 puts("Queue is full!");
35         }
36         else                //delete
37         {
38             if (QueueIsEmpty(&line))
39                 puts("Nothing to delete!");
40             else
41             {
42                 DeQueue(&temp, &line);
43                 printf("Removing %d from queue\n", temp);
44             }
45         }
46 
47         printf("%d items in queue\n", QueueItemCount(&line));
48         puts("Type \"a\" to add, \"d\" to delete, \"q\" to quit;");
49     }
50 
51     EmptyTheQueue(&line);
52     puts("Bye!");
53 
54     return 0;
55 }
use_q.c

第 17 章 高级数据表示(测试队列)