數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告組長(zhǎng)：陳楠201158504141 計(jì)114-1分?jǐn)?shù)：模塊1：設(shè)計(jì)與實(shí)現(xiàn) 模塊2：分析與討論模塊3： 測(cè)試組員2 潘長(zhǎng)志201158504133 計(jì)114-1分?jǐn)?shù)：模塊1：測(cè)試模塊2：設(shè)計(jì)與實(shí)現(xiàn)模塊3：分析與討論組員3：姜新新 201158504139 計(jì)114-1分?jǐn)?shù)：模塊1：分析與討論模塊2：測(cè)試模塊3：設(shè)計(jì)與實(shí)現(xiàn)2013年6月30日設(shè)計(jì)題目：煙臺(tái)公交系統(tǒng)題目簡(jiǎn)介：1. 題目?jī)?nèi)容： 煙臺(tái)公交系統(tǒng)包含*路公共汽車，覆蓋*站點(diǎn)，承載著煙臺(tái)6個(gè)區(qū)的交通。本系統(tǒng)以煙臺(tái)公交系統(tǒng)的6路為樣例，建立一套煙臺(tái)公交查詢系統(tǒng)，涵蓋三個(gè)功能模塊：線路信息查詢模塊、站點(diǎn)信息查詢

2、模塊、站到站信息查詢模塊。模塊1一、 線路信息查詢模塊（模塊1）的設(shè)計(jì)（分工：陳楠（設(shè)計(jì)與實(shí)現(xiàn)討論），盤長(zhǎng)治（設(shè)計(jì)分析），姜新新（測(cè)試）1. 模塊內(nèi)容：本模塊實(shí)現(xiàn)查詢各個(gè)線路的信息，包括：線路查詢、站點(diǎn)信息詢、站站查詢、最優(yōu)路線查詢。2. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)a) 本模塊每個(gè)站點(diǎn)的用BusStop類型表示struct BusStop char station20;char personnum20; typedef struct Node BusStop data; struct Node *next; LNode,*LinkedList;b) 用line表示每條線路typedef struct Lin

3、e char Name20;LNode *LineName;struct Line *next;LLine,*LLined;typedef struct Stack BusStop dataMAXSIZE; int top;SeqStack;SeqStack SeqStackInit()/構(gòu)造一個(gè)空棧SSeqStack S;S.top= -1; return S;3. 算法設(shè)計(jì)乘客查詢查詢算法void queryLine(LLined &L): ：該算法實(shí)現(xiàn)在所有路線中找到所有查找的路線，并顯示該路線信息。void queryLine(LLined &L)char linename20;cha

4、r yorn;SeqStack S;LinkedQueue Q;BusStop putout;BusStop out;bool haveon;LLined l;LinkedList link;l = (LLine*)malloc(sizeof(LLine);link = (LNode*)malloc(sizeof(LNode);l=L;S = SeqStackInit();Q = LinkedQueueInit();cout有以下線路供您查詢.endl;/*顯示有幾條線路*/while(l!=NULL) cout線路名稱:;coutNamenext;/*/coutlinename;l=L;/*

5、遍歷豎著的鏈表*/while(l!=NULL)if(strcmp(l-Name,linename)=0)link = l-LineName;/*遍歷找到的線路的各個(gè)站點(diǎn)并入隊(duì)*/while(link!=NULL)LinkedQueueIn(Q,link-data);link = link-next;haveon = true;/break;elsehaveon =false;l = l-next;if(!haveon)cout沒(méi)有您查詢的線路.Name,linename)=0)while(!LinkedQueueEmpty(Q)putout = LinkedQueueOut(Q);SeqSta

6、ckPush(S,putout);cout站點(diǎn)名稱:;coutputout.stationnext;coutyorn;if(yorn = y)cout已下為返程路線endl;while(!SeqStackEmpty(S)out=SeqStackPop(S);cout站點(diǎn)名稱:;coutout.stationendl;cout查詢完畢，請(qǐng)輸入您要進(jìn)行的下一步操作.endl二、 站點(diǎn)信息查詢模塊，查詢算法void querysinfo(LLined &L)void querysinfo(LLined &L)char stopname20;bool a;LLined l;LinkedList lin

7、k,link1;l = (LLine*)malloc(sizeof(LLine);link = (LNode*)malloc(sizeof(LNode);link1 = (LNode*)malloc(sizeof(LNode);l=L;coutstopname;while(l!=NULL)link = l-LineName;while(link!=NULL)if(strcmp(link-data.station,stopname)=0)a=true;break;elsea= false;link=link-next;l=l-next;if(a)break;if(!a)coutendl您要查詢的

8、站點(diǎn)不存在.LineName;link1 = l-LineName;link1 = link1-next;while(link!=NULL)if(strcmp(link-data.station,stopname)=0)coutendl;cout您查詢的站點(diǎn)位于:;coutName;cout號(hào)線路endl;cout此戰(zhàn)為始發(fā)站，站點(diǎn)名稱:;coutdata.stationendl;cout此站點(diǎn)上車人數(shù):;coutdata.personnumendl;coutnext!=NULL)cout下一站為:;coutnext-data.stationendl;elsecout此站點(diǎn)為終點(diǎn)站data.s

9、tation,stopname)=0)coutendl;cout您查詢的站點(diǎn)位于:;coutName;cout號(hào)線路endl;cout此站點(diǎn)名稱:;coutdata.stationendl;cout此站點(diǎn)上車人數(shù):;coutdata.personnumendl;cout此站點(diǎn)前一站站點(diǎn)名稱:;coutdata.stationnext!=NULL)cout此站點(diǎn)后一站站點(diǎn)名稱:;coutnext-data.stationendl;elsecout此站點(diǎn)為終點(diǎn)站next;link1 = link1-next;if(link1=NULL)break;l = l-next;3 站站查詢void que

10、rytwo(LLined &L)char one20;char two20;bool a;bool b;LLined l1,l2;LinkedList link1,link2,link3;l1= (LLine*)malloc(sizeof(LLine);l2= (LLine*)malloc(sizeof(LLine);link1 = (LNode*)malloc(sizeof(LNode);link2 = (LNode*)malloc(sizeof(LNode);link3 = (LNode*)malloc(sizeof(LNode);l1=L;coutone;while(l1!=NULL)l

11、ink1 = l1-LineName;while(link1!=NULL)if(strcmp(link1-data.station,one)=0)a=true;break;elsea=false;link1 = link1-next;if(a)break;l1 = l1-next;if(!a)cout您要查找的第一個(gè)站點(diǎn)不存在.endl;return;couttwo;l1 = L;while(l1!=NULL)link1 = l1-LineName;while(link1!=NULL)if(strcmp(link1-data.station,two)=0)b=true;break;elseb=

12、false;link1 = link1-next;l1 = l1-next;if(b)break;if(!b)cout您要查找的第二個(gè)站點(diǎn)不存在.LineName;while(link1!=NULL)if(strcmp(link1-data.station,one)=0)link2 = link1;while(link2!=NULL)if(strcmp(link2-data.station,two)=0)l2 = l1;cout線路名稱:;coutNamedata.station,two)!=0)cout站點(diǎn)名稱:;coutdata.stationnext;cout站點(diǎn)名稱:;coutdata

13、.stationnext;link1 = link1-next;l1 = l1-next;cout查詢完畢，請(qǐng)輸入您要進(jìn)行的下一步操作.endl;void querybest(LLined &L)char name 10020;char one20;char two20;int index = -1;int i = 100;int j = 0;bool a;bool b;LLined l1,l2;LinkedList link1,link2,link3;l1= (LLine*)malloc(sizeof(LLine);l2= (LLine*)malloc(sizeof(LLine);link1

14、 = (LNode*)malloc(sizeof(LNode);link2 = (LNode*)malloc(sizeof(LNode);link3 = (LNode*)malloc(sizeof(LNode);l1=L;coutone;while(l1!=NULL)link1 = l1-LineName;while(link1!=NULL)if(strcmp(link1-data.station,one)=0)a=true;break;elsea=false;link1 = link1-next;if(a)break;l1 = l1-next;if(!a)cout您要查找的第一個(gè)站點(diǎn)不存在.

15、endl;return;couttwo;l1 = L;while(l1!=NULL)link1 = l1-LineName;while(link1!=NULL)if(strcmp(link1-data.station,two)=0)b=true;break;elseb=false;link1 = link1-next;l1 = l1-next;if(b)break;if(!b)cout您要查找的第二個(gè)站點(diǎn)不存在.LineName;while(link1!=NULL)if(strcmp(link1-data.station,one)=0)link2 = link1;while(link2!=NU

16、LL)index+;if(strcmp(link2-data.station,two)=0)if(index Name);index = -1;break;if(index = i)j+;strcpy(namej,l1-Name);index = -1;break;/iflink2 = link2-next;/while/iflink1 = link1-next;/whilel1 = l1-next;/whileLLined l3;LinkedList link4;l3 = (LLine*)malloc(sizeof(LLine);link4 = (LNode*)malloc(sizeof(L

17、Node);l3=L;int o = 0;while(l3!=NULL)while(strcmp(l3-Name,nameo)=0)cout您可選擇最優(yōu)路線號(hào)為:;coutnameoendl;cout此路線經(jīng)過(guò)的各個(gè)站點(diǎn)為:LineName;while(link4!=NULL)cout站點(diǎn)名稱:;coutdata.stationnext;o+;l3 = l3-next;cout查詢完畢，請(qǐng)輸入您要進(jìn)行的下一步操作.endl;4.最優(yōu)線路查詢void querybest(LLined &L)char name 10020;char one20;char two20;int index = -1;

18、int i = 100;int j = 0;bool a;bool b;LLined l1,l2;LinkedList link1,link2,link3;l1= (LLine*)malloc(sizeof(LLine);l2= (LLine*)malloc(sizeof(LLine);link1 = (LNode*)malloc(sizeof(LNode);link2 = (LNode*)malloc(sizeof(LNode);link3 = (LNode*)malloc(sizeof(LNode);l1=L;coutone;while(l1!=NULL)link1 = l1-LineNa

19、me;while(link1!=NULL)if(strcmp(link1-data.station,one)=0)a=true;break;elsea=false;link1 = link1-next;if(a)break;l1 = l1-next;if(!a)cout您要查找的第一個(gè)站點(diǎn)不存在.endl;return;couttwo;l1 = L;while(l1!=NULL)link1 = l1-LineName;while(link1!=NULL)if(strcmp(link1-data.station,two)=0)b=true;break;elseb=false;link1 = li

20、nk1-next;l1 = l1-next;if(b)break;if(!b)cout您要查找的第二個(gè)站點(diǎn)不存在.LineName;while(link1!=NULL)if(strcmp(link1-data.station,one)=0)link2 = link1;while(link2!=NULL)index+;if(strcmp(link2-data.station,two)=0)if(index Name);index = -1;break;if(index = i)j+;strcpy(namej,l1-Name);index = -1;break;/iflink2 = link2-n

21、ext;/while/iflink1 = link1-next;/whilel1 = l1-next;/whileLLined l3;LinkedList link4;l3 = (LLine*)malloc(sizeof(LLine);link4 = (LNode*)malloc(sizeof(LNode);l3=L;int o = 0;while(l3!=NULL)while(strcmp(l3-Name,nameo)=0)cout您可選擇最優(yōu)路線號(hào)為:;coutnameoendl;cout此路線經(jīng)過(guò)的各個(gè)站點(diǎn)為:LineName;while(link4!=NULL)cout站點(diǎn)名稱:;co

22、utdata.stationnext;o+;l3 = l3-next;cout查詢完畢，請(qǐng)輸入您要進(jìn)行的下一步操作.endl;三、 線路信息查詢模塊（模塊1）的運(yùn)行與測(cè)試a) 測(cè)試方案和數(shù)據(jù)：本測(cè)試針對(duì)線路信息輸入分別為存在的線路、不存在的線路以及字符性的情形進(jìn)行測(cè)試。b) 測(cè)試結(jié)果：i. 當(dāng)輸入存在線路17，109時(shí)，均能正確顯示各站點(diǎn)信息。ii. 當(dāng)輸入不存在線路100時(shí)，顯示“沒(méi)有該線路”提示信息，且能正確返回查詢界面。iii. 當(dāng)輸入字符數(shù)據(jù)“十七路”，程序無(wú)法進(jìn)行下去。iv. 在最有線路查詢時(shí)不支持返程線路四、 分析與討論1. 測(cè)試結(jié)果分析本模塊實(shí)現(xiàn)了線路信息的查詢，但是對(duì)輸入為字符

23、數(shù)據(jù)美歐進(jìn)行處理。2. 對(duì)于題目所使用的數(shù)據(jù)結(jié)構(gòu)與算法進(jìn)行評(píng)價(jià)與分析，探討是否存在更多的解決途徑。該模塊所使用的數(shù)據(jù)結(jié)構(gòu)合適，站點(diǎn)結(jié)構(gòu)封裝了站點(diǎn)的全部信息，線路結(jié)構(gòu)采用了順序結(jié)構(gòu)，符合了線路信息變化不大的特點(diǎn)。模塊2 數(shù)據(jù)管理 一、1.分工：數(shù)據(jù)管理的設(shè)計(jì)（分工：潘長(zhǎng)治（設(shè)計(jì)與實(shí)現(xiàn)討論），陳楠（設(shè)計(jì)分析），姜新新（測(cè)試）2.模塊內(nèi)容：本模塊實(shí)現(xiàn)查詢數(shù)據(jù)的管理，包括：線路管理、站點(diǎn)管理、車輛管理、車輛發(fā)車表、車輛的動(dòng)態(tài)圖表。3.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)用bus表示各個(gè)站點(diǎn)的信息typedef struct Bus char station50; char startime50;Busnum; /每條線路形式

24、的車輛typedef struct BNode Busnum data; struct BNode *next; BLNode,*BLinkedList;typedef struct BLine char Name20;char sumnum3;char begin10;char end10;BLNode *LineName;struct BLine *next;BLLine,*BLLined;二、 算法實(shí)現(xiàn)用線路管理的實(shí)現(xiàn)算法：LLined LineAdd (LLined &L)來(lái)增加一條線路void LineDel (LLined &L)來(lái)刪除一條線路void changeLine(LLi

25、ned &L)來(lái)修改一條線路站點(diǎn)管理算法：void LinkedListAdd (LLined &L)增加站點(diǎn)void LinkedListDel (LLined &L)刪除站點(diǎn)void changestation(LLined &L) /修改站點(diǎn)信息車輛管理算法：void BusAdd(BLLined &L)/增加車輛void BusDel(BLLined &L)/刪除車輛void changeBus(BLLined &L)/修改車輛void queryBus(BLLined &L)/車輛查詢?nèi)?線路信息查詢模塊的運(yùn)行與測(cè)試a) 測(cè)試方案和數(shù)據(jù)：本測(cè)試針對(duì)數(shù)據(jù)管理信息輸入分別為存在的車輛、不存在的車輛進(jìn)行測(cè)試。b) 測(cè)試結(jié)果：i. 當(dāng)輸入存在車輛魯Y5601，時(shí)，魯Y13245均能正確顯示各站點(diǎn)信息。ii. 當(dāng)輸入不存在線路魯X123時(shí)，顯示“沒(méi)有該車輛”提示信息，且能正確返回查詢界面。iii. 車輛動(dòng)態(tài)圖表查詢時(shí)，當(dāng)輸入時(shí)間為11:00時(shí)能查詢出正確結(jié)果，當(dāng)輸入為11時(shí)程序報(bào)錯(cuò)四、 分析與討論3. 測(cè)試分析基本能實(shí)現(xiàn)數(shù)據(jù)管理的要求，有些細(xì)節(jié)有待改善4. 對(duì)于題目所使用的數(shù)據(jù)結(jié)構(gòu)與算法進(jìn)行評(píng)價(jià)與分析，探討是否存在更多的解決途徑。該模塊所使用的數(shù)據(jù)結(jié)構(gòu)合適，站點(diǎn)結(jié)構(gòu)封裝了站點(diǎn)的全部信息，數(shù)據(jù)管理使用的鏈表的查詢。 模塊3 數(shù)據(jù)統(tǒng)計(jì)一、1.線路信息查詢模塊（模塊1）的設(shè)計(jì)（分工：