计算机网络__实验__距离矢量路由算法C++实现源代码
创作日志: 昨天检查完了计网实验,这个代码完全是我自己码的,当时做的时候没在网上找。
目录
一、实验要求
1、将上面的网络拓扑图保存待用
例如,可用二维数组保存,数组下标或索引可隐含表示网络节点。数组元素保存网络拓扑图边上的权值。
2、为每个网络节点初始化并保存一张路由表
3、给每个网络节点一次执行距离矢量路由更新的机会,可用一个循环达到此效果
例如,当A执行距离矢量路由更新时,它需要它的邻居B和G的路由表,这里可忽略B和G发送路由表的操作,直接使用即可。
A更新前的路由表不能丢弃,原因有二:一、需要与更新后的路由表比较,看是否有变化;二、在A的邻居节点执行距离矢量路由更新时,它使用的是A的旧表,尽管此方式并非实际所用,但我们要求采用此种方式模拟所有节点同时进行路由更新的效果。
需要记录这一次路由更新过程中,每个节点的路由表是否发生变化。可用一个布尔变量来标记,初始化这个布尔变量为“假”,若出现一个网络节点的路由表发生变化的情况就置为“真”。
4、若布尔变量为“真”,则累加一次更新记录,并重复开始步骤3;若为“假”,则所有节点的路由表稳定了,可以输出一个节点从初始到稳定的所有路由表数据以及更新次数。
二、使用说明书
数据结构: 1. 用来存储网络结点拓扑图的图结构 (class G)
2. 路由表结构(class route_table)
3. 路由表的每一行的表项结构(class route_node)
数据文件:
我是采用读取文件的形式,这样子给老师展示的时候也不用手动输入浪费时间了,并且养成用文件输入的习惯是有必要的。
文件1:vNumber.txt (存放网络结点的总数量)
文件2:vertex.txt (存放所有网络结点的名字,我用的都是ABC这种)
文件3:edge.txt (存放边的信息,即两顶点名字和边的权值)
示例输入:
运行结果(先po出来 :) 说明可以运行哒 ):
三、源代码
一共两个文件:一个头文件,一个源文件。
头文件:Graph.h
#pragma once
using namespace std;
class G {
public:
int vNumber; //顶点数量
char vertex[30]; //最多顶点数量 30
int edge[30][30]; //边集合
public:
G() {
//构造函数,先把所有权值置0
memset(edge,0,sizeof(edge));
}
};
class route_node {
public:
char destination; //目的结点的名字
char exit; //出口结点的名字
int distance; //最短路径长度
};
class route_table {
public:
char route_name;
route_node items[30]; //至多30个表项
};
源文件:距离路由矢量算法.cpp
#include<iostream>
#include<fstream>
#include<assert.h>
#include<string>
#include "Graph.h"
using namespace std;
route_table tables[30]; //路由表 新
route_table temp_tables[30]; //缓存更改前的路由表 旧
void read_file_to_G( G* g ) {
string s;
//创建流对象
ifstream ifs0,ifs1, ifs2;
//打开文件,判断文件是否打开成功
ifs0.open("..\\数据文件\\vNumber2.txt", ios::in);
assert(ifs0.is_open()); //若失败,则输出错误消息,并终止进程
ifs1.open("..\\数据文件\\vertex2.txt", ios::in);
assert(ifs1.is_open());
ifs2.open("..\\数据文件\\edge2.txt", ios::in);
assert(ifs2.is_open());
//顶点数目
while (getline(ifs0, s)) {
g->vNumber = atoi(s.c_str());
}
//顶点文件,按字符读取
while(!ifs1.eof()) {
ifs1 >> g->vertex;
}
//边文件,按行读取,每行为两个顶点值和它们的边的权值
while ( getline(ifs2, s)) {
char v1 = s[0]; //获取第一个顶点
char v2 = s[1]; //获取第二个顶点
g->edge[v1- 65][v2 - 65] = atoi(s.substr(2).c_str()); //后面的就是权值了
g->edge[v2 - 65][v1 - 65] = g->edge[v1 - 65][v2 - 65]; //对称矩阵
//v-65是为了通过ASC码获取相应的下标,A对应65-65也就是0,B对应1,以此类推
}
ifs0.close();
ifs1.close(); //关闭文件输入流
ifs2.close();
}
//初始化路由表的函数
void init_route_table( G* g) {
//遍历每个结点
for (int i = 0; i < g->vNumber; i++) {
tables[i].route_name = g->vertex[i]; //路由表所有者名字
//遍历矩阵的相应行,填写自己的初始路由表
for (int j = 0; j < g->vNumber; j++) {
//如果是临接的
if (g->edge[i][j] != 0) {
//结点 i 的第 j 个表项:
tables[i].items[j].destination = g->vertex[j]; //目的地
tables[i].items[j].exit = g->vertex[j]; //出口和目的地一样
tables[i].items[j].distance = g->edge[i][j]; //开销
}
}
}
}
//拷贝路由表函数
void copy_table(G* g,route_table* oldt,route_table* newt) {
newt->route_name = oldt->route_name;
for (int r = 0; r < g->vNumber; r++) {
newt->items[r].destination = oldt->items[r].destination;
newt->items[r].distance = oldt->items[r].distance;
newt->items[r].exit = oldt->items[r].exit;
}
}
//距离矢量路由算法
void Distance_vector_routing(G* g) {
int count = 0 ; //更新计数
bool is_change; //路由表是否有变化的布尔值
//还没稳定,就进行一轮更新
do {
count++;
is_change = false;
//先把上次的路由表全部保存起来,至temp_tables
for (int c = 0; c < g->vNumber; c++) {
copy_table(g, &tables[c], &temp_tables[c]);
}
//依据temp_tables,依次更新每个结点 m 的路由表,更新后的至tables
for (int m = 0; m < g->vNumber; m++) {
//遍历它的路由表,更新每一个表项 q
for (int q = 0; q < g->vNumber ; q++) {
//分两种情况: 1.不为0,需要比较判断是否更新
// 2.表项的距离是0,说明要进行第一次更新
int curdis = temp_tables[m].items[q].distance; //记录m->q最小距离
if (curdis != 0) {
//遍历与m相邻的结点
for (int u = 0; u < g->vNumber; u++) {
// !0 也就是u->q的路径是已知的
if (g->edge[m][u] != 0 && temp_tables[u].items[q].distance != 0) {
// m->u + u->q 的距离 比 curdis 更小吗?
if (g->edge[m][u] + temp_tables[u].items[q].distance < curdis) {
is_change = true; //修改标记
curdis = g->edge[m][u] + temp_tables[u].items[q].distance;
tables[m].items[q].exit = g->vertex[u]; //出口改成u
tables[m].items[q].distance = curdis; //最短距离修改
}
}
}
}
else {
//遍历与m相邻的结点
for (int u = 0; u < g->vNumber; u++) {
if (g->edge[m][u] != 0 && temp_tables[u].items[q].distance != 0) {
is_change = true; //修改标记
curdis = g->edge[m][u] + temp_tables[u].items[q].distance;
tables[m].items[q].destination = g->vertex[q]; //添加目的结点
tables[m].items[q].exit = g->vertex[u]; //出口改成u
tables[m].items[q].distance = curdis; //最短距离修改
}
}
}
}
}
} while (is_change);
cout << endl<< "更新次数:" << count << endl << endl;
}
//打印路由表函数
void print_route_table(G* g) {
for (int i = 0; i < g->vNumber; i++) {
cout << tables[i].route_name << "的路由表:" << endl << endl;
cout << "目的结点 " << "出口结点 " << "开销" << endl;
for (int j = 0; j < g->vNumber; j++) {
cout << " "<<tables[i].items[j].destination << "\t"
<< " " << tables[i].items[j].exit << "\t"
<< " " << tables[i].items[j].distance << "\t"
<< endl;
}
cout << endl;
}
}
int main() {
G routes; //结点分布图
read_file_to_G(&routes); //读取文件
/* 打印存放网络拓扑图的二维矩阵
char c = 'A';
cout << "\tA\tB\tC\tD\tE\tF\tG\tH\t" << endl << endl;
for (int s = 0; s < routes.vNumber; s++) {
cout << char(c+s) << "\t";
for (int t = 0; t < routes.vNumber; t++) {
cout << routes.edge[s][t] << "\t";
}
cout << endl;
}
*/
init_route_table(&routes); //初始化所有路由表
Distance_vector_routing(&routes); //使用算法
print_route_table(&routes); //打印路由表
return 0;
}