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

1、目 錄1、 設(shè)計目的22、 設(shè)計內(nèi)容21. 題目 22. 問題描述23. 基本要求24. 實現(xiàn)提示23、 算法思想分析34、 算法描述與實現(xiàn)41.數(shù)據(jù)結(jié)構(gòu)類型定義 42.主要算法的流程圖及系統(tǒng)模塊劃分63.功能描述 74.程序代碼 85、 測試結(jié)果 176、 總結(jié)體會 201、 設(shè)計目的數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的核心課程，是一門實踐性很強的課程。為了學(xué)好這門課程，必須在掌握理論知識的同時，加強上機實踐。課程設(shè)計是加強學(xué)生實踐能力的一個強有力手段，要求學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫、將算法轉(zhuǎn)換成程序并上機調(diào)試的基本方法，還要求學(xué)生在完成程序設(shè)計的同時能夠?qū)懗霰容^規(guī)范的設(shè)計報告。本課程設(shè)計的目的就

2、是要達到理論與實際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)學(xué)生的基本程序設(shè)計素養(yǎng)和軟件工作者工作作風。2、 設(shè)計內(nèi)容1.題目：模擬停車場管理問題2.問題描述：設(shè)停車場只有一個可停放幾輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場按車輛到來的先后順序依次排列，若車場內(nèi)已停滿幾輛汽車，則后來的汽車只能在門外的便道上等候，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車即可進入；當停車場內(nèi)某輛車要離開時，由于停車場是狹長的通道，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門后，為它讓路的車輛在按原次序進入

3、車場。每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。3.基本要求：試為停車場編制按上述要求進行管理的模擬程序。在這里假設(shè)汽車不能從便道上開走。試設(shè)計一個停車場管理程序。4.實現(xiàn)提示：以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，例如：(a,1,5)表示一號牌照車在5這個時刻到達，而(d,5,20)表示5號牌照車在20這個時刻離去，整個程序可以在輸入信息為(e,0,0)時結(jié)束。對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內(nèi)或

4、便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表實現(xiàn)。需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車。3、 算法思想分析1. 輸入 根據(jù)提示輸入停車場容量n。2. 創(chuàng)建 根據(jù)讀入的停車場容量n，創(chuàng)建長度為n的棧（停車場）。3. 主要操作1）插入（車輛停入） 根據(jù)提示往棧中插入元素（車輛信息），即使車輛停在停車場中。首先檢查停車場是否已滿，若不滿，則車輛停放在停車場中，記錄車輛到達時間，并把此時間作為開始計費時間。若插入的元素個數(shù)超過停車場的容量，則此后的車輛停在便道上用隊列表示，即元素儲存在隊

5、列中。2）刪除（車輛離開） 根據(jù)提示刪除棧中的元素（車輛信息），即使車輛離開停車場，同時停在便道上的車輛停入停車場中。當車輛離開時，首先要尋找到要離開車輛的車牌號，若車是從停車場離開，則在它之后進入的車輛必須先退出(進入臨時棧)為它讓路，待該輛車開出大門外，其它車輛再按原次序進入停車場，并將停放在便道上第一位置的車開進停車場，離開的車輛按其在停車場內(nèi)停留的時間交費，并把離開車輛的離開時間作為便道上第一位置的車進入停車場的進入時間和開始計費時間。3） 顯示 根據(jù)提示操作，顯示當前停車場和便道使用情況。4） 退出 釋放停車場和便道（棧和隊列）上的車輛信息等，退出當前運行程序。4、 算法描述與實現(xiàn)1

6、.數(shù)據(jù)結(jié)構(gòu)類型定義/停車場車輛信息(存儲結(jié)構(gòu))typedef struct carinfor / 車輛信息 char szregmark64; / 車牌號 char szarrtime16; / 到達時間 char szenttime16; / 進入停車場(開始計費)時間 char szdeptime16; / 離開時間 tcarinfor, *lptcarinfor;szregmark64/車牌號szarrtime16/到達時間szenttime16/計費時間szdeptime16/離開時間carinfor停車場車輛信息存儲結(jié)構(gòu)/棧carstack存儲結(jié)構(gòu)typedef struct car

7、stack lptcarinfor lpcarinfor; / 車輛信息 int ntop; / 棧頂元素下標 int nstacksize; / 棧容量 tcarstack, *lptcarstack;棧頂元素下標 ntop停車場carstack(棧)存儲結(jié)構(gòu)lpcarinfornstacksize=ntop+1/便道車輛信息(存儲結(jié)構(gòu))typedef struct carnode / 鏈隊結(jié)點信息 tcarinfor carinfo; / 車輛信息 struct carnode *lpnext; / 指向下一個元素的指針 tcarnode, *lptcarnode;szregmark64/

8、車牌號szarrtime16/到達時間szenttime16/計費時間szdeptime16/離開時間carinfor便道車輛信息存儲結(jié)構(gòu)/ 鏈隊carqueue存儲結(jié)構(gòu)typedef struct carqueue lptcarnode lphead; / 頭結(jié)點 lptcarnode lprear; / 指向當前隊尾的指針 int neffsize; / 當前隊中元素個數(shù)(有效車位) tcarqueue, *lptcarqueue;lptcarnode lprear便道carsqueue(隊列)存儲結(jié)構(gòu)lptcarnode lpheadlpcarinfornext 程序運行界面 輸入停車場

9、容量，創(chuàng)建棧開 始根據(jù)當前提示操作取得key值向?；蜿犃屑尤朐匦畔⑾驐；蜿犃袆h除元素信息顯示棧和隊列的停車情況退出程序e、釋放空間ado2. 主要算法的流程圖及功能描述（1）流程圖：（2）系統(tǒng)模塊劃分：車進入停車場判斷停車場是否已滿車進入停車場記錄時間開始計費車輛離開記錄離開時間計算持續(xù)時間和費用否是進入便道記錄進入時間但不計費判斷停車場是否有空位否繼續(xù)等待是（3）算法描述：（1） void initstack( lptcarstack &lpcarstack, int nsize ) 初始化棧 lpcarstack,，為棧和車輛信息分配儲存空間，將其容量設(shè)置為 nsize。 int ini

10、tqueue( lptcarqueue &lpcarqueue ) 初始化鏈隊 lpcarqueue，分配隊列存儲空間和頭結(jié)點空間，有效車位初始化。（2） void push( lptcarstack &lpcarstack, tcarinfor carinfo ) 向棧中加入元素信息：車輛信息 carinfo 入棧 lpcarstack，棧頂元素下標+1。 int enqueue( lptcarqueue &lpcarqueue, tcarinfor carinfo ) 向隊列中加入元素信息：分配結(jié)點空間，車輛信息 carinfo 入隊 lpcarqueue，順序存儲到隊列中，有效車位加1。

11、（3） void pop( lptcarstack &lpcarstack, tcarinfor &carinfo ) 從棧中刪除元素時：車輛信息從棧 lpcarstack 中彈出并存入 carinfo中，棧頂元素下標-1。 int dequeue( lptcarqueue &lpcarqueue, tcarinfor &carinfo ) 從隊列中刪除元素時：隊頭元素從鏈隊 lpcarqueue 中出隊并存入 carinfo，當隊列中無元素時，返回error；否則carinfo中信息存入臨時隊列中，再釋放臨時隊列，隊列長度減1。（4） int main( void ) 主函數(shù)：主要設(shè)計一個分

12、支語句，讓用戶根據(jù)提示選擇要執(zhí)行的操作，實現(xiàn)所需要的功能。3. 程序代碼#include /getch(void)#include /內(nèi)存分配 #include #include #include #define ok 1#define error 0#define overflow -1#define clearscreen() system( cls ) / 清空當前屏幕/ 顯示字符串 szprompt 并等待用戶按下任意鍵#define pause(szprompt) printf( %s,szprompt),getch()/停車場車輛信息(存儲結(jié)構(gòu))typedef struct car

13、infor / 車輛信息 char szregmark64; / 車牌號 char szarrtime16; / 到達時間 char szenttime16; / 進入停車場(開始計費)時間 char szdeptime16; / 離開時間 tcarinfor, *lptcarinfor;/棧carstack存儲結(jié)構(gòu)typedef struct carstack lptcarinfor lpcarinfor; / 車輛信息 int ntop; / 棧頂元素下標 int nstacksize; / 棧容量 tcarstack, *lptcarstack;/ 初始化棧 lpcarstack, 將其

14、容量設(shè)置為 nsizevoid initstack( lptcarstack &lpcarstack, int nsize ) lpcarstack = ( lptcarstack ) malloc( sizeof ( tcarstack ) ); /棧儲存分配 lpcarstack-lpcarinfor = ( lptcarinfor ) malloc( nsize * sizeof ( tcarinfor ); /棧中車輛信息儲存分配 lpcarstack-ntop = -1; /棧中無元素 lpcarstack-nstacksize = nsize; /棧的長度為nsize/ 車輛信息

15、carinfo 入棧 lpcarstackvoid push( lptcarstack &lpcarstack, tcarinfor carinfo ) lpcarstack-ntop+; /棧頂元素下標+1 lpcarstack-lpcarinfor lpcarstack-ntop = carinfo; /把carinfo存入棧中/ 車輛信息從棧 lpcarstack 中彈出并存入 carinfovoid pop( lptcarstack &lpcarstack, tcarinfor &carinfo ) carinfo = lpcarstack-lpcarinfor lpcarstack-

16、ntop; /把棧中元素存入carinfo中 lpcarstack-ntop-; /棧頂元素下標減1/ 若棧 lpcarstack 空,返回 true;否則,返回 falsebool isstackempty( lptcarstack lpcarstack ) return lpcarstack-ntop = -1;/棧空時返回棧頂下標ntop值為-1/ 若棧 lpstackfull 滿,返回 true;否則,返回 falsebool isstackfull( lptcarstack lpcarstack )/棧滿返回ntop值為棧長度減1 return lpcarstack-ntop = (

17、 lpcarstack-nstacksize - 1 ); / 銷毀棧 lpcarstack,將指針 lpcarstack 置為 nullvoid destroystack( lptcarstack &lpcarstack ) free( lpcarstack-lpcarinfor ); /釋放車輛信息存儲空間 free( lpcarstack ); /釋放棧的存儲空間 lpcarstack = null; /把棧lpcarstack置空/便道車輛信息(存儲結(jié)構(gòu))typedef struct carnode / 鏈隊結(jié)點信息 tcarinfor carinfo; / 車輛信息 struct c

18、arnode *lpnext; / 指向下一個元素的指針 tcarnode, *lptcarnode;/ 鏈隊carqueue存儲結(jié)構(gòu)typedef struct carqueue lptcarnode lphead; / 頭結(jié)點 lptcarnode lprear; / 指向當前隊尾的指針 int neffsize; / 當前隊中元素個數(shù)(有效車位) tcarqueue, *lptcarqueue;/ 初始化鏈隊 lpcarqueueint initqueue( lptcarqueue &lpcarqueue ) lpcarqueue = ( lptcarqueue ) malloc( si

19、zeof( tcarqueue ) ); /分配對列存儲空間 lpcarqueue-lphead =lpcarqueue-lprear=( lptcarnode) malloc( sizeof( tcarnode ) ); /分配頭結(jié)點空間 if(!lpcarqueue-lphead) exit(overflow); /分配儲存失敗 lpcarqueue-lphead-lpnext = null; lpcarqueue-neffsize = 0; return ok;/ 車輛信息 carinfo 入隊 lpcarqueueint enqueue( lptcarqueue &lpcarqueue

20、, tcarinfor carinfo )/插入元素carinfo為隊lpcarqueue的新的隊尾元素 lptcarnode lpcarnode = ( lptcarnode ) malloc( sizeof( carnode ) ); /分配結(jié)點空間 if(!lpcarnode) exit(overflow); /分配儲存失敗 lpcarnode-carinfo = carinfo; lpcarnode-lpnext = null; lpcarqueue-lprear-lpnext = lpcarnode; lpcarqueue-lprear = lpcarnode; lpcarqueue

21、-neffsize+; return ok;/ 隊頭元素從鏈隊 lpcarqueue 中出隊并存入 carinfoint dequeue( lptcarqueue &lpcarqueue, tcarinfor &carinfo ) if(lpcarqueue-lphead=lpcarqueue-lprear) return error; /隊列里沒有元素，返回error lptcarnode lptemp = lpcarqueue-lphead-lpnext; carinfo = lptemp-carinfo; lpcarqueue-lphead-lpnext = lptemp-lpnext;

22、 /指向下一結(jié)點 if(lpcarqueue-lprear=lptemp) lpcarqueue-lphead=lpcarqueue-lprear; /如果隊列尾指針指向臨時結(jié)點時，隊列中沒有元素 free( lptemp ); /釋放臨時隊列 lpcarqueue-neffsize-; /容量-1 return ok;/ 若鏈隊 lpcarqueue 為空,返回 true;否則,返回 falsebool isqueueempty( lptcarqueue lpcarqueue ) return lpcarqueue-neffsize = 0; /鏈隊為空時返回長度為0/ 銷毀鏈隊 lpcar

23、queuevoid destroyqueue( lptcarqueue &lpcarqueue ) lptcarnode lpnextcarnode = null; for ( lptcarnode lpcarnode = lpcarqueue-lphead; lpcarnode != null; lpcarnode = lpnextcarnode ) lpnextcarnode = lpcarnode-lpnext; free( lpcarnode );/釋放結(jié)點 lpcarnode信息 free( lpcarqueue );/釋放隊列 lpcarqueue lpcarqueue = nul

24、l;/ 將字符串時間格式轉(zhuǎn)換為數(shù)字(分鐘)格式,例如 12:36 將被轉(zhuǎn)換為 756 =( 12 * 60 + 36 )int converttime ( char *lptime ) int nhour = 0; int nminu = 0; sscanf( lptime, %d:%d, &nhour, &nminu ); return nhour * 60 + nminu; / 根據(jù)在停車場內(nèi)的停留時間 ncontiminu (分鐘)計算費用double calcuexp ( int ncontiminu ) return ncontiminu * ( 5.0 / 60 );int mai

25、n( void ) int nparkcap = 0; / 停車場容量 putchar( n ); printf(tt*n); printf(tt=* *=n); printf(tt=*歡迎進入停車場管理系統(tǒng)*=n); printf(tt=* *=n); printf(tt*n); putchar( n ); printf( 請輸入停車場容量: ); scanf( %d, &nparkcap ); lptcarstack lpcarstack = null; / 停車場,用棧模擬 initstack( lpcarstack, nparkcap );/創(chuàng)建停車場 lptcarqueue lpca

26、rqueue = null; / 便道,用鏈隊模擬 initqueue( lpcarqueue ); /創(chuàng)建隊列 char comtype = null; / 命令類型 char szuserinput128 = null ; / 用戶輸入 do clearscreen(); putchar( n ); puts( - ); puts( 命令類型 ); puts( a - 車輛到達 ); puts( d - 車輛離開 ); puts( o - 顯示當前停車場和便道使用情況 ); puts( e - 退出程序 ); putchar( n ); puts( 例: ); puts( a,t45,14

27、:26 ); puts( d,e32,16:51 ); puts( e ); puts( o ); putchar( n ); printf( 請輸入命令: ); scanf( %s, szuserinput ); puts( - ); char szcarinfor 128 = null ; sscanf( szuserinput, / 將命令類型與車輛信息分開存放 %c,%s, &comtype, / 用戶輸入的前半部分,即命令類型 szcarinfor / 用戶輸入的后半部分,即車輛信息 );/sscanf()從一個字符串中讀進與指定格式相符的數(shù)據(jù). char *lpcomloc = n

28、ull; / 車輛信息字符串中的逗號位置 for ( lpcomloc = szcarinfor; *lpcomloc != 0; lpcomloc+ ) if ( *lpcomloc = , ) break;/跳出整個for循環(huán) *lpcomloc = 0; tcarinfor carinfo = null ; / 存儲本次用戶輸入的車輛信息 strcpy( carinfo.szregmark, szcarinfor );/把szcarinfor復(fù)制到carinfo.szregmark(車牌號)里 if (comtype = a )/車輛到達 strcpy( carinfo.szarrtim

29、e, lpcomloc + 1 );/把lpcomloc + 1復(fù)制到carinfo.szarrtime里 if ( false = isstackfull( lpcarstack ) )/判斷棧lpcarstack不滿時 strcpy( carinfo.szenttime, carinfo.szarrtime );/車輛到達時間szarrtime復(fù)制給開始收費時間szenttime push( lpcarstack, carinfo ); printf( 已進入停車場第 %d 個車位n,lpcarstack-ntop + 1); printf( 車牌號:tt%sn, carinfo.szre

30、gmark ); printf( 進入時間:t%sn, carinfo.szenttime ); puts( 是否收費:t是 ); else enqueue( lpcarqueue, carinfo );printf( 停車場已滿,已停放在便道的第 %d 個車位n,lpcarqueue-neffsize); printf( 車牌號:tt%sn, carinfo.szregmark ); printf( 停放時間:t%sn, carinfo.szarrtime ); puts( 是否收費:t否 ); else if (comtype = d ) strcpy( carinfo.szdeptime

31、, lpcomloc + 1 ); lptcarstack lptempcarstack = null; initstack( lptempcarstack, nparkcap );/ 創(chuàng)建臨時lptempcarstack，nparkcap（停車輛） tcarinfor carinfoout = null ; bool biscarfound = false; /初始化biscarfound while ( false = isstackempty( lpcarstack ) )/判斷棧lpcarstack不為空時 pop( lpcarstack, carinfoout ); /車輛出棧lpc

32、arstack if ( 0 != strcmp( carinfoout.szregmark, carinfo.szregmark ) )/比較 push( lptempcarstack, carinfoout );/車輛進棧lptempcarstack else biscarfound = true; break; while ( false = isstackempty( lptempcarstack ) )/判斷臨時棧不為空時 tcarinfor tempcarinfo = null ; pop( lptempcarstack, tempcarinfo ); push( lpcarsta

33、ck, tempcarinfo ); if ( false = biscarfound ) printf( 車牌號為 %s 的車未進入停車場.n, carinfo.szregmark ); pause( -n按任意鍵輸入下一條信息.n ); continue; strcpy( carinfoout.szdeptime, carinfo.szdeptime ); int nenttime = converttime ( carinfoout.szenttime ); int ndeptime = converttime ( carinfoout.szdeptime ); int ncontimi

34、nu = ndeptime - nenttime; printf( 計費時段:t%s - %s (共 %d 分鐘)n, carinfoout.szenttime, /開始計費時間 carinfoout.szdeptime, /車輛離開時間 ncontiminu /持續(xù)時間 ); double rexpense = calcuexp ( ncontiminu ); /計算停車費 printf( 應(yīng)交納的費用:t%.1lf 元n, rexpense ); if ( false = isqueueempty( lpcarqueue ) ) /如果隊列l(wèi)pcarqueue不空時 tcarinfor t

35、empcarinfo = null ; dequeue( lpcarqueue, tempcarinfo ); strcpy( tempcarinfo.szenttime, carinfoout.szdeptime ); push( lpcarstack, tempcarinfo ); puts( - ); printf( 停放在便道的第 1 個車位,車牌號為 %s 的車已進入停車場n, tempcarinfo.szregmark); else if (comtype = o ) clearscreen(); putchar( n ); puts( 停車場使用情況n ); puts( 車位t車牌號t到達時間t進入(開始計費)時間n); for ( int i = 0; i ntop; i+ ) printf( %dt%stt%stt%sn, i + 1, /車位 lpcarstack-lpcarinfor i.szregmark, /車牌號 lpcarstack-lpcarinfor i.szarrtime, /車輛到達時間 lpcarstack-lpcarinfor i.szenttime /車輛進停車場時間 ); /顯示停車場車輛信息 putchar( n ); putchar( n ); putchar( n ); puts( 便道使用情況n