Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
30 lines (20 sloc) 1.35 KB

循环链表

单向循环链表 - cricular linked list

  1. 单向循环链表与单链表的区别就是单向循环链表的终端结点的指针端由空改为了指向头结点,从而使整个单链表形成了一个环。

  2. 但书中对单向循环链表的应用阐述的不清,在分析过约瑟夫环问题后发现单向循环链表在实际应用中不带头结点更为实用,因为这样才能实现循环,如果有头指针且不做循环到头指针时继续循环的操作的话,只要循环到头指针时循环就会停止,这样和单链表就没有区别了,也没有实现从任意一点循环整个链表。而不带头指针的情况下在任意一点都可以循环整个链表,这时之用在循环体中加入跳出循环的判断就行了。

  3. 不带头结点的单向循环链表用rear-next表示第一个数据元素的节点,用rear表示终端结点。

双向循环链表 - double linked list

  1. 双向循环链表在数据存储结构中加入了一个指向直接前驱的指针域。

  2. 一般带有头结点。

  3. 在插入和删除节点时需要对前驱结点指针域和后继结点指针域进行操作,操作顺序及其重要:

//插入 s 结点
s->prior = p;
s->next  = p->next;
p->next->prior = s;
p->next  = s;

//删除 p 结点
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
You can’t perform that action at this time.