棧的操作(實(shí)驗(yàn)報(bào)告)

1、實(shí)驗(yàn)三 棧和隊(duì)列3.1實(shí)驗(yàn)?zāi)康模海?） 熟悉棧的特點(diǎn)（先進(jìn)后出）及棧的基本操作，如入棧、出棧等，掌握棧的基本操作在棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)；（2） 熟悉隊(duì)列的特點(diǎn)（先進(jìn)先出）及隊(duì)列的基本操作，如入隊(duì)、出隊(duì)等，掌握隊(duì)列的基本操作在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。3.2 實(shí)驗(yàn)要求：（1） 復(fù)習(xí)課本中有關(guān)棧和隊(duì)列的知識(shí)；（2） 用C語言完成算法和程序設(shè)計(jì)并上機(jī)調(diào)試通過；（3） 撰寫實(shí)驗(yàn)報(bào)告，給出算法思路或流程圖和具體實(shí)現(xiàn)（源程序）、算法分析結(jié)果（包括時(shí)間復(fù)雜度、空間復(fù)雜度以及算法優(yōu)化設(shè)想）、輸入數(shù)據(jù)及程序運(yùn)行結(jié)果（必要時(shí)給出多種可能的輸入數(shù)據(jù)和運(yùn)行結(jié)果）。3.3 基礎(chǔ)實(shí)驗(yàn)實(shí)驗(yàn)

2、1 棧的順序表示和實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容與要求:編寫一個(gè)程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序，完成如下功能：（1）初始化順序棧（2）插入元素（3）刪除棧頂元素（4）取棧頂元素（5）遍歷順序棧（6）置空順序棧分析:棧的順序存儲(chǔ)結(jié)構(gòu)簡稱為順序棧,它是運(yùn)算受限的順序表。對(duì)于順序棧，入棧時(shí)，首先判斷棧是否為滿，棧滿的條件為：p-top= =MAXNUM-1，棧滿時(shí)，不能入棧; 否則出現(xiàn)空間溢出，引起錯(cuò)誤，這種現(xiàn)象稱為上溢。出棧和讀棧頂元素操作，先判棧是否為空，為空時(shí)不能操作，否則產(chǎn)生錯(cuò)誤。通常棧空作為一種控制轉(zhuǎn)移的條件。注意：（1）順序棧中元素用向量存放（2）棧底位置是固定不變的，可設(shè)置在向

3、量兩端的任意一個(gè)端點(diǎn)（3）棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個(gè)整型量top（通常稱top為棧頂指針）來指示當(dāng)前棧頂位置參考程序:#include#include#define MAXNUM 20#define ElemType int/*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/typedef struct ElemType stackMAXNUM;int top;SqStack;/*初始化順序棧*/void InitStack(SqStack *p)if(!p)printf(Eorror);p-top=-1;/*入棧*/void Push(SqStack *p,ElemType x)if(p-topt

4、op=p-top+1;p-stackp-top=x;elseprintf(Overflow!n);/*出棧*/ElemType Pop(SqStack *p)ElemType x;if(p-top!=0)x=p-stackp-top;printf(以前的棧頂數(shù)據(jù)元素%d已經(jīng)被刪除！n,p-stackp-top);p-top=p-top-1;return(x);elseprintf(Underflow!n);return(0);/*獲取棧頂元素*/ElemType GetTop(SqStack *p)ElemType x;if(p-top!=0)x=p-stackp-top;return(x);

5、elseprintf(Underflow!n);return(0);/*遍歷順序棧*/void OutStack(SqStack *p)int i;printf(n);if(p-toptop;i=0;i-)printf(第%d個(gè)數(shù)據(jù)元素是：%6dn,i,p-stacki);/*置空順序棧*/void setEmpty(SqStack *p)p-top= -1;/*主函數(shù)*/main() SqStack *q;int y,cord;ElemType a;doprintf(n);printf(第一次使用必須初始化！n);printf(n);printf(n 主菜單 n);printf(n 1 初始

6、化順序棧 n);printf(n 2 插入一個(gè)元素 n);printf(n 3 刪除棧頂元素 n);printf(n 4 取棧頂元素 n);printf(n 5 置空順序棧 n);printf(n 6 結(jié)束程序運(yùn)行 n);printf(n-n);printf(請(qǐng)輸入您的選擇( 1, 2, 3, 4, 5,6);scanf(%d,&cord);printf(n);switch(cord)case 1:q=(SqStack*)malloc(sizeof(SqStack);InitStack(q);OutStack(q);break;case 2:printf(請(qǐng)輸入要插入的數(shù)據(jù)元素：a=);sca

7、nf(%d,&a);Push(q,a);OutStack(q);break;case 3:Pop(q);OutStack(q);break;case 4:y=GetTop(q);printf(n棧頂元素為：%dn,y);OutStack(q);break;case 5:setEmpty(q);printf(n順序棧被置空！n);OutStack(q);break;case 6:exit(0);while (cordtop=NULL;printf(n已經(jīng)初始化鏈棧！n);/*鏈棧置空*/void setEmpty(LinkStack * s)s-top=NULL; printf(n鏈棧被置空！n

8、);/*入棧*/void pushLstack(LinkStack * s, Elemtype x)StackNode * p;p=(StackNode *)malloc(sizeof(StackNode); /建立一個(gè)節(jié)點(diǎn)。p-data=x;p-next=s-top; /由于是在棧頂pushLstack，所以要指向棧頂。s-top=p; /插入/*出棧*/Elemtype popLstack(LinkStack * s)Elemtype x;StackNode * p;p=s-top; /指向棧頂if (s-top =0)printf(n?？?，不能出棧！n);exit(-1);x=p-dat

9、a; s-top=p-next; /當(dāng)前的棧頂指向原棧的nextfree(p); /釋放return x;/*取棧頂元素*/Elemtype StackTop(LinkStack *s)if (s-top =0)printf(n鏈?？課);exit(-1);return s-top-data;/*遍歷鏈棧*/void Disp(LinkStack * s)printf(n鏈棧中的數(shù)據(jù)為：n);printf(=n);StackNode * p;p=s-top;while (p!=NULL) printf(%dn,p-data);p=p-next;printf(=n);void main()pri

10、ntf(= 鏈棧操作=nn);int i,m,n,a;LinkStack * s;s=(LinkStack *)malloc(sizeof(LinkStack);int cord;doprintf(n);printf(第一次使用必須初始化！n);printf(n);printf(n 主菜單 n);printf(n 1 初始化鏈棧 n);printf(n 2 入棧 n);printf(n 3 出棧 n);printf(n 4 取棧頂元素 n);printf(n 5 置空鏈棧 n);printf(n 6 結(jié)束程序運(yùn)行 n);printf(n-n);printf(請(qǐng)輸入您的選擇( 1, 2, 3,

11、4, 5,6);scanf(%d,&cord);printf(n);switch(cord)case 1: InitStack(s);Disp(s);break;case 2:printf(輸入將要壓入鏈棧的數(shù)據(jù)的個(gè)數(shù)：n=); scanf(%d,&n); printf(依次將%d個(gè)數(shù)據(jù)壓入鏈棧：n,n);for(i=1;i=n;i+)scanf(%d,&a);pushLstack(s,a);Disp(s);break;case 3:printf(n出棧操作開始!n);printf(輸入將要出棧的數(shù)據(jù)個(gè)數(shù)：m=);scanf(%d,&m);for(i=1;i=m;i+)printf(n第%d次

12、出棧的數(shù)據(jù)是：%d,i,popLstack(s);Disp(s);break;case 4:printf(nn鏈棧的棧頂元素為：%dn,StackTop(s);printf(n);break;case 5:setEmpty(s);Disp(s);break;case 6:exit(0);while (cord=6);實(shí)驗(yàn)3 隊(duì)列的順序表示和實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容與要求編寫一個(gè)程序?qū)崿F(xiàn)順序隊(duì)列的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序，完成如下功能：（1）初始化隊(duì)列（2）建立順序隊(duì)列（3）入隊(duì)（4）出隊(duì)（5）判斷隊(duì)列是否為空（6）取隊(duì)頭元素（7）遍歷隊(duì)列分析:隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列實(shí)際上

13、是運(yùn)算受限的順序表。入隊(duì)時(shí)，將新元素插入rear所指的位置，然后將rear加1。出隊(duì)時(shí)，刪去front所指的元素，然后將front加1并返回被刪元素。順序隊(duì)列中的溢出現(xiàn)象：（1） 下溢現(xiàn)象。當(dāng)隊(duì)列為空時(shí)，做出隊(duì)運(yùn)算產(chǎn)生的溢出現(xiàn)象?！跋乱纭笔钦，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。（2） 真上溢現(xiàn)象。當(dāng)隊(duì)列滿時(shí)，做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象?！罢嫔弦纭笔且环N出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免。（3） 假上溢現(xiàn)象。由于入隊(duì)和出隊(duì)操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠(yuǎn)無法重新利用。當(dāng)隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模時(shí)，也可能由于尾指針已超越向量空間的上界而不能做入隊(duì)操作。該現(xiàn)象稱為假上溢現(xiàn)象。

14、注意：（1）當(dāng)頭尾指針相等時(shí)，隊(duì)列為空。（2）在非空隊(duì)列里，隊(duì)頭指針始終指向隊(duì)頭元素，尾指針始終指向隊(duì)尾元素的下一位置。參考程序:#include #include #define MAXNUM 100#define Elemtype int#define TRUE 1#define FALSE 0typedef structElemtype queueMAXNUM; int front; int rear;sqqueue; /*隊(duì)列初始化*/int initQueue(sqqueue *q) if(!q) return FALSE;q-front=-1;q-rear=-1;return TR

15、UE; /*入隊(duì)*/int append(sqqueue *q, Elemtype x) if(q-rear=MAXNUM-1) return FALSE; q-rear+;q-queueq-rear=x; return TRUE;/*出隊(duì)*/Elemtype Delete(sqqueue *q)Elemtype x;if (q-front=q-rear) return 0;x=q-queue+q-front;return x;/*判斷隊(duì)列是否為空*/int Empty(sqqueue *q)if (q-front=q-rear) return TRUE; return FALSE; /*取隊(duì)

16、頭元素*/int gethead(sqqueue *q)if (q-front=q-rear) return 0; return(q-queueq-front+1); /*遍歷隊(duì)列*/void display(sqqueue *q)int s; s=q-front; if (q-front=q-rear)printf(隊(duì)列空!n); else printf(n順序隊(duì)列依次為：);while(srear) s=s+1;printf(%dqueues);printf(n); printf(順序隊(duì)列的隊(duì)尾元素所在位置:rear=%dn,q-rear); printf(順序隊(duì)列的隊(duì)頭元素所在位置:fr

17、ont=%dn,q-front);/*建立順序隊(duì)列*/void Setsqqueue(sqqueue *q)int n,i,m;printf(n請(qǐng)輸入將要入順序隊(duì)列的長度:); scanf(%d,&n); printf(n請(qǐng)依次輸入入順序隊(duì)列的元素值:n);for (i=0;in;i+) scanf(%d,&m); append(q,m);main() sqqueue *head; int x,y,z,select; head=(sqqueue*)malloc(sizeof(sqqueue); doprintf(n第一次使用請(qǐng)初始化！n);printf(n請(qǐng)選擇操作(1-7):n);print

18、f(=n);printf(1 初始化n);printf(2 建立順序隊(duì)列n);printf(3 入隊(duì)n); printf(4 出隊(duì) n); printf(5 判斷隊(duì)列是否為空n); printf(6 取隊(duì)頭元素 n); printf(7 遍歷隊(duì)列n);printf(=n);scanf(%d,&select); switch(select) case 1: initQueue(head); printf(已經(jīng)初始化順序隊(duì)列！n);break; case 2: Setsqqueue(head); printf(n已經(jīng)建立隊(duì)列！n);display(head);break; case 3: prin

19、tf(請(qǐng)輸入隊(duì)的值:n ); scanf(%d,&x); append(head,x); display(head); break; case 4: z=Delete(head); printf(n隊(duì)頭元素%d已經(jīng)出隊(duì)！n,z);display(head); break; case 5: if(Empty(head) printf(隊(duì)列空n); else printf(隊(duì)列非空n); break; case 6: y=gethead(head); printf(隊(duì)頭元素為:%dn,y); break; case 7: display(head); break; while(select=7);

20、實(shí)驗(yàn)4 隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)實(shí)驗(yàn)內(nèi)容與要求:編寫一個(gè)程序?qū)崿F(xiàn)鏈隊(duì)列的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序，完成如下功能：（1）初始化并建立鏈隊(duì)列（2）入鏈隊(duì)列（3）出鏈隊(duì)列（4）遍歷鏈隊(duì)列分析:隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈隊(duì)列。它是限制僅在表頭刪除和表尾插入的單鏈表。注意：（1）和鏈棧類似，無須考慮判隊(duì)滿的運(yùn)算及上溢。（2）在出隊(duì)算法中，一般只需修改隊(duì)頭指針。但當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾，故刪去此結(jié)點(diǎn)時(shí)亦需修改尾指針，且刪去此結(jié)點(diǎn)后隊(duì)列變空。（3）和單鏈表類似，為了簡化邊界條件的處理，在隊(duì)頭結(jié)點(diǎn)前可附加一個(gè)頭結(jié)點(diǎn)。參考程序:#include#include#define

21、ElemType inttypedef struct QnodeElemType data;struct Qnode *next;Qnodetype;typedef structQnodetype *front;Qnodetype *rear;Lqueue;/*入鏈隊(duì)列*/void Lappend(Lqueue *q,int x)Qnodetype *s; s=(Qnodetype*)malloc(sizeof(Qnodetype);s-data=x;s-next=NULL;q-rear-next=s;q-rear=s;/*初始化并建立鏈隊(duì)列*/void creat(Lqueue *q)Qno

22、detype *h;int i,n,x;printf(輸入將建立鏈隊(duì)列元素的個(gè)數(shù)：n= );scanf(%d,&n);h=(Qnodetype*)malloc(sizeof(Qnodetype);h-next=NULL;q-front=h;q-rear=h;for(i=1;ifront=q-rear)printf(隊(duì)列為空!n);x=0;elsep=q-front-next;q-front-next=p-next;if(p-next=NULL)q-rear=q-front;x=p-data;free(p);return(x);/*遍歷鏈隊(duì)列*/void display(Lqueue *q)Qn

23、odetype *p; p=q-front-next; /*指向第一個(gè)數(shù)據(jù)元素節(jié)點(diǎn) */printf(n鏈隊(duì)列元素依次為：);while(p!=NULL)printf(%d-,p-data);p=p-next;printf(nn遍歷鏈隊(duì)列結(jié)束！ n);main()Lqueue *p;int x,cord;printf(n*第一次操作請(qǐng)選擇初始化并建立鏈隊(duì)列！*n );do printf(n 鏈隊(duì)列的基本操作n );printf(=n); printf( 主菜單 n); printf(=n);printf( 1 初始化并建立鏈隊(duì)列 n);printf( 2 入鏈隊(duì)列 n);printf( 3 出

24、鏈隊(duì)列 n);printf( 4 遍歷鏈隊(duì)列 n);printf( 5 結(jié)束程序運(yùn)行 n);printf(=n);scanf(%d,&cord);switch(cord)case 1:p=(Lqueue *)malloc(sizeof(Lqueue);creat(p);display(p);break;case 2:printf(請(qǐng)輸入隊(duì)列元素的值：x=);scanf(%d,&x);Lappend(p,x);display(p);break;case 3:printf(出鏈隊(duì)列元素：x=%dn,Ldelete(p);display(p);break;case 4:display(p);brea

25、k;case 5:exit (0);while (cord=5);3.4 提高實(shí)驗(yàn)實(shí)驗(yàn)1 迷宮的求解實(shí)驗(yàn)內(nèi)容與要求:迷宮只有兩個(gè)門，一個(gè)叫做入口，另一個(gè)叫做出口。把一只老鼠從一個(gè)無頂蓋的大盒子的入口處趕進(jìn)迷宮。迷宮中設(shè)置很多隔壁，對(duì)前進(jìn)方向形成了多處障礙，在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。求解迷宮問題，即找出從入口到出口的路徑。分析:迷宮問題是棧應(yīng)用的一個(gè)典型例子。求解過程可采用回溯法?；厮莘ㄊ且环N不斷試探且及時(shí)糾正錯(cuò)誤的搜索方法。從入口出發(fā)，按某一方向向前探索，若能走通（未走過的），即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一方向 ; 若所有的方向均沒有通路，

26、則沿原路返回前一點(diǎn)，換下一個(gè)方向再繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點(diǎn)。在求解過程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走（無路）時(shí)，能正確返回前一點(diǎn)以便繼續(xù)從下一個(gè)方向向前試探，則需要用一個(gè)棧保存所能夠到達(dá)的每一點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向，棧中保存的就是一條迷宮的通路。為了確保程序能夠終止，調(diào)整時(shí)，必須保證曾被放棄過的填數(shù)序列不被再次試驗(yàn)，即要求按某種有序模型生成填數(shù)序列。給解的候選者設(shè)定一個(gè)被檢驗(yàn)的順序，按這個(gè)順序逐一生成候選者并檢驗(yàn)。參考程序:#include #include #define n1 10 #define n2 10 typed

27、ef struct node int x; /存x坐標(biāo)int y; /存Y坐標(biāo)int c; /存該點(diǎn)可能的下點(diǎn)所在的方向,1表示向右,2向上,3向左,4向右linkstack; linkstack top100; /迷宮矩陣int mazen1n2=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

28、,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1,; int i,j,k,m=0;main() /初始化top,置所有方向數(shù)為左for(i=0;in1*n2;i+) topi.c=1;printf(the maze is:n);/打印原始迷宮矩陣 for(i=0;in1;i+) for(j=0;jn2;j+) printf(mazeij?* : ); printf(n); i=0;topi.x=1;topi.y=0;maze10=2;/*回溯算法*/doif(topi.c5) /還可以向前試探if(topi.x=5 & topi.y=9) /已找到一個(gè)組合/打印路徑print

29、f(The way %d is:n,m+);for(j=0;j,topj.x,topj.y);printf(n);/打印選出路徑的迷宮for(j=0;jn1;j+) for(k=0;kn2;k+) if(mazejk=0)printf( );else if(mazejk=2) printf(O );else printf(* );printf(n); mazetopi.xtopi.y=0;topi.c = 1;i-;topi.c += 1;continue;switch (topi.c) /向前試探case 1:if(mazetopi.xtopi.y+1=0)i+;topi.x=topi-1.

30、x;topi.y=topi-1.y+1;mazetopi.xtopi.y=2;elsetopi.c += 1;break;case 2:if(mazetopi.x-1topi.y=0)i+;topi.x=topi-1.x-1;topi.y=topi-1.y;mazetopi.xtopi.y=2;elsetopi.c += 1;break;case 3:if(mazetopi.xtopi.y-1=0)i+;topi.x=topi-1.x;topi.y=topi-1.y-1;mazetopi.xtopi.y=2;elsetopi.c += 1;break;case 4:if(mazetopi.x+

31、1topi.y=0)i+;topi.x=topi-1.x+1;topi.y=topi-1.y;mazetopi.xtopi.y=2;elsetopi.c += 1;break;else /回溯if(i=0) return; /已找完所有解mazetopi.xtopi.y=0;topi.c = 1;i-;topi.c += 1;while(1); 實(shí)驗(yàn)2 停車場(chǎng)管理實(shí)驗(yàn)內(nèi)容與要求:設(shè)停車場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車的狹長通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿n輛汽車，則后來的汽

32、車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后開入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必須按它停留的時(shí)間長短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。分析:綜合利用棧和隊(duì)列模擬停車場(chǎng)管理，學(xué)習(xí)利用棧和隊(duì)列解決實(shí)際問題。以棧模擬停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽

33、車在停車場(chǎng)內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車讓路而從停車場(chǎng)退出來的汽車，也用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號(hào)碼和進(jìn)入停車場(chǎng)的時(shí)刻。設(shè)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ù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)

34、碼及到達(dá)或離去的時(shí)刻，其中，A表示到達(dá)；D表示離去，E表示輸入結(jié)束。參考程序:#include#include#include#define MAX 2 /*車庫容量*/#define price 0.05 /*每車每分鐘費(fèi)用*/typedef struct timeint hour;int min;Time; /*時(shí)間結(jié)點(diǎn)*/typedef struct nodechar num10;Time reach;Time leave;CarNode; /*車輛信息結(jié)點(diǎn)*/typedef struct NODECarNode *stackMAX+1;int top;SeqStackCar; /*模擬

35、車站*/typedef struct carCarNode *data;struct car *next;QueueNode;typedef struct NodeQueueNode *head;QueueNode *rear;LinkQueueCar; /*模擬通道*/void InitStack(SeqStackCar *); /*初始化棧*/ int InitQueue(LinkQueueCar *); /*初始化便道*/int Arrival(SeqStackCar *,LinkQueueCar *); /*車輛到達(dá)*/ void Leave(SeqStackCar *,SeqStac

36、kCar *,LinkQueueCar *); /*車輛離開*/void List(SeqStackCar,LinkQueueCar); /*顯示存車信息*/ void main()SeqStackCar Enter,Temp;LinkQueueCar Wait;int ch;InitStack(&Enter); /*初始化車站*/ InitStack(&Temp); /*初始化讓路的臨時(shí)棧*/InitQueue(&Wait); /*初始化通道*/while(1) printf(n1. 車輛到達(dá));printf( 2. 車輛離開);printf( 3. 列表顯示);printf( 4. 退出系

37、統(tǒng)n);while(1)scanf(%d,&ch);if(ch=1&chtop=0;for(i=0;istacks-top=NULL;int InitQueue(LinkQueueCar *Q) /*初始化便道*/Q-head=(QueueNode *)malloc(sizeof(QueueNode);if(Q-head!=NULL)Q-head-next=NULL;Q-rear=Q-head;return(1);else return(-1);void PRINT(CarNode *p,int room) /*打印出站車的信息*/ int A1,A2,B1,B2;printf(n請(qǐng)輸入離開的

38、時(shí)間:/*:*/);scanf(%d:%d,&(p-leave.hour),&(p-leave.min);printf(n離開車輛的車牌號(hào)為:);puts(p-num);printf(n其到達(dá)時(shí)間為: %d:%d,p-reach.hour,p-reach.min);printf(離開時(shí)間為: %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應(yīng)交費(fèi)用為: %2.1f元,(B1-A1)*60+(B2-A2)*price);free(p);int

39、 Arrival(SeqStackCar *Enter,LinkQueueCar *W) /*車輛到達(dá)*/ CarNode *p;QueueNode *t;p=(CarNode *)malloc(sizeof(CarNode);flushall();printf(n請(qǐng)輸入車牌號(hào)(例:陜A1234):);gets(p-num);if(Enter-toptop+;printf(n車輛在車場(chǎng)第%d位置.,Enter-top);printf(n請(qǐng)輸入到達(dá)時(shí)間:/*:*/);scanf(%d:%d,&(p-reach.hour),&(p-reach.min);Enter-stackEnter-top=p

40、;return(1);else /*車場(chǎng)已滿，車進(jìn)便道*/ printf(n該車須在便道等待!);t=(QueueNode *)malloc(sizeof(QueueNode);t-data=p;t-next=NULL; W-rear-next=t;W-rear=t;return(1); void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) /*車輛離開*/int i, room;CarNode *p,*t;QueueNode *q;/*判斷車場(chǎng)內(nèi)是否有車*/if(Enter-top0) /*有車*/ while(1)

41、 /*輸入離開車輛的信息*/ printf(n請(qǐng)輸入車在車場(chǎng)的位置/1-%d/：,Enter-top);scanf(%d,&room);if(room=1&roomtop) break;while(Enter-toproom) /*車輛離開*/Temp-top+;Temp-stackTemp-top=Enter-stackEnter-top;Enter-stackEnter-top=NULL;Enter-top-; p=Enter-stackEnter-top;Enter-stackEnter-top=NULL;Enter-top-;while(Temp-top=1)Enter-top+;Enter-stackEnter-top=Temp-stackTemp-top;Temp-stackTe