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

1、電子信息工程學(xué)院2013級數(shù)據(jù)結(jié)構(gòu)實驗報告姓名學(xué)號實驗項目棧和隊列及其應(yīng)用（I）實驗內(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ù)采用順序結(jié)構(gòu)，主函數(shù)調(diào)用自己編寫的頭文件DataStructure_LinearList.h中的相關(guān)功能函數(shù)，完成實驗要求。 程序?qū)崿F(xiàn)步驟：1、順序棧結(jié)構(gòu)的基本操作：首先初始化一個順序棧結(jié)構(gòu)，然后輸入需入棧的元素個數(shù)N，通過

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

3、i問題的實現(xiàn)。其主要思想就是遞歸，在進行遞歸調(diào)用函數(shù)本身的時候，參數(shù)的傳遞、變量保存以及函數(shù)返回都使用了棧結(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ù)如下：#include "iost

4、ream" /標準輸入輸出流庫文件#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)實驗 實驗三：棧和隊列及其應(yīng)用（I） "); /設(shè)置cmd窗口標題

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

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.將十進制數(shù)轉(zhuǎn)換為二進制數(shù)" << endl;DecToBin(); /將十進制數(shù)轉(zhuǎn)換為二進制數(shù)cout << "2.漢羅塔問題" << endl << " 請輸入圓盤個數(shù)："int n; /圓盤個數(shù)char x = 'A', y = 'B', z = 'C'cin >> n;cout << "圓盤移動步驟："Hanoi(n, x, y, z);DestoryStack_Sq(S); /銷毀

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

9、_Sq(Q, data);GetHead_Sq(Q, data);cout << " 隊首元素：" << data << endl;cout << " 出隊列："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) 類 型 定 義*/*棧 和 隊 列*/* -棧數(shù)

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

12、e; /順序表中元素的數(shù)據(jù)類型/* -隊列動態(tài)存儲分配初始常量預(yù)定義- */#define QUEUE_INIT_SIZE 100 /隊列存儲空間的初始分配量#define QUEUEINCREMENT 10 /隊列存儲空間的分配增量#define MAXQUEUESIZE 100 /循環(huán)隊列最大長度/* -隊列順序存儲結(jié)構(gòu)類型定義- */typedef structQElemType *base; /隊列初始化動態(tài)分配存儲空間int front; /對頭指針向量，隊列不空，指向隊頭元素int rear; /隊尾指針向量，隊列不空，指向隊尾下一個位置SqQueue; /順序隊列結(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)造一個空順序棧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); /十進制數(shù)轉(zhuǎn)換為二進制數(shù)void Hanoi(int n, char x, char y, char z); /實現(xiàn)Hanoi問題，借助y塔將x塔上的n個圓盤搬移到z塔上/*

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

16、/實現(xiàn)隊列的逆置/* 功 能 函 數(shù) 定 義 區(qū)*/*棧 結(jié) 構(gòu) 函 數(shù) 定 義*/* 函數(shù)原型：Status InitStack_Sq(SqStack &S) * 函數(shù)功能：構(gòu)造一個空棧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ù)功能：將十進制數(shù)轉(zhuǎn)換為二進制* 入口參數(shù)：void* 出口參數(shù)：返回函數(shù)結(jié)果狀態(tài)*/Status DecToBin(void)LinkStack S;SElemType e;long data;printf(" 請輸入待轉(zhuǎn)換的十進制數(shù)：");scanf_s("%d", &data);InitStack_L(S);while (data

21、)Push_L(S, data % 2);data = data / 2;printf(" 轉(zhuǎn)換后的二進制數(shù)：");while (S->next)Pop_L(S, e);printf("%d", e);printf("n");return OK; /DecToBin/*隊 列 結(jié) 構(gòu) 函 數(shù) 定 義*/* 函數(shù)原型：Status InitQueue_Sq(SqQueue &Q)* 函數(shù)功能：構(gòu)造一個空隊列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ù)功能：若隊列不空，則返回隊頭元素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; /隊尾指針向量指向下一個元素return OK; /GetHead_Sq/* 函數(shù)原型：Status EnQueue_Sq(SqQueue &Q, QElemType e)* 函數(shù)功能：將元素e插入到隊列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