數(shù)據結構實驗報告5

1、數(shù)據結構實驗報告5數(shù)據結構實驗報告實驗 5學號：姓名：得分：、實驗目的1、復習棧的邏輯結構、存儲結構及基本操作;2、掌握順序棧、鏈棧。二、實驗內容1、(必做題)假設棧中數(shù)據兀素類型是字符型，請米 用順序棧實現(xiàn)棧的以下基本操作：(1) Status InitStack (&S)/構造空棧 S;(2) Status Push(&S, e)/元素 e入棧 S;(3) Status Pop(&S, &e)/棧 S 出棧，元素為 e。2、(必做題)請實現(xiàn)：對于一個可能包括括號、卜()的表達式，判定其中括號是否匹配。三、算法描述(采用自然語言描述)1.構建空棧S,輸入元素,

2、 棧中元素，輸出棧頂元素, 打印棧中元素。2構建空棧，輸入表達式,將元素依次入棧，遍歷打印 打印被輸出的元素，遍歷使用函數(shù)cou nt判斷表達式中括號是否匹配，如果匹配輸出匹配正確，不匹配則 輸出匹配錯誤。四、詳細設計1.L開J五、程序代碼(給出必要注釋)1.#i nclude<stdio.h>#in clude<stdlib.h>#defi ne MaxSize 100typedef struct no de* SqStack;typedef char ElemType;struct node/棧的數(shù)據結構int top;ElemType dataMaxSize;vo

3、id StatusInitStack(SqStack *L) 構造空棧 S (*L) = (SqStack*)malloc(sizeof(SqStack);(*L)->top = -1;void StatusPush(SqStack L, ElemType e) 元素 e入棧 S if (L->top = MaxSize - 1) printf(” 棧滿 n");elseL->top+;L->dataL->top = e;void StatusPop(SqStack L, ElemType *e) 棧 S 出棧， 元素為eif (L->top =

4、-1)printf("?？?n"); else!(.：舉誨辭YY酚"HU!d!(soe;s;iu|sn;e;s = A!X ¥sdXiiJU9|3 !s ed人丄uueim !s和印sbsOuieiut.uv.uud以!囘即vl £11o%11)uud(+! ；do;<-| => ! ：0 = !)Oj0 = ! A 審酚國豐 (1 >|OB；sbs);uud P!OA:do;<-|e;ep<-| = sea nf("%c", & e);while (e!='n')Sta

5、tusPush(s, e); sea nf("%c", & e);printf("n目前棧中元素為:n");Prin t(s);StatusPop(s, y);printf("n 出棧元素是:%cn", *y); printf("n棧頂元素出棧后，棧為:n"); Prin t(s);2.#i nclude<stdio.h>#in clude<malloc.h> #i nclude<stri ng.h>#defi ne STACK_INIT_SIZE 10 #defi ne

6、 STACK_GROW_SIZE 5 #defi ne ELEMT YPE chartypedef struct/*建立一個棧的首結點*/ELEMT YPE * base; ELEMT YPE * top; int stacksize; SpStack;int InitStack(SpStack *s)址*/*建立空的棧并返回首地s->base=(ELEMT YPE*)malloc(STACK_INIT_SIZE* sizeof(ELEMT YPE);if (!s->base) retur n 0;s->top=s->base; s->stacksize=ST r

7、eturn 1;int StackEmpty(SpStack *s)/* 判斷棧是否為空 */if (s->top=s->base) retur n 1;elsereturn 0;/*往棧頂插入/*判斷是否棧int Push(SpStack *s,ELEMTYPE e)元素即進棧*1if (s->top-s->base>=s->stacksize)滿*/s->base=(ELEMT YPE*)realloc(s->base,(s->stacksize+ STACK_GROW_SIZE)*sizeof(ELEMT YPE);if (!s-&g

8、t;base) retur n 0; s->stacksize+=STACK_GROW_SIZE; s->top=s->base+s->stacksize;*s->top+=e;return 1;int Pop(SpStack *s,ELEMTYPE *e)/* 讓棧頂元素依次輸出即出棧*/if (StackEmpty(s) return 0;*e=*(-s->top);return 1; int Count(SpStack *s)ELEMT YPE eSTACK_INIT_SIZE*2;ELEMT YPE e1;int i;In itStack(s);ge

9、ts(e);if ('n'=estrle n( e)-1) estrle n(e)-1=0; for (i=0; ei!='0： i+)switch (ei)case '(':case '':case '':Push(s,ei); break;case ')':case '':case '':if(StackEmpty(s) printf("匹配錯誤 n"); return 0;else Pop(s, &e1); break;if (StackEmpty(s)printf("匹配正確 n"); return 1;else printf("匹配錯誤 n");return 0;int mai n()SpStack s;printf（"請輸入一個可能包括括號、（）的表達 式 n"）;Cou nt(&s); free(s.base); return 0;六、測試和結果