【正文】 tQueue(amp。Wait)。 /*初始化通道*/while(1){ printf(\n1. 車輛到達(dá))。printf( 2. 車輛離開)。printf( 3. 列表顯示)。printf( 4. 退出系統(tǒng)\n)。while(1){scanf(%d,amp。ch)。if(ch=1amp。amp。ch=4)break。else printf(\n請選擇： 1|2|3|4.)。}switch(ch){ case 1:Arrival(amp。Enter,amp。Wait)。break。 /*車輛到達(dá)*/case 2:Leave(amp。Enter,amp。Temp,amp。Wait)。break。 /*車輛離開*/case 3:List(Enter,Wait)。break。 /*列表打印信息*/case 4:exit(0)。 /*退出主程序*/default: break。}}}void InitStack(SeqStackCar *s) /*初始化棧*/ { int i。stop=0。for(i=0。i=MAX。i++)sstack[stop]=NULL。}int InitQueue(LinkQueueCar *Q) /*初始化便道*/{Qhead=(QueueNode *)malloc(sizeof(QueueNode))。if(Qhead!=NULL){Qheadnext=NULL。Qrear=Qhead。return(1)。}else return(1)。}void PRINT(CarNode *p,int room) /*打印出站車的信息*/ {int A1,A2,B1,B2。printf(\n請輸入離開的時(shí)間:/**:**/)。scanf(%d:%d,amp。(p),amp。(p))。printf(\n離開車輛的車牌號為:)。puts(pnum)。printf(\n其到達(dá)時(shí)間為: %d:%d,p,p)。printf(離開時(shí)間為: %d:%d,p,p)。A1=p。A2=p。B1=p。B2=p。printf(\n應(yīng)交費(fèi)用為: %,((B1A1)*60+(B2A2))*price)。free(p)。}int Arrival(SeqStackCar *Enter,LinkQueueCar *W) /*車輛到達(dá)*/ { CarNode *p。QueueNode *t。p=(CarNode *)malloc(sizeof(CarNode))。flushall()。printf(\n請輸入車牌號(例:陜A1234):)。gets(pnum)。if(EntertopMAX) /*車場未滿，車進(jìn)車場*/{Entertop++。printf(\n車輛在車場第%d位置.,Entertop)。printf(\n請輸入到達(dá)時(shí)間:/**:**/)。scanf(%d:%d,amp。(p),amp。(p))。Enterstack[Entertop]=p。return(1)。}else /*車場已滿，車進(jìn)便道*/{ printf(\n該車須在便道等待!)。t=(QueueNode *)malloc(sizeof(QueueNode))。tdata=p。tnext=NULL。 Wrearnext=t。Wrear=t。return(1)。 }}void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W){ /*車輛離開*/int i, room。CarNode *p,*t。QueueNode *q。/*判斷車場內(nèi)是否有車*/if(Entertop0) /*有車*/ { while(1) /*輸入離開車輛的信息*/ {printf(\n請輸入車在車場的位置/1%d/：,Entertop)。scanf(%d,amp。room)。if(room=1amp。amp。room=Entertop) break。}while(Entertoproom) /*車輛離開*/{Temptop++。Tempstack[Temptop]=Enterstack[Entertop]。Enterstack[Entertop]=NULL。Entertop。} p=Enterstack[Entertop]。Enterstack[Entertop]=NULL。Entertop。while(Temptop=1){Entertop++。Enterstack[Entertop]=Tempstack[Temptop]。Tempstack[Temptop]=NULL。Temptop。}PRINT(p,room)。/*判斷通道上是否有車及車站是否已滿*/if((Whead!=Wrear)amp。amp。EntertopMAX) /*便道的車輛進(jìn)入車場*/{ q=Wheadnext。t=qdata。Entertop++。printf(\n便道的%s號車進(jìn)入車場第%d位置.,tnum,Entertop)。printf(\n請輸入現(xiàn)在的時(shí)間/**:**/:)。scanf(%d:%d,amp。(t),amp。(t))。Wheadnext=qnext。if(q==Wrear) Wrear=Whead。Enterstack[Entertop]=t。free(q)。}else printf(\n便道里沒有車.\n)。}else printf(\n車場里沒有車.)。 /*沒車*/ }void List1(SeqStackCar *S) /*列表顯示車場信息*/{int i。if(Stop0) /*判斷車站內(nèi)是否有車*/{printf(\n車場:)。printf(\n 位置 到達(dá)時(shí)間 車牌號\n)。for(i=1。i=Stop。i++){printf( %d ,i)。printf(%d:%d ,Sstack[i],Sstack[i])。puts(Sstack[i]num)。}}else printf(\n車場里沒有車)。}void List2(LinkQueueCar *W) /*列表顯示便道信息*/{ QueueNode *p。p=Wheadnext。if(Whead!=Wrear) /*判斷通道上是否有車*/{printf(\n等待車輛的號碼為:)。while(p!=NULL){puts(pdatanum)。p=pnext。}}else printf(\n便道里沒有車.)。 }void List(SeqStackCar S,LinkQueueCar W){int flag,tag。flag=1。while(flag){printf(\n請選擇 1|2|3:)。printf(\\\\n)。while(1){ scanf(%d,amp。tag)。if(tag=1||tag=3) break。else printf(\n請選擇 1|2|3:)。}switch(tag){case 1:List1(amp。S)。break。 /*列表顯示車場信息*/case 2:List2(amp。W)。break。 /*列表顯示便道信息*/case 3:flag=0。break。default: break。 }}}：（1）讀棧頂元素的算法與退棧頂元素的算法有何區(qū)別？（2）如果一個(gè)程序中要用到兩個(gè)棧，為了不發(fā)生上溢錯(cuò)誤，就必須給每個(gè)棧預(yù)先分配一個(gè)足夠大的存儲(chǔ)空間。若每個(gè)棧都預(yù)分配過大的存儲(chǔ)空間，勢必會(huì)造成系統(tǒng)空間緊張。如何解決這個(gè)問題？（3）棧的兩種存儲(chǔ)結(jié)構(gòu)在判別?？张c棧滿時(shí)，所依據(jù)的條件有何不同？（4）在程序中同時(shí)使用兩個(gè)以上的棧時(shí)，使用順序棧共享鄰接空間則很難實(shí)現(xiàn)，能否通過鏈棧來方便地實(shí)現(xiàn)？如何實(shí)現(xiàn)？（5）簡述棧和隊(duì)列的共同點(diǎn)和不同點(diǎn)。它們?yōu)槭裁磳儆诰€性表？（6）在順序隊(duì)列中，當(dāng)隊(duì)尾指針已經(jīng)指向了隊(duì)列的最后一個(gè)位置時(shí)，但事實(shí)上隊(duì)列中可能還有空位置。此時(shí)若有元素入列，就會(huì)發(fā)生“假溢出”。如何解決這個(gè)問題？（7）鏈棧只有一個(gè)top指針，對于鏈隊(duì)列，為什么要設(shè)計(jì)一個(gè)頭指針和一個(gè)尾指針？（8）一個(gè)程序中如果要用到兩個(gè)棧時(shí)，可通過兩個(gè)棧共享一維數(shù)組來實(shí)現(xiàn)。即雙向棧共享鄰接空間。如果一個(gè)程序中要用到兩個(gè)隊(duì)列，能否實(shí)現(xiàn)？如何實(shí)現(xiàn)？假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注意：不設(shè)頭指針），試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列算法。(9) 設(shè)計(jì)算法實(shí)現(xiàn)括弧配對的檢查。(10) 設(shè)計(jì)算法求解迷宮的一條最短路徑。(11) 求解“背包問題”。 “背包問題”的基本描述是：有一個(gè)背包，能盛放的物品總重量為 S，設(shè)有 N 件物品，其重量分別為w1，w2，...，wn，希望從N件物品中選擇若干件物品，所選物品的重量之和恰能放入該背包，即所選物品的重量之和等于S 。23