第 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

 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 }

 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 }