资料结构 宁列.ppt

1、資料結構,第5章佇列,5-1認識佇列,佇列 (queue) 是一個線性串列，兩端分別稱為前端 (front) 與後端 (rear)，當要新增資料時，必須放入佇列的後端，當要刪除資料時，必須從佇列的前端開始。,5-2佇列的實作,5-2-1使用陣列實作佇列 #define MAX_SIZE 6 typedef struct que char dataMAX_SIZE; int front; int rear; queue; queue Q; Q.front = -1; Q.rear = -1;,佇列應該要提供下列運算： 判斷佇列已滿 (isFull) 判斷佇列已空 (isEmpty) enqueu

2、e或新增 (add) enqueue(queue *Q, char value) if (Q-rear = (MAX_SIZE - 1) printf(佇列已滿！); else Q-data+Q-rear = value; dequeue或刪除 (delete) dequeue(queue *Q) if (Q-front = Q-rear) printf(佇列已空！); */ else printf(%c , Q-data+Q-front); ,假設佇列的最大長度為6，依序新增A、B、C、D等四個資料，然後刪除兩個資料，再新增E、F、G等三個資料，則變數front、rear的值與佇列的內容如下

3、：,環狀佇列 enqueue() 函數必須改寫成如下，以適用於環狀佇列： queue Q; Q.front = 0; Q.rear = 0; enqueue(queue *Q, char value) if (Q-rear + 1) % MAX_SIZE = Q-front) printf(佇列已滿！); else Q-rear = (Q-rear + 1) % MAX_SIZE; Q-dataQ-rear = value; ,dequeue() 函數必須改寫成如下，以適用於環狀佇列 ： dequeue(queue *Q) if (Q-front = Q-rear) printf(佇列已空！)

4、; else Q-front = (Q-front + 1) % MAX_SIZE; printf(%c , Q-dataQ-front); ,前面的例子改成環狀佇列後，佇列的內容如下：,5-2-2使用鏈結串列實作佇列,typedef struct node int data; struct node *next; list_node; typedef list_node *list_pointer; list_pointer front, rear;,若要新增資料，必須將資料放入佇列的後端，如下圖所示：,若要刪除資料，必須從佇列的前端開始，如下圖所示：,範例5.1：enqueue 根據本節宣

5、告的單向鏈結串列，撰寫一個函數實作佇列的新增資料運算。 enqueue(int value) list_pointer ptr; ptr = (list_pointer)malloc(sizeof(list_node); ptr-data = value; ptr-next = NULL; if (rear = NULL) front = ptr; else rear-next = ptr; rear = ptr; ,範例5.2：dequeue 根據本節宣告的單向鏈結串列，撰寫一個函數實作佇列的刪除資料運算。 dequeue() list_pointer ptr; if (front = NU

6、LL) printf(佇列已空！); else printf(%d , front-data); ptr = front; front = front-next; free(ptr); ,5-3雙向佇列,#define MAX_SIZE 100 typedef struct deq char dataMAX_SIZE; int frontL; int rearL; int frontR; int rearR; deque; queue Q; Q.frontL = -1; Q.rearL = -1; Q.frontR = MAX_SIZE; Q.rearR = MAX_SIZE;,雙向佇列應該要提供下列