棧和隊(duì)列的應(yīng)用實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告棧和隊(duì)列的應(yīng)用(10003809389j)一實(shí)驗(yàn)?zāi)康氖箤W(xué)生掌握棧的特點(diǎn)及其邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的實(shí)現(xiàn)；使學(xué)生掌握隊(duì)列的特點(diǎn)及其邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的實(shí)現(xiàn)；使學(xué)生掌握鏈棧和順序棧結(jié)構(gòu)的插入、刪除等基本運(yùn)算的實(shí)現(xiàn)；使學(xué)生掌握鏈隊(duì)列和順序隊(duì)列結(jié)構(gòu)的插入、刪除等基本運(yùn)算的實(shí)現(xiàn)；使學(xué)生熟練運(yùn)用棧結(jié)構(gòu)解決常見實(shí)際應(yīng)用問題；使學(xué)生熟練運(yùn)用隊(duì)列結(jié)構(gòu)解決常見實(shí)際應(yīng)用問題；二實(shí)驗(yàn)環(huán)境所需硬件環(huán)境為微機(jī)；所需軟件環(huán)境為MicrosoftVisualC++6.0；三實(shí)驗(yàn)內(nèi)容鏈棧:#include"LinkList0.c"/*詳見實(shí)驗(yàn)1*/LinkListInitStack_Sl(){LinkListS;S=InitList_Sl();returnS;}StatusDestroyStack_Sl(LinkListS){if(!S)returnERROR;/*鏈棧不存在*/DestroyList_Sl(S);returnOK;}StatusStackEmpty_Sl(LinkListS){if(!S)returnERROR;/*鏈棧不存在*/if(S->next==NULL)returnTRUE;elsereturnFALSE;}/*若鏈棧S存在，則當(dāng)S非空時(shí)返回棧頂元素e*/StatusStackGetTop_Sl(LinkListS){if(!S)returnERROR;/*鏈棧不存在*/if(S->next==NULL)returnFALSE;/*?？?/elsereturn(S->next->elem);}/*若鏈棧S存在，則當(dāng)S非空時(shí)，刪除棧頂元素并用e保存刪除的棧頂元素*/StatusStackPop_Sl(LinkListS,ElemType*e){if(!S)returnERROR;/*鏈棧不存在*/ListDelete_Sl(S,e);returnOK;}/*若鏈棧S存在時(shí)，插入元素e為新的棧頂元素*/StatusStackPush_Sl(LinkListS,ElemTypee){if(!S)returnERROR;/*鏈棧不存在*/ListInsert_Sl(S,e);returnOK;}/*若鏈棧S存在，返回鏈棧中元素個(gè)數(shù)*/intStackLength_Sl(LinkListS){if(!S)returnERROR;/*鏈棧不存在*/returnListLength_Sl(S);}/*若鏈棧S存在，遍歷鏈棧S，對(duì)每個(gè)元素執(zhí)行操作void(*operate)(ElemType*)*/StatusStackTraverse_Sl(LinkListS,void(*operate)(ElemType*)){if(!S)returnERROR;/*鏈棧不存在*/return(ListTraverse_Sl(S,operate));}鏈隊(duì)列#include"LinkList0.c"/*詳見實(shí)驗(yàn)1*/typedefstructQode{ElemTypeelem;structQode*next;}Qode,*Queue;typedefstruct{Queuefront;Queuerear;}Linkqueue,*LinkQueue;/*InitQueue_Sq()構(gòu)造一個(gè)空的隊(duì)列*/LinkQueueInitQueue_Sl(){LinkQueueQ;Q->front=Q->rear=(Queue)malloc(sizeof(Qode));if(!Q->front)returnNULL;/*存儲(chǔ)分配失敗*/Q->front->next=NULL;returnQ;}/*若隊(duì)列Q存在，銷毀鏈隊(duì)列Q*/StatusDestroyQueue_Sl(LinkQueueQ){Queuep;if(!Q)returnERROR;/*鏈隊(duì)列不存在*/do{/*釋放單向線性鏈表空間*/p=Q->front;Q->front=Q->front->next;free(p);}while(Q->front);returnOK;}/*若鏈隊(duì)列Q存在，則當(dāng)Q為空時(shí)返回TRUE，否則返回FALSE*/StatusQueueEmpty_Sl(LinkQueueQ){if(!Q)returnERROR;/*鏈隊(duì)列不存在*/if(Q->front==Q->rear)returnTRUE;elsereturnFALSE;}/*若鏈隊(duì)列Q存在，則當(dāng)Q非空時(shí)，返回隊(duì)頭元素e*/StatusQueueGetTop_Sl(LinkQueueQ,ElemTypee){if(!Q)returnERROR;/*鏈隊(duì)列不存在*/if(QueueEmpty_Sl(Q)==TRUE)returnFALSE;/*隊(duì)列空*/elsereturn(Q->front->next->elem);}/*若鏈隊(duì)列Q存在，則當(dāng)Q非空時(shí)，刪除隊(duì)頭元素并用e保存刪除的隊(duì)頭元素*/StatusDeQueue_Sl(LinkQueueQ,ElemType*e){Queuep;if(!Q)returnERROR;/*順序隊(duì)列不存在*/if(QueueEmpty_Sl(Q)==TRUE)returnFALSE;/*隊(duì)列空*/else{p=Q->front->next;*e=p->elem;Q->front->next=p->next;if(Q->front->next==NULL)Q->rear=Q->front;free(p);returnOK;}}/*若鏈隊(duì)列Q存在時(shí)，插入元素e為新的隊(duì)頭元素*/StatusEnQueue_Sl(LinkQueueQ,ElemTypee){Queuep;if(!Q)returnERROR;/*單向線性鏈表結(jié)點(diǎn)L不存在*/p=(Queue)malloc(sizeof(Qode));if(!p)exit(OVERFLOW);/*存儲(chǔ)空間增加失敗*/p->next=NULL;p->elem=e;Q->rear->next=p;Q->rear=p;returnOK;}/*若鏈隊(duì)列Q存在，返回鏈隊(duì)列元素個(gè)數(shù)*/intQueueLength_Sl(LinkQueueQ){inti=0;Queuep;if(!Q)returnERROR;/*鏈隊(duì)列不存在*/p=Q->front;while(p!=Q->rear){i++;p=p->next;}return(i);}/*若鏈隊(duì)列Q存在，遍歷鏈隊(duì)列Q，對(duì)每個(gè)元素執(zhí)行操作void(*operate)(ElemType*)*/StatusQueueTraverse_Sl(LinkQueueQ,void(*operate)(ElemType*)){Queuep;if(!Q)returnERROR;/*鏈隊(duì)列不存在*/p=Q->front->next;while(p!=NULL){operate(&p->elem);p=p->next;}return(OK);}表達(dá)式求解#include"LinkStack.c"http://用鏈棧實(shí)現(xiàn)中綴表達(dá)式求解。intprecede(intc,chard)//判斷運(yùn)算符的優(yōu)先級(jí)，{intt;switch(c){case45:case43:switch(d){case')':case'#':case'+':case'-':t=1;break;case'*':case'(':case'/':t=-1;break;default:t=-2;}break;case42:case47:switch(d){case'+':case'-':case')':case'*':case'/':case'#':t=1;break;case'(':t=-1;break;default:t=-2;}break;case40:if(d=='*'||d=='/'||d=='('||d=='+'||d=='-')t=-1;elseif(d==')')t=0;elset=-2;break;case41:if(d=='+'||d=='-'||d==')'||d=='#'||d=='*'||d=='/')t=1;elset=-2;break;case35:if(d=='*'||d=='/'||d=='('||d=='+'||d=='-')t=-1;elseif(d=='#')t=0;elset=-2;break;default:t=-2;}returnt;}intOperate(inta,inttheta,intb){//實(shí)現(xiàn)加減乘除運(yùn)算。intt;switch(theta){case43:t=a+b;break;case45:t=a-b;break;case42:t=a*b;break;case47:t=a/b;break;default:printf("Error");}returnt;}intmain(){charc;inta,b,d=1,p,q,theta,x;LinkListOPND,OPTR;printf("請(qǐng)輸入中綴表達(dá)式，以#結(jié)尾：\n");OPTR=InitStack_Sl();StackPush_Sl(OPTR,35);OPND=InitStack_Sl();c=getchar();while(c!='#'||StackGetTop_Sl(OPTR)!=35){//當(dāng)輸入字符和棧底元素都為#時(shí)退出循環(huán)。if(c>=48&&c<=57){p=c-48;c=getchar();//是數(shù)字就入棧while(c>=48&&c<=57){q=c-48;p=10*p+q;c=getchar();}//循環(huán)實(shí)現(xiàn)多位數(shù)求解StackPush_Sl(OPND,p);}else{switch(precede(StackGetTop_Sl(OPTR),c)){case-1:StackPush_Sl(OPTR,c);c=getchar();break;case0:StackPop_Sl(OPTR,&x);c=getchar();break;case1:StackPop_Sl(OPTR,&theta);StackPop_Sl(OPND,&b);StackPop_Sl(OPND,&a);StackPush_Sl(OPND,Operate(a,theta,b));break;default:printf("Error!");d=0;}}if(d==0)break;}//輸入錯(cuò)誤退出循環(huán)printf("結(jié)果為：%d\n",StackGetTop_Sl(OPND));}四實(shí)驗(yàn)分析及問題思考1、分析鏈棧和順序棧結(jié)構(gòu)之間的差異；答:順序棧結(jié)構(gòu)由一個(gè)順序表和一個(gè)top組成，而鏈棧由鏈表組成。順序棧有top記錄棧頂?shù)奈恢茫湕]有，但鏈棧的下一結(jié)點(diǎn)就是棧頂。插入和刪除順序棧頂元素時(shí)需要改變top的值，鏈棧不需要。2、分析順序表及線性鏈表的優(yōu)缺點(diǎn)；1順序表：優(yōu)點(diǎn)：1、邏輯相鄰，物理相鄰2可隨機(jī)存取任一元素3存儲(chǔ)空間使用緊湊缺點(diǎn)：1插入、刪除操作需要移動(dòng)大量的元素2預(yù)先分配空間需按最大空間分配，利用不充分3表容量難以擴(kuò)充 2線性鏈表：優(yōu)點(diǎn)：1空間合理利用，插入和刪除不需要移動(dòng)。2它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用3不需預(yù)先分配空間缺點(diǎn)：1實(shí)現(xiàn)某些操作不如順序存儲(chǔ)結(jié)構(gòu)。