一、設計內容與設計要求
 1．設計內容：
 出于不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時間盡可能短，出門旅游的游客則期望旅費盡可能省，而老年旅客則要求中轉次數最少。編制一個全國城市間的交通咨詢程序，為旅客提供兩種或三種最優決策的交通咨詢。系統可實現城市信息的管理以及兩種交通工具火車和飛機信息的管理，并提供最少中轉次數、最少時間和最少路費的交通路線咨詢。
 設計思路：首先用一種存儲結構表示旅途工具、出發點、終點、旅途時間和價格。對于要求選擇中轉次數最少的路徑，可對圖進行廣度搜索得到。對于尋找最少時間和最少路費的路徑，實際上就是圖最短路徑問題。可采用Dijkstra算法。
 2．設計要求：
課程設計報告正文內容
需求分析：課題的主要功能；
總體設計：課題的功能模塊的劃分（要求畫出模塊圖）；
程序流程圖：主要功能的實現（至少要有一個主要模塊的流程圖）；
程序調試及體會；
參考書目；
附錄（所有程序的原代碼，要求對程序寫出必要的注釋）。

書寫格式
 a．要求用A4紙打印成冊
 b．正文格式：一級標題用3號黑體,二級標題用四號宋體加粗,正文用小四號宋體;行距為22。
c．正文的內容:正文總字數要求在5000字以上（不含程序原代碼）。
 d．封面格式如下頁。

考核方式
 指導老師負責驗收程序的運行結果，并結合學生的工作態度、實際動手能力、創新精神和設計報告等進行綜合考評，并按優秀、良好、中等、及格和不及格五個等級給出每位同學的課程設計成績。具體考核標準包含以下幾個部分：
 a．平時出勤 （占10%）
 b．系統需求分析、功能設計、數據結構設計及程序總體結構合理與否（占10%）
 c．程序能否完整、準確地運行，個人能否獨立、熟練地調試程序（占40%）
 d．設計報告（占30%）
 注意：不得抄襲他人的報告（或給他人抄襲），一旦發現，成績為零分。
 e．獨立完成情況（占10%）。

課程驗收要求
 a．運行所設計的系統。
 b．回答有關問題。
 c．提交課程設計報告。
 d．提交軟盤（源程序、設計報告文檔）。
 e．依內容的創新程度，完善程序情況及對程序講解情況打分。
 
二、進度安排
 班級： 信息科學0501、0502、0503
 主講教師：郭鵬
 輔導教師：周鐵山、曹燚
 時間安排：
 第 18 周  
 星期一 分析問題，給出數學模型，選擇數據結構
     星期二 設計算法，給出算法描述
 星期三～星期五 編輯、編譯、調試源程序
        星期六 撰寫課程設計報告
 
 
 
 
 
 
 
 
 
 目        錄

 需求分析············································· 1
 
 總體設計（功能模塊圖）·································3
 
 程序流程圖··········································· 4
 
程序調試············································· 7

體會················································· 8

源程序清單············································9

參考書目·············································24
 
評分表················································25

 

 

 

 

需求分析
一）題目分析：
    1．通過對題目的分析知，是要讓我們能夠通過利用所學的數據結構的基本知識和技能來解決程序設計問，因此在搞程序設計之前先好好的把書復習一遍，弄清楚各個知識之間的聯系。
 2．由題目的分析知全國交通咨詢管理系統是有對城市信息的增加、刪除、修改、保存、查詢、有錯時提示出錯信息等功能，最后對數據進行保存并退出操作系統。由此可知需要將函數模塊化，將它做為一個獨立的函數體去實現它的功能。它可以分為四大功能模塊，每個模塊需要去各個擊破。其中可能用到C語言的指針與鏈表，因此，要先去復習一下C語言課本。
 3．根據這些功能和基本要求，可充分運用我們所學的數據結構的基本知識和技能去逐步的解決。其中將函數進行模塊化。在數據結構中，通過隊列，棧，圖的聲明來實現系統的各種功能的存儲各城市之間乘火車的消耗價格，時間，乘飛機的價格，時間，以及中轉站最少。利用指針和結點來實現城市與城市之間各種操作，而這些知識點都是我們學習數據結構必須掌握和學會運用的。
 4．完成程序功能的設置后，應對程序進行調試，以便在調試中能及時地找出錯誤并加以更正，這樣能使程序功能進一步的完善和正確。這就要求我們在編程和調試過程中養成認真分析和善于發現問題并及時解決的習慣，不懂的及時問老師或者其他同學。   
二）實現方法：
1．圖的實現和聲明
（1）根據題目要求，聲明了一個圖形的數據結構用來存儲任意幾個城市之間的各種信息，其中是把它們的TTime; TPrice; FTime; FPrice;的各種信息用鄰接矩陣存儲起來的。同時運用構造函數，利用特定的值來構造對象。
（2）struct City圖的結構，CreateCity建立鄰接圖，AddCity增加，DelCity刪除，EditCity修改，ShortestPath最小路徑，ShortestPath_DIJ求源點v0到各點的最短路徑 1火車時間最小,2火車金錢最小,3飛機時間最小,4飛機金錢最小，來實現的。
 
2．程序功能的實現
（1）全國交通咨詢信息錄入和增加的實現
 主要是對城市基本信息的輸入，包括（乘火車的價格，乘火車的時間，乘飛機的價格，乘飛機的時間，中轉站次數最少）在程序中只要用AddCity (輸入函數)和ShortestPath(C);來實現。
（2）全國交通咨詢信息顯示的實現
   主要為用戶ShortestPath(C);函數顯示城市之間的基本信息，包括上面錄入的信息和增加的內容。
（3）全國交通咨詢信息載入文件的實現
   在程序中用LoadCity(C);break（）函數來載入文件。
（4）全國交通咨詢信息刪除的實現
在程序中用DelCity(C)函數來實現對有錯的信息進行刪除。
（5）全國交通咨詢信息修改的實現
  在程序中用EditCity(C)（修改函數）來實現，而且可通過按編號或城市名來修改，當找不到要修改的內容時提示用戶可能輸入有誤，重新在輸一遍。
 （6）全國交通咨詢信息的重來  
 CreateCity(C);break重來，實現對錯誤的從新輸入。
 （7）全國交通咨詢信息的保存
  在程序中用SaveCity(C)保存函數來實現，并提示用戶數據已保存。
（8）全國交通咨詢信息的增加
ShowCityDat(C);break， case 2:AddCity(C);break 增加
 
 

 

 

 

 


功能模塊圖
   該課題可以分為如下幾個模塊：控制選擇功能項的main函數、建立鄰接圖的CreateCity(City *C)函數、增加城市的AddCity(City *C)函數、刪除城市的DelCity(City *C)函數、修改資料的EditCity(City *C)函數、求最小路徑的ShortestPath(City *C)函數、求其他最值的ShortestPath_DIJ(City *C,int v0,int k)函數、載入文件資料的LoadCity(City *C)函數、保存資料的SaveCity(City *C)函數、顯示城市之間關系數據的ShowCityName(City *C,int k)函數。
    功能模塊圖如下：
 
 
 
 
 
 
 
 
 
 程序流程圖

輸入int m; 
 
 輸入1（）輸入城市 
 輸入2（）輸入飛機 
 輸入3（）輸入火車 
 輸入4（）刪除飛機 
 輸入5（）刪除火車 
 輸入6（）顯示飛機 
 輸入7（）顯示火車 
 輸入8（）變換飛機 
 輸入9（）保存數據 
 輸入10（）顯示城市 
 輸入11（）顯示最短時間 
 輸入12（）更換飛機 
 輸入13（）錄入數據 
                   e!=0
是 
             否 
  結束 


2）add_city添加函數流程圖：


c_num++ 
 輸入city[c_num] 
結束 

 

3）delete_train刪除函數流程圖：


聲明int j 
for(j=i;j<=t_num;j++) 
 train[i+1]=>train[i]; 
t_num-- 
結束 

 

 

4）show_train顯示函數流程圖：


聲明int i 
輸出id-start-end-time、price 
for(i=0;i<t_num+1;i++) 
 輸出train[i].id-train[i].start-
-train[i].end-train[i].time  train[i].price); 
結束 

 

 

 

 

 

 

 

程序調試

 


心得體會
  一周課程設計很快就結束了，回顧自己所做的課程設計真是困難重重有喜亦有憂。從接觸計算機語言開始我雖然很喜歡這門課程但是我并沒有真正的做過稍微大點課題的課程設計，大多數做的是一些寫算法的題目僅此而已。因此，我在專業里所選的方向也就是計算科學中的算法設計。這一次課程設計讓我意識到我的知識是很零亂，多么的不連貫不系統化，我自感到在C語言以及數據結構方面的知識是那么的不扎實。同時也讓我意識到學習計算機語言是沒有什么捷徑可走的，靠的是平時的多練習，多上機操作才可能有好的效果。
 在拿到這個題目的時候我仔細的分析了一番，覺得自己只能寫一寫匡架性的東西出來而根本不知道如何去實現每一個函數。會用一點隊列的知識（比如通過隊列的先進先出的特點來存儲各種乘火車方式和乘飛機方式的時間，價格，中轉站最少的最優值），也會根據要求在模塊定義所需要的函數，但是不知道如何去實現，可能是由于C語言中的函數、指針及鏈表沒學到多少。所以，現在知道要用什么但是就是用不出。我從別人的作品中看出了我的不足，也感慨自己平時寫的太少了。我真的需要多多的練習。哪怕是一天寫一個也行。
 在答辨的時候老師問我二個問題，一個是程序演示后通過SaveCity(C)來保存，老師要我把具體位置找出來，這個還容易找的。第二個問題是我定義的靜態隊列給來干什么用的，我回答到是給來存儲各個城市之間交通來往的最優值包括最便宜價格，最短時間，中轉站最少。只能是看完別人的程序才恍然大悟，哦，原來是這樣實現這個函數的啊。我還在一邊自責我就怎么沒想到呢。當然那里面也有我自己的成分，就是那排名函數用的是冒泡排序法。還有類的基本框架也是。我想這樣的機會是不多的，以后我一定要自己寫，不會就看書或是問老師。要靠自己的努力去完成自己的任務，才不愧為一個學生。
 這次數據結構設計給我的感想與啟示。在整個程序的結構上的把握是一個很難的問題，在剛開始拿到課題的時候對整個的程序具體應該怎樣去劃分結構，以及怎樣去抽象各個對象的屬性等方面都感覺有點生疏，四大模塊分別實現各種功能，真的在這么短的時間內很難去完成實現的。所以我感到在平時的練習中我們應該多做一些例如：如何去具體的抽象出一個客觀事物的屬性，以及該事物所須完成的具體功能等等的操作練習。通過這次課程設計我發現了自己所存在的問題，不是課本知識沒掌握好而是用的太少以至用不出來的結局。下學期還有數據庫要學，我想也一定有課程設計，所以，在這個暑假我計劃從圖書館先借書來看。到時在家里沒事的時候就寫一寫數據庫方面的程序。以后學習的路還很長，希望通過這次課程設計能夠給我帶來的思考有助于我以后的學習。
源程序清單
//交通管理系統
//Powered by YJ
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define OK 1
#define ERROR 0
#define true 1
#define false 0
#define INFINITY 2000
#define MAX_VERTEX_NUM 30

int change = 0;
typedef int Status;
typedef int ElemType;

typedef struct QNode{ //隊列結構:節點存儲結構
  ElemType data;
  struct QNode *next;
}QNode,*QueuePtr;


typedef struct{ // 隊列
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

Status InitQueue(LinkQueue *Q){// 初始化隊列
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q->front) return ERROR;
    Q->front->next = NULL;
    return OK;
}

Status EnQueue(LinkQueue *Q,ElemType e){// 入隊
    QueuePtr p = NULL;
    p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) return ERROR;
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return OK;
}

Status DeQueue(LinkQueue *Q,ElemType *e){ // 出隊
    QueuePtr p = NULL;
    if(Q->front == Q->rear) return ERROR;
    p = Q->front->next;
    e = p->data;
    Q->front->next = p->next;
    if(Q->rear == p) Q->rear = Q->front;     // 注意當出隊后為空隊的情況
    free(p);
    return OK;
}


Status EmptyQueue(LinkQueue *Q){// 判斷是否為空隊列
    return Q->front == Q->rear?true:false;
}

Status CopyQueue(LinkQueue *Q1,LinkQueue *Q2){// 復制隊列(copy Q1 to Q2)
    int e;
    QueuePtr p;
    while(!EmptyQueue(Q2)) DeQueue(Q2,e);   // clean Q2
    p = Q1->front->next;// copy one by one
    while(p){
        e = p->data;
        p = p->next;
        EnQueue(Q2,e);
    }
    return OK;
}


typedef struct AdJ{// 圖的結構：鄰接矩陣
    int TTime;
    int TPrice;
    int FTime;
    int FPrice;
}ADJ;

typedef struct City{// 圖的結構 
    char name[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//城市名稱
    ADJ arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//鄰接矩陣
    int CityNum;//城市數
}City;

Status CreateCity(City *C){// 建立鄰接圖
    int i,j;

    printf("please input city num:");
    scanf("%d",&C->CityNum);

    for(i = 0;i < C->CityNum; i++){
        printf("input NO.%d city name:  ",i+1);
        scanf("%s",&C->name[i]);
    }

    for(i = 0; i < C->CityNum; i++)
        for(j = 0; j < C->CityNum; j++){
            C->arcs[i][j].TTime = INFINITY;
            C->arcs[i][j].TPrice = INFINITY;
            C->arcs[i][j].FTime = INFINITY;
            C->arcs[i][j].FPrice = INFINITY;
        }

    for(i = 0; i < C->CityNum; i++)
        for(j = i+1;j < C->CityNum; j++){
            printf("input TTime,TPrice,FTime,FPrice[%s -> %s]:  ",C->name[i],C->name[j]);
            scanf("%d%d%d%d",&C->arcs[i][j].TTime,&C->arcs[i][j].TPrice,&C->arcs[i][j].FTime,&C->arcs[i][j].FPrice);
            if(C->arcs[i][j].TTime == 0){
                C->arcs[i][j].TTime = INFINITY;
                C->arcs[i][j].TPrice = INFINITY;
                C->arcs[i][j].FTime = INFINITY;
                C->arcs[i][j].FPrice = INFINITY;
            }
            C->arcs[j][i] = C->arcs[i][j];
        }
    return ;
}