第一篇：數據結構課設
數據結構課設 大整數計數器 1.問題描述
實現大整數（200位以內的整數）的加、減、乘、除運算。2.設計要求
設計程序實現兩個大整數的四則運算，輸出這兩個大整數的和、差、積、商及余數。
3.數據結構
本課程設計采用順序串來實現。4.問題分析
由于整數數據存儲位數有限，因此引入串的概念，將整型數據用字符串進行存儲，利用字符串的一個字符存儲大整數的一位數值，然后根據四則運算規則，對相應位依次進行相應運算，同時保存進位，從而實現大整數精確的運算。具體設計思路如下：
（1）計算大整數加法時，采用數學中列豎式的方法，從個位（即字符串的最后一個字符）開始逐位相加，超過或達到10則進位，同時將該位計算結果存到另一個字符串中，直至加完大整數的所有位為止。
（2）計算大整數減法時，首先調用庫函數strcmp判斷這兩個大整數是否相等，如果相等則結果為0，否則用compare函數判斷被減數和減數的大小關系，進而確定結果為正數還是負數，然后對齊位依次進行減法，不夠減則向前借位，直至求出每一位減法之后的結果。
（3）計算大整數乘法時，首先讓乘數的每一位都和被乘數進行乘法運算，兩個乘數之積與進位相加作為當前位乘積，求得當前位的同時獲取進位值，進而實現大整數的乘法運算。
（4）計算大整數除法時，類似做減法，基本思想是反復做減法，從被除數里最多能減去多少次除數，所求得的次數就是商，剩余不夠減的部分則是余數，這樣便可計算出大整數除法的商和余數。
需求分析(1)任何一個表達式都是由操作數、運算符和界限符組成的,我們稱之為單詞.(2)表達式求值首先要符合四則運算規則: ① 先乘除,后加減 ② 從左到右進行運算 ③ 先括號內,后括號外(3)功能實現: ① 若當前單詞為數字串,則壓入數值棧 ② 若當前單詞為運算符并大于運算棧的棧頂符號,則進棧 ③ 若當前單詞為運算符并等于運算棧的棧頂符號,去括號,輸出 ④ 若當前單詞為運算符并小于運算棧的棧頂符號,則進行運算
課程設計的目的 通過課程設計全面掌握《C語言程序設計》關鍵知識點，掌握C語言中數組、指針、結構體、文件等方面的基本知識。
通過課程設計了解并掌握C語言程序設計的方法，熟悉C程序設計的開發環境及C程序的
調試過程。
培養學生查閱參考資料、手冊的自學能力，通過獨立思考深入鉆研有關問題，學會自己分析、解決問題的方法。
課程設計的任務和要求 任務： 編程求出輸入的兩個正整數之和，這兩個正整數的可能達到200位。
要求：
輸入：
共有兩行，第一行為第1個正整數；第二行為第2個正整數。
輸出：
2個正整數之和。
主要參與成員
姓 名 學 號
系 別 班 級 主要作用（分工）
成果形式
設計 軟件 作品 其他：
完成情況及以后的拓展設想 通過用C語言編寫函數基本實現了大整數相加這個程序，但該程序仍存在一些不足，還可以加上一些語句使程序具有容錯功能，并且可以正確計算一個負數和一個正數相加。
課 程 設 計 鑒 定 情 況 表 小組鑒定意見
小組長簽名：
年 月 日
指導教師意見
教師簽名：
****年**月**日
課程設計成績 優 良 及格 不及格 教研室意見
年 月 日 備注 《C語言程序設計》課程設計報告書 作者：廖 序 課程設計概述 課程設計名稱
大整數相加 任務要求: 編程求出輸入的兩個正整數之和，這兩個正整數的可能達到200位。
輸入：
共有兩行，第一行為第1個正整數；第二行為第2個正整數。
輸出：
2個正整數之和。開發環境: C語言。C語言是目前世界上流行、使用最廣泛的高級程序設計語言。1972年,C語言在美國貝爾實驗室里問世，后來又被多次改進，并出現了多種版本。80年代初，美國國家標準化協會（ANSI），根據C語言問世以來各種版本對C語言的發展和擴充，制定了ANSIC標準。
目前，在微機上廣泛使用的C語言編譯系統有MicrosoftC、Turbo C、Borland C等。這些C語言版本不僅實現了ANSIC標準，而且在此基礎上各自作了一些擴充，使之更加方便、完美。
C語言的特點: C語言是一種結構化語言。它層次清晰，便于按模塊化方式組織程序，易于調試和維護。C語言的表現能力和處理能力極強。它不僅具有豐富的運算符和數據類型，便于實現各類復雜的數據結構。它還可以直接訪問內存的物理地址，進行位(bit)一級的操作。
由于C語言實現了對硬件的編程操作，因此Ｃ語言集高級語言和低級語言的功能于一體。既可用于系統軟件的開發，也適合于應用軟件的開發。
此外，C語言還具有效率高，可移植性強等特點。因此廣泛地移植到了各類各型計算機上，從而形成了多種版本的C語言。
參考資料
李錚、葉艷冰、汪德俊，C語言程序設計基礎與應用，清華大學出版社，2005 [2]CSDN技術中心
二、概要設計
為了實現大整數相加這個程序，將程序劃分為了三個模塊： 輸入數據。運算。輸出結果。
首先定義了子函數Input()來存儲用戶輸入的兩個加數，為了滿足任意位數的兩個大整數相加,在子函數Input()中嵌套調用子函數Init()使sum數組里面存放的數初始化為”0”。
然后定義子函數Long_Add()使兩個大整數作加法運算,從后面往前面相加,附帶進位。定義子函數Output()實現輸出結果。
最后如下圖所示，在主函數main中調用Input()，Long_Add()，Output()三個子函數實現程序。
三、詳細設計
程序的流程圖:
四、調試過程 第一次 測試數據a=***7,b=111111 編譯運行后不能輸出結果，檢查函數后編譯正確。再次分析，發現如果直接把a，b，sum定義為unsigned int型的話，計算出來的和的范圍只能在0~65535之間，否則就會出現錯誤。嘗試將a，b，sum存放到字符數組中，從個位開始，一位一位相加。
第二次 測試數據a=***7,b=111111 編譯運行后仍不能輸出結果。分析原因，在用于輸出的子函數Output()中，輸出數組字符數組sum[]前未確定和的最高非零位。
嘗試加入for(i=0;i 第三次 測試數據a=99999919,b=99 編譯運行后發現計算出來結果不正確。經過分析，函數中沒有對最后 一個進位進行處理。 嘗試加入while(carry > 0)語句，再次進行調試。 { tempsum = sum[i]-'0'+carry;sum[i] = tempsum%10+'0';carry = tempsum/10;i--;} 第四次 測試數據a=99999919,b=99 編譯運行后得到正確結果。 第五次 隨意輸入幾組數據進行測試，結果都是正確的。程序得到實現。 五、結論與體會 通過不斷的調試、修改，本課程設計最終實現了200位以內的兩個大整數相加，但程序還 可以進一步完善，程序中仍存在一些不足之處，比如缺少容錯功能，不能準確計算負整數加正整數，等等問題 雖然C語言程序設計在上學期做為我們的必修課已經學習過了，但書到用時方恨少，這次課程設計的學習程序設計中暴露出的我自身的問題更是非常明顯。 一開始看到題目認為非常簡單，直接將兩個數都定義為整型。編寫程序并運行后發現并不能達到題目的要求，計算出來的和只能小于等于65535，否則就會出現錯誤。分析后，將數據作為字符串來處理，用for循環語句從存數的字符數組中一位一位的取數出來，按照數位對齊，從個位開始，按位相加，逢十進一的運算規則進行運算。最后用字符輸出函數putchar()輸出計算出來的結果。由于程序偏大且較復雜，將程序劃分為了輸入數據、運算、輸出數據三個子程序。數次編譯調試后，最終使程序得以實現。 經過三個星期的上機實踐學習，使我對C語言有了更進一步的認識和了解，讓我能夠進一步的掌握和運用C語言來編寫程序。要想學好C語言要重在實踐，要通過不斷的上機操作才能更好地學習它，通過實踐，我也發現我的好多不足之處和薄弱環節。 首先，基礎掌握不牢固，對于C語言中的許多基本語法尚沒有熟練掌握，在設計過程中仍需請教其它同學，查閱課本，設計效率很低。 其次，經典算法掌握不牢。在完成作業的過程中還需查閱書籍和借鑒他人。 再次，程序量過大的時候，頭緒理不清。雜亂無章，無系統性，不便調試和閱覽，自己也易于出錯。 并且對C語言中經常出現的錯誤也不了解，通過實踐，使我在這幾個方面的認識有所提高。 通過實踐的學習，我認到學好計算機要重視實踐操作，不僅僅是學習C語言，還是其它的語言，以及其它的計算機方面的知識都要重在實踐，所以后在學習過程中，我會更加注視實踐操作，使自己便好地學好計算機。 六、源程序清單 #include t;string.h> #define Max 1000 char sum[Max+1];/*和*/ char a[Max],b[Max];/*兩個加數*/ int len1,len2;void Input(char a[],char b[]){ int i,len;void Init(char a[]);/*對Init()函數進行聲明*/ printf(“Please enter two integer:n”);scanf(“%s %s”,a,b);len1=strlen(a);len2=strlen(b);Init(sum);len=strlen(a);for(i=len-1;i>=0;i--)sum[Max+i-len] = a[i];} void Init(char a[]) { int i;for(i=0;i void Long_Add(char sum[],char new[]){ int i,j;int len;int tempsum;int carry = 0;/*進位*/ len = strlen(new);/*從個位開始，按位相加，逢十進一*/ for(i=Max-1,j=len-1;i>=0,j>=0;i--,j--){ tempsum = sum[i]-'0'+new [j]-'0'+carry;sum[i] = tempsum%10+'0';carry = tempsum/10;} while(carry > 0)/*處理最后一個進位*/ { tempsum = sum[i]-'0'+carry;sum[i] = tempsum%10+'0';carry = tempsum/10;i--;} return;} void Output(char sum[]){int i,n;/*尋找和的最高非零位*/ for(i=0;i Long_Add(sum,b);Output(sum);getch();return 0; 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 課程設計報告 題目：華科校園導航 課程名稱：數據結構課程設計 專業班級： 學 號： 姓 名： 指導教師： 報告日期： 計算機科學與技術學院 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 任務書 數據結構是計算機科學技術與信息安全等專業的一門重要專業基礎課，牢固掌握數據結構的基礎知識，熟練地運用數據結構的思想與技術方法解決實際應用問題是是本課程學習的基本任務與目標。而課程設計是實現這一學習目標的重要環節和組成部分。通過課程設計的訓練，使學生加深對數據結構知識的理解，牢固掌握其應用方法，并合理靈活地解決一定實際問題，增強和提高綜合分析問題與解決問題的能力。 設計題目 華科地圖導航系統。設計目的 掌握圖結構的物理存儲結構、基本算法及其算法在相關領域中的應用。 設計內容 華中科技大學（Huazhong University of Science and Technology），簡稱華中大，坐落于湖北省武漢市，學校面積7000余畝。華科大校園具有典型的工科院校特征，道路筆直，建筑面積方方正正，這為構建電子地圖提供了極大的便利。本次課程設計要求以華中科技大學為背景，設計一個簡單的華科地圖導航程序，可以方便的為用戶提供搜索、導航等功能。 設計要求 基本要求： 1.輸入地點名，可以在地圖中以一定標記標示出地點所在的位置 2.鼠標移動到指定建筑處顯示建筑名稱 3.輸入或點擊起點和終點，找出最短的路徑，并在圖上描出路徑，路徑不能脫離道路 4.輸入起點，輸入特定的地點，如食堂，超市能夠找到最近的兩到三個 5.地點至少要包括清單中所列的位置 實驗提示： 1.將每個十字路口或特定建筑看作節點，構建圖模型，兩個節點的邊即是一個路段。對于某些節點，可能具有特定的意義，例如“圖書館”，可以為其設置一個名稱；而對于大多數節點，例如普通路口，可能并不需要名稱，只是用來構建圖模型的一個節點。信息的錄入可能需要人為輸入，需要編寫輔助程序。輔助程序可以如下構造： 程序首先載入一張圖片并顯示。程序具有多個文本框，當點擊圖片上 I 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 特定點時，獲取該點的坐標，第一個文本框顯示該點的圖像坐標，第二個文本框可以輸入地點名，第三個文本框用來輸入節點編號，剩下的文本框用來輸入直接相鄰的節點編號或者節點的屬性。點擊“確認”后可以將信息保存到磁盤。這樣可以實現坐標、節點編號和位置名稱的綁定，為實驗構圖采集數據。 2.特定建筑只需考慮建筑大門所對應的路段上的一點。例如“圖書館”建 筑，可認為“圖書館”位于圖書館大門和學校道路相接處，簡化處理。當鼠標移動到“圖書館”附近時，找到距離最近的具有名稱的節點顯示 即可。 3.對于存在折線的路段，將其看作多段處理；對于細碎的彎折路線，當作 直線簡化處理。 參考文獻 [1] 嚴蔚敏,吳偉民.數據結構(C語言版).北京: 清華大學出版社,1997 [2] 王曉東.計算機算法設計與分析.北京: 電子工業出版社, 2007 [3] 嚴蔚敏,吳偉民,米寧.數據結構題集(C語言版).北京: 清華大學出版社,1999 [4] Elliot B.Koffman and Paul A.T.Wolfgang..Objects, Abstraction, Data Structures and Design: Using C++.October 2005, ?2006 II華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 目錄 任務書.............................................................................................................................I 1 系統需求分析與總體設計........................................................................................1 1.1系統需求分析.................................................................................................1 1.2系統總體設計.................................................................................................1 2 系統詳細設計............................................................................................................2 2.1 有關數據結構的定義....................................................................................2 2.2 主要算法設計................................................................................................3 3 系統實現與測試........................................................................................................4 3.1 系統實現........................................................................................................4 3.2 系統測試........................................................................................................6 4 總結與展望..............................................................................................................13 4.1 全文總結......................................................................................................13 4.1 工作展望......................................................................................................13 5 體會..........................................................................................................................15 參考文獻......................................................................................................................16 附錄..............................................................................................................................17 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 系統需求分析與總體設計 1.1系統需求分析 華中科技大學（Huazhong University of Science and Technology），簡稱華中大，坐落于湖北省武漢市，學校面積7000余畝。華科大校園具有典型的工科院校特征，道路筆直，建筑面積方方正正，這為構建電子地圖提供了極大的便利。本次課程設計以華中科技大學為背景，設計一個簡單的華科校園地圖導航程序，可以方便的為用戶提供搜索、導航等功能。該系統的具體的功能為： 1.輸入任意地點名，可以在地圖中以一定標記顯示出該地點所在的位置； 2.輸入任意起點和終點，可以在地圖上查詢并顯示從起點到終點的最佳路線以及最短距離； 3.輸入任意地點名，可以在地圖上查詢并顯示出距離該地點最近的食堂或者超市，并給出從該地點到達食堂或者超市的最佳路線和最短距離； 4.鼠標移動到地圖上的某一地點是，顯示該地點的名稱和簡介； 5.系統能為用戶提供華科整體地圖、系統使用說明、設計信息。擁有以上的功能的導航應用將給不熟悉華科的用戶提供極大的便利，是人們所需要的。 1.2系統總體設計 系統的總體模塊圖如圖1所示。用戶進入系統后，在窗口主界面可以選擇“地圖導航”、“進入地圖”、“使用幫助”“關于導航”、“退出導航”等功能。在“地圖導航”功能中，用戶可以查詢某個地點或者某個地點附近最近的食堂和超市、到達該地點的最佳路徑和距離等，在過了一定時間后，系統會提示用戶選擇返回“地圖導航”界面還是進入“進入地圖”功能，然后系統根據用戶的選擇進入相應的界面；在“進入地圖”功能下，用戶可以瀏覽整個華科地圖并且查詢某個地點的名稱和簡介；在“使用幫助”下，用戶可以閱讀該系統的使用說明；在“關于導航”下，用戶可以了解該系統的設計信息；用戶點擊“退出導航”即可退出該系統。 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 圖 1 系統詳細設計 2.1 有關數據結構的定義 華科校園導游系統是用圖結構來實現的。具體數據結構如下： 定義景點的結構類型 typedef struct { 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 Point point;char name[20];char num;}Vexs; 定義景點坐標的結構類型 typedef struct { int x;int y;}Point; 定義圖的結構類型 struct MGraph { }; 聲明無向圖的鄰接矩陣類型 MGraph G[100],G0,G1; 初始化所有景點信息，存放在圖G1中 int CreateUDG1(MGraph &G1);Vexs vexs[MAX_VEX_NUM]; //頂點向量 int vexnum,arcnum; //頂點數，邊數 int arcs[MAX_VEX_NUM][MAX_VEX_NUM];//鄰接矩陣 2.2 主要算法設計 Floyd算法：void Floyd(void); 通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。 從圖的帶權鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；??；最后又用同樣的公式由D(n-1)構造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節點矩陣path來記錄兩點間的最短路徑。 采用松弛技術（松弛操作），對在i和j之間的所有其他點進行一次松弛。所以時間復雜度為O(n^3);其狀態轉移方程為map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；map[i,j]表示i到j的最短距離，K是窮舉i,j的斷點，map[n,n]初值應該為0，或者按照題目意思來做。當然，如果這條路沒有通的話，還必須特殊處理，比如沒有map[i,k]這 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 條路。 通過弗洛伊德算法計算出兩單間的最短路徑之后，就可以通過距離計算公式計算出兩點間的最短距離。 利用佛洛依德算法計算出每兩點間的最短路徑矩陣。里面有三重for循環，時間的復雜度為O(n^3)。系統實現與測試 3.1 系統實現 3.1.1 開發環境 本系統是在windows7下的Visual C++ 6.0編譯器中進行設計，但是一般的編譯器中沒有包含編寫界面的 Runtime Library 下選 Multi-threaded Debug(/MTd)Project->setting->C/C++->category(code generation)->using runtime library(debug multithread)。3.1.2 運行環境 Window7 64位旗艦版系統。3.1.3 主要函數及說明 1、void Floyd(void); 按照實際路況處理，利用佛洛依德算法，算出每兩點間的最短路徑矩陣。求 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 ->的最短路徑,如果->有弧，則存在一條長度為arcs[i][j]的路徑，但是該路徑不一定是最短路徑，尚需要進行n次試探。若存在（Vi,Vo,Vj），則比較(Vi，Vj）和(Vi,Vo）+（Vo,Vj）的大小。取（Vi,Vo,Vj）和(Vi，Vj）的較短者，繼續添加結點。依此類推，每次都找到短路徑，最后得到的便是最短路徑。把最短的路徑存到全局變量path中。 2、void LoadData(void)； 加載初期設定的信息包括所有圖片。并且將設定好的坐標信息存儲到圖G0中。并且使用佛洛依德算法，將每對景點之間的最短路徑距離算出并存儲最短路徑到全局變量path中。以方便后續程序的進行。 3、int CreateUDG1(MGraph &G1);加載所有景點信息，并存儲到圖G1中。（圖G1不包括路口坐標信息）。里面有兩個for循環，一個用來加載景點坐標，名稱和代號。另一個for循環用來構建完全圖G1,計算出每對景點的最短路徑(理想情況下處理的)。返回值為1。 4、int weight(Point a,Point b);計算兩個點之間的距離，利用公式，計算出的結果是double類型的，將結果強制類型轉換為int類型，并將其值返回。 5、void Musicplay(int mark)； 利用mciSendString函數，mark用來控制背景音樂的播放與停止。mark=1，循環播放音樂。界面打開時后臺啟動。當主界面上點擊音樂暫停圖標mark=2，音樂暫停.。當主界面上點擊音樂播放圖標mark=3，音樂恢復播放。.6、void Windows(void);加載事先做好的主界面背景圖。在上面輸出文字信息。用GetMouseMsg()；函數獲取鼠標信息，設置鼠標響應區，當鼠標移動到響應區時，文字實現顏色的改變。當單擊鼠標左鍵時，會進入到相應的函數里面，進行下一步操作。 7、void Viewmain(void);輸出景點坐標及名稱。設置景點活動區域，獲取鼠標信息，當鼠標移動到相應的景點活動區域，就會加載相應的景點圖片。 8、void Help(void); 有簡單的操作說明。操作說明是以圖片的形式加載進去的。圖片是事先用PS 5 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 準備好的。 9、void About(void);有簡單的作者信息及實驗感想。背景是以圖片的形式加載進去的。圖片是事先用PS準備好的。里面還有一個網頁鏈接，點擊后會用Systen函數，打開該網頁鏈接。 10、void Quit(void);關閉圖形區域，退出導航。詳細設計代碼見附錄。 3.2 系統測試 根據設計要求測試相關的功能，測試結果用相應的截圖表示。 1、運行程序，進入系統主窗口界面，結果如圖2所示。 圖 2 2、選擇主界面的“地圖導航功”能，進入功能選區，結果如圖3所示。華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 圖 3 2.1、在“地圖導航”功能界面選擇“place”（地點查詢）功能，查詢地點A（南大門）。輸入A，系統在地圖上正確地顯示地點A的位置。結果如圖4，圖5所示。 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 圖 4 圖 5 2.2、在“地圖導航”功能界面選擇“route”（路線查詢）功能，查詢A（南大門）到B（南一樓）之間的最佳路線和距離。輸入AB，系統在地圖上正確地顯示AB之前的最佳路線和距離。結果如圖6，圖7所示。 圖 6 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 圖 7 2.3、在“地圖導航”功能界面選擇“repast”（食堂查詢）功能，查詢B（南一樓）附近最近的食堂。輸入B，系統在地圖上正確地顯示B附近最近的食堂，并且給出了最佳路線和距離。結果如圖8，圖9所示。 圖 8 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 圖 9 2.4、在“地圖導航”功能界面選擇“market”（超市查詢）功能，查詢A（南大門）附近最近的超市。輸入A，系統在地圖上正確地顯示A附近最近的超市，并且給出了最佳路線和距離。結果如圖10，圖11所示。華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 圖 10 圖 11 3、在系統主界面選擇“進入地圖”功能，將鼠標光標移動到地圖的地點（機械大樓）上面，地圖右下角顯示該地點的具體信息。結果如圖12所示。 圖 12 11 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 4、在系統主界面選擇進入“使用幫助”功能，系統顯示該系統的使用說明。結果如圖13所示。 圖 13 5、在系統主界面選擇進入“關于導航”功能，系統顯示該系統的設計信息。結果如圖14所示。華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 圖 14 6、在系統主界面選擇“退出導航”功能，點擊“確定”即退出系統。結果如所示。總結與展望 圖 1 54.1 全文總結 對自己的工作做個總結，主要工作總結如下： （1）分析設計題目、設計內容和設計要求，到圖書館和網上查閱相關資料，制定設計計劃，為設計工作做準備。 （2）按照設計要求進行設計工作，設計合適的數據結構和算法，收集并處理相關的資料，編程實現。 （3）按照設計要求測試系統，調試程序BUG，優化、完善系統。（4）撰寫課程設計報告。 4.1 工作展望 在今后的研究中，圍繞著如下幾個方面開展工作： （1）此次設計使用了弗洛伊德算法，沒有設計出更高效的算法。所以應該 設計更合適的數據結構和更高效的算法，優化代碼，提高系統的效率。華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 （2）設計的系統功能還是比較單一。所以應該完善和擴充系統功能，使系 統能為用戶提供更多、更優質的服務。 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 體會 在該接觸到本次《數據結構》的課程設計時，心里是沒有底的，一開始就為了確定題目思考了很久，但是看到地圖就有了很多想法，回想起在課程的學習中對圖進行了深入地學習并且學習了諸多尋路算法，于是就選擇了這個題目，我覺得我可以根據自己所學習的圖的知識和算法設計出“華科地圖導航”。 “華科地圖導航”涉及到大量的圖形信息與繪圖信息，于是我開始尋找合適的開發的工具與語言進行編程設計。最開始在網上查詢相關信息了解到QT是寫圖形界面的好工具，但是進行上手學習后發現QT函數庫眾多，而我不能正確熟悉地使用，于是考慮了很久就放棄了。后來了解到了C語言的圖形庫easyx，于是上網查詢了相關的資料，對easyx有了大致的了解，上手很容易，只需根據其圖形函數與繪圖函數進行編程設計，課設就正式進入了設計、編寫、測試，然后順利完成課設。 感謝幫助過我同學和老師，也感謝我自己。 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 參考文獻 [1] 嚴蔚敏,吳偉民.數據結構(C語言版).北京: 清華大學出版社,1997 [2] 嚴蔚敏,吳偉民,米寧.數據結構題集(C語言版).北京: 清華大學出版社,1999 [3] 曹計昌,盧萍,李開.C語言與程序設計.北京: 電子工業出版社,2013 [4] 王曉東.計算機算法設計與分析.北京: 電子工業出版社, 2007 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 附錄 1.TourGuide.h #include #define MAX_VEX_NUM 100 //最大地點個數 #define N 22 //當前地點個數 #define All 60 //地點和路口總數 #define MAX_ROAD 10000 //相當于兩地點間斷開 int shortest[MAX_VEX_NUM][MAX_VEX_NUM]; //全局變量存貯最小路徑 int path[MAX_VEX_NUM][MAX_VEX_NUM]; //存貯路徑 int pos[][2]={ //地點坐標及路口坐標 //地點坐標 {208,430},{209,387},{50,404} ,{105,355}, {110,300},{170,300},{167,234},{230,150}, {310,235},{310,320},{390,320},{615,155}，{430,320},{430,150},{417,320},{368,307}，{406,320},{472,160},{5,185} ,{339,293}，{65,452} ,{109,439}, //路口坐標 {369,317},{46,379} ,{110,387},{368,293}, {168,386},{262,384},{112,320},{170,320}, {262,320},{309,292},{309,282},{110,284}, {170,284},{230,250},{309,250},{170,250}, {230,220},{307,220},{370,150},{2,219} , {108,188},{33,337} ,{109,250},{109,218}, {309,150},{108,150},{167,218},{427,250}, {368,218},{368,250},{166,150},{166,188}, {230,188},{309,188},{368,188},{230,282}, {230,320},{168,350} };char Num[]={ //地點編號 'A','B','C','D', 'E','F','G','H', 'I','J','K','L'，'M','N','O','P'，'Q','R','S','T'，'U','V' };char Name[][20]={ //地點名稱 “南大門”,“南一樓”,“西十二樓”,“西五樓”, “青年園”,“圖書館”,“科技樓”,“喻園餐廳”, 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 “機械學院”,“名人園”,“中心操場”,“東九樓”, “沁苑”,“喻園教工超市”,“東教工超市”, “東一食堂”,“紫荊園餐廳”,“清真食堂”, “百景園”,“東五樓”,“南三門”,“南二門” };typedef struct { int x;int y;}Point;typedef struct { Point point;char name[20];char num;}Vexs;struct MGraph { Vexs vexs[MAX_VEX_NUM]; //頂點向量 int arcs[MAX_VEX_NUM][MAX_VEX_NUM];//鄰接矩陣 int vexnum,arcnum; //頂點數，邊數 };MGraph G[100],G0,G1; //聲明無向圖的鄰接矩陣類型 int Gi;IMAGE map,map1; //圖片信息的加載 IMAGE loading;IMAGE about;IMAGE help;IMAGE background;IMAGE Aa,Bb,Cc,Dd,Ee,Ff,Gg,Hh,Ii,Jj,Kk,Ll,Mm,Nn,Oo,Pp,Qq,Rr,Ss,Tt,Uu,Vv,a1,a2,b1,b2,c1,c2,d1,d2;void LoadData(void); //加載信息 int CreateUDG1(MGraph &G1);//初始化所有景點信息 int weight(Point a,Point b);//計算兩點之間的距離 void Windows(void); //主窗口界面 void Musicplay(int mark);//播放音樂 void Showplace(void); //查找地點位置 void Showpoint(int i);void Shortest(void); //兩點之間的最短路徑 void Showline(int i,int j);//顯示輸入框 void Showline1(int i,int j);//顯示輸入框 void Showline2(int i,int j);//顯示輸入框 void Floyd(void); //佛洛依德算法，算出每兩點間的最短路徑矩陣 void Linemin(int i,int j); //畫最短路徑 void Findrepast(void); //查找附近的食堂 void Findmarket(void); //查找附近的超市 void Entermap(void); //進入地圖操作界面 void Viewmain(void); //瀏覽地點信息 void HelP(void); //操作說明 void About(void); //作者相關信息 void Quit(void); //退出系統 2.TourGuide.cpp 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 #include“head.h” int main(){ initgraph(640,480);HWND hwnd = GetHWnd(); // 設置窗口標題文字 SetWindowText(hwnd, “華科地圖導航”);LoadData();CreateUDG1(G1);Musicplay(1);Windows();return 0;} /*功能:對輸入的兩個點計算它們之間的距離，并將其返回到調用的函數中*/ int weight(Point a,Point b){ double x;int y;x=pow((a.x-b.x),2)+pow((a.y-b.y),2);x=sqrt(x);y=int(x);return y;} /*功能:加載程序運行必須的圖片及函數相關信息*/ void LoadData(void){ int i,j;loadimage(&loading,“./picture/loading.jpg”);loadimage(&about,“./picture/about.jpg”);loadimage(&help,“./picture/help.jpg”);loadimage(&background,“./picture/background.jpg”);loadimage(&map,“./picture/map.jpg”);loadimage(&map1,“./picture/map1.jpg”);loadimage(&Aa,“./picture/place/A.jpg”);loadimage(&Bb,“./picture/place/B.jpg”);loadimage(&Cc,“./picture/place/C.jpg”);loadimage(&Dd,“./picture/place/D.jpg”);loadimage(&Ee,“./picture/place/E.jpg”);loadimage(&Ff,“./picture/place/F.jpg”);loadimage(&Gg,“./picture/place/G.jpg”);loadimage(&Hh,“./picture/place/H.jpg”);loadimage(&Ii,“./picture/place/I.jpg”);loadimage(&Jj,“./picture/place/J.jpg”);loadimage(&Kk,“./picture/place/K.jpg”);loadimage(&Ll,“./picture/place/L.jpg”);loadimage(&Mm,“./picture/place/M.jpg”);loadimage(&Nn,“./picture/place/N.jpg”);loadimage(&Oo,“./picture/place/O.jpg”);loadimage(&Pp,“./picture/place/P.jpg”);loadimage(&Qq,“./picture/place/Q.jpg”);loadimage(&Rr,“./picture/place/R.jpg”);loadimage(&Ss,“./picture/place/S.jpg”);loadimage(&Tt,“./picture/place/T.jpg”);loadimage(&Uu,“./picture/place/U.jpg”);loadimage(&Vv,“./picture/place/V.jpg”);loadimage(&a1,“./picture/menu/a1.jpg”);華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 loadimage(&a2,“./picture/menu/a2.jpg”);loadimage(&b1,“./picture/menu/b1.jpg”);loadimage(&b2,“./picture/menu/b2.jpg”);loadimage(&c1,“./picture/menu/c1.jpg”);loadimage(&c2,“./picture/menu/c2.jpg”);loadimage(&d1,“./picture/menu/d1.jpg”);loadimage(&d2,“./picture/menu/d2.jpg”);for(i=1;i<=All;i++){ for(j=1;j<=All;j++) { G0.arcs[i][j]=MAX_ROAD; } } for(i=1;i<=All;i++) { shortest[i][i]=0; } for(i=0;i G0.vexs[i+1].point.x=pos[i][0]; G0.vexs[i+1].point.y=pos[i][1]; } //初始化連通路徑 G0.arcs[1][2]=G0.arcs[2][1]=weight(G0.vexs[1].point,G0.vexs[2].point);G0.arcs[1][22]=G0.arcs[22][1]=weight(G0.vexs[22].point,G0.vexs[1].point);G0.arcs[1][27]=G0.arcs[27][1]=weight(G0.vexs[27].point,G0.vexs[1].point); G0.arcs[1][28]=G0.arcs[28][1]=weight(G0.vexs[28].point,G0.vexs[1].point); G0.arcs[2][27]=G0.arcs[27][2]=weight(G0.vexs[27].point,G0.vexs[2].point); G0.arcs[2][28]=G0.arcs[28][2]=weight(G0.vexs[28].point,G0.vexs[2].point); G0.arcs[3][21]=G0.arcs[21][3]=weight(G0.vexs[21].point,G0.vexs[3].point); G0.arcs[3][24]=G0.arcs[24][3]=weight(G0.vexs[24].point,G0.vexs[3].point);G0.arcs[4][24]=G0.arcs[24][4]=weight(G0.vexs[24].point,G0.vexs[4].point); G0.arcs[4][25]=G0.arcs[25][4]=weight(G0.vexs[25].point,G0.vexs[4].point);G0.arcs[4][29]=G0.arcs[29][4]=weight(G0.vexs[29].point,G0.vexs[4].point);G0.arcs[4][60]=G0.arcs[60][4]=weight(G0.vexs[60].point,G0.vexs[4].point); G0.arcs[5][29]=G0.arcs[29][5]=weight(G0.vexs[29].point,G0.vexs[5].point);G0.arcs[5][34]=G0.arcs[34][5]=weight(G0.vexs[34].point,G0.vexs[5].point);G0.arcs[6][30]=G0.arcs[30][6]=weight(G0.vexs[6].point,G0.vexs[30].point);G0.arcs[6][35]=G0.arcs[35][6]=weight(G0.vexs[6].point,G0.vexs[35].point); G0.arcs[7][49]=G0.arcs[49][7]=weight(G0.vexs[7].point,G0.vexs[49].point);G0.arcs[7][38]=G0.arcs[38][7]=weight(G0.vexs[7].point,G0.vexs[38].point);G0.arcs[8][47]=G0.arcs[47][8]=weight(G0.vexs[8].point,G0.vexs[47].point);G0.arcs[8][53]=G0.arcs[53][8]=weight(G0.vexs[53].point,G0.vexs[8].point);G0.arcs[8][55]=G0.arcs[55][8]=weight(G0.vexs[55].point,G0.vexs[8].point);G0.arcs[9][37]=G0.arcs[37][9]=weight(G0.vexs[9].point,G0.vexs[37].point);G0.arcs[9][40]=G0.arcs[40][9]=weight(G0.vexs[9].point,G0.vexs[40].point);G0.arcs[10][31]=G0.arcs[31][10]=weight(G0.vexs[10].point,G0.vexs[31].point);G0.arcs[10][23]=G0.arcs[23][10]=weight(G0.vexs[10].point,G0.vexs[23].point);G0.arcs[10][32]=G0.arcs[32][10]=weight(G0.vexs[10].point,G0.vexs[32].point); G0.arcs[11][17]=G0.arcs[17][11]=weight(G0.vexs[11].point,G0.vexs[17].point); G0.arcs[11][23]=G0.arcs[23][11]=weight(G0.vexs[11].point,G0.vexs[23].point); G0.arcs[12][18]=G0.arcs[18][12]=weight(G0.vexs[12].point,G0.vexs[18].point); G0.arcs[13][50]=G0.arcs[50][13]=weight(G0.vexs[13].point,G0.vexs[50].point);G0.arcs[13][15]=G0.arcs[15][13]=weight(G0.vexs[13].point,G0.vexs[15].point); G0.arcs[14][18]=G0.arcs[18][14]=weight(G0.vexs[14].point,G0.vexs[18].point); G0.arcs[14][41]=G0.arcs[41][14]=weight(G0.vexs[14].point,G0.vexs[41].point);華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 G0.arcs[14][50]=G0.arcs[50][14]=weight(G0.vexs[14].point,G0.vexs[50].point); G0.arcs[15][17]=G0.arcs[17][15]=weight(G0.vexs[15].point,G0.vexs[17].point); G0.arcs[16][23]=G0.arcs[23][16]=weight(G0.vexs[16].point,G0.vexs[23].point); G0.arcs[16][26]=G0.arcs[26][16]=weight(G0.vexs[16].point,G0.vexs[26].point); G0.arcs[19][42]=G0.arcs[42][19]=weight(G0.vexs[19].point,G0.vexs[42].point); G0.arcs[19][43]=G0.arcs[43][19]=weight(G0.vexs[19].point,G0.vexs[43].point); G0.arcs[20][26]=G0.arcs[26][20]=weight(G0.vexs[20].point,G0.vexs[26].point); G0.arcs[20][32]=G0.arcs[32][20]=weight(G0.vexs[20].point,G0.vexs[32].point); G0.arcs[21][22]=G0.arcs[22][21]=weight(G0.vexs[22].point,G0.vexs[21].point); G0.arcs[22][25]=G0.arcs[25][22]=weight(G0.vexs[22].point,G0.vexs[25].point); G0.arcs[24][44]=G0.arcs[44][24]=weight(G0.vexs[24].point,G0.vexs[44].point); G0.arcs[25][27]=G0.arcs[27][25]=weight(G0.vexs[25].point,G0.vexs[27].point); G0.arcs[26][52]=G0.arcs[52][26]=weight(G0.vexs[26].point,G0.vexs[52].point); G0.arcs[27][60]=G0.arcs[60][27]=weight(G0.vexs[27].point,G0.vexs[60].point); G0.arcs[28][31]=G0.arcs[31][28]=weight(G0.vexs[28].point,G0.vexs[31].point); G0.arcs[29][30]=G0.arcs[30][29]=weight(G0.vexs[29].point,G0.vexs[30].point); G0.arcs[29][44]=G0.arcs[44][29]=weight(G0.vexs[29].point,G0.vexs[44].point); G0.arcs[30][59]=G0.arcs[59][30]=weight(G0.vexs[30].point,G0.vexs[59].point);G0.arcs[30][60]=G0.arcs[60][30]=weight(G0.vexs[30].point,G0.vexs[60].point); G0.arcs[31][59]=G0.arcs[59][31]=weight(G0.vexs[31].point,G0.vexs[59].point); G0.arcs[32][33]=G0.arcs[33][32]=weight(G0.vexs[32].point,G0.vexs[33].point); G0.arcs[33][37]=G0.arcs[37][33]=weight(G0.vexs[33].point,G0.vexs[37].point); G0.arcs[33][58]=G0.arcs[58][33]=weight(G0.vexs[33].point,G0.vexs[58].point); G0.arcs[34][35]=G0.arcs[35][34]=weight(G0.vexs[34].point,G0.vexs[35].point); G0.arcs[34][45]=G0.arcs[45][34]=weight(G0.vexs[34].point,G0.vexs[45].point); G0.arcs[35][38]=G0.arcs[38][35]=weight(G0.vexs[35].point,G0.vexs[38].point);G0.arcs[35][58]=G0.arcs[58][35]=weight(G0.vexs[35].point,G0.vexs[58].point); G0.arcs[36][37]=G0.arcs[37][36]=weight(G0.vexs[36].point,G0.vexs[37].point); G0.arcs[36][38]=G0.arcs[38][36]=weight(G0.vexs[36].point,G0.vexs[38].point); G0.arcs[36][39]=G0.arcs[39][36]=weight(G0.vexs[36].point,G0.vexs[39].point);G0.arcs[36][58]=G0.arcs[58][36]=weight(G0.vexs[36].point,G0.vexs[58].point); G0.arcs[37][52]=G0.arcs[52][37]=weight(G0.vexs[37].point,G0.vexs[52].point);G0.arcs[38][45]=G0.arcs[45][38]=weight(G0.vexs[45].point,G0.vexs[38].point);G0.arcs[39][49]=G0.arcs[49][39]=weight(G0.vexs[39].point,G0.vexs[49].point); G0.arcs[39][55]=G0.arcs[55][39]=weight(G0.vexs[39].point,G0.vexs[55].point);G0.arcs[39][40]=G0.arcs[40][39]=weight(G0.vexs[39].point,G0.vexs[40].point); G0.arcs[40][56]=G0.arcs[56][40]=weight(G0.vexs[40].point,G0.vexs[56].point); G0.arcs[40][51]=G0.arcs[51][40]=weight(G0.vexs[40].point,G0.vexs[51].point); G0.arcs[41][47]=G0.arcs[47][41]=weight(G0.vexs[41].point,G0.vexs[47].point);G0.arcs[41][57]=G0.arcs[57][41]=weight(G0.vexs[41].point,G0.vexs[57].point);G0.arcs[42][44]=G0.arcs[44][42]=weight(G0.vexs[42].point,G0.vexs[44].point);G0.arcs[42][46]=G0.arcs[46][42]=weight(G0.vexs[42].point,G0.vexs[46].point);G0.arcs[43][46]=G0.arcs[46][43]=weight(G0.vexs[43].point,G0.vexs[46].point); G0.arcs[43][48]=G0.arcs[48][43]=weight(G0.vexs[43].point,G0.vexs[48].point);G0.arcs[43][54]=G0.arcs[54][43]=weight(G0.vexs[43].point,G0.vexs[54].point);G0.arcs[45][46]=G0.arcs[46][45]=weight(G0.vexs[45].point,G0.vexs[46].point); G0.arcs[46][49]=G0.arcs[49][46]=weight(G0.vexs[46].point,G0.vexs[49].point);G0.arcs[47][56]=G0.arcs[56][47]=weight(G0.vexs[47].point,G0.vexs[56].point);G0.arcs[48][53]=G0.arcs[53][48]=weight(G0.vexs[48].point,G0.vexs[53].point);G0.arcs[49][54]=G0.arcs[54][49]=weight(G0.vexs[49].point,G0.vexs[54].point); G0.arcs[50][52]=G0.arcs[52][50]=weight(G0.vexs[50].point,G0.vexs[52].point);G0.arcs[51][52]=G0.arcs[52][51]=weight(G0.vexs[51].point,G0.vexs[52].point);G0.arcs[51][57]=G0.arcs[57][51]=weight(G0.vexs[51].point,G0.vexs[57].point); G0.arcs[53][54]=G0.arcs[54][53]=weight(G0.vexs[53].point,G0.vexs[54].point);G0.arcs[54][55]=G0.arcs[55][54]=weight(G0.vexs[54].point,G0.vexs[55].point);G0.arcs[55][56]=G0.arcs[56][55]=weight(G0.vexs[55].point,G0.vexs[56].point);G0.arcs[56][57]=G0.arcs[57][56]=weight(G0.vexs[56].point,G0.vexs[57].point);華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 G0.arcs[58][59]=G0.arcs[59][58]=weight(G0.vexs[58].point,G0.vexs[59].point Floyd();} /*功能:佛洛依德算法，將每對景點之間的最短路徑距離算出并存儲最短路徑到path中 */ void Floyd() { int i,j,k; for(i=1;i<=All;i++) { for(j=1;j<=All;j++) { shortest[i][j]=G0.arcs[i][j]; path[i][j]=j; } } /*初始化數組*/ for(k=1;k<=All;k++) { for(i=1;i<=All;i++) { for(j=1;j<=All;j++) { if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) { shortest[i][j]=shortest[i][k]+shortest[k][j]; path[i][j]=k; path[j][i]=k; /*記錄經過的路徑*/ } } } } } /*功能:初始化由所有景點構成的無向完全圖G1，并加載必要信息*/ int CreateUDG1(MGraph &G1){ int p,q;Gi=0;G1.vexnum=22; for(q=0;q G1.vexs[q].point.x=pos[q][0]; G1.vexs[q].point.y=pos[q][1]; strcpy(G1.vexs[q].name,Name[q]); G1.vexs[q].num=Num[q];} for(q=0;q { for(p=q;p G1.arcs[q][p]=G1.arcs[p][q]=weight(G1.vexs[p].point,G1.vexs[q].point);} return 1;} /*把音樂以資源形式嵌入exe并播放,mark用來控制音樂的播放與暫停*/ void Musicplay(int mark){ mciSendString(“open./music/1024.mp3 alias music”,NULL,0,NULL);華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 if(mark==1) mciSendString(_T(“play music repeat”),NULL,0,NULL);if(mark==2) mciSendString(_T(“pause music”),NULL,0,NULL);if(mark==3) mciSendString(_T(“resume music”),NULL,0,NULL);} /*功能:顯示主窗口界面,進入功能選擇區*/ void Windows(void){ cleardevice();int posx[]={265,265,265,265,265,31,62};int posy[]={180,220,260,300,340,449,449};putimage(0,0,&loading);settextstyle(25, 0, _T(“隸書”));setbkmode(TRANSPARENT);settextcolor(WHITE);outtextxy(posx[0],posy[0], _T(“地圖導航”));outtextxy(posx[1],posy[1], _T(“進入地圖”));outtextxy(posx[2],posy[2], _T(“使用幫助”));outtextxy(posx[3],posy[3], _T(“關于導航”));outtextxy(posx[4],posy[4], _T(“退出導航”));MOUSEMSG m;while(true){ m=GetMouseMsg(); if(m.uMsg==WM_MOUSEMOVE) { if(m.x>posx[0]&&m.x posy[0]&&m.y settextcolor(BLACK); else settextcolor(WHITE); outtextxy(posx[0],posy[0], _T(“地圖導航”)); if(m.x>posx[1]&&m.x posy[1]&&m.y settextcolor(BLACK); else settextcolor(WHITE); outtextxy(posx[1],posy[1], _T(“進入地圖”)); if(m.x>posx[2]&&m.x posy[2]&&m.y settextcolor(BLACK); else settextcolor(WHITE); outtextxy(posx[2],posy[2], _T(“使用幫助”)); if(m.x>posx[3]&&m.x posy[3]&&m.y settextcolor(BLACK); else settextcolor(WHITE); outtextxy(posx[3],posy[3], _T(“關于導航”)); if(m.x>posx[4]&&m.x posy[4]&&m.y settextcolor(BLACK); else settextcolor(WHITE); outtextxy(posx[4],posy[4], _T(“退出導航”)); } if(m.uMsg==WM_LBUTTONUP) { 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 if(m.x>posx[0]&&m.x posy[0]&&m.y Entermap(); if(m.x>posx[1]&&m.x posy[1]&&m.y Viewmain(); if(m.x>posx[2]&&m.x posy[2]&&m.y HelP(); if(m.x>posx[3]&&m.x posy[3]&&m.y About(); if(m.x>posx[4]&&m.x posy[4]&&m.y Quit(); if(m.x>posx[5]&&m.x posy[5]&&m.y Musicplay(3); if(m.x>posx[6]&&m.x posy[6]&&m.y Musicplay(2); } } cleardevice();return;} /*功能:進入地圖操作界面，可選功能項有最短路徑查詢和最佳路線問題*/ void Entermap(){ int posx[]={215,325,215,325,0};int posy[]={135,135,245,245,0};putimage(0,0,&background);MOUSEMSG m;while(true){ m=GetMouseMsg(); if(m.uMsg==WM_MOUSEMOVE) { if(m.x>posx[0]&&m.x posy[0]&&m.y putimage(215,135,&c2); else putimage(215,135,&c1); if(m.x>posx[1]&&m.x posy[1]&&m.y putimage(325,135,&d2); else putimage(325,135,&d1); if(m.x>posx[2]&&m.x posy[2]&&m.y putimage(215,245,&a2); else putimage(215,245,&a1); if(m.x>posx[3]&&m.x posy[3]&&m.y putimage(325,245,&b2); else putimage(325,245,&b1); } if(m.uMsg==WM_LBUTTONUP) { if(m.x>posx[0]&&m.x posy[0]&&m.y Showplace(); if(m.x>posx[1]&&m.x posy[1]&&m.y Shortest(); if(m.x>posx[2]&&m.x posy[2]&&m.y Findrepast(); if(m.x>posx[3]&&m.x posy[3]&&m.y 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 Findmarket(); if(m.x>posx[4]&&m.x posy[4]&&m.y Windows(); } } } /*功能:彈出地點查詢框，作為輸入信息用*/ void Showplace(void){ char s[10];int choose;HWND wnd = GetHWnd();M: if(InputBox(s, 10, “查找地點，如:我的選擇是:AnA南大門 B南一樓 C西十二樓 D西五樓nE青年園 F圖書館 G科技樓 H喻園餐廳nI機械學院 J名人園 K中心操場 L東九樓nM沁苑 N喻園教工超市 O東教工超市nP東一食堂 Q紫荊園餐廳 R清真食堂nS百景園 T東五樓 U南三門 V南二門”,“輸入地點編號”,NULL,300,90,false)==true){ choose=s[0]-'A'+1; if(0 Showpoint(choose); else if(MessageBox(wnd, _T(“選擇出現在A-V，請重新輸入”), _T(“提醒”)，MB_OK | MB_ICONWARNING)== IDOK) goto M; } else Entermap();} void Showpoint(int i){ HWND wnd = GetHWnd();char s[][100] = {“你現在查詢的是 : ”,“ 【紅色為查詢地點所在位置】”};char message[100];int a=i;strcpy(message,s[0]);putimage(0,0,&map1);strcat(message,G1.vexs[a-1].name);strcat(message,s[1]);setfillcolor(0x001eff);fillcircle(G1.vexs[a-1].point.x,G1.vexs[a-1].point.y,7); if(MessageBox(wnd, _T(message), _T(“提醒”)，MB_OK | MB_ICONQUESTION)== IDOK)Sleep(1000);if(MessageBox(wnd, _T(“你要繼續查詢嗎？n是 : 返回查詢界面n否 : 進入地圖界面”), _T(“提醒”)，MB_YESNO | MB_ICONQUESTION)== IDNO) Viewmain();else Entermap();} /*功能:彈出最短路徑查詢框，作為輸入信息用*/ void Shortest(void){ char s[10];int choose1,choose2;HWND wnd = GetHWnd();華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 M: if(InputBox(s, 10, “查詢線路，如:我的選擇是:ABnA南大門 B南一樓 C西十二樓 D西五樓nE青年園 F圖書館 G科技樓 H喻園餐廳nI機械學院 J名人園 K中心操場 L東九樓nM沁苑 N喻園教工超市 O東教工超市nP東一食堂 Q紫荊園餐廳 R清真食堂nS百景園 T東五樓 U南三門 V南二門”,“輸入兩地點編號”,NULL,300,90,false)==true){ choose1=s[0]-'A'+1; choose2=s[1]-'A'+1; if(0 Showline(choose1,choose2); else if(MessageBox(wnd, _T(“選擇出現在A-V，請重新輸入”), _T(“提醒”)，MB_OK | MB_ICONWARNING)== IDOK) goto M; } else Entermap();} /*功能:彈出食堂查詢框，作為輸入信息用*/ void Findrepast(void){ char s[10];int choose1,choose2;HWND wnd = GetHWnd();M: if(InputBox(s, 10, “查找地點附近食堂，如:我的選擇是:AnA南大門 B南一樓 C西十二樓 D西五樓nE青年園 F圖書館 G科技樓 H喻園餐廳nI機械學院 J名人園 K中心操場 L東九樓nM沁苑 N喻園教工超市 O東教工超市nP東一食堂 Q紫荊園餐廳 R清真食堂nS百景園 T東五樓 U南三門 V南二門”,“輸入編號”,NULL,300,90,false)==true){ choose1=s[0]-'A'+1; if(0 { if(choose1==6||choose1==7||choose1==8){ choose2=8; Showline1(choose1,choose2);} else if(choose1==1||choose1==2||choose1==9||choose1==10||choose1==16||choose1==20){ choose2=16; Showline1(choose1,choose2);} else if(choose1==11||choose1==13||choose1==15||choose1==17){ choose2=17; Showline1(choose1,choose2);} else if(choose1==12||choose1==14||choose1==18){ choose2=18; Showline1(choose1,choose2);} else{ choose2=19; Showline1(choose1,choose2);} } else if(MessageBox(wnd, _T(“選擇出現在A-V,W-X，請重新輸入”), _T(“提醒”)，MB_OK | MB_ICONWARNING)== IDOK) goto M; } else Entermap();華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 } /*功能:彈出食堂超市查詢框，作為輸入信息用*/ void Findmarket(void){ char s[10];int choose1,choose2;HWND wnd = GetHWnd();M: if(InputBox(s, 10, “查找地點附近超市，如:我的選擇是:AnA南大門 B南一樓 C西十二樓 D西五樓nE青年園 F圖書館 G科技樓 H喻園餐廳nI機械學院 J名人園 K中心操場 L東九樓nM沁苑 N喻園教工超市 O東教工超市nP東一食堂 Q紫荊園餐廳 R清真食堂nS百景園 T東五樓 U南三門 V南二門”,“輸入編號”,NULL,300,90,false)==true){ choose1=s[0]-'A'+1; if(0 { if(choose1==8||choose1==12||choose1==14||choose1==18||choose1==19){ choose2=14; Showline2(choose1,choose2);} else{ choose2=15; Showline2(choose1,choose2);} } else if(MessageBox(wnd, _T(“選擇出現在A-V,W-X，請重新輸入”), _T(“提醒”)，MB_OK | MB_ICONWARNING)== IDOK) goto M; } else Entermap();} /*功能:輸出最短路徑線路圖及最短距離*/ void Showline(int i,int j){ HWND wnd = GetHWnd();char s[][100] = {“你現在查詢的是 : ”,“→”,“的最短距離nn”,“最短距離為:”,“米 【藍色為起點,紅色為終點】”};char message[100];char string[10];int a,b;a=i;b=j;strcpy(message,s[0]);putimage(0,0,&map1);strcat(message,G1.vexs[a-1].name);strcat(message,s[1]);strcat(message,G1.vexs[b-1].name);strcat(message,s[2]);strcat(message,s[3]);Linemin(a,b);itoa(shortest[a][b]*3.68,string,10);strcat(message,string);strcat(message,s[4]);setfillcolor(BLUE);fillcircle(G1.vexs[a-1].point.x,G1.vexs[a-1].point.y,7);setfillcolor(0x001eff);fillcircle(G1.vexs[b-1].point.x,G1.vexs[b-1].point.y,7);if(MessageBox(wnd, _T(message), _T(“提醒”), 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 MB_OK | MB_ICONQUESTION)== IDOK)Sleep(1000);if(MessageBox(wnd, _T(“你要繼續查詢嗎？n是 : 返回查詢界面n否 : 進入地圖界面”), _T(“提醒”)，MB_YESNO | MB_ICONQUESTION)== IDNO) Viewmain();else Entermap();} /*功能:輸出食堂最短路徑線路圖及最短距離*/ void Showline1(int i,int j){ HWND wnd = GetHWnd();char s[][100] = {“你現在查詢的是 : ”,“ 附近最近的食堂 ”,“ 其路徑如圖nn”,“最短距離為:”,“米 【藍色為起點,紅色為終點】”};char message[100];char string[10];int a,b;a=i;b=j;strcpy(message,s[0]);putimage(0,0,&map1);strcat(message,G1.vexs[a-1].name);strcat(message,s[1]);strcat(message,G1.vexs[b-1].name);strcat(message,s[2]);strcat(message,s[3]);Linemin(a,b);itoa(shortest[a][b]*3.68,string,10);strcat(message,string);strcat(message,s[4]);setfillcolor(BLUE);fillcircle(G1.vexs[a-1].point.x,G1.vexs[a-1].point.y,7);setfillcolor(0x001eff);fillcircle(G1.vexs[b-1].point.x,G1.vexs[b-1].point.y,7);if(MessageBox(wnd, _T(message), _T(“提醒”)，MB_OK | MB_ICONQUESTION)== IDOK)Sleep(1000);if(MessageBox(wnd, _T(“你要繼續查詢嗎？n是 : 返回查詢界面n否 : 進入地圖界面”), _T(“提醒”)，MB_YESNO | MB_ICONQUESTION)== IDNO) Viewmain();else Entermap();} /*功能:輸出食堂最短路徑線路圖及最短距離*/ void Showline2(int i,int j){ HWND wnd = GetHWnd();char s[][100] = {“你現在查詢的是 : ”,“ 附近最近的超市 ”,“ 其路徑如圖nn”,“最短距離為:”,“米 【藍色為起點,紅色為終點】”};char message[100];char string[10];int a,b;a=i;b=j;strcpy(message,s[0]);putimage(0,0,&map1);華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 strcat(message,G1.vexs[a-1].name);strcat(message,s[1]);strcat(message,G1.vexs[b-1].name);strcat(message,s[2]);strcat(message,s[3]);Linemin(a,b);itoa(shortest[a][b]*3.68,string,10);strcat(message,string);strcat(message,s[4]);setfillcolor(BLUE);fillcircle(G1.vexs[a-1].point.x,G1.vexs[a-1].point.y,7);setfillcolor(0x001eff);fillcircle(G1.vexs[b-1].point.x,G1.vexs[b-1].point.y,7);if(MessageBox(wnd, _T(message), _T(“提醒”)，MB_OK | MB_ICONQUESTION)== IDOK)Sleep(1000);if(MessageBox(wnd, _T(“你要繼續查詢嗎？n是 : 返回查詢界面n否 : 進入地圖界面”), _T(“提醒”)，MB_YESNO | MB_ICONQUESTION)== IDNO) Viewmain();else Entermap();} /*功能:繪制最短路徑線路圖*/ void Linemin(int i,int j){ setlinestyle(PS_DASH|PS_JOIN_ROUND,4);if(path[i][j]==i||path[i][j]==j) line(G0.vexs[i].point.x,G0.vexs[i].point.y,G0.vexs[j].point.x,G0.vexs[j].point.y);else{ Linemin(path[i][j],i); Linemin(path[i][j],j);} setlinestyle(PS_SOLID,1);} /*功能:地圖地點相關信息的介紹*/ void Viewmain(){ IMAGE temp;int choose;putimage(0,0,&map);getimage(&temp,465,275,210,260);setfillcolor(0x001eff);settextstyle(20,0,“楷體”);settextcolor(BLACK);setbkmode(TRANSPARENT);for(choose=1;choose<=N;choose++){ fillcircle(pos[choose-1][0],pos[choose-1][1],7);} outtextxy(0,0,“返回”);outtextxy(80,0,“Tips:鼠標移動到相應的點范圍即可查看對應地點信息”);MOUSEMSG m;while(true){ m=GetMouseMsg(); if(m.uMsg==WM_MOUSEMOVE)華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 { if(m.x>pos[0][0]-7&&m.x pos[0][1]-7&&m.y putimage(465,275,&Aa); else if(m.x>pos[1][0]-7&&m.x pos[1][1]-7&&m.y putimage(465,275,&Bb); else if(m.x>pos[2][0]-7&&m.x pos[2][1]-7&&m.y putimage(465,275,&Cc); else if(m.x>pos[3][0]-7&&m.x pos[3][1]-7&&m.y putimage(465,275,&Dd); else if(m.x>pos[4][0]-7&&m.x pos[4][1]-7&&m.y putimage(465,275,&Ee); else if(m.x>pos[5][0]-7&&m.x pos[5][1]-7&&m.y putimage(465,275,&Ff); else if(m.x>pos[6][0]-7&&m.x pos[6][1]-7&&m.y putimage(465,275,&Gg); else if(m.x>pos[7][0]-7&&m.x pos[7][1]-7&&m.y putimage(465,275,&Hh); else if(m.x>pos[8][0]-7&&m.x pos[8][1]-7&&m.y putimage(465,275,&Ii); else if(m.x>pos[9][0]-7&&m.x pos[9][1]-7&&m.y putimage(465,275,&Jj); else if(m.x>pos[10][0]-7&&m.x pos[10][1]-7&&m.y putimage(465,275,&Kk); else if(m.x>pos[11][0]-7&&m.x pos[11][1]-7&&m.y putimage(465,275,&Ll); else if(m.x>pos[12][0]-7&&m.x pos[12][1]-7&&m.y putimage(465,275,&Mm); else if(m.x>pos[13][0]-7&&m.x pos[13][1]-7&&m.y putimage(465,275,&Nn); else if(m.x>pos[14][0]-7&&m.x pos[14][1]-7&&m.y putimage(465,275,&Oo); else if(m.x>pos[15][0]-7&&m.x pos[15][1]-7&&m.y putimage(465,275,&Pp); else if(m.x>pos[16][0]-7&&m.x pos[16][1]-7&&m.y putimage(465,275,&Qq); else if(m.x>pos[17][0]-7&&m.x pos[17][1]-7&&m.y putimage(465,275,&Rr); else if(m.x>pos[18][0]-7&&m.x pos[18][1]-7&&m.y putimage(465,275,&Ss);華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 else if(m.x>pos[19][0]-7&&m.x pos[19][1]-7&&m.y putimage(465,275,&Tt); else if(m.x>pos[20][0]-7&&m.x pos[20][1]-7&&m.y putimage(465,275,&Uu); else if(m.x>pos[21][0]-7&&m.x pos[21][1]-7&&m.y putimage(465,275,&Vv); else putimage(465,275,&temp); } if(m.uMsg==WM_LBUTTONUP) { if(m.x>0&&m.x<40&&m.y>0&&m.y<20) { setbkmode(TRANSPARENT); Windows(); } } } } /*功能:進入幫助功能界面，顯示操作說明*/ void HelP(void){ putimage(0,0,&help);MOUSEMSG m;while(true){ m=GetMouseMsg(); if(m.uMsg==WM_LBUTTONUP) if(m.x>0&&m.x<070&&m.y>0&&m.y<50) Windows();} } /*功能:顯示作者相關信息*/ void About(void){ int posx[]={0,25};int posy[]={0,350};cleardevice();putimage(0,0,&about);MOUSEMSG m;while(true){ m=GetMouseMsg(); if(m.uMsg==WM_LBUTTONUP) if(m.x>posx[0]&&m.x posy[0]&&m.y Windows();} } /*退出系統，結束程序的運行*/ void Quit(void){ HWND wnd = GetHWnd();if(MessageBox(wnd, _T(“你確定要退出嗎？”), _T(“提醒”)，31 華 中 科 技 大 學 計 算 機 科 學 與 技 術 學 院 課 程 設 計 報 告 } { } MB_OKCANCEL | MB_ICONQUESTION)== IDOK)closegraph();exit(0); #include ERROR 0//定義字符常量error #define OK 1//定義字符常量OK #define INFINITY INT_MAX//INT_MAX是系統庫中定義的無窮大常量，即2個字節所能表示的最大數 #define MAX_VERTEX_NUM 21//定義圖、網的最大定點數為21 #define STACK_INIT_SIZE 100//定義棧的容量 #define STACKINCREAMENT 10//定義棧的每次增長量 #define MAX_INT 10000 //無窮大 typedef int AdjType;typedef struct{ int pi[MAX_VERTEX_NUM];//存放v到vi的一條最短路徑 int end;}PathType;typedef char VType;//設頂點為字符類型 typedef enum{DG,UDG,DN,UDN}GraphKind;//定義圖、網的枚舉常量 /*················· 鄰接矩陣····················*/ typedef struct ArcCell { int adj; //弧的權值 //infotype *info;}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{ char vexs[MAX_VERTEX_NUM];//存儲頂點的數組 AdjMatrix arcs;//存儲鄰接矩陣的二維數組 int vexnum,arcnum;//頂點數和弧數 GraphKind kind;//鏈接矩陣的類型 }MGraph; /*················· 鄰接表····················*/ typedef struct ArcNode{ int adjvex;//與首節點關聯的頂點 int quan;//該頂點的權值 struct ArcNode *nextarc;//指向下一個節點的指針 }ArcNode,*AList;typedef struct VNode { char data;//鏈表的各頂點 AList firstarc;//鏈表的首節點 }VNode,AdjList[MAX_VERTEX_NUM];typedef struct{ AdjList vertices;//存儲鏈接表的各頂點 int vexnum,arcnum;//頂點書和弧數 GraphKind kind;//鏈接表的類型 }ALGraph; /*················· 隊列····················*/ typedef struct QNode{ char data;//隊列中元素數據 struct QNode *next;//指向下一元素的指針 }QNode,*QueuePre;typedef struct{ QueuePre front;//隊首指針 QueuePre rear;//隊尾指針 }LinkQueue; /*················· 棧····················*/ typedef struct { int *base;//棧底指針 int *top;//棧首指針 int stacksize;//棧的大小 }SqStack; /*················· 求最小生成樹中的輔助數組··········*/ typedef struct { char adjvex;//最小生成樹的節點 int lowcost;//到該節點的最小權值開銷 }closedges[MAX_VERTEX_NUM]; int option; //圖的類型標識符 int visited[MAX_VERTEX_NUM]; //頂點訪問標記數組 int indegree[MAX_VERTEX_NUM];//頂點入度記錄數組 int ve[MAX_VERTEX_NUM]; //頂點權值記錄數組 /*················· 鏈接矩陣類型設置··········*/ int SetGraphKind(MGraph &G,int option){ switch(option){ case 1: G.kind=DG;break; case 2: G.kind=UDG;break; case 3: G.kind=DN;break; case 4: G.kind=UDN;break; default: return ERROR; } return OK;} /*················· 鄰接表類型設置··········*/ int SetGraphKind(ALGraph &G,int option){ switch(option){ case 1: G.kind=DG;break; case 2: G.kind=UDG;break; case 3: G.kind=DN;break; case 4: G.kind=UDN;break; default: return ERROR; } return OK;} /*················· 鄰接矩陣頂點定位 ·················將頂點V代入，查詢頂點存儲數組，返回其數組下標 ··········*/ int LocateVex(MGraph G,char v){ int m; for(m=1;m<=G.vexnum;m++){ if(G.vexs[m]==v)return m; } printf(“您輸入的頂點不存在”); return ERROR;} /*················· 鄰接表頂點定位 ·················將頂點V代入，查詢頂點存儲數組，返回其數組下標 ··········*/ int LocateVex(ALGraph G,char v){ int m; for(m=1;m<=G.vexnum;m++){ if(G.vertices[m].data==v)return m; } printf(“您輸入的頂點不存在”); return ERROR; } /*················· 隊列創建··········*/ int InitQueue(LinkQueue &Q){ Q.front=Q.rear=(QueuePre)malloc(sizeof(QNode));//申請存儲空間，隊首隊尾指向同一位置 if(!Q.front)return ERROR;Q.front->next=NULL;return OK;} /*················· 元素入隊··········*/ int EnQueue(LinkQueue &Q,int e){ QueuePre p;p=(QueuePre)malloc(sizeof(QNode));if(!p)return OK;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return OK;} /*················· 元素出隊··········*/ int DeQueue(LinkQueue &Q,int &e){ QueuePre p;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;} /*················· 判斷隊列是否為空··········*/ int QueueEmpty(LinkQueue Q){ if(Q.front==Q.rear) return OK;return ERROR;} /*················· 棧的創建··········*/ int InitStack(SqStack &S){ S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;} /*················· //元素入棧··········*/ int Push(SqStack &S,int e){ if(S.top-S.base>=S.stacksize){ S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(int)); if(!S.base)return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREAMENT;} *S.top++=e;return OK;} /*················· 元素出棧··········*/ int Pop(SqStack &S,int &e){ if(S.top==S.base)return ERROR; e=*--S.top;return OK;} /*················· 判斷棧是否為空··········*/ int StackEmpty(SqStack S){ if(S.top==S.base)return OK;return ERROR;} /*················· 創建鄰接矩陣··········*/ int CreatGraph(MGraph &G){ int i,j,k,w;char x,y; if(!SetGraphKind(G,option)){printf(“對圖類型的設置失敗”);return ERROR;}//設置鏈接矩陣類型 printf(“鄰接矩陣：請輸入定點的個數、弧的個數：”); scanf(“%d %d”,&G.vexnum,&G.arcnum); if(G.vexnum>20){ printf(“您輸入的頂點個數超過最大值”); return ERROR; }//if printf(“請輸入%d個頂點n”,G.vexnum); for(i=1;i<=G.vexnum;++i){//輸入矩陣的各頂點 fflush(stdin);//清除緩存，略過 scanf(“%c”,&G.vexs[i]); }//for if(G.kind==DG||G.kind==UDG){//1.有向圖和無向圖的矩陣創建 for(i=1;i<=G.vexnum;i++)//矩陣初始化 for(j=1;j<=G.vexnum;j++) G.arcs[i][j].adj=0; if(G.kind==DG){//2.有向圖 printf(“請輸入有向圖的兩個相鄰的頂點 for(k=1;k<=G.arcnum;k++){//循環輸入 fflush(stdin); scanf(“%c%c”,&x,&y);//輸入矩陣中弧關聯的兩頂點 i=LocateVex(G,x);j=LocateVex(G,y);//將兩頂點轉換成頂點存儲數組的下標 G.arcs[i][j].adj=1; }//for }//2.if else{//2.無向圖 printf(“請輸入無向圖的兩個相鄰的頂點（x,y）：n”); for(k=1;k<=G.arcnum;k++){fflush(stdin); scanf(“%c%c”,&x,&y); i=LocateVex(G,x);j=LocateVex(G,y); G.arcs[i][j].adj=1;G.arcs[j][i].adj=G.arcs[i][j].adj;//反向關聯兩頂點 }//for }//2.else }//1.if else{//1.有向網和無向網 for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j].adj=INT_MAX;//矩陣初始化 if(G.kind==DN){ //3.有向網 printf(“請輸入有向網的兩個相鄰的頂點 for(k=1;k<=G.arcnum;k++){fflush(stdin); scanf(“%c%c %d”,&x,&y,&w); i=LocateVex(G,x);j=LocateVex(G,y); G.arcs[i][j].adj=w; }//for }//3.if else{//3 printf(“請輸入無向網的兩個相鄰的頂點（x,y）以及相應的權值w：n”); for(k=1;k<=G.arcnum;k++){fflush(stdin); scanf(“%c%c %d”,&x,&y,&w); i=LocateVex(G,x);j=LocateVex(G,y); G.arcs[i][j].adj=w;G.arcs[j][i].adj=G.arcs[i][j].adj;//逆向關聯 }//for }//3.else } return OK;} /*··············在鄰接表中插入節點··· ··········*/ int setList(int x,int y,ALGraph &G,int key[]){ int i,j,m,n;AList p,q; m=LocateVex(G,x);//獲取節點x對應的數組下標 n=LocateVex(G,y); p=G.vertices[m].firstarc;//獲取第m個鏈表的首節點 q=(AList)malloc(sizeof(ArcNode));//申請節點空間 if(!q)return ERROR; q->nextarc=NULL; q->adjvex=n; while(key[m]&&p->nextarc){//key存儲著該鏈表的長度，當其不為零時在首節點后插入新節點 p=p->nextarc; key[m]++;//鏈表長度加1 } if(!key[m]){G.vertices[m].firstarc=q;key[m]++;}//當鏈表長度為零時，新節點為首節點 else p->nextarc=q; return 1;} /*················· 創建鄰接表··········*/ int CreatAList(ALGraph &G){ int i,j,m,n,key[MAX_VERTEX_NUM];char x,y,w;AList p,q;SetGraphKind(G,option);printf(“鄰接表：請輸入頂點的個數和弧的個數：”);scanf(“%d %d”,&G.vexnum ,&G.arcnum);if(G.vexnum>20){ printf(“您輸入的頂點個數超過最大值”); return ERROR; } printf(“請輸入個頂點：n”);for(i=1;i<=G.vexnum;i++){ fflush(stdin); scanf(“%c”,&G.vertices[i].data); G.vertices[i].firstarc=NULL; key[i]=0;} if(G.kind==DG){//有向圖 printf(“請輸入弧（如AB,其中AB與BA是不同的弧）：n”); for(j=1;j<=G.arcnum;j++){ fflush(stdin); scanf(“%c%c”,&x,&y);//輸入弧的兩頂點 m=LocateVex(G,x);//將兩頂點轉換成數組下標 n=LocateVex(G,y); p=G.vertices[m].firstarc;//獲取第m個鏈表的首節點，及以第m個頂點為首節點的鏈表 q=(AList)malloc(sizeof(ArcNode));//申請節點存儲空間 if(!q)return ERROR; q->nextarc=NULL; q->adjvex=n; while(key[m]&&p->nextarc){//鏈表長度不為零，且下一個節點存在時，在首節點后插入新節點 p=p->nextarc; key[m]++; } if(!key[m]){G.vertices[m].firstarc=q;key[m]++;}//鏈表長度為零時，新節點為首節點 else p->nextarc=q; } } if(G.kind==UDG){ printf(“請輸入弧（如AB,其中AB與BA是不同的弧）：n”); for(j=1;j<=G.arcnum;j++){ fflush(stdin); scanf(“%c%c”,&x,&y); setList(x,y,G,key); setList(y,x,G,key); } } if(G.kind==DN){ printf(“請輸入依次輸入弧以及這條弧的權值（如AB 8,其中AB與BA是不同的弧）：n”); for(j=1;j<=G.arcnum;j++){ fflush(stdin); scanf(“%c%c %d”,&x,&y,&w); m=LocateVex(G,x); n=LocateVex(G,y); p=G.vertices[m].firstarc; q=(AList)malloc(sizeof(ArcNode)); if(!q)return ERROR; q->nextarc=NULL; q->quan=w; q->adjvex=n; while(key[m]&&p->nextarc){ p=p->nextarc; key[m]++; } if(!key[m]){G.vertices[m].firstarc=q;key[m]++;} else p->nextarc=q; } } if(G.kind==UDN){ printf(“無向網請輸入依次輸入弧以及這條弧的權值（如AB 8,其中AB與BA是不同的弧）：n”); for(j=1;j<=G.arcnum;j++){ fflush(stdin); scanf(“%c%c %d”,&x,&y,&w); m=LocateVex(G,x); n=LocateVex(G,y); p=G.vertices[m].firstarc; q=(AList)malloc(sizeof(ArcNode)); if(!q)return ERROR; q->nextarc=NULL; q->quan=w; q->adjvex=n; while(key[m]&&p->nextarc){ p=p->nextarc; key[m]++; } if(!key[m]){G.vertices[m].firstarc=q;key[m]++;} else p->nextarc=q; int temp; temp=m; m=n; n=temp; p=G.vertices[m].firstarc; q=(AList)malloc(sizeof(ArcNode)); if(!q)return ERROR; q->nextarc=NULL; q->quan=w; q->adjvex=n; while(key[m]&&p->nextarc){ p=p->nextarc; key[m]++; } if(!key[m]){G.vertices[m].firstarc=q;key[m]++;} else p->nextarc=q; } } return OK;} /*················· 判斷以第v個頂點為首節點的鏈表是否存在··········*/ int FirstAdjVex(ALGraph G,int v){ if(G.vertices[v].firstarc) } return G.vertices[v].firstarc->adjvex;//存在則返回首節點 return 0;/*················· 獲取以第v個頂點為首節點的鏈表中的節點w的子節點··········*/ int NextAdjVex(ALGraph G,int v,int w){ AList s;s=G.vertices[v].firstarc;//獲取鏈表的首節點v while(s->adjvex!=w)//當節點不是w時，指針后移直到找到節點w或到達最后一個節點 s=s->nextarc;if(s->nextarc)//跳出循環后，節點不為空，則表明找到了節點w，否則表示已至鏈表最后一個節點 return s->nextarc->adjvex;return 0;} /*················· 遍歷節點v的葉子節點··········*/ void DFS(ALGraph G,int v){ int w;visited[v]=1;printf(“%c ”,G.vertices[v]);//輸出第v個頂點，并標記為已訪問 for(w=FirstAdjVex(G,v);w>=1;w=NextAdjVex(G,v,w)){//遍歷第v個頂點的子節點，并遞歸遍歷子節點的子節點 if(!visited[w])DFS(G,w); } } /*················· 圖的深度優先遍歷··········*/ void DFSTraverse(ALGraph G){ int v;visited[0]=1;//數組的存儲是從1開始的，數組【0】不使用 for(v=1;v<=G.vexnum;v++)visited[v]=0;//初始化各頂點的訪問狀態為未訪問 for(v=1;v<=G.vexnum;v++) if(!visited[v])DFS(G,v);//從第一個頂點開始遍歷 } /*················· 圖的廣度優先遍歷··········*/ void BFSTraverse(ALGraph G){ int v,w,u;LinkQueue Q;for(v=1;v<=G.vexnum;v++)visited[v]=0;//初始化各頂點為未訪問 visited[0]=1;//數組的存儲是從1開始的，數組【0】不使用 InitQueue(Q);//創建隊列 for(v=1;v<=G.vexnum;v++)//從第一個頂點開始遍歷 if(!visited[v]){ visited[v]=1; printf(“%c ”,G.vertices[v]); EnQueue(Q,v);//將該頂點標記為已訪問，輸出，并加入到隊列中 while(!QueueEmpty(Q)){//遍歷隊列中頂點的所有子節點 DeQueue(Q,u);//獲取隊首的頂點，賦值給U for(w=FirstAdjVex(G,u);w>=1;w=NextAdjVex(G,u,w)){//遍歷頂點U所有未訪問的子節點 if(!visited[w]){ visited[w]=1; printf(“%c ”,G.vertices[w]); EnQueue(Q,w);//將子節點加入隊列，以便遍歷子節點的子節點 }//if else break; }//for }//while }//if } /*················· 計算各頂點入度··········*/ void FindInDegree(ALGraph G,int in[]){ int i,j,k;AList p;for(k=1;k<=G.vexnum;k++)in[k]=0;//初始化各頂點入度為0 for(i=1;i<=G.vexnum;i++){ p=G.vertices[i].firstarc;//獲取個鏈表的首節點 while(p){//遍歷鏈表的子節點 j=p->adjvex;//獲取子節點 in[j]++;//子節點的入度加1 in[i]++; p=p->nextarc;//指向下一子節點 } } } /*················· 拓撲排序（打印輸出）··········*/ int TopologicalSort(ALGraph G){ int i,k,count;AList p;SqStack S; FindInDegree(G,indegree);//計算各頂點入度 InitStack(S);//創建棧 for(i=1;i<=G.vexnum;i++) if(!indegree[i])Push(S,i);//尋找入度為0的點，并加入到棧中 count=0;//輸出的頂點個數 if(StackEmpty(S))printf(“此有向圖不符合條件！”);while(!StackEmpty(S)){ Pop(S,i);//從棧中取出頂點開始輸出 printf(“%c ”,G.vertices[i].data); ++count;//輸出的頂點個數加1 for(p=G.vertices[i].firstarc;p;p=p->nextarc){//將頂點i的子節點的入度減1 k=p->adjvex; if(!(--indegree[k]))Push(S,k);//如子節點的入度減為0，則入棧 } } if(count<=G.vexnum)return ERROR; else return OK;} /*················· 求最小生成樹··········*/ int Minimum(MGraph G,closedges m){ int i,j,min=INFINITY;for(i=1;i<=G.vexnum;i++){//從待選的可達集合中選取一條代價最小的邊 if(m[i].lowcost){//到頂點i可達時執行，即到頂點的權值不為0 if(m[i].lowcost min=m[i].lowcost; j=i; } } } return j;} /*················· 最小生成樹（普里姆算法實現）··········*/ void MinSpanTree_PRIM(MGraph G,char u){ int i,j,k;closedges closedge; k=LocateVex(G,u);//獲取初始頂點對應的數組下標 for(j=1;j<=G.vexnum;j++)//初始化輔助數組，計算從初始頂點到各頂點的最小代價 if(j!=k){ } closedge[j].adjvex=u;//u是已連通的頂點，表示該頂點J是同那個頂點連在一起 closedge[j].lowcost=G.arcs[k][j].adj; closedge[k].lowcost=0;//頂點k到自身的最小代價設為0，即該頂點已加入最小生成樹中 for(i=2;i<=G.vexnum;i++){ k=Minimum(G,closedge);//獲取最小代價邊連通的頂點 printf(“%c%c ”,closedge[k].adjvex,G.vexs[k]);//輸出最小生成樹的弧 closedge[k].lowcost=0;//該頂點已加入最小生成樹中 for(j=1;j<=G.vexnum;j++)//將頂點k代入重新計算到待連通頂點的最小代價 if(G.arcs[k][j].adj closedge[j].adjvex=G.vexs[k]; closedge[j].lowcost=G.arcs[k][j].adj; } } } /*················· 對鏈表進行拓撲排序，并存儲在棧中··········*/ int TopologicalOrder(ALGraph G,SqStack &T){ int i,j,k,count;SqStack S; AList p;FindInDegree(G,indegree);InitStack(S); for(i=1;i<=G.vexnum;i++)if(!indegree[i])Push(S,i);InitStack(T);count=1;for(i=1;i<=G.vexnum;i++)ve[i]=0;//初始化到達各頂點的總權值花銷為0 while(!StackEmpty(S)){ Pop(S,j);Push(T,j);++count; for(p=G.vertices[j].firstarc;p;p=p->nextarc){ k=p->adjvex; if(--indegree[k]==0)Push(S,k); if(ve[j]+p->quan>ve[k])ve[k]=ve[j]+p->quan;//頂點J的子節點K的總權值=頂點j的權值花銷+弧的權值,即該頂點的最早發生時間 } } if(count<=G.vexnum)return ERROR;else return OK;} /*················· 關鍵路徑 int j 指向頂點的數組下標 int k 被指向頂點的數組下標標 int ee 最早發生時間 int el 最晚發生時間 int dut 事件持續時間 char tag 關鍵路徑標識符，*表示該弧為關鍵路徑 SqStack T 堆 Alist p 鏈表的節點 int v1[MAX_VERTEX_NUM] 頂點權值記錄數組，及該頂點的最早發生時間 ··········*/ int CriticalPath(ALGraph G){ int i,j,k,ee,el,dut,v1[MAX_VERTEX_NUM];SqStack T;AList p;char tag;int str[10];int count=0;//聲明一個數組來存放關鍵路徑的各個節點，count表示當前數組使用長度，也可理解為下一節點的存放位置 if(!TopologicalOrder(G,T))return ERROR;//按拓撲排序將各頂點依次入棧 for(i=1;i<=G.vexnum;i++){//初始化各頂點的權值為最后一個頂點的總權值花銷，即工程的總時間花銷 v1[i]=ve[G.vexnum];} while(!StackEmpty(T))//按拓撲順序出棧，分別計算各頂點的最晚發生時間 for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){ k=p->adjvex;dut=p->quan; if(v1[k]-dut } for(j=1;j<=G.vexnum;j++)//循環代入所有頂點，遍歷其子節點，根據弧的權值，得到最早發生時間和最晚發生時間，并判斷該弧是否為關鍵路徑 for(p=G.vertices[j].firstarc;p;p=p->nextarc){ k=p->adjvex;dut=p->quan; ee=ve[j];el=v1[k]-dut; tag=(ee==el)?'*':' '; printf(“%d %d %d %d %d %cn”,j,k,dut,ee,el,tag); } /* 下面為非必需代碼，功能為輸出關鍵路徑*/ if(count==0)//存儲關鍵路徑的第一個節點（第一個鏈接表的首節點—— str[count++]=j;if(tag=='*')//如果該弧為關鍵路徑，則將該弧的被指向頂點存儲到str中 { str[count++]=k;} for(int n=0;n printf(“%d”,str[n]); printf(“->”); } return OK;} //求關鍵路徑 //Dijkstra算法 //求G（用鄰接矩陣表示）中源點v到其他各頂點最短路徑,n為G中頂點數 void Dijkstra(MGraph * G,PathType path[],int dist[],int v,int n){ int i,j,count,s[MAX_VERTEX_NUM],max,u;//s[n]用來標志源點到某頂點的最短路徑是否求出 for(i=1;i<=n;i++){//1.初始化 s[i]=0;if(G->arcs[v][i].adj!=INFINITY)dist[i]=G->arcs[v][i].adj;else dist[i]=MAX_INT;//v到其他頂點的權為當前最短路徑，送dist[i] path[i].pi[0]=v;path[i].end=0;} dist[v]=0;s[v]=1;//源點到源點本身的最短路徑求出 count=1; while(count<=n-1){//求n-1條最短路徑 max=MAX_INT;// MAX_INT為無窮大值，需要實際情況設置 for(j=1;j<=n;j++){//2.找當前最短路徑長度 if(s[j]==0&&dist[j] if(max==MAX_INT)break;//最短路徑求完（不足n-1）條，跳出while循環 s[u]=1;//表示V到Vu最短路徑求出 path[u].end++;path[u].pi[path[u].end]=u;for(j=1;j<=n;j++){//3.u求出后，修改dist和path向量，執行完后返回2，知道跳出循環 if(s[j]==0&&dist[j]>dist[u]+G->arcs[u][j].adj&&G->arcs[u][j].adj!=INFINITY){ dist[j]=dist[u]+G->arcs[u][j].adj;path[j]=path[u];} } count++;} } /*················· 有向圖的功能操作界面··········*/ void DG_(MGraph G1,ALGraph G2){ int i,j,k,m,key;AList s;char x,y; for(k=0;;){ key=0;system(“cls”);//清空顯示 printf(“**************************n”); printf(“你選擇了對有向圖的基本操作及應用：n1創建鄰接矩陣n2創建鄰接表n3拓撲結構n4退出n”); printf(“**************************n”); printf(“請選擇：”); scanf(“%d”,&m); switch(m){ case 1: CreatGraph(G1);printf(“有向圖的鄰接矩陣：n”); for(i=1;i<=G1.vexnum;i++){//輸出鄰接矩陣 for(j=1;j<=G1.vexnum;j++){ printf(“ %d”,G1.arcs[i][j].adj); } printf(“n”); }break; case 2: CreatAList(G2);printf(“有向圖的鄰接表：n”); for(i=1;i<=G2.vexnum;i++){//輸出鏈接表 printf(“%c:”,G2.vertices[i]); s=G2.vertices[i].firstarc; while(s){ j=s->adjvex;fflush(stdin); printf(“<%c ”,G2.vertices[i]); printf(“%c> ”,G2.vertices[j]); s=s->nextarc; } printf(“n”); }break; case 3:printf(“有向圖的拓撲排序：n”);TopologicalSort(G2);break;case 4:key=1;break;} printf(“n”); if(key)break;//跳出循環，返回上一層 system(“pause”);//暫停程序執行，直到監聽到操作 } printf(“nn”);} //DG /*················· 有向網的功能操作界面··········*/ void DN_(MGraph G1,ALGraph G2){ int i,j,k,m,key;AList s; for(k=0;;){ key=0; system(“cls”); printf(“**************************n”); printf(“你選擇了對有向網的基本操作及應用：n1創建鄰接矩陣n2創建鄰接表n3關鍵路徑n4最短路徑n5退出n”); printf(“**************************n”); printf(“請選擇：”); scanf(“%d”,&m); switch(m){ case 1: CreatGraph(G1);printf(“有向網的鄰接矩陣：n”); for(i=1;i<=G1.vexnum;i++){ for(j=1;j<=G1.vexnum;j++){ if(G1.arcs[i][j].adj==INT_MAX)printf(“ ∞”); else printf(“ %d”,G1.arcs[i][j].adj); } printf(“n”); }break; case 2: CreatAList(G2);printf(“有向網的鄰接表：n”); for(i=1;i<=G2.vexnum;i++){ printf(“%c:”,G2.vertices[i]); s=G2.vertices[i].firstarc; while(s){ j=s->adjvex;fflush(stdin); printf(“<%c ”,G2.vertices[i]); printf(“%c> ”,G2.vertices[j]); printf(“ %d ”,s->quan); s=s->nextarc; } printf(“n”); }break; case 3: printf(“有向網關鍵路徑：n”);CriticalPath(G2);break; case 4: {int i,j,v,count=0;//v為起點，n為頂點個數 char c; PathType path[MAX_VERTEX_NUM];//v到各頂點的最短路徑向量 int dist[MAX_VERTEX_NUM];//v到各頂點最短路徑長度向量 printf(“請輸入最短路徑起點：”); fflush(stdin); scanf(“%c”,&c); v=LocateVex(G1,c); Dijkstra(&G1,path,dist,v,G1.vexnum); for(i=1;i<=G1.vexnum;i++){ if(dist[i]!=0&&dist[i]!=MAX_INT) { printf(“%c到%c的最短路徑:”,G1.vexs[v],G1.vexs[i]); for(j=0;j<=path[i].end;j++){ printf(“%c ”,G1.vexs[path[i].pi[j]]); } printf(“n”); printf(“最短路徑長度:%d”,dist[i]);//輸出為MAX_INT則表示兩點間無路徑 printf(“n”); } else count++; } if(count==G1.vexnum)printf(“該頂點無出度！”); break;} case 5:key=1;break; }printf(“n”); if(key)break;system(“pause”);} printf(“nn”);} //DN /*················· 無向圖的功能操作界面··········*/ void UDG_(MGraph G1,ALGraph G2){ int i,j,k,m,key;AList s; for(k=0;;){ key=0; system(“cls”); printf(“**************************n”); printf(“你選擇了對無向圖的基本操作及應用：n1創建鄰接矩陣n2創建鄰接表n3深度遍歷n4廣度遍歷n5退出n”); printf(“**************************n”); printf(“請選擇：”); scanf(“%d”,&m); switch(m){ case 1:CreatGraph(G1);printf(“無向圖的鄰接矩陣：n”); for(i=1;i<=G1.vexnum;i++){ for(j=1;j<=G1.vexnum;j++){ printf(“ %d”,G1.arcs[i][j].adj); } printf(“n”); }break; case 2: CreatAList(G2);printf(“無向圖的鄰接表：n”); for(i=1;i<=G2.vexnum;i++){ printf(“%c:”,G2.vertices[i]); s=G2.vertices[i].firstarc; while(s){ j=s->adjvex;fflush(stdin); printf(“(%c ”,G2.vertices[i]); printf(“%c)”,G2.vertices[j]); s=s->nextarc; } printf(“n”); }break; case 3: printf(“無向圖的深度優先遍歷：n”);DFSTraverse(G2);printf(“n”);break; case 4: printf(“無向圖的廣度優先遍歷：n”);BFSTraverse(G2);break; case 5: key=1;break; }printf(“n”); if(key)break; system(“pause”);} printf(“nn”);} //UDG /*················· 無向網的功能操作界面··········*/ void UDN_(MGraph G1,ALGraph G2){ int i,j,m,k,key;AList s;char u; for(k=0;;){ key=0; system(“cls”); printf(“**********************************n”); printf(“你選擇了對無向網的基本操作及應用：n1創建鄰接矩陣n2創建鄰接表n3最小生成樹n4退出n”); printf(“**********************************n”); printf(“請選擇：”); scanf(“%d”,&m); switch(m){ case 1: CreatGraph(G1);printf(“無向網的鄰接矩陣：n”); for(i=1;i<=G1.vexnum;i++){ for(j=1;j<=G1.vexnum;j++){ if(G1.arcs[i][j].adj==INT_MAX)printf(“ ∞”); else printf(“ %d”,G1.arcs[i][j].adj); } printf(“n”); }break; case 2: CreatAList(G2);printf(“無向網的鄰接表：n”); for(i=1;i<=G2.vexnum;i++){ printf(“%c:”,G2.vertices[i]); s=G2.vertices[i].firstarc; while(s){ j=s->adjvex;fflush(stdin); printf(“(%c ”,G2.vertices[i]); printf(“%c)”,G2.vertices[j]); printf(“ %d ”,s->quan); s=s->nextarc; } printf(“n”); }break; case 3: printf(“請輸入第一個頂點：”); fflush(stdin); scanf(“%c”,&u); printf(“無向網的最小生成樹：n”); MinSpanTree_PRIM(G1,u);break; case 4: key=1;break; }printf(“n”); if(key)break; system(“pause”);} printf(“nn”);} //UDN /*················· 首界面··········*/ void main(){ MGraph G1; ALGraph G2;int i,n;for(i=0;;){ n=0; system(“cls”); printf(“n”); printf(“**************圖的基本操作及應用***************n1：有向圖的基本操作及應用n2：無向圖的基本操作及應用n3：有向網的基本操作及應用n4：無向網的基本操作及應用n5: 退出n”); printf(“********************************n”); printf(“請選擇：”); scanf(“%d”,&option); printf(“nn”); switch(option){ case 1: DG_(G1,G2);break; case 2: UDG_(G1,G2);break; case 3: DN_(G1,G2);break; case 4: UDN_(G1,G2);break; case 5: n=1;break; default: printf(“你輸入的編碼有誤！”);break; } if(n)break; printf(“nn”);} } 計算機網絡應用課程設計 報告 系（院）： 計算機科學學院 專業班級： 計科11511 姓 名： 鐘燦均 學 號： 201503687 指導教師： 余紹文 設計時間： 2017.6.12-2017.6.23 設計地點： 12教1樓機房 一、課程設計目的和意義 計算機網絡課程設計的目的，是為了讓我們更深入地掌握計算機網絡的核心內容，實現理論與實踐相結合。讓學生用具體的實踐成果，體現對理論知識的掌握程度。有利于學生提高計算機網絡的實踐能力，加深對計算機網絡理論知識的理解。其基本目的是： 1． 培養學生理論聯系實際的設計思想，訓練綜合運用所學的基礎理論知識，結合生產實際分析和解決網絡應用中問題的能力，從而使基礎理論知識得到鞏固和加深。2． 學習掌握網絡應用工程的一般設計過程和方法。 二、設計題目和要求 1．編寫程序，實現系統的基本功能； 2．要有用戶界面：要求至少采用文本菜單界面；鼓勵采用圖形菜單界面； 3．寫課程設計報告，內容包括： ? 封面（參見附錄I） ? 需求分析：以無歧義的陳述說明程序設計的任務，強調的是程序要做什么？給出功能模塊圖和流程圖。同時明確規定：輸入的形式和輸出值的范圍；輸出的形式；程序所能夠達到的功能；測試數據，包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。? 概要設計：包括程序設計組成框圖，程序中使用的存儲結構設計說明（如果指定存儲結構請寫出該存儲結構的定義）。 ? 詳細設計：包括模塊功能說明（如函數功能、入口及出口參數說明，函數調用關系描述等），每個模塊的算法設計說明（可以是描述算法的流程圖）。其中源程序要按照寫程序的規則來編寫，結構清晰，重點函數的重點變量，重點功能部分要加上清晰的程序注釋。? 運行結果：包括典型的界面、輸入和輸出數據等； ? 總結：包括課程設計中遇到的問題，解決問題的過程及體會、收獲、對課程設計的認識與思考等。 ? 附錄：包括主要程序清單，要有適當的注釋，使程序容易閱讀。? 開發環境：windows 10 ? 開發工具： vs2008 題目3：基于UDP協議的簡易聊天機器人 設計目標： 1．了解Socket通信的原理，在此基礎上編寫一個聊天程序； 2．理解upd原理;課程設計系統組成及模塊功能： 此課程設計實現了基于UDP的客戶/服務器通信程序，需要實現以下一些基本功能： 1.客戶端連接聊天機器人服務器； 2.消息發送：客戶端發送消息給機器人服務器。 3.消息接收：客戶端接收到機器人服務器發送給他的消息。4.可以有多個客戶端同時連接 5.智能回復功能：根據用戶發送的消息內容，稍微有點智能回復。 運行效果： 服務器端和客戶端截圖 三、設計內容 1、UDP傳送數據前并不與對方建立連接，即UDP是無連接的，在傳輸數據前，發送方和接收方相互交換信息使雙方同步。 2、UDP不對收到的數據進行排序，在UDP報文的首部中并沒有關于數據順序的信息（如TCP所采用的序號），而且報文不一定按順序到達的，所以接收端無從排起。 3、UDP對接收到的數據報不發送確認信號，發送端不知道數據是否被正確接收，也不會重發數據。 4、UDP傳送數據較TCP快速，系統開銷也少。 5、由于缺乏擁塞控制（congestion control），需要基于網絡的機制來減小因失控和高速UDP流量負荷而導致的擁塞崩潰效應。換句話說，因為UDP發送者不能夠檢測擁塞，所以像使用包隊列和丟棄技術的路由器這樣的網絡基本設備往往就成為降低UDP過大通信量的有效工具。數據報擁塞控制協議(DCCP)設計成通過在諸如流媒體類型的高速率UDP流中增加主機擁塞控制來減小這個潛在的問題。 從以上UDP協議特點可知，UDP提供的是無連接的、不可靠的數據傳送方式，是一種盡力而為的數據交付服務。 1.服務端 1.2.3.4.5.加載協議棧； 創建套接字； 將套接字綁定到一個本地地址和端口bind； 等待接收數據recvfrom;關閉套接字； 2.客戶端 1.2.3.4.加載協議棧； 創建套接字socket； 向服務器發送數據sendto;關閉套接字； 3.相關代碼顯示：（客戶端） int main(int argc, char* argv[]){ system(“@color 0e”);WORD socketVersion = MAKEWORD(2, 2);WSADATA wsaData;if(WSAStartup(socketVersion, &wsaData)!= 0){ } sockaddr_in sin;sin.sin_family = AF_INET;sin.sin_port = htons(8888);sin.sin_addr.S_un.S_addr = inet_addr(m);int len = sizeof(sin);return 0;以上代碼為相關版本信息及熱啟動的一些操作；; 結構體端口號及相關地址信息以及轉化函數，將輸入的信息轉化為計算機可識別的二進制代碼，進行相關構造 char * sendData = new char[255];cout << “主人:”;cin >> sendData;while(strcmp(sendData, “#”)!= 0){ sendto(sclient, sendData, strlen(sendData), 0,(sockaddr *)&sin, len);char recvData[255];int ret = recvfrom(sclient, recvData, 255, 0,(sockaddr *)&sin, &len);if(ret > 0){ } recvData[ret] = 0x00;cout << “機器人:”;printf(recvData);4.相關代碼展示：（服務端） SOCKET serSocket = socket(AF_INET, SOCK_DGRAM, IPPROTO_UDP);if(serSocket == INVALID_SOCKET){ } printf(“socket error!”);return 0;3 if(bind(serSocket,(sockaddr *)&serAddr, sizeof(serAddr))== SOCKET_ERROR){ } sockaddr_in remoteAddr;int nAddrLen = sizeof(remoteAddr);char * sendData = new char[255];char recvData[255];while(true){ int ret = recvfrom(serSocket, recvData, 255, 0,(sockaddr *)&remoteAddr, //printf(recvData);if(ret > 0){ } struct Ro { char recv[255];char send[255];recvData[ret] = 0x00;printf(“接受到一個連接：%s rn”, inet_ntoa(remoteAddr.sin_addr));cout << “主人:”;printf(recvData);printf(“bind error!”);closesocket(serSocket);return 0;以上為對套接字的綁定及判斷綁定是否成功，以及對于相關信息的初始化 &nAddrLen);}Ro;FILE *fp;fp = fopen(“G:機器人問答機制.txt”, “r”);while(!feof(fp)){ } fscanf(fp, “%s %s”, Ro.recv, Ro.send);if(strcmp(recvData, Ro.recv)== 0){ } else { } strcpy(sendData, Ro.send);break;strcpy(sendData, “對不起，我不知道”);4 fclose(fp);cout << endl;cout << “機器人:” << sendData << endl;sendto(serSocket, sendData, strlen(sendData), 0,(sockaddr *)&remoteAddr, nAddrLen); 四、設計成果以及心得 1．成果 2.心得 通過對課設的相關的操作，加強了對于相關知識的理解，對于知識的應用也得以加強，在課設過程中，聊天機器人制作較為有趣，對于TCP與UDP的通信方式有了進一步的理解和加強，對于socket編程的相關基礎也得以進一步的理解和學習。在今后的學習過程中希望可以將所學知識應用于實際，學以致用。而且對于課設中存在的問題和不足，以及通過老師的講解，對一些算法加以分析和改進，從而不斷完善課設內容，對內容的理解得以加深。 指導老師意見： 成績: 教師簽名： 2017年6月23日 本次課程設計我們小組順利的完成了鍋爐內膽水溫與循環水流量串級控制系統。我們通過討論對過程參數方面的知識有了更加深入的了解。我負責的是傳模擬量采集模塊。 和以前做過的課程設計一樣，經過兩周的課程設計和學習鞏固過程，我充分認識到理論聯系實際能力的重要性。另外還讓我知道設計過程中應自始至終持有嚴謹的科學態度，不能存有一絲的僥幸心理。首先設計中發現自己的理論知識掌握的不牢固。其次就是在設計過程中出現了很多問題，但是自己不會具體情況具體分析。本次工程實踐就是利用THJ-4型過程控制實驗裝置為硬件基礎做鍋爐內膽水溫控制系統實驗分析，采用MCGS組態軟件在上位機實現顯示和控制。通過本次工程實踐，來熟悉工業過程控制的控制流程以及其控制原理。 同學的幫助在為期一周的課設候中有至關重要的作用。因為一個人的能力是有限的。在同學的點滴幫助下不斷的自我完善，從而達到目的。 我覺得作為一名自動化專業的學生，傳感器的課程設計是很有意義的。更重要的是如何把自己平時所學的東西應用到實際中。雖然自己對于這門課懂的并不多，很多基礎的東西都還沒有很好的掌握，覺得很難，也沒有很有效的辦法通過自身去理解，但是靠著這一個禮拜的“學習”，在小組同學的幫助和講解下，漸漸對這門課逐漸產生了些許的興趣，自己開始主動學習并逐步從基礎慢慢開始弄懂它。我認為這個收獲應該說是相當大的。覺得課程設計反映的是一個從理論到實際應用的過程，但是更遠一點可以聯系到以后畢業之后從學校轉到踏上社會的一個過程。小組人員的配合﹑相處，以及自身的動腦和努力，都是以后工作中需要的。第二篇：數據結構課設報告
第三篇：數據結構課設(完整代碼可直接運行)附注釋
第四篇：計算機網絡課設
第五篇：課設小結
點擊咨詢 