• 双向链表的节点交换

千次阅读 2019-09-19 17:25:28
这两天关于双向链表节点交换,用了很长的时间去学习,理解,敲了好多次,总是达不到效果,就是能想明白,但是在写的时候不是出现这样就是那样的问题,最后参照另外一位CSDN博主的帖子,才写出一个完整的函数, ...
这两天关于双向链表的节点的交换,用了很长的时间去学习,理解,敲了好多次,总是达不到效果,就是能想明白,但是在写的时候不是出现这样就是那样的问题,最后参照另外一位CSDN博主的帖子,才写出一个完整的函数,

贴上代码,以便自己以后随时查看,没有图.

void swap(USERINFO *head,USERINFO *left,USERINFO *right)
{
USERINFO *temp;
if (right->next == NULL) //t结点是否为尾结点
{
if (left->next == right) //p,t结点是否相邻
{
//与尾结点相邻的交换代
right->next = left;
right->pre = left->pre;
left->next = NULL;
left->pre->next = right;
left->pre = right;
}
else
{
//与尾结点不相邻的交换代
right->next = left->next;
right->pre->next = left;
temp = right->pre;
right->pre = left->pre;
left->next->pre = right;
left->next = NULL;
left->pre->next = right;
left->pre = temp;
}
}
else
{
if (left->next == right) //p,t结点是否相邻
{
//相邻的交换代
right->next->pre = left;
temp = right->next;
right->next = left;
right->pre = left->pre;
left->next = temp;
left->pre->next = right;
left->pre = right;
}
else
{
//不相邻的交换代
right->next->pre = left;
temp = right->next;
right->next = left->next;
left->next->pre = right;
left->next = temp;
right->pre->next = left;
temp = right->pre;
right->pre = left->pre;
left->pre->next = right;
left->pre = temp;
}
}
}



展开全文
• 交换index // 更改prev next if (attrFromNode.prev) { attrFromNode.prev.next = targetNode; } if (attrTargetNode.next) { attrTargetNode.next.prev = fromNode; } targetNode.prev =...


switchChainNode(fromNode, targetNode) {
let attrFromNode = {
index: fromNode.index,
prev: fromNode.prev,
next: fromNode.next
};
let attrTargetNode = {
index: targetNode.index,
prev: targetNode.prev,
next: targetNode.next
};

let isSibling = attrTargetNode.prev === fromNode;
// 交换index
// 更改prev next

if (attrFromNode.prev) {
attrFromNode.prev.next = targetNode;
}

if (attrTargetNode.next) {
attrTargetNode.next.prev = fromNode;
}

targetNode.prev = attrFromNode.prev;
fromNode.next = attrTargetNode.next;

if (isSibling) {
targetNode.next = fromNode;
fromNode.prev = targetNode;
} else {
targetNode.next = attrFromNode.next;
fromNode.prev = attrTargetNode.prev;

if (attrTargetNode.prev) {
attrTargetNode.prev.next = fromNode;
}
if (attrFromNode.next) {
attrFromNode.next.prev = targetNode;
}
}

fromNode.index = attrTargetNode.index;
targetNode.index = attrFromNode.index;
}

转载于:https://www.cnblogs.com/vaal-water/p/10245611.html
展开全文
• 双向链表的定义上一节学习了单向链表单链表详解。今天学习双链表。学习之前先对单向链表和双向链表做个回顾。单向链表特点：  1.我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的.   2.只能从头遍历到...
@[TOC]1.双向链表的定义上一节学习了单向链表单链表详解。今天学习双链表。学习之前先对单向链表和双向链表做个回顾。单向链表特点：  1.我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的.   2.只能从头遍历到尾或者从尾遍历到头(一般从头到尾)双向链表特点  1.每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 实现起来要困难一些  2.相对于单向链表, 必然占用内存空间更大一些.  3.既可以从头遍历到尾, 又可以从尾遍历到头双向链表的定义:  双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。下图为双向链表的结构图。  从上中可以看到，双向链表中各节点包含以下 3 部分信息：  指针域：用于指向当前节点的直接前驱节点；  数据域：用于存储数据元素。  指针域：用于指向当前节点的直接后继节点；双向循环链表的定义:  双向链表也可以进行首尾连接，构成双向循环链表,如下图所示在创建链表时，只需要在最后将收尾相连即可(创建链表代码中已经标出)。其他代码稍加改动即可。双链表的节点结构用 C 语言实现为：/*随机数的范围*/#define MAX 100/*节点结构*/typedef struct Node{    struct Node *pre;    int data;    struct Node *next;}Node;2.双向链表的创建  同单链表相比，双链表仅是各节点多了一个用于指向直接前驱的指针域。因此，我们可以在单链表的基础轻松实现对双链表的创建。  需要注意的是，与单链表不同，双链表创建过程中，每创建一个新节点，都要与其前驱节点建立两次联系，分别是：  将新节点的 prior 指针指向直接前驱节点；  将直接前驱节点的 next 指针指向新节点；  这里给出创建双向链表的 C 语言实现代码：Node* CreatList(Node * head,int length){    if (length == 1)    {        return( head = CreatNode(head));    }    else    {        head = CreatNode(head);        Node * list=head;        for (int i=1; ipre=NULL;            body->next=NULL;            body->data=rand()%MAX;            /*直接前趋结点的next指针指向新结点*/            list->next=body;            /*新结点指向直接前趋结点*/            body->pre=list;            /*把body指针给list返回*/            list=list->next;        }    }    /*加上以下两句就是双向循环链表*/    // list->next=head;    // head->prior=list;    return head;}3.双向链表的插入  根据数据添加到双向链表中的位置不同，可细分为以下 3 种情况：1.添加至表头  将新数据元素添加到表头，只需要将该元素与表头元素建立双层逻辑关系即可。  换句话说，假设新元素节点为 temp，表头节点为 head，则需要做以下 2 步操作即可：  temp->next=head; head->prior=temp;  将 head 移至 temp，重新指向新的表头；  将新元素 7 添加至双链表的表头，则实现过程如下图所示：2.添加至表的中间位置  同单链表添加数据类似，双向链表中间位置添加数据需要经过以下 2 个步骤，如下图所示：  新节点先与其直接后继节点建立双层逻辑关系；  新节点的直接前驱节点与之建立双层逻辑关系；3.添加至表尾  与添加到表头是一个道理，实现过程如下：  找到双链表中最后一个节点；  让新节点与最后一个节点进行双层逻辑关系；/*在第add位置的前面插入data节点*/Node * InsertListHead(Node * head,int add,int data){    /*新建数据域为data的结点*/    Node * temp=(Node*)malloc(sizeof(Node));    if(head == NULL)    {        printf("malloc error!");        return NULL;    }        else    {        temp->data=data;        temp->pre=NULL;        temp->next=NULL;     }    /*插入到链表头，要特殊考虑*/    if (add==1)    {        temp->next=head;        head->pre=temp;        head=temp;    }    else    {        Node * body=head;        /*找到要插入位置的前一个结点*/        for (int i=1; inext;        }        /*判断条件为真，说明插入位置为链表尾*/        if (body->next==NULL)        {            body->next=temp;            temp->pre=body;        }        else        {            body->next->pre=temp;            temp->next=body->next;            body->next=temp;            temp->pre=body;        }    }    return head;}c/*在第add位置的后面插入data节点*/Node * InsertListEnd(Node * head,int add,int data){    int i = 1;    /*新建数据域为data的结点*/    Node * temp=(Node*)malloc(sizeof(Node));    temp->data=data;    temp->pre=NULL;    temp->next=NULL;    Node * body=head;    while ((body->next)&&(inext;        i++;    }    /*判断条件为真，说明插入位置为链表尾*/    if (body->next==NULL)    {        body->next=temp;        temp->pre=body;        temp->next=NULL;    }    else    {        temp->next=body->pre->next;        temp->pre=body->pre;        temp->pre=body->pre;        body->pre->next=temp;    }    return head;}4.双向链表的删除  双链表删除结点时，只需遍历链表找到要删除的结点，然后将该节点从表中摘除即可。  例如，删除元素 2 的操作过程如图 所示：Node * DeleteList(Node * head,int data){    Node * temp=head;    /*遍历链表*/    while (temp)    {        /*判断当前结点中数据域和data是否相等，若相等，摘除该结点*/        if (temp->data==data)         {            /*判断是否是头结点*/            if(temp->pre == NULL)            {                head=temp->next;                temp->next = NULL;                free(temp);                return head;            }            /*判断是否是尾节点*/            else if(temp->next == NULL)            {                temp->pre->next=NULL;                free(temp);                return head;            }            else            {                temp->pre->next=temp->next;                temp->next->pre=temp->pre;                free(temp);                return head;               }        }        temp=temp->next;    }    printf("Can not find %d!",data);    return head;}5.双向链表更改节点数据  更改双链表中指定结点数据域的操作是在查找的基础上完成的。实现过程是：通过遍历找到存储有该数据元素的结点，直接更改其数据域即可。/*更新函数，其中，add 表示更改结点在双链表中的位置，newElem 为新数据的值*/Node *ModifyList(Node * p,int add,int newElem){    Node * temp=p;    /*遍历到被删除结点*/    for (int i=1; inext;    }    temp->data=newElem;    return p;}6.双向链表的查找  通常，双向链表同单链表一样，都仅有一个头指针。因此，双链表查找指定元素的实现同单链表类似，都是从表头依次遍历表中元素。/*head为原双链表，elem表示被查找元素*/int FindList(Node * head,int elem){/*新建一个指针t，初始化为头指针 head*/    Node * temp=head;    int i=1;    while (temp)     {        if (temp->data==elem)        {            return i;        }        i++;        temp=temp->next;    }    /*程序执行至此处，表示查找失败*/    return -1;}7.双向链表的打印/*输出链表的功能函数*/void PrintList(Node * head){    Node * temp=head;    while (temp)     {        /*如果该节点无后继节点，说明此节点是链表的最后一个节点*/        if (temp->next==NULL)         {            printf("%d",temp->data);        }        else        {            printf("%d->",temp->data);        }        temp=temp->next;    }}8.测试函数及结果int main() {    Node * head=NULL;    //创建双链表    head=CreatList(head,5);    printf("新创建双链表为");    PrintList(head);    //在表中第 5 的位置插入元素 1    head=InsertListHead(head, 5,1);    printf("在表中第 5 的位置插入元素 1");    PrintList(head);    //在表中第 3 的位置插入元素 7    head=InsertListEnd(head, 3, 7);    printf("在表中第 3 的位置插入元素 7");    PrintList(head);    // //表中删除元素 7    head=DeleteList(head, 7);    printf("表中删除元素 7");    PrintList(head);    printf("元素 1 的位置是：%d",FindList(head,1));    //表中第 3 个节点中的数据改为存储 6    head = ModifyList(head,3,6);    printf("表中第 3 个节点中的数据改为存储6");    PrintList(head);    return 0;}  大家的鼓励是我继续创作的动力，如果觉得写的不错，欢迎关注，点赞，收藏，转发，谢谢！以上代码均为测试后的代码。如有错误和不妥的地方，欢迎指出。部分内容参考网络，如有侵权，请联系删除。
展开全文
• // 双向链表排序.cpp : 定义控制台应用程序的入口点。//#include &ltstdio.h&gt#include &ltstdlib.h&gt#include &ltstring.h&gt#define len sizeof(struct node)struct node{int data;...
// 双向链表排序.cpp : 定义控制台应用程序的入口点。//#include &ltstdio.h&gt#include &ltstdlib.h&gt#include &ltstring.h&gt#define len sizeof(struct node)struct node{int data;struct node *next;struct node *last;};struct list{struct node *head,*tail;int l;};void main(){struct list a;printf("请输入A链表的元素个数\n");scanf("%d",&a.l);int i,x=1;struct node *p1,*p2,*p3;printf("请输入A链表的第1个数据\n");p1=p2=(struct node*)malloc(len);scanf("%d",&p1-&gtdata);a.head=p1;p1-&gtlast=NULL;for(i=2;i&lt=a.l;i++){p2=(struct node*)malloc(len);p1-&gtnext=p2;p2-&gtlast=p1;p1=p2;printf("请输入A链表的第%d个数据\n",i);scanf("%d",&p1-&gtdata);}p1-&gtnext=NULL;a.tail=p1;//链表A生成完毕//for(p2=a.tail;p2-&gtlast-&gtlast;p2=p2-&gtlast)//考虑第一个链点进行交换的情况//{if(p2-&gtdata&ltp2-&gtlast-&gtdata){p3=p2-&gtlast;if(p2-&gtnext){p3-&gtlast-&gtnext=p2;p2-&gtlast=p3-&gtlast;p2-&gtnext-&gtlast=p3;p3-&gtnext=p2-&gtnext;p3-&gtlast=p2;p2-&gtnext=p3;p2=p3;}else{p3-&gtnext=NULL;p2-&gtlast=p3-&gtlast;p3-&gtlast-&gtnext=p2;p2-&gtnext=p3;p3-&gtlast=p2;p2=p3;a.tail=p2;//考虑最后两个链点交换的情况//}}}if(p2-&gtlast-&gtdata&gtp2-&gtdata){p3=p2-&gtlast;p2-&gtlast=NULL;p3-&gtnext=p2-&gtnext;p2-&gtnext-&gtlast=p3;p3-&gtlast=p2;p2-&gtnext=p3;p2=p3;a.head=p2-&gtlast;}p1=a.head;while(p1-&gtnext){for(p2=a.tail;p2-&gtlast!=p1;p2=p2-&gtlast){if(p2-&gtdata&ltp2-&gtlast-&gtdata){p3=p2-&gtlast;if(p2-&gtnext){p3-&gtlast-&gtnext=p2;p2-&gtlast=p3-&gtlast;p2-&gtnext-&gtlast=p3;p3-&gtnext=p2-&gtnext;p3-&gtlast=p2;p2-&gtnext=p3;p2=p3;}else{p3-&gtnext=NULL;p2-&gtlast=p3-&gtlast;p3-&gtlast-&gtnext=p2;p2-&gtnext=p3;p3-&gtlast=p2;p2=p3;a.tail=p2;//考虑最后两个链点交换的情况//}}}p1=p1-&gtnext;}p1=a.head;printf("%d\t",p1-&gtdata);do{p1=p1-&gtnext;printf("%d\t",p1-&gtdata);}while(p1-&gtnext);//新链表输出//}`
展开全文
• 双向链表中的交换节点

千次阅读 2016-03-13 11:26:25
双向链表交换两个节点的值 struct node* temp; //定义一个中间结构体存储q->last和p->next temp->last=q->last; temp->next=p->next; p->next=q->next; q->last->next=p; p->last->next=q; q->next=...
• 双向链表的奇偶节点交换（即1节点和2节点交换，然后3节点和4节点交换） #include < iostream > #include < string > #include < vector > #include < iterator > using namespace std; typedef ...
• 概述：双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我...
• 我们可以分析一下，当删除的是最后一个元素时，直接把最后一个元素置为null，当删除的不是最后一个节点的时候，我们可以把node节点和node.next指针指向的节点交换值，这样子只需要把node的下...
• 插入排序需要从后往前遍历寻找可以插入的位置，所以会使用到双向链表 typedef struct Node//定义的结构体 { int data; struct Node* per; //记录前驱 struct Node* next; }*List; 创建带头节点的双链表 List ...
• 给同学们的C语言课程设计练习作业一下难了不止一个档次，... 而这一切的基础就在于对链表的创建、删除、输出、写入文件、从文件读出......一、链表结构和静态/动态链表二、单链表的建立与遍历三、单链表的插入与删除...
• Java语言高分悬赏：怎么交换双向链表的头节点和第一个元素的节点？卡住了谁来帮我
• 双向链表(3) - 反转双向链表

千次阅读 2015-06-14 00:57:31
实现双向链表的反转。参考下面的例图： (a) 原始双向链表 (b) 已经反转的双向链表 下面是一个用于反转双向链表的简单方法。所需要做的事情就是交换每个节点的前向指针和后向指针，然后调整链表的头指针和尾指针。
• 上次写的一个双向链表有位朋友给我留言说希望能让我帮忙实现连表排序，但是不是值交换而是节点交换，今天终于有时间来分享了，晚了点实在不好意思。上次的文章链表我是用结构体struct封装的，用起来不是很方便，这边...
• 题目：假设有一个双向链表，链表中每个节点定义如下： public class Node { public Node Before; public Node After; public int Content; } 请写出一段逻辑，将已知的两个节点（A节点、B节点）在链表中的位置...
• 分享给大家供大家参考，具体如下：概述：双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点...
• 分享给大家供大家参考，具体如下：概述：双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任 ..本文实例讲述了Java实现双链表互相交换任意两...
• 双向链表反转

千次阅读 2019-06-10 19:10:31
本文中的双向链表，具有一个首指针h，但没有尾指针，不是循环链表。链表反转时，要做两件事情，一是将数据部分的pre指针和next指针交换值；二是将h指针指向反转后的头数据节点指针，并将新链表的尾数据节点指针的...
• 双向链表的C++代码实现(1)数据节点的代码编写(2)迭代器(3)链表初始化(4)获取节点(5)插入和删除节点（6）链表的交换与合并3.完整代码4.简单的测试代码 1.什么是双向链表 这里既然要实现双向链表，就首先要知道双向...
• 一个双向链表排序问题： 题目： 建立一个长度为n的带头结点的双向链表，使得该链表中的数据元素递增有序排列。...第二遍，从最后一个节点开始倒着往前找，找到最小节点min，与第一个节点交换，第二...