實驗三棧和隊列及其應(yīng)用

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

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

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

4、s.h" I/cmd 窗口設(shè)置函數(shù)頭文件#inelude "ADT.h"/數(shù)據(jù)結(jié)構(gòu)中相關(guān)結(jié)構(gòu)體類型定義與相關(guān)數(shù)據(jù)類型定義#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)實驗實驗三：棧和隊列與其應(yīng)用I" );/設(shè)置cmd窗口標題system( "color F1" );/設(shè)置控制臺窗口的背景色和

5、前景色system( "date /T" );/輸岀當前的日期pri nt();cout << "實驗內(nèi)容一：采用順序存儲結(jié)構(gòu)，實現(xiàn)棧的存儲和根本操作"<< endl;SqStack S;SEIemTypee;InitStack Sq(S);/ 構(gòu)造一個空棧 Sint count;cout << "請輸入需入棧的元素個數(shù)：N ="cin >> cou nt;cout << "請輸入元素：”；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.將十進制數(shù)轉(zhuǎn)換為二進制數(shù)“ <<en dl;DecToBi n();/將十

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

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

9、;< data << endl;cout << "岀隊列："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ù)類型

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

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

12、100/循環(huán)隊列最大長度/*隊列順序存儲結(jié)構(gòu)類型定義-*/typedefstructQEIemType*base;/隊列初始化動態(tài)分配存儲空間int front;/對頭指針向量，隊列不空，指向隊頭元素int rear;/隊尾指針向量，隊列不空，指向隊尾下一個位置SqQueue順序隊列結(jié)構(gòu)類型#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)造一個空順序棧 SStatusGetTop_Sq( SqStack &S, SEIemType&e);/返回棧頂元素 eStatusStackEmpty_Sq( SqStack &S);/判斷棧 S是否為空StatusDestoryStack_Sq( SqStack &S);/銷毀順序棧 SStatusPush_Sq( SqStack &S, SElemTypee);/元素 e壓入順序棧StatusPop_Sq( SqStack &S, SElemT

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

15、&Q, QEIemTypee); II 將元素 e插入到隊列 Q中Status DeQueue_SqSqQueue&Q, QEIemType&e); II 將元素 e從順序隊列中刪除并返 回Status InverseQueue_Sq( SqQueue&Q);II 實現(xiàn)隊列的逆置/*功能函數(shù)定義區(qū)*/I*棧結(jié)構(gòu)函數(shù)定義 *II*函數(shù)原型Status In itStack_Sq(SqStack &S)*函數(shù)功能構(gòu)造一個空棧S*入口參數(shù)SqStack類型的結(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ù)功能銷毀棧S*入口參數(shù)SqStack類型的結(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ù)功能將十進制數(shù)轉(zhuǎn)換為二進制*入口參數(shù)void*出口參數(shù)返回函數(shù)結(jié)果狀態(tài)*/Status DecToB

19、in( void )LinkStack S;SElemTypee;long data;printf("請輸入待轉(zhuǎn)換的十進制數(shù)：");scanf s( "%d", &data);In itStack_L(S);while (data)Push_L(S, data % 2); data = data / 2;pri ntf("轉(zhuǎ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)造一個空隊列Q*入口參數(shù)SqQueue類型的結(jié)構(gòu)體變量C的引用&Q*出口參數(shù)返回函數(shù)結(jié)果狀態(tài)隊列結(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、此次實驗完成了對順序存儲結(jié)構(gòu)的棧和隊列的根本操作與簡單應(yīng)用， 加深了對課本知識的理解和掌握。此次實驗相對較容易，但卻是很根底的， 在以后的二叉樹、圖等高級數(shù)據(jù)結(jié)構(gòu)都需要用到它，所以棧和隊列是非常重 要的，有些細節(jié)局部是值得高度重視的，也是容易出錯的地方。2、 棧頂指針指向的是棧頂元素的下一個位置，在進展出棧操作時，應(yīng)先 將棧頂指針向量自減，指向棧頂元素，才能保證棧中元素正確出棧。當進展 連續(xù)入隊列操作時，要改變的是隊尾指針的指向，而不是隊頭指針；雖然初 始狀態(tài)

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