全國交通咨詢模擬

1、數據結構課程設計課題：全國交通咨詢模擬學 院：計算機科學與技術專 業(yè)： 通信工程 班 級： 0903 學 號： 2009115020322學生姓名： 指導教師： 一、題目分析1.【問題描述】處于對不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時間盡可能的短，出門旅游的游客則希望旅費盡可能的省，而老年旅客則要求中轉次數最少。編制一個全國城市間的交通咨詢程序，為旅客提供兩到三種最優(yōu)決策的交通咨詢。2.【基本要求】（1）提供對城市信息進行編輯（添加、刪除）的功能。（2）城市之間有兩種工具：火車和飛機。提供對列車時刻表和飛機航班表的編輯。（3）提供兩種最優(yōu)決策：最快到達或最省

2、錢到達。全程只考慮一種交通工具。（4）旅途中耗費的總時間應該包括中轉站的等候時間。（5）咨詢以用戶和計算機的對話方式進行。由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具。輸出信息：最快需要多長時間才能到達或者最少需要多少旅費才能到達，并詳細說明依次于何時乘坐哪一趟列車或哪一次班機到何地。二、概要設計1.【抽象數據類型】本程序運用了圖這種數據結構，并以鄰接表作交通圖的存儲結構。數據對象V：V是具有相同特性的數據元素的集合，稱為頂點集。數據關系R：R=VR VR=<v,w>|v,wV且P(v,w),<v,w>表示從v到w的弧。 謂詞P(v,w)定義了弧<v,w>

3、;的意義或信息基本操作：AdjInitiate(&G)初始化鄰接表AdjDestroy（&G）撤銷鄰接表InsertVertex(&G,i,&a)插入結點DeleteVertex(&G,i)刪除結點InsertEdge()插入邊DeleteEdge()刪除邊GetFirstVex（）取第一個鄰接結點GetNextVex()取下一個鄰接結點CreatGraph()創(chuàng)建圖鄰接表的存儲結構typedef struct Nodeint dest;struct Node *next;int t_time;float t_price;int t_start5;int

4、 t_get5;int f_time;float f_price;int f_start5;int f_get5;Edge;typedef structDataType data20;int score;Edge *adj;AdjLHeight;typedef structAdjLHeight aMax;int numOfVerts;int numOfEdges;AdjLGraph;棧的存儲結構typedef struct snodeint data;struct snode *next;LSNode;其他基本操作：void Administer(AdjLGraph *G);void User

5、Demand(AdjLGraph *G);void CreatTraffic(AdjLGraph *G);void EditCity(AdjLGraph *G);void AddCity(AdjLGraph *G);void DeleteCity(AdjLGraph *G);void EditTraffic(AdjLGraph *G);int AddTraffic(AdjLGraph *G,int a);int DeleteTraffic(AdjLGraph *G,int a);void LeastMoney(AdjLGraph *G,int v1,int v2,int Traffic)voi

6、d LeastTime(AdjLGraph *G,int v1,int v2,int Traffic)2.【程序的模塊】主函數main退出用戶咨詢UserDemand管理系統(tǒng)AdministerAdminister(&G)Administer(&G)管理系統(tǒng)Administer退出編輯道路EditTraffic編輯城市EditCity初始化交通系統(tǒng)CreatTraffic編輯城市EditCity退出添加城市AddCity刪除城市DeleteCity編輯道路EditTraffic退出添加道路Addtraffic刪除道路DeleteTraffic用戶咨詢UserDemand退出最省

7、錢到達LeastMoney最快到達LeastTime三、詳細設計1.【函數調用關系】DeleteQueueEnterQueueTransferDisposePrintGraphCreatTrafficInsertVextexAddcityEditCityDeleteVextexDeletetCityInsertEdgeAddTrafficEditTrafficAdministerDeleteTrafficDeleteEdgeStackPushMain()LeastMoneyStackPopUserDemandStackTopLeastTime2.【源文件】#include<stdio.h

8、>#include<stdlib.h>#include<string.h>#include<malloc.h>typedef char DataType;#define Max 30#define MaxEdges 60#define MaxWeight 10000int Traffic5*MaxEdges;int tag=0;#include"Adj.h"#include"LStack.h"#include"Dijkstra.h"void Administer(AdjLGraph *G);v

9、oid UserDemand(AdjLGraph *G);void CreatTraffic(AdjLGraph *G);void EditCity(AdjLGraph *G);void AddCity(AdjLGraph *G);void DeleteCity(AdjLGraph *G);void EditTraffic(AdjLGraph *G);int AddTraffic(AdjLGraph *G,int a);int DeleteTraffic(AdjLGraph *G,int a);void main()AdjLGraph G;AdjInitiate(&G);int i;

10、do system("cls");printf("nnnnnnn 請選擇程序功能:n");printf(" *n");printf(" * 1=管理系統(tǒng) *n");printf(" * 2=用戶咨詢 *n");printf(" * 3=退出 *n");printf(" *n");printf(" 選擇?"); scanf("%d",&i); getchar(); switch(i) case 1:Admini

11、ster(&G); break; case 2:UserDemand(&G); break; case 3:break; while(i!=3);void Administer(AdjLGraph *G)int i; dosystem("cls");printf("nnnnnnn 請選擇程序功能:n");printf(" *n");printf(" * 1=初始化交通系統(tǒng) *n");printf(" * 2=編輯城市 *n");printf(" * 3=編輯交通 *n&

12、quot;);printf(" * 4=返回 *n");printf(" *n");printf(" 選擇?");scanf("%d",&i);getchar(); switch(i) case 1:CreatTraffic(G); break; case 2:EditCity(G); break; case 3:EditTraffic(G); break; case 4:break; while(i!=4);void UserDemand(AdjLGraph *G)int i=0,e=0,j,v1,v2;

13、FILE *fp,*fr;if(fp=fopen("city.txt","rb")=NULL)printf("無法打開文件!n");while(!feof(fp)fscanf(fp,"%10s",G->ai.data);i+;fclose(fp);G->numOfVerts=i;if(fr=fopen("traffic.txt","rb")=NULL)printf("無法打開文件!n");while(!feof(fr)fscanf(fr,&qu

14、ot;%5d",&Traffice);if(Traffice=-1)e-;e+;fclose(fr);G->numOfEdges=e/5;if(tag=0)for(j=0;j<G->numOfEdges;j+)Edge *p;p=(Edge *)malloc(sizeof(Edge); /*申請鄰接邊單鏈表結點空間*/p->dest=Traffic5*j+1; /*置鄰接邊弧頭序號*/p->next=G->aTraffic5*j.adj; /*新結點插入單鏈表的表頭*/G->aTraffic5*j.adj=p; /*頭指針指向新的單鏈

15、表表頭*/EditEdge(p,Traffic5*j+2,Traffic5*j+3,Traffic5*j+4);system("cls");for(j=0;j<G->numOfVerts;j+)printf("%d=%sn",j,G->aj.data);printf("n 選取起始站：");scanf("%d",&v1);printf("n 選取終點站：");scanf("%d",&v2);do system("cls")

16、;printf("nnnnnnn 請選擇程序功能:n");printf(" *n");printf(" * 1=最省錢到達 *n");printf(" * 2=最快到達 *n");printf(" * 3=返回 *n");printf(" *n");printf(" 選擇?");scanf("%d",&i);getchar(); switch(i) case 1:LeastMoney(G,v1,v2,Traffic); brea

17、k; case 2:LeastTime(G,v1,v2,Traffic); break; case 3:AdjDestroy(G);AdjInitiate(G); break; while(i!=3); tag=0;void CreatTraffic(AdjLGraph *G)tag=1;int i=0,e=0,j,v1,v2;DataType cityMax20;char flag='Y'while(flag='y'|flag='Y')system("cls");printf("nnnnnnn 輸入城市名:&quo

18、t;);gets(cityi);i+;printf("n 繼續(xù)輸入?(Y/N)");flag=getchar();getchar();printf("n 是否保存城市文本?(Y/N)");flag=getchar();getchar();if(flag='y'|flag='Y')FILE *fp;if(fp=fopen("city.txt","wb")=NULL)printf("無法打開文件!n");for(j=0;j<i;j+)fprintf(fp,&qu

19、ot;%10s",cityj);fclose(fp);dosystem("cls");for(j=0;j<i;j+)printf("%d=%sn",j,cityj); printf("n 選擇初始站："); scanf("%d",&v1); printf("n 選擇到達站："); scanf("%d",&v2);getchar();Traffic5*e=v1;Traffic5*e+1=v2;e+;printf("n 繼續(xù)編輯?(Y/N

20、)");flag=getchar();getchar();while(flag='Y'|flag='y');CreatGraph(G,city0,i,Traffic,e);printf("n 是否保存交通道路文本?(Y/N)");flag=getchar();getchar();if(flag='y'|flag='Y')FILE *fp;if(fp=fopen("traffic.txt","wb")=NULL)printf("無法打開文件!n"

21、;);for(j=0;j<5*e;j+)fprintf(fp,"%5d",Trafficj);fclose(fp);void EditCity(AdjLGraph *G)int i=0,e=0,j;FILE *fp,*fr;if(fp=fopen("city.txt","rb")=NULL)printf("無法打開文件!n");while(!feof(fp)fscanf(fp,"%10s",G->ai.data);i+;fclose(fp);G->numOfVerts=i;if

22、(fr=fopen("traffic.txt","rb")=NULL)printf("無法打開文件!n");while(!feof(fr)fscanf(fr,"%5d",&Traffice);if(Traffice=-1)e-;e+;fclose(fr);G->numOfEdges=e/5;if(tag=0)for(j=0;j<G->numOfEdges;j+)Edge *p;p=(Edge *)malloc(sizeof(Edge); /*申請鄰接邊單鏈表結點空間*/p->dest

23、=Traffic5*j+1; /*置鄰接邊弧頭序號*/p->next=G->aTraffic5*j.adj; /*新結點插入單鏈表的表頭*/G->aTraffic5*j.adj=p; /*頭指針指向新的單鏈表表頭*/EditEdge(p,Traffic5*j+2,Traffic5*j+3,Traffic5*j+4); system("cls"); printf("nnnnnnn 請選擇程序功能:n"); printf(" *n"); printf(" * 1=新增城市 *n"); printf(&

24、quot; * 2=刪除城市 *n"); printf(" * 3=返回 *n"); printf(" *n"); printf(" 選擇?"); scanf("%d",&i); getchar(); switch(i) case 1:AddCity(G); break; case 2:DeleteCity(G); break; case 3:break; void AddCity(AdjLGraph *G)tag=1;int i=0,j;DataType cityMax20;if(G->n

25、umOfVerts<Max)FILE *fp;if(fp=fopen("city.txt","rb")=NULL)printf("無法打開文件!n");while(!feof(fp)fscanf(fp,"%10s",cityi);i+;fclose(fp);system("cls");for(j=0;j<G->numOfVerts;j+)printf("%d=%sn",j,G->aj.data);printf("n 輸入城市名:")

26、;DataType a20;scanf("%s",a);strcpy(cityi,a);i+;FILE *fr;if(fr=fopen("city.txt","wb")=NULL)printf("無法打開文件!n");for(j=0;j<i;j+)fprintf(fr,"%10s",cityj);fclose(fr);InsertVertex(G,G->numOfVerts,a);else printf("城市數量已達最大值");void DeleteCity(A

27、djLGraph *G)tag=1;int v1,j,e=0;system("cls");for(j=0;j<G->numOfVerts;j+)printf("%d=%sn",j,G->aj.data);printf("n 選取城市序號：");scanf("%d",&v1);j=0;while(j<G->numOfEdges)if(Traffic5*j=v1|Traffic5*j+1=v1)Traffic5*j=-1;Traffic5*j+1=-1;Traffic5*j+2=-

28、1;Traffic5*j+3=-1;Traffic5*j+4=-1;j+;j=0;while(j<G->numOfEdges)if(Traffic5*j>v1)Traffic5*j-;if(Traffic5*j+1>v1)Traffic5*j+1-;j+;FILE *fp;if(fp=fopen("traffic.txt","wb")=NULL)printf("無法打開文件!n");for(j=0;j<5*G->numOfEdges;j+)fprintf(fp,"%5d",Tra

29、fficj);fclose(fp);DeleteVertex(G,v1);if(fp=fopen("traffic.txt","rb")=NULL)printf("無法打開文件!n");while(!feof(fp)fscanf(fp,"%5d",&Traffice);if(Traffice=-1)e-;e+;fclose(fp);G->numOfEdges=e/5;if(fp=fopen("traffic.txt","wb")=NULL)printf(&quo

30、t;無法打開文件!n");for(j=0;j<5*G->numOfEdges;j+)fprintf(fp,"%5d",Trafficj);fclose(fp);if(fp=fopen("city.txt","wb")=NULL)printf("無法打開文件!n");for(j=0;j<G->numOfVerts;j+)fprintf(fp,"%10s",G->aj.data);fclose(fp);void EditTraffic(AdjLGraph *G

31、)int i=0,e=0,j;FILE *fp,*fr;if(fp=fopen("city.txt","rb")=NULL)printf("無法打開文件!n");while(!feof(fp)fscanf(fp,"%10s",G->ai.data);i+;fclose(fp);G->numOfVerts=i;if(fr=fopen("traffic.txt","rb")=NULL)printf("無法打開文件!n");while(!feof(f

32、r)fscanf(fr,"%5d",&Traffice);if(Traffice=-1)e-;e+;fclose(fr);G->numOfEdges=e/5;if(tag=0)for(j=0;j<G->numOfEdges;j+)Edge *p;p=(Edge *)malloc(sizeof(Edge); /*申請鄰接邊單鏈表結點空間*/p->dest=Traffic5*j+1; /*置鄰接邊弧頭序號*/p->next=G->aTraffic5*j.adj; /*新結點插入單鏈表的表頭*/G->aTraffic5*j.adj

33、=p; /*頭指針指向新的單鏈表表頭*/EditEdge(p,Traffic5*j+2,Traffic5*j+3,Traffic5*j+4); system("cls"); printf("nnnnnnn 請選擇程序功能:n"); printf(" *n"); printf(" * 1=新增道路 *n"); printf(" * 2=刪除道路 *n"); printf(" * 3=返回 *n"); printf(" *n"); printf("

34、選擇?"); scanf("%d",&i); switch(i) case 1:AddTraffic(G,Traffic); break; case 2:DeleteTraffic(G,Traffic); break; case 3:break; int AddTraffic(AdjLGraph *G,int a)tag=1;int i,j,v1,v2;system("cls");for(j=0;j<G->numOfVerts;j+)printf("%d=%sn",j,G->aj.data);pri

35、ntf("n 選取城市序號：");scanf("%d",&v1);printf("n 選取另一個城市序號：");scanf("%d",&v2);if(v1<0|v1>=G->numOfVerts|v2<0|v2>=G->numOfVerts)system("cls");printf("nnnnnnn 城市序號參數越界出錯！");printf("n 請選擇程序功能:n"); printf(" *n

36、"); printf(" * 1=返回 *n"); printf(" *n"); printf(" 選擇?"); scanf("%d",&i); getchar();doswitch(i)case 1:return 0;while(i!=1); elsej=GetFirstVex(*G,v1);if(j=-1)Traffic5*G->numOfEdges=v1;Traffic5*G->numOfEdges+1=v2;char flag;InsertEdge(G,v1,v2);print

37、f("n 是否保存交通道路文本?(Y/N)");flag=getchar(); getchar(); if(flag='y'|flag='Y') FILE *fp; if(fp=fopen("traffic.txt","wb")=NULL)printf("無法打開文件!n");for(j=0;j<5*G->numOfEdges;j+) fprintf(fp,"%5d",Trafficj); fclose(fp);return 1;elsewhile(j

38、!=v2&&j!=-1)j=GetNextVex(*G,v1,j);if(j=v2)system("cls");printf("nnnnnnn %s-%s已被編輯過",G->av1.data,G->av2.data);printf("n 如需改動數據可先刪除后再重新編輯");printf("n 請選擇程序功能:n");printf(" *n");printf(" * 1=返回 *n");printf(" *n");printf(

39、" 選擇?");scanf("%d",&i);getchar();doswitch(i)case 1:return 0;while(i!=1);else char flag;Traffic5*G->numOfEdges=v1;Traffic5*G->numOfEdges+1=v2; InsertEdge(G,v1,v2); printf("n 是否保存交通道路文本?(Y/N)"); flag=getchar(); getchar(); if(flag='y'|flag='Y') FI

40、LE *fp; if(fp=fopen("traffic.txt","wb")=NULL) printf("無法打開文件!n"); for(j=0;j<5*G->numOfEdges;j+) fprintf(fp,"%5d",Trafficj); fclose(fp);return 1;int DeleteTraffic(AdjLGraph *G,int a)tag=1;int i,j,v1,v2,e=0;system("cls");for(j=0;j<G->numOfV

41、erts;j+)printf("%d=%sn",j,G->aj.data);printf("n 選取城市序號：");scanf("%d",&v1);printf("n 選取另一個城市序號：");scanf("%d",&v2);if(DeleteEdge(G,v1,v2)=0)printf("n 請選擇程序功能:n");printf(" *n"); printf(" * 1=返回 *n"); printf("

42、; *n"); printf(" 選擇?"); scanf("%d",&i); getchar();doswitch(i)case 1:return 0;while(i!=1);j=0;while(Traffic5*j!=v1|Traffic5*j+1!=v2)j+;Traffic5*j=-1;Traffic5*j+1=-1;Traffic5*j+2=-1;Traffic5*j+3=-1;Traffic5*j+4=-1;char flag;getchar();printf("n 是否保存交通道路文本?(Y/N)");

43、flag=getchar();getchar();printf("%cn",flag);if(flag='y'|flag='Y')FILE *fp;if(fp=fopen("traffic.txt","wb")=NULL)printf("無法打開文件!n");for(j=0;j<5*(G->numOfEdges+1);j+)fprintf(fp,"%5d",Trafficj);fclose(fp);if(fp=fopen("traffic.t

44、xt","rb")=NULL)printf("無法打開文件!n");while(!feof(fp)fscanf(fp,"%5d",&Traffice);if(Traffice=-1)e-;e+;fclose(fp);G->numOfEdges=e/5;if(fp=fopen("traffic.txt","wb")=NULL)printf("無法打開文件!n");for(j=0;j<5*G->numOfEdges;j+)fprintf(fp,

45、"%5d",Trafficj);fclose(fp);return 1;3.【頭文件】/*Adj.h(圖的基本操作)添加到頭文件*/typedef struct Nodeint dest;struct Node *next;int t_time;float t_price;int t_start5;int t_get5;int f_time;float f_price;int f_start5;int f_get5;Edge;typedef structDataType data20;int score;Edge *adj;AdjLHeight;typedef struct

46、AdjLHeight aMax;int numOfVerts;int numOfEdges;AdjLGraph;void AdjInitiate(AdjLGraph *G)/*初始化圖G*/int i;G->numOfVerts=0;G->numOfEdges=0;for(i=0;i<Max;i+)G->ai.score=i;G->ai.adj=NULL;void AdjDestroy(AdjLGraph *G)/*撤銷圖G中所有鄰家邊單鏈表*/int i;Edge *p,*q;for(i=0;i<G->numOfVerts;i+)p=G->ai

47、.adj;while(p!=NULL)q=p->next;free(p);p=q;void InsertVertex(AdjLGraph *G,int i,DataType *vertex)/*在圖G中第i（0iMax）個位置插入結點數據元素vertex*/if(i>=0&&i<Max)strcpy(G->ai.data,vertex);G->numOfVerts+;else printf("結點越界n");int DeleteEdge(AdjLGraph *G,int v1,int v2);void DeleteVertex(AdjLGraph *G,int i)int j,a;Edge *p,*q;p=G->ai.adj;while(p)q=p->next;free(p);p=q;G->numOfEdges-;G->ai.adj=NULL;for(j=i+1;j<=G->numOfVerts-1;j+)strcp