精华内容
下载资源
问答
  • 双向链表插入节点

    2017-09-12 23:15:00
    双向链表插入节点 1、根据实例分析 2、把节点之间的关系看成 是边的拆除和重建 3、为了方便叙述,给边标了号 如图所示是我们要操作的结构体和在双向链表的图。 现在我们的目的就是在ab节点之间插入x节点。 ...

    双向链表插入节点

    1、根据实例分析

    2、把节点之间的关系看成 是边的拆除和重建

    3、为了方便叙述,给边标了号

    如图所示是我们要操作的结构体和在双向链表的图。

    现在我们的目的就是在ab节点之间插入x节点。

    现在我把这六条线都遍上号:

    在插入之前,2,6这两条边是存在的,这两条边就是:

     

    在插入之后,2,6这两条边不存在了,存在的边为4,1,3,5,这四条边就是:

     

    所以要想实现在a,b节点中插入x节点,也就是实现

     

     

    在这个图中,1和6是同一条边,都是a->next,3和2是同一条边,都是b->pre.

     

    现在我们是通过p指针在这个双休链表中找到了b节点,也就是p==b的,并且我们有一个x节点是待插入的。

    在这种情况下,我们找a节点就只能通过p节点,p->pre就代表a。

    显然2这条边就是p->pre,所以我们要想找到a节点,就必须有2这条边。

    而1,4两条边的操作都和a节点有关。

    所以我们要想操作1,4两条边,就必须有a节点,也就是2这条边。

    5这条边的插入顺序很自由,因为我们的x节点和p节点都是已知的。

    所以我们的一个插入顺序为这样:

    1、先拆第6条边,接上第一条边:

    2、然后接上第4条边:

    3、然后接上第5条边:

    4、最后拆除第二条边接上第三条边:

     

     大工告成。

    说一句,这个循序不是唯一的,比如说5这条边我可以在任意时候插入。

    并且如果p节点现在不是指向b,而是指向a,那么一切又都变化了,所以重在理解吧。

     

    展开全文
  • 本文将详细介绍建立双向链表,实现对双向链表插入,删除操作,需要了解的朋友可以参考下
  • 双向链表插入删除

    2013-05-09 20:39:13
    双向链表的建立、查找、插入、删除,是理想的学习资料,快来下载
  • 原文地址:双向链表插入、删除操作作者:joyes414来源:http://blog.csdn.net/csdanca11/article/details/7173856   双向链表 循环单链表的出现,虽然能够实现从任一结点出发沿着链能找到其前驱结点,但时间耗费是O...

    来源:http://blog.csdn.net/csdanca11/article/details/7173856

     

    双向链表

    循环单链表的出现,虽然能够实现从任一结点出发沿着链能找到其前驱结点,但时间耗费是On)。如果希望从表中快速确定某一个结点的前驱,另一个解决方法就是在单链表的每个结点里再增加一个指向其前驱的指针域prior。这样形成的链表中就有两条方向不同的链,我们可称之为双(向)链表(DoubleLinked List)。双链表的结构定义如下:

    typedef structDNode

    {

    ElemType data;

    struct DNode*prior,*next;

    }DNode,*DoubleList;

    双链表的结点结构如图2.14所示。

    与单链表类似,双链表一般也是有头指针唯一确定的,增加头结点也能使双链表的某些运算变得方便。同时双向链表也可以有循环表,称为双向循环链表,其结构如图2.15所示。

    由于在双向链表中既有前向链又有后向链,寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。设指针p指向双链表中某一结点,则有下式成立:

    P->prior->next=p=p->next->prior

    在双向链表中,那些只涉及后继指针的算法,如求表长度、取元素、元素定位等,与单链表中相应的算法相同,但对于前插和删除操作则涉及到前驱和后继两个方向的指针变化,因此与单链表中的算法不同。

    1.双向链表的前插操作

    算法描述:欲在双向链表第i个结点之前插入一个新的结点,则指针的变化情况如图2.16所示。

    intDlinkIns(DoubleList L,int i,ElemType e)

    {

    DNode *s,*p;

    s=(DNode*)malloc(sizeof(DNode));

    if(s)

    {

    s->data=e;

    s->prior=p->prior;p->prior->next=s;

    s->next=p;p->prior=s;

    return TRUE;

    }

    else

    teturn fALSE;

    }

    算法双向链表的插入操作

    2.双向链表的删除操作

    算法描述:欲删除双向链表中的第i个结点,则指针的变化情况如图2.17所示。

    intDlinkDel(DoubleList L,int i,ElemType *e)

    {

    DNode *p;

    *e=p->prior->next=p->next;

    p->next->prior->p=p->prior;

    free(p);

    return TRUE;

    }

    展开全文
  • 双向链表插入结点的理解。

    千次阅读 2017-06-06 20:22:49
    这几天集中时间看了下单双链表的内容,发现双向链表插入很难理解,今天恍然大悟,最重要的部分就是如何使得你的代码跟你的作图能够吻合起来,这样就不用死记硬背。 下图为双向链表插入,知乎里偶然看见的一张...

    这几天集中时间看了下单双链表的内容,发现双向链表的插入很难理解,今天恍然大悟,最重要的部分就是如何使得你的代码跟你的作图能够吻合起来,这样就不用死记硬背。

     

    下图为双向链表的插入,知乎里偶然看见的一张图,这几步操作也非常明了,只是我图中画的不是很准,我都用红色箭头做了修改,这样就一目了然了。

    总体来讲,要将s结点嵌入到双向链表中,需要切断并重新连接两根线,还要再额外连两根线,看图四,非常明显总共动了4根线,所以用了4条语句来做插入

    1. s->next=p->next

    这边p->next其实就是后面一个节点x,而不是x->pre,但图画的感觉像x-pre

    2. s->prior=p

    这步没什么问题

    3. p->next=s

    箭头也画的不好,画的像s->pre,其实是s

    4. s->next->prior=s

    s->next其实就是后面的一个节点x,所以就是x->prior连接了s

     

    所以做完第三四步之后,就看到s和p连接上了,s和x也连上了。

     

    展开全文
  • function Node(value) { this.value = value; this.prev = null; this.next = null; return this; } ...function List() { this.head = new Node(null);... this.insert = function(index, node...
    
    function Node(value) {
        this.value = value;
        this.prev = null;
        this.next = null;
        return this;
    }
    
    function List() {
        this.head = new Node(null);
        this.insert = function(index, node) {
            let pNode = this.find(index);
            let nNode = pNode.next;
            pNode.next = node;
            node.next = nNode;
            node.prev = pNode;
            nNode.prev = node;
        }
        this.find = function(index) {
            let node = this.head;
            while(--index) {
                node = node.next
            }
            return node;
        }
        this.append = function(node) {
            let lastNode = this.head
            while(lastNode.next != null ) {
                lastNode = lastNode.next
            }
            node.prev = lastNode
            lastNode.next = node;
            
        }
    
        return this;
    }
    
    let list = new List();
    let N1 = new Node(1);
    let N2 = new Node(2);
    let N3 = new Node(3);
    let N4 = new Node(4);
    let N5 = new Node(5);
    let N6 = new Node(6);
    
    list.append(N1);
    list.append(N2);
    list.append(N3);
    list.append(N4);
    list.append(N5);
    list.append(N6);
    
    list.insert(1,new Node(7))
    
    console.log(list.find(2))
    
    
    展开全文
  • 看到一道面试题: typedef struct node { int value; struct node* next;...//实现有序双向链表插入和删除 int insert1(S_LIST_NODE* _list, int value); int delete1(S_LIST_NODE* _list, int value...
  • 双向链表插入与删除

    2014-08-27 10:59:31
    #include #include #include typedef struct node { int data; struct node *pre; struct node *next;... 双向链表删除结点 */ dnode *Del_Node(dnode *Head, int num) { dnode *p1,*p2; p1 = Head; /
  • 双向链表——插入、删除指定位置和相同节点
  • 双向链表是在单链表的基础上添加了前驱指针域。 其中,双向链表的插入以及反置是最常见的操作,也是程序员面试过程经常遇到的。 下面是我实现的过程,有其他好的想法请不吝赐教。 1 链表反置: ...2 链表插入
  • 分为正向序号插入数值和逆向序号插入数值 正向code: #include #include using namespace std; typedef struct Dulnode { int data; struct Dulnode *prior,*next; }DulNode; DulNode *Input(int n...
  • 双向链表 在单链表的基础上增加了前缀结点,一定程度上提升了查找元素的速度 在查找元素时,可以反向查找前缀结点 插入结点过程(分为4步) 这四个步骤的顺序可调整,但是必须要保证需要的链不断!!...
  • 目录1.插入 1.插入
  • 双向链表插入排序

    千次阅读 2012-12-08 15:46:59
    /* * func.c * * Created on: 2012-12-5 * Author: Administrator */ #include "head.h" void Initialize(pList p) { p->head=NULL;... puts("插入失败"); return 0; } void modify() { }
  • 1、在p节点之前插入q节点(在脑海中构建下面这样一副图片) p->prio p q 先建立p->prio和插入节点q的关系,然后就能够顺利进行插入操作了 p->prio->next = q; /* 先建立p->prio和插入节点q的...
  • /*头插法创建双向链表*/ void Create ( pDoubleLink L , int n ) { int i , data ; pDoubleLink p ; printf ( "输入创建链表各元素的值:\n" ) ; for ( i = 0 ; i < n ; i ++ ) { ...
  • 带模板双向链表插入

    2014-06-21 11:54:07
    #include template struct DLNode { T data; DLNode<T> *prior,*next; }; template class DLinkList ...cout在L的表尾依次插入1~5后,L="; L.ListTraverse(print); return 0; }

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,627
精华内容 2,650
关键字:

双向链表插入