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

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

3、用向量存放（2）棧底位置是固定不變的，可設(shè)置在向量兩端的任意一個端點(diǎn)（3）棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個整型量top （通常稱top為棧頂指針）來指示當(dāng)前棧頂位置-4y. rCP iv參考程序 :#include #include #define MAXNUM 2010#define ElemType int/* 定義順序棧的存儲結(jié)構(gòu) */ typedef struct ElemType stackMAXNUM; int top;SqStack;/* 初始化順序棧 */void InitStack(SqStack *p) if(!p)printf(Eorror); p-top=-

4、1;/*入棧 */void Push(SqStack *p,ElemType x) if(p-toptop=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 G

5、etTop(SqStack *p) ElemType x;if(p-top!=0)x=p-stackp-top;return(x); elseprintf(Underflow!n);return(0);/* 遍歷順序棧 */void OutStack(SqStack *p)int i; printf(n); if(p-toptop;i=0;i-) printf( 第 %d 個數(shù)據(jù)元素是：%6dn,i,p-stacki);/* 置空順序棧 */void setEmpty(SqStack *p)p-top= -1;/* 主函數(shù) */main() SqStack *q;int y,cord;Elem

6、Type a;doprintf(n);printf( 第一次使用必須初始化！ printf(n);n);printf(n主菜單n);printf(n1初始化順序棧n);printf(n2插入一個元素n);printf(n3刪除棧頂元素n);printf(n4取棧頂元素n);printf(n5置空順序棧n);printf(n6結(jié)束程序運(yùn)行n);printf(nn);printf( 請輸入您的選擇 ( 1, 2, 3, 4, 5,6); scanf(%d,&cord);printf(n); switch(cord) case 1:q=(SqStack*)malloc(sizeof(SqStack)

7、;InitStack(q);OutStack(q);break;case 2: printf( 請輸入要插入的數(shù)據(jù)元素： a=); scanf(%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;P

8、rintf(n 已經(jīng)初始化鏈棧！ n);/* 鏈棧置空 */void setEmPty(LinkStack * s) s-toP=NULL;Printf(n 鏈棧被置空！ n);/*入棧*/void PushLstack(LinkStack * s, ElemtyPe x) StackNode * P;P=(StackNode *)malloc(sizeof(StackNode); / 建立一個節(jié)點(diǎn)。 P-data=x;/由于是在棧頂P ushLstack，所以要指向棧頂。/插入P-next=s-toP; s-toP=P;/*出棧*/ElemtyPe x; StackNode * P;P=s-

9、toP; if (s-toP =0) Printf(n 棧空，不能出棧！ n);exit(-1); x=P-data; s-toP=P-next; free(P); return x;ElemtyPe PoPLstack(LinkStack * s)/指向棧頂/當(dāng)前的棧頂指向原棧的 next/釋放/* 取棧頂元素 */Elemtype StackTop(LinkStack *s) if (s-top =0) printf(n 鏈棧空 n); exit(-1); return s-top-data;/* 遍歷鏈棧 */ void Disp(LinkStack * s) printf(n 鏈棧中的

10、數(shù)據(jù)為： n); printf(= StackNode * p; p=s-top; while (p!=NULL) printf(%dn,p-data); p=p-next; printf(= void main() printf(= int i,m,n,a; LinkStack * s; s=(LinkStack *)malloc(sizeof(LinkStack); int cord;do printf(n);printf( 第一次使用必須初始化！ n); printf(n);鏈棧操作printf(n主菜單n);printf(n1初始化鏈棧n);printf(n2入棧n);printf(n

11、3出棧n);printf(n4取棧頂元素n);printf(n5置空鏈棧n);printf(n6結(jié)束程序運(yùn)行n);printf(nn);printf( 請輸入您的選擇 ( 1, 2, 3, 4, 5,6); scanf(%d,&cord);printf(n);switch(cord) case 1: InitStack(s);Disp(s);n);n);nn);break;case 2:printf( 輸入將要壓入鏈棧的數(shù)據(jù)的個數(shù)： n=);scanf(%d,&n);printf( 依次將 %d 個數(shù)據(jù)壓入鏈棧： n,n);for(i=1;i=n;i+)scanf(%d,&a);pushLst

12、ack(s,a);Disp(s);break;case 3: 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;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í)

13、現(xiàn)并在此基礎(chǔ)上設(shè)計一個主程序， 完成如下功能：初始化隊(duì)列 建立順序隊(duì)列 入隊(duì) 出隊(duì) 判斷隊(duì)列是否為空 取隊(duì)頭元素實(shí)驗(yàn)內(nèi)容與要求 編寫一個程序?qū)崿F(xiàn)順序隊(duì)列的各種基本運(yùn)算， （1）（2）（3）（4）（5）（6）127）遍歷隊(duì)列分析:隊(duì)列的順序存儲結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表。 入隊(duì)時，將新元素插入 rear所指的位置，然后將 rear加1。出隊(duì)時， 然后將 front 加 1 并返回被刪元素。 順序隊(duì)列中的溢出現(xiàn)象： （1 ） 下溢現(xiàn)象。當(dāng)隊(duì)列為空時，做出隊(duì)運(yùn)算產(chǎn)生的溢出現(xiàn)象。 作程序控制轉(zhuǎn)移的條件。 （2） 真上溢 現(xiàn)象。 狀態(tài)，應(yīng)設(shè)法避免。 （3） 假上溢 現(xiàn)象。 間永遠(yuǎn)

14、無法重新利用。當(dāng)隊(duì)列滿時，做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。刪去 front 所指的元素，下溢”是正常現(xiàn)象，常用真上溢 ”是一種出錯由于入隊(duì)和出隊(duì)操作中，頭尾指針只增加不減小，當(dāng)隊(duì)列中實(shí)際的元素個數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模時，假上溢 現(xiàn)象。致使被刪元素的空也可能由于尾指針已超越向量空間的上界而不能做入隊(duì)操作。該現(xiàn)象稱為 注意：（1）當(dāng)頭尾指針相等時，隊(duì)列為空。（2）在非空隊(duì)列里，隊(duì)頭指針始終指向隊(duì)頭元素，尾指針始終指向隊(duì)尾元素的下一位置。-4y. rCP iv參考程序 :#include #include #define MAXNUM 100 #define Elemtype int #define

15、 TRUE 1 #define FALSE 0 typedef struct Elemtype queueMAXNUM;int front;int rear;sqqueue;/* 隊(duì)列初始化 */ int initQueue(sqqueue *q) if(!q) return FALSE;q-front=-1; q-rear=-1;return TRUE;/* 入隊(duì)*/ int append(sqqueue *q, Elemtype x) if(q-rear=MAXNUM-1) return FALSE; q-rear+; q-queueq-rear=x; return TRUE;30/*出隊(duì)

16、 */Elemtype Delete(sqqueue *q) /* 遍歷隊(duì)列 */ void display(sqqueue *q) :rear=%dn,q-rear);:front=%dn,q-front);/* 建立順序隊(duì)列 */ void Setsqqueue(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;

17、/* 取隊(duì)頭元素 */int gethead(sqqueue *q) if (q-front=q-rear) return 0; return(q-queueq-front+1);int s;s=q-front;if (q-front=q-rear) printf( 隊(duì)列空 !n); elseprintf(n 順序隊(duì)列依次為： ); while(srear) s=s+1; printf(%dqueues); printf(n);printf( 順序隊(duì)列的隊(duì)尾元素所在位置 printf( 順序隊(duì)列的隊(duì)頭元素所在位置 int n,i,m;printf(n 請輸入將要入順序隊(duì)列的長度scanf(%d

18、,&n);printf(n 請依次輸入入順序隊(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 第一次使用請初始化！ n);printf(n 請選擇操作 (1-7):n);printf(= printf(1 printf(2 printf(3 printf(4 printf(5 printf(6 printf(7 printf(=初始化 n); 建立順序隊(duì)列 n); 入

19、隊(duì) n);出隊(duì) n); 判斷隊(duì)列是否為空 n); 取隊(duì)頭元素 n); 遍歷隊(duì)列 n);n);n);initQueue(head);printf( 已經(jīng)初始化順序隊(duì)列！ n); break;scanf(%d,&select); switch(select) case 1:case 2:Setsqqueue(head);printf(n 已經(jīng)建立隊(duì)列！ n); display(head);break;case 3:printf( 請輸入隊(duì)的值 :n ); scanf(%d,&x); append(head,x); display(head);break; case 4: z=Delete(head

20、);printf(n 隊(duì)頭元素 %d 已經(jīng)出隊(duì)！ n,z); display(head);break;case 5: if(Empty(head)printf( 隊(duì)列空 n);elseprintf( 隊(duì)列非空 n);break;case 6: y=gethead(head);printf( 隊(duì)頭元素為 :%dn,y); break;case 7: display(head);break;while(select=7);實(shí)驗(yàn) 4 隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)初始化并建立鏈隊(duì)列入鏈隊(duì)列出鏈隊(duì)列 遍歷鏈隊(duì)列實(shí)驗(yàn)內(nèi)容與要求 : 編寫一個程序?qū)崿F(xiàn)鏈隊(duì)列的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計一個主程序，完成如下功能：

21、（1）（2）（3）（4） 分析: 隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊(duì)列。它是限制僅在表頭刪除和表尾插入的單鏈表。 注意：（1）和鏈棧類似，無須考慮判隊(duì)滿的運(yùn)算及上溢。（2）在出隊(duì)算法中，一般只需修改隊(duì)頭指針。但當(dāng)原隊(duì)中只有一個結(jié)點(diǎn)時，該結(jié)點(diǎn)既是隊(duì) 頭也是隊(duì)尾，故刪去此結(jié)點(diǎn)時亦需修改尾指針，且刪去此結(jié)點(diǎn)后隊(duì)列變空。（3）和單鏈表類似，為了簡化邊界條件的處理，在隊(duì)頭結(jié)點(diǎn)前可附加一個頭結(jié)點(diǎn)。 參考程序 :#include #include #define ElemType int typedef struct Qnode ElemType data;struct Qnode *next; Qnodetyp

22、e; typedef struct Qnodetype *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) Qnodetype *h;int i,n,x;printf( 輸入將建立鏈隊(duì)列元素的個數(shù)： n= ); scanf(%d,&n);

23、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) Qnodetype *p;p=q-front-next; /* 指向第一個數(shù)據(jù)元素節(jié)點(diǎn) pr

24、intf(n 鏈隊(duì)列元素依次為： while(p!=NULL) printf(%d-,p-data); p=p-next; printf(nn 遍歷鏈隊(duì)列結(jié)束！ main() Lqueue *p;int x,cord;printf(n* 第一次操作請選擇初始化并建立鏈隊(duì)列！ do);n);*/*n ); printf(nprintf(=printf(主菜單n);=n);printf(=n);printf(1初始化并建立鏈隊(duì)列n);printf(2入鏈隊(duì)列n);printf(3出鏈隊(duì)列n);printf(4遍歷鏈隊(duì)列n);printf(5結(jié)束程序運(yùn)行n);鏈隊(duì)列的基本操作 n );n);prin

25、tf(= scanf(%d,&cord); switch(cord) case 1:p=(Lqueue *)malloc(sizeof(Lqueue);creat(p);display(p);break;case 2: printf( 請輸入隊(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);break;case 5:exit (0);while (cord=5);3.4 提高實(shí)驗(yàn)實(shí)驗(yàn)

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

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

28、 nodeint 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,0,0,0,0,

29、0,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; /* 回溯算法 */ do if(topi.c5)/ 還可以向前試探if(topi.x=5 & topi.y=9) /已找到一個組合 / 打印路徑printf(The way %d is:n,

30、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.x;topi.

31、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+1topi.y

32、=0)i+;topi.x=topi-1.x+1;topi.y=topi-1.y;mazetopi.xtopi.y=2;else topi.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 停車場管理 實(shí)驗(yàn)內(nèi)容與要求 :設(shè)停車場內(nèi)只有一個可停放 n 輛汽車的狹長通道， 且只有一個大門可供汽車進(jìn)出。 汽車在 停車場內(nèi)按車輛到達(dá)時間的先后順序， 依次由北向南排列 （大門在最南端， 最先到達(dá)的第一 輛車停放在車場的最北端） ，若車場內(nèi)已停滿 n

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

34、達(dá)或離 去的時刻， 對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為： 若是車輛到達(dá)， 則輸出汽車在停車 場內(nèi)或便道上的停車位置； 若是車離去； 則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費(fèi)用 （在便道上停留的時間不收費(fèi)） 。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。 需另設(shè)一個棧， 臨時停放為給要離去的汽車讓路而從停車場退出來的汽車， 構(gòu)實(shí)現(xiàn)。 輸入數(shù)據(jù)按到達(dá)或離去的時刻有序。 棧中每個元素表示一輛汽車， 汽車的牌照號碼和進(jìn)入停車場的時刻。3， 20）， （ A，設(shè) n=2,輸入數(shù)據(jù)為：（ A 1, 5）, （ A 2,10）, （ D ,15）, （ A4， 25），（A，5， 30），（D，2， 35），（

35、D，4， 40），（E，0， 0）。每一組輸入數(shù)據(jù)包括 三個數(shù)據(jù)項(xiàng)：汽車 到達(dá)”或 離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，其中，A表示到達(dá)； DI示離去，戰(zhàn)示輸入結(jié)束。參考程序 :#include #include#include#define MAX 2 /* 車庫容量 */#define price 0.05 /* 每車每分鐘費(fèi)用 */ typedef struct timeint hour;int min;Time; /* 時間結(jié)點(diǎn) */typedef struct node char num10;Time reach; Time leave;CarNode; /* 車輛信息結(jié)點(diǎn)

36、*/ typedef struct NODECarNode *stackMAX+1;int top;SeqStackCar; /* 模擬車站 */ typedef struct carCarNode *data; struct car *next;QueueNode; typedef struct NodeQueueNode *head; QueueNode *rear;LinkQueueCar; /* 模擬通道 */ void InitStack(SeqStackCar *); /* 初始化棧 */ int InitQueue(LinkQueueCar *); /* 初始化便道 */ int

37、 Arrival(SeqStackCar *,LinkQueueCar *); /* 車輛到達(dá) */ void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *); /* 車輛離開 */ void List(SeqStackCar,LinkQueueCar); /* 顯示存車信息 */ void main()SeqStackCar Enter,Temp; LinkQueueCar Wait;初始化車站 */ 初始化讓路的臨時棧 */ 初始化通道 */int ch;InitStack(&Enter); /* InitStack(&Temp); /*

38、 InitQueue(&Wait); /* while(1)車輛離開 ); 列表顯示 );退出系統(tǒng) n); printf(n1. 車輛到達(dá) ); printf( 2. printf( 3. printf( 4. 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

39、=Q-head;return(1);else return(-1);void PRINT(CarNode *p,int room) /* 打印出站車的信息 */int A1,A2,B1,B2;printf(n 請輸入離開的時間 :/*:*/); scanf(%d:%d,&(p-leave.hour),&(p-leave.min); printf(n 離開車輛的車牌號為 :);puts(p-num);printf(n 其到達(dá)時間為 : %d:%d,p-reach.hour,p-reach.min); printf( 離開時間為 : %d:%d,p-leave.hour,p-leave.min);

40、 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 Arrival(SeqStackCar *Enter,LinkQueueCar *W) /* 車輛到達(dá) */ CarNode *p;QueueNode *t;p=(CarNode *)malloc(sizeof(CarNode);flushall();printf(n 請輸入車牌號 (例：陜 A1234)：);gets(p-num);if(Enter

41、-toptop+;printf(n 車輛在車場第 %d 位置 .,Enter-top);printf(n 請輸入到達(dá)時間 ：/*：*/); scanf(%d：%d,&(p-reach.hour),&(p-reach.min); Enter-stackEnter-top=p;return(1);else /*車場已滿，車進(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(SeqS

42、tackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) /* 車輛離開 */int i, room;CarNode *p,*t;QueueNode *q;/* 判斷車場內(nèi)是否有車 */ if(Enter-top0) /* 有車 */ while(1) /* 輸入離開車輛的信息 */printf(n 請輸入車在車場的位置 /1-%d/ ： ,Enter-top); scanf(%d,&room);if(room=1&roomtop) break; while(Enter-toproom) /* 車輛離開 */Temp-top+; Temp-stackT

43、emp-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-stackTemp-top=NULL;Temp-top-;PRINT(p,room);/* 判斷通道上是否有車及車站是否已滿 */ if(W-head!=W-rear)&Enter-tophead-next;t=q-data;Enter-top+;printf(n 便道的 %s 號車進(jìn)入車場第 %d 位置 .,t-num,Enter-top); printf(n 請輸入現(xiàn)在的時間 /*:*/:);scanf(%d:%d,&(t-reach.hour),&(t-reach.min); W-head-next=q-next;if(q=W-rear) W-rear=W-head; Enter-stackEnter-top=t;free(q);else printf(n 便道里沒有車 .n);