《清華大學(xué)_嚴(yán)蔚敏版_數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-停車場》由會員分享，可在線閱讀，更多相關(guān)《清華大學(xué)_嚴(yán)蔚敏版_數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-停車場（21頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 停車場管理系統(tǒng)專 業(yè)： 班 級：姓 名：學(xué) 號：指導(dǎo)教師： 完成日期：2008年6月25日 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書一、開設(shè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的目的 數(shù)據(jù)結(jié)構(gòu)是一門實踐性較強(qiáng)的軟件基礎(chǔ)課程，為了學(xué)好這門課程，必須在掌握理論知識的同時，加強(qiáng)上機(jī)實踐。本課程設(shè)計的目的就是要達(dá)到理論與實際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機(jī)內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設(shè)計技能，特開設(shè)此課程設(shè)計。二、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的具體內(nèi)容停車場管理系統(tǒng)問題描述 車輛的信息包括：車牌號、汽車到達(dá)/離去標(biāo)志、到達(dá)/離去時刻等。利用棧結(jié)構(gòu)模擬停車場，用隊列結(jié)構(gòu)模擬等待

2、的便道?；疽髄 收費：根據(jù)車輛到達(dá)和離開停車場的時間計時收費。l 查詢：通過車牌號能查到該車輛在停車場或便道中的位置l 調(diào)度：當(dāng)有車輛從停車場離開時，等待的車輛按順序進(jìn)入停車場停放。三、課程設(shè)計要求1、獨立思考，按要求認(rèn)真完成本次課程設(shè)計。 2、按照課程設(shè)計的具體要求完成幾個內(nèi)容。 a) 需求分析：敘述課題的功能要求；b ) 概要設(shè)計：詳細(xì)說明每個部分的算法設(shè)計及過程，可以輔助流程圖；， c）詳細(xì)設(shè)計：算法實現(xiàn)的源程序（設(shè)計的具體語言不限制）；d）調(diào)試分析：測試數(shù)據(jù)，時間復(fù)雜度分析，和每個模塊設(shè)計和調(diào)試時存在問題的思考。3、報告書提交（報告書的書寫格式參照以下條目）l 認(rèn)真完成報告書，使用

3、B5紙張，正文用小四字體, 打印。首頁為封面，要求寫清楚標(biāo)題、班級、姓名、指導(dǎo)教師、完成日期。第二頁為本任務(wù)書。第三頁為教師評語。第四頁為目錄。從第五頁開始，為報告書正文。l 報告書正文具體內(nèi)容包括：算法的簡介、說明及分析；整個程序的功能設(shè)計與分析；程序測試與分析，附程序清單。四、完成期限二八年六月二十三日 二七年六月二十七日 指導(dǎo)教師：黎婭 機(jī)電信息工程系 二八年六月二十日教師評語：目 錄任務(wù)書 2教師評語 3目錄 4一、 數(shù)據(jù)結(jié)構(gòu)內(nèi)容簡介 5二、 需求分析 5三、 算法設(shè)計 61.概要設(shè)計 72.詳細(xì)設(shè)計 9四、 程序功能分析 13 1.算法分析與探討 132.調(diào)試分析 13 3.程序測試

4、 14 4.測試結(jié)果 145.源程序代碼 15五、 總結(jié) 20 六、 參考文獻(xiàn) 21 一、 數(shù)據(jù)結(jié)構(gòu)內(nèi)容簡介數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，算法就是對數(shù)據(jù)運算的描述。程序設(shè)計的實質(zhì)就是對實際問題選取一種優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計一個優(yōu)秀的算法，而且優(yōu)秀的算法很大程度上取決于描述實際問題的數(shù)據(jù)結(jié)構(gòu)。棧是限定僅在表尾進(jìn)行插入和刪除的線性表。對棧來說，允許進(jìn)行插入和刪除的一端，稱為棧頂(top)；不允許插入和刪除的另一端則稱為棧底(bottom)。棧的運算有：(1)初始化CREAT(S):建立一個空棧；(2)入棧PUSH(S,x):在棧中加入一個新元素x；(3)出棧POP(S):刪除棧S的棧頂

5、元素；(4)取棧頂GETTOP(S):讀取S中的棧頂元素；(5)判空EMPTY(S)：測試棧S是否為空。隊列和棧一樣，均屬于限定性的數(shù)據(jù)結(jié)構(gòu)，也屬于線性表的一種。和棧相反，隊列是一種先進(jìn)先出的線性表，它只允許在表達(dá)的一端進(jìn)行插入，二在另一端進(jìn)行刪除元素，在隊列中，允許插入的一端稱為隊尾(Rear)，允許刪除的一端稱為隊頭(Front)。隊列的基本操作有：(1)構(gòu)造空隊列InitQueue(Q);(2)隊列銷毀DestroyQueue；(3)隊列清空ClearQueue(Q)；(4)取頭元素GetHead(Q,e)；(5)隊列插入Enqueue(Q,e)；(6)隊頭刪除Dequeue(Q,e)；

6、二、需求分析本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的具體內(nèi)容是停車場管理系統(tǒng)，該系統(tǒng)用棧結(jié)構(gòu)模擬停車場，限定停車場的容量為n，用隊列結(jié)構(gòu)模擬等待的便道，空間不限制。車輛的信息包括：車牌號、汽車到達(dá)/離去標(biāo)志、到達(dá)/離去時刻等。按照從終端讀入的數(shù)據(jù)序列進(jìn)行模擬管理。每輛車需要三個數(shù)據(jù)，其中車輛數(shù)據(jù)為：A表示到達(dá)，D表示離去，E表示程序結(jié)束。車輛牌照為整型數(shù)據(jù)。進(jìn)場或離場時間同樣為整型數(shù)據(jù)。對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。停車場管理系統(tǒng)主要實現(xiàn)以下幾個功能： (1)根

7、據(jù)車輛到達(dá)停車場到車輛離開停車場時所停留的時間進(jìn)行計時收費。 (2)該程序設(shè)計能夠通過車牌號能查到該車輛在停車場或便道中的位置。(3)當(dāng)有車輛從停車場離開時，等待的車輛按順序進(jìn)入停車場停放。實現(xiàn)停車場的調(diào)度功能。該程序設(shè)計可以完整的模擬停車場的管理過程。三、算法設(shè)計停車場管理系統(tǒng)是充分利用數(shù)據(jù)結(jié)構(gòu)中棧和隊列的思想實現(xiàn)的，棧是一種只能在叫做棧的一段進(jìn)行進(jìn)?；蛘叱鰲２僮鞯木€性數(shù)據(jù)結(jié)構(gòu)。棧的主要特點是”后進(jìn)先出”，即后進(jìn)棧的元素先處理。停車場的容量即為棧的存儲空間，停車場的車輛的?？渴菬o秩序的，因此采用鏈?zhǔn)酱鎯Φ姆绞礁m合，也方便車輛的調(diào)度。隊列是限定僅能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線

8、性表。隊列中可以插入的一端稱為隊尾，可以刪除的一端稱為隊首。把一個元素插入隊列中的操作為進(jìn)隊，隊列中刪除一個元素的操作為出隊。隊列存取操作符合：先進(jìn)先出。停車場的車輛到達(dá)停車和車輛的離開的管理方式就是采用隊列的“先進(jìn)先出”的移動的思想。停車場的入口就是隊列的隊首，停車場的出口就是隊列的隊尾。停車場管理系統(tǒng)流程圖如圖1所示。關(guān)閘開閘出口 入口 車輛過閘開閘繳費車輛過閘計時關(guān)閘調(diào)度等待準(zhǔn)備離場停車圖1 停車場管理系統(tǒng)流程圖1、概要設(shè)計1.1設(shè)定棧的抽象數(shù)據(jù)類型定義為：ADT stack數(shù)據(jù)對象：D=ai|aicharset, i=1,2,n,n0數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=2,n基本操

9、作：initstack(&S, n)操作結(jié)果：構(gòu)造一個空棧S,該?？纱娣舗個元素。push(&S, e)初始條件：棧S已存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。pop(&S, &e)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素，并以e返回其值。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：銷毀棧S。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將S清為空棧。StackLength(&S)初始條件：棧S已存在。操作結(jié)果：返回棧S的長度。StackEmpty(&S)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。GetTo

10、p(S, &e)初始條件：棧S已存在。操作結(jié)果：若棧S不空，則以e返回棧頂元素。StackTraverse(S, visit()初始條件：棧S已存在。操作結(jié)果：從棧底到棧頂依次對S中的每個元素調(diào)用函數(shù)visit()。ADT stack1.2 設(shè)定隊列的抽象數(shù)據(jù)類型定義為：ADT Queue數(shù)據(jù)對象：D=ai|aiElemSet, i=1,2,n,n0數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=2,n基本操作：InitQueue(&Q)操作結(jié)果：構(gòu)造一個空隊列Q。DestroyQueue(&Q)初始條件：隊列Q已存在。操作結(jié)果：隊列Q被銷毀，不再存在。ClearQueue(&Q)初始條件：隊列Q已存

11、在。操作結(jié)果：將Q清為空隊列。QueueEmpty(&Q)初始條件：隊列Q已存在。操作結(jié)果：若Q為空隊列，則返回TRUE，否則返回FALSE。QueueLength(Q)初始條件：隊列Q已存在。操作結(jié)果：返回Q的元素個數(shù)，即隊列的長度。GetHead(Q, &e)初始條件：Q為非空隊列。操作結(jié)果：用e返回Q的隊頭元素。EnQueue(&Q, e)初始條件：隊列Q已存在。操作結(jié)果：插入元素e為Q的新的隊尾元素。DeQueue(&Q, &e)初始條件：Q為非空隊列。操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。QueueTraverse(Q, visit()初始條件：Q已存在且非空。操作結(jié)果：從隊頭

12、到隊尾，依次對Q的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。ADT Queue2.詳細(xì)設(shè)計1 車輛信息類型typedef struct nodeint passport; /存儲車輛牌照信息int time; /存儲進(jìn)場時間信息node;2棧類型（停車場）typedef struct stacknode *base;node *top;int stacksize;stack;void initstack(stack &S,int n) /構(gòu)造空棧S.base=(node *)malloc(n*sizeof(node);S.top=S.base;S.stacksiz

13、e=n;void push(stack &S,node e) /入棧函數(shù)if(S.top-S.base)=S.stacksize)EnQueue(Q,e); /如果棧滿，調(diào)用入隊函數(shù)else S.top-passport=e.passport;S.top-time=e.time;S.top+;int pop(stack &S,node &e) /出棧函數(shù)if(S.top=S.base)return ERROR; /如果?？?，返回ERROR-S.top;e.passport=S.top-passport;e.time=S.top-time;return OK;3隊列類型（便道）typedef s

14、truct Qnodenode Qdata;struct Qnode *next;Qnode;typedef struct Qnode *front;Qnode *rear;LinkQueue;void EnQueue(LinkQueue &Q,node e) /入隊函數(shù)Qnode *q;q=(Qnode *)malloc(sizeof(Qnode);q-Qdata.passport=e.passport;q-Qdata.time=e.time;q-next=NULL;if(count=0)Q.front=q;count+; /若創(chuàng)建節(jié)點前隊空，頭指針指向節(jié)點Q.rear-next=q;Q.r

15、ear=q;void DeQueue(LinkQueue &Q,node &e) /出隊函數(shù)if(Q.rear=NULL)else e.passport=Q.front-Qdata.passport;e.time=Q.front-Qdata.time;Q.front=Q.front-next;if(Q.front=NULL)Q.rear=Q.front;count=0;4全局變量及編譯預(yù)處理語句#define ERROR 0#define OK 1#define NULL 0int count=0; /隊列是否為空的標(biāo)志int times;stack s,temp; /初始化棧LinkQueu

16、e Q; /初始化隊列5主函數(shù)及其他函數(shù)的C+算法void main()int n,exit;float money;char info;int pass;Q.front=NULL;Q.rear=(Qnode *)malloc(sizeof(Qnode);Q.rear-next=Q.rear;printf(停車場容量:);cinn;initstack(s,n);initstack(temp,n);printf(停車場費率:);cinmoney;while(exit!=OK)printf(n請輸入車輛數(shù)據(jù)nA到達(dá) D離去 E結(jié)束:);cininfo;printf(請輸入車輛牌照:);cinpas

17、s;if(info=A|info=E)printf(請輸入進(jìn)場時間:);if(info=D)printf(請輸入離場時間:);cintimes;if(info=E)exit=OK;else if(info=A)int i,j;node a;a.passport=pass;a.time=times;push(s,a);for(i=1;inext;j+;printf(停車位置(便道):%dn,j);else if(info=D)node d;int tp,counter=0;docounter+;tp=pop(s,d);while(tp!=ERROR)if(d.passport=pass)floa

18、t m;m=(times-d.time)*money;printf(停留時間:%d 需交費:%fn,times-d.time,m);while(temp.base!=temp.top)pop(temp,d);push(s,d);wait(s);d.passport=9999;tp=ERROR;elsepush(temp,d);d.passport=0;tp=ERROR;while(d.passport=0|countern);else if(info!=A&info!=D&info!=E)void wait(stack &S)if(S.top-S.base)=(S.stacksize-1)&c

19、ount!=0)node temp;DeQueue(Q,temp);temp.time=times;push(S,temp);三、程序功能分析1、算法分析與探討 該停車場管理系統(tǒng)首先初始化棧模擬停車場的容量，車輛到達(dá)時實現(xiàn)入棧操作，在棧中加入一個新元素，然后為新元素設(shè)置變量保存車輛的信息。車輛的信息包括：車牌號、汽車到達(dá)/離去標(biāo)志、到達(dá)/離去時刻等。用隊列模擬便道，實現(xiàn)能夠通過車牌號等信息就可以查到車輛在便道中的位置。按照從終端讀入的數(shù)據(jù)序列進(jìn)行模擬管理。每輛車需要三個數(shù)據(jù)，其中車輛數(shù)據(jù)為：A表示到達(dá)，D表示離去，E表示程序結(jié)束。車輛牌照為整型數(shù)據(jù)。進(jìn)場或離場時間同樣為整型數(shù)據(jù)。對每一組輸入數(shù)

20、據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。如果停車場滿了即棧滿了就調(diào)用隊列函數(shù)，等其他車輛離開后新的車輛在進(jìn)入便道。2、調(diào)試分析（1）一開始在調(diào)試程序時遇到了內(nèi)存錯誤，經(jīng)過DEBUG，找到了引起內(nèi)存錯誤的原因：即在建立隊頭指針與隊尾指針時沒有對指針進(jìn)行初始化(沒有為指針動態(tài)分配空間)。問題得到解決。 （2）在Wait函數(shù)中的If語句處，一開始的算法有些問題，導(dǎo)致實現(xiàn)的功能與設(shè)想的有出入，無法得到正確的結(jié)果。原條件為: S.top-S.base=S.stacksize后改

21、為： (S.top-S.base)=(S.stacksize-1)&count!=0 該函數(shù)的功能得以正確實現(xiàn)。（3）在EnQueue函數(shù)中，一開始用的是建立實體結(jié)點，用隊頭隊尾指針指向該實體的方法來創(chuàng)建隊列。在調(diào)試過程中發(fā)現(xiàn)，忽略了生存期，導(dǎo)致隊列并沒有被創(chuàng)建。改為創(chuàng)建指針，并為指針分配空間，再給頭指針和尾指針賦值的方式解決問題。雖然指針也有生存期，但為它分配的空間卻并沒有被收回，于是隊列創(chuàng)建成功，問題解決。 （4）本程序中：車輛到達(dá),離去時的時間復(fù)雜度均為：O(n)。本程序空間復(fù)雜度為：O(n)。 （5）經(jīng)驗體會：借助DEBUG和Watch，可以更快的找到程序中的非語法錯誤。在聲明一個指針

22、后，要對指針進(jìn)行初始化，并且0可以作為地址使用。注意生存期對程序的影響。3、程序測試（1）輸入車輛數(shù)據(jù)：A為到達(dá)，D為離去，E為結(jié)束程序。（2）接著輸入車輛的牌照信息（3）若為到達(dá)的車輛，輸入進(jìn)場信息，若為離去的車輛，輸入離場信息。（4）若車輛到達(dá)，可得到車輛的停放位置信息，若車輛離去，可得到車輛的停放時間（在便道上的停放時間除外），以及應(yīng)該交納的費用。（5）本程序不斷循環(huán)要求輸入車輛信息，直到輸入的車輛數(shù)據(jù)為E時，程序結(jié)束。4、測試結(jié)果測試數(shù)據(jù)：設(shè)n=2輸入數(shù)據(jù)：2輸出：停車場容量:2停車場費率:6A，1，5 停車位置(停車場內(nèi)):1A，2，10 停車位置(停車場內(nèi)):2D，1，15 停留時

23、間:10 需交費:60.00A，3，20 停車位置(停車場內(nèi)):2A，4，25 停車位置(便道):1A，5，30 停車位置(便道):2D，2，35 停留時間:25 需交費:150.00D，4，40 停留時間:5 需交費:30.00E，0，05、源程序代碼#include #include #include #define ERROR 0#define OK 1#define NULL 0typedef struct nodeint passport;int time;node;typedef struct stacknode *base;node *top;int stacksize;stac

24、k;typedef struct Qnodenode Qdata;struct Qnode *next;Qnode;typedef struct Qnode *front;Qnode *rear;LinkQueue;int count=0;int times;stack s,temp;LinkQueue Q;void initstack(stack &S,int n)S.base=(node *)malloc(n*sizeof(node);S.top=S.base;S.stacksize=n;void EnQueue(LinkQueue &Q,node e);void DeQueue(Link

25、Queue &Q,node &e);void push(stack &S,node e)if(S.top-S.base)=S.stacksize)EnQueue(Q,e);else S.top-passport=e.passport;S.top-time=e.time;S.top+;int pop(stack &S,node &e)if(S.top=S.base)return ERROR;-S.top;e.passport=S.top-passport;e.time=S.top-time;return OK;void wait(stack &S)if(S.top-S.base)=(S.stac

26、ksize-1)&count!=0)node temp;DeQueue(Q,temp);temp.time=times;push(S,temp);void EnQueue(LinkQueue &Q,node e)Qnode *q;q=(Qnode *)malloc(sizeof(Qnode);q-Qdata.passport=e.passport;q-Qdata.time=e.time;q-next=NULL;if(count=0)Q.front=q;count+;Q.rear-next=q;Q.rear=q;void DeQueue(LinkQueue &Q,node &e)if(Q.rea

27、r=NULL)else e.passport=Q.front-Qdata.passport;e.time=Q.front-Qdata.time;Q.front=Q.front-next;if(Q.front=NULL)Q.rear=Q.front;count=0;void main()int n,exit;float money;char info;int pass;Q.front=NULL;Q.rear=(Qnode *)malloc(sizeof(Qnode);Q.rear-next=Q.rear;printf(停車場容量:);cinn;initstack(s,n);initstack(t

28、emp,n);printf(停車場費率:);cinmoney;while(exit!=OK)printf(n請輸入車輛數(shù)據(jù)nA到達(dá) D離去 E結(jié)束:);cininfo;printf(請輸入車輛牌照:);cinpass;if(info=A|info=E)printf(請輸入進(jìn)場時間:);if(info=D)printf(請輸入離場時間:);cintimes;if(info=E)exit=OK;else if(info=A)int i,j;node a;a.passport=pass;a.time=times;push(s,a);for(i=1;inext;j+;printf(停車位置(便道):%

29、dn,j);else if(info=D)node d;int tp,counter=0;docounter+;tp=pop(s,d);while(tp!=ERROR)if(d.passport=pass)float m;m=(times-d.time)*money;printf(停留時間:%d 需交費:%fn,times-d.time,m);while(temp.base!=temp.top)pop(temp,d);push(s,d);wait(s);d.passport=9999;tp=ERROR;elsepush(temp,d);d.passport=0;tp=ERROR;while(d

30、.passport=0|countern);else if(info!=A&info!=D&info!=E)總 結(jié)本次課程設(shè)計主要是運用本學(xué)期學(xué)的數(shù)據(jù)結(jié)構(gòu)的知識設(shè)計一個停車場管理系統(tǒng)，使本學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)的課程內(nèi)容得到了具體的運用，更加深了對這門課程的理解。在本次課程設(shè)計中不僅加深了對棧和隊列等數(shù)據(jù)結(jié)構(gòu)的理解和掌握，同時一定程度上提高了自己程序設(shè)計和閱讀程序的能力。本次課程設(shè)計提高了我們的專業(yè)知識，使自己所學(xué)的內(nèi)容運用到實際中來，也增強(qiáng)了實際操作能力，為以后的工作學(xué)習(xí)提供了一個良好的鋪墊。通過本次課程設(shè)計的實踐學(xué)習(xí)，我認(rèn)識到了學(xué)好計算機(jī)要重視實踐操作，所以在以后的學(xué)習(xí)過程中，我會更加注重實踐操作，使自己更好地學(xué)好計算機(jī)。參考文獻(xiàn)1.黃保和 數(shù)據(jù)結(jié)構(gòu)（C語言版） 上海交通大學(xué)出版社，20002.朱站立 數(shù)據(jù)結(jié)構(gòu) 西安交通大學(xué)出版社，20003.嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)(C語言版） 清華大學(xué)出版社，19974.唐策善 數(shù)據(jù)結(jié)構(gòu)(C語言版) 北京高等教育出版社，19975.許卓群 數(shù)據(jù)結(jié)構(gòu) 北京高等教育出版社，19876.袁蒲佳 數(shù)據(jù)結(jié)構(gòu) 華中理工大學(xué)出版社，19917.楊正宏 數(shù)據(jù)結(jié)構(gòu) 中國鐵道出版設(shè)，20018.唐發(fā)根 數(shù)據(jù)結(jié)構(gòu) 北京科學(xué)出版社，19989.徐孝凱 數(shù)據(jù)結(jié)構(gòu) 清華大學(xué)出版社，1999