距离向量算法（D-V）
发布时间
阅读量：
阅读量
题目描述
RIP路由协议是一种分布式的基于距离向量的路由选择协议。
距离向量（D-V）算法：
收到相邻路由器（设其地址为 X）的一个 RIP 报文：
① 先修改此 RIP 报文中的所有项目：把“下一跳”字段中的地址都改为 X，并把所有的“距离”字段的值加 1。
② 对修改后的RIP报文中的每一个项目，重复以下步骤：
若原来的路由表中没有目的网络N，则把该项目添加到路由表中；
否则（即在路由表中有目的网络N），若下一跳R路由器地址为X，则把收到的项目替换原路由表中的项目；
否则（即下一跳路由器不是X），若收到的项目中的距离d小于路由表中的距离，则进行更新。否则，什么也不做。
③ 若 3 分钟还没有收到相邻Router的更新信息，则把此相邻Router标记为不可达的路由器，即把距离置为16（距离为16表示不可达）。
④ 返回。
现在假设有一台路由器B，收到邻居路由器C发送过来的RIP路由更新报文。编写程序：使用D-V算法更新路由器B的路由表。
输入描述
输入的第一行为两个正整数M、N（M,N<100），分别表示路由器B的路由表有M行，邻居路由器C发送过来的路由表有N行。
接下来的M+N行，每行包括3个字段：目的网络、距离、下一跳路由器。
前M行为路由器B的路由表，后N行为邻居路由器C发送过来的路由表。
输出描述
输出更新后路由器B的路由表，格式详见样例输出。
输入样例
2 3
N1 3 C
N3 4 E
N1 3 D
N2 4 F
N3 1 -
输出样例
N1 4 C
N2 5 C
N3 2 C
AC代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct point
{
char s[4];
int num;
char ch;
}a[110],b[110];
int n,m;
bool cmp(point x,point y)
{
if(x.s[1]<y.s[1]) return true;
return false;
}
void fun(point x,point y)
{
x.s[0]=y.s[0];
x.s[1]=y.s[1];
x.num=y.num;
x.ch=y.ch;
}
int dengyu(point x,point y)
{
if(x.s[0]==y.s[0] && x.s[1]==y.s[1]) return 1;
return 0;
}
int main()
{
cin>>m>>n;
for(int i=0;i<m;i++)
cin>>a[i].s>>a[i].num>>a[i].ch;
for(int i=0;i<n;i++)
cin>>b[i].s>>b[i].num>>b[i].ch;
for(int i=0;i<n;i++)
{
b[i].ch='C';
b[i].num++;
}
for(int i=0;i<n;i++)
{
int j=-1;
for(int kk=0;kk<m;kk++)
{
if(dengyu(b[i],a[kk])) j=kk;
}
if(j==-1)
{
a[m].s[0]=b[i].s[0];
a[m].s[1]=b[i].s[1];
a[m].num=b[i].num;
a[m].ch=b[i].ch;
m++;
}
else
{
if(a[j].ch==b[i].ch)
{
a[j].s[0]=b[i].s[0];
a[j].s[1]=b[i].s[1];
a[j].num=b[i].num;
a[j].ch=b[i].ch;
}
else
{
if(a[j].num>b[i].num)
{
a[j].s[0]=b[i].s[0];
a[j].s[1]=b[i].s[1];
a[j].num=b[i].num;
a[j].ch=b[i].ch;
}
}
}
}
sort(a,a+m,cmp);
for(int i=0;i<m;i++)
{
cout<<a[i].s<<" "<<a[i].num<<" "<<a[i].ch<<endl;
}
return 0;
}
全部评论 (0)
还没有任何评论哟~