數(shù)據(jù)結(jié)構(gòu)實驗報告—隊列

1、算法與數(shù)據(jù)結(jié)構(gòu)課程教師評閱意見：簽名：年月日實驗成績：一、實驗?zāi)康恼莆贞犃械拇鎯Y(jié)構(gòu)及進隊/出隊等操作的實現(xiàn)。二、實驗內(nèi)容及要求1. 實現(xiàn)隊列的一種存儲結(jié)構(gòu)。2. 實現(xiàn)隊列的相關(guān)操作。3. 利用隊列的操作特點，借助進隊與出隊操作完成打印二項式系數(shù)的任務(wù)。三、系統(tǒng)分析(1) 數(shù)據(jù)方面：該隊列數(shù)據(jù)元素類型采用整型，在此基礎(chǔ)上進行隊列的一些基本操作，應(yīng)用體現(xiàn)在打印二項式系數(shù)即打印楊輝三角形。(2) 功能方面：1. 進隊操作：若隊列不滿，則將元素x進入隊列。2. 出隊操作：若隊列不空，則退出隊頭元素x并由函數(shù)返回true,否則返回false。3. 獲取隊頭元素：若隊列不為空，貝U函數(shù)返回true及隊頭

2、元素的值，否則返回false。4. 判斷隊列是否為空、判斷隊列是否滿。5. 計算隊列中元素個數(shù)：直接返回隊列中元素個數(shù)。6. 活空隊列內(nèi)容：隊頭指針和隊尾指針置0。7. 打印楊輝三角形前n行數(shù)字。四、系統(tǒng)設(shè)計(1)設(shè)計的主要思路隊列得基丁數(shù)組得存儲表示亦稱為順序隊列，是利用一個一維數(shù)組作為隊列元素的存儲結(jié)構(gòu)，并且設(shè)置兩個指針front和rear,分別指示隊歹U的隊頭和隊尾位置。每當(dāng)添加一個新元素時，先將新元素添加到rear所指位置，再讓隊尾指針rear進1。每當(dāng)退出隊頭元素，應(yīng)當(dāng)先把front所指位置元素記錄下來，再讓隊頭指針進1,指示下一隊頭元素位置，最后把記錄下來的元素值返回。但當(dāng)隊頭指針

3、front=rear,隊歹0為空；而當(dāng)rear=maxSize時，隊歹U滿，如果再加入新元素，就會產(chǎn)生“溢出”。但這種“溢出”可能時假溢出，因為在數(shù)組的前端可能還有空位置。為了能夠充分地使用數(shù)組中的存儲空間，把數(shù)組的前端和后端連接起來，形成一個環(huán)形表，即把存儲隊歹0兀素的表從邏輯上看成一個環(huán)，成為循環(huán)隊列。循環(huán)隊列的首尾相接，當(dāng)隊頭指針front和隊尾指針rear進到maxSize-1后，再前進一個位置就自動到0.這可以利用除法取余的運算實現(xiàn)。(2)數(shù)據(jù)結(jié)構(gòu)的設(shè)計隊列的定義是一種限定存取位置的線性表。它只允許在表的一端插入，在另一端刪除。允許插入的一端叫做隊尾，允許刪除的一端叫做隊頭。最先進入

4、隊列的元素最先退出隊列，隊列這種特性叫做先進先出。對頭指針進1：front=(front+1)%maxSize;隊尾指針進1:rear=(rear+1)%maxSize;隊歹0初始化：front=rear=0;循環(huán)隊歹0的隊頭指針和隊尾指針初始化時都設(shè)置為0:front=rear=0.在隊尾插入新元素和刪除隊頭元素時，兩個指針都按順時針方向進1.當(dāng)它們進到maxSize-1時，并不表示表的終結(jié)，只要有需要，利用運算可以前進到數(shù)組的0號位置。五、編程環(huán)境與實驗步驟(1) 編程環(huán)境操作系統(tǒng)：Windows操作系統(tǒng)；編程工具軟件：VisualStudio2017(2) 實驗步驟無文件操作。(3) 編

5、譯參數(shù)無特殊的編譯參數(shù)設(shè)置。六、實現(xiàn)代碼主要功能的實現(xiàn)代碼楊輝三角函數(shù)：voidYANGVI(intn)(Queue<int>q(n+2);inti=1;intj=0;ints=0,k=0;intt,u;q.EnQueue(i);q.EnQueue(i);for(i=1;i<=n;i+)(q.EnQueue(k);for(j=1;j<=i+2;j+)(q.DeQueue(t);u=s+t;q.EnQueue(u);s=t;a0=1;if(j!=i+2)(ao=s;o+;楊輝三角形輸出顯示函數(shù)：voidShow(int*a,intn)(inti,j;intsum=0;in

6、tk=0;for(i=0;i<n;i+)(for(j=0;j<n-i-1;j+)cout<<setw(3)<<""/前導(dǎo)空格，為單個數(shù)據(jù)的一半寬度for(j=0;j<=i;j+)(cout<<setw(6)<<asum+j;k+;sum=k;cout<<endl;SeqQueueffi環(huán)隊歹U棋板：template<classT>classQueue(public:Queue(intsz=100);Queue()(deleteelements;boolEnQueue(T&x);

7、boolDeQueue(T&x);boolgetFront(T&x);voidmakeEmpty()(front=rear=0;boolIsEmpty();boolIsFull();intgetSize();friendostream&operator<<(ostream&os,Queue<T>&Q);private:intrear,front;T*elements;intmaxSize;template<classT>Queue<T>:Queue(intsz)(rear=0;front=0;maxSize

8、=sz;elements=newTmaxSize;assert(elements!=NULL);/斷f：動態(tài)存儲分配成功與否template<classT>boolQueue<T>:EnQueue(T&x)if(IsFull()=true)returnfalse;elementsrear=x;rear=(rear+1)%maxSize;returntrue;template<classT>boolQueue<T>:DeQueue(T&x)if(IsEmpty()=true)returnfalse;x=elementsfront;f

9、ront=(front+1)%maxSize;returntrue;template<classT>boolQueue<T>:getFront(T&x)if(IsEmpty()=true)returnfalse;x=elementsfront;returntrue;template<classT>boolQueue<T>:IsEmpty()return(front=rear)?true:false;template<classT>boolQueue<T>:IsFull()return(rear+1)%maxSize

10、=front)?true:false;template<classT>intQueue<T>:getSize()return(rear-front+maxSize)%maxSize;template<classT>ostream&operator<<(ostream&os,Queue<T>&Q)os<<"front="<<Q.front<<",rear="<<Q.rear<<endl;for(inti=Q.fro

11、nt;i!=Q.rear;i=(i+1)%Q.maxSize)os<<i<<":"<<Q.elementsi<<endl;returnos;七、測試結(jié)果與說明n為4時楊輝三角輸出為：VS2017W.51JProject1OebugPro作:如什康；41I11211331清按任.意鍵繼續(xù)一一n為10時楊輝三角輸出為:F:jmVS2017?!jProject1DebugProject1,exe輸入行數(shù)：10111121133114641151010511615201561172135352171182856705628811936

12、84126126843691請按任意鍵繼續(xù).-.n為20時楊輝三角輸出為:20111121133114641510105116152015611721353521711S385&70562B811936E413612684369111045120210252210120451011.115516533042462獺1655511112通2204957929247924前22066121113732E57U12B71716171612S77152867313114933jM1D012W300334323003200210013649114111510545515653003&00

13、5M35643550O&30031365455105151116120560183C4368燦811412S7011440S008436818205的1.2016111713&6802380們槌123761M48243W243101944812376618823606801361711131535163060日豌1856431824437534S62D43753318241S164855330WB16153IS11191719刖3876116282713250388755S2923789237B755825D38827132116283S76日的17119請按任意健催探八、實驗

14、分析(1) 算法的性能分析打印楊輝三角：從三角形的形狀可知，除第一行以外，在打印第i行時，用到上一行(第i-1行)的數(shù)據(jù)，在打印第i+1行時，乂用到第i行的數(shù)據(jù)。隊列的操作的時間復(fù)雜度都是O(1)。循環(huán)隊列和鏈隊列的空間性能的比較與順序棧和鏈棧的空間性能比較類似，只是循環(huán)隊列不能像順序棧那樣共享空間，通常不能在一個數(shù)組中存儲兩個循環(huán)隊歹0。(2) 數(shù)據(jù)結(jié)構(gòu)的分析隊列是另一種限定存取位置的線性表。它只允許在表的一端插入，在另一端刪除。隊列所具有的這種特性就叫做先進先出。為了能夠充分地使用數(shù)組中的空問，把數(shù)組的前端和后端連接起來，形成一個環(huán)形的表，即把存儲隊列元素的表從邏輯上看成一個環(huán)，成為循環(huán)隊

15、列。適用場景：當(dāng)儲存數(shù)據(jù)比較大的時候適合用隊列。九、實驗總結(jié)經(jīng)過幾天的努力，完成了數(shù)據(jù)結(jié)構(gòu)的隊列的實驗內(nèi)容，能夠熟練掌握隊列的基本操作并且對丁隊列的應(yīng)用有所了解，掌握了隊列的特點即先進先出，以及進隊、出隊等基本操作。并實現(xiàn)了隊列的應(yīng)用即打印二項展開式的系數(shù)。在程序的整個分析、設(shè)計、實現(xiàn)、測試等環(huán)節(jié)都有所收獲。由丁前面幾次實驗積累的經(jīng)驗，加上課堂上老師的相應(yīng)講解，在程序的分析階段花費的時間主要在確定隊列存儲方式上，在確定使用循環(huán)隊列存儲元素后，乂對循環(huán)隊列的基本操作進行了學(xué)習(xí),在掌握循環(huán)隊列的實現(xiàn)后將代碼編寫完成后，這次實驗也變得沒那么困難了。本次實驗的難點就在丁使用隊列輸出二項式系數(shù)，由丁需要用隊列實現(xiàn)所以就必須要熟練掌握循環(huán)隊列的實現(xiàn)代碼，最開始寫的時候由丁忽略了循環(huán)隊列最多只能存儲maxSize-1個元素，所以導(dǎo)致二項式系數(shù)輸出的最后一行始終有問題，反復(fù)逐步調(diào)試了幾次代碼才發(fā)現(xiàn)了問題所在，這個過程讓我印象比較深刻，對