循環(huán)隊列的實現(xiàn)與運算

1、電子信息學(xué)院實驗報告書課程名： 數(shù)據(jù)結(jié)構(gòu) 題 目： 循環(huán)隊列的實現(xiàn)和運算 實驗類別 設(shè)計 班 級： BX1001 學(xué) 號： 1 姓 名： 趙艷 2011年10 月 10日1、 實驗題目（1) 掌握隊列 “先進先出”的特點；（2) 復(fù)習(xí)隊列的入隊、出隊、插入、刪除等基本運算。（3) 掌握循環(huán)隊列的特點，以及循環(huán)隊列的應(yīng)用。2、 實驗內(nèi)容（1） 在順序存儲結(jié)構(gòu)上實現(xiàn)輸出受限制的雙端循環(huán)隊列的入隊和出隊（只允許隊頭輸出）算法。（2） 設(shè)每個元素表示一個待處理的作業(yè)，元素值表示作業(yè)的預(yù)計時間。入隊列采取簡化的短作業(yè)優(yōu)先原則，若一個新提交的作業(yè)的預(yù)計執(zhí)行時間小于對頭和隊尾作業(yè)的平均時間，則插入在隊頭，否

2、則插入在隊尾。（3） 循環(huán)隊列數(shù)據(jù)類型：#define MAXLEN 10typedef struct int dataMAXLEN; int front,rear;csequeue; (4)入隊作業(yè)處理的預(yù)計執(zhí)行時間可以用隨機數(shù)函數(shù)rand()產(chǎn)生，也可以從鍵盤輸入。3、 實驗要求（1） 利用C（C+）語言完成算法設(shè)計和程序設(shè)計。（2） 上機調(diào)試通過實驗程序。（3） 輸入數(shù)據(jù)，檢驗程序運行結(jié)果。（4） 給出具體的算法分析，包括時間復(fù)雜度和空間復(fù)雜度等。（5） 撰寫實驗報告。4、 實驗步驟與源程序 實驗步驟 首定義MAXLEN=10，然后初始化隊列，再定義數(shù)據(jù)類型、頭、尾指針。下面定義五個函數(shù)

3、，分別是入隊函數(shù)、出隊函數(shù)、顯示函數(shù)和長度計算函數(shù)。在入隊時要判斷是否隊滿，隊滿不能入隊。出隊要判斷隊是否為空，隊空不能出隊。判斷隊列長度的函數(shù)，用隊尾指針與隊首指針之差來計算。最后的主函數(shù)是一個隊列菜單和相應(yīng)的對函數(shù)的調(diào)用，菜單界面主要通過printf（）函數(shù)來實現(xiàn)，下面一一對應(yīng)有switch（）語句來實現(xiàn)。 源代碼#include#define MAXLEN 10typedef struct int dataMAXLEN; / 定義數(shù)據(jù)的類型 int front,rear; / 定義隊頭、隊尾指針csequeue;csequeue q; void IniQueue() / 初始化隊列 q.

4、front=q.rear=MAXLEN-1; void InQueue() / 入隊函數(shù) int x ; printf(ntt 輸入一個入隊的整數(shù)數(shù)據(jù)：); scanf(%d,&x); if (q.front=(q.rear+1) % MAXLEN ) printf(ntt 隊滿，不能入隊! n); return; q.rear=(q.rear+1) % MAXLEN; q.dataq.rear=x; printf(ntt 入隊成功! n); void Outsequeue() / 出隊函數(shù) if (q.front=q.rear) printf (ntt 此隊列為空! ); return ;

5、/ 隊空不能出隊 else q.front=(q.front+1) % MAXLEN; printf(ntt 出隊元素為：%dn,q.dataq.front); / 輸出隊頭元素 return; void ShowQueue() / 顯示函數(shù) int k=q.front; if (k=q.rear) printf(ntt 此隊列為空! n); return; printf(ntt 此隊列元素為：); do k=(k+1)%MAXLEN; printf(%4d,q.datak); while(k!=q.rear); printf(n);int length() int k; k=(q.rear-

6、q.front+MAXLEN)% MAXLEN; return k;void main() / 主函數(shù) int i=1; int choice; IniQueue(); while (i) printf(ntt 循 環(huán) 隊 列n);printf(ntt*);printf(ntt* 1-顯 示 *);printf(ntt* 2-進 隊 *);printf(ntt* 3-出 隊 *); printf(ntt* 4-求 隊 列 長 度 *);printf(ntt* 0-返 回 *);printf(ntt*);printf(nntt 請選擇菜單號: );scanf(%d,&choice);switch

7、(choice) case 1: ShowQueue(); break; case 2: InQueue(); break; case 3: Outsequeue(); break; case 4: printf(ntt 隊列長度為: %d n,length();break; case 0: i=0; break; 5、 測試數(shù)據(jù)與實驗結(jié)果（可以抓圖粘貼） 6、 結(jié)果分析與實驗體會程序可以運行，結(jié)果正確，在實驗中是對五個函數(shù)的調(diào)用，我在實驗中更清楚的認識到隊列跟棧的不同，隊列是先進先出，棧是后進先出。但這個程序只有對一個元素的處理，入隊、出隊、顯示、求長度，出棧后隊列長度為0。進隊是通過把新元素插入隊尾，出隊是輸出隊頭元素。我再次加深了入隊要判斷棧滿，用語句q.front=(q.rear+1) % MAXLEN判斷，入隊有兩種輸入方法，隊首和隊尾。出隊要判斷隊是否為空，用語句q.front=q.rear判斷。如果不判斷，會影響程序運行，也會