欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

计算机网络__实验__距离矢量路由算法C++实现源代码

程序员文章站 2022-03-25 09:52:25
...

创作日志: 昨天检查完了计网实验,这个代码完全是我自己码的,当时做的时候没在网上找。

目录

一、实验要求

二、使用说明书

三、源代码


一、实验要求

计算机网络__实验__距离矢量路由算法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  (存放边的信息,即两顶点名字和边的权值)

示例输入:

计算机网络__实验__距离矢量路由算法C++实现源代码

计算机网络__实验__距离矢量路由算法C++实现源代码

                    计算机网络__实验__距离矢量路由算法C++实现源代码             计算机网络__实验__距离矢量路由算法C++实现源代码              计算机网络__实验__距离矢量路由算法C++实现源代码

 

运行结果(先po出来 :)  说明可以运行哒 ):

计算机网络__实验__距离矢量路由算法C++实现源代码              计算机网络__实验__距离矢量路由算法C++实现源代码

 

三、源代码

    一共两个文件:一个头文件,一个源文件。


   头文件: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;


}

 

相关标签: 计算机网络

上一篇: Go语言time包

下一篇: go语言--os包