棧的操作(實驗報告)21600字-第1篇

棧的操作(實驗報告)21600字

實驗三棧和隊列3.1實驗目的：（1）熟悉棧的特點（先進后出）及棧的基本操作，如入棧、出棧等，掌握棧的基本操作在棧的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)上的實現(xiàn)；（2）熟悉隊列的特點（先進先出）及隊列的基本操作，如入隊、出隊等，掌握隊列的基本操作在隊列的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)上的實現(xiàn)。3.2實驗要求：（1）復習課本中有關棧和隊列的知識；（2）用C語言完成算法和程序設計并上機調(diào)試通過；（3）撰寫實驗報告，給出算法思路或流程圖和具體實現(xiàn)（源程序）、算法分析結(jié)果（包括時間復雜度、空間復雜度以及算法優(yōu)化設想）、輸入數(shù)據(jù)及程序運行結(jié)果（必要時給出多種可能的輸入數(shù)據(jù)和運行結(jié)果）。3.3基礎實驗[實驗1]棧的順序表示和實現(xiàn)實驗內(nèi)容與要求:編寫一個程序?qū)崿F(xiàn)順序棧的各種基本運算，并在此基礎上設計一個主程序，完成如下功能：（1）初始化順序棧（2）插入元素（3）刪除棧頂元素（4）取棧頂元素（5）遍歷順序棧（6）置空順序棧分析:棧的順序存儲結(jié)構(gòu)簡稱為順序棧,它是運算受限的順序表。對于順序棧，入棧時，首先判斷棧是否為滿，棧滿的條件為：p->top==MAXNUM-1，棧滿時，不能入棧;否則出現(xiàn)空間溢出，引起錯誤，這種現(xiàn)象稱為上溢。出棧和讀棧頂元素操作，先判棧是否為空，為空時不能操作，否則產(chǎn)生錯誤。通常?？兆鳛橐环N控制轉(zhuǎn)移的條件。注意：（1）順序棧中元素用向量存放（2）棧底位置是固定不變的，可設置在向量兩端的任意一個端點（3）棧頂位置是隨著進棧和退棧操作而變化的，用一個整型量top（通常稱top為棧頂指針）來指示當前棧頂位置參考程序:#include<stdio.h>#include<stdlib.h>#defineMAXNUM201#defineElemTypeint/*定義順序棧的存儲結(jié)構(gòu)*/typedefstruct{ElemTypestack[MAXNUM];inttop;}SqStack;/*初始化順序棧*/voidInitStack(SqStack*p){if(!p)printf("Eorror");p->top=-1;}/*入棧*/voidPush(SqStack*p,ElemTypex){if(p->top<MAXNUM-1){p->top=p->top+1;p->stack[p->top]=x;}elseprintf("Overflow!\n");}/*出棧*/ElemTypePop(SqStack*p){ElemTypex;if(p->top!=0){x=p->stack[p->top];printf("以前的棧頂數(shù)據(jù)元素%d已經(jīng)被刪除！\n",p->stack[p->top]);p->top=p->top-1;return(x);}else{printf("Underflow!\n");return(0);}}/*獲取棧頂元素*/ElemTypeGetTop(SqStack*p){ElemTypex;if(p->top!=0){x=p->stack[p->top];return(x);}else{printf("Underflow!\n");2return(0);}}/*遍歷順序棧*/voidOutStack(SqStack*p){inti;printf("\n");if(p->top<0)printf("這是一個空棧！");printf("\n");for(i=p->top;i>=0;i--)printf("第%d個數(shù)據(jù)元素是：%6d\n",i,p->stack[i]);}/*置空順序棧*/voidsetEmpty(SqStack*p){p->top=-1;}/*主函數(shù)*/main(){SqStack*q;inty,cord;ElemTypea;do{printf("\n");printf("第一次使用必須初始化！\n");printf("\n");printf("\n主菜單\n");printf("\n1初始化順序棧\n");printf("\n2插入一個元素\n");printf("\n3刪除棧頂元素\n");printf("\n4取棧頂元素\n");printf("\n5置空順序棧\n");printf("\n6結(jié)束程序運行\(zhòng)n");printf("\n--------------------------------\n");printf("請輸入您的選擇(1,2,3,4,5,6)");scanf("%d",&cord);printf("\n");switch(cord){case1:{q=(SqStack*)malloc(sizeof(SqStack));InitStack(q);OutStack(q);}break;case2:3{printf("請輸入要插入的數(shù)據(jù)元素：a=");scanf("%d",&a);Push(q,a);OutStack(q);}break;case3:{Pop(q);OutStack(q);}break;case4:{y=GetTop(q);printf("\n棧頂元素為：%d\n",y);OutStack(q);}break;case5:{setEmpty(q);printf("\n順序棧被置空！\n");OutStack(q);}break;case6:exit(0);}}while(cord<=6);}[實驗2]棧的鏈式表示和實現(xiàn)實驗內(nèi)容與要求:編寫一個程序?qū)崿F(xiàn)鏈棧的各種基本運算，并在此基礎上設計一個主程序，完成如下功能：（1）初始化鏈棧（2）鏈棧置空（3）入棧（4）出棧（5）取棧頂元素（6）遍歷鏈棧分析:鏈棧是沒有附加頭結(jié)點的運算受限的單鏈表。棧頂指針就是鏈表的頭指針。注意：（1）LinkStack結(jié)構(gòu)類型的定義可以方便地在函數(shù)體中修改top指針本身（2）若要記錄棧中元素個數(shù)，可將元素個數(shù)屬性放在LinkStack類型中定義。（3）鏈棧中的結(jié)點是動態(tài)分配的，所以可以不考慮上溢。4參考程序:#include"stdio.h"#include"malloc.h"#include"stdlib.h"typedefintElemtype;typedefstructstacknode{Elemtypedata;stacknode*next;}StackNode;typedefstruct{stacknode*top;//棧頂指針}LinkStack;/*初始化鏈棧*/voidInitStack(LinkStack*s){s->top=NULL;printf("\n已經(jīng)初始化鏈棧！\n");}/*鏈棧置空*/voidsetEmpty(LinkStack*s){s->top=NULL;printf("\n鏈棧被置空！\n");}/*入棧*/voidpushLstack(LinkStack*s,Elemtypex){StackNode*p;p=(StackNode*)malloc(sizeof(StackNode));//建立一個節(jié)點。p->data=x;p->next=s->top;//由于是在棧頂pushLstack，所以要指向棧頂。s->top=p;//插入}/*出棧*/ElemtypepopLstack(LinkStack*s){Elemtypex;StackNode*p;p=s->top;//指向棧頂if(s->top==0){printf("\n?？?，不能出棧！\n");exit(-1);}x=p->data;s->top=p->next;//當前的棧頂指向原棧的nextfree(p);//釋放returnx;}5/*取棧頂元素*/ElemtypeStackTop(LinkStack*s){if(s->top==0){printf("\n鏈?？誠n");exit(-1);}returns->top->data;}/*遍歷鏈棧*/voidDisp(LinkStack*s){printf("\n鏈棧中的數(shù)據(jù)為：\n");printf("=======================================\n");StackNode*p;p=s->top;while(p!=NULL){printf("%d\n",p->data);p=p->next;}printf("=======================================\n");}voidmain(){printf("=================鏈棧操作=================\n\n");inti,m,n,a;LinkStack*s;s=(LinkStack*)malloc(sizeof(LinkStack));intcord;do{printf("\n");printf("第一次使用必須初始化！\n");printf("\n");printf("\n主菜單\n");printf("\n1初始化鏈棧\n");printf("\n2入棧\n");printf("\n3出棧\n");printf("\n4取棧頂元素\n");printf("\n5置空鏈棧\n");printf("\n6結(jié)束程序運行\(zhòng)n");printf("\n--------------------------------\n");printf("請輸入您的選擇(1,2,3,4,5,6)");scanf("%d",&cord);printf("\n");switch(cord){case1:{InitStack(s);Disp(s);6}break;case2:{printf("輸入將要壓入鏈棧的數(shù)據(jù)的個數(shù)：n=");scanf("%d",&n);printf("依次將%d個數(shù)據(jù)壓入鏈棧：\n",n);for(i=1;i<=n;i++){scanf("%d",&a);pushLstack(s,a);}Disp(s);}break;case3:{printf("\n出棧操作開始!\n");printf("輸入將要出棧的數(shù)據(jù)個數(shù)：m=");scanf("%d",&m);for(i=1;i<=m;i++){printf("\n第%d次出棧的數(shù)據(jù)是：%d",i,popLstack(s));}Disp(s);}break;case4:{printf("\n\n鏈棧的棧頂元素為：%d\n",StackTop(s));printf("\n");}break;case5:{setEmpty(s);Disp(s);}break;case6:exit(0);}}while(cord<=6);}[實驗3]隊列的順序表示和實現(xiàn)實驗內(nèi)容與要求編寫一個程序?qū)崿F(xiàn)順序隊列的各種基本運算，并在此基礎上設計一個主程序，完成如下功能：（1）初始化隊列（2）建立順序隊列（3）入隊（4）出隊（5）判斷隊列是否為空（6）取隊頭元素7（7）遍歷隊列分析:隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實際上是運算受限的順序表。入隊時，將新元素插入rear所指的位置，然后將rear加1。出隊時，刪去front所指的元素，然后將front加1并返回被刪元素。順序隊列中的溢出現(xiàn)象：（1）"下溢"現(xiàn)象。當隊列為空時，做出隊運算產(chǎn)生的溢出現(xiàn)象?！跋乱纭笔钦，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。（2）"真上溢"現(xiàn)象。當隊列滿時，做進棧運算產(chǎn)生空間溢出的現(xiàn)象?！罢嫔弦纭笔且环N出錯狀態(tài)，應設法避免。（3）"假上溢"現(xiàn)象。由于入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。當隊列中實際的元素個數(shù)遠遠小于向量空間的規(guī)模時，也可能由于尾指針已超越向量空間的上界而不能做入隊操作。該現(xiàn)象稱為"假上溢"現(xiàn)象。注意：（1）當頭尾指針相等時，隊列為空。（2）在非空隊列里，隊頭指針始終指向隊頭元素，尾指針始終指向隊尾元素的下一位置。參考程序:#include<stdio.h>#include<malloc.h>#defineMAXNUM100#defineElemtypeint#defineTRUE1#defineFALSE0typedefstruct{Elemtypequeue[MAXNUM];intfront;intrear;}sqqueue;/*隊列初始化*/intinitQueue(sqqueue*q){if(!q)returnFALSE;q->front=-1;q->rear=-1;returnTRUE;}/*入隊*/intappend(sqqueue*q,Elemtypex){if(q->rear>=MAXNUM-1)returnFALSE;q->rear++;q->queue[q->rear]=x;returnTRUE;}8/*出隊*/ElemtypeDelete(sqqueue*q){Elemtypex;if(q->front==q->rear)return0;x=q->queue[++q->front];returnx;}/*判斷隊列是否為空*/intEmpty(sqqueue*q){if(q->front==q->rear)returnTRUE;returnFALSE;}/*取隊頭元素*/intgethead(sqqueue*q){if(q->front==q->rear)return0;return(q->queue[q->front+1]);}/*遍歷隊列*/voiddisplay(sqqueue*q){ints;s=q->front;if(q->front==q->rear)printf("隊列空!\n");else{printf("\n順序隊列依次為：");while(s<q->rear){s=s+1;printf("%d<-",q->queue[s]);}printf("\n");printf("順序隊列的隊尾元素所在位置:rear=%d\n",q->rear);printf("順序隊列的隊頭元素所在位置:front=%d\n",q->front);}}/*建立順序隊列*/voidSetsqqueue(sqqueue*q){intn,i,m;printf("\n請輸入將要入順序隊列的長度:");scanf("%d",&n);printf("\n請依次輸入入順序隊列的元素值:\n");for(i=0;i<n;i++){scanf("%d",&m);append(q,m);}}9main(){sqqueue*head;intx,y,z,select;head=(sqqueue*)malloc(sizeof(sqqueue));do{printf("\n第一次使用請初始化！\n");printf("\n請選擇操作(1--7):\n");printf("===================================\n");printf("1初始化\n");printf("2建立順序隊列\(zhòng)n");printf("3入隊\n");printf("4出隊\n");printf("5判斷隊列是否為空\n");printf("6取隊頭元素\n");printf("7遍歷隊列\(zhòng)n");printf("===================================\n");scanf("%d",&select);switch(select){case1:{initQueue(head);printf("已經(jīng)初始化順序隊列！\n");break;}case2:{Setsqqueue(head);printf("\n已經(jīng)建立隊列！\n");display(head);break;}case3:{printf("請輸入隊的值:\n");scanf("%d",&x);append(head,x);display(head);break;}case4:{z=Delete(head);printf("\n隊頭元素%d已經(jīng)出隊！\n",z);display(head);break;}case5:{if(Empty(head))printf("隊列空\n");10elseprintf("隊列非空\n");break;}case6:{y=gethead(head);printf("隊頭元素為:%d\n",y);break;}case7:{display(head);break;}}}while(select<=7);}[實驗4[隊列的鏈式表示和實現(xiàn)實驗內(nèi)容與要求:編寫一個程序?qū)崿F(xiàn)鏈隊列的各種基本運算，并在此基礎上設計一個主程序，完成如下功能：（1）初始化并建立鏈隊列（2）入鏈隊列（3）出鏈隊列（4）遍歷鏈隊列分析:隊列的鏈式存儲結(jié)構(gòu)簡稱為鏈隊列。它是限制僅在表頭刪除和表尾插入的單鏈表。注意：（1）和鏈棧類似，無須考慮判隊滿的運算及上溢。（2）在出隊算法中，一般只需修改隊頭指針。但當原隊中只有一個結(jié)點時，該結(jié)點既是隊頭也是隊尾，故刪去此結(jié)點時亦需修改尾指針，且刪去此結(jié)點后隊列變空。（3）和單鏈表類似，為了簡化邊界條件的處理，在隊頭結(jié)點前可附加一個頭結(jié)點。參考程序:#include<stdio.h>#include<stdlib.h>#defineElemTypeinttypedefstructQnode{ElemTypedata;structQnode*next;}Qnodetype;typedefstruct{Qnodetype*front;11Qnodetype*rear;}Lqueue;/*入鏈隊列*/voidLappend(Lqueue*q,intx){Qnodetype*s;s=(Qnodetype*)malloc(sizeof(Qnodetype));s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;}/*初始化并建立鏈隊列*/voidcreat(Lqueue*q){Qnodetype*h;inti,n,x;printf("輸入將建立鏈隊列元素的個數(shù)：n=");scanf("%d",&n);h=(Qnodetype*)malloc(sizeof(Qnodetype));h->next=NULL;q->front=h;q->rear=h;for(i=1;i<=n;i++){printf("鏈隊列第%d個元素的值為：",i);scanf("%d",&x);Lappend(q,x);}}/*出鏈隊列*/ElemTypeLdelete(Lqueue*q){Qnodetype*p;ElemTypex;if(q->front==q->rear){printf("隊列為空!\n");x=0;}else{p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;free(p);12}return(x);}/*遍歷鏈隊列*/voiddisplay(Lqueue*q){Qnodetype*p;p=q->front->next;/*指向第一個數(shù)據(jù)元素節(jié)點*/printf("\n鏈隊列元素依次為：");while(p!=NULL){printf("%d-->",p->data);p=p->next;}printf("\n\n遍歷鏈隊列結(jié)束！\n");}main(){Lqueue*p;intx,cord;printf("\n*****第一次操作請選擇初始化并建立鏈隊列！*****\n");do{printf("\n鏈隊列的基本操作\n");printf("=========================================\n");printf("主菜單\n");printf("=========================================\n");printf("1初始化并建立鏈隊列\(zhòng)n");printf("2入鏈隊列\(zhòng)n");printf("3出鏈隊列\(zhòng)n");printf("4遍歷鏈隊列\(zhòng)n");printf("5結(jié)束程序運行\(zhòng)n");printf("==========================================\n");scanf("%d",&cord);switch(cord){case1:{p=(Lqueue*)malloc(sizeof(Lqueue));creat(p);display(p);}break;case2:{printf("請輸入隊列元素的值：x=");scanf("%d",&x);Lappend(p,x);display(p);}break;case3:{printf("出鏈隊列元素：x=%d\n",Ldelete(p));13}display(p);}break;case4:{display(p);}break;case5:{exit(0);}}}while(cord<=5);3.4提高實驗[實驗1]迷宮的求解實驗內(nèi)容與要求:迷宮只有兩個門，一個叫做入口，另一個叫做出口。把一只老鼠從一個無頂蓋的大盒子的入口處趕進迷宮。迷宮中設置很多隔壁，對前進方向形成了多處障礙，在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口。求解迷宮問題，即找出從入口到出口的路徑。分析:迷宮問題是棧應用的一個典型例子。求解過程可采用回溯法?；厮莘ㄊ且环N不斷試探且及時糾正錯誤的搜索方法。從入口出發(fā)，按某一方向向前探索，若能走通（未走過的），即某處可以到達，則到達新點，否則試探下一方向;若所有的方向均沒有通路，則沿原路返回前一點，換下一個方向再繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點。在求解過程中，為了保證在到達某一點后不能向前繼續(xù)行走（無路）時，能正確返回前一點以便繼續(xù)從下一個方向向前試探，則需要用一個棧保存所能夠到達的每一點的下標及從該點前進的方向，棧中保存的就是一條迷宮的通路。為了確保程序能夠終止，調(diào)整時，必須保證曾被放棄過的填數(shù)序列不被再次試驗，即要求按某種有序模型生成填數(shù)序列。給解的候選者設定一個被檢驗的順序，按這個順序逐一生成候選者并檢驗。參考程序::#include<stdio.h>#include<stdlib.h>#definen110#definen210typedefstructnode{intx;//存x坐標inty;//存Y坐標intc;//存該點可能的下點所在的方向,1表示向右,2向上,3向左,4向右14}linkstack;linkstacktop[100];//迷宮矩陣intmaze[n1][n2]={1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,};inti,j,k,m=0;main(){//初始化top[],置所有方向數(shù)為左for(i=0;i<n1*n2;i++){top[i].c=1;}printf("themazeis:\n");//打印原始迷宮矩陣for(i=0;i<n1;i++){for(j=0;j<n2;j++)printf(maze[i][j]?"*":"");printf("\n");}i=0;top[i].x=1;top[i].y=0;maze[1][0]=2;/*回溯算法*/do{if(top[i].c<5)//還可以向前試探{if(top[i].x==5&&top[i].y==9)//已找到一個組合{//打印路徑printf("Theway%dis:\n",m++);for(j=0;j<=i;j++){printf("(%d,%d)-->",top[j].x,top[j].y);}printf("\n");//打印選出路徑的迷宮for(j=0;j<n1;j++){for(k=0;k<n2;k++){if(maze[j][k]==0)printf("");elseif(maze[j][k]==2)printf("O");elseprintf("*");}printf("\n");}maze[top[i].x][top[i].y]=0;top[i].c=1;15i--;top[i].c+=1;continue;}switch(top[i].c)//向前試探{case1:{if(maze[top[i].x][top[i].y+1]==0){i++;top[i].x=top[i-1].x;top[i].y=top[i-1].y+1;maze[top[i].x][top[i].y]=2;}else{top[i].c+=1;}break;}case2:{if(maze[top[i].x-1][top[i].y]==0){i++;top[i].x=top[i-1].x-1;top[i].y=top[i-1].y;maze[top[i].x][top[i].y]=2;}else{top[i].c+=1;}break;}case3:{if(maze[top[i].x][top[i].y-1]==0){i++;top[i].x=top[i-1].x;top[i].y=top[i-1].y-1;maze[top[i].x][top[i].y]=2;}else{top[i].c+=1;}break;}case4:{if(maze[top[i].x+1][top[i].y]==0){i++;top[i].x=top[i-1].x+1;top[i].y=top[i-1].y;maze[top[i].x][top[i].y]=2;}else{top[i].c+=1;}break;}}}else//回溯16{if(i==0)return;//已找完所有解maze[top[i].x][top[i].y]=0;top[i].c=1;i--;top[i].c+=1;}}while(1);}[實驗2]停車場管理實驗內(nèi)容與要求:設停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。分析:綜合利用棧和隊列模擬停車場管理，學習利用棧和隊列解決實際問題。以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表實現(xiàn)。需另設一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實現(xiàn)。輸入數(shù)據(jù)按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進入停車場的時刻。設n=2,輸入數(shù)據(jù)為：（?A?，1，5），（?A?，2，10），（?D?，1，15），（?A?，3，20），（?A?，4，25），（?A?，5，30），（?D?，2，35），（?D?，4，40），（?E?，0，0）。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，其中，?A?表示到達；?D?表示離去，?E?表示輸入結(jié)束。參考程序:#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX2/*車庫容量*/#defineprice0.05/*每車每分鐘費用*/typedefstructtime{inthour;intmin;}Time;/*時間結(jié)點*/17typedefstructnode{charnum[10];Timereach;Timeleave;}CarNode;/*車輛信息結(jié)點*/typedefstructNODE{CarNode*stack[MAX+1];inttop;}SeqStackCar;/*模擬車站*/typedefstructcar{CarNode*data;structcar*next;}QueueNode;typedefstructNode{QueueNode*head;QueueNode*rear;}LinkQueueCar;/*模擬通道*/voidInitStack(SeqStackCar*);/*初始化棧*/intInitQueue(LinkQueueCar*);/*初始化便道*/intArrival(SeqStackCar*,LinkQueueCar*);/*車輛到達*/voidLeave(SeqStackCar*,SeqStackCar*,LinkQueueCar*);/*車輛離開*/voidList(SeqStackCar,LinkQueueCar);/*顯示存車信息*/voidmain(){SeqStackCarEnter,Temp;LinkQueueCarWait;intch;InitStack(&Enter);/*初始化車站*/InitStack(&Temp);/*初始化讓路的臨時棧*/InitQueue(&Wait);/*初始化通道*/while(1){printf("\n1.車輛到達");printf("2.車輛離開");printf("3.列表顯示");printf("4.退出系統(tǒng)\n");while(1){scanf("%d",&ch);if(ch>=1&&ch<=4)break;elseprintf("\n請選擇：1|2|3|4.");}switch(ch){case1:Arrival(&Enter,&Wait);break;/*車輛到達*/case2:Leave(&Enter,&Temp,&Wait);break;/*車輛離開*/case3:List(Enter,Wait);break;/*列表打印信息*/case4:exit(0);/*退出主程序*/18default:break;}}}voidInitStack(SeqStackCar*s)/*初始化棧*/{inti;s->top=0;for(i=0;i<=MAX;i++)s->stack[s->top]=NULL;}intInitQueue(LinkQueueCar*Q)/*初始化便道*/{Q->head=(QueueNode*)malloc(sizeof(QueueNode));if(Q->head!=NULL){Q->head->next=NULL;Q->rear=Q->head;return(1);}elsereturn(-1);}voidPRINT(CarNode*p,introom)/*打印出站車的信息*/{intA1,A2,B1,B2;printf("\n請輸入離開的時間:/**:**/");scanf("%d:%d",&(p->leave.hour),&(p->leave.min));printf("\n離開車輛的車牌號為:");puts(p->num);printf("\n其到達時間為:%d:%d",p->reach.hour,p->reach.min);printf("離開時間為:%d:%d",p->leave.hour,p->leave.min);A1=p->reach.hour;A2=p->reach.min;B1=p->leave.hour;B2=p->leave.min;printf("\n應交費用為:%2.1f元",((B1-A1)*60+(B2-A2))*price);free(p);}intArrival(SeqStackCar*Enter,LinkQueueCar*W)/*車輛到達*/{CarNode*p;QueueNode*t;p=(CarNode*)malloc(sizeof(CarNode));flushall();printf("\n請輸入車牌號(例:陜A1234):");gets(p->num);if(Enter->top<MAX)/*車場未滿，車進車場*/{Enter->top++;printf("\n車輛在車場第%d位置.",Enter->top);printf("\n請輸入到達時間:/**:**/");scanf("%d:%d",&(p->reach.hour),&(p->reach.min));Enter->stack[Enter->top]=p;return(1);}else/*車場已滿，車進便道*/19{printf("\n該車須在便道等待!");t=(QueueNode*)malloc(sizeof(QueueNode));t->data=p;t->next=NULL;W->rear->next=t;W->rear=t;return(1);}}voidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W){/*車輛離開*/inti,room;CarNode*p,*t;QueueNode*q;/*判斷車場內(nèi)是否有車*/if(Enter->top>0)/*有車*/{while(1)/*輸入離開車輛的信息*/{printf("\n請輸入車在車場的位置/1--%d/：",Enter->top);scanf("%d",&room);if(room>=1&&room<=Enter->top)break;}while(Enter->top>room)/*車輛離開*/{Temp->top++;Temp->stack[Temp->top]=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;}p=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;while(Temp->top>=1){Enter->top++;Enter->stack[Enter->top]=Temp->stack[Temp->top];Temp->stack[Temp->top]=NULL;Temp->top--;}PRINT(p,room);/*判斷通道上是否有車及車站是否已滿*/if((W->head!=W->rear)&&Enter->top<MAX)/*便道的車輛進入車場*/{q=W->head->next;t=q->data;Enter->top++;printf("\n便道的%s號車進入車場第%d位置.",t->num,Enter