交通圖咨詢查詢系統(tǒng)數據結構培訓資料(共53頁)

1、信息科學與工程學院結構數據課 程 設 計 報 告課程設計名稱： 交通咨詢系統(tǒng) 專 業(yè) 班 級 ： 計算機xxx 學 生 姓 名 ： xxx 學 號 ： 2015xxxx 指 導 教 師 ： xx 課程設計時間： 2016.07.08 計算機應用技術 專業(yè)課程設計任務書學生姓名Xxx專業(yè)班級學號題 目交通咨詢系統(tǒng)課題性質A課題來源D指導教師白浩同組姓名無主要內容1. 建立交通網絡圖的存儲結構。2. 某個城市到達其余各城市的最短路徑。3. 實現兩個城市之間最短路徑的問題。4. 主要目的是給用戶提供路徑咨詢任務要求5. 根據需求分析給出概要設計，本系統(tǒng)包括以下功能模塊：添加信息、查詢信息、刪除信息、

2、修改信息、退出和保存信息；6. 結合課題利用數據結構相關知識，利用C語言實現該系統(tǒng)的所有上述功能，要求界面友善，程序運行正常；7. 提交課程設計報告1份（具體寫作要求參考樣例），可運行的系統(tǒng)和源代碼電子版一套。參考文獻嚴蔚敏.數據結構（C語言版）.北京：清華大學出版社譚浩強.C語言程序設計.（第三版）北京：清華大學出版社審查意見指導教師簽字：xx教研室主任簽字：xx 2016 年 06 月 27 日 說明：本表由指導教師填寫，由教研室主任審核后下達給選題學生，裝訂在設計（論文）首頁填 表 說 明1“課題性質”一欄：A工程設計；B工程技術研究；C軟件工程（如CAI課題等）；D文獻型綜述；E其它。

3、2“課題來源”一欄：A自然科學基金與部、省、市級以上科研課題；B企、事業(yè)單位委托課題；C校、院（系、部）級基金課題；D自擬課題。目錄1 需求分析11.1 添加交通圖信息11.2 查詢單源最短路徑11.3 查詢多源最短路徑11.4 更新交通圖信息21.6 讀取、保存信息22 概要設計32.1 數據類型的定義32.2 功能模塊結構圖43 運行環(huán)境64 開發(fā)工具和編程語言65 詳細設計75.1 圖結構的基本操作75.1.1添加城市結點和路徑結點85.1.2修改城市結點和路徑結點85.1.3刪除城市結點和路徑結點85.1.4退出保存85.2 迪杰斯特拉算法的實現85.2.1 迪杰斯特拉算法函數85.2

4、.2 提取迪杰斯特拉函數信息85.2.3 求多源最短路徑86 程序編碼97 運行結果418 心得體會469參考文獻471 需求分析本系統(tǒng)中的數據來源于標準輸入設備（如鍵盤）和文件，可以實現對交通圖城市、城市到其余城市的距離的操作，根據需要可查詢某兩個城市之間的最短距離、城市到各城市的最短距離，各個城市到各個城市的最短距離，以及路徑。本系統(tǒng)要實現的功能有：添加城市和城市間距離，刪除城市及城市間距離，修改城市間距離，查詢城市間的最短路徑，查詢某個城市到某個城市的最短路徑。具體如下： 1.1 添加交通圖信息能錄入新數據（城市和路徑）。當錄入了重復的城市和路徑時，則提示數據錄入重復并取消錄入；當交通圖

5、中超過15個城市時，存儲空間已滿，不能再錄入新數據；錄入的新數據能按遞增的順序自動進行條目編號。1.2 查詢單源最短路徑能夠實現輸入起點城市名后，查詢出其到各個城市的最短路徑，輸出該城市到的其他所有的城市的最短路徑。1.3 查詢多源最短路徑 輸入起點城市名和終點城市名，查詢出兩個城市的最短路徑，并輸出該最短路徑。1.4 更新交通圖信息根據給定的城市名能夠修改該城市的名字?；蛘咻斎雰蓚€城市，修改一條路徑的距離。 1.5 刪除交通圖信息 根據輸入的城市名 ，刪除與該城市有關的所有路徑。輸入兩個城市可以刪除一條路徑。 1.6 讀取、保存信息能夠實現退出系統(tǒng)時把交通圖中的信息保存在一個文件中，在程序瑕

6、疵運行時能夠讀取出來。2 概要設計2.1 數據類型的定義1. 定義交通圖城市的元素類型 typedef struct _citychar name10;城市名 struct _path * firstpath；/第一個路徑 AdjList15,CityNode;2. 定義交通圖的路徑元素類型 typedef struct _pathint adjcity/鄰接點域int distance；/距離 struct _path *nextpath；/下一個路徑 PathNode,*PathPtr;3. 定義交通圖類型 typedef struct int cities;int paths; AdjL

7、ist list；Graph ;4. 全局變量PList head;typedef int PathMatrix;typedef int ShortPathTable;PathMatrix PMAX_CITIESMAX_CITIES;ShortPathTable DMAX_CITIES;2.2 功能模塊結構圖根據需求分析，為了滿足用戶的功能需求，按照軟件開發(fā)方法學中的模塊劃分原則，我將本系統(tǒng)主要劃分為如下模塊：操作交通圖信息，和查詢交通圖路徑兩大模塊。各模塊之間的關系如圖1所示。 圖 1模塊結構圖為了實現上述功能模塊，分別在順序表和單鏈表物理結構上定義了多個函數，本系統(tǒng)定義的函數和功能如下：1

8、. 數據結構部分部分 void initalize_graph(Graph *G)功能為：圖初始化，即生成一個空圖。int CreatAdjList(Graph *G)/初始化交通圖功能為：圖的創(chuàng)建，用圖存儲數據。void ADD_CITY(Graph *G)功能為：往圖G中插入一個城市結點。void ADD_PATH(Graph *G,int ori,int add,PathNode *p)功能為：往圖G中插入一個路徑結點。void DELETE_CITY(Graph *G,int city)功能為：刪除圖G中的指定的城市及其相關的路徑。void DELETE_PATH(Graph *G,i

9、nt left,int right)功能為：刪除圖G中一條指定的路徑。void UPDATE_PATH(Graph *G,int left,int right)功能為：更新圖G中的一個路徑信息 。Status SqListSearchByName(SqList *L,char *name) ;功能為：通過姓名查找順序表中,返回值為其在通訊錄中的位置 。void UPDATE_CITY(Graph *G,int city,char *name)功能為：更新圖G中的一個城市信息 。Status SqListSearchByName(SqList *L,char *phone) ;功能為：通過電話號

10、碼查找順序表中,返回值為其在通訊錄中的位置。 2.程序功能部分 void MODE_CLIENT(Graph *G)功能為：客戶端界面函數。 void MODE_ADMIN(Graph *G)功能為：管理員端界面函數。 int ReadAdjList(Graph *G)功能為：從文件中讀取交通圖。 int WriteAdjList(Graph *G) 功能為：在文件中存儲交通圖。 void menu(int i)功能為：各種的端界面打印。3.算法實現部分void ShortestPath(Graph *G,int v0)功能為：迪杰斯特拉算法，求出對V0單源最短路徑。void Print(Gr

11、aph *G,int v0)功能為：根據迪杰斯特拉算法，打印出V0單源最短路徑。void Print2(Graph *G,int v1,int v2)功能為：根據迪杰斯特拉算法，打印出V1和V2的最短路徑。void FindPath(Graph *G,int v)功能為：打印出V1到V2的經過路徑。int dis(Graph *G,int left,int right)功能為：返回指定路徑的距離。3 運行環(huán)境1. 硬件環(huán)境:PC機內存 4G；硬盤500G2. 軟件環(huán)境：操作系統(tǒng)：windows104 開發(fā)工具和編程語言開發(fā)環(huán)境：CodeBlocks 、Dev C+編程語言：C語言5 詳細設計在

12、概要設計的基礎上，對每個模塊進行內部邏輯處理部分詳細設計。下面分別列出各個模塊具體實現流程圖：5.1 圖結構的基本操作 觀察了數據對象后，我選擇用一個鄰接表用來存儲圖2信息，則數據結構的基本操作也就確定了，分別為圖的添加、刪除、更新。 圖 2 模擬交通圖添加城市結點和路徑結點 和圖的基本操作相同，只是該城市每增加一個城市結點要在弧的鄰接點對應的城市上也增加一條弧。修改城市結點和路徑結點 和圖的基本操作相同。5.1.3刪除城市結點和路徑結點 和圖的基本操作相同，只是該城市每刪除一個城市結點要在弧的鄰接點對應的城市上也刪除那條弧。退出保存 在主函數的開始部分添加Read函數，在管理員修改模式添加W

13、rite函數。實現對圖結構的讀取保存。 5.2 迪杰斯特拉算法的實現 把算法實現得到不僅僅是一系列數組，而是將這些數組的信息提煉成有用的信息輸出出來，將抽象的數據轉換為具象的信息。 5.2.1 迪杰斯特拉算法函數 定義了若干個全局輔助變量，如路徑矩陣P和距離數組D，final用來標記是否找到了點的最短路徑在函數的初始階段進行對個輔助變量的初始化，第一趟把V0相鄰的路徑距離保存下來。選擇一個最小的用final記錄下來，記錄下最終的D和P值。再遍歷其他結點，如果出現新的路徑，且路徑小于最大值INFINITY，則保存路徑和距離以便下次比較。循環(huán)n-1次得到V0到各結點的最短距離和路徑。5.2.2 提

14、取迪杰斯特拉函數信息 根據P函數與D函數，可以將V0到每個終點的經過結點和最終路徑求出，利用Print函數打印出V0和V，再調用FindPath函數，打印經過的結點。最后打印出距離，便可在屏幕上打印出單源最短路徑。5.2.3 求多源最短路徑 對每個結點循環(huán)調用便可打印出每個結點到其他結點的最短路徑，通過改變Print函數的形參，便可以求出兩點間的最短路徑。 6 程序編碼根據詳細設計轉化為如下代碼，下面列出部分代碼：#include#include #include#define OVERFLOW 0#define MAX_CITIES 15#define INFINITY 999#define

15、 FALSE 0#define TRUE 1typedef struct _path int adjcity;/鄰接點域 int distance;/距離 struct _path *nextpath;/下一個路徑 PathNode,*PListMAX_CITIES;typedef struct _city char name10;/城市名 struct _path *firstpath;/第一個路徑 AdjList15,CityNode;typedef struct int cities; int paths; AdjList list; Graph;PList head;typedef i

16、nt PathMatrix;typedef int ShortPathTable;PathMatrix PMAX_CITIESMAX_CITIES;ShortPathTable DMAX_CITIES;int CreatAdjList(Graph *G)/初始化交通圖 PathNode *p,*p1,*pre; int i=0; printf(請輸入交通路徑數目n); scanf(%d,&G-paths); printf(請輸入城市數目n); scanf(%d,&G-cities); for(i=0; icities; i+) printf(請輸入第%d個城市名稱n,i+1); getchar

17、(); scanf(%s,G-); G-listi.firstpath=(PathNode *)malloc(sizeof(PathNode); p=G-listi.firstpath; printf(請輸入城市第一條路徑的鄰接城市的位置（-1表示結束）n); scanf(%d,&p-adjcity); printf(請輸入城市第一條路徑的距離n); scanf(%d,&p-distance); if(p-adjcity=-1) free(p); p=NULL; G-listi.firstpath = NULL;/把弧鏈表的first置為NULL while(p) p-ne

18、xtpath=(PathNode *)malloc(sizeof(PathNode); pre=p; p=p-nextpath; printf(請輸入城市下一條路徑的鄰接城市（-1表示結束）n); scanf(%d,&p-adjcity); if(p-adjcity=-1) free(p); p=NULL; pre-nextpath = NULL;/置pre為弧鏈表結束的節(jié)點 break; printf(請輸入城市下一條路徑的距離n); scanf(%d,&p-distance); return 0;int ReadAdjList(Graph *G)/讀取交通圖 FILE *fp; int r

19、,i; PathNode *p,*p1,*pre; if( fp=fopen(graph.txt,r)=NULL) printf(文件打開失敗); exit(0); r=fscanf(fp,%d %d ,&G-paths,&G-cities); if(r=2) for(i=0; icities; i+) fscanf(fp,%s,G-); G-listi.firstpath=(PathNode *)malloc(sizeof(PathNode); p=G-listi.firstpath; fscanf(fp,%d,&p-adjcity); if(p-adjcity=-1)

20、free(p); p=NULL; G-listi.firstpath = NULL;/把弧鏈表的first置為NULL break; else fscanf(fp,%d,&p-distance); while(1) p-nextpath=(PathNode *)malloc(sizeof(PathNode); pre = p; p=p-nextpath; fscanf(fp,%d,&p-adjcity); if(p-adjcity=-1) free(p); p=NULL; pre-nextpath = NULL;/置pre為弧鏈表結束的節(jié)點 break; else fscanf(fp,%d,&

21、p-distance); fclose(fp); return 0;int WriteAdjList(Graph *G)/讀取交通圖 FILE *fp; int r,i; PathNode *p,*p1; if( fp=fopen(graph.txt,w)=NULL) printf(文件打開失敗); exit(0); fprintf(fp,%d %d ,G-paths,G-cities); for(i=0; icities; i+) fprintf(fp,%s ,G-); p=G-listi.firstpath; while(p) fprintf(fp,%d %d ,p-a

22、djcity,p-distance); p=p-nextpath; fprintf(fp,-1 ); fclose(fp); return 0;void ADD_PATH(Graph *G,int ori,int add,PathNode p)/添加路徑 PathNode *pr; pr=(PathNode *)malloc(sizeof(PathNode); pr-adjcity=add; pr-distance=p.distance; pr-nextpath=G-listori.firstpath; G-listori.firstpath=pr;void ADD_CITY(Graph *G

23、)/添加城市 int i=0; PathNode *p,*pre; if(G-cities=MAX_CITIES) return ; while(strcmp(G-,0)!=0) i+; G-cities+; printf(請輸入%d城市的名稱n,i+1); getchar(); scanf(%s,G-); G-listi.firstpath=(PathNode *)malloc(sizeof(PathNode); p=G-listi.firstpath; printf(請輸入城市第一條路徑的鄰接城市的位置（-1表示結束）n); scanf(%d,&p-

24、adjcity); printf(請輸入城市第一條路徑的距離n); scanf(%d,&p-distance); if(p-adjcity=-1) free(p); p=NULL; G-listi.firstpath = NULL;/把弧鏈表的first置為NULL else ADD_PATH(G,p-adjcity,i,*p); while(p) p-nextpath=(PathNode *)malloc(sizeof(PathNode); pre = p; p=p-nextpath; printf(請輸入城市下一條路徑的鄰接城市（-1表示結束）n); scanf(%d,&p-adjcity

25、); printf(請輸入城市下一條路徑的距離n); scanf(%d,&p-distance); if(p-adjcity=-1) free(p); p=NULL; pre-nextpath = NULL;/置pre為弧鏈表結束的節(jié)點 else ADD_PATH(G,p-adjcity,i,*p); void UPDATE_CITY(Graph *G,int city,char *name) strcpy(G-,name);int FindCity(Graph *G,char name)/返回城市的序號 int i; for(i=0; icities; i+) if

26、(strcmp(name,G-)=0) return i; return -1;void UPDATE_PATH(Graph *G,int left,int right) PathNode *p; int dis; printf(請輸入修改后的路徑距離n); scanf(%d,&dis); p=G-listleft.firstpath; while(1) if(right=p-adjcity) p-distance=dis; break; p=p-nextpath; p=G-listright.firstpath; while(1) if(left=p-adjcity) p

27、-distance=dis; break; p=p-nextpath; return ;void DELETE_PATH(Graph *G,int left,int right) PathNode *p,*pre; int dis; p=G-listleft.firstpath; pre=p; while(p) if(right=p-adjcity) break; p=p-nextpath; while(1) if(p=G-listleft.firstpath) G-listleft.firstpath=p-nextpath; free(p); break; if(pre-nextpath=p

28、) pre-nextpath=p-nextpath; free(p); break; p=G-listright.firstpath; pre=p; while(p) if(left=p-adjcity) break; p=p-nextpath; while(1) if(p=G-listright.firstpath) G-listright.firstpath=p-nextpath; free(p); break; if(pre-nextpath=p) pre-nextpath=p-nextpath; free(p); break; return ;void DELETE_CITY(Grap

29、h *G,int city) int i; while(G-listcity.firstpath) DELETE_PATH(G,city,G-listcity.firstpath-adjcity); G-cities-; for(i=city+1; icities; i+) G-listi-1=G-listi;void menu(int i) switch(i) case 0: printf(=- ( - ) 乾杯 n); printf(歡迎進入交通咨詢系統(tǒng)n); printf(ttttt1：任意鍵進入客戶模式n); printf(tttt2：輸入密碼進入管理員模式n); printf(ttt

30、3：輸入0退出系統(tǒng)n); printf(o)oBINGO!=n); break; case 1: printf(=- ( - ) 乾杯 n); printf(歡迎進入交通咨詢系統(tǒng)管理員模式n); printf(tttttttt輸入：n); printf(ttttttt1：初始化交通圖n); printf(tttttt2：更新交通圖信息n); printf(ttttt3：刪除交通圖信息n); printf(tttt4：添加交通圖信息n); printf(ttt5：創(chuàng)建交通圖n); printf(tt6：退出n); printf(o)oBINGO!=n); break; case 2: print

31、f(=- ( - ) 乾杯 n); printf(歡迎進入交通咨詢系統(tǒng)客戶模式n); printf(tttttttt輸入：n); printf(ttttttt1：咨詢某城市到其他所有城市的最短路徑n); printf(tttttt2：咨詢所有城市間的最短路徑n); printf(ttttt3：咨詢兩城市間的最短路徑n); printf(tttt4：瀏覽地圖的鄰接表表示n); printf(ttt5：退出n); printf(o)oBINGO!=n); break; void initalize_graph(Graph *G) int i; for(i=0; ,0); G-

32、listi.firstpath=NULL; void MODE_ADMIN(Graph *G) int i=0,j; char name20,name120; PathNode *p; while(1) menu(1); scanf(%d,&i); switch(i) case 1: initalize_graph(G); printf(初始化完成！n); break; case 2: printf(1：修改城市名n2：修改路徑距離n3:返回上一層n); scanf(%d,&j); if(j=1) printf(請輸入要修改的城市名稱n); gets(name); printf(請輸入要修改后

33、的城市名稱n); gets(name1); UPDATE_CITY(G, FindCity(G,name),name1); printf(修改完成！n); else if(j=2) printf(請輸入要修改的兩個中第一個城市的名稱n); gets(name); printf(請輸入要修改的兩個中第二個城市的名稱n); gets(name1); UPDATE_PATH(G,FindCity(G,name),FindCity(G,name1); printf(修改完成！n); else break; break; case 3: printf(1：刪除城市n2：刪除路徑n3:返回上一層n); s

34、canf(%d,&j); if(j=1) printf(請輸入要刪除的城市名稱n); gets(name); DELETE_CITY(G,FindCity(G,name); printf(刪除完成！n); else if(j=2) printf(請輸入要刪除的路徑中第一個城市的名稱n); gets(name); printf(請輸入要修改的兩個中第二個城市的名稱n); gets(name1); DELETE_PATH(G,FindCity(G,name),FindCity(G,name1); printf(刪除完成！n); else break; break; case 4: printf(1

35、：添加城市n2：添加路徑n3:返回上一層n); scanf(%d,&j); if(j=1) ADD_CITY(G); printf(添加完成！n); else if(j=2) p=(PathNode *)malloc(sizeof(PathNode); printf(請輸入要添加的路徑中第一個城市的名稱n); gets(name); printf(請輸入要添加的兩個中第二個城市的名稱n); gets(name1); printf(請輸入要添加的路徑的距離n); scanf(%d,p-adjcity); ADD_PATH(G,FindCity(G,name),FindCity(G,name1),

36、*p); ADD_PATH(G,FindCity(G,name1),FindCity(G,name),*p); printf(添加完成！n); else break; break; case 5: CreatAdjList(G); printf(創(chuàng)建完成！n); break; default : return ; WriteAdjList(G); int dis(Graph *G,int left,int right) PathNode *p; p=G-listleft.firstpath; while(p) if(right=p-adjcity) return p-distance; p=p

37、-nextpath; return INFINITY;void ShortestPath(Graph *G,int v0) int i,w,v,min,l=0; int finalMAX_CITIES;/Dijkstra tool for(v=0; vcities; v+) finalv=FALSE; Dv=dis(G,v0,v); for(w=0; wcities; w+) Pvw=FALSE; if(DvINFINITY) Pvv0=1; Pvw=1; Dv0=0; finalv0=TRUE; for(i=1; icities; i+) min=INFINITY; for(w=0; wci

38、ties; w+) if(!finalw) if(Dwmin) v=w; min=Dw; finalv=TRUE; for(w=0; wcities; w+) if(!finalw&(min+dis(G,v,w)Dw) Dw=min+dis(G,v,w); strcpy(char*)Pw,(char *)Pv); Pwv=TRUE; void FindPath(Graph *G,int v) int i=0; for(i=0; iMAX_CITIES; i+) if(Pvi=1) if(dis(G,v,i),G-);void Print(Graph *G,int v0) i

39、nt i; PathNode *p,*pre; for(i=0; icities; i+) if(i!=v0) printf(%s到%s的最短距離為%d，路徑如下：n,G-,G-,Di); printf(%s-,G-); Piv0=0; Pii=0; FindPath(G,i); printf(%sn,G-); void Print2(Graph *G,int v1,int v2) printf(%s到%s的最短距離為%d，路徑如下：n,G-,G-,Dv2); pri

40、ntf(%s-,G-); Pv2v1=0; Pv2v2=0; FindPath(G,v2); printf(%sn,G-);void Print3(Graph *G) int i;PathNode *p; for(i=0; icities; i+) p=G-listi.firstpath-nextpath; printf(|%-2d%-12s-%-12s%-3d|, i+1, G-, G-listG-, G-listi.firstpath-distance); while(p

41、) printf(-%-12s%-3d|, G-, p-distance); p=p-nextpath; printf(); putchar(10); void MODE_CLIENT(Graph *G) int i,j; int v0,v1,v2; char name120,name220,name20; while(1) menu(2); scanf(%d,&i); switch(i) case 1: printf(請輸入城市的名稱：n); scanf(%s,name); v0=FindCity(G,name); if(v0=-1) printf(輸入有

42、誤或者沒有該城市！); break; ShortestPath(G,v0); Print(G,v0); break; case 3: printf(請輸入第一個城市的名稱：n); scanf(%s,name1); v1=FindCity(G,name1); printf(請輸入第二個城市的名稱：n); scanf(%s,name2); v2=FindCity(G,name2); if(v1=-1|v2=-1) printf(輸入有誤或者沒有該城市！); break; ShortestPath(G,v1); Print2(G,v1,v2); break; case 2: for(j=0; jci

43、ties; j+) ShortestPath(G,j); Print(G,j); break; case 4: Print3(G); getchar(); getchar(); break; default: return ; int main() Graph G; int password=123; initalize_graph(&G); ReadAdjList(&G); while(1) menu(0); scanf(%d,&password); if(password=123) MODE_ADMIN(&G); else if(password=0) return 0; else MOD

44、E_CLIENT(&G); return 0;7 運行結果插入城市函數測試：輸入：TextCity03-1輸出結果：添加完成！查看鄰接表結果：刪除城市函數測試：輸入：LaSa輸出結果：刪除完成！查看鄰接表結果對比：刪除前：刪除后：更新城市函數測試：略；修改城市函數測試：略；退出保存函數測試：略；單源多終點函數測試：輸入：TextCity輸出結果：單源單終點函數測試：輸入：TextCityGuangzhou輸出結果：輸入有誤或者沒有該城市！輸入：TextCityGuangZhou輸出結果：TextCity到GuangZhou的最短距離為13，路徑如下：TextCity-BeiJing-Guang

45、Zhou多源多終點函數測試：BeiJing-ShangHaiBeiJing到ZhengZhou的最短距離為5，路徑如下：BeiJing-HanDan-ZhengZhouBeiJing到XiAn的最短距離為5，路徑如下：BeiJing-XiAnBeiJing到WuHan的最短距離為7，路徑如下：BeiJing-HanDan-WuHanBeiJing到GuangZhou的最短距離為10，路徑如下：BeiJing-GuangZhouBeiJing到ShenYang的最短距離為4，路徑如下：BeiJing-TianJin-ShenYangBeiJing到LaSa的最短距離為25，路徑如下：BeiJing-XiAn-LaSaBeiJing到HanDan的最短距離為3，路徑如下：BeiJing-HanDanBeiJing到TextCity的最短距離為3，路徑如下：BeiJing-TextCityTianJin到BeiJing的最短距離為1，路徑如下：TianJin-BeiJingTia