數(shù)據(jù)結(jié)構(gòu)大作業(yè)

1、浙江大學(xué)城市學(xué)院實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)實(shí)驗(yàn)項(xiàng)目名稱 實(shí)驗(yàn)九 棧的應(yīng)用學(xué)生姓名丁汀專業(yè)班級(jí)信管1006 學(xué)號(hào)實(shí)驗(yàn)成績 指導(dǎo)老師（簽名）日期一.實(shí)驗(yàn)?zāi)康暮鸵?、學(xué)會(huì)通過對(duì)問題的分析，設(shè)計(jì)一種合理的數(shù)據(jù)結(jié)構(gòu)，并進(jìn)行定義及操作的實(shí) 現(xiàn)。2、掌握利用棧各種操作來進(jìn)行具體的實(shí)際應(yīng)用。3、加強(qiáng)綜合程序的分析、設(shè)計(jì)能力。二.實(shí)驗(yàn)內(nèi)容1、共享?xiàng)５脑O(shè)置，問題描述如下：在一個(gè)數(shù)組空間stackMaxSize#可以同時(shí)存放兩個(gè)順序棧，棧底分別處在數(shù) 組的兩端，當(dāng)?shù)?個(gè)棧的棧頂指針topi等于一1時(shí)則棧1為空，當(dāng)?shù)?個(gè)棧的 棧頂指針top2等于MaxSize時(shí)則棧2為空。兩個(gè)棧均向中間增長，當(dāng)有元素向 棧1進(jìn)棧

2、時(shí)，使top1增1得到新的棧頂位置，當(dāng)有元素向棧 2進(jìn)棧時(shí)，使top2 減1得到新的棧頂位置。當(dāng)top1=top2-1或top1+1=top2時(shí)，存儲(chǔ)空間用完， 無法再向任一棧做進(jìn)棧操作，此時(shí)可考慮給出錯(cuò)誤信息并停止運(yùn)行。要求： 給出共享?xiàng)５捻樞虼鎯?chǔ)類型定義。 給出共享?xiàng)５某橄髷?shù)據(jù)類型定義。建立頭文件，包含共享?xiàng)５幕静僮鲗?shí)現(xiàn)函數(shù)；建立主程序文件，在主函數(shù) 中對(duì)共享?xiàng)５母鱾€(gè)操作進(jìn)行測(cè)試。2、利用上述共享?xiàng)?，?shí)現(xiàn)火車車廂的調(diào)度模擬設(shè)火車車廂分為三類：硬座、硬臥、軟臥，分別用 A、B、C表示。下圖描述 車廂調(diào)度的示意圖，圖中右端為排列無序的車廂，左端為調(diào)度后的車廂排列，使 得所有軟臥車廂在最前面、

3、所有硬臥車廂在中間、所有硬座車廂在最后。編程模擬上述車廂調(diào)度過程。提示：兩個(gè)輔助鐵軌相當(dāng)于兩個(gè)棧，右端車廂進(jìn)入用相應(yīng)字符串給出，如 “BBACBCAABBCAa左端車廂的用新生成的字符串給出。在 給出模擬函數(shù)，并 在主函數(shù)中進(jìn)行調(diào)用測(cè)試。CCCBBBBBAAAAABBACBCAABBCAA鐵軌3、填寫實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告文件取名為。4、上傳實(shí)驗(yàn)報(bào)告文件、源程序文件及到Ftp服務(wù)器上()的文件夾下。三.抽象數(shù)據(jù)類型定義ADT STACK isData:元素具有ElemType類型的棧，用標(biāo)示符StackType表示棧對(duì)象類型 Operation:void InitStack(Stack &

4、S)操作結(jié)果：初始化棧S,即構(gòu)造一個(gè)空棧 Svoid Push(Stack &S, ElemType item,int i)操作結(jié)果：元素item進(jìn)棧，作為新的棧頂元素ElemType Pop(Stack &S,int i)操作結(jié)果：棧頂元素出棧，并返回其值ElemType Peek(Stack S,int i)操作結(jié)果：取S當(dāng)前棧頂元素，并返回，但元素不出棧End STACK四.存儲(chǔ)結(jié)構(gòu)定義及算法思路一、定義共建棧的相關(guān)屬性struct Stack ElemType *stack ;實(shí)驗(yàn)結(jié)果與分析B一回W任意輸入 T串字符其中n表示褒座.日表示屈臥.c表示軟臥”Bi 舊CRc

5、anRBC白口CCC DBS A ft A A A Pi*eany ky to cont: inue六.心得體會(huì)【附錄-源程序】#include<>#include<>typedef char ElemType;struct Stack ElemType *stack ;int topi;int MaxSize;int top2;；#include ""void main()Stack s;char a20;int i,j,m=0,n=0;InitStack(s);coutvv”任意輸入一用字符(其中A表示硬座，B表示硬臥，C表示軟 臥):"

6、;<<endl;i=0;cin>>a;while(ai='A'|ai='B'|ai='C') if(ai='C')cout<<ai;else if(ai='B')Push(s,ai);m+;elsePush(s,ai);n+;i+;for(i=0;i<m;i+)cout<<Pop(s);for(j=0;j<n;j+)cout<<Pop(s); void InitStack(Stack &S)=20;=new ElemType口；if(!cerr<<”動(dòng)態(tài)申請(qǐng)失敗!"<<endl;exit；=-1;=;bool EmptyStack(Stack &S)return =-1&&=;void Push(Stack &S, ElemType item)!"<<endl;if=cout<<"棧已經(jīng)全滿，沒有多余的空間存放元素elseif(item='B')+;=item;if(item='A');=item;ElemType Pop(Stack &S