路由表生成程序

《路由表生成程序》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案路由表3.1任务要求3.1.1需求分析给定图的拓扑，每个组有小差别，然后从拓扑输入、任意去掉边、定点， 指定路由器号，生成其路由表并输出。3.1.2要求使用文件保存网络的拓扑结构，数据格式自己定义；使用C语言编写路由表生成程序，程序运行后，根据用户选择去掉的边、定点等，重新生成路由表，输出到屏幕并保存到文件；整个程序由小组分工完成，利用VSourceSafe同步保存各自代码至同一服务器上。3.1.3拓扑图3.2设计思路精彩文档实用标准文案3.2.1路由算法设计主要根据狄克斯拉算法(Dijkastra)来求。此算法的思想是：设置两个顶点的集合S

2、和T，集合S中存放已经找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点，设为V0，然后从集合T中选择到源点V0路径长度最短的顶点u加入到集合S中，集合S中每加入一个新的顶点u，都要修改源点V0到集合T中剩余顶点的当前路径最短路径长度值，集合T中各顶点的新的当前最短路径长度值为原来的当前最短路径长度值与从源点过顶点u到达该顶点的路径长度值中的较小者。此过程不断重复，直到集合中的顶点全部加入到集合S中去为止。3.2.2详细设计利用数据结构图的运用和链表，以及c语言文件的读取。设计了如下图的头文件;AdjMGraph.

3、h,涉及到了对图的节点删除和增加，以及打印的等。还有链表的储存结构，SeqList.h和网路拓扑结构的的文件C:UsersAdministratorDesktop新建文件夹(tuoputu10.txt3.3源代码AdjMGraph.h#include"SeqList.h"//邻接矩阵实现图的存储类型定义typedefstruct{精彩文档实用标准文案SeqListvertices;//存放顶点的顺序表intedge[MaxVertices][MaxVertices];//存放边的邻接矩阵intnumOfEdges;//边的数目}AdjMGraph

4、;//图的结构体定义typedefstruct{introw;//行下标intcol;//列下标intweight;//权值}RowColWeight;//边信息结构体定义//置带权有向图G为空图voidGraphInitiate(AdjMGraph*G){inti,j;for(i=0;iedge[i][j]=0;}else{G->edge[i][j]=MaxWeight;}//MaxWeight表示权值无穷大}G->numOfEdges=0;

5、//边的条数置为0ListInitiate(&G->vertices);//顶点顺序表初始化}//在带权有向图G中插入顶点vertex。如果图中已经有顶点vertex,则图不变，时间复杂度:O(n)。voidInsertVertex(AdjMGraph*G,DataTypevertex){//if(IsVertex(G,vertex)<0)if(ListInsert(&G->vertices,G->vertices.size,vertex)==0)//在顶点顺序表的表尾插入顶点vertex精彩文档实用标准文案{printf("插入顶点时空间已满无法插入！

6、");exit(1);}}/*在带权有向图G中插入一条第v1个顶点指向第v2个顶点，权值为weight的有向边。*如果v1和v2有一个不是图中的顶点，则图不变；如果v1和v2相等，则图不变。*如果图已经包含该边，则边的权值更改为新的权值，时间复杂度:O(1)。上面插入的是有向边，我们插入无向边的时候可以进行两次的有向边的插入。*/voidInsertEdge(AdjMGraph*G,intv1,intv2,intweight){DataTypex;if(v1!=v2){if((ListGet(G->vertices,v1,&x)==0)

7、

8、(ListGe

9、t(G->vertices,v2,&x)==0)){printf("插入边时参数v1和v2越界出错！");exit(1);}G->edge[v1][v2]=weight;G->edge[v2][v1]=weight;G->numOfEdges++;}}//在带权有向图G中删除一条第v1个顶点指向第v2个顶点的边。voidDeleteEdge(AdjMGraph*G,intv1,intv2){G->edge[v1][v2]=MaxWeight;G->edge[v2][v1]=MaxWeight;G->numOfEdges--;}精彩文档实用标准文案//

10、删除顶点//在带权有向图G中删除第v个顶点，时间复杂度:O(n^2)。voidD