数据结构之线性结构的离散存储(循环列表和双向链表)

循环列表:

将单链表中 终端节点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。

循环链表解决了一个很麻烦的问题。如何从当中一个结点出发,访问到链表的全部节点。

其实循环链表和单链表的主要差异就在于循环的判断条件上,原来是判断p->next是否为空,现在则是
p->next不等于头结点,则循环未结束。

单链表中,我们有了头结点时,我们可以用0(1)的时间访问第一个结点,但对于要访问最后一个结点,
却需要0(n)时间,因为我们需要将单链表全部扫描一遍。

有没有可能用0(1)的时间由链表指针访问到最后一个结点呢?当然可以

不过我们需要改造一下这个循环链表,不用头指针,而是用指向终端节点的尾指针来表示循环链表,此时
查找开始节点和终端节点都很方便
终端节点用尾指针rear指示,则查找终端节点是0(1),而开始结点,其实就是rear->next->next,其时间复杂度也为0(1)。

将两个循环链表合并成一个表时,有了尾指针非常简单。

rearA->next                                       rearA
rearB->next   rearB->next                         rearB

p = rearA->next ;  //保存A表的头结点
rearA->next = rearB->next->next ; //将本是指向B表的第一个结点(不是头结点)
                                  //赋值给rearA->next
q = rearB->next;
rearB->next = p; //将A表的头结点赋值给rearB->next

free(q);         //释放q


双向链表:

我们在单链表中,有了next指针,这就使我们查找下一结点的时间复杂度为0(1)。可是我们要查找的是上一节点的话,那最坏的时间复杂度就是0(n).因为每次都要从头开始遍历查找。

双向链表是在单链表的每个节点中,再设置一个指向前驱结点的指针域。所以在双向链表中的节点都有两个指针域,一个指向直接后继,另一个指向直接前驱。

//线性表的双向链表存储结构
typedef struct DulNode 
{
     int data;
     struct DulNode *prior;   //直接前驱指针
     struct DulNode *next;    //直接后继指针
}  node;

typedef struct DulNode*  pnode;
既然单链表可以有循环链表,那么双向链表当然也可以是循环表。

由于这是双向链表,那么对于链表中的某一个结点p,它的后继的前驱是谁?当然还是他自己。它的前驱的后继自然也是它自己。

p->next->prior = p = p->prior->next   .. 

在插入和删除时,需要更改两个指针变量。

插入操作时,其实并不复杂,不过顺序很重要,千万不能写反了

我们现在假设存储元素e的节点s,要实现将结点s插入到结点p和p->next之间需要下面几步:

     p                s             p->next
  前驱ai后继       前驱e后继      前驱ai+1后继

顺序是先搞定s的前驱和后继,再搞定后结点的前驱,最后解决前节点的后继
s->prior = p;           //把p赋值给s的前驱
s->next = p->next;      //把p->next赋值给s的后继
p->next->prior = s;     //把s赋值给p->next的前驱
p->next = s;            //把s赋值给p的后继

如果插入操作理解,那么删除操作,就比较简单。
若要删除结点p,只需要下面两步骤:
  p->prior                p                    p->next
   ai-1                    ai                   ai+1

p->prior->next = p->next;     //把p->next赋值给p->prior的后继
p-next->prior = p->prior;     //把p->prior赋值给p->next前驱
free(p);                      //释放节点


总的来说,线性表的这两种结构其实是后面其他数据结构的基础,把他们学明白了,对后面的学习至关重要。
                       线性表
顺序存储结构                            链式存储结构
                      单链表  静态链表  循环链表     双向链表

详细程序见:http://blog.csdn.net/li_101357/article/details/46955945

    原文作者:li_101357
    原文地址: https://blog.csdn.net/li_101357/article/details/46956047
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞