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

棧的操作(實(shí)驗(yàn)報(bào)告)(此文檔為word格式，下載后您可任意編輯修改！)實(shí)驗(yàn)三棧和隊(duì)列3.1實(shí)驗(yàn)?zāi)康模菏煜５奶攸c(diǎn)（先進(jìn)后出）及棧的基本操作，如入棧、出棧等，掌握棧的基本操作在棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)；熟悉隊(duì)列的特點(diǎn)（先進(jìn)先出）及隊(duì)列的基本操作，如入隊(duì)、出隊(duì)等，掌握隊(duì)列的基本操作在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。實(shí)驗(yàn)要求：復(fù)習(xí)課本中有關(guān)棧和隊(duì)列的知識(shí)；用C語(yǔ)言完成算法和程序設(shè)計(jì)并上機(jī)調(diào)試通過(guò)；撰寫實(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é)果）?；A(chǔ)實(shí)驗(yàn)[實(shí)驗(yàn)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）置空順序棧棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第1頁(yè)。分析:棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第1頁(yè)。棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧,它是運(yùn)算受限的順序表。對(duì)于順序棧，入棧時(shí)，首先判斷棧是否為滿，棧滿的條件為：p->top==MAXNUM-1，棧滿時(shí)，不能入棧;否則出現(xiàn)空間溢出，引起錯(cuò)誤，這種現(xiàn)象稱為上溢。出棧和讀棧頂元素操作，先判棧是否為空，為空時(shí)不能操作，否則產(chǎn)生錯(cuò)誤。通常棧空作為一種控制轉(zhuǎn)移的條件。注意：（1）順序棧中元素用向量存放（2）棧底位置是固定不變的，可設(shè)置在向量?jī)啥说娜我庖粋€(gè)端點(diǎn)（3）棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個(gè)整型量top（通常稱top為棧頂指針）來(lái)指示當(dāng)前棧頂位置參考程序:#include<stdio.");}*出棧*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); }}*獲取棧頂元素*棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第2頁(yè)。ElemTypeGetTop(SqStack*p)棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第2頁(yè)。{ ElemTypex; if(p->top!=0) { x=p->stack[p->top]; return(x); } else { printf("Underflow!\n"); return(0); }}*遍歷順序棧*voidOutStack(SqStack*p){ inti; printf("\n"); if(p->top<0) printf("這是一個(gè)空棧！"); printf("\n"); for(i=p->top;i>=0;i--) printf("第%d個(gè)數(shù)據(jù)元素是：%6d\n",i,p->stack[i]);}*置空順序棧*voidsetEmpty(SqStack*p){p->top=-1;}*主函數(shù)*main(){SqStack*q; inty,cord;ElemTypea;棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第3頁(yè)。 do{棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第3頁(yè)。 printf("\n"); printf("第一次使用必須初始化！\n"); printf("\n"); printf("\n主菜單\n"); printf("\n1初始化順序棧\n"); printf("\n2插入一個(gè)元素\n"); printf("\n3刪除棧頂元素\n"); printf("\n4取棧頂元素\n"); printf("\n5置空順序棧\n"); printf("\n6結(jié)束程序運(yùn)行\(zhòng)n"); printf("\n\n"); printf("請(qǐng)輸入您的選擇(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: { printf("請(qǐng)輸入要插入的數(shù)據(jù)元素：a="); scanf("%d",&a); Push(q,a); OutStack(q); }break; case3: { Pop(q); OutStack(q);棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第4頁(yè)。 }break;棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第4頁(yè)。 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);}[實(shí)驗(yàn)2]棧的鏈?zhǔn)奖硎竞蛯?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）遍歷鏈棧分析:鏈棧是沒(méi)有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。注意：（1）LinkStack結(jié)構(gòu)類型的定義可以方便地在函數(shù)體中修改top指針本身（2）若要記錄棧中元素個(gè)數(shù)，可將元素個(gè)數(shù)屬性放在LinkStack類型中定義。棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第5頁(yè)。（3）鏈棧中的結(jié)點(diǎn)是動(dòng)態(tài)分配的，所以可以不考慮上溢。棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第5頁(yè)。參考程序:#include"stdio.");}*鏈棧置空*voidsetEmpty(LinkStack*s){ s->top=NULL;printf("\n鏈棧被置空！\n");}*入棧*voidpushLstack(LinkStack*s,Elemtypex){ StackNode*p; p=(StackNode*)malloc(sizeof(StackNode));建立一個(gè)節(jié)點(diǎn)。 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;當(dāng)前的棧頂指向原棧的next free(p);釋放 returnx;棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第6頁(yè)。}棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第6頁(yè)。*取棧頂元素*ElemtypeStackTop(LinkStack*s){ if(s->top==0) { printf("\n鏈棧空\(chéng)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");棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第7頁(yè)。 printf("\n主菜單\n");棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第7頁(yè)。 printf("\n1初始化鏈棧\n"); printf("\n2入棧\n"); printf("\n3出棧\n"); printf("\n4取棧頂元素\n"); printf("\n5置空鏈棧\n"); printf("\n6結(jié)束程序運(yùn)行\(zhòng)n"); printf("\n\n"); printf("請(qǐng)輸入您的選擇(1,2,3,4,5,6)"); scanf("%d",&cord); printf("\n"); switch(cord) { case1: {InitStack(s); Disp(s); }break; case2: {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; case3: { printf("\n出棧操作開始!\n"); printf("輸入將要出棧的數(shù)據(jù)個(gè)數(shù)：m="); scanf("%d",&m);棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第8頁(yè)。 for(i=1;i<=m;i++)棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第8頁(yè)。 {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);}

[實(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ì)列分析:棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第9頁(yè)。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表。棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第9頁(yè)。入隊(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)無(wú)法重新利用。當(dāng)隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模時(shí)，也可能由于尾指針已超越向量空間的上界而不能做入隊(duì)操作。該現(xiàn)象稱為"假上溢"現(xiàn)象。注意：（1）當(dāng)頭尾指針相等時(shí)，隊(duì)列為空。（2）在非空隊(duì)列里，隊(duì)頭指針始終指向隊(duì)頭元素，尾指針始終指向隊(duì)尾元素的下一位置。參考程序:#include<stdio.FALSE; q->front=-1; q->rear=-1; returnTRUE;}*入隊(duì)*intappend(sqqueue*q,Elemtypex){ if(q->rear>=MAXNUM-1)returnFALSE; q->rear++; q->queue[q->rear]=x; returnTRUE;}*出隊(duì)*ElemtypeDelete(sqqueue*q){ Elemtypex;棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第10頁(yè)。 if(q->front==q->rear)return0;棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第10頁(yè)。 x=q->queue[++q->front]; returnx;}*判斷隊(duì)列是否為空*intEmpty(sqqueue*q){ if(q->front==q->rear)returnTRUE;returnFALSE;}*取隊(duì)頭元素*intgethead(sqqueue*q){ if(q->front==q->rear)return0;return(q->queue[q->front+1]);}*遍歷隊(duì)列*voiddisplay(sqqueue*q){ ints; s=q->front; if(q->front==q->rear) printf("隊(duì)列空!\n"); else {printf("\n順序隊(duì)列依次為："); while(s<q->rear) {s=s+1; printf("%d<-",q->queue[s]); } printf("\n");printf("順序隊(duì)列的隊(duì)尾元素所在位置:rear=%d\n",q->rear); printf("順序隊(duì)列的隊(duì)頭元素所在位置:front=%d\n",q->front); }棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第11頁(yè)。}棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第11頁(yè)。*建立順序隊(duì)列*voidSetsqqueue(sqqueue*q){ intn,i,m; printf("\n請(qǐng)輸入將要入順序隊(duì)列的長(zhǎng)度:"); scanf("%d",&n); printf("\n請(qǐng)依次輸入入順序隊(duì)列的元素值:\n"); for(i=0;i<n;i++) { scanf("%d",&m); append(q,m);} }main(){sqqueue*"); printf("\n請(qǐng)選擇操作(1--7):\n"); printf("===================================\n"); printf("1初始化\n"); printf("2建立順序隊(duì)列\(zhòng)n"); printf("3入隊(duì)\n"); printf("4出隊(duì)\n"); printf("5判斷隊(duì)列是否為空\(chéng)n"); printf("6取隊(duì)頭元素\n"); printf("7遍歷隊(duì)列\(zhòng)n"); printf("===================================\n"); scanf("%d",&select); switch(select) {case1: {initQueue("); break; }case2:棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第12頁(yè)。 {Setsqqueue(");棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第12頁(yè)。 display("); scanf("%d",&x); append(",z); display("); else printf("隊(duì)列非空\(chéng)n");break; } case6: { y=gethead(",y); break; } case7: { display(,x; printf("輸入將建立鏈隊(duì)列元素的個(gè)數(shù)：n="); scanf("%d",&n); ;i++) { printf("鏈隊(duì)列第%d個(gè)元素的值為：",i); scanf("%d",&x); Lappend(q,x); }}*出鏈隊(duì)列*ElemTypeLdelete(Lqueue*q){ Qnodetype*p; ElemTypex; if(q->front==q->rear) { printf("隊(duì)列為空!\n"); x=0;棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第13頁(yè)。 }棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第13頁(yè)。 else { p=q->front->next; q->front->next=p->next; if(p->next==NULL) q->rear=q->front; x=p->data; free(p); } return(x);}*遍歷鏈隊(duì)列*voiddisplay(Lqueue*q){ Qnodetype*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("\n\n遍歷鏈隊(duì)列結(jié)束！\n");}main(){ Lqueue*p; intx,cord; printf("\n*****第一次操作請(qǐng)選擇初始化并建立鏈隊(duì)列！*****\n"); do {printf("\n鏈隊(duì)列的基本操作\n"); printf("=========================================\n"); printf("主菜單\n");棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第14頁(yè)。 printf("=========================================\n");棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第14頁(yè)。 printf("1初始化并建立鏈隊(duì)列\(zhòng)n"); printf("2入鏈隊(duì)列\(zhòng)n"); printf("3出鏈隊(duì)列\(zhòng)n"); printf("4遍歷鏈隊(duì)列\(zhòng)n"); printf("5結(jié)束程序運(yùn)行\(zhòng)n"); printf("==========================================\n"); scanf("%d",&cord); switch(cord) { case1: { p=(Lqueue*)malloc(sizeof(Lqueue)); creat(p); display(p); }break; case2: { printf("請(qǐng)輸入隊(duì)列元素的值：x="); scanf("%d",&x); Lappend(p,x); display(p); }break; case3: { printf("出鏈隊(duì)列元素：x=%d\n",Ldelete(p)); display(p); }break; case4: {display(p);}break; case5: {exit(0);} } }while(cord<=5);棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第15頁(yè)。}棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第15頁(yè)。

3.4提高實(shí)驗(yàn)[實(shí)驗(yàn)1]迷宮的求解實(shí)驗(yàn)內(nèi)容與要求:迷宮只有兩個(gè)門，一個(gè)叫做入口，另一個(gè)叫做出口。把一只老鼠從一個(gè)無(wú)頂蓋的大盒子的入口處趕進(jìn)迷宮。迷宮中設(shè)置很多隔壁，對(duì)前進(jìn)方向形成了多處障礙，在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。求解迷宮問(wèn)題，即找出從入口到出口的路徑。分析:迷宮問(wèn)題是棧應(yīng)用的一個(gè)典型例子。求解過(guò)程可采用回溯法。回溯法是一種不斷試探且及時(shí)糾正錯(cuò)誤的搜索方法。從入口出發(fā)，按某一方向向前探索，若能走通（未走過(guò)的），即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一方向;若所有的方向均沒(méi)有通路，則沿原路返回前一點(diǎn)，換下一個(gè)方向再繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無(wú)路可走又返回到入口點(diǎn)。在求解過(guò)程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走（無(wú)路）時(shí)，能正確返回前一點(diǎn)以便繼續(xù)從下一個(gè)方向向前試探，則需要用一個(gè)棧保存所能夠到達(dá)的每一點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向，棧中保存的就是一條迷宮的通路。為了確保程序能夠終止，調(diào)整時(shí)，必須保證曾被放棄過(guò)的填數(shù)序列不被再次試驗(yàn)，即要求按某種有序模型生成填數(shù)序列。給解的候選者設(shè)定一個(gè)被檢驗(yàn)的順序，按這個(gè)順序逐一生成候選者并檢驗(yàn)。參考程序::#include<stdio.(){初始化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++)棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第16頁(yè)。

printf(maze[i][j]?"*":"

");棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第16頁(yè)。

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)已找到一個(gè)組合

{

打印路徑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;

i--;

top[i].c+=1;

continue;}

switch(top[i].c)

向前試探

{

case1:{

if(maze[top[i].x][top[i].y+1]==0)

{i++;棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第17頁(yè)。

top[i].x=top[i-棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第17頁(yè)。

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;}棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第18頁(yè)。

else棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第18頁(yè)。

{

top[i].c+=1;}

break;}

}

}

else

回溯

{if(i==0)return;

已找完所有解

maze[top[i].x][top[i].y]=0;

top[i].c=1;

i--;

top[i].c+=1;}}while(1);}[實(shí)驗(yàn)2]停車場(chǎng)管理實(shí)驗(yàn)內(nèi)容與要求:設(shè)停車場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿n輛汽車，則后來(lái)的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后開入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。分析:綜合利用棧和隊(duì)列模擬停車場(chǎng)管理，學(xué)習(xí)利用棧和隊(duì)列解決實(shí)際問(wèn)題。以棧模擬停車場(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á)，則輸出汽車在停車場(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í)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第19頁(yè)。需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車讓路而從停車場(chǎng)退出來(lái)的汽車，也用順序存儲(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í)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第19頁(yè)。設(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)碼及到達(dá)或離去的時(shí)刻，其中，‘A’表示到達(dá)；‘D’表示離去，‘E’表示輸入結(jié)束。參考程序: #include<stdio.;}Time;*時(shí)間結(jié)點(diǎn)*typedefstructnode{charnum[10];Timereach;Timeleave;}CarNode;*車輛信息結(jié)點(diǎn)*typedefstructNODE{CarNode*stack[MAX+1];inttop;}SeqStackCar;*模擬車站*typedefstructcar{CarNode*data;structcar*next;}QueueNode;typedefstructNode{QueueNode*(){SeqStackCarEnter,Temp;LinkQueueCarWait;intch;InitStack(&Enter);*初始化車站*InitStack(&Temp);*初始化讓路的臨時(shí)棧*棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第20頁(yè)。InitQueue(&Wait);*初始化通道*棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第20頁(yè)。while(1){printf("\n1.車輛到達(dá)");printf("2.車輛離開");printf("3.列表顯示");printf("4.退出系統(tǒng)\n");while(1){scanf("%d",&ch);if(ch>=1&&ch<=4)break;elseprintf("\n請(qǐng)選擇：1|2|3|4.");}switch(ch){case1:Arrival(&Enter,&Wait);break;*車輛到達(dá)*case2:Leave(&Enter,&Temp,&Wait);break;*車輛離開*case3:List(Enter,Wait);break;*列表打印信息*case4:exit(0);*退出主程序*default:break;}}}voidInitStack(SeqStackCar*s)*初始化棧*{inti;s->top=0;for(i=0;i<=MAX;i++)s->stack[s->top]=NULL;}intInitQueue(LinkQueueCar*Q)*初始化便道*{Q->(1);}elsereturn(-1);}voidPRINT(CarNode*p,introom)*打印出站車的信息*{intA1,A2,B1,B2;printf("\n請(qǐng)輸入離開的時(shí)間:**:**");scanf("%d:%d",&(p->leave.));棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第21頁(yè)。printf("\n離開車輛的車牌號(hào)為:");棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第21頁(yè)。puts(p->num);printf("\n其到達(dá)時(shí)間為:%d:%d",p->reach.);printf("離開時(shí)間為:%d:%d",p->leave.);A1=p->reach.;B1=p->leave.;printf("\n應(yīng)交費(fèi)用為:%2.1f元",((B1-A1)*60+(B2-A2))*price);free(p);}intArrival(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->top<MAX)*車場(chǎng)未滿，車進(jìn)車場(chǎng)*{Enter->top++;printf("\n車輛在車場(chǎng)第%d位置.",Enter->top);printf("\n請(qǐng)輸入到達(dá)時(shí)間:**:**");scanf("%d:%d",&(p->reach.));Enter->stack[Enter->top]=p;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;棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第22頁(yè)。return(1);}}棧的操作(實(shí)驗(yàn)報(bào)告)全文共25頁(yè)，當(dāng)前為第22頁(yè)。voidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W){*車輛離開*inti,room;CarNode*p,*t;QueueNode*q;*判斷車場(chǎng)內(nèi)是否有車*if(Enter->top>0)*有車*{while(1)*輸入離開車輛的信息*{printf("\n請(qǐng)輸入車在車場(chǎng)的位置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;En