棧和隊列的應(yīng)用實驗報告

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