數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告項(xiàng)目:專業(yè):班級:學(xué)號:姓名:指導(dǎo)老師：20062007學(xué)年第二學(xué)期一、問題描述：有一個(gè)渡口，每條渡輪一次能裝載10輛汽車過江，過江車輛分為客車和貨車兩類，上渡輪有如下規(guī)定：(1) 同類汽車先到先上船。(2) 客車先與貨車上船。(3) 每上4輛客車才允許上一輛貨車，但若等待的客車不足4輛則用貨車填補(bǔ)，反過來，若沒有貨車等待則用客車填補(bǔ)。(4) 裝滿10輛后則自動(dòng)開船，當(dāng)?shù)却龝r(shí)間較長時(shí)車輛不足10輛也應(yīng)人為控制發(fā)船。二、算法思想：此問題應(yīng)建立和使用兩個(gè)隊(duì)列，一個(gè)為客車隊(duì)列，另一個(gè)為貨車隊(duì)列，到渡口需過江的汽車分別進(jìn)入到相應(yīng)隊(duì)列中。當(dāng)渡口有渡輪時(shí)先讓客車隊(duì)列中的4個(gè)車輛出隊(duì)并開

2、進(jìn)渡輪，再讓貨車隊(duì)列中的一個(gè)車輛出隊(duì)并開進(jìn)渡輪，若某一類車輛隊(duì)列為空則從另一個(gè)隊(duì)列中補(bǔ)充。當(dāng)渡輪上的車輛已滿則自動(dòng)開船，此時(shí)應(yīng)打印出已裝車輛的每個(gè)車號。若裝載不足10輛，但兩個(gè)車輛隊(duì)列全為空，應(yīng)繼續(xù)等待一段時(shí)間，若等待時(shí)間較長，仍不滿載則應(yīng)人為控制開船。三、基本要求：總體原則是客車優(yōu)先于貨車，比例為4:1,但能根據(jù)實(shí)際情況，靈活調(diào)整裝載的汽車以及發(fā)船的控制。四、模塊劃分：(2)具體應(yīng)用模塊：1 .隊(duì)列的相關(guān)運(yùn)算：(存于單獨(dú)源文件“鏈?zhǔn)疥?duì)列.cpp”中)voidInitQueue(LinkQueue&Q)初始化隊(duì)列voidEnQueue(LinkQueue&Q,ElemTypei

3、tem)/向隊(duì)列中插入一個(gè)元素ElemTypeOutQueue(LinkQueue&Q)從隊(duì)列中刪除一個(gè)元素voidClearQueue(LinkQueue&Q)/清除隊(duì)列中的所有元素，使之變成空隊(duì)boolEmptyQueue(LinkQueue&HQ)/檢查隊(duì)列是否為空2 .渡輪輸出相關(guān)模塊：voidPrint(inta,intn)/輸出本次輪渡所載汽車編號voidOutputQueue(constLinkQueue&q1,constLinkQueue&q2)/輸出汽車排隊(duì)等待的情況五、數(shù)據(jù)結(jié)構(gòu)：建立兩個(gè)鏈接隊(duì)列，一個(gè)為客車隊(duì)列，另一個(gè)為貨車隊(duì)列，到渡

4、口需過江的汽車分別進(jìn)入到相應(yīng)隊(duì)列中。鏈接隊(duì)列的定義為：structLinkQueueLNode*front;/隊(duì)首指針LNode*rear;/隊(duì)尾指針;主函數(shù)中使用switch()函數(shù)，將功能表中的六種選擇分別表示為case1case6。具體表示：swtch(flag)/falg為輸入的功能序號case1: /車到渡口進(jìn)行登記case2: /輪渡到渡口進(jìn)行登記case3: /汽車上輪渡case4: /命令輪渡起航case5: /輸出當(dāng)前汽車排隊(duì)情況case6: /結(jié)束程序運(yùn)行六、源程序：鏈?zhǔn)疥?duì)列.cppvoidInitQueue(LinkQueue&Q)/初始化隊(duì)列Q.front=Q.

5、rear=NULL;voidEnQueue(LinkQueue&Q,ElemTypeitem)/向隊(duì)列中插入一個(gè)元素LNode*newptr=newLNode();newptr->data=item;newptr->next=NULL;if(Q.rear=NULL)/若隊(duì)列為空，則新結(jié)點(diǎn)既是隊(duì)首又是隊(duì)尾Q.front=Q.rear=newptr;Q.rear->next=newptr;/若隊(duì)列非空，則新結(jié)點(diǎn)被鏈接到隊(duì)尾Q.rear=newptr;ElemTypeOutQueue(LinkQueue&Q)/從隊(duì)列中刪除一個(gè)元素if(Q.front=NULL) /

6、若隊(duì)列為空則終止運(yùn)行cout<<"Empty!"<<endl;exit(1);LNode *p;p=Q.front;ElemType a=p->data;Q.front=p->next;if(Q.front=NULL)Q.rear=NULL;delete p;return a;/暫存隊(duì)首元素以便返回/暫存隊(duì)首指針以便回收隊(duì)首結(jié)點(diǎn)/使隊(duì)首指針指向下一個(gè)結(jié)點(diǎn)/若刪除后隊(duì)列為空，則使隊(duì)尾指針為空/返回刪除的隊(duì)首元素void ClearQueue(LinkQueue& Q) / 清除隊(duì)列中的所有元素，使之變成空隊(duì) LNode *b;b=Q

7、.front;while(Q.front!=NULL) /依次刪除隊(duì)列中的每個(gè)元素/對首時(shí)針賦給pQ.front=b->next;delete b;b=Q.front;Q.rear=NULL;/置隊(duì)尾指針為空bool EmptyQueue(LinkQueue& HQ)return HQ.front=NULL;/檢查隊(duì)列是否為空輪渡 .cpp#include<iostream.h>#include<stdlib.h>#include<time.h>/此頭文件包含有上time 函數(shù)和 ctime 函數(shù)的typedef int ElemType; s

8、truct LNodeElemType data;LNode* next;/值域/鏈接指針域;structLinkQueueLNode*front;/隊(duì)首指針LNode*rear;/隊(duì)尾指針;#include"鏈接隊(duì)列.cpp"/輸出本次輪渡所載汽車編號voidPrint(inta,intn)longt;t=time(0);/當(dāng)前機(jī)器系統(tǒng)時(shí)間被保存到t中，單位為秒cout<<endl;cout<<"輪渡開始起航->"<<endl;cout<<"本次過江的時(shí)間:"<<ct

9、ime(&t)<<endl;/ctime(&t)函數(shù)的值為根據(jù)參數(shù)t轉(zhuǎn)換得到的日期和時(shí)間的字符串cout<<"本次輪渡所載汽車：”；for(inti=0;i<n;i+)cout<<ai<<''cout<<endl;/輸出汽車排隊(duì)等待的情況voidOutputQueue(constLinkQueue&q1,constLinkQueue&q2)cout<"客車等候的情況："；LNode*p=q1.front;if(p=NULL)cout<<

10、;"暫時(shí)無客車等候."<<endl;while(p!=NULL)cout<<p->data<<''p=p->next;cout<<endl;cout<<"貨車排隊(duì)的情況："；p=q2.front;if(p=NULL)cout<<"暫時(shí)無貨車等候."<<endl;while(p!=NULL)cout<<p->data<<''p=p->next;cout<<endl

11、;voidmain()/q1和q2隊(duì)列用來分別存儲待渡江的客車和貨車LinkQueueq1,q2;/對q1和q2進(jìn)行初始化InitQueue(q1);InitQueue(q2);/用flag保存用戶選擇，用mark登記輪渡到渡口intflag,mark=0;/用數(shù)組a記錄輪渡上的每個(gè)汽車號，用n記錄汽車的個(gè)數(shù)inta10,n=0;/用t1和t2登記時(shí)間longt1,t2;/程序處理結(jié)果do/顯示功能表并接受用戶選擇L1:cout<<"功能表:"<<endl;cout<<"1-車到渡口進(jìn)行登記"<<endl;

12、cout<<"2-輪渡到渡口進(jìn)行登記"<<endl;cout<<"3-汽車上輪渡"<<endl;cout<<"4-命令輪渡起航"<<endl;cout<<"5-輸出當(dāng)前汽車排隊(duì)情況"<<endl;cout<<"6-結(jié)束程序運(yùn)行"<<endl<<endl;cout<<"請輸入你的選擇(1-6)："docin>>flag;if

13、(flag<1|flag>6)cout<<"輸入功能號錯(cuò)，重輸:"while(flag<1|flag>6);intx,i;/根據(jù)不同選擇進(jìn)行相應(yīng)處理switch(flag)case 1:cout<<"輸入車輛號，假定小于100為客車，否則為貨車，"<<endl;cout<<"可以輸入多輛車，用空格分開，直到輸入-1為止。"<<endl;while(1)cin>>x;if(x=-1)break;if(x<100)EnQueue(q1,x

14、);/客車進(jìn)q1隊(duì)elseEnQueue(q2,x);/貨車進(jìn)q2隊(duì)break;/結(jié)束switch語句case 2:if(mark=1)cout<<"渡輪已在渡口等待，不要重復(fù)登記！"<<endl;break;/結(jié)束switch語句mark=1;/渡輪到口岸登記cout<<"渡輪已到渡口，可以上船！"<<endl;n=0;/裝載車輛數(shù)初始為0；t1=time(0);/登記渡輪到渡口時(shí)間，單位為秒break;/結(jié)束switch語句case 3:if(EmptyQueue(q1)&&EmptyQ

15、ueue(q2)cout<<"暫無汽車過江！"<<endl;if(mark=1&&n!=0)t2=time(0)-t1;/計(jì)算到目前為止渡輪等待時(shí)間的秒數(shù)cout<<"輪渡未滿，有車"<<n<<"輛，已等待"<<t2/60<<"分"cout<<t2%60<<"秒，等候其他汽車上渡輪！"<<endl;break;/結(jié)束switch語句if(mark!=1)cout

16、<<"渡輪未到，請汽車稍后上渡輪！"<<endl;break;/結(jié)束switch語句doi=0;/首先上4輛客車while(!EmptyQueue(q1)&&n<10&&i<4)an+=OutQueue(q1);i+;/滿10輛開船，打印車輛號，重新對mark和n清0，轉(zhuǎn)功能號表if(n=10)Print(a,n);mark=0;n=0;gotoL1;/進(jìn)4輛客車則接著進(jìn)一輛貨車，不滿4輛則由貨車補(bǔ)if(i=4)if(!EmptyQueue(q2)an+=OutQueue(q2);elsewhile(!Em

17、ptyQueue(q2)&&n<10&&i<5)an+=OutQueue(q2);i+;滿10輛則開船if(n=10)Print(a,n);mark=0;n=0;gotoL1;while(!EmptyQueue(q1)|!EmptyQueue(q2);只要客車或貨車隊(duì)列不全為空，則繼續(xù)執(zhí)行do循環(huán)t2=time(0)-t1;登記渡輪已經(jīng)等待時(shí)間的秒數(shù)cout<<"渡輪上有車"<<n<<"輛,已等待”<<t2/60<<"分"<<t2

18、%60;cout<<"秒，等候其他汽車上渡輪！"<<endl;break;結(jié)束switch語句case 4:if(n=0|mark=0)cout<<"輪渡上無車過江或根本無渡輪！不需要起航！"<<endl;elsePrint(a,n);mark=0;n=0;break;case 5:OutputQueue(q1,q2);break;結(jié)束switch語句case 6:if(!EmptyQueue(q1)|!EmptyQueue(q2)cout<<"還有汽車未渡江，暫不能結(jié)束！"

19、<<endl;break;結(jié)束switch語句if(n!=0)cout<<"渡輪上有車，不能結(jié)束，需命令開渡輪！"<<endl;break;結(jié)束switch語句cout<<"程序運(yùn)行結(jié)束！"<<endl;return;執(zhí)行結(jié)束返回/switch語句終端位置while(1);外層do循環(huán)終端位置ClearQueue(q1);ClearQueue(q2);主函數(shù)結(jié)束位置七、測試數(shù)據(jù)：C："輪渡.exe”功能表：1-車到渡口進(jìn)行登記2-輪渡到渡口進(jìn)行登記3-汽車上輪渡4-命令輪渡起航5-輸出

20、當(dāng)前汽車排隊(duì)情況6-結(jié)束程序運(yùn)行請輸入你的選擇（1-6）:1輸入車輛號，假定小于100為客車，否則為貨車，可以輸入多輛車，用空格分開，直到輸入-1為止。45786723832109321235874919391894562031425388-1功能表：1-車到渡口進(jìn)行登記2-輪渡到渡口進(jìn)行登記3-汽車上輪渡4-命令輪渡起航5-輸出當(dāng)前汽車排隊(duì)情況6-結(jié)束程序運(yùn)行請輸入你的選擇（1-6）:2渡輪已到渡口，可以上船！功能表：1-車到渡口進(jìn)行登記2-輪渡到渡口進(jìn)行登記3-汽車上輪渡4-命令輪渡起航5-輸出當(dāng)前汽車排隊(duì)情況6-結(jié)束程序運(yùn)行請輸入你的選擇（1-6）:3輪渡開始起航->本次過江的時(shí)間

21、：WedJul0418:23:372007本次輪渡所載汽車：4578673223832123587109功能表：1-車到渡口進(jìn)行登記2-輪渡到渡口進(jìn)行登記3-汽車上輪渡4-命令輪渡起航5-輸出當(dāng)前汽車排隊(duì)情況6-結(jié)束程序運(yùn)行請輸入你的選擇（1-6）:2渡輪已到渡口，可以上船！功能表：1-車到渡口進(jìn)行登記2-輪渡到渡口進(jìn)行登記3-汽車上輪渡4-命令輪渡起航5-輸出當(dāng)前汽車排隊(duì)情況6-結(jié)束程序運(yùn)行請輸入你的選擇（1-6）:3渡輪上有車9輛，已等待0分10秒，等候其他汽車上渡輪!功能表：1-車到渡口進(jìn)行登記2-輪渡到渡口進(jìn)行登記3-汽車上輪渡4-命令輪渡起航5-輸出當(dāng)前汽車排隊(duì)情況6-結(jié)束程序運(yùn)行請輸入你的選擇（1-6）:4輪渡開始起航->本次過江的時(shí)間：WedJul0418:27:352007本次輪渡所載汽車：4919395318988456203142功能表：1-車到渡口進(jìn)行登記2-輪渡到渡口進(jìn)行登記3-汽車上輪渡4-命令輪渡起航5-輸出當(dāng)前汽車排隊(duì)情況6-結(jié)束程序運(yùn)行請輸入你的選擇（1-6）:5客車等候的情況：暫時(shí)無客車等候.貨車排隊(duì)的情況：暫時(shí)無貨車等候.功能表：1-車到渡口進(jìn)行登記2-輪渡到渡口進(jìn)行登記3-汽車上輪渡4-命令輪渡起航5-輸出當(dāng)前汽車排隊(duì)情況6-結(jié)束程序運(yùn)行請輸入你的選擇（1-6）: