循環(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è)計(jì)BX1001課程名：題 目:實(shí)驗(yàn)類別班 級(jí):學(xué) 號(hào):姓 名:101003020141趙艷10日2011 年 10算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-1 -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í)間，

2、則插 入在隊(duì)頭，否則插入在隊(duì)尾。（3）循環(huán)隊(duì)列數(shù)據(jù)類型：#define MAXLEN 10typedef struct int dataMAXLEN;int fron t,rear; csequeue;（4）入隊(duì)作業(yè)處理的預(yù)計(jì)執(zhí)行時(shí)間可以用隨機(jī)數(shù)函數(shù)ran d（）產(chǎn)生，也可以從鍵盤輸入。3、實(shí)驗(yàn)要求（1）利用C （C+）語(yǔ)言完成算法設(shè)計(jì)和程序設(shè)計(jì)。（2）上機(jī)調(diào)試通過(guò)實(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)步驟與源程序?qū)嶒?yàn)步驟首定義MAXLEN=1,然后初始化隊(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)用，菜單界面主要通過(guò)printf （）函數(shù)來(lái)實(shí)現(xiàn),下面一一對(duì)應(yīng)有switch （）語(yǔ)句來(lái)實(shí)現(xiàn)。源代碼#in clude<stdio.h>#defi ne MAXLEN 10typedef struct int dataMAXLEN;/定義數(shù)據(jù)的類型算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-# -算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-2 -int fron t,rear;/定義隊(duì)頭、隊(duì)尾指針?biāo)?/p>

4、法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-3 -csequeue;csequeue q;初始化隊(duì)列void Ini Queue()/ q.fro nt=q.rear=MAXLEN-1;入隊(duì)函數(shù)void In Queue()/ int x ;prin tf("ntt輸入一個(gè)入隊(duì)的整數(shù)數(shù)據(jù)：");scan f("%d"，& x);if (q.fro nt=(q.rear+1) % MAXLEN ) printf("ntt隊(duì)滿，不能入隊(duì)！ n”)； return; q.rear=(q.rear+1) % MAXLEN;q.dataq.rear=x;prin tf

5、("nttvoid Outsequeue() if (q.fron t=q.rear) printf ("ntt入隊(duì)成功！ n");/此隊(duì)列為空! "); return ;/出隊(duì)函數(shù)隊(duì)空不能出隊(duì)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-# -算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-# -else q.fro nt=(q .fron t+1) % MAXLEN;prin tf("ntt出隊(duì)元素為：%dn",q.dataq.fro nt); /輸出隊(duì)頭元素算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-# -算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-5 -return;顯示函數(shù)void ShowQueue()/

6、int k=q.fr ont;此隊(duì)列為空！ n"); return;此隊(duì)列元素為：");if (k=q.rear) prin tf("nttprin tf("nttdo k=(k+1)%MAXLEN;prin tf("%4d",q.datak); while(k!=q.rear);prin tf("n");int len gth() int k;k=(q.rear-q.fro nt+MAXLEN)% MAXLEN;return k;void main()/主函數(shù) int i=1;int choice;Ini Que

7、ue();while (i)prin tf("ntt循環(huán)隊(duì)列n");prin tf("ntt* *");prin tf("ntt*");prin tf("ntt*");prin tf("ntt*");prin tf("ntt*");prin tf("ntt*");prin tf("ntt* *");prin tf("nntt請(qǐng)選擇菜單號(hào)：”);scan f("%d",&choice); switch

8、(choice)case 1: ShowQueue(); break;case 2: In Queue(); break;case 3: Outsequeue(); break;case 4: prin tf("ntt隊(duì)列長(zhǎng)度為：%d n",length();break;case 0: i=0; break;5、測(cè)試數(shù)據(jù)與實(shí)驗(yàn)結(jié)果（可以抓圖粘貼）循環(huán)隊(duì)列12 3 4 0隊(duì)隊(duì)-回長(zhǎng)列隊(duì)進(jìn)出顯求返請(qǐng)選擇菜單號(hào)：1輸入一個(gè)入隊(duì)的整數(shù)數(shù)據(jù)；1循壞隊(duì)列12 3 4 0H H H 丹仔K-MK-MT 丹葉算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-# -算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-# -請(qǐng)選擇菜單號(hào)：3此隊(duì)列

9、元素為乂1 13循環(huán)隊(duì)列算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-# -算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-# -三二隊(duì)隊(duì)-$!回長(zhǎng)列進(jìn)出顯求返12 3 4 0M w M M M二二沁算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-6 -請(qǐng)選擇菜單號(hào)：4 隊(duì)列長(zhǎng)度為：36、結(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ì)是通過(guò)把新元素插入隊(duì)尾，出隊(duì)是輸出隊(duì)頭元素。我再次加深了入隊(duì)要判斷棧滿，用語(yǔ)句q.fro nt=（q.rea葉1）% MAXLEW斷，入隊(duì)有兩種輸入方法，隊(duì)首和隊(duì)尾。出隊(duì)要判斷隊(duì)是否為空，用語(yǔ)句q.fro nt=q.