您当前位置:618教育论文网 >> 最新论文 >> 美术教学集 >> 浏览文章

浅议标号标号树编解码的线性算法毕业设计论文格式

浅议标号标号树编解码的线性算法毕业设计论文格式内容导读:现标号树t中求解u节点的邻接点运算。  PR( LTree t,int c[] )  { int i,j,u,v;  u=v=j=0;  for(i=1;i<N-1;i++)  * { if(v<j&&t.data==1) u=v;  //找编号最小的叶子节点u  else  { while(t.data!=1) ;  u=j;  }  v=GetAdjvex(t,u); // 找叶子u相邻节点v源于:大专毕业论文http://www.618jyw.com  c=v; //将

  摘要:标号树的编码是一串能够映射一棵标号树结构的标号序列,由于在现代优化算法中便于运算而常常被采用。本文对四种常见的标号树的编解码方法进行了综述,并就标号树直观的边集表示和编码表示之间的转换算法进行讨论,实现了四种标号树编解码的线性算法。

  关键词:标号树;Prufer编码;Nevile编码;DM编码

  ● 引言

  标号树是计算机领域中常见的一种数据组织形式,它的传统存储方法通常有双亲表示法、孩子表示法、孩子兄弟表示法、边集表示法等,这些表示方法,在遗传、粒子群等现代优化算法中,由于很难进行运算,所以很少被使用。而标号树的编码是一串可以映射一棵标号树的标号序列,由于其存储简单、便于运算,常常被采用,因而对于标号树编码的深入讨论,无论在计算机的理论还是应用上,都有着十分重要的意义。

  1918年Prufer在证明Cayley定理时,最先提出了Prufer编码,1953年Neville提出了三种编码方法,其中第一种和Prufer码一样,后两种称之为Neville2码、Neville3码,近年来Deo和Micikevicius又提出了一种新的编码方法。我们将上述四种编码简称为PR、N2、N3、DM码。

  根据编码定义,以上四种编码除DM编解码的算法时间为О(n),其他三种都为О(n2)。近年来一些文献用算法语言给出了它们的线性算法思想。本文在综述上述四种编解码规则之后,用C语言,就标号树直观的边集表示和编码表示之间的转换,给出了编码和解码的线性算法。

  ● 标号树的编码

  1.编码方法

  总的来说,四种编码方法都是以叶节点的删除为基础,直至只剩下一条边为止,按照n-2个叶节点的删除顺序,依次将其在删除前的邻接点编号组成一个数字序列,就是其标号树的编码。四种编码的不同在于叶节点的删除顺序不同。

  (1)PR编码

  删除标号树中最小编号的叶节点;重复第一步,直至该标号树剩一条边。

  如图1所示的标号树,PR编码的叶子节点删除顺序应为3、4、5、6、8、1、2、9,其相应的邻接点顺序为(6,10,6,7,1,2,7,7)。

  (2)N2编码

  按升序将标号树的叶节点整批删除;在修正过的标号树上重复第一步,直至该标号树剩一条边。

  如图1,N2编码的叶子节点删除顺序应为第一层的3、4、5、8、9和第二层的1、6、10,其相应的邻接点顺序为(6,10,6,1,7,2,7,7)。

  (3)N3编码

  从最小叶节点开始,逐个删除其所在链上的节点,直至该链被删除;重复第一步,直至该标号树剩一条边。

  如图1,N3编码的叶节点删除顺序应为第一条链3,第二条链4、10,第三条链5、6,第四条链8、1、2,其相应的邻接点顺序为(6,10,7,6,7,1,2,7)。

  (4)DM编码

  按升序将标号树的叶节点整批删除;对修正过的标号树按照其叶节点出现的先后顺序进行整批删除;重复第二步,直至该标号树剩一条边。

  如图1,DM编码的叶子节点删除顺序应为第一层的3、4、5、8、9和第二层的10,6,1,其相应的邻接点顺序为(6,10,6,1,7,7,7,2)。

  2.编码算法

  (1)存储结构

  typedef struct node

  { int data;

  struct node *next;

  } Node;

  typedef Node LTree[N+1];

  LTree t;

  标号树的存储结构采用了图的邻接表存储形式,其说明语句如上,标号树的邻接表存储示意图见图2。将标号树中每个节点i的度数存放在t[i]的data域中,将与该节点i相邻的所有邻接点,以链表链接在t[i]的next域中,为了节点i和t数组下标的一致,这里数组的长度定义为N+1。

  (2)PR编码算法

  PR编码算法的思想:在邻接表t中顺序查找出第一个度数为1的节点j(t[j].data=1),当前最小的叶节点u=j,求出和u相邻的节点v,写入编码数组,删除最小叶节点u(t[u].data--,t[v].data--);比较v和j,如果v

  PR编码算法实现见函数PR( ),c数组存放标号树的PR编码;函数GetAdjvex( )实现标号树t中求解u节点的邻接点运算。

  PR( LTree t,int c[] )

  { int i,j,u,v;

  u=v=j=0;

  for(i=1;i

  * { if(v

  //找编号最小的叶子节点u

  else

  { while(t[++j].data!=1) ;

  u=j;

  }

  v=GetAdjvex(t,u); // 找叶子u相邻节点v

源于:大专毕业论文http://www.618jyw.com

  c[i]=v; //将节点v写入c数组

  t[u].data--; t[v].data--; // 删除边(u,v)

  }

  }

  int GetAdjvex(LTree t ,int u )

  { Node *p=t[u].next;

  while( t[p->data].data==0) p=p->next;

源于:免费毕业论文网站http://www.618jyw.com


浅议标号标号树编解码的线性算法毕业设计论文格式内容回顾: