數(shù)據(jù)結(jié)構(gòu)課程設計報告(含源碼)

1、. . . . 科技學院課程設計報告院（系）:電氣與信息工程學院專業(yè)班級: 計科普0902 學生: 鄧小祥 學 號: 2009441656 設計地點（單位）_計算機基礎自主學習中心I306_設計題目:_停車場管理系統(tǒng)設計_ 完成日期： 2011年 1月 14日指導教師評語: _ _ 成績（五級記分制）:_ _ 指導教師（簽字）:_ _ 19 / 24科技學院課程設計任務書設計題目：停車場管理系統(tǒng)的設計學生課程名稱數(shù)據(jù)結(jié)構(gòu)課程設計專業(yè)班級計科2009-01、02地 點計算機基礎自主學習中心起止時間2011.01.4-2011.01.14設計容與要求問題描述：設停車場是一個可停放n輛汽車的狹長通道

2、，且只有一個大門可供汽車進出。汽車在停車場按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在停車場的最北端），若停車場已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序?；疽笠詶ＤM停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到

3、達”或“離去”信息、汽車牌照以與到達或離去的時刻。對每一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場或便道上的停車位置；若是車輛離去，則輸出汽車在停車場停留的時間和應交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。設計參數(shù)設n=2，輸入數(shù)據(jù)為：（A,1,5）,（A,2,10）,（D,1,15）,（A,3,20）,（A,4,25）,（A5,30）,（D,2,35）,（D,4,40）,（E,0,0）。其中：A表示到達（arrival）；D表示離去（departure）；E表示輸出結(jié)束（end）。參考資料1嚴蔚敏 吳偉民 著， 數(shù)據(jù)結(jié)構(gòu)（C語言版）

4、，清華大學，2007.42Richard F.Gilberg Behrouz A.Forouzan, Data Structures A Pseudocode Approach with C，second edition, Thomson, 2005.13. 春葆 著，數(shù)據(jù)結(jié)構(gòu)教程，清華大學，2005.1說明.本表應在每次實施前一周由負責教師填寫二份，院系審批后交院系辦備案，一份由負責教師留用。.若填寫容較多可另紙附后。3.一題多名學生共用的，在設計容、參數(shù)、要求等方面應有所區(qū)別。教研室主任：向毅 指導教師：向毅、奎、熊茜 2010年 12 月 20日摘要隨著現(xiàn)在數(shù)據(jù)處理的多樣性、復雜性，數(shù)據(jù)

5、結(jié)構(gòu)的應用也隨之運用的更加的廣泛，運用數(shù)據(jù)結(jié)構(gòu)處理問題也更加的方便快捷。此次停車場管理系統(tǒng)的設計是利用兩個堆棧來分別模擬停車場以與停車場車輛為其它車輛讓路時退出停車的臨時停放地點。通道上車輛的停放則用一個隊列來實現(xiàn)，此時，通道上車輛的離開或者進入停車場只需改變此隊列上的結(jié)點。對于要對停車場的車輛根據(jù)其停放時間收取相應的停車費用，可以記錄下車輛進入以與離開停車場的時間，再用時間差乘以相應的單價并且打印出最后的費用就可以實現(xiàn)。關鍵詞：數(shù)據(jù)結(jié)構(gòu)、堆棧、對列、計時收費目錄摘要I1.設計容與要求11.1 設計容11.2 設計要求12.概要設計12.1 設計思想12.2 主要模塊22.3 程序結(jié)構(gòu)23.系

6、統(tǒng)分析與設計33.1 系統(tǒng)數(shù)據(jù)結(jié)構(gòu)設計33.1.1 堆棧33.1.2 隊列33.2系統(tǒng)算法設計和流程43.2.1系統(tǒng)算法設計43.2.2系統(tǒng)流程圖54.系統(tǒng)測試65.致8參考文獻9附錄101.設計容與要求1.1 設計容設計一個停車場，停車場是一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在停車場的最北端），若停車場已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門

7、外，其他車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。1.2 設計要求以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照以與到達或離去的時刻。對每一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場或便道上的停車位置；若是車輛離去，則輸出汽車在停車場停留的時間和應交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。2.概要設計2.1 設計思想此停車場管理系統(tǒng)是在一個狹長

8、的通道上的，而且只有一個大門可以供車輛進出，并且要實現(xiàn)停車場某輛車要離開時，在它之后進入停車場的車都必須先退出停車場為它讓路，待其開出停車場后，這些車再依原來的次序進場的功能，就可以設計兩個堆棧，其中一個堆棧用來模擬停車場，另一個堆棧用來模擬臨時停車場，該臨時停車場用來存放當有車輛離開時，原來停車場為其讓路的車輛。至于當停車場已滿時，需要停放車輛的通道可以用一個隊列來實現(xiàn)。當停車場開走一輛車時，通道上便有一輛車進入停車場，此時只需要將對列元素彈到堆棧中就可以了，使通道上第一輛車進入停車場這個堆棧，并且使通道上原來的第二輛車成為通道上的第一輛車。2.2 主要模塊首先定義用來模擬停車場的堆棧以與用

9、來模擬通道的隊列為全局變量，然后編寫主函數(shù)，在此主函數(shù)中實現(xiàn)對其它各個模塊的調(diào)用。在主函數(shù)中首先調(diào)用Menu()函數(shù)，出現(xiàn)歡迎用戶使用的主界面，然后提示用戶進入此停車場管理系統(tǒng)后，再出現(xiàn)一個供用戶選擇的界面，在用戶的選擇過程中，程序又分別調(diào)用車輛的進入、車輛的離開、停車場停放車輛的信息以與退出程序這四個函數(shù)模塊。其中，在車輛的離開那個模塊函數(shù)中又調(diào)用了打印離開車輛信息的函數(shù)，在停車場停放車輛信息的那個模塊函數(shù)中，又分別調(diào)用了顯示停車場上車輛信息的函數(shù)以與顯示便道上車輛信息的函數(shù)。最后，從調(diào)用的這四個函數(shù)中回到主函數(shù)結(jié)束整個程序的運行。2.3 程序結(jié)構(gòu)導航菜單汽車進入汽車離開車庫信息信息處理退出

10、系統(tǒng)圖2.1模塊調(diào)用結(jié)構(gòu)圖3.系統(tǒng)分析與設計3.1 系統(tǒng)數(shù)據(jù)結(jié)構(gòu)設計本停車場管理系統(tǒng)是利用堆棧和隊列來進行實現(xiàn)的，分別利用堆棧和隊列的基本操作。3.1.1 堆棧利用堆棧的性質(zhì)就可以模擬出停車場的部車道，車輛必須滿足先進后出的規(guī)律，里面的車輛出入必須先移出后進的車輛。堆棧的基本操作如下：creatStack() 建立堆棧pushStack (STACK* stack, void* dataInPtr) 壓入元素進棧popStack (STACK* stack, void* dataInPtr) 彈出棧元素fullStack (STACK* stack) 判斷棧滿emptyStack (STACK

11、* stack) 判斷棧空destoryStack (STACK* stack) 銷毀堆棧3.1.2 隊列利用隊列的性質(zhì)可以模擬出停車場外部的便道，當停車場部的車滿后將車輛停在便道上。便道著滿足隊列的性質(zhì)先進先出，當部有空位就將便道上第一輛車停如。隊列的基本操作如下：createQueue () 建立隊列enqueue (QUEUE* queue, void* itemPtr) 元素進對dequeue (QUEUE* queue) 元素出隊fullQueue (QUEUE* queue) 判斷隊滿emptyQueue (QUEUE* queue) 判斷隊空destroyQueue(QUEUE*

12、 queue) 銷毀隊列3.2系統(tǒng)算法設計和流程3.2.1系統(tǒng)算法設計分別利用一個堆棧和一個隊列來模擬停車廠部車道和外部便道，當有車停入時則將車的信息壓入棧中，當部車道滿了后則將車先停到便道中等候車位。當車輛要出去時則利用一個臨時的堆棧來進行數(shù)據(jù)的緩存，先將車的信息壓入臨時堆棧，當目標車出棧后則將臨時棧的元素轉(zhuǎn)入停車場棧中，并將便道的上的車的第一輛轉(zhuǎn)入部車道。通過堆棧、隊列對信息的查詢也只需要對結(jié)構(gòu)元素一一遍歷即可，這樣就可以實現(xiàn)對停車場信息的處理。系統(tǒng)主要2個部分：停車 取車都是對堆棧和隊列的操作。汽車進入時則壓入堆?；蜿犃兄?，離開時則彈出。定義汽車的屬性結(jié)構(gòu)體，并用結(jié)構(gòu)體來描述和存儲汽車的

13、信息。typedef structint number;車牌號int time; 進入時間char size; 汽車型號 CAR;汽車的入庫時對堆棧和隊列的壓入操作，將汽車信息結(jié)構(gòu)體鏈到堆棧隊列中CAR* car; 定義一汽車的信息pushStack(stack,car); 壓棧與進入車庫中enqueue(queue, car); 進對與停放在便道上汽車離開時將堆?；蜿犃兄械哪繕似囆畔h掉并對信息處理分析打印出要的信息車庫中車的離開處理：carout=(CAR*)popStack(stack)pushStack(changestack,carout) 將汽車信息轉(zhuǎn)入臨時棧中保存pushSta

14、ck(stack,changecar) 處理后汽車信息從新存入車庫棧中便道上車輛的離開：changecar=(CAR*)dequeue(queue)enqueue(changequeue,changecar) 將汽車信息轉(zhuǎn)入臨時隊中保存enqueue(queue,changecar) 處理后汽車信息從新存入便道隊中通過部車庫棧和便到隊列來存儲汽車信息，然后通過其得基本操作來得到汽車的進入和離開，并得到預期的結(jié)果。3.2.2系統(tǒng)流程圖開始初始化棧parklot和隊列road進入主菜單車進入車離開退出目標車前車輛進臨時棧目標車計費便道車信息車場內(nèi)信息判便道是否有車車場是否為空列表顯示元素進棧par

15、klot便道車進車場元素進隊列road判斷棧是否為滿結(jié)束退出列表顯示是否否是否是圖3.5 程序流程圖4.系統(tǒng)測試進入系統(tǒng)，先調(diào)用void beginsystem(STACK*stack,QUEUE*queue)函數(shù)進行初始化堆棧和隊列，讀取已保存的信息。然后調(diào)用menu()函數(shù)調(diào)出導航菜單提供功能導航，如圖4.1圖4.1通過導航菜單分別對不同的功能進行實現(xiàn)，而調(diào)用相關的函數(shù)。車輛進入時則調(diào)用停車函數(shù)void car_park(STACK*stack,QUEUE* queue)，可以將車輛信息顯示并將車入庫。圖4.2同樣的車庫信息、汽車離開、退出系統(tǒng)也通過調(diào)用各自的函數(shù)來實現(xiàn)的，分別為void

16、park_imformation(STACK* stack,QUEUE*queue)void car_gone(STACK*stack,QUEUE*queue)void quittosave(STACK*stack,QUEUE*queue)圖4.3圖4.4操作完成后保存信息并安全的退出系統(tǒng)。圖4.55.致感學校為我們配備了專門的實驗室，讓我們有更好的學習環(huán)境，能更專心的學習；感老師辛勤的工作，耐心的為我們講解，讓我們能更好的理解知識、應用知識；感我的同學們，在我編寫遇到困難時，是他們給我的講解，是我克服了困難，把程序編的跟好；感父母，他們給了我精神和物質(zhì)上的支持，使我向著自己的目標不斷努力，不

17、斷前進，不斷創(chuàng)新。簽名：鄧小祥日期：2011-1-11參考文獻1嚴蔚敏 吳偉民 著， 數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學，2007.42Richard F.Gilberg Behrouz A.Forouzan, Data Structures A Pseudocode Approach with C，second edition, Thomson, 2005.13春葆 著，數(shù)據(jù)結(jié)構(gòu)教程，清華大學，2005.14. C程序設計經(jīng)典教程，美Deitel,H.M.，美Deitel,P.J.著，清華大學，20065. 鑫.VC+深入詳解.：電子工業(yè)：20076錢能.C+程序設計教程.：清華大學:2009附

18、錄Main:#include<stdio.h>#include"StackADT.h"#include"QueueADT.h"#include"Menu.h"#include"car_park.h"#include"car_gone.h"#include"park_imformatiom.h"#include"Beginsystem.h"#include"QuittoSave.h"int main()STACK* parkl

19、ot;QUEUE* road;char z;parklot=creatStack();road=createQueue();beginsystem(parklot,road);while(1)menu();z=getchar();fflush(stdin);if(z='q')quittosave(parklot,road);break;switch(z)case 'p': car_park(parklot,road);break;case 'g': car_gone(parklot,road);break;case 'i': pa

20、rk_imformation(parklot,road);break;default: printf("enter the right order.n");break;printf("any key to continue.n");getchar();fflush(stdin);system("cls");return 0;調(diào)用函數(shù)：堆棧、隊列操作：STACK* creatStack (void)STACK* stack;stack = (STACK*) malloc( sizeof (STACK);if (stack) stack-

21、>count = 0; stack->top = NULL;return stack;bool pushStack (STACK* stack, void* dataInPtr)STACK_NODE* newPtr;newPtr = (STACK_NODE* ) malloc(sizeof( STACK_NODE);if (!newPtr) return false;newPtr->dataPtr = dataInPtr; newPtr->link = stack->top; stack->top = newPtr; (stack->count)+;

22、return true;void* popStack (STACK* stack) void* dataOutPtr; STACK_NODE* temp;if (stack->count = 0) dataOutPtr = NULL;else temp = stack->top; dataOutPtr = stack->top->dataPtr; stack->top = stack->top->link; free (temp); (stack->count)-; return dataOutPtr;bool fullStack (STACK*

23、 stack) STACK_NODE* temp;if (temp = (STACK_NODE*)malloc (sizeof(*(stack->top) && stack->count<2) free (temp); return false;return true;bool emptyStack (STACK* stack) return (stack->count = 0);STACK* destoryStack (STACK* stack) STACK_NODE* temp;if (stack) while (stack->top != N

24、ULL) free (stack->top->dataPtr); temp = stack->top; stack->top = stack->top->link; free (temp); free (stack);return NULL;QUEUE* createQueue (void)QUEUE* queue;queue = (QUEUE*) malloc (sizeof (QUEUE);if (queue) queue->front = NULL; queue->rear = NULL; queue->count = 0; retu

25、rn queue;bool enqueue (QUEUE* queue, void* itemPtr)QUEUE_NODE* newPtr;if (!(newPtr = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE) return false;newPtr->dataPtr = itemPtr; newPtr->next = NULL; if (queue->count = 0) queue->front = newPtr;else queue->rear->next = newPtr; (queue->count)+;q

26、ueue->rear = newPtr;return true;void* dequeue (QUEUE* queue) void* dataOutPtr;QUEUE_NODE* deleteLoc;if (queue->count=0) dataOutPtr = NULL; dataOutPtr = queue->front->dataPtr;deleteLoc = queue->front;if (queue->count = 1) queue->rear = queue->front = NULL;else queue->front

27、= queue->front->next;(queue->count)-;free (deleteLoc);return dataOutPtr;bool fullQueue (QUEUE* queue) QUEUE_NODE* temp;if (temp = (QUEUE_NODE*)malloc(sizeof(*(queue->rear) && queue->count<5) free (temp); return false; return true;bool emptyQueue (QUEUE* queue) return (queue

28、->count = 0);#ifndef _STDBOOL_H_#define _STDBOOL_H_#define _bool_true_false_are_defined 1#ifndef _cplusplus#define false 0#define true 1#define bool _Bool#if _STDC_VERSION_ < 199901L && _GNUC_ < 3typedef int _Bool;#endif#endif /* !_cplusplus */#endif /* !_STDBOOL_H_ */應用函數(shù)：void menu

29、(void)printf("tt|-|n");printf("tt|<p> park car <g> get car |n");printf("tt|<i> park imformation<q> quit to out |n");printf("tt|-|n");printf("tt(cost one hour: small car is 1 yuan,middlen tt caris 2 yuan,big car is 3 yuan.)n");

30、printf("ttyou want:");void beginsystem(STACK*stack,QUEUE*queue)CAR* temp;FILE* fp;fp=fopen("DATA.dat","r");if(fp!=NULL)fseek(fp,0,SEEK_SET);while(1)temp=(CAR*)malloc(sizeof(CAR);temp->number=-1;fread(temp,sizeof(CAR),1,fp);if(temp->number=-1)break;else if(!fullSta

31、ck(stack)pushStack(stack,temp);elseenqueue(queue,temp);fclose(fp);fp=fopen("DATA.dat","w");fclose(fp);free(temp);void car_park(STACK*stack,QUEUE* queue)CAR* car;car=(CAR*)malloc(sizeof(CAR);car->place='a'printf("car number:");scanf("%d",&car->

32、;number);fflush(stdin);printf("car's in time:");scanf("%d",&car->time);fflush(stdin);printf("car's size(ssmall/mmiddle/llarge?):");while(1)car->size=getchar();fflush(stdin);if(car->size='s'|car->size='m'|car->size='l')b

33、reak;printf("enter the right car's size(ssmall/mmiddle/llarge?):");if(!fullStack(stack)printf("the car has been paked and count the time for pay.n now the time is %d.n",car->time);pushStack(stack,car);else if(!fullQueue(queue)printf("the parklot is full,your car park

34、in the road.n here you pay for not.n");enqueue(queue, car);elseprintf("there is no more parking lot.n");void car_gone(STACK*stack,QUEUE*queue)STACK* changestack;QUEUE* changequeue;CAR* carout;CAR* changecar;int number;int time;int found=0;int count;changestack=creatStack();changequeue

35、=createQueue();if(!emptyStack(stack) | !emptyQueue(queue)printf("Enter the outcar number:");scanf("%d",&number);fflush(stdin);printf("Enter the outcar time:");scanf("%d",&time);fflush(stdin);while(!emptyStack(stack)carout=(CAR*)popStack(stack);if(carou

36、t->number=number)found=1;break;pushStack(changestack,carout);while(!emptyStack(changestack)changecar=(CAR*)popStack(changestack);pushStack(stack,changecar);if(found=1)switch(carout->size)case 's':printf("this parking cost %d hour(s),you should pay %d yuan for it.n",time-carou

37、t->time,1*(time-carout->time);break;case 'm':printf("this parking cost %d hour(s),you should pay %d yuan for it.n",time-carout->time,2*(time-carout->time);break;case 'l':printf("this parking cost %d hour(s),you should pay %d yuan for it.n",time-carout-

38、>time,3*(time-carout->time);break;default:break;if(!emptyQueue(queue)changecar=(CAR*)dequeue(queue);printf("The car %d in the road have been parking.n",changecar->number);pushStack(stack,changecar);else count=queue->count;while(!emptyQueue(queue)changecar=(CAR*)dequeue(queue);i

39、f(changecar->number=number)printf("Car is not in the parklot,you pay for not.n");elseenqueue(changequeue,changecar);while(!emptyQueue(changequeue)changecar=(CAR*)dequeue(changequeue);enqueue(queue,changecar);if(queue->count=count)printf("can not find this car,or the parklot is e

40、mpty .n please check your car number.n");free(changestack);free(changequeue);void park_imformation(STACK* stack,QUEUE*queue)STACK_NODE* temp1;QUEUE_NODE* temp2;CAR* temp3;if(!emptyStack(stack)if(!fullStack (stack)printf("there is %d cars in the park lot,%d for car to park.n",stack->count,10-stack->count);else if(fullStack (stack)&am