「食物链拓扑算法java」食物链延伸模式
本篇文章给大家谈谈食物链拓扑算法java，以及食物链延伸模式对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
拓扑排序算法实现
拓扑排序算法实现采用邻接表作为拓扑排序算法的存储结构，所设计的系统要有简单的 DOS 界面，方便用户进行操作，完成以下功能：
1、实现图的基本运算，如：增加边，删除边，判断边是不是存在等；
2、实现堆栈类，要求采用链式存储结构实现；
3、实现拓扑排序算法，要求使用堆栈类存放入度为零的顶点；
4、输出拓扑排序的结果到文本文件中保存；
5、退出系统。
拓扑排序 编程
*/
#include stdio.h
#include malloc.h
// 输出有向图的一个拓扑序列。实现算法7.12的程序
// 图的邻接表存储表示
#define MAX_NAME 3 // 顶点字符串的最大长度+1
#define MAX_VERTEX_NUM 20
typedef int InfoType; // 存放网的权值
typedef char VertexType[MAX_NAME]; // 字符串类型
typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网}
typedef struct ArcNode
{
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
InfoType *info; // 网的权值指针）
}ArcNode; // 表结点
typedef struct VNode
{
VertexType data; // 顶点信息
ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];// 头结点
typedef struct
{
AdjList vertices;
int vexnum,arcnum; // 图的当前顶点数和弧数
int kind; // 图的种类标志
}ALGraph;
// 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。
int LocateVex(ALGraph G,VertexType u)
{
int i;
for(i=0;iG.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
// 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)。
int CreateGraph(ALGraph *G)
{
int i,j,k;
int w; // 权值
VertexType va,vb;
ArcNode *p;
printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d",(*G).kind);
printf("请输入图的顶点数和边数:（空格）\n");
scanf("%d%d", (*G).vexnum, (*G).arcnum);
printf("请输入%d个顶点的值(%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i = 0; i (*G).vexnum; ++i) // 构造顶点向量
{
scanf("%s", (*G).vertices[i].data);
(*G).vertices[i].firstarc = NULL;
}
if((*G).kind == 1 || (*G).kind == 3) // 网
printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
else // 图
printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
for(k = 0;k (*G).arcnum; ++k) // 构造表结点链表
{
if((*G).kind==1||(*G).kind==3) // 网
scanf("%d%s%s",w,va,vb);
else // 图
scanf("%s%s",va,vb);
i = LocateVex(*G,va); // 弧尾
j = LocateVex(*G,vb); // 弧头
p = (ArcNode*)malloc(sizeof(ArcNode));
p-adjvex = j;
if((*G).kind == 1 || (*G).kind == 3) // 网
{
p-info = (int *)malloc(sizeof(int));
*(p-info) = w;
}
else
p-info = NULL; // 图
p-nextarc = (*G).vertices[i].firstarc; // 插在表头
(*G).vertices[i].firstarc = p;
if((*G).kind = 2) // 无向图或网,产生第二个表结点
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p-adjvex = i;
if((*G).kind == 3) // 无向网
{
p-info = (int*)malloc(sizeof(int));
*(p-info) = w;
}
else
p-info = NULL; // 无向图
p-nextarc = (*G).vertices[j].firstarc; // 插在表头
(*G).vertices[j].firstarc = p;
}
}
return 1;
}
// 输出图的邻接表G。
void Display(ALGraph G)
{
int i;
ArcNode *p;
switch(G.kind)
{
case DG: printf("有向图\n");
break;
case DN: printf("有向网\n");
break;
case AG: printf("无向图\n");
break;
case AN: printf("无向网\n");
}
printf("%d个顶点：\n",G.vexnum);
for(i = 0; i G.vexnum; ++i)
printf("%s ",G.vertices[i].data);
printf("\n%d条弧(边):\n", G.arcnum);
for(i = 0; i G.vexnum; i++)
{
p = G.vertices[i].firstarc;
while(p)
{
if(G.kind = 1) // 有向
{
printf("%s→%s ",G.vertices[i].data,
G.vertices[p-adjvex].data);
if(G.kind == DN) // 网
printf(":%d ", *(p-info));
}
else // 无向(避免输出两次)
{
if(i p-adjvex)
{
printf("%s－%s ",G.vertices[i].data,
G.vertices[p-adjvex].data);
if(G.kind == AN) // 网
printf(":%d ",*(p-info));
}
}
p=p-nextarc;
}
printf("\n");
}
}
// 求顶点的入度，算法7.12、7.13调用
void FindInDegree(ALGraph G,int indegree[])
{
int i;
ArcNode *p;
for(i=0;iG.vexnum;i++)
indegree[i]=0; // 赋初值
for(i=0;iG.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
indegree[p-adjvex]++;
p=p-nextarc;
}
}
}
typedef int SElemType; // 栈类型
#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACKINCREMENT 2 // 存储空间分配增量
// 栈的顺序存储表示 P46
typedef struct SqStack
{
SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}SqStack; // 顺序栈
// 构造一个空栈S。
int InitStack(SqStack *S)
{
// 为栈底分配一个指定大小的存储空间
(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if( !(*S).base )
exit(0); // 存储分配失败
(*S).top = (*S).base; // 栈底与栈顶相同表示一个空栈
(*S).stacksize = STACK_INIT_SIZE;
return 1;
}
// 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。
int StackEmpty(SqStack S)
{
if(S.top == S.base)
return 1;
else
return 0;
}
// 插入元素e为新的栈顶元素。
int Push(SqStack *S, SElemType e)
{
if((*S).top - (*S).base = (*S).stacksize) // 栈满，追加存储空间
{
(*S).base = (SElemType *)realloc((*S).base,
((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));
if( !(*S).base )
exit(0); // 存储分配失败
(*S).top = (*S).base+(*S).stacksize;
(*S).stacksize += STACKINCREMENT;
}
*((*S).top)++=e;
// 这个等式的++ * 优先级相同，但是它们的运算方式，是自右向左
return 1;
}
// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。
int Pop(SqStack *S,SElemType *e)
{
if((*S).top == (*S).base)
return 0;
*e = *--(*S).top;
// 这个等式的++ * 优先级相同，但是它们的运算方式，是自右向左
return 1;
}
// 算法7.12 P182
// 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序
// 列并返回1, 否则返回0。
int TopologicalSort(ALGraph G)
{
int i,k,count,indegree[MAX_VERTEX_NUM];
SqStack S;
ArcNode *p;
FindInDegree(G,indegree); // 对各顶点求入度indegree[0..vernum-1]
InitStack(S); // 初始化栈
for(i=0;iG.vexnum;++i) // 建零入度顶点栈S
if(!indegree[i])
Push(S,i); // 入度为0者进栈
count=0; // 对输出顶点计数
while(!StackEmpty(S))
{
// 栈不空
Pop(S,i);
printf("%s ",G.vertices[i].data); // 输出i号顶点并计数
++count;
for(p=G.vertices[i].firstarc;p;p=p-nextarc)
{
// 对i号顶点的每个邻接点的入度减1
k=p-adjvex;
if(!(--indegree[k])) // 若入度减为0,则入栈
Push(S,k);
}
}
if(countG.vexnum)
{
printf("此有向图有回路\n");
return 0;
}
else
{
printf("为一个拓扑序列。\n");
return 1;
}
}
int main()
{
ALGraph f;
printf("请选择有向图\n");
CreateGraph(f);
Display(f);
TopologicalSort(f);
system("pause");
return 0;
}
/*
输出效果：
请选择有向图
请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): 0
请输入图的顶点数和边数:（空格）
4 4
请输入4个顶点的值(3个字符):
a
b
c
d
请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):
a b
a c
b d
c d
有向图
4个顶点：
a b c d
4条弧(边):
a→c a→b
b→d
c→d
a b c d 为一个拓扑序列。
请按任意键继续. . .
*/
一种高效的链路层拓扑发现算法
一、LLDP协议概述
随着网络技术的发展，接入网络的设备的种类越来越多，配置越来越复杂，来自不同设备厂商的设备也往往会增加自己特有的功能，这就导致在一个网络中往往会有很多具有不同特性的、来自不同厂商的设备，为了方便对这样的网络进行管理，就需要使得不同厂商的设备能够在网络中相互发现并交互各自的系统及配置信息。
LLDP（Link Layer Discovery Protocol，链路层发现协议）就是用于这个目的的协议。LLDP定义在802.1ab中,它是一个二层协议，它提供了一种标准的链路层发现方式。LLDP协议使得接入网络的一台设备可以将其主要的能力，管理地址，设备标识，接口标识等信息发送给接入同一个局域网络的其它设备。当一个设备从网络中接收到其它设备的这些信息时，它就将这些信息以MIB的形式存储起来。
这些MIB信息可用于发现设备的物理拓扑结构以及管理配置信息。需要注意的是LLDP仅仅被设计用于进行信息通告，它被用于通告一个设备的信息并可以获得其它设备的信息，进而得到相关的MIB信息。它不是一个配置、控制协议，无法通过该协议对远端设备进行配置，它只是提供了关于网络拓扑以及管理配置的信息，这些信息可以被用于管理、配置的目的，如何用取决于信息的使用者。
二、LLDP结构
LLDP的框架结构如图所示：
此图也表明LLDP就是一个信息发现与通告协议，LLDP的实体主要维护了两个MIB库，一个 local system MIB，一个remote system MIB。从其名字也可以看出，一个用于维护本地相关的设备MIB信息，一个用于维护远端设备MIB信息。
LLDP通过与上图中右侧的几个MIB库交互来初始化并维护 local system MIB，并将本地的相关信息通告出去；同时当接收到来自其它设备的信息时就将其更新到remote system MIB中。通过这种工作方式，一个设备就可以将自己的信息通告出去并获得网络中其它设备的相关信息，最终获得反应网络拓扑以及其它配置信息的两个MIB库。这两个库可以被其用户用来完成各种功能。
需要说明的是LLDP信息的通告以及接收处理不受端口的STP状态的影响。
三、LLDP基本概念
1．LLDP帧格式
封装有 LLDPDU 的报文称为 LLDP 帧，其封装格式有两种：Ethernet II 和 SNAP（Subnetwork Access Protocol，子网访问协议）。
1.1 Ethernet II格式封装的LLDP帧
上图是以Ethernet II格式封装的LLDP帧，其中各字段的含义如下：
DA：目的 MAC地址，为固定的组播 MAC地址 0x0180-C200-000E。
SA：源 MAC地址，为端口 MAC地址或设备MAC地址（如有端口地址则用端口MAC地址，否则用设备MAC地址）。
Type：帧类型，为 0x88CC。
Data：数据，为 LLDPDU。
FCS：帧检验序列。
1.2 SNAP格式封装的LLDP帧
上图是以SNAP格式封装的LLDP帧，其中各字段的含义如下：
DA：目的MAC地址，为固定的组播 MAC地址 01-80-C2-00-00-0E。
SA：源MAC地址，为端口MAC地址或设备MAC地址（如果有端口地址则用端口MAC地址，否则用设备MAC地址）。
Type：帧类型，为 0xAAAA-0300-0000-88CC。
Data：数据，为 LLDPDU。
FCS：帧检验序列。
1.3 目地地址
目地地址实际上包括三个，分别为01-80-C2-00-00-0E，01-80-C2-00-00-03，01-80-C2-00-00-00。这三个地址分别用于不同的目地，它们可以跨越不同的网络。
01-80-C2-00-00-0E，也被称为Nearest Bridge组地址：无论是Two-Port MAC Relay (TPMR)组件还是S-VLAN组件还是C-VLAN组件，还是802.1D网桥都不能转发目地为该地址的帧。简单的说任何类型的网桥都不能转发目地为该地址的帧，目地为该地址的帧被限制在连接两个网桥接口的连接上传输。
01-80-C2-00-00-03，也被称为Nearest non-TPMR Bridge组地址：对于目地地址为该地址的帧，Two-Port MAC Relay (TPMR)组件将成为一个中继器，即不接收它。而S-VLAN组件，C-VLAN组件，以及802.1D网桥不能转发它，而是需要进行接收并处理。因此目地地址为该地址的帧将跨越TPMR。
01-80-C2-00-00-00，也被称为Nearest non-Customer Bridge组地址：对于目地地址为该地址的帧，Two-Port MAC Relay (TPMR)组件以及S-VLAN组件将成为中继器，即不接收它。而C-VLAN组件，以及802.1D网桥不能转发它，而是需要进行接收并处理。因此目地地址为该地址的帧将跨越TPMR以及S-VLAN。
TPMR以及S-VLAN，C-VLAN都是802.1Q中的概念，包括这三者的网络以及各个地址的作用范围如下图所示：
2. LLDPDU
LLDPPDU是LLDP的有效负载，用于承载要发送的消息。LLPDU的格式如下图所示：
LLDPDU采用了TLV的格式，即type+lenght+value的格式，type表示TLV的类型，length是以字节为单位的TLV的长度，value是该TLV的值。其中Chassis ID TLV，Port ID TLV Time To Live TLV以及End Of LLDPDU TLV是强制的，必须包含的部分，除此之外在TLV Time To Live TLV和End Of LLDPDU TLV之间可以包含0个到多个可选的其它TLV。
3. TLV
TLV是组成 LLDPDU的单元，每个 TLV都代表一个信息。LLDPDU的TLV可以分为两大类：
被认为是网络管理的基础的TLV集合，所有的LLDP实现都需要支持。
组织定义的TLV扩展集和，包括 802.1组织定义 TLV、802.3组织定义TLV以及其他组织定义的TLV。这些TLV用于增强对网络设备的管理，可根据实际需要选择是否在 LLDPDU中发送。
TLV的基本格式如图所示：
TLV的类型域的定义及分配如下图所示：
其中type0-8属于基本的TLV集合。对于其中的Mandatory的TLV，它是必须包含在LLDP中的。
组织定义TLV集合的格式如下图所示：
其中：
OUI：组织机构的ID。
organizationally defined subtype：组织自定义的类型。
organizationally defined information string：传输的信息。
4. 基础TLV集合的TLV定义
几个强制的必须包含的TLV的定义如下。非强制的可以参考IEEE802.1AB。
4.1 End Of LLDPDU TLV
该TLV用于标识LLDPDU的结束。其格式如下：
由于length=0，因此它不包含value域。
4.2 Chassis ID TLV
该TLV用于通告该LLDPDU发送者的chassis ID。由于有很多方式可用来标识一个chassis，因此在该类TLV中包含一个子类型域用于告诉接收者，发送者的chassis ID采用的是哪一种标识方式。其格式如图所示：
每个LLDPDU必须包含且仅包含一个该类型的TLV。由于chassis ID实际上是用于标识设备的，因此在连接可用时它应该保持不变。
chassis子类型所可能的取值如图所示：
4.3 Port ID TLV
它用于标识发送该LLDPDU的设备的端口。类似于chassis ID，有很多方式可以标识一个Port，因此该TLV也包含一个子类型域。其格式如下图所示：
每个LLDPDU必须包含一个且只能包含一个该类型的TLV。同时，当端口可用时，从该端口发送出去的LLDPDU的该TLV应该保持不变。
其子类型的可能取值如下图所示：
4.4 Time To Live TLV
该TLV用于告诉接收端，它接收到的这些信息的有效期有多长。其格式如图所示：
TTL的时间单位是秒，由于只有2个字节长，因而最大有效时间是65536秒。如果在这个时间到期了还没有新的LLDPDU被收到，则该TLV所属的那个LLDPDU携带的信息会被从MIB中删除。如果收到了新的LLDPDU，则：
如果TTL不为0，则会用新收到的LLDPDU的信息替换MIB库中的相应的信息（即与该LLDPDU的发送者相关的MIB信息，LLDP使用Chassis ID + Port ID来判断是否来自于同一个源，这也是要求这两者保持不变的原因）。
如果TTL为0，则删除相应的MIB库中的信息（即与该LLDPDU的发送者相关的MIB信息）。因此TTL为0的LLDPDU又被称为SHUTDOWN LLDPDU。
每一个LLDPDU必须包含且只能包含一个该类型的TLV。
四、工作机制
LLDP是一个用于信息通告和获取的协议，但是需要注意的一点是，LLDP发送的信息通告不需要确认，不能发送一个请求来请求获取某些信息，也就是说LLDP是一个单向的协议，只有主动通告一种工作方式，无需确认，不能查询、请求（比如像ARP协议那样请求某个IP的MAC地址）。
LLDP主要完成如下工作：
初始化并维护本地MIB 库中的信息。
从本地MIB 库中提取信息，并将信息封装到LLDP 帧中。LLDP帧的发送有两种触发方式，一是定时器到期触发，一是设备状态发生了变化触发。
识别并处理接收到的LLDPDU帧
维护远端设备LLDP MIB 信息库。
当本地或远端设备MIB信息库中有信息发生变化时，发出通告事件。
1．LLDPDU发送
1.1 发送机制
LLDPDU的发送可以被如下事件触发：
与本地MIB信息库相关联的定时器txTTR到期时，这将确保远端接收系统中的相关信息不会因为TTL到期而过期。
本地MIB信息库中的信息发生了改变时，会立即发送LLDPDU，这将保证改变能及时被更新。
如果一个“新邻居”被识别，将会启用快速发送机制，在很短的时间内连续发送指定数量（txFastInit，默认值为4）的LLDPDU，以确保“新邻居”能被快速更新。如果远端系统MIB信息库因为过载（tooManyNeighbors）而不能容纳新的邻居信息，则会为了避免过多的PDU传输而抑制快速发送行为。
LLDP的常规发送时间是建立在系统的tick之上的，间隔为1秒一个，为了防止在共享介质的LAN（shared media LAN）中同时出现大量的LLDPDU（因为接入同一个LAN的多个系统的时间是同步的，因而多个系统上的基于tick的1秒定时器可能同时到期），发送定时器引入了一个随机的抖动，这就使得常规的LLDP帧的发送间隔时间的平均值仍是1秒，但是具体到某一次到期时间可能并不是准确的1秒。
同时为了防止在有多个端口需要发送LLDPDU的系统中，所有的端口的定时器都在同一时间到期，因而标准建议将采用某种机制将多个发送实例的定时器到期时间给错开，以避免一个系统在同一时刻发送大量的LLDPDU。
1.2 发送状态机
LLDPDU的发送状态机如图所示
对于该状态机：
为了防止过于频繁的重新初始化发送状态机，在LLDP的发送状态机中引入了一个延时，该延时限制了在关闭发送状态机后，必须至少等待多长时间才能重新初始化发送状态机。
是否发送SHUTDOWNLLDPDU由本地的LLDP工作状态决定。
是否发送正常的LLDPDU由txNow和txCredit决定。这两个变量都由发送定时器状态机更新。txNow决定是否发送，而txCredit则是一个信用量，决定了可以发送的量，如果是0则不允许发送，只有大于0的值才允许发送，每发送一个该值就减1。更重要的是在本地信息快速改变时，txCredit即允许连续发送多个LLDPDU，但是又对可以连续发送的LLDPDU帧数做了限制，这使得本地状态的快速改变可以及时被通告出去，但是又不能无限发送导致网络出现大量LLDPDU帧。
1.3发送定时器状态机
LLDP发送定时器状态机如图所示：
localChange表示本地信息是否发生改变；txTTR表示下一次定时器到期的时间；newNeighbor表示是否发现了新的邻居，并由接收状态设置，由该状态机清除；txTick表示基于系统时间的1秒定时器是否到期。
对于该状态机：
SIGNAL_TX用于触发发送，它会将txNow设置为允许发送，并设置本地信息发生改变为FALSE，如果当前不是在快速发送状态（txFast = 0）就设置发送定时器下次到期时间为msgTxInterval（msgTxInterval默认为30秒，取值范围1-3600秒），否则设置发送定时器下次到期时间为msgFastTx（msgFastTx默认值为1秒，取值范围1-3600秒）
如果本地信息发生了改变，就立即进入SIGNAL_TX
如果定时器到期，则如果txFast大于0，则将其减1并进入SIGNAL_TX，否则直接进入SIGNAL_TX
如果发现了新邻居，则首先将发现新邻居的标识更新为没有发现新邻居，然后如果当前已经处于快速发送状态就直接进入发送定时器到期状态（以触发一次立即发送），否则设置txFast的值为txFastInit的值（txFastInit默认值为4，取值范围1-8）
如果基于系统时间的1秒定时器到期，则给txCredit增加信用量，其最大值为txCreditMax，txCreditMax是一个取值在1到10之间的值，默认值为5。
这里有取值范围的几个变量都是可配置的变量。
从上述两个状态机的工作状态可以看出，发送定时器状态机用于维护信用量以及是否允许发送LLDPDU帧，而发送状态机根据这两个信息来决定是否发送。
另外需要注意的是LLDP所使用的所有定时器操作都是基于“基于系统时间的1秒定时器的”，每当这个定时器到期时它除了会将txTick设置为TRUE外，还会处理其它的定时功能。
2．LLDPDU 接收
2.1 接收机制
LLDP帧的接收由3个阶段组成：帧的识别、帧的校验以及LLDP远端MIB信息库更新。
2.1.1 帧的识别
帧识别由在LLDP/LSAP（链路服务访问点）进行，检查的内容是帧的目的地是否是LLDP的组播MAC地址，帧的类型是否是LLDP。
2.1.2 帧的验证
该过程会首先根据TLV的格式定义依次校验Chassis ID TLV，Port ID TLV， Time To Live TLV，如果这三个TLV都存在且有效，才会进一步的解码可选的TLV直到遇到End Of LLDPDU TLV，然后根据获得的信息更新远端MIB信息库。
2.1.3 远端MIB信息库更新
在前两步都通过之后，LLDPDU的接收者就需要根据解析出来的信息更新远端MIB信息库。在MIB信息库中，LLDP使用chassis ID + Port ID来标识、存储来自不同源的信息。
如果远端MIB库中已经有对应于该chassis ID + Port ID的信息，则使用收到的帧中的新的TTL来更新TTL。并用对于收到的新的LLDPPDU中的每一种type，如果有变化就进行更新，如果某种type原来不存在，则需要将其添加到MIB库中。
如果实现不支持某种类型的type，则
如果type不是127，则按照基本TLV的格式将其存储到远端MIB库，存储格式为type， length，value。
如果type是127，则按照组织定义TLV的格式将其存储到远端MIB库，存储格式为type， length，value，OUI，组织自定义子类型，以及信息域。
更新时，如果需要添加新的chassis ID + Port ID的表项，或者为某个chassis ID + Port ID添加新的TLV，则可能遇到没有内存的问题，标准没有规定必须如何处理，只是给出了一些建议：
忽略新的LLDPDU的信息
删除最旧的信息以释放空间给新的信息
随机删除一些旧的信息以释放空间给新的信息
LLDPDU 携带的TTL（Time To Live）值会影响接收端的处理方式，如果它不为0，则更新相应信息的老化时间，如果接收到的LLDPDU 中的TTL 等于0，则将立刻老化掉相应的信息（即与该LLDPDU的发送者相关的MIB信息）。
如果一个chassis ID + Port ID标识的信息的TTL超时，则相应的MIB信息会被删除。
2.2 接收状态机
LLDPDU的接收状态机如图所示：
3. LLDP工作模式
LLDP可以工作在多种模式下：
TxRx：既发送也接收LLDP 帧。
Tx：只发送不接收LLDP 帧。
Rx：只接收不发送LLDP 帧。
Disable：既不发送也不接收LLDP 帧（准确的说，这并不是一个LLDP的状态，这可能是LLDP功能被关闭了，也可能是设备就不支持）。
由于LLDP可以单独工作在发送或接收模式下，因此LLDP协议的实现需要支持单独初始化发送或者接收功能。当工作模式发生变化时，需要根据老的/新的工作模式来关闭/打开发送或者接收的功能。
拓扑排序
1、堆栈
栈是一种特殊的线性表，插入或删除栈元素的运算只能在表的一端进行，称运算的一端为栈顶，另一端称为栈底。队列也是一种特殊的线性表（基本操作都是线性操作的子集）。
特点：后进先出
栈又称为“后进先出”的线性表，简称LIFO表。
栈的链式实现是以链表作为栈的存储结构，并在这种存储结构上实现栈的基本运算。栈的链式实现称为链栈。
2、有向无环图
描述含有公共子式的表达式的有效工具；
描述一项工程或系统的进行过程的有效工具。
3、一些概念
通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。
我们用一种有向图来表示这些工程、计划等，在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这种用顶点表示活动，用弧来表示活动间的优先关系的有向图叫做顶点表示活动的网络(Actire On Vertices)简称为AOV网。
拓扑排序：
假设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列vl，v2，…，vn称做一个拓扑序列(TopologicalOrder)，当且仅当该顶点序列满足下列条件：若在有向图G中存在从顶点vi到vj的一条路径，则在顶点序列中顶点vi必须排在顶点vj之前。通常，在AOV网中，将所有活动排列成一个拓扑序列的过程叫做拓扑排序(Topological Sort)。
在AOV网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。
判定网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。
4、拓扑排序的算法思想
输入AOV网络。令 n 为顶点个数。
（1）在AOV网络中选一个没有直接前驱的顶点，并输出之；
（2）从图中删去该顶点, 同时删去所有它发出的有向边；
重复以上步骤，直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。
5、拓扑排序算法的C语言描述
在实现拓扑排序的算法中，采用邻接表作为有向图的存储结构，每个顶点设置一个单链表，每个单链表有一个表头结点，在表头结点中增加一个存放顶点入度的域count，这些表头结点构成一个数组。
为了避免重复检测入度为0的点，另设一栈存放所有入度为0的点。
对于有n个顶点和e条边的有向图而言，for循环中建立入度为0的顶点栈时间为O（n）；若在拓扑排序过程中不出现有向环，则每个顶点出栈、入栈和入度减1的操作在while循环语句中均执行e次，因此拓扑排序总的时间花费为O (n+e)。
6、拓扑排序算法的C语言实现
#include"stdio.h"
#define MAX_VERTEX_NUM20
#include"conio.h"
#include"stdlib.h"
#define STACK_INIT_SIZE16
#define STACKINCREMENT5
typedef int SElemType;
typedef charVertexType;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
//我们依然用邻接表来作图的存储结构
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
int info;
}ArcNode; //表结点类型
typedef struct VNode{
VertexType data;
int count;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];//头结点
typedef struct{
AdjList vertices; //邻接表
int vexnum,arcnum;
}ALGraph;
int InitStack(SqStackS)
{
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) exit(-1);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 1;
}//InitStack
int Push(SqStackS,SElemType e)
{
if((S.top-S.base)=S.stacksize)
{
S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(-1);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}//if
*(S.top)=e;
S.top++;
return 1;
}//Push
int Pop(SqStackS,SElemType e)
{
if(S.top==S.base)return 0;
--S.top;
e=*S.top;
return 1;
}//Pop
int StackEmpty(SqStackS)
{
if(S.top==S.base)return 1;
else return 0;
}//StackEmpty
int LocateVex(ALGraphG,char u)
{
int i;
for (i=0;iG.vexnum;i++)
{ if(u==G.vertices[i].data) return i; }
if (i==G.vexnum) {printf("Error u!\n");exit(1);}
return 0;
}
voidCreateALGraph_adjlist(ALGraph G)
{
int i,j,k,w;
char v1,v2,enter;
ArcNode *p;
printf("Input vexnum arcnum:\n");
scanf("%d",G.vexnum);
scanf("%d",G.arcnum);
printf("Input Vertices(以回车隔开各个数据):\n");
for (i=0;iG.vexnum;i++)
{ scanf("%c%c",enter,G.vertices[i].data);//注意点，解说
G.vertices[i].firstarc=NULL;
}//for
printf("InputArcs(v1,v2,w)以回车分开各个数据:\n");
for (k=0;kG.arcnum;k++)
{
scanf("%c%c",enter,v1);
scanf("%c%c",enter,v2);
//scanf("%d",w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
p=(ArcNode*)malloc(sizeof(ArcNode));
p-adjvex=j;
//p-info = w;
p-nextarc=G.vertices[i].firstarc; //前插法,即每次都插入到头结点的后面
G.vertices[i].firstarc=p;
printf("Next\n");
}//for
return;
}//CreateALGraph_adjlist
voidFindInDegree(ALGraph G)
{
int i,j;
for(i=0;iG.vexnum;i++)
{
G.vertices[i].count=0;
}//for
for(j=0;jG.vexnum;j++)
{
//G.vertices[i].count++;
for(ArcNode*p=G.vertices[j].firstarc;p;p=p-nextarc)
G.vertices[p-adjvex].count++;
}//for
}//FindInDegree
int TopoSort(ALGraphG)
{
SqStack S;
FindInDegree(G);
InitStack(S);
for(inti=0;iG.vexnum;i++)
if(G.vertices[i].count==0) Push(S,i);
int countt=0;
while(!StackEmpty(S))
{
int i,m;
m=Pop(S,i);
printf(" %c",G.vertices[i].data); ++countt;
for(ArcNode *p=G.vertices[i].firstarc;p;p=p-nextarc)
{ int k;
k=p-adjvex;
if(!(--G.vertices[k].count)) Push(S,k);
}//for
}//while
if(counttG.vexnum) return 0;
else return 1;
}//TopoSort
int main()
{
ALGraph G;
CreateALGraph_adjlist(G);
TopoSort(G);
return 1;
}
7、malloc函数和realloc函数
realloc: void *realloc(void *block, size_t size)，将block所指存储块调整为大小size，返回新块的地址。如能满足要求，新块的内容与原块一致；不能满足要求时返回NULL，此时原块不变。
malloc:void *malloc(size_t size)：分配一块足以存放大小为size的存储，返回该存储块的地址，不能满足时返回NULL。
数据结构 java开发中常用的排序算法有哪些
排序算法有很多，所以在特定情景中使用哪一种算法很重要。为了选择合适的算法，可以按照建议的顺序考虑以下标准：
（1）执行时间
（2）存储空间
（3）编程工作
对于数据量较小的情形，（1）（2）差别不大，主要考虑（3）；而对于数据量大的，（1）为首要。
主要排序法有：
一、冒泡（Bubble）排序——相邻交换
二、选择排序——每次最小/大排在相应的位置
三、插入排序——将下一个插入已排好的序列中
四、壳（Shell）排序——缩小增量
五、归并排序
六、快速排序
七、堆排序
八、拓扑排序
一、冒泡（Bubble）排序
----------------------------------Code 从小到大排序n个数------------------------------------
void BubbleSortArray()
{
for(int i=1;in;i++)
{
for(int j=0;in-i;j++)
{
if(a[j]a[j+1])//比较交换相邻元素
{
int temp;
temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;
}
}
}
}
-------------------------------------------------Code------------------------------------------------
效率 O（n²）,适用于排序小列表。
二、选择排序
----------------------------------Code 从小到大排序n个数--------------------------------
void SelectSortArray()
{
int min_index;
for(int i=0;in-1;i++)
{
min_index=i;
for(int j=i+1;jn;j++)//每次扫描选择最小项
if(arr[j]arr[min_index]) min_index=j;
if(min_index!=i)//找到最小项交换，即将这一项移到列表中的正确位置
{
int temp;
temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp;
}
}
}
-------------------------------------------------Code-----------------------------------------
效率O（n²），适用于排序小的列表。
三、插入排序
--------------------------------------------Code 从小到大排序n个数-------------------------------------
void InsertSortArray()
{
for(int i=1;in;i++)//循环从第二个数组元素开始，因为arr[0]作为最初已排序部分
{
int temp=arr[i];//temp标记为未排序第一个元素
int j=i-1;
while (j=0 arr[j]temp)/*将temp与已排序元素从小到大比较，寻找temp应插入的位置*/
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
}
}
------------------------------Code--------------------------------------------------------------
最佳效率O（n）；最糟效率O（n²）与冒泡、选择相同，适用于排序小列表
若列表基本有序，则插入排序比冒泡、选择更有效率。
四、壳（Shell）排序——缩小增量排序
-------------------------------------Code 从小到大排序n个数-------------------------------------
void ShellSortArray()
{
for(int incr=3;incr0;incr--)//增量递减，以增量3，2，1为例
{
for(int L=0;L(n-1)/incr;L++)//重复分成的每个子列表
{
for(int i=L+incr;in;i+=incr)//对每个子列表应用插入排序
{
int temp=arr[i];
int j=i-incr;
while(j=0arr[j]temp)
{
arr[j+incr]=arr[j];
j-=incr;
}
arr[j+incr]=temp;
}
}
}
}
--------------------------------------Code-------------------------------------------
适用于排序小列表。
效率估计O（nlog2^n）~O（n^1.5），取决于增量值的最初大小。建议使用质数作为增量值，因为如果增量值是2的幂，则在下一个通道中会再次比较相同的元素。
壳（Shell）排序改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。
五、归并排序
----------------------------------------------Code 从小到大排序---------------------------------------
void MergeSort(int low,int high)
{
if(low=high) return;//每个子列表中剩下一个元素时停止
else int mid=(low+high)/2;/*将列表划分成相等的两个子列表,若有奇数个元素，则在左边子列表大于右侧子列表*/
MergeSort(low,mid);//子列表进一步划分
MergeSort(mid+1,high);
int [] B=new int [high-low+1];//新建一个数组，用于存放归并的元素
for(int i=low,j=mid+1,k=low;i=mid j=high;k++)/*两个子列表进行排序归并，直到两个子列表中的一个结束*/
{
if (arr[i]=arr[j];)
{
B[k]=arr[i];
I++;
}
else
{ B[k]=arr[j]; j++; }
}
for( ;j=high;j++,k++)//如果第二个子列表中仍然有元素，则追加到新列表
B[k]=arr[j];
for( ;i=mid;i++,k++)//如果在第一个子列表中仍然有元素，则追加到新列表中
B[k]=arr[i];
for(int z=0;zhigh-low+1;z++)//将排序的数组B的 所有元素复制到原始数组arr中
arr[z]=B[z];
}
-----------------------------------------------------Code---------------------------------------------------
效率O（nlogn），归并的最佳、平均和最糟用例效率之间没有差异。
适用于排序大列表，基于分治法。
六、快速排序
------------------------------------Code--------------------------------------------
/*快速排序的算法思想：选定一个枢纽元素，对待排序序列进行分割，分割之后的序列一个部分小于枢纽元素，一个部分大于枢纽元素，再对这两个分割好的子序列进行上述的过程。*/ void swap(int a,int b){int t;t =a ;a =b ;b =t ;}
int Partition(int [] arr,int low,int high)
{
int pivot=arr[low];//采用子序列的第一个元素作为枢纽元素
while (low high)
{
//从后往前栽后半部分中寻找第一个小于枢纽元素的元素
while (low high arr[high] = pivot)
{
--high;
}
//将这个比枢纽元素小的元素交换到前半部分
swap(arr[low], arr[high]);
//从前往后在前半部分中寻找第一个大于枢纽元素的元素
while (low high arr [low ]=pivot )
{
++low ;
}
swap (arr [low ],arr [high ]);//将这个枢纽元素大的元素交换到后半部分
}
return low ;//返回枢纽元素所在的位置
}
void QuickSort(int [] a,int low,int high)
{
if (low high )
{
int n=Partition (a ,low ,high );
QuickSort (a ,low ,n );
QuickSort (a ,n +1,high );
}
}
----------------------------------------Code-------------------------------------
平均效率O（nlogn），适用于排序大列表。
此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢纽，可能导致O（n²）的最糟用例效率。若数基本有序，效率反而最差。选项中间值作为枢纽，效率是O（nlogn）。
基于分治法。
七、堆排序
最大堆：后者任一非终端节点的关键字均大于或等于它的左、右孩子的关键字，此时位于堆顶的节点的关键字是整个序列中最大的。
思想：
(1)令i=l,并令temp＝ kl ;
(2)计算i的左孩子j=2i+1;
(3)若j＝n－1，则转(4),否则转(6);
(4)比较kj和kj+1,若kj+1kj,则令j＝j＋1，否则j不变；
(5)比较temp和kj，若kjtemp，则令ki等于kj，并令i=j,j=2i+1,并转(3),否则转(6)
(6)令ki等于temp，结束。
-----------------------------------------Code---------------------------
void HeapSort(SeqIAst R)
{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元 int I; BuildHeap(R)； //将R[1-n]建成初始堆for(i=n;i1；i--) //对当前无序区R[1..i]进行堆排序，共做n-1趟。{ R[0]=R[1]; R[1]=R[i]; R[i]=R[0]; //将堆顶和堆中最后一个记录交换 Heapify(R,1,i-1); //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质 } } ---------------------------------------Code--------------------------------------
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)， 它是不稳定的排序方法。
堆排序与直接插入排序的区别:
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
八、拓扑排序
例 ：学生选修课排课先后顺序
拓扑排序：把有向图中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。
方法：
在有向图中选一个没有前驱的顶点且输出
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出（拓扑排序成功），或者当图中不存在无前驱的顶点（图中有回路）为止。
---------------------------------------Code--------------------------------------
void TopologicalSort()/*输出拓扑排序函数。若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR*/
{
int indegree[M];
int i,k,j;
char n;
int count=0;
Stack thestack;
FindInDegree(G,indegree);//对各顶点求入度indegree[0....num]
InitStack(thestack);//初始化栈
for(i=0;iG.num;i++)
Console.WriteLine("结点"+G.vertices[i].data+"的入度为"+indegree[i]);
for(i=0;iG.num;i++)
{
if(indegree[i]==0)
Push(thestack.vertices[i]);
}
Console.Write("拓扑排序输出顺序为：");
while(thestack.Peek()!=null)
{
Pop(thestack.Peek());
j=locatevex(G,n);
if (j==-2)
{
Console.WriteLine("发生错误，程序结束。");
exit();
}
Console.Write(G.vertices[j].data);
count++;
for(p=G.vertices[j].firstarc;p!=NULL;p=p.nextarc)
{
k=p.adjvex;
if (!(--indegree[k]))
Push(G.vertices[k]);
}
}
if (countG.num)
Cosole.WriteLine("该图有环，出现错误，无法排序。");
else
Console.WriteLine("排序成功。");
}
----------------------------------------Code--------------------------------------
算法的时间复杂度O（n+e）。
网络拓扑发现的目前Java技术实现的拓扑发现产品
ObjectSNMP是采用Java技术和SNMP技术实现的网络拓扑发现产品，目前的功能如下：
全网设备发现：可以按网络号、IP范围、多个网络范围内，自动搜索发现设备，获取设备的基本信息、设备类型（交换、路由、路由交换、终端设备、厂商特有类型等）、MAC地址、ARP表、交换机端口、路由器接口、路由表、交换机转发表、主机IP地址等信息。
网络漫游发现：给定少数几个已知的网络号、IP范围，按用户指定的漫游深度和漫游广度，进行全网漫游发现。
网络拓扑自动发现：可以发现交换机与交换机、交换机与PC机、交换机与终端设备、交换机与路由器、路由交换机与路由交换机之间 的连接关系。连接关系可以定位到具体的设备端口、设备接口上。支持在任意指定的设备之间发现它们的所有连接，在全网范围内发现连接关系。
ObjectSNMP的物理拓扑自动发现采用了全新的技术：即支持单一Cisco、华为网络，也支持各种厂商设备混合网络。支持模糊连接定位，在数据不全或设备缺失的情况下，尽可能发现连接关系。可在任意的网络环境中工作，不需要用户对网络做任何假设（如路由器假设、根交换机假设、上/下行端口假设、边缘设备假设等）。
关于食物链拓扑算法java和食物链延伸模式的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。