停車場管理系統(tǒng)專 業(yè)： 班 級：姓 名：學 號：指導教師： 完成日期：2008年6月25日 數(shù)據(jù)結構課程設計任務書一、開設數(shù)據(jù)結構課程設計的目的 數(shù)據(jù)結構是一門實踐性較強的軟件基礎課程，為了學好這門課程，必須在掌握理論知識的同時，加強上機實踐。本課程設計的目的就是要達到理論與實際應用相結合，使同學們能夠根據(jù)數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設計技能， 特開設此課程設計。二、數(shù)據(jù)結構課程設計的具體內(nèi)容停車場管理系統(tǒng)問題描述 車輛的信息包括：車牌號、汽車到達/離去標志、到達/離去時刻等。利用棧結構模擬停車場，用隊列結構模擬等待的便道?；疽髄 收費：根據(jù)車輛到達和離開停車場的時間計時收費。l 查詢：通過車牌號能查到該車輛在停車場或便道中的位置l 調(diào)度：當有車輛從停車場離開時，等待的車輛按順序進入停車場停放。三、課程設計要求1、獨立思考，按要求認真完成本次課程設計。 2、按照課程設計的具體要求完成幾個內(nèi)容。 a) 需求分析：敘述課題的功能要求；b ) 概要設計：詳細說明每個部分的算法設計及過程，可以輔助流程圖；， c）詳細設計：算法實現(xiàn)的源程序（設計的具體語言不限制）；d）調(diào)試分析：測試數(shù)據(jù)，時間復雜度分析，和每個模塊設計和調(diào)試時存在問題的思考。3、報告書提交（報告書的書寫格式參照以下條目）l 認真完成報告書，使用B5紙張，正文用小四字體, 打印。首頁為封面，要求寫清楚標題、班級、姓名、指導教師、完成日期。第二頁為本任務書。第三頁為教師評語。第四頁為目錄。從第五頁開始，為報告書正文。l 報告書正文具體內(nèi)容包括：算法的簡介、說明及分析；整個程序的功能設計與分析；程序測試與分析，附程序清單。四、完成期限二八年六月二十三日 二七年六月二十七日 指導教師：黎婭 機電信息工程系 二八年六月二十日教師評語：目 錄任務書 2教師評語 3目錄 4一、 數(shù)據(jù)結構內(nèi)容簡介 5二、 需求分析 5三、 算法設計 61.概要設計 72.詳細設計 9四、 程序功能分析 13 1.算法分析與探討 132.調(diào)試分析 13 3.程序測試 14 4.測試結果 145.源程序代碼 15五、 總結 20 六、 參考文獻 21 一、 數(shù)據(jù)結構內(nèi)容簡介數(shù)據(jù)結構指的是數(shù)據(jù)的邏輯結構和存儲結構，算法就是對數(shù)據(jù)運算的描述。程序設計的實質就是對實際問題選取一種優(yōu)秀的數(shù)據(jù)結構，加之設計一個優(yōu)秀的算法，而且優(yōu)秀的算法很大程度上取決于描述實際問題的數(shù)據(jù)結構。棧是限定僅在表尾進行插入和刪除的線性表。對棧來說，允許進行插入和刪除的一端，稱為棧頂(top)；不允許插入和刪除的另一端則稱為棧底(bottom)。棧的運算有：(1)初始化CREAT(S):建立一個空棧；(2)入棧PUSH(S,x):在棧中加入一個新元素x；(3)出棧POP(S):刪除棧S的棧頂元素；(4)取棧頂GETTOP(S):讀取S中的棧頂元素；(5)判空EMPTY(S)：測試棧S是否為空。隊列和棧一樣，均屬于限定性的數(shù)據(jù)結構，也屬于線性表的一種。和棧相反，隊列是一種先進先出的線性表，它只允許在表達的一端進行插入，二在另一端進行刪除元素，在隊列中，允許插入的一端稱為隊尾(Rear)，允許刪除的一端稱為隊頭(Front)。隊列的基本操作有：(1)構造空隊列InitQueue(Q);(2)隊列銷毀DestroyQueue；(3)隊列清空ClearQueue(Q)；(4)取頭元素GetHead(Q,e)；(5)隊列插入Enqueue(Q,e)；(6)隊頭刪除Dequeue(Q,e)；二、需求分析本次數(shù)據(jù)結構課程設計的具體內(nèi)容是停車場管理系統(tǒng)，該系統(tǒng)用棧結構模擬停車場，限定停車場的容量為n，用隊列結構模擬等待的便道，空間不限制。車輛的信息包括：車牌號、汽車到達/離去標志、到達/離去時刻等。按照從終端讀入的數(shù)據(jù)序列進行模擬管理。每輛車需要三個數(shù)據(jù)，其中車輛數(shù)據(jù)為：A表示到達，D表示離去，E表示程序結束。車輛牌照為整型數(shù)據(jù)。進場或離場時間同樣為整型數(shù)據(jù)。對每一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應交納的費用（在便道上停留的時間不收費）。停車場管理系統(tǒng)主要實現(xiàn)以下幾個功能： (1)根據(jù)車輛到達停車場到車輛離開停車場時所停留的時間進行計時收費。 (2)該程序設計能夠通過車牌號能查到該車輛在停車場或便道中的位置。(3)當有車輛從停車場離開時，等待的車輛按順序進入停車場停放。實現(xiàn)停車場的調(diào)度功能。該程序設計可以完整的模擬停車場的管理過程。三、算法設計停車場管理系統(tǒng)是充分利用數(shù)據(jù)結構中棧和隊列的思想實現(xiàn)的，棧是一種只能在叫做棧的一段進行進?；蛘叱鰲２僮鞯木€性數(shù)據(jù)結構。棧的主要特點是”后進先出”，即后進棧的元素先處理。停車場的容量即為棧的存儲空間，停車場的車輛的停靠是無秩序的，因此采用鏈式存儲的方式更適合，也方便車輛的調(diào)度。隊列是限定僅能在表的一端進行插入，在表的另一端進行刪除的線性表。隊列中可以插入的一端稱為隊尾，可以刪除的一端稱為隊首。把一個元素插入隊列中的操作為進隊，隊列中刪除一個元素的操作為出隊。隊列存取操作符合：先進先出。停車場的車輛到達停車和車輛的離開的管理方式就是采用隊列的“先進先出”的移動的思想。停車場的入口就是隊列的隊首，停車場的出口就是隊列的隊尾。停車場管理系統(tǒng)流程圖如圖1所示。關閘開閘出口 入口 車輛過閘開閘繳費車輛過閘計時關閘調(diào)度等待準備離場停車圖1 停車場管理系統(tǒng)流程圖1、概要設計1.1設定棧的抽象數(shù)據(jù)類型定義為：ADT stack數(shù)據(jù)對象：D=ai|aicharset, i=1,2,n,n0數(shù)據(jù)關系：R1=|ai-1,aiD,i=2,n基本操作：initstack(&S, n)操作結果：構造一個空棧S,該?？纱娣舗個元素。push(&S, e)初始條件：棧S已存在。操作結果：在棧S的棧頂插入新的棧頂元素e。pop(&S, &e)初始條件：棧S已存在。操作結果：刪除S的棧頂元素，并以e返回其值。DestroyStack(&S)初始條件：棧S已存在。操作結果：銷毀棧S。ClearStack(&S)初始條件：棧S已存在。操作結果：將S清為空棧。StackLength(&S)初始條件：棧S已存在。操作結果：返回棧S的長度。StackEmpty(&S)初始條件：棧S已存在。操作結果：若S為空棧，則返回TRUE，否則返回FALSE。GetTop(S, &e)初始條件：棧S已存在。操作結果：若棧S不空，則以e返回棧頂元素。StackTraverse(S, visit()初始條件：棧S已存在。操作結果：從棧底到棧頂依次對S中的每個元素調(diào)用函數(shù)visit()。ADT stack1.2 設定隊列的抽象數(shù)據(jù)類型定義為：ADT Queue數(shù)據(jù)對象：D=ai|aiElemSet, i=1,2,n,n0數(shù)據(jù)關系：R1=|ai-1,aiD,i=2,n基本操作：InitQueue(&Q)操作結果：構造一個空隊列Q。DestroyQueue(&Q)初始條件：隊列Q已存在。操作結果：隊列Q被銷毀，不再存在。ClearQueue(&Q)初始條件：隊列Q已存在。操作結果：將Q清為空隊列。QueueEmpty(&Q)初始條件：隊列Q已存在。操作結果：若Q為空隊列，則返回TRUE，否則返回FALSE。QueueLength(Q)初始條件：隊列Q已存在。操作結果：返回Q的元素個數(shù)，即隊列的長度。GetHead(Q, &e)初始條件：Q為非空隊列。操作結果：用e返回Q的隊頭元素。EnQueue(&Q, e)初始條件：隊列Q已存在。操作結果：插入元素e為Q的新的隊尾元素。DeQueue(&Q, &e)初始條件：Q為非空隊列。操作結果：刪除Q的隊頭元素，并用e返回其值。QueueTraverse(Q, visit()初始條件：Q已存在且非空。操作結果：從隊頭到隊尾，依次對Q的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。ADT Queue2.詳細設計1 車輛信息類型typedef struct nodeint passport; /存儲車輛牌照信息int time; /存儲進場時間信息node;2棧類型（停車場）typedef struct stacknode *base;node *top;int stacksize;stack;void initstack(stack &S,int n) /構造空棧S.base=(node *)malloc(n*sizeof(node);S.top=S.base;S.stacksize=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 struct 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.rear=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全局變量及編譯預處理語句#define ERROR 0#define OK 1#define NULL 0int count=0; /隊列是否為空的標志int times;stack s,temp; /初始化棧LinkQueue 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("停車場容量:");cin>>n;initstack(s,n);initstack(temp,n);printf("停車場費率:");cin>>money;while(exit!=OK)printf("n請輸入車輛數(shù)據(jù)nA到達 D離去 E結束:");cin>>info;printf("請輸入車輛牌照:");cin>>pass;if(info='A'|info='E')printf("請輸入進場時間:");if(info='D')printf("請輸入離場時間:");cin>>times;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;i<=n;i+)if(s.basei-1.passport=a.passport)printf("停車位置(停車場內(nèi)):%dn",i);Qnode *tp;tp=Q.front;if(tp=NULL)elsej=1;while(tp!=Q.rear)tp=tp->next;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)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.passport=0|counter>n);else if(info!='A'&&info!='D'&&info!='E')void wait(stack &S)if(S.top-S.base)=(S.stacksize-1)&&count!=0)node temp;DeQueue(Q,temp);temp.time=times;push(S,temp);三、程序功能分析1、算法分析與探討 該停車場管理系統(tǒng)首先初始化棧模擬停車場的容量，車輛到達時實現(xiàn)入棧操作，在棧中加入一個新元素，然后為新元素設置變量保存車輛的信息。車輛的信息包括：車牌號、汽車到達/離去標志、到達/離去時刻等。用隊列模擬便道，實現(xiàn)能夠通過車牌號等信息就可以查到車輛在便道中的位置。按照從終端讀入的數(shù)據(jù)序列進行模擬管理。每輛車需要三個數(shù)據(jù)，其中車輛數(shù)據(jù)為：A表示到達，D表示離去，E表示程序結束。車輛牌照為整型數(shù)據(jù)。進場或離場時間同樣為整型數(shù)據(jù)。對每一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應交納的費用（在便道上停留的時間不收費）。如果停車場滿了即棧滿了就調(diào)用隊列函數(shù)，等其他車輛離開后新的車輛在進入便道。2、調(diào)試分析（1）一開始在調(diào)試程序時遇到了內(nèi)存錯誤，經(jīng)過DEBUG，找到了引起內(nèi)存錯誤的原因：即在建立隊頭指針與隊尾指針時沒有對指針進行初始化(沒有為指針動態(tài)分配空間)。問題得到解決。 （2）在Wait函數(shù)中的If語句處，一開始的算法有些問題，導致實現(xiàn)的功能與設想的有出入，無法得到正確的結果。原條件為: S.top-S.base=S.stacksize后改為： (S.top-S.base)=(S.stacksize-1)&&count!=0 該函數(shù)的功能得以正確實現(xiàn)。（3）在EnQueue函數(shù)中，一開始用的是建立實體結點，用隊頭隊尾指針指向該實體的方法來創(chuàng)建隊列。在調(diào)試過程中發(fā)現(xiàn)，忽略了生存期，導致隊列并沒有被創(chuàng)建。改為創(chuàng)建指針，并為指針分配空間，再給頭指針和尾指針賦值的方式解決問題。雖然指針也有生存期，但為它分配的空間卻并沒有被收回，于是隊列創(chuàng)建成功，問題解決。 （4）本程序中：車輛到達,離去時的時間復雜度均為：O(n)。本程序空間復雜度為：O(n)。 （5）經(jīng)驗體會：借助DEBUG和Watch，可以更快的找到程序中的非語法錯誤。在聲明一個指針后，要對指針進行初始化，并且0可以作為地址使用。注意生存期對程序的影響。3、程序測試（1）輸入車輛數(shù)據(jù)：A為到達，D為離去，E為結束程序。（2）接著輸入車輛的牌照信息（3）若為到達的車輛，輸入進場信息，若為離去的車輛，輸入離場信息。（4）若車輛到達，可得到車輛的停放位置信息，若車輛離去，可得到車輛的停放時間（在便道上的停放時間除外），以及應該交納的費用。（5）本程序不斷循環(huán)要求輸入車輛信息，直到輸入的車輛數(shù)據(jù)為E時，程序結束。4、測試結果測試數(shù)據(jù)：設n=2輸入數(shù)據(jù)：2輸出：停車場容量:2停車場費率:6A，1，5 停車位置(停車場內(nèi)):1A，2，10 停車位置(停車場內(nèi)):2D，1，15 停留時間: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 <stdio.h>#include <iostream.h>#include <malloc.h>#define ERROR 0#define OK 1#define NULL 0typedef struct nodeint passport;int time;node;typedef struct stacknode *base;node *top;int stacksize;stack;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(LinkQueue &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.stacksize-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.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;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("停車場容量:");cin>>n;initstack(s,n);initstack(temp,n);printf("停車場費率:");cin>>money;while(exit!=OK)printf("n請輸入車輛數(shù)據(jù)nA到達 D離去 E結束:");cin>>info;printf("請輸入車輛牌照:");cin>>pass;if(info='A'|info='E')printf("請輸入進場時間:");if(info='D')printf("請輸入離場時間:");cin>>times;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;i<=n;i+)if(s.basei-1.passport=a.passport)printf("停車位置(停車場內(nèi)):%dn",i);Qnode *tp;tp=Q.front;if(tp=NULL)elsej=1;while(tp!=Q.rear)tp=tp->next;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)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.passport=0|counter>n);else if(info!='A'&&info!='D'&&info!='E')總 結本次課程設計主要是運用本學期學的數(shù)據(jù)結構的知識設計一個停車場管理系統(tǒng)，使本學期所學的數(shù)據(jù)結構的課程內(nèi)容得到了具體的運用，更加深了對這門課程的理解。在本次課程設計中不僅加深了對棧和隊列等數(shù)據(jù)結構的理解和掌握，同時一定程度上提高了自己程序設計和閱讀程序的能力。本次課程設計提高了我們的專業(yè)知識，使自己所學的內(nèi)容運用到實際中來，也增強了實際操作能力，為以后的工作學習提供了一個良好的鋪墊。通過本次課程設計的實踐學習，我認識到了學好計算機要重視實踐操作，所以在以后的學習過程中，我會更加注重實踐操作，使自己更好地學好計算機。參考文獻1.黃保和 數(shù)據(jù)結構（C語言版） 上海交通大學出版社，20002.朱站立 數(shù)據(jù)結構 西安交通大學出版社，20003.嚴蔚敏 數(shù)據(jù)結構(C語言版） 清華大學出版社，19974.唐策善 數(shù)據(jù)結構(C語言版) 北京高等教育出版社，19975.許卓群 數(shù)據(jù)結構 北京高等教育出版社，19876.袁蒲佳 數(shù)據(jù)結構 華中理工大學出版社，19917.楊正宏 數(shù)據(jù)結構 中國鐵道出版設，20018.唐發(fā)根 數(shù)據(jù)結構 北京科學出版社，19989.徐孝凱 數(shù)據(jù)結構 清華大學出版社，1999