循環(huán)隊(duì)列的實(shí)現(xiàn)與運(yùn)算

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

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

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

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

5、/ 隊(duì)空不能出隊(duì) else q.front=(q.front+1) % MAXLEN; printf(ntt 出隊(duì)元素為：%dn,q.dataq.front); / 輸出隊(duì)頭元素 return; void ShowQueue() / 顯示函數(shù) int k=q.front; if (k=q.rear) printf(ntt 此隊(duì)列為空! n); return; printf(ntt 此隊(duì)列元素為：); 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) 隊(duì) 列n);printf(ntt*);printf(ntt* 1-顯 示 *);printf(ntt* 2-進(jìn) 隊(duì) *);printf(ntt* 3-出 隊(duì) *); printf(ntt* 4-求 隊(duì) 列 長(zhǎng) 度 *);printf(ntt* 0-返 回 *);printf(ntt*);printf(nntt 請(qǐng)選擇菜單號(hào): );scanf(%d,&choice);switch

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