数据结构-双向列表与循环列表
循环链表
循环链表(Circular Linked List)：是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环。
从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。
循环链表的操作
对于单循环链表，除链表的合并外，其它的操作和单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上作以下简单修改：
⑴ 判断是否是空链表：head->next==head ;
⑵ 判断是否是表尾结点：p->next==head ;
双向链表
双向链表(Double Linked List) :指的是构成链表的每个结点中设立两个指针域：
一个指向其直接前趋的指针域prior，
一个指向其直接后继的指针域next。
这样形成的链表中有两个方向不同的链，故称为双向链表。
和单链表类似，双向链表一般增加头指针也能使双链表上的某些运算变得方便。
将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。
双向链表是为了克服单链表的单向性的缺陷而引入的
双向链表结构具有对称性，设p指向双向链表中的某一结点，则其对称性可用下式描述：
(p->prior)->next = p = (p->next)->prior ;
结点p的存储位置存放在其直接前趋结点p->prior的直接后继指针域中，同时也存放在其直接后继结点p->next的直接前趋指针域中。
① 若插入时仅仅标记出直接前驱结点，钩链时必须注意先后次序是： “先右后左” 。部分语句组如下：
s =(DulNode *)malloc(sizeof(DulNode));
s ->data=e;
s ->next=p->next; p->next->prior=s;
p->next= s; s ->prior=p; /* 钩链次序非常重要 */
② 插入时同时指出直接前驱结点p和直接后继结点q，钩链时无须注意先后次序。部分语句组如下：
s=(DulNode *)malloc(sizeof(DulNode));
s ->data=e;
p->next= s; s ->next=q;
s ->prior=p; q->prior= s; 双向链表的结点删除
设要删除的结点为p ，删除时可以不引入新的辅助指针变量，可以直接先断链，再释放结点。部分语句组如下：
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);注意：
与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指向
对两个多项式链表进行相加，生成一个新的链表存放相加后的结果，原来两个多项式链表依然存在，不发生任何改变，如果要再对原来两个多项式进行其它操作也不影响。
算法描述
Ploy *add_ploy(ploy *La， ploy *Lb)
/* 将以La ，Lb为头指针表示的一元多项式相加，生成一个新的结果多项式 */
{ ploy *Lc , *pc , *pa , *pb , *p ; float x ;
Lc=pc=(ploy *)malloc(sizeof(ploy)) ;
pa=La->next ; pb=Lb->next ;
while (pa!=NULL&&pb!=NULL)
{ if (pa->expn<pb->expn)
{ p=(ploy *)malloc(sizeof(ploy)) ;
p->coef=pa->coef ; p->expn=pa->expn ;
p->next=NULL ; /* 生成一个新的结果结点并赋值 */
pc->next=p ; pc=p ; pa=pa->next ;
} /* 生成的结点插入到结果链表的最后，pa指向下一个结点 */
if (pa->expn>pb->expn)
{ p=(ploy *)malloc(sizeof(ploy)) ;
p->coef=pb->coef ; p->expn=pb->expn ;
p->next=NULL ; /* 生成一个新的结果结点并赋值 */
pc->next=p ; pc=p ; pb=pb->next ;
} /* 生成的结点插入到结果链表的最后，pb指向下一个结点 */
if (pa->expn==pb->expn)
{ x=pa->coef+pb->coef ;
if (abs(x)<=1.0e-6) /* 系数和为0*/
{ pa=pa->next ; pb=pb->next ; } /*pa, pb分别直接后继结点 */
else /* 系数和不为0，生成的结点插入到结果链表的最后， pa, pb分别直接后继结点 */
{ p=(ploy *)malloc(sizeof(ploy)) ;
p->coef=x ; p->expn=pb->expn ;
p->next=NULL ; /* 生成一个新的结果结点并赋值 */
pc->next=p ; pc=p ;
pa=pa->next ; pb=pb->next ;
} } } /* end of while */
if (pb!=NULL)
while(pb!=NULL)
{ p=(ploy *)malloc(sizeof(ploy)) ;
p->coef=pb->coef ; p->expn=pb->expn ;
p->next=NULL ; /* 生成一个新的结果结点并赋值 */
pc->next=p ; pc=p ; pb=pb->next ;
}
if (pa!=NULL)
while(pa!=NULL)
{ p=(ploy *)malloc(sizeof(ploy)) ;
p->coef=pb->coef ; p->expn=pa->expn ;
p->next=NULL ; /* 生成一个新的结果结点并赋值 */
pc->next=p ; pc=p ; pa=pa->next ;
}
return (Lc) ;
本站文章为和通数据库网友分享或者投稿，欢迎任何形式的转载，但请务必注明出处.
同时文章内容如有侵犯了您的权益，请联系QQ：970679559，我们会在尽快处理。