實(shí)驗(yàn)三棧和隊(duì)列及其應(yīng)用

1、學(xué)號(hào)某某實(shí)驗(yàn)項(xiàng)目棧和隊(duì)列與其應(yīng)用1實(shí)驗(yàn)內(nèi)容1.采用順序存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)棧的存儲(chǔ)和根本操作。棧的抽象數(shù)據(jù)類(lèi)型定義參見(jiàn)教材第45頁(yè)。棧的順序存儲(chǔ)結(jié)構(gòu)定義參見(jiàn)教材第46頁(yè)。2.采用順序存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)隊(duì)列的存儲(chǔ)和根本操作隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義參見(jiàn)教材第59頁(yè)。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)定義參見(jiàn)教材第64頁(yè)。算法設(shè)計(jì)與程序?qū)崿F(xiàn):算法分析函數(shù)，完成實(shí)驗(yàn)要求。程序?qū)崿F(xiàn)步驟：1、順序棧結(jié)構(gòu)的根本操作： 首先初始化一個(gè)順序棧結(jié)構(gòu)，然后輸入需入棧的兀素個(gè)數(shù) N,通過(guò)一個(gè)循環(huán)依次輸入N個(gè)兀素，在輸入的冋時(shí)調(diào)用入棧函數(shù)這樣就完成了N個(gè)兀素的入棧操作，隨后調(diào)用返回棧頂兀素的函數(shù)，返回棧頂兀素，接著通過(guò)循環(huán)調(diào)用出棧函數(shù)完成出棧操作

2、，最后銷(xiāo)毀棧結(jié)構(gòu)。當(dāng)然在進(jìn)展入棧和出棧操作時(shí)，會(huì)使用判斷棧是否為空、對(duì)棧進(jìn)展遍歷等操J作，這樣就實(shí)現(xiàn)了對(duì)棧的根本操作。2、棧結(jié)構(gòu)的根本應(yīng)用：1將輸入的十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)。首本次實(shí)驗(yàn)主函數(shù)采用順序結(jié)構(gòu)， 主函數(shù)調(diào)用自己編寫(xiě)的頭文件 中的相關(guān)功能先初始化一個(gè)棧結(jié)構(gòu)，構(gòu)造一個(gè)空棧，然后輸入十進(jìn)制數(shù)N,根據(jù)十進(jìn)制轉(zhuǎn)換為二進(jìn)制的方法除二取余法通過(guò)循環(huán)判斷將每次除二求模的數(shù)入棧， 接著通過(guò)判斷?？諚l件，依次將棧中的元素出棧，然后輸出這樣就實(shí)現(xiàn)了十 進(jìn)制對(duì)二進(jìn)制的轉(zhuǎn)換，當(dāng)然其他進(jìn)制之間的也是如此。2Hanoi問(wèn)題的實(shí)現(xiàn)。其主要思想就是遞歸，在進(jìn)展遞歸調(diào)用函數(shù)本身的時(shí)候，參數(shù)的傳遞、 變量保存以與函數(shù)返回

3、都使用了棧結(jié)構(gòu)操作系統(tǒng)建立。3、順序隊(duì)列的根本操作：首先初始化一個(gè)空的順序結(jié)構(gòu)隊(duì)列，然后輸入需入隊(duì)列的元素個(gè)數(shù) N,通過(guò)一個(gè)循環(huán)依次輸入N個(gè)元素，輸入的同時(shí)調(diào)用入隊(duì)列函數(shù)，完成了 N個(gè)元素的入隊(duì)列操作，接著調(diào)用返回隊(duì)頭元素的函 數(shù)，返回隊(duì)頭元素，接著通過(guò)循環(huán)調(diào)用出隊(duì)列函數(shù)完成出隊(duì)列操作，最后銷(xiāo) 毀順序隊(duì)列結(jié)構(gòu)，這樣就實(shí)現(xiàn)了對(duì)棧的根本操作。核心程序此程序中用到的自己編寫(xiě)的頭文件以在下面給出，而頭文件的說(shuō)明如此 在主函數(shù)中文件包含局部的注釋處，核心程序如下：1.主函數(shù)如下：#inelude "iostream" II標(biāo)準(zhǔn)輸入輸岀流庫(kù)文件#include "window

4、s.h" I/cmd 窗口設(shè)置函數(shù)頭文件#inelude "ADT.h"/數(shù)據(jù)結(jié)構(gòu)中相關(guān)結(jié)構(gòu)體類(lèi)型定義與相關(guān)數(shù)據(jù)類(lèi)型定義#inelude "DataStructure_LinearList.h"/數(shù)據(jù)結(jié)構(gòu)第二章線性表中相關(guān)函數(shù)的定義與聲明usingn amespace std;void print( void );int main( void )system( "title數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)實(shí)驗(yàn)三：棧和隊(duì)列與其應(yīng)用I" );/設(shè)置cmd窗口標(biāo)題system( "color F1" );/設(shè)置控制臺(tái)窗口的背景色和

5、前景色system( "date /T" );/輸岀當(dāng)前的日期pri nt();cout << "實(shí)驗(yàn)內(nèi)容一：采用順序存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)棧的存儲(chǔ)和根本操作"<< endl;SqStack S;SEIemTypee;InitStack Sq(S);/ 構(gòu)造一個(gè)空棧 Sint count;cout << "請(qǐng)輸入需入棧的元素個(gè)數(shù)：N ="cin >> cou nt;cout << "請(qǐng)輸入元素：”；for (int i = 0; i < count; i+)cin &

6、gt;> e;Push Sq(S, e);GetTop_Sq(S, e);cout << " 棧頂元素："<< e << endl;cout << "岀棧："while (Pop_Sq(S, e)cout << e <<""cout << endl << "棧的應(yīng)用："<< endl << "1.將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)“ <<en dl;DecToBi n();/將十

7、進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)cout << "2.漢羅塔問(wèn)題"<< endl <<"請(qǐng)輸入圓盤(pán)個(gè)數(shù)："nt n;/圓盤(pán)個(gè)數(shù)char x = 'A' , y ='B' , z = C ; |cin >> n;cout << "圓盤(pán)移動(dòng)步驟："Hanoi(n, x, y, z);DestoryStack Sq(S);/ 銷(xiāo)毀棧 Scout << en dl;pri nt();cout << "實(shí)驗(yàn)內(nèi)容二：采用順序存儲(chǔ)結(jié)構(gòu)，

8、實(shí)現(xiàn)隊(duì)列的存儲(chǔ)和根本操作"<<en dl;SqQueueQ;QElemTypedata;InitQueue_Sq(Q);/ 構(gòu)造一個(gè)空隊(duì)列 Qcout << "請(qǐng)輸入需入隊(duì)列的元素個(gè)數(shù)：N ="cin >> cou nt;cout << "請(qǐng)輸入元素：”；for ( int i = 0; i < count; i+)cin >> data;En Queue Sq(Q, data);GetHead_Sq(Q, data);cout << " 隊(duì)首元素："<

9、;< data << endl;cout << "岀隊(duì)列："while (DeQueue_Sq(Q, data)cout << data <<""cout << en dl;pri nt();cout << en dl;void print( void )cout << endl <<<< en dl;I *“2.頭文件"ADT.h"的局部程序如下:#ifndef ADT_H_#define ADT_H_/*常量和數(shù)據(jù)類(lèi)型

10、預(yù)定義*/*函數(shù)結(jié)果狀態(tài)代碼 */#define TRUE1#define FALSE0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/*數(shù)據(jù)類(lèi)型預(yù)定義 */typedefint Status ;/函數(shù)結(jié)果狀態(tài)類(lèi)型typedefint _bool ;/bool 狀態(tài)類(lèi)型*/數(shù)據(jù)結(jié)構(gòu)類(lèi)型定義*/*棧和隊(duì)列*/*棧數(shù)據(jù)類(lèi)型定義 */typedefi nt SEIemType順序表中元素的數(shù)據(jù)類(lèi)型/*棧動(dòng)態(tài)存儲(chǔ)分配初始常量預(yù)定義*/#define STACK_INIT_SIZE100/棧表存儲(chǔ)空間的初始分配量#d

11、efine STACKINCREMENT/棧表存儲(chǔ)空間的分配增量/*順序棧結(jié)構(gòu)類(lèi)型定義 */typedefstructSEIemType* base;/ 棧底指針SEIemType* top;/ 棧頂指針nt stacksize;/當(dāng)前以分配的存儲(chǔ)空間SqStack;/順序棧結(jié)構(gòu)類(lèi)型/*隊(duì)列數(shù)據(jù)類(lèi)型定義 */typedefi nt QEIemType順序表中元素的數(shù)據(jù)類(lèi)型/*隊(duì)列動(dòng)態(tài)存儲(chǔ)分配初始常量預(yù)定義 */#define QUEUE_INIT_SIZE100/隊(duì)列存儲(chǔ)空間的初始分配量#define QUEUEINCREMENT/隊(duì)列存儲(chǔ)空間的分配增量#define MAXQUEUESIZE

12、100/循環(huán)隊(duì)列最大長(zhǎng)度/*隊(duì)列順序存儲(chǔ)結(jié)構(gòu)類(lèi)型定義-*/typedefstructQEIemType*base;/隊(duì)列初始化動(dòng)態(tài)分配存儲(chǔ)空間int front;/對(duì)頭指針向量，隊(duì)列不空，指向隊(duì)頭元素int rear;/隊(duì)尾指針向量，隊(duì)列不空，指向隊(duì)尾下一個(gè)位置SqQueue順序隊(duì)列結(jié)構(gòu)類(lèi)型#endif /* ADT H */"DataStructure_StackQueue.h"中局部函數(shù)定義如下:#incIude <stdio.h>#incIude <maIIoc.h>#incIude "ADT.h"/*功能函數(shù)聲明區(qū)*/*

13、棧*/棧的根本操作Status InitStack_Sq( SqStack &S);/ 構(gòu)造一個(gè)空順序棧 SStatusGetTop_Sq( SqStack &S, SEIemType&e);/返回棧頂元素 eStatusStackEmpty_Sq( SqStack &S);/判斷棧 S是否為空StatusDestoryStack_Sq( SqStack &S);/銷(xiāo)毀順序棧 SStatusPush_Sq( SqStack &S, SElemTypee);/元素 e壓入順序棧StatusPop_Sq( SqStack &S, SElemT

14、ype&e);/元素 e岀棧II棧的應(yīng)用Status DecToBin( void );II十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)void Hanoi( int n, char x, char y, char z); II 實(shí)現(xiàn) Hanoi問(wèn)題，借助 y塔將x塔 上的n個(gè)圓盤(pán)搬移到z塔上I* 隊(duì)列*III隊(duì)列的根本操作Status InitQueue_Sq( SqQueue&Q);II 構(gòu)造一個(gè)空的順序隊(duì)列 QStatus GetHead_Sq( SqQueue&Q, QEIemType&e); II 返回順序隊(duì)列的隊(duì)頭元素 eStatus EnQueue_Sq(SqQueue

15、&Q, QEIemTypee); II 將元素 e插入到隊(duì)列 Q中Status DeQueue_SqSqQueue&Q, QEIemType&e); II 將元素 e從順序隊(duì)列中刪除并返 回Status InverseQueue_Sq( SqQueue&Q);II 實(shí)現(xiàn)隊(duì)列的逆置/*功能函數(shù)定義區(qū)*/I*棧結(jié)構(gòu)函數(shù)定義 *II*函數(shù)原型Status In itStack_Sq(SqStack &S)*函數(shù)功能構(gòu)造一個(gè)空棧S*入口參數(shù)SqStack類(lèi)型的結(jié)構(gòu)體變量S的引用&S*出口參數(shù)返回函數(shù)結(jié)果狀態(tài)*IStatus InitStack_Sq( S

16、qStack &S) Sbase = ( SEIemType *)malloc( STACK_INIT_SIZE* sizeof (SEIemType); if (! Sbase)return (OVERFLOWStop = S.base;S stacksize = STACK_INIT_SIZEreturn OK /Ini tStack_SqI*函數(shù)原型Status DestoryStack Sq(SqStack &S)*函數(shù)功能銷(xiāo)毀棧S*入口參數(shù)SqStack類(lèi)型的結(jié)構(gòu)體變量S的引用&S*出口參數(shù)返回函數(shù)結(jié)果狀態(tài)Status DestoryStack_Sq( SqS

17、tack &S) SEIemType*p;while ( S.base !=S.top)p = - S.top;free(p);return OKDestoryStack_Sq/*/Status Push_Sq( SqStack &S, SElemType)SElemType* newbase;if ( S.top -S.base >= S.stacksize)newbase = ( SElemType*)realloc(S.base, ( STACKINCREMENTSstacksize)* sizeof (SElemTypg);f (!newbase)return O

18、VERFLOWSbase = n ewbase;Stop = S.base + S.stacksize;S stacksize += STACKINCREMENT*Stop+ = e;return OKPush_Sq/*/Status Pop_Sq( SqStack &S SElemType&e) if ( S.top = Sbase)return ERRORe = * - Stop; return OKPop_Sq/*函數(shù)原型Status DecToBi n( void)*函數(shù)功能將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制*入口參數(shù)void*出口參數(shù)返回函數(shù)結(jié)果狀態(tài)*/Status DecToB

19、in( void )LinkStack S;SElemTypee;long data;printf("請(qǐng)輸入待轉(zhuǎn)換的十進(jìn)制數(shù)：");scanf s( "%d", &data);In itStack_L(S);while (data)Push_L(S, data % 2); data = data / 2;pri ntf("轉(zhuǎn)換后的二進(jìn)制數(shù)：")；while (S->next)Pop_L(S, e); printf( "%d", e);printf( "n");return OK/*

20、 /DecToBin*函數(shù)原型Status InitQueue Sq(SqQueue &Q)*函數(shù)功能構(gòu)造一個(gè)空隊(duì)列Q*入口參數(shù)SqQueue類(lèi)型的結(jié)構(gòu)體變量C的引用&Q*出口參數(shù)返回函數(shù)結(jié)果狀態(tài)隊(duì)列結(jié)構(gòu)函數(shù)定義*/Status InitQueue_Sq( SqQueue&Q Qbase = ( QElemType*)malloc( QUEUE_INIT_SIZE sizeof (QElemType); if (! Qbase)return (OVERFLOWQfront =Qrear = 0;return OKl ni tQueue_Sq/return OKEn Qu

21、eue_Sq/* 函數(shù)原型：Status DeQueue_Sq(SqQueue &S, QElemType &e) 1、此次實(shí)驗(yàn)完成了對(duì)順序存儲(chǔ)結(jié)構(gòu)的棧和隊(duì)列的根本操作與簡(jiǎn)單應(yīng)用， 加深了對(duì)課本知識(shí)的理解和掌握。此次實(shí)驗(yàn)相對(duì)較容易，但卻是很根底的， 在以后的二叉樹(shù)、圖等高級(jí)數(shù)據(jù)結(jié)構(gòu)都需要用到它，所以棧和隊(duì)列是非常重 要的，有些細(xì)節(jié)局部是值得高度重視的，也是容易出錯(cuò)的地方。2、 棧頂指針指向的是棧頂元素的下一個(gè)位置，在進(jìn)展出棧操作時(shí)，應(yīng)先 將棧頂指針向量自減，指向棧頂元素，才能保證棧中元素正確出棧。當(dāng)進(jìn)展 連續(xù)入隊(duì)列操作時(shí)，要改變的是隊(duì)尾指針的指向，而不是隊(duì)頭指針；雖然初 始狀態(tài)

22、下隊(duì)頭指針和隊(duì)尾指針都指向頭一個(gè)元素，所以做第一個(gè)插入時(shí)關(guān)系不大，但第二次開(kāi)始就一定要改變尾指針。3 因?yàn)闂Ｊ窍Ｍ?dāng)有需要進(jìn)展入棧操作時(shí)就一定能夠入棧，一般來(lái)說(shuō)， 初始化順序空棧時(shí)，不應(yīng)限定棧的最大容量，但在順序結(jié)構(gòu)當(dāng)中存儲(chǔ)空間是 由程序員需要時(shí)事先指定分配的，一個(gè)合理的做法就是：先為棧分配一個(gè)根 本容量，然后在應(yīng)用過(guò)程中，當(dāng)棧的空間不夠使用時(shí)再逐段擴(kuò)大。* 函數(shù)原型：Status GetHead_Sq(SqQueue &Q, QElemType &e)*函數(shù)功能：假如隊(duì)列不空，如此返回隊(duì)頭元素e,并返回函數(shù)結(jié)果狀態(tài)OK否如此返回ERROR*入口參數(shù)：SqQueue類(lèi)型的結(jié)構(gòu)體變量C的引用&Q,QEIemTyp類(lèi)型元素e的引用&e*岀口參數(shù)：返回函數(shù)結(jié)果狀態(tài)*/Status GetHead_Sq(SqQueue& Q QElemType&e)if ( Qfront = Qrear)return ERRORe = Qbase Qrear - 1;/隊(duì)尾指針向量指向下一個(gè)元素return OK /GetHead_Sq/*|*函數(shù)原型Status En Queue_Sq(SqQueue &Q, QElemType e)*函數(shù)功能將元素e插入到隊(duì)列Q中|*入口參數(shù)SqQueue類(lèi)