數(shù)據(jù)結(jié)構(gòu)實驗(共13頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)實驗報告實驗序號：4 實驗項目名稱：棧的操作學(xué)號姓名專業(yè)、班實驗地點指導(dǎo)教師實驗時間一、實驗?zāi)康募耙?. 熟悉棧的基本概念；2. 掌握棧的順序存儲結(jié)構(gòu)；3掌握棧的應(yīng)用。二、實驗設(shè)備（環(huán)境）及要求微型計算機(jī)；windows 操作系統(tǒng)；Microsoft Visual Studio 6.0集成開發(fā)環(huán)境。三、實驗內(nèi)容與步驟1.棧的順序表表示和實現(xiàn)的如下：#include <iostream>#define MaxSize 100using namespace std;typedef int ElemType;typedef structElemType

2、 dataMaxSize;int top;SqStack;void InitStack(SqStack *st) /初始化棧st->top=-1;int StackEmpty(SqStack *st) /判斷棧為空return (st->top=-1);void Push(SqStack *st,ElemType x) /元素進(jìn)棧if(st->top=MaxSize-1)printf("棧上溢出!n");elsest->top+; /移動棧頂位置st->datast->top=x; /元素進(jìn)棧void Pop(SqStack *st,El

3、emType &e) /出棧if(st->top=-1)printf("棧下溢出n");elsee=st->datast->top; /元素出棧st->top-; /移動棧頂位置int main()SqStack L;SqStack *st=&L;ElemType e;int i;InitStack(st);for(i=1;i<10;+i)Push(st,i);printf("入棧元素是：%dn",i);for(i=1;i<10;+i)Pop(st,e);printf("出棧元素是：%dn&q

4、uot;,e);return 0; 改寫以上程序，實現(xiàn)功能如下：1）調(diào)用棧操作函數(shù)實現(xiàn)判別一個算術(shù)表達(dá)式中的圓括號配對是否正確。2）改寫Push和Pop函數(shù)，使得以上兩個函數(shù)可以一次性將一個數(shù)組入棧和出棧。（1）（2）2.C/C+的庫函數(shù)中已經(jīng)實現(xiàn)了棧，實例如下：#include<stack> /引入棧using namespace std;int main()int a;stack<int>s;scanf("%d",&a);s.push(a); /入棧printf("%dn",s.top(); /取得棧頂元素輸出s.po

5、p(); /出棧return 0; 請根據(jù)以上程序，設(shè)計算法如下：判別一個算術(shù)表達(dá)式中的圓括號和方括號配對是否正確。四、分析與討論五、教師評語簽名：日期：成績附源程序清單：1.（1）#include <stdio.h>#define MaxSize 100#define SUCCESS 0#define ERROR -1typedef structint nDataMaxSize;int nTop;SqStack;void InitStack(SqStack *PST_List) /初始化棧PST_List ->nTop = -1;int StackEmpty(SqStack

6、 *PST_List) /判斷棧為空if (PST_List ->nTop = -1)return ERROR;elsereturn SUCCESS;void Push(SqStack *PST_List, int nData) /元素進(jìn)棧if (PST_List ->nTop = MaxSize - 1)printf("棧上溢出!n");elsePST_List ->nTop+; /移動棧頂位置PST_List ->nDataPST_List->nTop = nData; /元素進(jìn)棧void Pop(SqStack *PST_List, in

7、t *pnData) /出棧if (PST_List ->nTop = -1)printf("棧下溢出n");elsepnData = &PST_List ->nDataPST_List ->nTop; /元素出棧PST_List ->nTop-; /移動棧頂位置int GetTop(SqStack *PST_List) /獲取棧頂if ( ! StackEmpty(PST_List) ) /先判斷是否為空棧,不是空棧則返回棧頂return (PST_List->nDataPST_List ->nTop);elsereturn E

8、RROR;int JudgeBrackets(SqStack *PST_List) /判斷圓括號是否配對成功char cData;/輸入變量int nSign = 0;/判斷標(biāo)志int *pnData = NULL;/傳入pop中的參數(shù)printf("請輸入一個表達(dá)式：");cData = getchar();while (cData != 'n') /按下回車結(jié)束死循環(huán)switch (cData)case '(': /對于左括號就入棧Push(PST_List, (int)cData); break;case ')':if

9、(GetTop(PST_List) = '(') /棧頂有左括號就出棧Pop(PST_List, pnData);else /否則就將判斷標(biāo)志置1nSign = 1;break;default: /對于其他的輸入不做操作 break;cData = getchar();if (GetTop(PST_List) = '(') /結(jié)束輸入后判斷棧頂是否還有左括號nSign = 1;if (nSign = 1)printf("圓括號配對不成功！n");elseprintf("圓括號配對成功！n");return SUCCESS;

10、int main()SqStack ST_List;SqStack *PST_List = &ST_List;/int nData;/int nIndex;InitStack(PST_List);JudgeBrackets(PST_List);/*for(nIndex = 1; nIndex < 10; +nIndex)Push(PST_List, nIndex);printf("入棧元素是：%dn", nIndex);for(nIndex = 1; nIndex < 10; +nIndex)Pop(PST_List, nData);printf(&qu

11、ot;出棧元素是：%dn", nData);*/return 0; （2）void Push(SqStack *PST_List, int *pnData, int nLength) /元素進(jìn)棧int nIndex = 0;if (PST_List ->nTop = MaxSize - 1)printf("棧上溢出!n");elseif( ( MaxSize - PST_List ->nTop - 1) >= nLength) /判斷棧剩余空間是否大于要入棧的元素個數(shù)for(nIndex = 0; nIndex < nLength; nIn

12、dex+)PST_List ->nTop+; /移動棧頂位置 PST_List ->nDataPST_List->nTop = pnDatanIndex; /元素進(jìn)棧printf("入棧元素為: %d n", PST_List ->nDataPST_List->nTop);printf("元素進(jìn)棧成功!n");else /?？臻g小于要入棧元素的個數(shù)，只入棧剩余空間大小的元素個數(shù)printf("?？臻g只剩 %d 個， 而數(shù)組元素有 %d 個，所以只入棧 %d 個!n", (MaxSize - PST_Lis

13、t ->nTop -1 ), nLength, (MaxSize - PST_List ->nTop - 1);nLength = MaxSize - PST_List ->nTop - 1; /長度賦值為剩余空間大小for(nIndex = 0; nIndex < nLength; nIndex+)PST_List ->nTop+; /移動棧頂位置 PST_List ->nDataPST_List->nTop = pnDatanIndex; /元素進(jìn)棧printf("入棧元素為: %d n", PST_List ->nDat

14、aPST_List->nTop);printf("元素進(jìn)棧成功!n");void Pop(SqStack *PST_List, int *pnData, int nLength) /出棧int nIndex = 0 ;if (PST_List ->nTop = -1)printf("棧下溢出n");elseif( nLength <= PST_List ->nTop + 1)/要出棧元素個數(shù)小于當(dāng)前棧頂for(nIndex = 0; nIndex < nLength; nIndex+) pnDatanIndex = PST_

15、List ->nDataPST_List ->nTop; /元素出棧printf("出棧元素是：%dn", PST_List ->nDataPST_List ->nTop); PST_List ->nTop-; /移動棧頂位置printf("元素出棧成功!n");else /要出棧元素個數(shù)大于當(dāng)前棧頂，把棧內(nèi)全部元素出棧nLength = PST_List ->nTop + 1;for(nIndex = 0; nIndex < nLength; nIndex+)pnDatanIndex = PST_List -&

16、gt;nDataPST_List ->nTop; /元素出棧printf("出棧元素是：%dn", PST_List ->nDataPST_List ->nTop); PST_List ->nTop-; /移動棧頂位置printf("元素出棧成功!n");2.#include<stack> /引入棧#include<stdio.h>using namespace std;int main()char cBuff;int nSign = 0; /判斷標(biāo)志，初值為0stack<char>StList

17、;printf("輸入表達(dá)式，以 # 號結(jié)束輸入!n");doscanf("%c", &cBuff);switch (cBuff)case '':StList.push(cBuff); /入棧/printf("入棧：%cn", cBuff);break;case '(':StList.push(cBuff); /入棧/printf("入棧：%cn", cBuff);break;case ')':if(StList.empty() /對于一開始就輸入")"的情況作出判斷，直接配對失敗 nSign = -1;elseif (StList.top() = '(') /取得棧頂元素輸出 /出棧 /printf("出棧：%cn", StList.top(); StList.pop(); else nSign = -1; break;case '':if(StList.empty() /對于一開始就輸入""的情況作出判斷，直接配對失敗 nSign = -1;elseif (StList.top() = '') /取得棧頂元素輸