算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)棧與隊(duì)列的應(yīng)用

1、信息科學(xué)與工程學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)任務(wù)書(shū) 教師：19- 20學(xué)年第 學(xué)期 專(zhuān)業(yè)名稱(chēng)：實(shí)驗(yàn)學(xué)時(shí)：2實(shí)驗(yàn)題目：棧與隊(duì)列的 應(yīng)用實(shí)驗(yàn)環(huán)境：CodeBlocks 實(shí)驗(yàn)?zāi)康模?掌握棧的定義及實(shí)現(xiàn)；2掌握利用棧求解算術(shù)表達(dá)式 的方法。 實(shí)驗(yàn)內(nèi)容：1 依據(jù)順序棧存儲(chǔ)結(jié)構(gòu)的定義如下：#define MAXSIZE 100 typedef char SEIemType; typedef struct SEIemType *base; SEIemType *top; int stacksize; JSqStack;調(diào)試并測(cè)試常用操作如下：int lnitStack( SqStack typedef char

2、SEIemType; typedef struct SEIemType *base; SEIemType *top; int stacksize; JSqStack; int lnitStack( SqStack if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=MAXSIZE; return OK; int StackEmpty( SqStack S ) ( if(S.top=S.base) cout 棧滿(mǎn) ” endl; else cout 棧沒(méi)滿(mǎn) endl int StackLength( SqStack S ) ( return

3、 S.top-S.base; int Push( SqStack *S.top+=e; return OK; int Pop( SqStack e=*-S.top; return OK; 2設(shè)單鏈表中存放n個(gè)字符，試設(shè)計(jì)一個(gè)算法，判斷該字符串是否中心對(duì) 稱(chēng)。#include #include #in clude #define MAX 147 struct node ( char data; struct node ext; ; int judge(struct node *head,int len) ( struct node *top5*p1 ,*p2; top = NULL; p1 =

4、head-next; for(int i = 0 ; i data = p1-data; p2n ext = top; top = p2; p1 = p1- n ext; if(len%2 = 1) p1 = p1n ext; p2 = top; for(int i = 0 ; i data != p1data) break; top = p2n ext; p1 = ext; p2 = top; if(!top) return 1; else return 0; int main() ( int n=0; char strMAX; struct node *head,*p; head = p

5、= (struct node *)malloc(sizeof(struct no de); head- next = p-next = NULL; printf(-請(qǐng)輸入一個(gè)字符串：F)； gets(str); int len = strlen(str); while(n data = strn; pnext = head-next; head-next = p; n+; if(judge(head,len) printf(%s是一個(gè)回文!n,str); else printf(%s不是一個(gè)回文!n,str); return 0; C:UserslenovoDesktop333333binDe

6、bug33333 C:UserslenovoDesktop333333binDebug33 謫輸人一個(gè)字苻串： 12345 12345不是一個(gè)回文! Process returned 0 (0 x0) execution ti *ress any key to continue- 3.(通過(guò)修改完善教材中的算法3.22，利用棧來(lái)實(shí)現(xiàn)算術(shù)表達(dá)式求值的算法。對(duì)算法 3.22中調(diào)用的幾個(gè)函數(shù)要給出其實(shí)現(xiàn)過(guò)程： (1)函數(shù)ln(c):判斷c是否為運(yùn)算符； (2) 函數(shù)Precede(t1,t2):判斷運(yùn)算符t1和t2的優(yōu)先級(jí)； (3) 函數(shù) Operate(a,theta,b):對(duì) a 和 b 進(jìn)行二

7、元運(yùn)算 theta 程序運(yùn)行時(shí)，輸入合法的算術(shù)表達(dá)式(中間值及最終結(jié)果要在09之間，可以包括加 減乘除和括號(hào))，便可輸出相應(yīng)的計(jì)算結(jié)果。如下圖： 請(qǐng)輸入算術(shù)表達(dá)式中間值及最纟冬結(jié)杲要在。9之間)，并以U結(jié)束 2(4?/3*2 ress typedef char SEIemType; typedef struct SEIemType *base; SEIemType *top; int stacksize; SqStack; int lnitStack( SqStack if(IS.base) exit(OVERFLOW); S.top=S.base; S.stacksize=MAXSIZE;

8、return 1; int Push( SqStack *S.top+=e; return 1; int Pop( SqStack e=*-S.top; return 1; int GetTop(SqStack S) ( if(S.top!=S.base) return *(S.top-1); int ln(SEIemType c) switch(c) /判斷讀入的字符是哪一種運(yùn)算符， case return TRUE; break; case fJ: return TRUE; break; case *: return TRUE; break; case 7: return TRUE; br

9、eak; case return TRUE; break; case y： return TRUE; break; case return TRUE; break; default: return FALSE; SEIemType Precede(SEIemType t1,SEIemType SEIemType f; switch(t2) /判斷運(yùn)算符棧的棧頂元素和讀入的運(yùn)算符之間誰(shuí)的優(yōu)先級(jí)更高，并返回結(jié)果 case V: if(n=：=f |t1=#) f=N; else t= break; caseif (t1=f |t1=#) f=N; else f=： break; case if (

10、t1 =,+,|t1 =f-,|t1 =,(,| |t1 =#) f=ff; break; case 71: if (t1 =+f|t1 =,J|t1 =TI|t1 =#f) f=f； else break; case if (ti =+|ti =,-,|ti =*(| |ti =#|ti =*| |ti =/*) f=,; break; default: printf(” 輸入超出范圍。u)； return f; SEIemType Operate(SEIemType a,SEIemType theta,SEIemType b) SEIemType c; a=a-*O*; /因?yàn)閍，b均為字

11、符型，所以轉(zhuǎn)化成int型 b=b-,O,; switch(theta) case V: c=a+b+*O; break; /再將計(jì)算的結(jié)果轉(zhuǎn)化為字符型 case ： c=a-b+O; break; c=a*b+O*; break; case 7: c=a/b+O; break; return c; /返回計(jì)算結(jié)果 char EvaluateExpression() SqStack OPND,OPTR; char ch,theta,a,b,x; InitStack(OPND); lnitStack(OPT R); Push(OPTR, #); cin ch; while(ch!=#|GetTop

12、(OPTR)!=#) if(!ln(ch) Push(OPND,ch); cin ch; else switch(Precede(GetTop(OPTR),ch) case ch; break; case、： Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; case=: Pop(OPTR,x); cinch; break; return GetTop(OPND); using namespace std; int main() char w; coutvv”請(qǐng)輸入算數(shù)表達(dá)式，并以#結(jié)

13、束n”； w=EvaluateExpression(); /將運(yùn)算結(jié)果賦值給w w=w-48; /將字符轉(zhuǎn)換成數(shù)字printf(計(jì) 算結(jié)果為%dn*w); 實(shí)驗(yàn)提示：(僅供參考，每個(gè)函數(shù)的具體實(shí)現(xiàn)可以有多種方法) 1 將棧的定義和實(shí)現(xiàn)單獨(dú)保存在頭文件“ stack.h”中，然后在表達(dá)式求值的源程序 sy3.cpp 中包含此頭文件(即 #include “ stack.h ” ) 2.表達(dá)式求值源程序sy3.cpp的具體實(shí)現(xiàn) (1) 主函數(shù)如下： void main() cout請(qǐng)輸入算術(shù)表達(dá)式，并以 # 結(jié)束.vvendl; coutEvaluateExpression()endl; (2)

14、函數(shù) EvaluateExpression 的實(shí)現(xiàn)見(jiàn)算法 3.22 (3) 函數(shù)ln(c)的實(shí)現(xiàn)可以采用以下方式： Status ln(SEIemType c)/ 應(yīng)在前面有定義 typedef char SEIemType; /判斷c是否為運(yùn)算符 switch(c) case+:return TRUE; /補(bǔ)充完整 default:return FALSE; (4) 函數(shù)Precede(t1,的實(shí)現(xiàn)可以采用以下形式：SEIemType Precede(SEIemType t1,SEIemType/根據(jù)教材表3.1，判斷兩個(gè)運(yùn)算符的優(yōu)先矢系 SEIemType f; switch(t2) case caseif(t1=(|t1=#) else 5： break; /補(bǔ)充完整 return f; ) (5)函數(shù) Operate(a,theta,b)的實(shí)現(xiàn)可以采用以下方式：SEIemType Operate(SEIemType a,SEIemType theta,SEIemType b) SEIemType c; a=a-48; b=b-48; switch(theta) case,+,:c=a+b+48; break; /補(bǔ)充完整 return