課程實驗報告+2

1、課程實驗報告專業(yè)年級2012級軟件工程課程名稱數(shù)據(jù)結(jié)構(gòu)C語言描述指導教師申紅婷學生姓名王曉霞學號實驗日期實驗地點A3篤行樓A棟306實驗成績教務(wù)處制2013年10月07日實驗項目棧和隊列實驗名稱目的：1.使學生對棧和隊列的順序存儲結(jié)構(gòu)和鏈式結(jié)構(gòu)、基本操作和應(yīng)用，能通過實驗達到掌握和應(yīng)用的目的。實驗2.要求學生對棧和隊列的順序存儲結(jié)構(gòu)和鏈式結(jié)構(gòu)的基本操作均作驗證性實驗，對棧和列的應(yīng)用各作一個設(shè)計性實驗，并寫出實驗報告。目的及要求二.要求：實驗前認真預習實驗內(nèi)容，實驗時自覺遵守課堂紀律，嚴格按操作規(guī)程操作，既要獨立操作又要與其他同學配合，在實驗過程中必須按照實驗內(nèi)容認真做完實驗實驗實驗認真填寫相關(guān)

2、實驗報告。棧和隊列的順序存儲結(jié)構(gòu)和鏈式結(jié)構(gòu)、基本操作和應(yīng)用。內(nèi)容1、閱讀下面程序，將函數(shù)Push和函數(shù)Pop補充完整。要求輸入元素序列12345e,運行結(jié)果如下所示。#include實驗步驟實驗步驟#include#defineERROR0#defineOK1#defineSTACK_INT_SIZE10/*存儲空間初始分配量*/#defineSTACKINCREMENT5/*存儲空間分配增量*/typedefintElemType;/*疋義兀素的類型*/typedefstructElemType*base;ElemType*top;intstacksize;/*當前已分配的存儲空間*/SqS

3、tack;intInitStack(SqStack*S);/*構(gòu)造空棧*/intpush(SqStack*S,ElemTypee);/*入棧*/intPop(SqStack*S,ElemType*e);/*出棧*/intCreateStack(SqStack*S);/*創(chuàng)建棧*/voidPrintStack(SqStack*S);/*出棧并輸出棧中元素*/intInitStack(SqStack*S)S-base=(ElemType*)malloc(STACK_INT_SIZE*sizeof(ElemType);if(!S-base)returnERROR;S_top=S_base;S-sta

4、cksize=STACK_INT_SIZE;returnOK;/*lnitStack*/intPush(SqStack*S,ElemTypee)if(S-top-S-base=S-stacksize)S-base=(ElemType*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(ElemType);S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;*S-top+=e;return1;/*Push*/intPop(SqStack*S,ElemType*e)if(S-top!=S-ba

5、se)*e=*-S-top;return1;elsereturn0;/*Pop*/intCreateStack(SqStack*S)inte;if(lnitStack(S)printf(InitSuccess!n);elseprintf(InitFail!n);returnERROR;printf(inputdata:(Terminatedbyinputingacharacter)n);while(scanf(%d,&e)Push(S,e);returnOK;/*CreateStack*/voidPrintStack(SqStack*S)ElemTypee;while(Pop(S,&e)pri

6、ntf(%3d,e);/*Pop_and_Print*/intmain()SqStackss;printf(n1-createStackn);CreateStack(&ss);printf(n2-Pop&Printn);PrintStack(&ss);printf(n);return0;算法分析：輸入元素序列12345,為什么輸出序列為54321?體現(xiàn)了棧的什么特性？程序運行結(jié)果如下圖所示：r*C:Windowssystem32Debugfgf.?Kelcrea七InitSuccess*Inputdata：2-Pop&Print74S985Presskeytocontinuea因為當main函

7、數(shù)調(diào)用PrintStack(&ss)時，程序轉(zhuǎn)到函數(shù)體中，而在該函數(shù)體內(nèi)，又調(diào)用了intPop(SqStack*S,ElemType*e)，此函數(shù)的功能是棧S的棧頂元素退棧并返回其值。所以輸入元素序列12345，輸出序列為54321。而這則體現(xiàn)了棧是只允許在表的一端進行操作的線性表并且具有先進后出的特性。2、在第1題的程序中，編寫一個十進制轉(zhuǎn)換為二進制的數(shù)制轉(zhuǎn)換算法函數(shù)(要求利用棧來實現(xiàn))，并驗證其正確性。實現(xiàn)代碼voidconveshen(SqStack*S)ElemTypen,h;intm=0,k=0;InitStack(S);printf(lnputelementn);scanf(%d,

8、&n);while(n)m+;Push(S,n%2);n=n/2;while(km)k+;Pop(S,&h);printf(%d,h);intmain()SqStackS;conveshen(&S);printf(n);return0;驗證C:V7indowssystem32Debugfgd,exeF,Inputelement2511001Pressanykeytocontinue3、閱讀并運行程序，并分析程序功能#include#include#include#defineM20#defineelemtypechartypedefstructelemtypestackM;inttop;sta

9、cknode;voidinit(stacknode*st);voidpush(stacknode*st,elemtypex);voidpop(stacknode*st);voidinit(stacknode*st)st-top=0;voidpush(stacknode*st,elemtypex)if(st-top=M)printf(thestackisoverflow!n);elsest_top=st_top+1;st-stackst-top=x;voidpop(stacknode*st)if(st-top0)st-top-;elseprintf(StackisEmpty!n);intmain

10、()charsM;inti;stacknode*sp;printf(createaemptystack!n);sp=malloc(sizeof(stacknode);init(sp);printf(inputaexpression:n);gets(s);for(i=0;itop=O)printf(match)!n”);elseprintf(notmatch)!n”);return0;輸入:2+(c-d)*6-(f-7)*a)/6運行結(jié)果：f9、Windowssystem32Debugfgd.exehpeteaEmptystack!inputaexpression:2+*6-C-75Ma/6CJ

11、match*J*Pi*es：Snykeytocorktxnue輸入：a-(c-d)*6-(s/3-x)/2運行結(jié)果:-C:Windov;ssystem32Debugfgd.execreateaemptystack*i.nputaexpression:a-Ccd?*6s/3xJ/21J*Pressan9kevtocontinue程序的基本功能判斷所輸入多項式的左右括號是否配對運行環(huán)境說明實驗環(huán)境PC計算機，Windows2000(或WindowsXP)及以上版本，C基礎(chǔ)數(shù)據(jù)設(shè)置及說明計算機，Windows2000(或WindowsXP)及以上版本，C均能正常運行TOCo1-5hz通過這次實驗，我已經(jīng)基本掌握了本章的學習要點和實驗的基本要求以及目的。第一個程序填空題使我學會了棧和隊列的結(jié)構(gòu)定義，邏輯特性及其基本操作的使用。而第二個程序分析則使我明白了棧和隊列的順序存儲表示和鏈式存儲表示，這使得我懂得了該在什么情況下分別實用兩種存儲表示并用程序代碼實現(xiàn)它們相應(yīng)的操作。雖然我最終順利完成了實驗，但是在實驗過程中我也遇到了許多問題，比如說，不清楚實驗結(jié)果與分析實驗結(jié)果與分析棧和隊列的結(jié)構(gòu)定義以至于在后續(xù)過