路由表生成程序

1、實用標(biāo)準(zhǔn)文案路由表3.1 任務(wù)要求3.1.1 需求分析指定路由器號,給定圖的拓?fù)?，每個組有小差別，然后從拓?fù)漭斎?、任意去掉邊、定點, 生成其路由表并輸出。3.1.2 要求使用文件保存網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，數(shù)據(jù)格式自己定義；使用c語言編寫路由表生成程序，程序運行后，根據(jù)用戶選擇去掉的邊、定點等，重新生成路由表，輸出到屏幕并保存到文件；整個程序由小組分工完成，利用VSource Safe同步保存各自代碼至同一服務(wù)器上。3.1.3 拓?fù)鋱D精彩文檔3.2 設(shè)計思路3.2.1 路由算法設(shè)計主要根據(jù)狄克斯拉算法(Dijkastra)來求。此算法的思想是：設(shè)置兩個頂點的集合 S和T,集 合S中存放已經(jīng)找到最短路徑

2、的頂點，集合 T中存放當(dāng)前還未找到最短路徑的頂點。初始 狀態(tài)時，集合S中只包含源點，設(shè)為 V0,然后從集合T中選擇到源點V0路徑長度最短的 頂點u加入到集合S中，集合S中每加入一個新的頂點u,都要修改源點 V0到集合T中剩余頂點的當(dāng)前路徑最短路徑長度值，集合 T中各頂點的新的當(dāng)前最短路徑長度值為原來的 當(dāng)前最短路徑長度值與從源點過頂點u到達該頂點的路徑長度值中的較小者。此過程不斷重復(fù)，直到集合中的頂點全部加入到集合S中去為止。3.2.2 詳細設(shè)計利用數(shù)據(jù)結(jié)構(gòu)圖的運用和鏈表，以及c語言文件的讀取。設(shè)計了如下圖的頭文件；AdjMGraph.h,涉及到了對圖的節(jié)點刪除和增加，以及打印的等。還有鏈表的

3、儲存結(jié)構(gòu)，SeqList.h和網(wǎng)路拓?fù)浣Y(jié)構(gòu)的的文件新建文件夾(tuoputu10.txt3.3 源代碼AdjMGraph.h#include "SeqList.h"鄰接矩陣實現(xiàn)圖的存儲類型定義typedef structSeqList vertices; 存放頂點的順序表int edgeMaxVerticesMaxV ertices;存放邊的鄰接矩陣 int numOfEdges; 邊的數(shù)目AdjMGraph;/圖的結(jié)構(gòu)體定義typedef structint row; 行下標(biāo)int col;列下標(biāo)int weight; 權(quán)值RowColWeight;/邊信息結(jié)構(gòu)體定義置帶

4、權(quán)有向圖G為空圖void GraphInitiate(AdjMGraph *G) int i,j;for(i=0;i<MaxVertices;i+)for(j=0;j<MaxVertices;j+)if(i=j) G->edgeij=0; else G->edgeij=MaxWeight;/MaxWeight表示權(quán)值無窮大 G->numOfEdges=0; 邊的條數(shù)置為0ListInitiate(&G->vertices);頂點順序表初始化在帶權(quán)有向圖 G中插入頂點vertexo如果圖中已經(jīng)有頂點vertex,則圖不變，時間復(fù)雜度:O(n)。void

5、 InsertVertex(AdjMGraph *G,DataType vertex) /if(IsVertex(G ,vertex)<0)if(ListInsert(&G->vertices,G->vertices.size,vertex)=0)/在頂點順序表的表尾插入頂點 vertexprintf("插入頂點時空間已滿無法插入！")；exit(1);/*在帶權(quán)有向圖G中插入一條第v1個頂點指向第v2個頂點，權(quán)值為 weight的有向邊。* 如果v1和v2有一個不是圖中的頂點，則圖不變；如果 v1和v2相等，則圖不變。* 如果圖已經(jīng)包含該邊，則邊

6、的權(quán)值更改為新的權(quán)值，時間復(fù)雜度 ：0(1)。上面插入的是有向邊，我們插入無向邊的時候可以進行兩次的有向邊的插入。* /void InsertEdge(AdjMGraph *G ,int v1,int v2,int weight) DataType x;if(v1!=v2)if(ListGet(G->vertices,v1,&x)=0)|(ListGet(G->vertices,v2,&x)=0)printf("插入邊時參數(shù) v1和v2越界出錯！ n");exit(1);G->edgev1v2=weight;G->edgev2v1=w

7、eight;G->numOfEdges+;在帶權(quán)有向圖 G中刪除一條第v1個頂點指向第v2個頂點的邊。void DeleteEdge(AdjMGraph *G ,int v1,int v2) G->edgev1v2=MaxWeight;G->edgev2v1=MaxWeight; G->numOfEdges-;刪除頂點在帶權(quán)有向圖G中刪除第v個頂點，時間復(fù)雜度：0(門人2)。 void DeleteVertex(AdjMGraph *G ,int v)int m3,i,j;m3=v-1;if(m3<0|m3>=G->vertices.size) pri

8、ntf("對不起，此鏈路內(nèi)沒有您想要刪除的路由節(jié)點n");exit(0); else/for(i=m3;i<G->vertices.size;i+)for(j=0,i=m3;j<G->vertices.size;j+) G->edgeji=MaxWeight;/for(i=m3;i<G->vertices.size;i+)for(i=m3,j=0;j<G->vertices.size;j+)G->edgeij=MaxWeight;/for(i=m3;i<G->vertices.size;i+)/G-&g

9、t;vertices.listi=G->vertices.listi-1;/G->vertices.size-;/printf("刪除結(jié)點成功n");有沒有向是一樣的。則返回該在帶權(quán)有向圖G中取第v個頂點的第一個鄰接頂點，如果這樣的鄰接頂點存在, 頂點在頂點順序表的序號，否則返回-1.時間復(fù)雜度：O(n)。int GetFirstVex(AdjMGraph G ,int v)int col;DataType x;v=v-1;if(ListGet(G.vertices,v,&x)=0)printf("取第一個鄰接頂點時參數(shù)v越界出錯！ n&quo

10、t;);exit(1);尋找鄰接矩陣v行中從最左開始第一個值非零且非無窮大的權(quán)值對應(yīng)的頂點for(col=0;col<G .vertices.size;col+)if(G.edgevcol>0 && G .edgevcol < MaxWeight) return col;return -1;在帶權(quán)有向圖G中取第v1個頂點的繼鄰接結(jié)點第v2個頂點之后的下一個鄰接結(jié)點，時間復(fù)雜度:O(n)。int GetNextVex(AdjMGraph G,int v1,int v2) int col;DataType x;if(ListGet(G.vertices,v1,&a

11、mp;x)=0)|(ListGet(G .vertices,v2,&x)=0) printf("取下一鄰接頂點時參數(shù)v1和v2越界出錯！ n");exit(1); if(G.edgev1v2=0) printf("v2不是v1的鄰接頂點n"); exit(1);尋找鄰接矩陣v行中從第v2+1列開始的第一個值非零且非無窮大的權(quán)值對應(yīng)的頂點for(col=v2+1;col<G .vertices.size;col+)if(G.edgev1col>0 && G.edgev1col<MaxWeight) return c

12、ol;return -1;/創(chuàng)建有向圖G,通過在空圖 G中插入n個頂點和e條邊實現(xiàn)。時間復(fù)雜度:O(nA2+e) o void CreatGraph(AdjMGraph *G ,DataType v,int n,RowColWeight W,int e)int i,k;Graphlnitiate(G);for(i=0;i<n;i+) cout<<n<<endl;InsertVertex(G,vi); for(k=0;k<e;k+)InsertEdge(G,Wk.row,Wk.col,Wk.weight); /迪克特斯拉算法求得是最短路徑和相應(yīng)的路由器void

13、 Dijkstra(AdjMGraph *G , int v0, int distance口，int path)/*帶權(quán)圖G從下標(biāo)0頂點到其它頂點的最短距離distance*/*和最短路徑上頂點前驅(qū)下標(biāo) path*/int n = G->vertices.size;int *S = (int *)malloc(sizeof(int)*n); /S 數(shù)組int minDis, i, j, u;FILE *fp;/*初始化*/for(i = 0; i < n; i +)distancei = G->edgev0i;Si = 0;if(i != v0 && dist

14、ancei < MaxWeight) pathi = v0;else pathi = -1;Sv0 = 1;u*/*在當(dāng)前還未找到最短路徑的頂點集中選取具有最短距離的頂點for(i = 1; i < n; i +)minDis = MaxWeight;for (j = 0;j < n;j +)if(Sj = 0 && distance0 < minDis) u = j;minDis = distance;/*當(dāng)已不再存在路徑時算法結(jié)束*/if(minDis = MaxWeight) return;Su = 1; /*標(biāo)記頂點u已從集合T加入到集合S中*/

15、*修改從v0到其它頂點的最短距離和最短路徑*/for(j = 0; j < n; j+)if(Sj = 0 && G->edgeuj < MaxWeight && distanceu + G->edgeuj < distance)distance = distanceu + G->edgeuj;pathj = u;printf("目的路由下一跳路由n");fp=fopen("luyoubiao.txt","w");for(i=0;i<n;i+)if (i=v0)

16、 continue;j=i；while(pathj!=v0)j=pathj；if (j=-1) break;printf("%5d%12dn",i+1,j+1);fprintf(fp,"%5d%12dn",i+1,j+1);fclose(fp);SeqList.h typedef structDataType listMaxSize; int size ;SeqList;/初始化順序表/*初始化順序表L*/void ListInitiate(SeqList *L)L->size = 0; /*函數(shù)作用：求當(dāng)前元素個數(shù)*/*返回順序表L的當(dāng)前數(shù)據(jù)元素

17、個數(shù)*/int ListLength(SeqList L) return L.size; /*函數(shù)作用：插入數(shù)據(jù)元素*/int ListInsert(SeqList *L, int i, DataType x)/*在順序表L的第i(0 <= i = size)個位置前插入數(shù)據(jù)元素值x*/*插入成功返回1,插入失敗返回0*/int j;/cout<<i<<"應(yīng)有的數(shù)字"<<endl;if(L->size >= MaxSize) printf("順序表已滿無法插入！n");return 0;else if

18、(i < 0 | i > L->size)printf("參數(shù)i不合法！n");return 0; else/*為插入做準(zhǔn)備*/for(j = L->size; j > i; j-)L->listj = L->listj-1;L->listi = x; /cout<<x<<""cout<<x<<"hao"<<endl;L->size+;元素個數(shù)加1cout<<L->size<<"&q

19、uot;return 1; /*函數(shù)作用：刪除數(shù)據(jù)元素*/int ListDelete(SeqList *L, int i, DataType *x)/*刪除順序表L中位置為i(0 <= i = size-1)的數(shù)據(jù)元素并存放到x中*/*刪除成功返回1,刪除失敗返回0*/int j;if(L->size <= 0) printf（"順序表已空無數(shù)據(jù)元素可刪！n"）;return 0;else if(i < 0 | i > L->size-1 ) printf("參數(shù)i不合法！n"); return 0 ; else*x

20、 = L->listi; /*保存刪除的元素到 x中*/*依次前移*/for(j = i+1; j <= L->size-1; j+)L->listj-1 = L->listj;L->size-;return 1;元素個數(shù)減1/*函數(shù)作用：取數(shù)據(jù)元素*/ int ListGet(SeqList L, int i, DataType *x) /*取順序表L中第i個數(shù)據(jù)元素存于x中，成功返回1,失敗返回0*/ if(i < 0 | i > L.size-1)printf("參數(shù)i不合法！n");return 0; else *x

21、= L.listi;return 1;路由表生成程序.c#include <stdlib.h>#include <malloc.h>#include<windows.h>#include<stdio.h>#include<string.h>#include<conio.h>typedef int DataType;#define MaxSize 10#define MaxVertices 10#define MaxWeight 10000#include "AdjMGraph.h"AdjMGraph g

22、1; int aMaxSize;RowColWeight rcw100;/主函數(shù) void menu()int p;void putList();void Deletevertex();void Deleteedge();void Insertedge();printf(”*網(wǎng)絡(luò)路由生成*n");printf(”*請選擇相應(yīng)實現(xiàn)功能*n");printf(”*1.路由表輸出并打印 *n、;printf(”*2.刪除節(jié)點*n");printf(”*3.刪除邊*n");printf(”*4.填加邊*n");printf(”*5.退出系統(tǒng)*n&quo

23、t;);printf(”*請輸入你白選擇(15) *n)scanf("%d",&p);if(p<1|p>5)printf("nn輸入序號不屬于菜單，請重新輸入 nn");p=6;switch(p)case 1:putList();break;/路由表輸出并打印case 2:Deletevertex();break;刪除節(jié)點case 3:Deleteedge();break;刪除邊case 4:Insertedge();break;case 5:exit(0);break; 退出case 6:menu();void putList()i

24、nt i,j；int distance7,path7;v'n");printf("請輸入你要生成的路由表的起始路由器是第幾個路由器 scanf("%d",&i);i-；Dijkstra(&g1,i,distance,path);printf("從頂點%d到其他各頂點的最短距離為：n",ai);for(j=0;j<g1.vertices.size;j+)printf("到頂點 %d 的最短距離為 %dn",aj,distancej); menu(); void Deletevertex(

25、)int i;printf("請輸入你要刪除的是第幾個頂點vn");scanf("%d",&i);DeleteVertex(&g1,i);menu();void Deleteedge()int i,j;printf("請輸入你要刪除的邊的兩個頂點v1,v2n");scanf("%d%d",&i,&j);DeleteEdge(&g1,i-1,j-1);menu(); void Insertedge()int i,j,w;printf("請輸入你要刪除的邊的兩個頂點和其

26、權(quán)直v1,v2,wn");scanf("%d%d%d",&i,&j,&w);InsertEdge(&g1,i-1,j-1,w);menu();int main()/ AdjMGraph g1;int i,j,k；FILE *fp;讀入文件/ int aMaxSize;/ RowColWeight rcw100;fp=fopen("tuoputu10.txt","r");fscanf(fp,"%d",&i);for(k=0;k<i;k+)fscanf(fp,&q

27、uot;%d",&ak);fscanf(fp,"%d",&j);for(k=0;k<j;k+)fscanf(fp,"%d%d%d",&rcwk.row,&rcwk.col,&rcwk.weight);fclose(fp);GraphInitiate(&g1);CreatGraph(&g1,a,i,rcw,j);menu();3.3.3數(shù)據(jù)文本文件程序的數(shù)據(jù)存儲在文本文件中tuoputu10.txt中，從文件讀入，文本文件如下:71 2 3 4 5 6 7260 1 20 3 60 5

28、 11 0 21 2 21 3 42 1 22 3 12 5 32 6 23 0 63 1 43 2 13 4 13 6 64 3 14 5 34 6 15 0 15 2 35 4 35 6 16 2 26 3 66 4 16 5 1運行程序，路由表以文件的形式輸出，存儲在文件luyoubiao.txt中目的路由 下一跳路由1 22 24 45 46 67 73.4程序運行結(jié)果3.4.1 輸出路由表運行程序，隨機輸入要生成路由表的起點結(jié)點，輸出該點的路由表程序運行，輸入生成路由表結(jié)點序號3,輸出結(jié)點3到各路由器的下一跳路由以及到該路由的距離，并將路由表以文件的形式輸出，保存在文件路由表.txt

29、中。3.4.2 刪除邊刪除圖中邊，刪除節(jié)點 3到結(jié)點4的邊，并再次輸出結(jié)點 3的路由表:M MX MMM XC M M M M X M： M Ji M M M M MHM M NMiMMX MMXMXXXMHMiMHMSi 艮出 系上亢 KM MMM MJOt MX* MMXM MHM iMHM MHM iM 丁 JftXNKKMKXMiMMIHXXXMMiXXKKi青漏;；'、,f爾的；先I 1*5 J MKMSKMMSXXKXMXXMXXXHMXXXXXXXHXNXXXXHXXi.路由表 "MlOOiHCMXMMXMMlH MMXMitMrM2 田 1 p k KM：MJ

30、<M：M!<M!MM：M!MM：XM，MK<3 卅'j力 *請選擇相應(yīng)實現(xiàn)功能mX 射 M M M M M * X M M X M M X M M N M XH M 網(wǎng)由HJtKHKKHKMMHKXiMMSMMMiXMXW：:HHWIM-MSKHMSKHWXItKHI!*2 .刪除MXMHHKMStKXMKMMKMHKMMK-3 .KMXKHXXMNXKKXMKKMXKMXMi 青喻入你的選擇M：苴M MMMJtKX XMXMMX MM1H M； MM M：4 t直力口指力 X注芭隆隆百隆隆隆隆隆隆隆黃睡MMX M M：黃Mi MHM MH «M«

31、WW*MhM：*MbM：w5 .出 系，充MM MM X k MM M* MXMiiMMKJfMiHMMiKHMiKKiMMiNiMMiHM 陀g 合9 MIHTKHMXKBKMMKHMKXMXXMKKHj-eXHji!2 2 7 7 6 712 4 5 6 75到 到請送拄重厘軍理我能M 葡M HMM M： HMMy MMM M M Mi HM *j_ .月今 由 1?。撼?H T 印XKXXKXXH jCXHM>CHX>OCX>OCXX4 力口邊XMKXaiCKjCHKMXXMXHXIOCjOCXXHXMXXX為離巨£垣的 42。4332 點為為為為為對為 頂離離離離離離離 生巨巨巨巨巨巨一巨 他短短短短短短短 普瞽瞽瞽胃瞽瞽甑 的的的的的的 31234567 點點點點點點點點刪除結(jié)點3,4之間的邊，再次輸出結(jié)點 3的路由表，與之前的路由表中到達結(jié)點4的路由發(fā)上改變，距離也相應(yīng)的改變了。3.4.3添加邊添加邊，添加結(jié)點 3到結(jié)點4的邊，權(quán)值設(shè)為2,并再次輸出結(jié)點 3的路由表：MMtJiCMMtJiCH 筑)CJCMtMIHKMiJtMElCHStKM3 1%J3 3a3J*J33*J3J233*J3J*J3。KEEEEKEKEKEKEKKKEgKEK JT上.X IPs «. X X «. X «. X iM