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

    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,那么一切又都变化了,所以重在理解吧。

     

    展开全文
  • 关于双向链表插入节点的问题

    千次阅读 2012-09-05 10:38:12
    Status ListInsert(DuLinkList L, int i, ElemType e) {  DuLinkList p;  DuLNode *s; //定义一个链表节点指针  if (i ListLength(L) + 1)  return ERROR;  p = GetElemP(L
    Status ListInsert(DuLinkList L, int i, ElemType e)
    {
            DuLinkList p;
            DuLNode *s; //定义一个链表节点指针
            if (i < 1 || i > ListLength(L) + 1)
                    return ERROR;
            p = GetElemP(L, i-1);//得到位置i-1处节点的地址
            s -> data = e;
            s -> next = p -> next;
            p -> next -> prior = s;
            p -> next = s;
            s -> prior = p;
            return OK; 

    }

    这样写出来的函数可以成功对双向链表进行插入嘛?需要对s使用malloc函数进行开辟空间吗?
     其实我以前一直不明白,定义了一个DuLNode*s,指针,那么它本身就有存放的地址,为什么还要再开辟空间 s=(LinkList)malloc(sizeof(LNode)),将开辟空间的地址给他。

    经过调试发现,DuLNode *s定义的指针,地址为0x8049a7c(这个地址在栈里面),L地址为0x804a008(这个地址在堆里面)。
     插入第一个节点,发现没问题,ListInsert函数返回时,0x8048a7c也可以访问,里面放的data也是1,可是第二 次再调用的时候,又定义了一个DuLNode *s,栈的地址在第一次返回时相当于已经收回,这次调用该函数,系统认为那个地址没用了,可以继续申请,所以申请的地址还是0x8049a7c(每次编译时候该地址会变,但是,和第一次调用ListInsert函数时候地址是一样的),再向该data里面写入数据时,就会把第一次写的数据覆盖也就是说,这个链表每次插入就都只有两个节点,以后定义的s也都是0x8049a7c这个地址。
                    所以,要使用malloc这个函数,他调用后,会在堆区申请块空间,改空间跟栈不同,不会在函数调用返回后释放,直到free函数,才会释放这个空间。 那么每次调用插入函数,都会在堆区申请一个空间,那么最后链表也在堆区里面放着。如果像前面那样,不用malloc函数,就好比表头在堆区里面放着,然后第一个节点在栈区,以后开辟的节点也就是第一节点的地址。

    展开全文
  • Attention: 当删除的是最后一个节点时,

    Attention:

    当删除的是倒数第二个节点,仅剩Pm时,Pm->pos=pm->pre=pm ;指向的都是孤立的最后一个节点;

    当删除的是最后一个节点时,返回NULL;

    当删除的是 其余节点时,返回的是被删除节点的PRE节点。并做好双向指针设置。


    打印节点、寻找节点时,均要保存head节点,防止陷入查找死循环。

    //双向链表,删除节点,插入节点
    #include <stdio.h>
    # include<malloc.h>
    #include <conio.h>
    
    
     typedef struct BiListNode{
    	int element;
    	BiListNode* Pre;//指向前节点
    	BiListNode* Pos;//指向后节点
    
    }node;
    
     int  insertNode(node* L,int m,int n);
     node* findNode(node* L,int m);
     node* deleteNode(node*L,int m);
     void PrintList(node*L);
    
    
    int  insertNode(node* L,int m,int n){//在双向链表的m节点后插入n值节点,若无m节点,则在头节点处插入,
    	if (L->element==NULL)
    	{
    		L->element=n;//插入第一个node
    		L->Pos=L->Pre=L;//第一个node的前向后向指针均指向自己
    
    	} 
    	else
    	{   node* Pn=(node*)malloc(sizeof(node));
    	    Pn->element=n;
    		node* POS=findNode(L,m);//寻找m所在的节点位置
    		if(!POS) //未找到m节点,直接插入到头节点后面
    		{
    			POS=L;
    		}
    		//找到m节点
    		
             node* Ppos=POS->Pos;//m的原始后向节点
    		 POS->Pos=Pn;
    		 Pn->Pre=POS;
             Pn->Pos=Ppos;//n指向m的原始后向节点
    		 Ppos->Pre=Pn;
    	}
    	return 1;//插入成功 返回1
    
     }
    node* findNode(node* L,int m){//找到m,返回m所在的&node,否则返回Null
    	node* head=L;//保存头节点的位置,防止无限循环查找
    	if (!L)
    	{
    		printf("null! The LIST is EMPTY!");
    		return NULL;
    	}
    	if (L->element==m)
    	{
    		return L;
    	} 
    	else
    	{
    		L=L->Pos;
    		while(L->element!=m && L!=head){
    			L=L->Pos;
    		}
    		if (L==head)//遍历所有节点,无m
    		{
    			return NULL;
    		} 
    		if(L->element==m)//Binggo! 找到m
    		{
    			return L;
    		}
    		
    
    	}
    	
    
    
    
    }
    node* deleteNode(node*L,int m){//找到元素m所在的节点,并删除
    node* Pm=findNode(L,m);
    
    if (!Pm)//POS==NULL,不存在m
    {
    	printf("Lucky! NO number%d !\n",m);
    	return L;
    	
    } 
    else
    {   
    	node* PRE=Pm->Pre;
    	node* POS=Pm->Pos;
    	if(PRE==POS)
    	{   if (PRE==Pm)//删除的是最后一个节点
    	{
    		free(Pm);
    		printf("Delete %d succesfully!\n",m);
    		printf("the last number in list!\n");
    		return NULL;
    
    	} 
    	else//删除的是倒数第二个元素
    	{
    		free(Pm);
    		printf("Delete %d succesfully!\n",m);
    		PRE->Pos=POS->Pre=PRE;
    		return PRE;
    
    	}
    		
    	}
    	else{
    		PRE->Pos=POS;
    		POS->Pre=PRE;
    		free(Pm);
    		printf("Delete %d succesfully!\n",m);
    		return PRE;
    	}
    	
    	
    }
    
    
    }
    
    void PrintList(node*L){
    	node* head=L;//保存入口节点,防止打印陷入死循环
    	int flag=1;
    	printf("the numbers in the bidirection List:\n");
    	if(!L)
    		printf("EMPTY list!\n");
    	while (L && flag)
    	{
    		printf("%6d",L->element);
    		L=L->Pos;
    		flag=(L!=head);
    	}
    }
    
    
    int main(){
       node* First=(node*)malloc(sizeof(node));//第一个node
       First->element=NULL;
       First->Pos=First->Pre=NULL;//空节点内容都为NULL;
       printf("Hello,buddy!\n Please input a number:\n ");
       int m=NULL,n=NULL;
       while (scanf("%d",&n))
       {
         if(insertNode(First,m,n))
    	 {	m=n;}
    	 else
    	 {
    		 printf("Oops! Insert Failed!\n");
    		 break;
    	 }    
       }
       while (int c=getchar()!='\n')
       {
        printf("%c %d",c,c);
       }
       /************delete**************/
       printf("buddy! input the number to be deleted:\n ");
       while (scanf("%d",&m))
       {
    	   First=deleteNode(First,m);
    	   
       }
       /********** Print List  **************/
       PrintList(First);
       getch();
    }
    



    展开全文
  • 双向链表——有序双向链表插入节点

    双向链表——有序双向链表中插入节点


    双向链表——有序双向链表中插入节点

    #include<iostream>
    using namespace std;
    struct node       //node结构体,里面有两个个node指针,用来指向上/下一个node对象
    {
    	int x;
    	node *left;   //指向什么类型的对象,就用什么类型的指针
    	node *right;
    };
    
    node* create(int n)         //创建链表,参数n表示结点的个数,返回类型是结点指针node*
    {
    	if(n<1)                 //参数检测,链表最少有一个节点
    	{
    		cout<<"error input n!"<<endl;	
    		exit(0);
    	}
    	
    	node *head=new node;    //建立头结点
    	node *p=head;           //创建用于往后指的node指针
    
    
    	for(int i=1;i<=n;i++)
    	{
    		node *temp=new node;      //new一个node指针
    		temp->x=rand()%100;
    		p->right=temp;            //将p的right指向创建的temp,把新节点连接到链表后面
    		temp->left=p;             //temp的left指向p,新节点left指向上一个节点
    		p=temp;                   //将p指向新结点temp,即p移动到下一个节点
    	}
    
    	p->right=NULL;                //创建完成后,p->right为空,最后一个节点的right位null
    	head->right->left=NULL;       //创建完成后,第一个节点的left为null
    
    	return head;
    }
    
    void display(node *head)         //输出链表
    {
    	node *p;
    	p=head->right;               //p重新指向头结点后的那个结点,即for循环创建的第一个结点
    	if(p==NULL)
    		cout<<"NULL List";
    	while(p!=NULL)               //输出
    	{
    		cout<<p->x<<"  ";
    		p=p->right;
    	}
    	cout<<endl;
    }
    
    void sort(node *head)
    {
    	node *p,*s;
    	p=head->right;               //p重新指向头结点后的那个结点,即for循环创建的第一个节点
    	int temp;                    //用于交换的临时变量
    	while(p)                     //外循环从头结节后的第一个节点开始
    	{	
    		s=p->right;              //内循环从p的后一个结点开始
    		while(s)
    		{
    			if(p->x > s->x)      //只交换结点里面的x,结点不动
    			{
    				temp=p->x;
    				p->x=s->x;
    				s->x=temp;
    	
    			}
    
    
    			s=s->right;          //内循环后移
    		}
    		
    		p=p->right;              //外循环后移
    	}
    
    }
    
    void insert(node *head, int n)     //直接将数n插入到链表head的适当位置
    {
    	node *p,*s;
    	p=head;                        //p重新指向头结点后的那个结点,即for循环创建的第一个节点
    	
    	while(p->right)
    	{
    		if(p->right->x > n)        //在有序列表中找到第一个比n大的节点,在它前面插入就行
    		{	
    			node *temp=new node;
    			temp->x=n;
    
    
    			s=p->right;           //用于反向连接的临时node指针s
    
    
    			temp->right=p->right;
    			p->right=temp;        //插入适当位置,正向连接链表
    			
    			s->left=temp;         //反向连接链表
    			temp->left=p;
    
    
    			break;
    			
    		}
    		p=p->right;
    
    	}
    
    
    	if(p->right==NULL)            //如果链表最后一个数还比n小,则直接放在链表最后
    	{
    		node *temp=new node;
    		temp->x=n;
    
    		p->right=temp;            //连接上新来的最后一个节点
    		temp->right=NULL;         //right指针为null
    		temp->left=p;             //反向连接
    	}
    
    }
    
    void insert1(node *head, int n)    //既然有排序,就直接将插入的节点连接到第一个节点,然后排序
    {
    
    
    	node *s,*p=head;                        //p重新指向头结点后的那个结点,即for循环创建的第一个节点
    	node *t=new node;
    	t->x=n;
    
    
    	s=p->right;        //用于反向连接的临时node指针s
    
    
    	t->right=p->right; //插入适当位置,正向连接链表
    	p->right=t;       
    			
    	s->left=t;         //反向连接链表
    	t->left=p;
    
    
    	sort(head);        //借助上面的排序
    
    
    }
    
    
    int main()
    {
    	node *list; 
    	list=create(10);      //建立链表
    	display(list);        //输出显示建立的链表,这里是讯链表,不用输出
    	
    	sort(list);           //排序,称为有序列表
    	display(list);        //显示排序后的链表
     
    	insert(list,-2);      //在有序列表中插入
    	display(list);        //显示有序列表插入后的链表
    
    
    	insert1(list,99);     //在有序列表中插入
    	display(list);        //显示有序列表插入后的链表
    
    	return 0;
    }


    展开全文
  • #include<cstdio> #include<cstdlib> typedef struct DoubleLinkedList { int data; struct DoubleLinkedList *pre; struct DoubleLinkedList *next; }DlinkedList_Node;...//建立链表 D...
  • 双向链表节点插入和删除

    千次阅读 2019-04-26 00:49:33
    //跳过头节点的0 while(tmp) { if(tmp->val == num) { del_node = tmp; break; } tmp = tmp->next; } del_node->next->pre = del_node->pre; del_node->pre->next = del_node->next; free(del...
  • 双向链表——插入、删除指定位置和相同节点
  • 双向链表:每一个节点前后指针域都和它的上一个节点互相指向,尾节点的next指向空,首节点的pre指向空。 二、使用 注:跟单链表差不多,简单写常用的。循环链表无法形象化打印,后面也暂不实现了,但是要注意循环...
  • 双向链表插入与删除(c++实现)

    千次阅读 2020-04-30 16:28:13
    目录前言双向链表插入节点实现代码双向链表删除节点实现代码整个项目的完整代码运行截图总结 前言 本篇文章主要接着上文的双向链表的创建与遍历(c++实现) ...
  • 双向链表 在单链表的基础上增加了前缀结点,一定程度上提升了查找元素的速度 在查找元素时,可以反向查找前缀结点 插入结点过程(分为4步) 这四个步骤的顺序可调整,但是必须要保证需要的链不断!!...
  • 不得不说 加上头结点的链表 确实方便! #ifndef DLIST_H_INCLUDED #define DLIST_H_INCLUDED typedef int ElemType; struct node {  ElemType data;  struct node*prior;  struct node*next;...
  • 指定位置插入节点 先找到要插入的位置(通过节点的属性,比如id或者有序数字) 与单链表不同的时候插入后,next 和 pre 都要与前后节点相连 // 按排序插入节点 public void addByOrder(Node2 node) { // 头节点...
  • 双向链表的增删改查思路代码实现 思路 代码实现 import java.util.Scanner; public class DoubleLinkedListDemo { public static void main(String[] args) { DoubleLinkedList doubleLinkedList = new ...
  • 双向链表节点删除

    2014-09-07 12:49:54
    void ddeletenode(dlistnode*p)  {  p–>prior–>next=p–>next;... 注意:与单链表的插入和删除操作不同的是,在双链表插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为O(1)。
  • 写一个函数insert,用来向一个动态链表插入节点。 方法一: #include <stdio.h> #include <stdlib.h> struct Student { //声明结构体(双向链表结构体) int num; float score; struct Student *...
  • 双向链表插入与删除节点

    千次阅读 2017-05-20 13:58:27
    typedef struct linknode//定义双向链表 { int data; linknode *prior,*next; } Node,*Linklist; Linklist Createlist(int n);//建立双向链表 void Addnode(Linklist L,int i,int x);//向链表中的第i个位置
  • 双向链表(1) - 基本介绍以及插入节点
  • C语言-双向链表

    2021-06-16 10:35:21
    双向链表插入节点: 使用双向链表对数据进行“增删查改”的完整操作代码: 双向链表及其创建、双向链表基本操作 可以看出,双向链表中各节点包括: ① 指针域:指向当前节点的直接前驱(前一个)节点; ② ...
  • 数据结构-编程实现一个双向链表节点插入 1:这里分为两种插入情况:一种是 插入位置在中间,另一种是插入位置在末尾。两种情况有一点不同:插入位置在中间时需要把p的原后继节点的前驱指针指向新插入节点。 ...
  • 插入排序需要从后往前遍历寻找可以插入的位置,所以会使用到双向链表 typedef struct Node//定义的结构体 { int data; struct Node* per; //记录前驱 struct Node* next; }*List; 创建带头节点的双链表 List ...
  • 双向链表的查找、删除、插入节点

    千次阅读 2018-06-21 00:04:47
    双向链表插入无需定位到节点的前一位,因为其本身有prior指针。从根本上来讲,它和单链表是类似的:#include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; typedef struct student { int num; ...
  • 要求是创建一个双向链表,并插入数据,之后查找制定数据并删除。但是,程序虽然编译通过却不能正常运行
  • java建立双向链表插入结点,删除节点
  • struct ListNode { int val; ListNode *pre; ListNode *next; //ListNode(int _val):val(_val), next(nullptr), random(nullptr){} } void insert(ListNode* head,int v) ... ListNode* node=new ListNode;...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,885
精华内容 754
关键字:

双向链表插入节点