數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告—停車場問題.doc

計算機(jī)軟件技術(shù)基礎(chǔ) 實(shí)驗(yàn)報告I數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二：停車場管理問題一、問題描述1.實(shí)驗(yàn)題目： 設(shè)停車場是一個可停放 n 輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端）。若停車場內(nèi)已經(jīng)停滿 n輛車，那么后來的車只能在門外的便道上等候。一旦有車開走，則排在便道上的第一輛車即可開入。當(dāng)停車場內(nèi)某輛車要離開時，在它之后進(jìn)入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場。每輛停放在車場的車在它離開停車場時必須按它停留的時間長短繳納費(fèi)用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。2基本要求：以棧模擬停車場，以隊(duì)列模擬車場外的便道，按照從終端讀入數(shù)據(jù)的序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)：汽車的“到達(dá)”（A表示）或“離去”（D表示）信息、汽車標(biāo)識（牌照號）以及到達(dá)或離去的時刻。對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或者便道上的停車位置；若是車輛離去，則輸出汽車在停車場停留的時間和應(yīng)繳納的費(fèi)用（便道上停留的時間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。3測試數(shù)據(jù)： 設(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ù)包括三個數(shù)據(jù)項(xiàng)：汽車 “到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，其中，A表示到達(dá)；D表示離去，E表示輸入結(jié)束。其中：（A，1，5）表示1號牌照車在5這個時刻到達(dá)，而（D，1，15）表示1號牌照車在15這個時刻離去。二、需求分析 1.程序所能達(dá)到的基本可能： 本程序用來模擬一個可停放n輛車的停車場的停車管理問題。用棧和隊(duì)列模擬停車場及場外通道，輸入車輛狀態(tài)（到達(dá)或者離開），車牌號和時間，就可顯示停車位置或者該車在停車場停留時間及應(yīng)繳費(fèi)用。2.輸入的形式及輸入值范圍： 程序接受5個命令，分別是：到達(dá)（A,車牌號,時間)；離去(D,車牌號,時間)；停車場（P, 0, 0）顯示停車場的車數(shù)；候車場（W, 0, 0）顯示候車場的車數(shù)；退出（E, 0, 0）退出程序。3.輸出的形式： 對于車輛到達(dá)，要輸出汽車在停車場內(nèi)或者便道上的停車位置；對于車輛離去，則輸出汽車在停車場停留的時間和應(yīng)繳納的費(fèi)用（便道上不收費(fèi)）。用戶輸入完畢后，程序自動運(yùn)行輸出運(yùn)行結(jié)果。4.測試數(shù)據(jù)要求： 設(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ù)包括三個數(shù)據(jù)項(xiàng)：汽車 “到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，其中，A表示到達(dá)；D表示離去，E表示輸入結(jié)束。其中：（A，1，5）表示1號牌照車在5這個時刻到達(dá)，而（D，1，15）表示1號牌照車在15這個時刻離去。三、概要設(shè)計 為了實(shí)現(xiàn)上述功能，該程序以棧模擬停車場以及臨時停放為給要離去的汽車讓路而從停車場退出來的汽車的場地，以隊(duì)列模擬車場外的便道，因此需要棧和隊(duì)列這兩個抽象數(shù)據(jù)類型。 1. 棧抽象數(shù)據(jù)類型定義 ： ADT SqStack 數(shù)據(jù)對象：D=ai,bi,ci,di|aiint, biint,ciint,dichar),i =1,2.,n,n0: 數(shù)據(jù)關(guān)系：R=(ai,bi,di,)|ai,bi,diD,ai,bi,distruct car; 基本操作： Car_enter(carnum,cartime)/將到達(dá)車輛a的信息入棧s或者入隊(duì)q Car_Leave(carnum,cartime)；/將待離開車輛d出棧s，并將q中相應(yīng)車輛入棧并進(jìn)行相關(guān)的操作 Result(char carmove,int carnum,int cartime)/根據(jù)輸入信息完成車輛的離開或者到達(dá) ADT SqStack ADT的C語言形式說明： typedef struct /構(gòu)造一個順序棧struct Node1 homeMaxSize; int stacktop; /棧頂?shù)闹羔楽tack;2. 隊(duì)列抽象數(shù)據(jù)類型定義 ADT LinkQueue 數(shù)據(jù)對象：D=ai,bi,ci|aiQnode*, biQnode*,ciint), i =1,2.,n,n0; 數(shù)據(jù)關(guān)系：R= 基本操作：Car_enter(carnum,cartime)/將到達(dá)車輛a的信息入棧s或者入隊(duì)q Car_Leave(carnum,cartime)；/將待離開車輛d出棧s，并將q中相應(yīng)車輛入棧并進(jìn)行相關(guān)的操作 Result(char carmove,int carnum,int cartime)/根據(jù)輸入信息完成車輛的離開或者到達(dá) ADT LinkQueueADT的C語言形式說明：typedef struct /構(gòu)建一個鏈?zhǔn)疥?duì)列QNode *front,*rear;Queue; void Car_enter(int carnum,int cartime) /到達(dá)車輛的信息入?；蛘呷腙?duì)void Car_Leave(int carnum,int cartime)/車離開int Result(char carmove,int carnum,int cartime)/根據(jù)輸入信息完成車輛的離開或者達(dá)到 3. 主程序流程及其模塊調(diào)用關(guān)系:1） 主程序流程： 主函數(shù)提示用戶輸入指令：到達(dá)（A,車牌號,時間)；離去(D,車牌號,時間)；停車場P 顯示停車場的車數(shù)；候車場W顯示候車場的車數(shù)；退出E退出程序。 調(diào)用int Result(char carmove,int carnum,int cartime)根據(jù)輸入信息完成車輛的離開或者達(dá)到。 若輸入A則調(diào)用Car_enter(int carnum,int cartime) ，創(chuàng)建順序棧CarS和鏈?zhǔn)疥?duì)列CarQ，根據(jù)棧是否滿決定輸入的信息入棧還是入隊(duì)列。若棧未滿，輸入的車輛信息入棧，若已滿，入隊(duì)列。 若輸入D則調(diào)用Car_Leave(int carnum,int cartime)：創(chuàng)建一個臨時棧存放退出讓路的車，若在車庫中找到對應(yīng)的車，車庫中該車后面的車輛信息進(jìn)入臨時棧CarS2，該車出棧，顯示車牌號，此時時間，停留時間，應(yīng)繳費(fèi)用。臨時棧中的車的信息再回到CarS中。此時若隊(duì)列CarQ不為空則將隊(duì)列中車輛信息放入棧CarS中。若在車庫中找不到對應(yīng)的車的車牌號信息，則在表示候車場的隊(duì)列中找該車信息，如果它在隊(duì)列的最后，直接出列并輸出車牌號，此時時間，停留時間，應(yīng)繳費(fèi)用。如果它不在隊(duì)尾，先把對應(yīng)信息保存在一個指向隊(duì)列的指針中，輸出車牌號，此時時間，停留時間，應(yīng)繳費(fèi)用。刪除隊(duì)列中此結(jié)點(diǎn)表示此車離開候車場。 若輸入P，則輸出車庫車輛數(shù)PCar； 若輸入W，則輸出候車場車輛數(shù)WCar； 若輸入E，則退出程序。2） 調(diào)用關(guān)系 四、詳細(xì)設(shè)計 1. 元素類型、結(jié)點(diǎn)類型和結(jié)點(diǎn)指針類型：typedef struct Node1 /構(gòu)建一個結(jié)構(gòu)體 int carnum; int time;Node1;typedef struct Node2 int carnum; int time; struct Node2 *next;Node2; 2、 創(chuàng)建順序棧 typedef struct /構(gòu)造一個順序棧struct Node1 homeMaxSize; int stacktop; /棧頂?shù)闹羔楽tack;3、 創(chuàng)建鏈?zhǔn)疥?duì)列 typedef struct /構(gòu)建一個鏈?zhǔn)疥?duì)列Node2 *front,*rear;Queue; 4. 車輛到達(dá)：void Car_enter(int carnum,int cartime) /到達(dá)車輛的信息入?；蛘呷腙?duì) if(CarS.stacktopcarnum=carnum; CarQ.front-time=cartime;/到達(dá)車輛信息加入到隊(duì)列中 WCar+; /候車場車輛數(shù)+1 printf(%d號車進(jìn)入候車場! 到達(dá)時刻:%d 位置:%dn,CarQ.front-carnum=carnum,CarQ.front-time=cartime,WCar); CarQ.front-next=(Node2 *)malloc(sizeof(Node2);/分配空間 CarQ.front=CarQ.front-next;/更改隊(duì)列指針5. 車輛離開void Car_Leave(int carnum,int cartime)/車離開Stack CarS2;/構(gòu)造一個棧臨時存放為了讓位退出來的車 int i;int findcar=-1; Node2 *p,*f; CarS2.stacktop=0;/設(shè)臨時棧CarS2為空 for(i=0;ifindcar;CarS2.stacktop+)/將車庫里面在i車外面的車移動到臨時棧CarS2中 CarS2.homeCarS2.stacktop.carnum=CarS.homeCarS.stacktop.carnum; CarS2.homeCarS2.stacktop.time=CarS.homeCarS.stacktop.time; printf(%d號車離開停車場! 離開時刻: %d,停留時長(%d)n,CarS.homeCarS.stacktop.carnum,cartime,cartime-CarS.homeCarS.stacktop.time); PCar-;/車庫內(nèi)車輛-1 printf(應(yīng)付停車費(fèi) %dn,(cartime-CarS.homeCarS.stacktop.time)*5); for(i=CarS2.stacktop-1;i=0;i-)/把臨時棧里面的車移回去 CarS.homeCarS.stacktop.carnum=CarS2.homei.carnum; CarS.homeCarS.stacktop.time=CarS2.homei.time; CarS.stacktop+; CarS2.stacktop-; if(CarQ.front!=CarQ.rear)/如果候車場有車，將它移進(jìn)車庫 CarS.homeCarS.stacktop.carnum=CarQ.rear-carnum;/將隊(duì)列中的車牌號信息放入棧 CarS.homeCarS.stacktop.time=cartime;/將此時的時刻記錄入棧CarS，確保計算費(fèi)用是從車輛從候車場進(jìn)入車庫后才開始算 CarS.stacktop+; PCar+;/車庫車輛數(shù)+1 WCar-;/候車場車輛數(shù)-1 p=CarQ.rear; CarQ.rear=CarQ.rear-next; free(p); else/如果車庫中找不到此車，再在候車場找 p=CarQ.rear; if(p!=CarQ.front&p-carnum!=carnum) /候車場隊(duì)列不為空 f=p-next; while(f!=CarQ.front&f-carnum!=carnum) p=f; f=f-next; if(f-carnum=carnum)/如果尋找的車在便道上，出隊(duì)列 findcar=1; p-next=f-next; printf(%d號車離開候車場! 離開時間: %d,停留時長(%d)n,f-carnum,cartime,cartime-f-time); WCar-; printf(應(yīng)付停車費(fèi): %dn,(cartime-f-time)*0); free(f); if(p-carnum=carnum)/要離開的車在隊(duì)尾，直接出隊(duì) findcar=1; CarQ.rear=CarQ.rear-next; printf(%d號車離開候車場!離開時間: %d,停留時長(%d)!n,p-carnum,cartime,cartime-p-time); WCar-; printf(應(yīng)付停車費(fèi): %dn,(cartime-p-time)*0); free(p); if(findcar=-1) printf(%d號車不在停車場中!n,carnum);6. 主函數(shù) main()printf(試驗(yàn)名稱：停車場管理問題n); printf(學(xué)號：n); printf(姓名：xxn); printf(=n); time_t rawtime1; struct tm * timeinfo1; time (&rawtime1); timeinfo1 = localtime (&rawtime1); /時間函數(shù)；printf (程序運(yùn)行開始,當(dāng)前日期和時間: %s, asctime(timeinfo1);int go=1,carnum,cartime,MM; char carmove; CarS.stacktop=0; CarQ.rear=CarQ.front=(Node2 *)malloc(sizeof(Node2); while(go) printf(n車輛到達(dá)請輸入A;n車輛離開請輸入D;n顯示停車場內(nèi)車數(shù)請輸入P;n顯示候車場車數(shù)請輸入W;n退出程序請輸入E:n); printf(n請輸入信息:);carmove=getchar(); printf(n); switch(carmove) case A: printf(%cn車牌號:t,carmove); scanf(%d,&carnum); printf(時間:t); scanf(%d,&cartime); MM=Result(carmove,carnum,cartime); if(!MM)go=0; break; case D: printf(%cn車牌號:t,carmove); scanf(%d,&carnum); printf(現(xiàn)在時刻:t); scanf(%d,&cartime); MM=Result(carmove,carnum,cartime); if(!MM)go=0; break; case W: printf(正在外通道等待的車數(shù)量是: %dn,WCar); break; case P: printf(車庫內(nèi)車的數(shù)量是: %dn,PCar); break; case E:printf(退出!n); time_t rawtime2; struct tm * timeinfo2; time (&rawtime2); timeinfo2 = localtime (&rawtime2); printf (程序運(yùn)行結(jié)束,當(dāng)前日期和時間: %s, asctime(timeinfo2); return 0; getchar();五、調(diào)試分析 此程序是分模塊設(shè)計，根據(jù)輸入的指令調(diào)用“到達(dá)”和“離開”模塊，使車的信息入棧入隊(duì)，或出棧出隊(duì)。每次運(yùn)行后又返回主菜單。程序整體結(jié)構(gòu)清晰，操作方便。六、使用說明用戶根據(jù)提示輸入指令：到達(dá)輸入A,離開輸入D，顯示車庫車輛數(shù)輸入P，顯示候車場車輛數(shù)輸入W，退出程序輸入E。輸入A后，根據(jù)提示輸入車牌號i和此時時間，將顯示“第i號車進(jìn)入車庫！時間： 位置：”或“第i號車進(jìn)入候車場！時間： 位置：”；輸入D后，根據(jù)提示輸入車牌號i和此時時間，將顯示“第i號車離開車庫！時間： 停留時間： 應(yīng)繳費(fèi)用：”?；颉暗趇號車離開候車場！時間： 停留時間： 應(yīng)繳費(fèi)用：”；輸入W后顯示“正在外通道等待的車數(shù)量是：”；輸入P后顯示“車庫內(nèi)車的數(shù)量是”；輸入E后退出程序。七、調(diào)試結(jié)果 設(shè)車庫最大容量為2.輸入一組數(shù)據(jù)進(jìn)行測試：（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）。初始界面為：輸入到達(dá)車輛：到達(dá)車輛超過車庫容量時：輸入車輛離開信息：輸入P輸入W：輸入E：八 、遇到的問題和解決方法1. 開始，程序編寫完成后雖然沒有報錯，卻不能運(yùn)行，如圖經(jīng)檢查程序，將Stack *CarS; Queue *CarQ; 這兩個指針型變量改成Stack CarS; /用來表示車庫的棧Queue CarQ; /用來表示候車場的隊(duì)列，再次運(yùn)行發(fā)現(xiàn)可以成功運(yùn)行。2. 當(dāng)輸入上述數(shù)據(jù)后輸入P和W后顯示的車輛數(shù)不對，當(dāng)車庫內(nèi)車輛離開時，外通道的車進(jìn)入車庫，但PCar和WCar沒有正確跟隨變化，如圖經(jīng)檢查程序，在if(CarQ.front!=CarQ.rear)/如果候車場有車，將它移進(jìn)車庫 CarS.homeCarS.stacktop.carnum=CarQ.rear-carnum;/將隊(duì)列中的車牌號信息放入棧 CarS.homeCarS.stacktop.time=cartime;/將此時的時刻記錄入棧CarS，確保計算費(fèi)用是從車輛從候車場進(jìn)入車庫后才開始算 CarS.stacktop+; p=CarQ.rear; CarQ.rear=CarQ.rear-next; free(p);這段程序中少了 PCar+; WCar-;，加上后再次運(yùn)行，程序正確。3.計算費(fèi)用時發(fā)現(xiàn)錯誤，在候車廳時間也被計入停車費(fèi)。經(jīng)檢查程序，將CarS.homeCarS.stacktop.time=CarQ.rear-time;改成CarS.homeCarS.stacktop.time=cartime;使其計費(fèi)時間從進(jìn)入車庫開始而不是從達(dá)到候車場開始。再次運(yùn)行發(fā)現(xiàn)結(jié)果正確。九、實(shí)驗(yàn)收貨和感想 這是第一次運(yùn)用棧和隊(duì)列的相關(guān)知識編寫程序，開始看到這個題目感覺挑戰(zhàn)很大，從未嘗試過這么復(fù)雜的一個系統(tǒng)。停車場問題相較與約瑟夫斯問題要復(fù)雜得多，分了多個模塊。起初編寫時漏洞很多，好在當(dāng)框架出來后各個漏洞都可以被彌補(bǔ)。比如程序剛運(yùn)行成功時，發(fā)現(xiàn)不能顯示位置，車庫車輛數(shù)和候車場車輛數(shù)不正確，計費(fèi)不正確等很多漏洞，但這些細(xì)節(jié)的小問題都比較容易排查修改，最終終于做出了符合要求的停車場管理系統(tǒng)。當(dāng)完成后，我對棧和隊(duì)列的相關(guān)算法的理解也更加清晰深刻了。這個程序中還有一些靈活可變的地方，用宏定義定義了車庫容量和費(fèi)用單價，使具體數(shù)字可以較為靈活的改變，增加了這個程序的使用價值。計算機(jī)實(shí)踐課程給了我動手操作的機(jī)會，使我將理論和實(shí)際操作結(jié)合起來，更好地理解算法，更快地學(xué)會編程。每次編程都感覺收獲非常多。練習(xí)的越多，對算法語句越是熟練，越能有深刻的理解，不僅幫助我更好的學(xué)習(xí)軟件技術(shù)基礎(chǔ)也為以后我們專業(yè)課的道路打好基石，對我們的邏輯能力也是很大的提升。十、源程序#include#include#include #define MaxSize 2/車庫最大容量#define fee 10/在車庫中停車的單價typedef struct Node1 /構(gòu)建一個結(jié)構(gòu)體 int carnum; int time;Node1;typedef struct /構(gòu)造一個順序棧struct Node1 homeMaxSize; int stacktop; /棧頂?shù)闹羔楽tack;typedef struct Node2 int carnum; int time; struct Node2 *next;Node2; typedef struct /構(gòu)建一個鏈?zhǔn)疥?duì)列Node2 *front,*rear;Queue; Stack CarS; /用來表示車庫的棧Queue CarQ; /用來表示候車場的隊(duì)列int PCar=0;/車庫里車的數(shù)量int WCar=0;/候車場的車的數(shù)量void Car_enter(int carnum,int cartime) /到達(dá)車輛的信息入?；蛘呷腙?duì) if(CarS.stacktopcarnum=carnum; CarQ.front-time=cartime;/到達(dá)車輛信息加入到隊(duì)列中 WCar+; /候車場車輛數(shù)+1 printf(%d號車進(jìn)入候車場! 到達(dá)時刻:%d 位置:%dn,CarQ.front-carnum=carnum,CarQ.front-time=cartime,WCar); CarQ.front-next=(Node2 *)malloc(sizeof(Node2);/分配空間 CarQ.front=CarQ.front-next;/更改隊(duì)列指針void Car_Leave(int carnum,int cartime)/車離開Stack CarS2;/構(gòu)造一個棧臨時存放為了讓位退出來的車 int i;int findcar=-1; Node2 *p,*f; CarS2.stacktop=0;/設(shè)臨時棧CarS2為空 for(i=0;ifindcar;CarS2.stacktop+)/將車庫里面在i車外面的車移動到臨時棧CarS2中 CarS2.homeCarS2.stacktop.carnum=CarS.homeCarS.stacktop.carnum; CarS2.homeCarS2.stacktop.time=CarS.homeCarS.stacktop.time; printf(%d號車離開停車場! 離開時刻: %d,停留時長(%d)n,CarS.homeCarS.stacktop.carnum,cartime,cartime-CarS.homeCarS.stacktop.time); PCar-;/車庫內(nèi)車輛-1 printf(應(yīng)付停車費(fèi) %dn,(cartime-CarS.homeCarS.stacktop.time)*5); for(i=CarS2.stacktop-1;i=0;i-)/把臨時棧里面的車移回去 CarS.homeCarS.stacktop.carnum=CarS2.homei.carnum; CarS.homeCarS.stacktop.time=CarS2.homei.time; CarS.stacktop+; CarS2.stacktop-; if(CarQ.front!=CarQ.rear)/如果候車場有車，將它移進(jìn)車庫 CarS.homeCarS.stacktop.carnum=CarQ.rear-carnum;/將隊(duì)列中的車牌號信息放入棧 CarS.homeCarS.stacktop.time=cartime;/將此時的時刻記錄入棧CarS，確保計算費(fèi)用是從車輛從候車場進(jìn)入車庫后才開始算 CarS.stacktop+; PCar+;/車庫車輛數(shù)+1 WCar-;/候車場車輛數(shù)-1 p=CarQ.rear; CarQ.rear=CarQ.rear-next; free(p); else/如果車庫中找不到此車，再在候車場找 p=CarQ.rear; if(p!=CarQ.front&p-carnum!=carnum) /候車場隊(duì)列不為空 f=p-next; while(f!=CarQ.front&f-carnum!=carnum) p=f; f=f-next; if(f-carnum=carnum)/如果尋找的車在便道上，出隊(duì)列 findcar=1; p-next=f-next; printf(%d號車離開候車場! 離開時間: %d,停留時長(%d)n,f-carnum,cartime,cartime-f-time); WCar-; printf(應(yīng)付停車費(fèi): %dn,(cartime-f-time)*0); free(f); if(p-carnum=carnum)/要離開的車在隊(duì)尾，直接出隊(duì) findcar=1; CarQ.rear=CarQ.rear-next; printf(%d號車離開候車場!離開時間: %d,停留時長(%d)!n,p-carnum,cartime,cartime-p-time); WCar-; printf(應(yīng)付停車費(fèi): %dn,(cartime-p-time)*0); free(p); if(findcar=-1) printf(%d號車不在停車場中!n,carnum);int Result(char carmove,int carnum,int cartime)/根據(jù)輸入信息完成車輛的離開或者達(dá)到switch(carmove) case A:Car_enter(carnum,cartime);break; case D:Car_Leave(carnum,cartime);break; defa