第 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 }