數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 停車場管理

1、課程設(shè)計(jì)任務(wù)書及成績評定課題名稱停車場管理、題目的目的和要求： 設(shè)計(jì)中要求綜合運(yùn)用所學(xué)知識，上機(jī)解決一些與實(shí)際應(yīng)用結(jié)合緊密的、規(guī)模較大的問題，通過分析、設(shè)計(jì)、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)技術(shù)，掌握分析、解決實(shí)際問題的能力。通過這次設(shè)計(jì)，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。、設(shè)計(jì)進(jìn)度及完成情況日 期內(nèi) 容12.29-12.30熟悉設(shè)計(jì)任務(wù)，查閱有關(guān)文獻(xiàn)資料，確定所采用的數(shù)據(jù)結(jié)構(gòu)，初步制定解決問題的方法，

2、完成課程設(shè)計(jì)說明書內(nèi)容1-3部分12.311.4選擇合適的存儲結(jié)構(gòu),明確解決問題的算法，上機(jī)編寫并調(diào)試源程序1.41.5整體調(diào)試程序并記錄調(diào)試中的問題，完成課程設(shè)計(jì)說明書第4-6部分。1.81.9演示設(shè)計(jì)成果，考核成績。整理課程設(shè)計(jì)報(bào)告。、主要參考文獻(xiàn)及資料1 嚴(yán)蔚敏，吳偉民主編. 數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社. 2002 2 殷人昆等著. 數(shù)據(jù)結(jié)構(gòu)（C+版）. 清華大學(xué)出版社. 20013 金遠(yuǎn)平著. 數(shù)據(jù)結(jié)構(gòu)（C+描述）. 清華大學(xué)出版社. 2005 4 許卓群等著. 數(shù)據(jù)結(jié)構(gòu)與算法. 高等教育出版社. 20045 Frank M.Carrano 等著. 數(shù)據(jù)結(jié)構(gòu)與+高級教程.清華

3、大學(xué)出版社. 20046 嚴(yán)蔚敏、吳偉民. 數(shù)據(jù)結(jié)構(gòu)習(xí)題集（C語言版）.清華大學(xué)出版社. 2002學(xué)科部主任_（簽字）、成績評定：設(shè)計(jì)成績： （教師填寫）指導(dǎo)老師： （簽字）二九 年 一 月 五 日目 錄第一章 概述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1第二章 系統(tǒng)分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2第三章 概要設(shè)計(jì).

4、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3第四章 詳細(xì)設(shè)計(jì)與源程序. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6第五章 調(diào)試過程中的問題及系統(tǒng)測試情況. . . . . . . . . . . . . . . . . . 11第六章 結(jié)束語. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5、. . . . . .12參考文獻(xiàn). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13第一章 概述一、本課程設(shè)計(jì)意義 課程設(shè)計(jì)是實(shí)踐性教學(xué)中的一個重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相關(guān)的各個方面，是一門獨(dú)立于課程之外的特殊課程。課程設(shè)計(jì)是讓同學(xué)們對所學(xué)的課程更全面的學(xué)習(xí)和應(yīng)用，理解和掌握課程的相關(guān)知識。數(shù)據(jù)結(jié)構(gòu)是一門重要的專業(yè)基礎(chǔ)課，是計(jì)算機(jī)理論和應(yīng)用的核心基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、

6、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。二、本課程設(shè)計(jì)任務(wù)及目的停車場是一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。停車場內(nèi)已停了n輛汽車，后來的汽車只能在門外的便道上等候，一旦有車開走，排在通道上的第一輛車即可開入；當(dāng)停車場內(nèi)每輛車要離開時，在它之后進(jìn)入的車輛必須先退出停車場為其讓路，待該輛車開出大門，其他車輛再按原次序進(jìn)入停車場。為停車場編寫按上述要求進(jìn)行管理的模擬程序。第二章 系統(tǒng)分析一、問題描述設(shè)停車場是一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車

7、輛到達(dá)時間的先后順序，依次由北向南排列（大門在南端，最先到達(dá)的第一輛車停放在停車場的最北端），若停車場內(nèi)已停了n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)每輛車要離開時，在它之后進(jìn)入的車輛必須先退出停車場為其讓路，待該輛車開出大門，其他車輛再按原次序進(jìn)入停車場，每輛停放在停車場的車在它離開停車場時必須按它停留在停車場內(nèi)的時間長短交納停車費(fèi)。試為停車場編寫按上述要求進(jìn)行管理的模擬程序。二、基本要求以棧模擬停車場，以隊(duì)列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)：汽車到達(dá)或離去信息，汽車牌照號碼以

8、及到達(dá)或離去的時刻。對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：在停車場內(nèi)停留的時間和應(yīng)交納的費(fèi)用（在便道上停留的時間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。三、測試數(shù)據(jù) 設(shè)n=2，輸入數(shù)據(jù)（A，1，5），（A，2，15），（D，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到達(dá)（arrival）；D表示離去（departure）；E表示輸出（end）。四、實(shí)現(xiàn)思路需要另設(shè)一個棧，臨時停放為離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實(shí)現(xiàn)。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項(xiàng)：汽車的牌照號碼和

9、進(jìn)入停車場的時刻。第三章 概要設(shè)計(jì)一、棧的抽象數(shù)據(jù)類型 ADT stack數(shù)據(jù)對象：D=aiaicharset,I=1,2,，n,n=0數(shù)據(jù)關(guān)系：R1=ai-1,aiai-1,aiD,I=2,n基本操作：Initstack(&S)操作結(jié)果：構(gòu)造一個空棧S。DestroyStack(&S)初始條件：棧S已經(jīng)存在。操作結(jié)果：操作結(jié)果：銷毀棧S。ClaerStack(&S)初始條件：棧S已經(jīng)存在。操作結(jié)果：將S清空為空棧。StackLength(&S)初始條件：棧S已經(jīng)存在。操作結(jié)果：返回棧S的長度。StackEmpty(&S)初始條件：棧S已經(jīng)存在。操作結(jié)果：若S為空棧，則返回TURE，否則返回F

10、ALSE。GetTop(S,&e)初始條件：棧S已經(jīng)存在。操作結(jié)果：若棧S不空，則以e返回棧頂元素。Push(&S,e)初始條件：棧S已經(jīng)存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。Pop(&S,&e)初始條件：棧S已經(jīng)存在。操作結(jié)果：刪除S的棧頂元素，并以e返回其值。StackTraverse(S,visit()初始條件：棧S已經(jīng)存在。操作結(jié)果：從棧底到棧頂依次對S中的每個元素調(diào)用函數(shù)visit( )。ADT stack二、鏈?zhǔn)疥?duì)列的抽象數(shù)據(jù)類型typedef struct Qnode QelemType data; Struct Qnode next;Qnode,QueuePtr;ty

11、pedef structQueuePtr front; 隊(duì)頭指針QueuePtr rear; 隊(duì)尾指針ADT Queue數(shù)據(jù)對象：D=aiaiElemSet,i=1,2,n,n=0數(shù)據(jù)關(guān)系：R1=ai-1,aiai-1,aiD,i=2,n 約定中端為隊(duì)列頭，后端為隊(duì)列尾。基本操作：InitQueue(&Q)操作結(jié)果：構(gòu)造一個空隊(duì)列Q。DestroyQueue(&Q)初始條件：隊(duì)列Q已經(jīng)存在。操作結(jié)果：隊(duì)列Q被銷毀，不再存在。ClearQueue(&Q)初始條件：隊(duì)列Q已經(jīng)存在。操作結(jié)果：將Q清為空隊(duì)列。QueueEmpty(Q)初始條件：隊(duì)列Q已經(jīng)存在。操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，

12、否則FALSE。QueueLength(Q)初始條件：隊(duì)列Q已經(jīng)存在。操作結(jié)果：返回Q的元素個數(shù)，即隊(duì)列的長度。GetHead(Q,&e)初始條件：Q為非空隊(duì)列。操作結(jié)果：用e返回的e隊(duì)頭元素。EnQueue(&Q,e)初始條件：隊(duì)列Q已經(jīng)存在。操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。DeQueue(&Q,&e)初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。QueueTraverse(Q,visit()初始條件：Q已經(jīng)存在且非空。操作結(jié)果：從隊(duì)頭到隊(duì)尾，依次對Q的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。ADT Queue三、模塊劃分1、主程

13、序模塊main()初始化while(重復(fù)條件) 接受命令； switch(調(diào)用條件)Case調(diào)用條件A 到達(dá)處理；break；Case調(diào)用條件D 離開處理；break；Case調(diào)用條件E 退出處理； 2、2個棧模塊-實(shí)現(xiàn)棧抽象數(shù)據(jù)類型3、隊(duì)列模塊-實(shí)現(xiàn)隊(duì)列抽象數(shù)據(jù)類型 四、模塊調(diào)用關(guān)系主程序模塊棧模塊1隊(duì)列模塊棧模塊2 圖3-1 模塊調(diào)用關(guān)系棧模塊1-模擬停車場棧模塊2-模擬倒車場隊(duì)列模塊-模擬車道第四章 詳細(xì)設(shè)計(jì)與源程序一、詳細(xì)設(shè)計(jì)以棧模擬停車場,以隊(duì)列模擬停車場外的便道,按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。另設(shè)一個棧，臨時停放為離去的汽車讓路而從停車場退出來的汽車。棧以順序存儲結(jié)構(gòu)實(shí)

14、現(xiàn)，隊(duì)列以鏈表存儲結(jié)構(gòu)實(shí)現(xiàn)。停車場棧park模擬停車場。臨時棧Aux-park模擬倒車場。便道隊(duì)列Road模擬停車場外便道。程序運(yùn)行后，先設(shè)定停車時間單位和計(jì)費(fèi)單位，再設(shè)定停車場容量（測試數(shù)據(jù)設(shè)定停車場容量n=2）。繼續(xù)輸入車輛數(shù)據(jù)：車輛屬性（到達(dá)A或離開D）、車牌號、時間（到達(dá)時間或離開時間）。程序根據(jù)輸入數(shù)據(jù)中的“車輛屬性”進(jìn)入該屬性程序模塊。輸出車輛停放位置或離開時的收據(jù)。然后循環(huán)，繼續(xù)輸入車輛數(shù)據(jù)。當(dāng)輸入車輛數(shù)據(jù)為E時，程序自動退出。二、源程序可執(zhí)行程序文件名：停車問題.exe停車場問題管理程序代碼如下：#include/定義輸入輸出函數(shù)#include/數(shù)據(jù)流輸入輸出#include

15、/字符串處理#include/定義數(shù)學(xué)函數(shù) #include /定義雜項(xiàng)函數(shù)及內(nèi)存分配函數(shù) #define size 2 /停車場位置數(shù)/模擬停車場的堆棧的性質(zhì)typedef struct zanlind int number; /汽車車號 int ar_time; /汽車到達(dá)時間 zanInode;typedef struct zanInode *base; /停車場的堆棧底 zanInode *top; /停車場的堆棧頂 int stacksize_curren;stackhead;/堆棧的基本操作；void initstack(stackhead &L) /構(gòu)造一個空棧 L.base=(

16、zanInode*)malloc(size*sizeof(zanlind);if(!L.base)exit(0); /存儲分配失敗 L.top=L.base; L.stacksize_curren=0;void push(stackhead &L,zanInode e) /把元素e壓入L棧成為新的棧頂元素 *L.top+=e; L.stacksize_curren+;void pop(stackhead &L,zanInode &e) /把元素e彈出L棧 if(L.top=L.base) coutnext=NULL; q.length=0;void enqueue(linkqueue &q,i

17、nt number,int ar_time) /把元素插入隊(duì)列成為新的隊(duì)尾元素（屬性為number，ar_time） queueptr p; p=(queueptr)malloc(sizeof(duilie); if(!p) exit(0); p-number=number; p-ar_time=ar_time; p-next=NULL; q.rear-next=p; q.rear=p; q.length+;void popqueue(linkqueue &q,queueptr &w) /把元素插入隊(duì)列（屬性為number，ar_time） queueptr p; if(q.front=q.r

18、ear) cout停車場的便道為空 ! !next; w=p; q.front-next=p-next; q.length-; if(q.rear=p) q.front=q.rear;void jinru(stackhead &st,linkqueue &q) /對進(jìn)入停車場的汽車的處理； int number,time_a; coutnumber; couttime_a; if(st.stacksize_curren2) zanInode e; e.number=number; e.ar_time=time_a; push(st,e); cout 該車已進(jìn)入停車場在: st.stacksiz

19、e_curren 號車道endlendl; else enqueue(q,number,time_a);/插入元素time_a為q的新的隊(duì)尾元素 cout停車場已滿，該車先停在便道的第q.length個位置上endl; void likai(stackhead &st,stackhead &sl,linkqueue &q) /對離開的汽車的處理 /st堆棧為停車場，sl堆棧為倒車場 int number,time_d,flag=1,money,arrivaltime; /q為便道隊(duì)列 coutnumber; couttime_d; zanInode e,q_to_s; queueptr w;

20、while(flag) /找到要開出的車，并彈出停車場棧 pop(st,e); push(sl,e); if(e.number=number) flag=0; money=(time_d-e.ar_time)*2; arrivaltime=e.ar_time; pop(sl,e); /把臨時堆棧的第一輛車（要離開的）去掉； while(sl.stacksize_curren) /把倒車場的車倒回停車場 pop(sl,e); push(st,e); if(st.stacksize_currennumber; push(st,q_to_s); cout車牌為q_to_s.number的車已從通道進(jìn)

21、入停車場,所在的停車位為:st.stacksize_currenendlendl; cout 收 據(jù)endl; cout = 車牌號: numberendl; cout=endl; cout|進(jìn)車場時刻 | 出車場時刻 | 停留時間 | 應(yīng)付（元）|endl; cout=endl; cout| arrivaltime | time_d | time_d-arrivaltime | money |endl;cout-endlendl;int main()/主函數(shù)int m=100;char flag; /進(jìn)入或離開的標(biāo)識；stackhead sting,slinshi; /停車場和臨時倒車場堆棧

22、的定義；linkqueue line; /隊(duì)列的定義；initstack(sting); /構(gòu)造停車場堆棧stinginitstack(slinshi); /構(gòu)造倒車場堆棧slinshiinitqueue(line); /構(gòu)造便道隊(duì)列l(wèi)inewhile(m) coutn * 停車場管理程序 *endl; cout=endl; cout* *endl; cout* A - 汽車 進(jìn) 車場 D - 汽車 出 車場 *endl; cout* *endl; cout* E - 退出 程序 *endl; cout=endl; coutflag; switch(flag) case A: jinru(st

23、ing,line);break; /汽車進(jìn)車場 case D: likai(sting,slinshi,line);break; /汽車出車場 case E: exit(0); m-;return 0; 第五章 調(diào)試過程中的問題及系統(tǒng)測試情況一、出現(xiàn)的問題1、編程過程中忽略頭文件的作用，導(dǎo)致漏掉了一個頭文件,以致產(chǎn)生下列錯誤提示。錯誤提示：error C2065: malloc : undeclared identifier error C2065: exit : undeclared identifier 執(zhí)行 cl.exe 時出錯.在代碼中加上#definestdlib.h，解決此問題。2、沒有良好的編程習(xí)慣，沒有合適的縮進(jìn)及換行，給程序的調(diào)試帶來了比較多的困難。3、編程過程中比較粗心，一些程序結(jié)束的分號和成對出現(xiàn)的大括號忘記寫。第六章 結(jié)束語 通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我認(rèn)識到從課本上學(xué)到的知識是遠(yuǎn)遠(yuǎn)不夠的。本次設(shè)計(jì)使我深入的了解了棧與隊(duì)列的建立、插入、刪除和在實(shí)際問題下靈活運(yùn)用它們，另一方面使我對棧和隊(duì)列的抽象數(shù)據(jù)類型有了進(jìn)一步的認(rèn)識。雖然經(jīng)過努力終于把該系統(tǒng)完成，可是該系統(tǒng)還是不完善，程序