1、課程實驗報告記錄+2作者:日期:課程實驗報告專業年級2012級軟件工程課程名稱 數據結構C語言描述指導教師申紅婷學生姓名王曉霞學號 20122205041002實驗日期2012.11.7實驗地 點 A3篤行樓A棟306實驗成績教務處制2013年10月07日實驗項目名稱棧和隊列實驗一.目的：1使學生對棧和隊列的順序存儲結構和鏈式結構、基本操作和應用，能通過實驗 達到掌握和應用的目的。實驗目的及要求2 要求學生對棧和隊列的順序存儲結構和鏈式結構的基本操作均作驗證性實驗， 對棧和列的應用各作一個設計性實驗，并寫出實驗報告。二要求：實驗前認真預習實驗內容，實驗時自覺遵守課堂紀律，嚴格按操作規程操作，既

2、要獨立操作又要與其他同學配合，在實驗過程中必須按照實驗內容認真做完實驗，并認真填寫相關實驗報告。實驗內容棧和隊列的順序存儲結構和鏈式結構、基本操作和應用。1、閱讀下面程序，將函數Push和函數Pop補充完整。要求輸入元素序列1 2 3 4 5e,運行結果如下所示。#in clude<stdio.h>#in clude<malloc.h>實驗步驟#defi ne ERROR 0 #defi ne OK 1#defi ne STACK_INT_SIZE 10 /*#defi ne STACKINCREMENT 5 /* typedef int ElemType; /* ty

3、pedef structElemType *base;存儲空間初始分配量*/存儲空間分配增量*/定義元素的類型*/當前已分配的存儲空間*/ElemType *top; int stacksize; /* SqStack;intlnitStack(SqStack *S); /*構造空棧 */in t push(SqStack *S,ElemType e); /*入棧 */int Pop(SqStack *S,ElemType *e); /*出棧 */int CreateStack(SqStack *S);/*創建棧 */void Prin tStack(SqStack *S); /*出棧并輸出棧

4、中元素 */int In itStack(SqStack *S)S->base=(ElemType*)malloc(STACK_INT_SIZE*sizeof(ElemType);if(!S->base) return ERROR;S->top=S->base;S->stacksize=STACK_INT_SIZE;return OK;/*lni tStack*/int Push(SqStack *S,ElemType e)if (S->top-S->base>=S->stacksize)S->base=(ElemType*)real

5、loc( S->base,(S->stacksize+STACKINCREME NT)*sizeof(ElemType);S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT;*S_>top+=e;return 1;/*Push*/int Pop(SqStack *S,ElemType *e)if (S->top!=S->base)*e=*-S->top;return 1;elsereturn 0;/*Pop*/int CreateStack(SqStack *S)int

6、e;if(lni tStack(S)printf("Init Success!n");elseprintf("Init Fail!n");return ERROR;prin tf("i nput data:(Term in ated by in put ing a character)n");while(sca nf("%d", &e)Push(S,e);return OK;/*CreateStack*/void Prin tStack(SqStack *S)ElemType e;while(Pop(S,

7、&e)prin tf("%3d",e);/*Pop_a nd_Pri nt*/int mai n()SqStack ss;prin tf("n1-createStack n");CreateStack(&ss);prin tf("n2-Pop&Prin tn");Prin tStack(&ss);prin tf("n");return 0;算法分析：輸入元素序列1 2 3 4 5 ，為什么輸出序列為5 4 3 2 1?體現了棧的什么特性？程序運行結果如下圖所示：'CAV/i

8、nd owssystem 3 2Debu gXfgf exe"t-createStackI nitinput data: CTerrtirtftt&d by input;in$| a GharaEtci'?5 8 ? & 4 ? c2PopftPpint74 b 985Pr&ss 質ny key to因為當main函數調用PrintStack(&ss)時，程序轉到函數體中，而在該函數體內，又調用了 int Pop(SqStack *S,ElemType *e)，此函數的功能是棧 S的棧頂元素退棧并返回其值。所以輸入元素序列 1 2345 ，輸出

9、序列為54 3 2 1 。而這則 體現了棧是只允許在表的一端進行操作的線性表并且具有先進后出的特性。2 、在第1題的程序中，編寫一個十進制轉換為二進制的數制轉換算法函數(要求利用棧來實現)，并驗證其正確性。實現代碼void con veshe n( SqStack *S)ElemType n,h;int m=O,k=O;Ini tStack(S);prin tf("l nput eleme nt n");scan f("%d", &n);while( n) m+;Push(S, n%2); n=n/2;while(k<m)k+;Pop(S,

10、&h);prin tf("%d",h);int mai n()SqStack S;con veshe n(&S);prin tf("n");return 0;驗證' C:Wi nd ows'5/sterr 3 2De txj gVgdxxe"Input elenent2E11001Press 曰ny Jsep to continue3、閱讀并運行程序，并分析程序功能。#in clude<stdio.h>#in clude<malloc.h>#in clude<stri ng.h>

11、;#defi ne M 20#defi ne elemtype char typedef structelemtype stackM;int top;stack no de;void in it(stack node *st);void push(stack node *st,elemtype x);void pop(stack node *st);void in it(stack node *st)st->top=0;void push(stack node *st,elemtype x)if(st->top=M)prin tf("the stack is overfl

12、ow!' n");elsest_>top=st_>top+1;st->stackst->top=x;void pop(stack node *st)if(st->top>0) st->top-;else printf(“ Stack is Empty!n” );int mai n()char sM;int i;stack node *sp;prin tf("create a empty stack!' n");sp=malloc(sizeof(stack no de);ini t(sp);prin tf(&

13、quot;i nput a expressi on :n");gets(s);for(i=0;i<strle n( s);i+)if(si='(')push(sp,si);if(si=')')pop(sp);if(sp->top=0)prin tf("'('match')'!n");elseprin tf("'(' not match')'!'n ”);return 0;輸入：2+(c-d)*6-(f-7)*a)/6運行結果：輸入：a-(c

14、-d)*6-(s/3-x)/2運行結果：i- 'CAW i nd W5system 32De bu gfgd.exe'cr'cate a enpt y stack? input 孔ss ioft:-<s/3-x>/21 < J no t match' > ' !Pi*ess anp key to continue實驗環境實驗結果與分析程序的基本功能：判斷所輸入多項式的左右括號是否配對。(一) 運行環境說明PC計算機，Windows 2000(或 Windows XP)及以上版本，C(二) 基礎數據設置及說明計算機，Windows 2000(或 Windows XP)及以上版本，C均能正常運行。通過這次實驗，我已經基本掌握了本章的學習要點和實驗的基本要求以及目的。第一個程序填空題使我學會了棧和隊列的結構定義，邏輯特性及其基本操作的使用。而第二個程序分析則使我明白了棧和隊列的順序存儲表示和鏈式存儲表示，這使得我懂得了該在什么情況下分別實用兩種存儲表示并用程序代碼實現它們相應的操作。雖然我