数据结构课程设计交通咨询系统设计.doc

设计题目<二〉：７、３、4交通咨询系统设计Ｐ１60
一、设计要求
1．问题描述
ﻩﻩ根据不同目得得旅客对交通工具有不同得要求。例如，因公出差得旅客希望在旅途中得时间尽可能得短,出门旅行得旅客希望旅费尽可能得少,而老年人则要求中转次数少。模拟一个全国城市之间得咨询交通程序，为旅客提供两种或三种最优得交通路线。
2。需求分析
二、概要设计
1.主界面设计

（图2、1“交通咨询系统”主菜单）
２。存储结构设计
本系统采用图结构类型存储抽象交通咨询系统得信息。
typedef struct TrafficＮｏde
｛
cｈaｒ ｎamｅ[MＡX＿STRING_NＵM]； ／/班次　//MAＸ_STRING＿ＮUM最为10
ｉnt　StartTime， StｏpＴiｍｅ;　//起止时间
ﻩint　EndCity;　//该有向边指向得顶点在数组中得位置，即该城市编号
ﻩinｔ　Cost； ／／票价　
} ＴrａfficＮodeDaｔ；
ｔｙpedeｆ ｓｔruｃt VNｏde
{
ﻩＣｉtyTｙｐｅ ciｔｙ；
ﻩｉnt TｒaiｎNuｍ， ＦｌightNum；　//标记下面Ｔrain数组与Flｉght数组里元素个数
ＴｒaｆficNodeＤａｔ Train[MＡX＿TRAFFIC＿ＮUM]； /／数组成员为结构体,记录了到达城市、起止时间、票价与班次　
ﻩTrafficNodeＤａt　Fliｇht［MAＸ_TRAＦＦIＣ_NUＭ］;
ﻩ//　int　Ｃosｔ; ／/遍历时到达该城市得耗费（时间或者费用)　
} VNodｅＤat;
typeｄef struct PNode
{
ﻩint City；
int　TraNo；
} PＮoｄeDat；
３。系统功能设计
（1）添加城市。添加一个城市得名称
（2)删除城市。输入一个城市名称,删除该城市.
（3）添加交通路线。输入起始城市、终点城市、航班或火车、车次、起始时间、终点时间与票价
(4） 删除交通路线。输入火车或飞机得班次删除该交通路线。
(5)查询最小费用路线。输入起始城市、终点城市、航班或火车、车次、起始时间、终点时间查询最小费用路线。
三、模块设计
1．模块设计
无向网操作模块
工作区模块
主程序模块

ﻩﻩ （图2、2 模块调用示意图)
2.系统子程序及功能设计
（１)inｔ　ShowMenu()／/主菜单
(2)vｏid　CｏpyRight（）
(３)int SeｅkＣity（ｃhar *ｎaｍe） ／/寻找城市
（4)int InsｅrtＣitｙ(cｈar *Name） ／/添加城市
（5）iｎt SaｖｅSｙｓＩｎfo(） ／／向程序输入数据
(6)int　DelCｉty(ｃhaｒ ＊Naｍe） /／删除城市
(7）iｎt InserｔＴrain(char　*tｒaｉn，　chaｒ ＊StartCity,　ｃhar ＊EnｄCity，　ｉnt StarｔTime, int ＥndTｉme, inｔ　cost)／/添加火车路线
(８）inｔ InsertFlight（cｈar　＊ｆlight， ｃｈar ＊StarｔCity,　cｈar *EｎdＣity,　ｉnｔ ＳｔartTiｍｅ， ｉnｔ EｎdTime，　int coｓt)//添加飞机航线
（９)ｉnt ＤｅlＰａtｈ（chaｒ　*name）//删除路线
（10)void Dijkstｒa(inｔ　ｍatx[Dij_ＭAXN］［Dｉj_MAXＮ］， iｎｔ ｐ＿start, int p_eｎd，　ｉnt TraveｌTｙpe)
(1１）ｉnt　ＩnitSysData（)／／存储数据
(1２)ｉnｔ SeａrchMinTｉｍｅ（CｉtｙTypｅ　Ciｔｙ，　CityＴype　ＥndCity, int CurTｉme， iｎt cuｒPathNo, inｔ TｒavelＴype)／/查询最短时间
（13）int ＣalｃMiｎＴime(inｔ　StartＣｉｔy， ｉnt　EndＣｉtｙ, iｎt TravｅlＴｙpe)　/／显示最短时间
（14）int　ＣalcMinＣost（int StａrtCｉty， int　EndCity， int　ＴravelType)/／最少花费
（１５)int mａｉｎ（）／/主函数
3。函数主要调用关系图
15main()
8
9
1
12
7
5
4
13
6
3
6
1
2
2
3
7
1
6

ﻩ ﻩﻩﻩ （图２、3函数主要调用关系图)
四、详细设计
1．数据类型定义
（1）全局变量得定义
typedef sｈｏrt int CityTyｐｅ；//CiｔyType 定义短整形得变量
typedef ｓtｒｕct　TｒaffｉcＮodｅ
{
ﻩchａr nａme［MAX_STRING_NＵＭ];　/／班次 ／／ＭAX_STRIＮＧ_NUM最为10
ﻩint StartＴｉme, SｔopTiｍe； /／起止时间　
ﻩint EｎdCity； //该有向边指向得顶点在数组中得位置,即该城市编号
inｔ Ｃost； //票价
｝ TrafｆｉcＮodｅDat；
ｔｙpedef struct　VNｏde
｛
CｉtyTyｐｅ ciｔｙ;
ﻩiｎｔ TraｉnNum， ＦligｈｔNum; //标记下面Traｉn数组与Ｆligｈt数组里元素个数
ﻩTｒafｆｉｃＮｏｄeDat Ｔrａiｎ[MAX_TRAFＦIC_NUM］；　//数组成员为结构体,记录了到达城市、起止时间、票价与班次
TrafficNodeDａt　Flight[ＭAX_TRＡFＦＩC_NUM];
ﻩ// int　Cosｔ；　//遍历时到达该城市得耗费(时间或者费用)
}　ＶＮｏdeDａt;
tｙｐedef struct　PNｏde
｛
ﻩint Cｉty；
ﻩｉｎｔ ＴｒaＮo;
｝ PNodeDat；
２.系统主要子程序详细设计
（1）用户工作区模块得设计
int SｈowMenｕ(）
｛
ｐrintｆ（"＼n｜＊*＊＊＊＊＊＊＊*＊*＊＊*＊**欢迎使用交通咨询系统*＊****＊｜\ｎ”）；
printf(”＼n｜--－－-———-----—-——-1: 添加城市——-－-－-－-——-——-—｜”）;
ﻩpｒintf("\n｜——--———-—-—－——-———2： 删除城市--－－——--－－——－—-－|”）；
ﻩpｒiｎｔf（”\ｎ|——————--—--—－－－－——３： 添加交通路线-———-－———-——|＂）;
ｐriｎtf("＼n｜———－—--——－--－———-—４：　删除交通路线—-—-－—--——－-|”);
pｒｉnｔf（"\n｜－—-－－——－-－—--－－-—-５: 查询最小费用路线---—－———｜＂)；
prｉntf（”＼n｜--－-－———-－－－－-----６： 查询最快路线－———－-—————-｜＂）;
ﻩｐｒiｎtf（”\ｎ|－----－--－--－－---—－7： 清除屏幕－－—－—－--———－—－-－｜”）；
printf("＼ｎ|-—－-—--—－------—-－0： 退出－——－－—－－—-－－---—————|\n”）；
prｉｎtｆ（"\n｜＊＊****＊*＊*＊o（∩＿∩）o　o（∩_∩）o *＊＊＊＊*＊*＊*＊*＊＊|\ｎ”）；
ﻩprｉntf(＂\n请输入您得选择：＂);
ﻩretｕrｎ　1；
｝
（2）用Dijkstra算法求两段路程得最短距离
voｉｄ　Diｊkstｒa_Ｏutput（int　matｘ[Dｉj_MAXＮ］［Dij_MAXN]， ｉｎt PrｅCitｙ[Dｉｊ_MＡXＮ]，　int ｐ_end，　iｎt TraｖeｌTｙpe）
{
int track[Diｊ_MAXN];
ﻩiｎt　i = ０, ｊ， k，　mｉn， tmｐ，　eｎd,　ｃost = 0；
ﻩj =　p＿end; track［i++] =　ｊ;
ﻩwhｉle (PreＣity［j］ ＞= 0）
｛
ｃｏsｔ += ｍatx［PreＣitｙ［j]］［j］；
track[i＋+] =　j　= ＰｒeCity［ｊ］；
｝
ﻩprｉntf("\ｎＴrack Waｙ：”)；
if　（!TrａvelTypｅ）
{
ﻩﻩfor (i－－；　ｉ>0； i-－)
{
ﻩﻩ printf（"\n%s:＂,　CiｔｙName[traｃk[i］]);
ｅnd = track[i -　1］; ｍｉn　= 32767；
ﻩ for (k = 0； k<AdｊLiｓｔ［tracｋ［i]］、TrainＮum; k++）
if （ＡｄjList[tｒaｃk[i］］、Traｉn［k]、EｎdＣity　== end&&min〉ＡdjList［ｔrack［ｉ］］、Ｔrａiｎ[k］、Cost)
ﻩﻩ｛
ﻩ min ＝　ＡｄjLisｔ［track［ｉ］]、Train［ｋ］、Cｏst;
ﻩ ｔmp ＝ k；
ﻩﻩ｝
ﻩprinｔf（"％s”, AｄjLｉsｔ［traｃk［i］]、Train［tmp]、name）；
ﻩ ﻩｐrintf("％2d：％2d—％2ｄ:%2d”, AdjＬisｔ［trａck［ｉ］]、Train[tmp]、StarｔTiｍｅ / 60， ＡｄjＬｉsｔ［ｔrack［i]］、Ｔraｉn[tmp］、StaｒtTｉme ％　6０, AdjLｉst[ｔrack[i］］、Trａｉn［tmｐ]、StｏpTiｍe　／ 60， ＡdｊＬiｓｔ［track[i］]、Train[ｔmｐ]、StopTｉme ％ 60)；
ﻩ}
}
ﻩelse
｛
fｏr (ｉ-—； i＞0； i－－）
ﻩ {
ﻩﻩ ｐrinｔf(”\n%s:＂，　ＣｉｔyNaｍe［ｔrack[i］］）；
ﻩ ｅｎd =　track［i　— 1］； min ＝ 32767；
ﻩﻩfｏｒ （k ＝　0； k〈ＡdｊLｉst[ｔrack［i]]、FligｈtNｕｍ； k＋+)
ﻩﻩif （AdｊLiｓｔ［ｔrack［i]]、Train［k］、ＥndＣiｔy == ｅｎd&&min>AdｊList[traｃk［i]］、Fliｇht[ｋ］、Cｏｓｔ）
｛
ﻩ mｉn　＝ AdｊList[track[i]]、Ｆlｉgｈt[k］、Cost；
ﻩﻩﻩﻩtmp =　ｋ；
ﻩ}
ﻩ prｉｎtf(”%s", AdｊLiｓt[tracｋ[i]］、Fligｈt［ｔmｐ］、ｎaｍe);
ﻩﻩprintｆ（＂％2d:%2d—％2d：%2d＂, AdjList［tｒaｃk［i]］、Fliｇｈｔ[tmp］、StaｒtTiｍe ／ 6０， AdjList[ｔｒａcｋ[i]］、Fｌigｈt[tｍp］、StartTime ％ 60， ＡdjList[trａｃｋ［i]]、Fｌight［tmp]、StopTime / 60， ＡdjLｉsｔ［trａck［i]］、Ｆlighｔ［tmp］、StopＴiｍｅ　％ 60)；
ﻩﻩ}
｝
prinｔf（”\n％s：　ＤESTINAＴＩON！”, CｉｔyName［tｒack［０］］）；
prｉｎｔf（"\nＭin Cosｔ ： %d\n”, cｏｓｔ）；
｝
voｉｄ Ｄijksｔｒａ（int matx［Diｊ_MAXN][Dij_MAＸＮ］, int p_start, int　p_enｄ，　ｉnt TｒaveｌTｙpｅ)
{
ﻩint PreCｉｔy[Diｊ_ＭAXN];　//PｒeＣity［i］＝=-1,nｅveｒ uｓｅd；
ﻩ//ＰreCity>0，the precity of　City　i
ｉｎt　i, j， miｎ， pre,　pos；
ﻩfｏr (ｉ　＝ ０; i＜CityNuｍ；　i++）
｛
ﻩﻩＰrｅCity[i］ = －1；
ﻩ}
ﻩPrｅCitｙ［p_start］ =　—2；
ｗhｉle (PｒeＣity［ｐ_end］ ＝= -1）
｛
ﻩmｉｎ　＝ —1；
ﻩﻩｆoｒ (ｉ = 0；　i<CiｔyNｕm；　i++)
ﻩ iｆ　（PreＣity［i］ !=　-1）
ﻩ {
ﻩﻩ fｏr （j　= ０；　j＜CiｔyNum； j++）
if (ＰreCｉty[j]　＝=　－1 &＆　matx［i]［ｊ］>０ ＆＆ （ｍiｎ<0　｜| ｍａｔx［i][j］<mｉn)）
ﻩ {
ﻩ prｅ = i； pos = ｊ；　min ＝ maｔx［ｉ］［ｊ]；
ﻩﻩﻩ}
ﻩ}
PreCity[pｏs] = pｒe;
ﻩ｝
ﻩDiｊｋｓｔｒa_Output(ｍatｘ， PreCiｔy， p＿enｄ,　TravelTypｅ）；
｝
五、测试分析
1、 添加城市
在主菜单下,用户输入１，添加城市名称。

ﻩ（图２、4添加城市）
2.删除城市
在主菜单下，用户输入2，删除已添加城市名称.

ﻩﻩ （图2、５删除城市)
3.添加交通路线
在主菜单下，用户输入３，已添加城市名称。添加起始城市、终点城市名称、乘车类型、乘车班次、起始时刻、终点时刻、与票价。

ﻩ (图２、6添加交通路线）
４.删除交通路线
输入班次号，删除交通路线

ﻩﻩ （图2、7删除交通路线）
５。查询最小费用交通路线

ﻩﻩﻩ(图2、8　查询最小费用交通路线)
６。查询最快交通路线

ﻩ （图2、9查询最快交通路线)
7。清除屏幕
８.退出
六、用户手册
使用本系统时，用户需先向程序添加城市后，在已有城市基础上添加已有城市得路线与使用各项功能。
七、调试报告
程序运行无错误,但当系统输入其她无储存内容时程序会意外中断,代码需要优化。
八、程序清单
＃include　”stdafｘ、ｈ”
#ｉncludｅ <sｔdｉo、h＞　
＃inｃｌudｅ 〈ｓｔrｉng、h>
#iｎcｌude <sｔdlｉｂ、h>
#dｅfine EＲR 0
＃define OK 1
#define Dｉj_MAXN １０0
#define MＡX_VERＴEＸ_NUＭ 1００
＃definｅ　MAX_STRING_ＮUM　100
＃deｆiｎe MAX_TRAFFIC＿NUＭ 100
cｏｎst ｃhaｒ CitｙＦile［］ = "cｉty、ｔxt"；
ｃonｓt　char TraiｎFiｌe［] ＝ ＂ｔraiｎ、txt";
ｃonst　chａｒ FliｇhtＦile［］ ＝ ”ｆliｇｈt、txt”；
ｔｙpedef sｈort inｔ ＣityＴyｐe；/／CityＴype 定义短整形得变量
typedef ｓtrucｔ ＴraffiｃＮode
｛
cｈar name［MAＸ_SＴRIＮG_ＮUM]; //班次　//MＡX_STRINＧ_ＮＵM最为１0
int StartTime, StopTime; //起止时间　
ﻩinｔ EｎｄCity； //该有向边指向得顶点在数组中得位置,即该城市编号
int Cost； //票价
} TｒaｆficＮｏdｅＤａt；
typｅdef stｒuct ＶNode
｛
ﻩCｉｔyTｙpｅ ciｔy;
ﻩint TrａinNum, FligｈtＮum; /／标记下面Trａin数组与Fligｈt数组里元素个数
ﻩTraｆficNoｄｅDaｔ　Tｒaiｎ［MAX＿ＴＲAFFIC_NUＭ］; //数组成员为结构体，记录了到达城市、起止时间、票价与班次　
ﻩTrａffｉcNｏdｅDat　Ｆlight[MAＸ＿ＴＲAFＦＩC_NUM］；
/／ inｔ Cost； //遍历时到达该城市得耗费（时间或者费用)
}　ＶNodeDat;
ｔypedeｆ ｓtruct PＮｏde
{
int City；
ﻩint　TraNｏ；
｝ PNoｄeＤat；
ＶNodeＤat AdｊList[MAX_VEＲTEX_NUM］；
char CitｙName［ＭＡX＿VERTＥX_NUM］[MAＸ_ＳTRIＮG_NUM］； //城市名，采用第一下标为该城市在本程序中得编号　
int　CityＮuｍ； //城市数目
PＮoｄｅDaｔ　Pａth[MAＸ＿ＶＥＲTEX_NＵＭ]; //存储临时最小时间路径　
PＮｏdｅＤat　MｉnＰath[MAX_VＥRＴEX＿NUM］； ／/存储搜索到当前得最小时间路径
inｔ　MｉnTｉme, StarｔＴimｅ；
iｎt curPａtｈ;
int ShoｗＭenu(）
｛
pｒintf(＂\ｎ|＊＊***＊**＊*＊＊*＊＊**＊欢迎使用交通咨询系统＊＊＊***＊｜\n")；
pｒｉｎｔf（”\n｜-—－－－－—---—－——————1： 添加城市－-－————-——－--—-—|＂）；
ﻩprintf（＂\n｜－——－—－—-—-——－—-——-２： 删除城市－---———--－-－--－—|＂）；
prinｔf(”\n|—－－——－-－-—-－—-－—－—3： 添加交通路线－－—-——-—-——－｜＂)；
prｉｎtｆ（"\ｎ|—-－——--－—-——-－－-－－4： 删除交通路线-——---－-－－-—｜”)；
printf（"\n｜—-—-————－－－-－－—－—－5： 查询最小费用路线——－－—－--｜"）;
priｎｔｆ（"\n|—----－—－—－——-—-———6： 查询最快路线---－---－—-——｜")；
prｉnｔf（＂\n｜——-—－-－-—-—---———-7：　清除屏幕－－－---—－－－－——－-－｜"）；
ﻩprintf(”\ｎ｜－－—－—————-—-—-———－0:　退出-－－-—-－—－-----－－—-－—|＼n＂)；
ﻩｐriｎtｆ（＂＼n|＊＊*＊＊***＊＊*o(∩_∩）o o（∩_∩)o　*＊＊＊＊***＊＊＊**＊|\ｎ"）；
ﻩpriｎtf(”\ｎ请输入您得选择：＂）;
retｕrn　1；
｝
void ＣopｙRigｈt(）
｛
ﻩpriｎtf(＂\n”)；
}
iｎt　SeekCiｔy（ｃhar *name） //寻找城市
｛
ﻩint i；
ｆｏｒ （i　= 0；　i〈ＣitｙNuｍ；　i++）
ﻩ｛
if （ｓtｒcmp(name，　CitｙNaｍｅ[i］） == 0) //比较函数,若相等，则返回ｉ值
ﻩ {
ﻩ reｔｕrn i；
ﻩ｝
}
ﻩretuｒn　-１;
}
／/==＝＝======＝＝=======＝=====＝=＝==========＝==＝===Eｄit　Inｆo＝===＝=====＝=＝==＝＝========＝＝=====＝===＝＝=＝======＝==＝==
int　SaveＳysIｎfo() ／/向程序输入数据
｛
FILE *fp;　iｎt i， j， tｏtａl；
ｆp = fopｅn（CitｙFile， "w"）; /／打开ＣitｙFile文档
fｐrｉntf（ｆp，　＂%d\n”, CityNum）;　/／往文档中写城市得数量
ﻩfoｒ (i = ０；　ｉ<ＣiｔyNum; i++）
{
ﻩfpriｎtｆ(fp, ＂％s\n”, CiｔｙNaｍe［ｉ])；　／/往文档中写城市得名字
ﻩ｝
ﻩfcloｓe（fｐ)；／/将ＣityFile文档关闭
ﻩｔoｔal　= 0；
fｐ =　fｏpｅｎ(TｒainFｉlｅ, "w”）；//打开ＴrainFile文档　
ﻩfor (i = ０; i<CｉtyNum； i++)　／／计算列车班次得数量
ﻩ｛
ﻩtｏtal += ＡdjList[i］、TrainNum；
｝
ﻩfｐriｎtｆ（fｐ, ”％ｄ\n"， toｔal）;　/／往文档中写列车班次得数量
ﻩｆｏr （i =　0; i〈CitｙNｕｍ；　ｉ++） //
ﻩ{
ﻩfoｒ (j = ０; j〈AdjLisｔ［i］、TraｉnＮｕm;　j＋＋) ／／往文档中写列车得车次、始发城市、终点城市
ﻩ {
ﻩ fpｒintf(fp，　”％s %s ％s "，　ＡdjList[i］、Ｔrａｉn[j］、naｍe,
ﻩCiｔｙNamｅ[i]，
ﻩ CityＮamｅ[AｄjＬiｓt［i]、Ｔrain［ｊ］、ＥndCity]）;
ﻩﻩ ｆpriｎｔf(fp， "％2ｄ:％2d ％２d：%2d　％d\n”， AｄjLｉst［i］、Ｔｒａｉｎ［j]、ＳtaｒtTime / 60,　//往文档中写
ﻩﻩ ﻩAdjLisｔ[i］、Tｒain[j]、StartＴimｅ ％ 60，
ﻩﻩﻩ AdjLiｓt［ｉ］、Traiｎ[j］、ＳtopTiｍe / 60，
ﻩ ﻩAdjList[ｉ］、Train［j]、StopTime ％ 6０，
ﻩ AｄjＬisｔ［i］、Ｔrａiｎ[j］、Ｃｏsｔ）；
ﻩ}
}
ﻩfｃｌose(fｐ）； tｏtal　=　0;
fp = fopen（FｌightFiｌｅ，　"w”）；
ｆor （i = 0； i<CityＮum； i++)
｛
ﻩﻩtoｔaｌ += AｄjList［i］、ＦｌighｔNum;
ﻩ}
ﻩfprｉntf（fp, ”%d＼n”,　ｔotal)；
for （i ＝　0；　i〈ＣitｙＮｕm; i＋＋)
ﻩ{
ﻩfor (j　= ０； ｊ〈AdjLｉｓt［i］、FlighｔNum; j++）
ﻩ｛
fprinｔf（ｆp， "%s　％s %ｓ ”, AdjＬist［i]、Ｆlight［j]、nａmｅ,
ﻩ ﻩＣityNamｅ［ｉ］，
ﻩﻩﻩﻩＣitｙNaｍｅ[AdｊLisｔ[ｉ］、Ｆligｈt[j］、EｎdCity］）;
ﻩﻩfprinｔｆ（fp, "%2ｄ:％２d　％2d：％２d　％d\ｎ",　AｄjLｉsｔ[i]、Flight［j］、StartTime / ６0，
ﻩﻩ AdｊLｉst［i]、Flight[j]、SｔarｔTime % 60，
ﻩﻩﻩ AdjLｉsｔ［i]、Ｆlｉght［j]、StｏpTｉｍe　/ 60,
ﻩ ﻩAｄjLiｓt［i]、Ｆlighｔ［ｊ］、StoｐTｉｍe % 60，
ﻩ ﻩAdjＬist［i］、Fｌｉgｈt［j]、Cｏｓt）；
ﻩﻩ}
}
ﻩｆｃlｏse（fp）； return 1;
}
ｉnt InsertCｉty（chaｒ *Name) ／／添加城市
｛
sｔrcpy(CityName[CitｙNｕm]， Name);
ﻩAｄjList［ＣitｙNum］、ｃity =　CiｔｙＮｕm；
AdjList[ＣｉtyNuｍ]、ＦlighｔNuｍ = 0；
AdｊList［ＣｉtyNum］、TrａinＮum = 0;
CｉｔｙNｕm+＋;
ﻩｒetuｒn　1;
}
int DｅｌＣity(ｃｈａｒ ＊Ｎame） //删除城市
｛
int　city， i, j，o=1，ｋ=1;
ﻩcｉty ＝ SeekCiｔｙ(Name)；
prｉｎｔf("%s",Name）；
ﻩwhｉlｅ (ｔｒue）
ﻩ{
ﻩ whｉlｅ （CityName［k] ！＝ Namｅ）
ﻩ ｛
k+＋;
｝
ﻩﻩｉf （k 〉 ＣityNum）
ﻩ｛
ﻩ o－—;
ﻩpｒiｎｔf（"未找到此城市，请重新输入！"）；
ﻩﻩreｔurｎ ０；
｝
ﻩ ｆor　(i = ｃiｔy; i ＜ CiｔｙNuｍ — 1； ｉ++) //???可能city就是从０开始得
ﻩ{
ﻩ ｓｔrcpy（ＣityNａme［i], CitｙName[i　＋ 1]）；
AｄjLiｓt[i]、FliｇhｔNum = AdｊLisｔ［ｉ　+ １]、FlｉghtNuｍ；
ﻩﻩﻩAdjＬｉst［i］、TrainＮum = ＡｄjLiｓt［ｉ +　1]、TrainNum;
ﻩﻩﻩfor　(j　= 0; j　＜ AdjＬiｓｔ［i］、FlighｔNuｍ; ｊ++） //为什么没有火车得?？
ﻩﻩ ｛
ﻩ ﻩﻩAdjＬist［i］、Fｌight[j]、Coｓｔ　= AdjList[i ＋ １］、Flighｔ［j]、Ｃost;
ﻩ ﻩﻩＡdjLiｓt［ｉ]、Ｆlｉｇht［j］、EndCｉty　= ＡdjList[i + １］、Flighｔ［ｊ］、EndCiｔy;
ﻩﻩ ﻩｓｔrcpy（AdjＬist[i]、Ｆlｉght［j］、ｎame, AdjLiｓt［i + １]、Fligｈt[j]、naｍe）；
ﻩﻩﻩﻩＡdjLｉst[i]、Ｆlｉght［ｊ]、SｔartTime ＝ AｄｊＬｉst［i +　１］、Ｆliｇht[j］、StartＴimｅ；
ﻩﻩﻩ AdjＬist［i］、Ｆlight［ｊ]、StopTimｅ = ＡdｊLiｓt［i + 1］、Ｆlighｔ[j］、StopTimｅ；
ﻩﻩ ｝
ﻩﻩ}
ﻩCityNum-—；
ﻩ｝
ｒetuｒn　１；
}
int IｎｓertTraiｎ(chａr ＊train, cｈar ＊StartCity, ｃhａｒ　＊EndＣitｙ, int　SｔａrtTime, ｉｎt ＥndTｉme, int cｏst）
｛
ﻩｉnt i，　ｊ; //InsertTraｉn（ｎame,s_cｉtｙ，e＿city,ｓ_hour*6０+s_miｎｕte,e_ｈour*6０+ｅ_minute,cost);
i = SｅeｋCｉty(ＳtartCｉty）;
j = SeｅkCity（EｎdCｉtｙ);
AｄｊList［i］、Traiｎ［AｄｊList［i］、TraiｎNum]、Ｃoｓt = cost;
AdjLｉst［i］、Ｔｒaｉn［ＡdjLiｓt［ｉ］、TraｉnNum]、EｎdCiｔy　= j；
ﻩAdｊLiｓt［ｉ］、Ｔraｉｎ［ＡdjＬiｓt［i］、ＴraｉｎNuｍ］、StarｔＴimｅ　＝ ＳｔａrtＴime；
AｄｊＬist［ｉ］、Traiｎ［AdｊList［i]、TraｉnＮum]、StopＴime = EndTime;
ﻩstrｃpy(AdjLiｓｔ［i］、Tｒａｉn［ＡdjList［i］、TrainNum］、namｅ, train)；
AdjＬｉsｔ[ｉ］、TｒainNum＋＋；　//火车得数加1
retuｒｎ １；
}
ｉnt　ＩｎsｅrtＦliｇht(char　＊ｆｌiｇht,　cｈar *StａｒｔCity， char ＊EｎdCity,　int StarｔTime, inｔ EｎdTiｍe， int ｃost)
｛
ﻩｉnt i, j；　
i　＝ SeekＣitｙ(StａｒtCiｔy）；
j = SeekCity（ＥndCity）；
AdｊList［ｉ］、Flｉght[AｄjLiｓt［i]、FｌightNum］、Ｃost = cost；
ﻩＡdjＬｉst[ｉ]、Flight[ＡｄjLisｔ［i］、FlｉghtＮum]、EｎdCity　＝ j；
ﻩＡｄjＬiｓｔ［i］、Flｉgｈt[AdjList[i］、FlｉghtNuｍ]、SｔartTiｍe = StａrtTime；
AdjＬisｔ[i］、Fｌｉghｔ[AdｊList［i]、FlｉghｔＮｕm］、SｔopＴiｍe =　EndTime;
ﻩstrcｐy（AｄjList[i］、Traiｎ[AdjＬist［i]、ＦlightNum］、nａmｅ， flight)；
ﻩＡdjList［ｉ］、FliｇｈtNum++;
return 1；
｝
iｎt　DelＰaｔｈ(char ＊name）
｛
ﻩint i, ｊ,　fｌag ＝ 0;
ﻩfｏｒ （ｉ = 0； ｉ<ＣityNum; i+＋)
{
ﻩfor　(j = 0； j〈AｄｊLisｔ［i］、FlightNuｍ； j+＋）　/／注意ｊ就是从0开始得
ﻩﻩif （strcmｐ(ＡｄjＬist［i］、Flighｔ［j]、ｎaｍe，　name） == 0)
ﻩﻩ{
ﻩﻩflag = １； bｒeａk;
ﻩ}
ﻩif　（flaｇ）
{
ﻩ ｆoｒ （; ｊ＜AdjLisｔ［ｉ］、FliｇhtNum —　１; ｊ++) //把删除得航班后得每个航班向前移一位
ﻩﻩ ｛
ﻩ AｄｊLｉst［ｉ]、Fligｈｔ[j］、Cｏst = ＡｄjLｉｓt[i]、Fligｈt［j　+ 1］、Ｃost;
ﻩﻩ AｄjList[ｉ］、Fligｈt[j]、EnｄCｉty =　AｄｊＬiｓt[i］、Flight[j + 1]、EndCity；
ﻩﻩﻩstrcpy(AdjList[i]、Fligｈt[j]、naｍe， AｄjList［i］、Fliｇht［j + 1］、name）；
ﻩﻩﻩ AdjLｉst[ｉ]、Ｆlｉgｈt[ｊ]、SｔartTime = AdjList［ｉ]、Fｌighｔ[j　+ 1]、ＳｔartTｉme;
ﻩﻩ AdjList[i]、Fｌight［j］、ＳtopTimｅ　= ＡｄjLｉｓｔ［i］、Ｆlight［ｊ + 1]、ＳtoｐTｉme；
ﻩﻩ}
ﻩAｄｊLｉst[i］、FｌｉghtNuｍ—-; ｂｒeak；
ﻩ}
for　(ｊ　= 0； j<AdjLｉｓt[i]、TraｉｎＮuｍ；　j++)
ﻩﻩiｆ (strｃmp（ＡdjＬiｓt［ｉ]、Ｔraiｎ[j]、nａme, ｎame) =＝ 0)
ﻩ {
ﻩﻩflag ＝ １; ｂｒeak；
ﻩ }
ﻩ ｉf （ｆlag)
{
ﻩﻩfor (； j<AdjLiｓt［i］、TｒainＮum - １； j++） ／/把删除得列车后得每个列车车次都前移一位
{
ﻩﻩﻩﻩAdjList[i］、Train［j]、Cｏst　＝　AdjLｉsｔ[i］、Trａin［ｊ + 1］、Cost；
ﻩ ﻩ AdjＬisｔ［ｉ］、Tｒain[j]、ＥｎdCｉｔy = AdjLｉst［i］、Ｔraiｎ［j + １]、ＥndＣity;
ﻩ ﻩsｔｒcpｙ（AdjList［i]、Ｔrａin[j］、namｅ, AdjＬｉsｔ［ｉ］、Traiｎ[j + 1］、naｍe）；
ﻩﻩ AｄjＬist[i］、Traｉn［j］、StａrｔTiｍｅ ＝ AｄｊLiｓt［i]、Train[j　+ 1］、SｔartＴime;
ﻩﻩ AdｊList[i]、Traiｎ［j］、ＳtｏｐＴimｅ =　AdjLisｔ[i］、Trａｉn[ｊ　+ 1]、StopTｉｍｅ;
}
ﻩ AdｊＬist［i]、ＴrainNum—-； brｅak;
ﻩﻩ｝
｝
ﻩreｔｕrn 1;
｝
/／＝=====＝=====＝=====＝======＝=＝==＝=＝=＝==＝＝=＝====＝Check Ｉnｆｏ====＝==＝===＝==＝=＝＝=====＝==＝======＝===＝=＝====＝==＝
void Dijksｔra＿Output(ｉｎt matx[Diｊ_MＡＸＮ］[Dij＿MAＸN］， ｉnｔ　PｒｅCity［Ｄij＿MAXN], iｎt p＿end， ｉnt TrａveｌType)
｛
ﻩinｔ traｃｋ［Ｄij_MＡXN]；
ﻩｉnt i =　0, j,　k, min, ｔｍp， enｄ， coｓt　＝ ０；
j = p_ｅnd;　traｃk［i＋+］ ＝ j;
while (ＰreCity［j] 〉= ０)
｛
ﻩﻩcost += ｍａtx［PreCity［j]］［j];
ﻩ track[i++］ = j =　PreＣｉty［ｊ］;
}
printｆ（"\ｎTracｋ　Way:"）；
ｉf （!ＴrａｖｅlＴype）
ﻩ｛
ﻩ foｒ （i——;　i〉０;　ｉ--）
ﻩﻩ｛
ﻩ ﻩｐｒintf(”＼n％s："， CityＮａme[trａck［i]]）;
ﻩﻩﻩｅnｄ　= traｃｋ[i - 1］； min ＝ 3276７；
ﻩ ﻩfoｒ （k = ０；　k〈ＡdjＬｉst［ｔrａcｋ[i］］、ＴraｉnNum; ｋ+＋）
iｆ （ＡdjLｉsｔ［ｔrａcｋ[i］]、Traｉn[k]、EndCｉｔy ==　end＆＆ｍiｎ〉ＡdjList［trａck［i］］、Train[k］、Ｃost）
ﻩ {
ﻩﻩ min　=　ＡdjＬｉｓt[tracｋ［i］]、Ｔrain［k］、Ｃｏｓt；
ﻩtｍp = ｋ;
ﻩ ｝
ﻩ pｒintf（”%s”, AｄjList［traｃｋ［i]]、Traｉn［tmp]、naｍe）;
ﻩ printｆ（"％2d：%2d－%2d：％２d＂， AdjLｉsｔ[tｒack［i]]、Train[ｔmp]、StarｔTimｅ　/ 60, ＡｄjLｉsｔ[traｃk［i]]、Traｉn［tmp］、StaｒtＴime ％ 60, AｄjLiｓt［tracｋ［i］］、Traｉｎ［ｔmｐ]、SｔopTiｍe / 6０， AdｊLiｓt［trａck［ｉ］]、Traiｎ[tmp]、ＳtoｐTｉme ％　6０)；
ﻩ}
｝
ﻩelsｅ
ﻩ｛
for (i——; i>0; ｉ－-）
ﻩﻩ{
ﻩ printｆ（"\n％s：＂， ＣityNａｍe[ｔｒack［i］]);
ﻩﻩend =　ｔｒaｃk[i　— 1]； miｎ　= 3２7６7;
ﻩﻩﻩfor　（k =　0; k<AdjLisｔ[ｔrack[i］]、ＦlightNuｍ； k++)
ﻩ ｉｆ （AｄjLiｓt［track［i]］、Train［k］、EｎｄＣｉｔy == end&&miｎ〉AdjLｉst［track［i]］、Ｆｌigｈt[ｋ]、Cｏｓt)
ﻩﻩ｛
ﻩﻩｍin ＝　AｄjList[ｔrack［i］]、Fｌighｔ[k］、Cost；
ﻩ ﻩﻩtｍp =　k;
｝
ﻩ printf（”%ｓ＂， AdｊList［tｒaｃｋ[i]]、Ｆlｉｇht[tmp]、ｎaｍe);
ﻩ prｉｎtf（"％2d:%2d—％2d:％２d”, AｄｊLisｔ［ｔrack[i]]、Flight［tmp]、SｔａrｔTime / 6０, AdjＬisｔ[tｒack［i]］、Fｌiｇｈｔ[tmｐ］、StaｒtＴｉmｅ % 6０， AdjLiｓｔ［ｔrack[i]］、Flight[tmｐ］、StｏpTｉme / ６0， AｄjLiｓt［trａck［i]］、Fliｇht［tmp］、ＳtｏpTime ％ ６0)；
}
｝
printf（＂\n%s: DＥSTINATＩOＮ！”，　CiｔyNamｅ［tｒack[0]］）;
prｉntｆ(”\nMin Cost : ％d\n"， cost