0807020213刘继凤-数据结构课程设计.doc

湖南科技大学面数据结构（C语言）课程设计报告湖南科技大学 数据结构（C语言）课程设计报告中国省会铁路网查询系统学生姓名： 刘 继 凤 学 号： 0807020213 年级专业： 08级信息与计算科学 班 级： 信息二班 指导老师： 学 院： 数学与计算科学学院 同组成员： 湖南湘潭提交日期：2010年6月目 录1、需求分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32、程序主要功能. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33、系统框架图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34、界面表现. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45、程序源代码. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66、程序设计不足. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167、课程设计总结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168、参考文献. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16中国省会铁路网查询系统一、 需求分析 在现代化生活中，坐火车出行已经日益普遍，所以铁路网查询系统有着十分重要的作用，然而，用大型软件系统来于小型的企事业单位与个人，不啻于“杀鸡用牛刀”，因此小型的的软件对于这种单位和个人自然有十分重要作用。本人出与这种目的制作了这个中国省会铁路查询系统，这个系统大致上显示有各省会之间的距离信息，可以很方便的让用户得到由省会间的最短坐火车的线路。二、程序的主要功能A. 显示线路地图功能：可以显示全国34个省会和它们之间的线路与距离信息。B. 由网生成最小树功能：可以显示遍历全国省会的最短乘车线路。C. 两省会间最佳线路查询功能：可以显示由用户指定的两个省会城市间的最短距离三、系统框架图中国铁路网查询系统铁路网显示铁路网遍历生成最小树求最短距离本系统说明退出本系统四、界面表现图 1系统主界面图 2铁路网显示界面图 3线路查询界面图 4系统说明界面五、程序源代码#include #include #include #define Max 99999typedef struct int Vex35; /顶点 int Arc3535; /边 liu;bool visit35= 0 ;void Print( int i )/由省会代号输出显示省会名称 switch( i ) case 1: printf( 哈尔滨 ); break; case 2: printf( 长春 ); break; case 3: printf( 沈阳 ); break; case 4: printf( 呼和浩特 ); break; case 5: printf( 乌鲁木齐 ); break; case 6: printf( 银川 ); break; case 7: printf( 北京 ); break; case 8: printf( 天津 ); break; case 9: printf( 太原 ); break; case 10: printf( 石家庄 ); break; case 11: printf( 西宁 ); break; case 12: printf( 兰州 ); break; case 13: printf( 济南 ); break; case 14: printf( 西安 ); break; case 15: printf( 郑州 ); break; case 16: printf( 南京 ); break; case 17: printf( 成都 ); break; case 18: printf( 合肥 ); break; case 19: printf( 上海 ); break; case 20: printf( 重庆 ); break; case 21: printf( 武汉 ); break; case 22: printf( 杭州 ); break; case 23: printf( 南昌 ); break; case 24: printf( 长沙 ); break; case 25: printf( 贵阳 ); break; case 26: printf( 拉萨 ); break; case 27: printf( 昆明 ); break; case 28: printf( 福州 ); break; case 29: printf( 台北 ); break; case 30: printf( 南宁 ); break; case 31: printf( 广州 ); break; case 32: printf( 澳门 ); break; case 33: printf( 香港 ); break; case 34: printf( 海口 ); break;default: printf( 有误！无法到达！ ); break; liu Feng( void ) /初始化铁路网 liu va; int i, j; for( i=0; i=34; i+ ) va.Vexi = i; for( i=0; i=34; i+ ) for( j=0; j=34; j+ ) va.Arcij = Max; va.Arc12 = va.Arc21 = 242; va.Arc24 = va.Arc42 = 1477; va.Arc23 = va.Arc32 = 305; va.Arc512 = va.Arc125 = 1892; va.Arc46 = va.Arc64 = 676; va.Arc47 = va.Arc74 = 668; va.Arc37 = va.Arc73 = 703; va.Arc38 = va.Arc83 = 704; va.Arc612 = va.Arc126 = 468; va.Arc78 = va.Arc87 = 137; va.Arc710 = va.Arc107 = 227; va.Arc1112 = va.Arc1211 = 216; va.Arc1126 = va.Arc2611 = 1972; va.Arc813 = va.Arc138 = 357; va.Arc1217 = va.Arc1712 = 1172; va.Arc1214 = va.Arc1412 = 676; va.Arc910 = va.Arc109 = 220; va.Arc914 = va.Arc149 = 651; va.Arc915 = va.Arc159 = 577; va.Arc1015 = va.Arc1510 = 412; va.Arc1013 = va.Arc1310 = 304; va.Arc1315 = va.Arc1513 = 668; va.Arc1316 = va.Arc1613 = 667; va.Arc1415 = va.Arc1514 = 511; va.Arc1417 = va.Arc1714 = 842; va.Arc1518 = va.Arc1815 = 602; va.Arc1516 = va.Arc1615 = 697; va.Arc1618 = va.Arc1816 = 155; va.Arc1619 = va.Arc1916 = 315; va.Arc1727 = va.Arc2717 = 1100; va.Arc1720 = va.Arc2017 = 315; va.Arc1718 = va.Arc1817 = 1708; va.Arc1821 = va.Arc2118 = 384; va.Arc1819 = va.Arc1918 = 457; va.Arc1922 = va.Arc2219 = 188; va.Arc2221 = va.Arc2122 = 999; va.Arc2223 = va.Arc2322 = 629; va.Arc2228 = va.Arc2822 = 740; va.Arc2024 = va.Arc2420 = 1094; va.Arc2021 = va.Arc2120 = 1232; va.Arc2124 = va.Arc2421 = 362; va.Arc2123 = va.Arc2321 = 355; va.Arc2325 = va.Arc2523 = 1264; va.Arc2331 = va.Arc3123 = 948; va.Arc2328 = va.Arc2823 = 662; va.Arc2425 = va.Arc2524 = 949; va.Arc2527 = va.Arc2725 = 639; va.Arc2530 = va.Arc3025 = 875; va.Arc2531 = va.Arc3125 = 1444; va.Arc2730 = va.Arc3027 = 828; va.Arc3031 = va.Arc3130 = 817; return va;void Ji( void )/输出显示铁路网信息 printf( ntt 中国省会城市之间的铁路网nttttttt注：（单位：公里）nn ); printf( ttttttt 哈尔滨n ); printf( tttttttt 242 n ); printf( 乌鲁木齐ttt _ 长春n ); printf( ttt /t 1477tt/ 305 n ); printf( tt 呼和浩特tt 沈阳n ); printf( 1892tt/ 676 _ _/ n ) ; printf( tt 银川t 668 / 703 /n ); printf( _ / tt227北京137 / 704n ); printf( tt 西宁 / 468t 220 / 天津 _/n ); printf( tt /216兰州 t 太原 - 石家庄 / n ); printf( tt / / 651/ / 304 / 357n ); printf( tt / 676 /577/ /412_ 济南 n ); printf( t / 1172 / / / 668 n ); printf( t / 西安 - 郑州_ 667n ); printf( t / / / 511 697 /n ); printf( t / / 842 /602 _ 南京 _n ); printf( / / / 1708 /155 457 315n ); printf( / 成都_ -_ 合肥 - 上海n ); printf( / / 315 1232 384/ _ 杭州/ 188n ); printf( / 1972 重庆 - 武汉/ 999_/ / n ); printf( / 1094362/355南昌/ 629 /n ); printf( / 1100 949/长沙 / 740n ); printf( / _ 贵阳 _/ 662 /n ); printf( 拉萨 /639 1264 / _ n ); printf( ttt 昆明 875 1444 / /n ); printf( ttt _ /948 福州n ); printf( ttt 828 /817 台北n ); printf( ttt 南宁 - 广州n ); printf( ttt 澳门 香港n ); printf( nttt 海口n ); printf( ntt特别说明： 本图为现实模拟，如有不准确的地方还请见谅！n ) ; void DFS ( liu va, int v )/从第v个顶点出发递归地深度优先遍历 static int i=0; visitv = 1; if(i=0) Print( v ); else printf( ); Print( v ); for( i=1; i=34; i+ ) if( (va.Arcvi88888)&!visiti ) DFS( va, i ); void DFSTra( liu va, int v )/对网va做深度优先遍历 int a; for( a=v; a35; a+ ) if( !visita ) DFS( va, a );void PrimTree( liu va, int v )/用普里姆算法生成最小树 struct int vex; int low; close34; int i, j, k, min; for( i=0; i34; i+ ) closei.vex=#; closei.low = Max;for( i=1; i34; i+ )if( va.Arcvi88888 ) closei-1.vex = va.Vexv;closei-1.low = va.Arcvi;for( i=1; i34; i+ ) min = Max; for( j=1; j=34; j+ ) if( closej.low min&closej.vex!=# ) min = closej.low; k = j; i=closek.vex; j=va.Vexk+1; printf( tt ); Print( i ); printf( ); Print( j ); printf( %d 公里nn, closek.low ); closek.low = 0; closek.vex = #; for( j=1; j=34; j+ ) if( va.Arck+1jclosej-1.low&closej-1.low!=0 ) closej-1.vex = va.Vexk+1; closej-1.low = va.Arck+1j; void ShortPath( liu va, int v1, int v2 )/用迪杰斯特拉算法求显示v1和v2间的最佳线路 int d35, p3535, min; bool f35; int i, j, v, k=0, m; for( i=0; i35; i+ ) fi = 0; di = va.Arcv1i; for( j=0; j35; j+ ) pij = 0; if( diMax ) piv1 = 1; pii = 1; dv1 = 0; fv1 = 1; for( i=2; i35; i+ ) min = Max; for( j=1; j35; j+ ) if( !fj ) if( djmin ) v = j; min = dj; fv = 1; for( j=1; j35; j+ ) if( !fj&( min+va.Arcvjdj ) ) dj = min + va.Arcvj; pj = pv; pjj = 1; m = 0; for( i=1; i35; i+ ) if( pv2i=1) k+; if( m=0 ) Print(i); else printf( , va.Arcmi ); Print(i);m=i; if( k=0 ) printf( 没有线路可以抵达 ); Print(v2); else printf( nnnnnnntttttt全线路程为 %d 公里 n, dv2 );int main( )/主函数 liu va; time_t nowtime; struct tm *timeinfo; time( &nowtime ); timeinfo = localtime( &nowtime ); int year, month, day, hour, min, x, v1, v2; year = timeinfo-tm_year + 1900; month = timeinfo-tm_mon + 1; day = timeinfo-tm_mday; hour = timeinfo-tm_hour; min = timeinfo-tm_min; va = Feng(); system( cls );/输出显示主界面 printf(nt 系统时间：|-%d/%d/%d %d:%d-| n, year, month, day, hour, min ); printf( t|-| ); printf(ntt*); printf(nntt*中国省会铁路网查询系统*); printf(nntt*); printf(nntt* 1.中国省会铁路网 *); printf(nntt* 2.北京遍历铁路网 *); printf(nntt* 3.北京最小生成树 *); printf(nntt* 4.两城间最小路径 *); printf(nntt* 5.系统帮助与说明 *); printf(nntt* 6.退出铁路网系统 *); printf(nntt*); printf( nt|-|n ); printf( 请选择操作： ); scanf(%d, &x); switch( x ) case 1: system( cls ); Ji(); system( pause ); main(); case 2: system( cls ); printf( t|-|n ); printf(nt 系统时间：|-%d/%d/%d %d:%d-| nn, year, month, day, hour, min ); printf( t|-|nnnt ); DFSTra( va, 1 ); system( pause ); main(); case 3: system( cls ); printf( t|-|n ); printf(nt 系统时间：|-%d/%d/%d %d:%d-| nn, year, month, day, hour, min ); printf( t|-|nn ); PrimTree( va, 1 ); system( pause ); main(); case 4: system( cls ); printf( t|-|n ); printf(nt 系统时间：|-%d/%d/%d %d:%d-| nn, year, month, day, hour, min ); printf( t|-|n ); printf( nt注:各省会城市代号:n ); printf( nt1、哈尔滨 2、长春 3、沈阳 4、呼合浩特 5、乌鲁木齐 ); printf( nnt6、银川 7、北京 8、天津 9、太原 10、石家庄 ); printf( nnt11、西宁 12、兰州 13、济南 14、西安 15、郑州 ); printf( nnt16、南京 17、成都 18、合肥 19、上海 20、重庆 ); printf( nnt21、武汉 22、杭州 23、南昌 24、长沙 25、贵阳 ); printf( nnt26、拉萨 27、昆明 28、福州 29、台北 30、南宁 ); printf( nnt31、广州 32、澳门 33、香港 34、海口n ); pp:printf( ntt请输入出发城市的代号： ); scanf( %d, &v1 ); if( v134|v134|v21 )goto pp1; if( v1=v2 ) printf( nntt您输入的两个省会城市代号相同，请重新确认后再输入！n ); goto pp; system( cls ); printf( t|-|n ); printf(nt 系统时间：|-%d/%d/%d %d:%d-| nn, ye