计算机网络
实验报告
——路由算法
实验内容
路由算法的实现
实验原理
1.每个结点用从源结点沿已知最佳路径到本结点的距离来标注,标注分为临
时性标注和永久性标注。开始时,所有结点都为临时性标注,标注为无穷大。
2.源结点标注为 0,且为永久性标注,令其为工作结点。
3.检查与工作结点相邻的临时性结点,若该结点到工作结点的距离与工作结
点的标注之和小于该结点的标注,则用新计算得到的和,重新标注该结点。
4.在整个图中查找具有最小值的临时性标注结点,将其变为永久性结点,并
成为下一轮检查的工作结点。
5.重复第 3、4 步,直到目的结点成为工作结点。
实验目的
了解静态路由和动态路由的运行机制;
验证路由算法的功能和性能;
掌握路由算法工作过程。
实验要求
可以使用任何编程工具和编程语言实现
可以编写 Windows 应用程序,也可以编写 DOS 程序
二个路由算法选其中一种,实现算法:
最短路径路由算法(静态路由):可以根据某给定的拓扑结构表和权表,
计算某路由器到各个路由器的最优化路径,存储在该路由器的路由表中
距离矢量路由算法(动态路由):可以根据某给定的拓扑结构表和权表,
实现某路由器能定时更新路由表
源程序
#include "stdio.h"
#include "malloc.h"
#define maxium 32767
#define maxver 9 /*defines the max number of vertexs which the programm can
handle*/
#define OK 1
struct Point
{
char vertex[3];
struct Link *work;
struct Point *next;
};
struct Link
{
char vertex[3];
int value;
struct Link *next;
};
struct Table /*the workbannch of the algorithm*/
{
int cost;
int Known;
char vertex[3];
char path[3];
struct Table *next;
};
int Dijkstra(struct Point *,struct Table *);
int PrintTable(int,struct Table *);
int PrintPath(int,struct Table *,struct Table *);
struct Table * CreateTable(int,int);
struct Point * FindSmallest(struct Table *,struct Point *);/*Find the vertex which has
the smallest value reside in the table*/
int main()
{
int i,j,num,temp,val;
char c;
struct Point *poinpre,*poinhead,*poin;
struct Link *linpre,*linhead,*lin;
struct Table *tabhead;
poinpre=poinhead=poin=(struct Point *)malloc(sizeof(struct Point));
poin->next=NULL;
poin->work=NULL;
restart:
printf("Notice:if you wanna to input a vertex,you must use the format of
number!\n");
printf("Please input the number of points:\n");
scanf("%d",&num);
if(num>maxver||num<1||num%1!=0)
{
printf("\nNumber of points exception!");
goto restart;
}
for(i=0;i<num;i++)
{
printf("Please input the points next to point %d,end with 0:\n",i+1);
poin=(struct Point *)malloc(sizeof(struct Point));
poinpre->next=poin;
poin->vertex[0]='v';
poin->vertex[1]='0'+i+1;
poin->vertex[2]='\0';
linpre=lin=poin->work;
linpre->next=NULL;
for(j=0;j<num-1;j++)
{
printf("The number of the %d th vertex linked to vertex
%d:",j+1,i+1);
scanf("%d",&temp);
if(temp==0)
{
lin->next=NULL;
break;
}
else
{
lin=(struct Link *)malloc(sizeof(struct Link));
linpre->next=lin;