双向链表和循环链表

冷不防 2022-06-08 03:05 306阅读 0赞

一、双向链表

每个结点有两个指针域和若干数据域，其中一个指针域指向它的前趋结点，一个指向它的后继结点。它的优点是访问、插入、删除更方便，速度也快了。但“是以空间换时间”。

【数据结构的定义】 

  1. struct node{
  2.     int data;
  3.     node *pre,*next;//pre指向前趋，next指向后继 
  4. };
  5. node *head,*p,*q,*r;

20170912234055181

  1. void insert(node *head,int i,int x)//在双向链表的第i个结点之前插入x
  2. {
  3.     node *s,*p;
  4.     int j;
  5.     s=new node;
  6.     s->data=x;
  7.     p=head;
  8.     j=0;
  9.     while((p->next!=NULL)&&(j<i))//最终p指向第i个结点 
  10.     {
  11.         p=p->next; 
  12.         j=j+1;
  13.     }
  14.     if(p=NULL)
  15.     {
  16.         cout<<"no this position!";
  17.     } 
  18.     else
  19.     {
  20.         s->pre=p->pre;//将s的前驱指向p个前驱
  21.         p->pre->next=s;//将p的本来前驱结点的后继指向s 
  22.         s->next=p;//将s的后继指向p
  23.         p->pre=s;//将s的前驱指向p的前驱
  24.     }
  25. }

20170913000021920

二、循环链表

单向循环链表：最后一个结点的指针指向头结点。如下图：

20170913001605723

双向循环链表：最后一个结点的指针指向头结点，且头结点的前趋指向最后一个结点。如下图：

20170913001801948

发表评论

表情：
评论列表 （有 0 条评论，306人围观）

还没有评论，来说两句吧...

相关阅读

    相关 循环链表及双向链表

    一、循环链表 循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。

    叁歲伎倆叁歲伎倆/ 0 赞/ 160 阅读

    相关 双向链表和循环链表

    一、双向链表 每个结点有两个指针域和若干数据域，其中一个指针域指向它的前趋结点，一个指向它的后继结点。它的优点是访问、插入、删除更方便，速度也快了。但“是以空间换时间”。

    冷不防冷不防/ 0 赞/ 307 阅读

    相关 双向链表与循环链表

    双向链表 单链表的一个优点是结构简单，但是它也有一个缺点，即在单链表中只能通过一个结点的引用访问其后续结点，而无法直接访问其前驱结点， 要在单链表中找到某个结点的前驱结点

    古城微笑少年丶古城微笑少年丶/ 0 赞/ 355 阅读