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

1、電子信息工程學(xué)院2013級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告姓名學(xué)號(hào)實(shí)驗(yàn)項(xiàng)目棧和隊(duì)列及其應(yīng)用（I）實(shí)驗(yàn)內(nèi)容1采用順序存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)棧的存儲(chǔ)和基本操作。棧的抽象數(shù)據(jù)類型定義參見(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ù)類型定義參見(jiàn)教材第59頁(yè)。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)定義參見(jiàn)教材第64頁(yè)。算法設(shè)計(jì)與程序?qū)崿F(xiàn)：算法分析 本次實(shí)驗(yàn)主函數(shù)采用順序結(jié)構(gòu)，主函數(shù)調(diào)用自己編寫(xiě)的頭文件DataStructure_LinearList.h中的相關(guān)功能函數(shù)，完成實(shí)驗(yàn)要求。 程序?qū)崿F(xiàn)步驟：1、順序棧結(jié)構(gòu)的基本操作：首先初始化一個(gè)順序棧結(jié)構(gòu)，然后輸入需入棧的元素個(gè)數(shù)N，通過(guò)

2、一個(gè)循環(huán)依次輸入N個(gè)元素，在輸入的同時(shí)調(diào)用入棧函數(shù),這樣就完成了N個(gè)元素的入棧操作，隨后調(diào)用返回棧頂元素的函數(shù)，返回棧頂元素，接著通過(guò)循環(huán)調(diào)用出棧函數(shù)完成出棧操作，最后銷毀棧結(jié)構(gòu)。當(dāng)然在進(jìn)行入棧和出棧操作時(shí)，會(huì)使用判斷棧是否為空、對(duì)棧進(jìn)行遍歷等操作，這樣就實(shí)現(xiàn)了對(duì)棧的基本操作。2、棧結(jié)構(gòu)的基本應(yīng)用：（1）將輸入的十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)。首先初始化一個(gè)棧結(jié)構(gòu)，構(gòu)造一個(gè)空棧，然后輸入十進(jìn)制數(shù)N，根據(jù)十進(jìn)制轉(zhuǎn)換為二進(jìn)制的方法（除二取余法）通過(guò)循環(huán)判斷將每次除二求模的數(shù)入棧，接著通過(guò)判斷棧空條件，依次將棧中的元素出棧，然后輸出這樣就實(shí)現(xiàn)了十進(jìn)制對(duì)二進(jìn)制的轉(zhuǎn)換，當(dāng)然其他進(jìn)制之間的也是如此。（2）Hano

3、i問(wèn)題的實(shí)現(xiàn)。其主要思想就是遞歸，在進(jìn)行遞歸調(diào)用函數(shù)本身的時(shí)候，參數(shù)的傳遞、變量保存以及函數(shù)返回都使用了棧結(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ì)列操作，最后銷毀順序隊(duì)列結(jié)構(gòu)，這樣就實(shí)現(xiàn)了對(duì)棧的基本操作。核心程序此程序中用到的自己編寫(xiě)的頭文件以在下面給出，而頭文件的說(shuō)明則在主函數(shù)中文件包含部分的注釋處，核心程序如下：1.主函數(shù)如下：#include "iost

4、ream" /標(biāo)準(zhǔn)輸入輸出流庫(kù)文件#include "windows.h" /cmd窗口設(shè)置函數(shù)頭文件#include "ADT.h" /數(shù)據(jù)結(jié)構(gòu)中相關(guān)結(jié)構(gòu)體類型定義及相關(guān)數(shù)據(jù)類型定義#include "DataStructure_LinearList.h" /數(shù)據(jù)結(jié)構(gòu)第二章線性表中相關(guān)函數(shù)的定義及聲明using namespace 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)題

5、system("color F1"); /設(shè)置控制臺(tái)窗口的背景色和前景色 system("date /T"); /輸出當(dāng)前的日期print();cout << "實(shí)驗(yàn)內(nèi)容一：采用順序存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)棧的存儲(chǔ)和基本操作" << endl;SqStack S;SElemType e;InitStack_Sq(S); /構(gòu)造一個(gè)空棧Sint count;cout << "請(qǐng)輸入需入棧的元素個(gè)數(shù)：N = "cin >> count;cout << "請(qǐng)輸入

6、元素："for (int i = 0; i < count; i+)cin >> 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 <<

7、 "1.將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)" << endl;DecToBin(); /將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)cout << "2.漢羅塔問(wèn)題" << endl << " 請(qǐng)輸入圓盤(pán)個(gè)數(shù)："int 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); /銷毀

8、棧Scout << endl;print();cout << "實(shí)驗(yàn)內(nèi)容二：采用順序存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)隊(duì)列的存儲(chǔ)和基本操作" << endl;SqQueue Q;QElemType data;InitQueue_Sq(Q); /構(gòu)造一個(gè)空隊(duì)列Qcout << "請(qǐng)輸入需入隊(duì)列的元素個(gè)數(shù)：N = "cin >> count;cout << "請(qǐng)輸入元素："for (int i = 0; i < count; i+)cin >> data;EnQueue

9、_Sq(Q, data);GetHead_Sq(Q, data);cout << " 隊(duì)首元素：" << data << endl;cout << " 出隊(duì)列："while (DeQueue_Sq(Q, data)cout << data << " "cout << endl;print();cout << endl;void print(void)cout << endl << "*" <

10、< endl;2.頭文件”ADT.h”的部分程序如下：#ifndef ADT_H_#define ADT_H_/* 常 量 和 數(shù) 據(jù) 類 型 預(yù) 定 義*/* -函數(shù)結(jié)果狀態(tài)代碼- */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/* -數(shù)據(jù)類型預(yù)定義- */typedef int Status; /函數(shù)結(jié)果狀態(tài)類型typedef int _bool; /bool狀態(tài)類型/* 數(shù) 據(jù) 結(jié) 構(gòu) 類 型 定 義*/*棧 和 隊(duì) 列*/* -棧數(shù)

11、據(jù)類型定義- */typedef int SElemType; /順序表中元素的數(shù)據(jù)類型/* -棧動(dòng)態(tài)存儲(chǔ)分配初始常量預(yù)定義- */#define STACK_INIT_SIZE 100 /棧表存儲(chǔ)空間的初始分配量#define STACKINCREMENT 10 /棧表存儲(chǔ)空間的分配增量/* -順序棧結(jié)構(gòu)類型定義- */typedef structSElemType * base; /棧底指針SElemType * top; /棧頂指針int stacksize; /當(dāng)前以分配的存儲(chǔ)空間SqStack; /順序棧結(jié)構(gòu)類型/* -隊(duì)列數(shù)據(jù)類型定義- */typedef int QElemTyp

12、e; /順序表中元素的數(shù)據(jù)類型/* -隊(duì)列動(dòng)態(tài)存儲(chǔ)分配初始常量預(yù)定義- */#define QUEUE_INIT_SIZE 100 /隊(duì)列存儲(chǔ)空間的初始分配量#define QUEUEINCREMENT 10 /隊(duì)列存儲(chǔ)空間的分配增量#define MAXQUEUESIZE 100 /循環(huán)隊(duì)列最大長(zhǎng)度/* -隊(duì)列順序存儲(chǔ)結(jié)構(gòu)類型定義- */typedef structQElemType *base; /隊(duì)列初始化動(dòng)態(tài)分配存儲(chǔ)空間int front; /對(duì)頭指針向量，隊(duì)列不空，指向隊(duì)頭元素int rear; /隊(duì)尾指針向量，隊(duì)列不空，指向隊(duì)尾下一個(gè)位置SqQueue; /順序隊(duì)列結(jié)構(gòu)類型#end

13、if /* ADT_H_ */3.頭文件"DataStructure_StackQueue.h"中部分函數(shù)定義如下：#include <stdio.h>#include <malloc.h>#include "ADT.h"/* 功 能 函 數(shù) 聲 明 區(qū)*/* -棧- */棧的基本操作Status InitStack_Sq(SqStack &S); /構(gòu)造一個(gè)空順序棧SStatus GetTop_Sq(SqStack &S, SElemType &e); /返回棧頂元素eStatus StackEmpty_

14、Sq(SqStack &S); /判斷棧S是否為空Status DestoryStack_Sq(SqStack &S); /銷毀順序棧SStatus Push_Sq(SqStack &S, SElemType e); /元素e壓入順序棧Status Pop_Sq(SqStack &S, SElemType &e); /元素e出棧/棧的應(yīng)用Status DecToBin(void); /十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)void Hanoi(int n, char x, char y, char z); /實(shí)現(xiàn)Hanoi問(wèn)題，借助y塔將x塔上的n個(gè)圓盤(pán)搬移到z塔上/*

15、 -隊(duì) 列- */隊(duì)列的基本操作Status InitQueue_Sq(SqQueue &Q); /構(gòu)造一個(gè)空的順序隊(duì)列QStatus GetHead_Sq(SqQueue &Q, QElemType &e); /返回順序隊(duì)列的隊(duì)頭元素eStatus EnQueue_Sq(SqQueue &Q, QElemType e); /將元素e插入到隊(duì)列Q中Status DeQueue_Sq(SqQueue &Q, QElemType &e); /將元素e從順序隊(duì)列中刪除并返回Status InverseQueue_Sq(SqQueue &Q);

16、/實(shí)現(xiàn)隊(duì)列的逆置/* 功 能 函 數(shù) 定 義 區(qū)*/*棧 結(jié) 構(gòu) 函 數(shù) 定 義*/* 函數(shù)原型：Status InitStack_Sq(SqStack &S) * 函數(shù)功能：構(gòu)造一個(gè)空棧S* 入口參數(shù)：SqStack類型的結(jié)構(gòu)體變量S的引用&S* 出口參數(shù)：返回函數(shù)結(jié)果狀態(tài)*/Status InitStack_Sq(SqStack &S)S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);if (!S.base) return(OVERFLOW);S.top = S.base;S.stack

17、size = STACK_INIT_SIZE;return OK; /InitStack_Sq/* 函數(shù)原型：Status DestoryStack_Sq(SqStack &S)* 函數(shù)功能：銷毀棧S* 入口參數(shù)：SqStack類型的結(jié)構(gòu)體變量S的引用&S* 出口參數(shù)：返回函數(shù)結(jié)果狀態(tài)*/Status DestoryStack_Sq(SqStack &S)SElemType *p;while (S.base != S.top)p = -S.top;free(p);return OK; /DestoryStack_Sq/* 函數(shù)原型：Status Push_Sq(SqSt

18、ack &S, SElemType e)* 函數(shù)功能：將元素e入棧* 入口參數(shù)：SqStack類型的結(jié)構(gòu)體變量S的引用&S,SElemType類型元素e* 出口參數(shù)：返回函數(shù)結(jié)果狀態(tài)*/Status Push_Sq(SqStack &S, SElemType e)SElemType *newbase;if (S.top - S.base >= S.stacksize)newbase = (SElemType *)realloc(S.base, (STACKINCREMENT + S.stacksize)*sizeof(SElemType);if (!newbase

19、)return OVERFLOW;S.base = newbase;S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;return OK; /Push_Sq/* 函數(shù)原型：Status Pop_Sq(SqStack &S, SElemType &e)* 函數(shù)功能：將元素e出棧* 入口參數(shù)：SqStack類型的結(jié)構(gòu)體變量S的引用&S,SElemType類型元素e的引用&e* 出口參數(shù)：返回函數(shù)結(jié)果狀態(tài)*/Status Pop_Sq(SqStack &S, SElem

20、Type &e)if (S.top = S.base)return ERROR;e = * -S.top;return OK; /Pop_Sq/* 函數(shù)原型：Status DecToBin(void)* 函數(shù)功能：將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制* 入口參數(shù)：void* 出口參數(shù)：返回函數(shù)結(jié)果狀態(tài)*/Status DecToBin(void)LinkStack S;SElemType e;long data;printf(" 請(qǐng)輸入待轉(zhuǎn)換的十進(jìn)制數(shù)：");scanf_s("%d", &data);InitStack_L(S);while (data

21、)Push_L(S, data % 2);data = data / 2;printf(" 轉(zhuǎn)換后的二進(jìn)制數(shù)：");while (S->next)Pop_L(S, e);printf("%d", e);printf("n");return OK; /DecToBin/*隊(duì) 列 結(jié) 構(gòu) 函 數(shù) 定 義*/* 函數(shù)原型：Status InitQueue_Sq(SqQueue &Q)* 函數(shù)功能：構(gòu)造一個(gè)空隊(duì)列Q* 入口參數(shù)：SqQueue類型的結(jié)構(gòu)體變量Q的引用 &Q* 出口參數(shù)：返回函數(shù)結(jié)果狀態(tài)*/Status I

22、nitQueue_Sq(SqQueue &Q)Q.base = (QElemType *)malloc(QUEUE_INIT_SIZE * sizeof(QElemType);if (!Q.base)return(OVERFLOW);Q.front = Q.rear = 0;return OK; /InitQueue_Sq/* 函數(shù)原型：Status GetHead_Sq(SqQueue &Q, QElemType &e)* 函數(shù)功能：若隊(duì)列不空，則返回隊(duì)頭元素e,并返回函數(shù)結(jié)果狀態(tài)OK，否則返回ERROR* 入口參數(shù)：SqQueue類型的結(jié)構(gòu)體變量Q的引用&Q

23、,QElemType類型元素e的引用&e* 出口參數(shù)：返回函數(shù)結(jié)果狀態(tài)*/Status GetHead_Sq(SqQueue &Q, QElemType &e)if (Q.front = Q.rear)return ERROR;e = Q.baseQ.rear - 1; /隊(duì)尾指針向量指向下一個(gè)元素return OK; /GetHead_Sq/* 函數(shù)原型：Status EnQueue_Sq(SqQueue &Q, QElemType e)* 函數(shù)功能：將元素e插入到隊(duì)列Q中* 入口參數(shù)：SqQueue類型的結(jié)構(gòu)體變量Q的引用&Q,QElemType類型元素e* 出口參數(shù)：返回函數(shù)結(jié)果狀態(tài)*/Status EnQueue_Sq(SqQueue &Q, QElemType e)QElemType *newbase;if (Q.front - Q.rear >= QUEUE_INIT_SIZE)newbase = (QElemType *)realloc(Q.base, (STACKINCREMENT + QUEUE_INIT_SIZE)*siz