《计算机网络自顶向下》 Miscellaneous Lab2 Implementing an Algorithm（距离向量路由算法）_综合

文章目录

- 前引
- Lab2 距离向量路由算法
- - Lab2 文档查阅（友情提供下载链接）
  - 距离向量路由算法实现思路
  - 修改原框架代码的地方
  - codeblocks c语言项目多个.c文件处理
  - 原框架代码prog.c（已格式优化）
  - 原框架代码node0.c（已优化格式）
  - 原框架代码node1.c（已优化格式）
  - 原框架代码node2.c（已优化格式）
  - 原框架代码node3.c（已优化格式）
  - 最终实现代码
  - - main.c
    - node0.c
    - node1.c
    - node2.c
    - node3.c
  - 最终实现效果

前引

各位好本来对于这个Lab2 我是想和昨天的Wireshark Lab + Socket Lab昨天一天做完的哈哈但最后发现自己还是太理想了我做很多事情都是以理想的状态去做但是基本上在最后总是会发现现实和预期总是会差一些

但还好现在这个Lab的基础任务基本上已经大功告成了 ^^ 我只做了最基础的任务进阶任务我觉得至少要考虑毒性逆转其实实现起来也不是很难就需要用一个数组来记录现在更新过后的数组究竟是哪个位置变了对于变了哪个位置的数我们在表中置于999 之后再重新计算距离

但鉴于人懒 - - 在想着早点结束这个计算机网络课程过段时间可能人超级忙的原因就不再做那个进阶任务了 Forgive me - -

Lab2 距离向量路由算法

Lab2 文档查阅（友情提供下载链接）

方便大家下载相关文档下面是查阅链接
Programming Assignment 6: Implementing an Algorithm
prog3.c
node0.c
node1.c
node2.c
node3.c

下面是大概文档中文翻译截图大家看看就好详细的还是点进去网页链接看吧
在这里插入图片描述

距离向量路由算法实现思路

其实这个算法当然是不难的难的是处理那些特殊情况比如环形黑洞那些 - -
我做这个Lab 其实到最后也只是完成了最基本的路由算法没有做状态更迭的那部分

那这里就写一下实现思路吧剩余的部分相信大家做过第一个Lab对于这些代码阅读起来也不是很难吧qwq（不会有第一个Lab没做的来做第二个Lab的hxd吧- -）
其实这个就是一个动态规划不断地更迭状态的代码下面举个例子就直接放代码了哈

不知道大家学过dijkstra算法没有如果学的话这部分就可以不看了
我们每次向邻居发自己的邻近点的距离
就比如0 挨着1 2 3 0->2 1 0->1 10 0->3 50
我们消息挨个发发到了2这里 2就把自己的点挨个拿出来看
比如2到1之前的距离是80 2想要优化距离就用下面的式子
2->1 = min(2->1,2->0 + 0->1)
2->3 = min(2->3,2->0 + 0->3)

例子就是这个这个相信大家还是可以看的懂的哈那下面直接放代码了

修改原框架代码的地方

1、因为自己调试和我认为一些数据是没有给全的
就比如node3初始化距离的时候都没有数据可以初始于是我就自己按照图中的模仿node1.c加了个connectcosts3[4]

2、jimsrand 修改double mmm = 0x7fff

3、由于使用的是codeblocks 就增加了stdbool.h

4、修改了node1 2 3 4的调试语句 最后全部extern到prog.c中统一输出方便看结果

codeblocks c语言项目多个.c文件处理

由于用的是windows平台我用的是codeblocks 这个还是我提一嘴吧
怕有的hxd不知道怎么弄我直接先开一个项目然后打开所在文件夹
最后再把node 0 1 2 3.c一起放到那个文件夹里面就ok了如下图

在这里插入图片描述

原框架代码prog.c（已格式优化）

#include <stdio.h>#define LINKCHANGES 1
/* ****************************************************************** Programming assignment 3: implementing distributed, asynchronous,distance vector routing.THIS IS THE MAIN ROUTINE. IT SHOULD NOT BE TOUCHED AT ALL BY STUDENTS!**********************************************************************//* a rtpkt is the packet sent from one routing update process toanother via the call tolayer3() */
struct rtpkt
{
    int sourceid;       /* id of sending router sending this pkt */int destid;         /* id of router to which pkt being sent(must be an immediate neighbor) */int mincost[4];    /* min cost to node 0 ... 3 */
};int TRACE = 1;             /* for my debugging */
int YES = 1;
int NO = 0;creatertpkt( initrtpkt, srcid, destid, mincosts)struct rtpkt *initrtpkt;int srcid;int destid;int mincosts[];
{
    int i;initrtpkt->sourceid = srcid;initrtpkt->destid = destid;for (i=0; i<4; i++)initrtpkt->mincost[i] = mincosts[i];
}/***************************************************************** ***************** NETWORK EMULATION CODE STARTS BELOW *********** The code below emulates the layer 2 and below network environment:- emulates the tranmission and delivery (with no loss and nocorruption) between two physically connected nodes- calls the initializations routines rtinit0, etc., once beforebeginning emulationTHERE IS NOT REASON THAT ANY STUDENT SHOULD HAVE TO READ OR UNDERSTAND THE CODE BELOW. YOU SHOLD NOT TOUCH, OR REFERENCE (in your code) ANY OF THE DATA STRUCTURES BELOW. If you're interested in how I designed the emulator, you're welcome to look at the code - but again, you should have to, and you defeinitely should not have to modify ******************************************************************/struct event
{
    float evtime;           /* event time */int evtype;             /* event type code */int eventity;           /* entity where event occurs */struct rtpkt *rtpktptr; /* ptr to packet (if any) assoc w/ this event */struct event *prev;struct event *next;
};
struct event *evlist = NULL;   /* the event list *//* possible events: */
#define FROM_LAYER2 2
#define LINK_CHANGE 10float clocktime = 0.000;main()
{
    struct event *eventptr;init();while (1){
    eventptr = evlist;            /* get next event to simulate */if (eventptr==NULL)goto terminate;evlist = evlist->next;        /* remove this event from event list */if (evlist!=NULL)evlist->prev=NULL;if (TRACE>1){
    printf("MAIN: rcv event, t=%.3f, at %d",eventptr->evtime,eventptr->eventity);if (eventptr->evtype == FROM_LAYER2 ){
    printf(" src:%2d,",eventptr->rtpktptr->sourceid);printf(" dest:%2d,",eventptr->rtpktptr->destid);printf(" contents: %3d %3d %3d %3d\n",eventptr->rtpktptr->mincost[0], eventptr->rtpktptr->mincost[1],eventptr->rtpktptr->mincost[2], eventptr->rtpktptr->mincost[3]);}}clocktime = eventptr->evtime;    /* update time to next event time */if(eventptr->evtype == FROM_LAYER2 ){
    if(eventptr->eventity == 0)rtupdate0(eventptr->rtpktptr);else if (eventptr->eventity == 1)rtupdate1(eventptr->rtpktptr);else if (eventptr->eventity == 2)rtupdate2(eventptr->rtpktptr);else if (eventptr->eventity == 3)rtupdate3(eventptr->rtpktptr);else{
    printf("Panic: unknown event entity\n");exit(0);}}else if (eventptr->evtype == LINK_CHANGE ){
    if (clocktime<10001.0){
    linkhandler0(1,20);linkhandler1(0,20);}else{
    linkhandler0(1,1);linkhandler1(0,1);}}else{
    printf("Panic: unknown event type\n");exit(0);}if(eventptr->evtype == FROM_LAYER2 )free(eventptr->rtpktptr);        /* free memory for packet, if any */free(eventptr);                    /* free memory for event struct */}terminate:printf("\nSimulator terminated at t=%f, no packets in medium\n", clocktime);
}init()                         /* initialize the simulator */
{
    int i;float sum, avg;float jimsrand();struct event *evptr;printf("Enter TRACE:");scanf("%d",&TRACE);srand(9999);              /* init random number generator */sum = 0.0;                /* test random number generator for students */for (i=0; i<1000; i++)sum=sum+jimsrand();    /* jimsrand() should be uniform in [0,1] */avg = sum/1000.0;if(avg < 0.25 || avg > 0.75){
    printf("It is likely that random number generation on your machine\n" );printf("is different from what this emulator expects. Please take\n");printf("a look at the routine jimsrand() in the emulator code. Sorry. \n");exit(0);}clocktime=0.0;                /* initialize time to 0.0 */rtinit0();rtinit1();rtinit2();rtinit3();/* initialize future link changes */if (LINKCHANGES==1){
    evptr = (struct event *)malloc(sizeof(struct event));evptr->evtime =  10000.0;evptr->evtype =  LINK_CHANGE;evptr->eventity =  -1;evptr->rtpktptr =  NULL;insertevent(evptr);evptr = (struct event *)malloc(sizeof(struct event));evptr->evtype =  LINK_CHANGE;evptr->evtime =  20000.0;evptr->rtpktptr =  NULL;insertevent(evptr);}
}/****************************************************************************/
/* jimsrand(): return a float in range [0,1]. The routine below is used to */
/* isolate all random number generation in one location. We assume that the*/
/* system-supplied rand() function return an int in therange [0,mmm] */
/****************************************************************************/float jimsrand()
{
    double mmm = 0x7fff;   /* largest int - MACHINE DEPENDENT!!!!!!!! */float x;                   /* individual students may need to change mmm */x = rand()/mmm;            /* x should be uniform in [0,1] */return(x);
}/********************* EVENT HANDLINE ROUTINES *******/
/* The next set of routines handle the event list */
/*****************************************************/insertevent(p)struct event *p;
{
    struct event *q,*qold;if (TRACE>3){
    printf(" INSERTEVENT: time is %lf\n",clocktime);printf(" INSERTEVENT: future time will be %lf\n",p->evtime);}q = evlist;     /* q points to header of list in which p struct inserted */if (q==NULL){
       /* list is empty */evlist=p;p->next=NULL;p->prev=NULL;}else{
    for (qold = q; q !=NULL && p->evtime > q->evtime; q=q->next)qold=q;if (q==NULL)    /* end of list */{
    qold->next = p;p->prev = qold;p->next = NULL;}else if (q==evlist) /* front of list */{
    p->next=evlist;p->prev=NULL;p->next->prev=p;evlist = p;}else    /* middle of list */{
    p->next=q;p->prev=q->prev;q->prev->next=p;q->prev=p;}}
}printevlist()
{
    struct event *q;printf("--------------\nEvent List Follows:\n");for(q = evlist; q!=NULL; q=q->next)printf("Event time: %f, type: %d entity: %d\n",q->evtime,q->evtype,q->eventity);printf("--------------\n");
}/************************** TOLAYER2 ***************/
tolayer2(packet)struct rtpkt packet;
{
    struct rtpkt *mypktptr;struct event *evptr, *q;float jimsrand(),lastime;int i;int connectcosts[4][4];/* initialize by hand since not all compilers allow array initilization */connectcosts[0][0]=0;  connectcosts[0][1]=1;  connectcosts[0][2]=3;connectcosts[0][3]=7;connectcosts[1][0]=1;  connectcosts[1][1]=0;  connectcosts[1][2]=1;connectcosts[1][3]=999;connectcosts[2][0]=3;  connectcosts[2][1]=1;  connectcosts[2][2]=0;connectcosts[2][3]=2;connectcosts[3][0]=7;  connectcosts[3][1]=999;  connectcosts[3][2]=2;connectcosts[3][3]=0;/* be nice: check if source and destination id's are reasonable */if (packet.sourceid<0 || packet.sourceid >3){
    printf("WARNING: illegal source id in your packet, ignoring packet!\n");return;}if (packet.destid<0 || packet.destid >3){
    printf("WARNING: illegal dest id in your packet, ignoring packet!\n");return;}if (packet.sourceid == packet.destid){
    printf("WARNING: source and destination id's the same, ignoring packet!\n");return;}if (connectcosts[packet.sourceid][packet.destid] == 999){
    printf("WARNING: source and destination not connected, ignoring packet!\n");return;}/* make a copy of the packet student just gave me since he/she may decide *//* to do something with the packet after we return back to him/her */mypktptr = (struct rtpkt *) malloc(sizeof(struct rtpkt));mypktptr->sourceid = packet.sourceid;mypktptr->destid = packet.destid;for (i=0; i<4; i++)mypktptr->mincost[i] = packet.mincost[i];if (TRACE>2){
    printf(" TOLAYER2: source: %d, dest: %d\n costs:",mypktptr->sourceid, mypktptr->destid);for (i=0; i<4; i++)printf("%d ",mypktptr->mincost[i]);printf("\n");}/* create future event for arrival of packet at the other side */evptr = (struct event *)malloc(sizeof(struct event));evptr->evtype =  FROM_LAYER2;   /* packet will pop out from layer3 */evptr->eventity = packet.destid; /* event occurs at other entity */evptr->rtpktptr = mypktptr;       /* save ptr to my copy of packet *//* finally, compute the arrival time of packet at the other end.medium can not reorder, so make sure packet arrives between 1 and 10time units after the latest arrival time of packetscurrently in the medium on their way to the destination */lastime = clocktime;for (q=evlist; q!=NULL ; q = q->next){
    if ( (q->evtype==FROM_LAYER2  && q->eventity==evptr->eventity) )lastime = q->evtime;}evptr->evtime =  lastime + 2.*jimsrand();if (TRACE>2)printf(" TOLAYER2: scheduling arrival on other side\n");insertevent(evptr);
}

原框架代码node0.c（已优化格式）

#include <stdio.h>extern struct rtpkt {
    int sourceid;       /* id of sending router sending this pkt */int destid;         /* id of router to which pkt being sent(must be an immediate neighbor) */int mincost[4];    /* min cost to node 0 ... 3 */};extern int TRACE;
extern int YES;
extern int NO;struct distance_table
{
    int costs[4][4];
} dt0;/* students to write the following two routines, and maybe some others */void rtinit0()
{
    }void rtupdate0(rcvdpkt)struct rtpkt *rcvdpkt;
{
    }printdt0(dtptr)struct distance_table *dtptr;
{
    printf(" via \n");printf(" D0 | 1 2 3 \n");printf(" ----|-----------------\n");printf(" 1| %3d %3d %3d\n",dtptr->costs[1][1],dtptr->costs[1][2],dtptr->costs[1][3]);printf("dest 2| %3d %3d %3d\n",dtptr->costs[2][1],dtptr->costs[2][2],dtptr->costs[2][3]);printf(" 3| %3d %3d %3d\n",dtptr->costs[3][1],dtptr->costs[3][2],dtptr->costs[3][3]);
}linkhandler0(linkid, newcost)int linkid, newcost;
/* called when cost from 0 to linkid changes from current value to newcost*/
/* You can leave this routine empty if you're an undergrad. If you want */
/* to use this routine, you'll need to change the value of the LINKCHANGE */
/* constant definition in prog3.c from 0 to 1 */
{
    }

原框架代码node1.c（已优化格式）

#include <stdio.h>
extern struct rtpkt 
{
    int sourceid;       /* id of sending router sending this pkt */int destid;         /* id of router to which pkt being sent(must be an immediate neighbor) */int mincost[4];    /* min cost to node 0 ... 3 */
};extern int TRACE;
extern int YES;
extern int NO;int connectcosts1[4] = {
     1,  0,  1, 999 };struct distance_table
{
    int costs[4][4];
}dt1;/* students to write the following two routines, and maybe some others */rtinit1()
{
    }rtupdate1(rcvdpkt)struct rtpkt *rcvdpkt;
{
    }printdt1(dtptr)struct distance_table *dtptr;{
    printf(" via \n");printf(" D1 | 0 2 \n");printf(" ----|-----------\n");printf(" 0| %3d %3d\n",dtptr->costs[0][0], dtptr->costs[0][2]);printf("dest 2| %3d %3d\n",dtptr->costs[2][0], dtptr->costs[2][2]);printf(" 3| %3d %3d\n",dtptr->costs[3][0], dtptr->costs[3][2]);
}linkhandler1(linkid, newcost)int linkid, newcost;
/* called when cost from 1 to linkid changes from current value to newcost*/
/* You can leave this routine empty if you're an undergrad. If you want */
/* to use this routine, you'll need to change the value of the LINKCHANGE */
/* constant definition in prog3.c from 0 to 1 */
{
    }

原框架代码node2.c（已优化格式）

#include <stdio.h>extern struct rtpkt
{
    int sourceid;       /* id of sending router sending this pkt */int destid;         /* id of router to which pkt being sent(must be an immediate neighbor) */int mincost[4];    /* min cost to node 0 ... 3 */
};extern int TRACE;
extern int YES;
extern int NO;struct distance_table
{
    int costs[4][4];
} dt2;/* students to write the following two routines, and maybe some others */void rtinit2()
{
    
}void rtupdate2(rcvdpkt)struct rtpkt *rcvdpkt;{
    }printdt2(dtptr)struct distance_table *dtptr;{
    printf(" via \n");printf(" D2 | 0 1 3 \n");printf(" ----|-----------------\n");printf(" 0| %3d %3d %3d\n",dtptr->costs[0][0],dtptr->costs[0][1],dtptr->costs[0][3]);printf("dest 1| %3d %3d %3d\n",dtptr->costs[1][0],dtptr->costs[1][1],dtptr->costs[1][3]);printf(" 3| %3d %3d %3d\n",dtptr->costs[3][0],dtptr->costs[3][1],dtptr->costs[3][3]);
}

原框架代码node3.c（已优化格式）

#include <stdio.h>extern struct rtpkt
{
    int sourceid;       /* id of sending router sending this pkt */int destid;         /* id of router to which pkt being sent(must be an immediate neighbor) */int mincost[4];    /* min cost to node 0 ... 3 */
};extern int TRACE;
extern int YES;
extern int NO;struct distance_table
{
    int costs[4][4];
} dt2;/* students to write the following two routines, and maybe some others */void rtinit2()
{
    
}void rtupdate2(rcvdpkt)struct rtpkt *rcvdpkt;{
    }printdt2(dtptr)struct distance_table *dtptr;{
    printf(" via \n");printf(" D2 | 0 1 3 \n");printf(" ----|-----------------\n");printf(" 0| %3d %3d %3d\n",dtptr->costs[0][0],dtptr->costs[0][1],dtptr->costs[0][3]);printf("dest 1| %3d %3d %3d\n",dtptr->costs[1][0],dtptr->costs[1][1],dtptr->costs[1][3]);printf(" 3| %3d %3d %3d\n",dtptr->costs[3][0],dtptr->costs[3][1],dtptr->costs[3][3]);
}

最终实现代码

main.c

#include <stdio.h>
#include <stdbool.h>#define LINKCHANGES 1
/* ****************************************************************** Programming assignment 3: implementing distributed, asynchronous,distance vector routing.THIS IS THE MAIN ROUTINE. IT SHOULD NOT BE TOUCHED AT ALL BY STUDENTS!**********************************************************************//* a rtpkt is the packet sent from one routing update process toanother via the call tolayer3() */
struct rtpkt
{
    int sourceid;       /* id of sending router sending this pkt */int destid;         /* id of router to which pkt being sent(must be an immediate neighbor) */int mincost[4];    /* min cost to node 0 ... 3 */
};int TRACE = 1;             /* for my debugging */
int YES = 1;
int NO = 0;extern printdt0(dtptr);
extern printdt1(dtptr);
extern printdt2(dtptr);
extern printdt3(dtptr);
extern struct distance_table dt0;
extern struct distance_table dt1;
extern struct distance_table dt2;
extern struct distance_table dt3;creatertpkt( initrtpkt, srcid, destid, mincosts)struct rtpkt *initrtpkt;int srcid;int destid;int mincosts[];
{
    int i;initrtpkt->sourceid = srcid;initrtpkt->destid = destid;for (i=0; i<4; i++)initrtpkt->mincost[i] = mincosts[i];
}/***************************************************************** ***************** NETWORK EMULATION CODE STARTS BELOW *********** The code below emulates the layer 2 and below network environment:- emulates the tranmission and delivery (with no loss and nocorruption) between two physically connected nodes- calls the initializations routines rtinit0, etc., once beforebeginning emulationTHERE IS NOT REASON THAT ANY STUDENT SHOULD HAVE TO READ OR UNDERSTAND THE CODE BELOW. YOU SHOLD NOT TOUCH, OR REFERENCE (in your code) ANY OF THE DATA STRUCTURES BELOW. If you're interested in how I designed the emulator, you're welcome to look at the code - but again, you should have to, and you defeinitely should not have to modify ******************************************************************/struct event
{
    float evtime;           /* event time */int evtype;             /* event type code */int eventity;           /* entity where event occurs */struct rtpkt *rtpktptr; /* ptr to packet (if any) assoc w/ this event */struct event *prev;struct event *next;
};
struct event *evlist = NULL;   /* the event list *//* possible events: */
#define FROM_LAYER2 2
#define LINK_CHANGE 10float clocktime = 0.000;main()
{
    struct event *eventptr;init();while (1){
    eventptr = evlist;            /* get next event to simulate */if (eventptr==NULL)goto terminate;evlist = evlist->next;        /* remove this event from event list */if (evlist!=NULL)evlist->prev=NULL;if (TRACE>1){
    printf("MAIN: rcv event, t=%.3f, at %d",eventptr->evtime,eventptr->eventity);if (eventptr->evtype == FROM_LAYER2 ){
    printf(" src:%2d,",eventptr->rtpktptr->sourceid);printf(" dest:%2d,",eventptr->rtpktptr->destid);printf(" contents: %3d %3d %3d %3d\n",eventptr->rtpktptr->mincost[0], eventptr->rtpktptr->mincost[1],eventptr->rtpktptr->mincost[2], eventptr->rtpktptr->mincost[3]);}}clocktime = eventptr->evtime;    /* update time to next event time */if(eventptr->evtype == FROM_LAYER2 ){
    if(eventptr->eventity == 0)rtupdate0(eventptr->rtpktptr);else if (eventptr->eventity == 1)rtupdate1(eventptr->rtpktptr);else if (eventptr->eventity == 2)rtupdate2(eventptr->rtpktptr);else if (eventptr->eventity == 3)rtupdate3(eventptr->rtpktptr);else{
    printf("Panic: unknown event entity\n");exit(0);}}else if (eventptr->evtype == LINK_CHANGE ){
    if (clocktime<10001.0){
    linkhandler0(1,20);linkhandler1(0,20);}else{
    linkhandler0(1,1);linkhandler1(0,1);}}else{
    printf("Panic: unknown event type\n");exit(0);}if(eventptr->evtype == FROM_LAYER2 )free(eventptr->rtpktptr);        /* free memory for packet, if any */free(eventptr);                    /* free memory for event struct */}terminate:printdt0(&dt0);printf("\n");printdt1(&dt1);printf("\n");printdt2(&dt2);printf("\n");printdt3(&dt3);printf("\n");printf("\nSimulator terminated at t=%f, no packets in medium\n", clocktime);
}init()                         /* initialize the simulator */
{
    int i;float sum, avg;float jimsrand();struct event *evptr;printf("Enter TRACE:");scanf("%d",&TRACE);srand(9999);              /* init random number generator */sum = 0.0;                /* test random number generator for students */for (i=0; i<1000; i++)sum=sum+jimsrand();    /* jimsrand() should be uniform in [0,1] */avg = sum/1000.0;if(avg < 0.25 || avg > 0.75){
    printf("It is likely that random number generation on your machine\n" );printf("is different from what this emulator expects. Please take\n");printf("a look at the routine jimsrand() in the emulator code. Sorry. \n");exit(0);}clocktime=0.0;                /* initialize time to 0.0 */rtinit0();rtinit1();rtinit2();rtinit3();/* initialize future link changes */if (LINKCHANGES==1){
    evptr = (struct event *)malloc(sizeof(struct event));evptr->evtime =  10000.0;evptr->evtype =  LINK_CHANGE;evptr->eventity =  -1;evptr->rtpktptr =  NULL;insertevent(evptr);evptr = (struct event *)malloc(sizeof(struct event));evptr->evtype =  LINK_CHANGE;evptr->evtime =  20000.0;evptr->rtpktptr =  NULL;insertevent(evptr);}
}/****************************************************************************/
/* jimsrand(): return a float in range [0,1]. The routine below is used to */
/* isolate all random number generation in one location. We assume that the*/
/* system-supplied rand() function return an int in therange [0,mmm] */
/****************************************************************************/float jimsrand()
{
    double mmm = 0x7fff;   /* largest int - MACHINE DEPENDENT!!!!!!!! */float x;                   /* individual students may need to change mmm */x = rand()/mmm;            /* x should be uniform in [0,1] */return(x);
}/********************* EVENT HANDLINE ROUTINES *******/
/* The next set of routines handle the event list */
/*****************************************************/insertevent(p)struct event *p;
{
    struct event *q,*qold;if (TRACE>3){
    printf(" INSERTEVENT: time is %lf\n",clocktime);printf(" INSERTEVENT: future time will be %lf\n",p->evtime);}q = evlist;     /* q points to header of list in which p struct inserted */if (q==NULL){
       /* list is empty */evlist=p;p->next=NULL;p->prev=NULL;}else{
    for (qold = q; q !=NULL && p->evtime > q->evtime; q=q->next)qold=q;if (q==NULL)    /* end of list */{
    qold->next = p;p->prev = qold;p->next = NULL;}else if (q==evlist) /* front of list */{
    p->next=evlist;p->prev=NULL;p->next->prev=p;evlist = p;}else    /* middle of list */{
    p->next=q;p->prev=q->prev;q->prev->next=p;q->prev=p;}}
}printevlist()
{
    struct event *q;printf("--------------\nEvent List Follows:\n");for(q = evlist; q!=NULL; q=q->next)printf("Event time: %f, type: %d entity: %d\n",q->evtime,q->evtype,q->eventity);printf("--------------\n");
}/************************** TOLAYER2 ***************/
tolayer2(packet)struct rtpkt packet;
{
    struct rtpkt *mypktptr;struct event *evptr, *q;float jimsrand(),lastime;int i;int connectcosts[4][4];/* initialize by hand since not all compilers allow array initilization */connectcosts[0][0]=0;  connectcosts[0][1]=1;  connectcosts[0][2]=3;connectcosts[0][3]=7;connectcosts[1][0]=1;  connectcosts[1][1]=0;  connectcosts[1][2]=1;connectcosts[1][3]=999;connectcosts[2][0]=3;  connectcosts[2][1]=1;  connectcosts[2][2]=0;connectcosts[2][3]=2;connectcosts[3][0]=7;  connectcosts[3][1]=999;  connectcosts[3][2]=2;connectcosts[3][3]=0;/* be nice: check if source and destination id's are reasonable */if (packet.sourceid<0 || packet.sourceid >3){
    printf("WARNING: illegal source id in your packet, ignoring packet!\n");return;}if (packet.destid<0 || packet.destid >3){
    printf("WARNING: illegal dest id in your packet, ignoring packet!\n");return;}if (packet.sourceid == packet.destid){
    printf("WARNING: source and destination id's the same, ignoring packet!\n");return;}if (connectcosts[packet.sourceid][packet.destid] == 999){
    printf("WARNING: source and destination not connected, ignoring packet!\n");return;}/* make a copy of the packet student just gave me since he/she may decide *//* to do something with the packet after we return back to him/her */mypktptr = (struct rtpkt *) malloc(sizeof(struct rtpkt));mypktptr->sourceid = packet.sourceid;mypktptr->destid = packet.destid;for (i=0; i<4; i++)mypktptr->mincost[i] = packet.mincost[i];if (TRACE>2){
    printf(" TOLAYER2: source: %d, dest: %d\n costs:",mypktptr->sourceid, mypktptr->destid);for (i=0; i<4; i++)printf("%d ",mypktptr->mincost[i]);printf("\n");}/* create future event for arrival of packet at the other side */evptr = (struct event *)malloc(sizeof(struct event));evptr->evtype =  FROM_LAYER2;   /* packet will pop out from layer3 */evptr->eventity = packet.destid; /* event occurs at other entity */evptr->rtpktptr = mypktptr;       /* save ptr to my copy of packet *//* finally, compute the arrival time of packet at the other end.medium can not reorder, so make sure packet arrives between 1 and 10time units after the latest arrival time of packetscurrently in the medium on their way to the destination */lastime = clocktime;for (q=evlist; q!=NULL ; q = q->next){
    if ( (q->evtype==FROM_LAYER2  && q->eventity==evptr->eventity) )lastime = q->evtime;}evptr->evtime =  lastime + 2.*jimsrand();if (TRACE>2)printf(" TOLAYER2: scheduling arrival on other side\n");insertevent(evptr);
}

node0.c

#include <stdio.h>
#include <stdbool.h>extern struct rtpkt {
    int sourceid;       /* id of sending router sending this pkt */int destid;         /* id of router to which pkt being sent(must be an immediate neighbor) */int mincost[4];    /* min cost to node 0 ... 3 */};extern int TRACE;
extern int YES;
extern int NO;int connectcosts0[4] = {
     0,  1,  3,  7};struct distance_table
{
    int costs[4][4];
} dt0;/* students to write the following two routines, and maybe some others */void rtinit0()
{
    int i,j;struct rtpkt packet;for(i=0;i<4;++i){
    for(j=0;j<4;++j){
    if(i == j)  dt0.costs[i][j] == 0;else    dt0.costs[i][j] = 999;}}for(i=0;i<4;++i)dt0.costs[0][i] = dt0.costs[i][0] = packet.mincost[i] = connectcosts0[i];packet.sourceid = 0;for(i=0;i<4;++i){
    packet.destid = i;if(connectcosts0[i] != 999 && i != 0) tolayer2(packet);}
}void rtupdate0(rcvdpkt)struct rtpkt *rcvdpkt;
{
    bool flag = false;int source = rcvdpkt->sourceid,i;if(source < 0 || source >= 4)   return;for(i=0;i<4;++i)dt0.costs[source][i] = rcvdpkt->mincost[i];for(i=0;i<4;++i){
    if(dt0.costs[0][i] > dt0.costs[0][source] + dt0.costs[source][i]){
    flag = true;dt0.costs[0][i] = dt0.costs[0][source] + dt0.costs[source][i];}}if(flag){
    struct rtpkt packet;packet.sourceid = 0;for(i=0;i<4;++i)packet.mincost[i] = dt0.costs[0][i];for(i=0;i<4;++i){
    packet.destid = i;if(dt0.costs[0][i] != 999 && i != 0) tolayer2(packet);}}
}printdt0(dtptr)struct distance_table *dtptr;
{
    printf(" via \n");printf(" D0 | 0 1 2 3 \n");printf(" ----|-----------------\n");printf(" 0| %3d %3d %3d %3d\n",dtptr->costs[0][0],dtptr->costs[0][1],dtptr->costs[0][2],dtptr->costs[0][3]);
}linkhandler0(linkid, newcost)int linkid, newcost;
/* called when cost from 0 to linkid changes from current value to newcost*/
/* You can leave this routine empty if you're an undergrad. If you want */
/* to use this routine, you'll need to change the value of the LINKCHANGE */
/* constant definition in prog3.c from 0 to 1 */
{
    }

node1.c

#include <stdio.h>
#include <stdbool.h>extern struct rtpkt {
    int sourceid;       /* id of sending router sending this pkt */int destid;         /* id of router to which pkt being sent(must be an immediate neighbor) */int mincost[4];    /* min cost to node 0 ... 3 */};extern int TRACE;
extern int YES;
extern int NO;int connectcosts1[4] = {
     1,  0,  1, 999 };struct distance_table
{
    int costs[4][4];
}dt1;/* students to write the following two routines, and maybe some others */rtinit1()
{
    int i,j;struct rtpkt packet;packet.sourceid = 1;for(i=0;i<4;++i){
    for(j=0;j<4;++j){
    if(i == j)  dt1.costs[i][j] == 0;else    dt1.costs[i][j] = 999;}}for(i=0;i<4;++i)dt1.costs[1][i] = dt1.costs[i][1] = packet.mincost[i] = connectcosts1[i];for(i=0;i<4;++i){
    packet.destid = i;if(connectcosts1[i] != 999 && i != 1) tolayer2(packet);}
}rtupdate1(rcvdpkt)struct rtpkt *rcvdpkt;
{
    bool flag = false;int source = rcvdpkt->sourceid,i;if(source < 0 || source >= 4)   return;for(i=0;i<4;++i)dt1.costs[source][i] = rcvdpkt->mincost[i];for(i=0;i<4;++i){
    if(dt1.costs[1][i] > dt1.costs[1][source] + dt1.costs[source][i]){
    flag = true;dt1.costs[1][i] = dt1.costs[1][source] + dt1.costs[source][i];}}struct rtpkt packet;if(flag){
    packet.sourceid = 1;for(i=0;i<4;++i)packet.mincost[i] = dt1.costs[1][i];for(i=0;i<4;++i){
    packet.destid = i;if(dt1.costs[1][i] != 999 && i != 1) tolayer2(packet);}}
}printdt1(dtptr)struct distance_table *dtptr;{
    printf(" via \n");printf(" D1 | 0 1 2 3 \n");printf(" ----|-----------------\n");printf(" 1| %3d %3d %3d %3d\n",dtptr->costs[1][0],dtptr->costs[1][1],dtptr->costs[1][2],dtptr->costs[1][3]);
}linkhandler1(linkid, newcost)int linkid, newcost;
/* called when cost from 1 to linkid changes from current value to newcost*/
/* You can leave this routine empty if you're an undergrad. If you want */
/* to use this routine, you'll need to change the value of the LINKCHANGE */
/* constant definition in prog3.c from 0 to 1 */
{
    }

node2.c

#include <stdio.h>
#include <stdbool.h>extern struct rtpkt
{
    int sourceid;       /* id of sending router sending this pkt */int destid;         /* id of router to which pkt being sent(must be an immediate neighbor) */int mincost[4];    /* min cost to node 0 ... 3 */
};extern int TRACE;
extern int YES;
extern int NO;int connectcosts2[4] = {
     3,  1,  0, 2};struct distance_table
{
    int costs[4][4];
} dt2;/* students to write the following two routines, and maybe some others */void rtinit2()
{
    int i,j;struct rtpkt packet;packet.sourceid = 2;for(i=0;i<4;++i){
    for(j=0;j<4;++j){
    if(i == j)  dt2.costs[i][j] == 0;else    dt2.costs[i][j] = 999;}}for(i=0;i<4;++i)dt2.costs[2][i] = dt2.costs[i][2] = packet.mincost[i] = connectcosts2[i];for(i=0;i<4;++i){
    packet.destid = i;if(connectcosts2[i] != 999 && i != 2) tolayer2(packet);}
}void rtupdate2(rcvdpkt)struct rtpkt *rcvdpkt;
{
    bool flag = false;int source = rcvdpkt->sourceid,i;if(source < 0 || source >= 4)   return;for(i=0;i<4;++i)dt2.costs[source][i] = rcvdpkt->mincost[i];for(i=0;i<4;++i){
    if(dt2.costs[2][i] > dt2.costs[2][source] + dt2.costs[source][i]){
    flag = true;dt2.costs[2][i] = dt2.costs[2][source] + dt2.costs[source][i];}}if(flag){
    struct rtpkt packet;packet.sourceid = 2;for(i=0;i<4;++i)packet.mincost[i] = dt2.costs[2][i];for(i=0;i<4;++i){
    packet.destid = i;if(dt2.costs[2][i] != 999 && i != 2) tolayer2(packet);}}
}printdt2(dtptr)struct distance_table *dtptr;{
    printf(" via \n");printf(" D2 | 0 1 2 3 \n");printf(" ----|-----------------\n");printf(" 2| %3d %3d %3d %3d\n",dtptr->costs[2][0],dtptr->costs[2][1],dtptr->costs[2][2],dtptr->costs[2][3]);
}

node3.c

#include <stdio.h>
#include <stdbool.h>extern struct rtpkt
{
    int sourceid;       /* id of sending router sending this pkt */int destid;         /* id of router to which pkt being sent(must be an immediate neighbor) */int mincost[4];    /* min cost to node 0 ... 3 */
};extern int TRACE;
extern int YES;
extern int NO;int connectcosts3[4] = {
     7,  999,  2, 0};struct distance_table
{
    int costs[4][4];
} dt3;/* students to write the following two routines, and maybe some others */void rtinit3()
{
    int i,j;struct rtpkt packet;packet.sourceid = 3;for(i=0;i<4;++i){
    for(j=0;j<4;++j){
    if(i == j)  dt3.costs[i][j] == 0;else    dt3.costs[i][j] = 999;}}for(i=0;i<4;++i)dt3.costs[3][i] = dt3.costs[i][3] = packet.mincost[i] = connectcosts3[i];for(i=0;i<4;++i){
    packet.destid = i;if(connectcosts3[i] != 999 && i != 3) tolayer2(packet);}
}void rtupdate3(rcvdpkt)struct rtpkt *rcvdpkt;
{
    bool flag = false;int source = rcvdpkt->sourceid,i;if(source < 0 || source >= 4)   return;for(i=0;i<4;++i)dt3.costs[source][i] = rcvdpkt->mincost[i];for(i=0;i<4;++i){
    if(dt3.costs[3][i] > dt3.costs[3][source] + dt3.costs[source][i]){
    flag = true;dt3.costs[3][i] = dt3.costs[3][source] + dt3.costs[source][i];}}if(flag){
    struct rtpkt packet;packet.sourceid = 3;for(i=0;i<4;++i)packet.mincost[i] = dt3.costs[3][i];for(i=0;i<4;++i){
    packet.destid = i;if(dt3.costs[3][i] != 999 && i != 3) tolayer2(packet);}}
}printdt3(dtptr)struct distance_table *dtptr;
{
    printf(" via \n");printf(" D3 | 0 1 2 3 \n");printf(" ----|-----------------\n");printf(" 3| %3d %3d %3d %3d\n",dtptr->costs[3][0],dtptr->costs[3][1],dtptr->costs[3][2],dtptr->costs[3][3]);
}

最终实现效果

大家可以对照一下图检查一下是不是每个都是最短距离那就先写到这里辣各位再见