精华内容
下载资源
问答
  • 删除结点的(直接)前驱结点,并返回此结点的值
  • 在plist中删除p节点,时间复杂度要求O(1) 算法 因为时间复杂度为O(1),所以常规思路遍历链表是不行的。删除节点,其实是把该节点数据域清除,已知了p节点,那么可以知道它的next节点,所以可以把p节点的下一个节点的...

    题目背景

    在plist中删除p节点,时间复杂度要求O(1)

    算法

    因为时间复杂度为O(1),所以常规思路遍历链表是不行的。删除节点,其实是把该节点数据域清除,已知了p节点,那么可以知道它的next节点,所以可以把p节点的下一个节点的数据域赋值给p节点数据域,再让p节点的next指向p->next->next,就实现了p节点数据域的清除,也就间接删除了p节点。
    如果p是最后一个节点,则只好遍历链表,复杂度O(n)
    只有p是最后一个节点时间复杂度才是O(n),平均时间复杂度(O(1)*(n-1) + O(n))/n = O(1),所以该算法时间复杂度仍为O(1)

    C代码

    bool DeleteP(Linklist plist, Linklist p)//在plist中删除p节点,O(1)
    {
    	assert(plist != NULL);
    	assert(p != NULL);
    	if (plist == NULL || p == NULL)	
    		return false;
    	if (p->next != NULL)//p不是最后一个节点
    	{
    		//把p->next->data的值赋值给p->data,再让p->next指向下下个节点
    		p->data = p->next->data;
    		p->next = p->next->next;
    		free(p->next);
    		return true;
    	}
    	else//p是最后一个节点
    	{
    		LinkList tmp;
    		for (; tmp->next->next != NULL;)
    		{
    			tmp = tmp->next;
    		}
    		tmp->next = NULL;
    		free(tmp->next->next);
    		return true;
    	}
    }
    
    展开全文
  •  算法思想:我们无法得到p所指结点的前驱,但是其后继是知道的,当前结点和后继结点的区别是data的不同,我们可以将p所指向结点的后继的值赋给p所指向的结点,将p所指向结点的后继删除,将该后继的后继地址赋给p的...

    1,算法描述:在无头单链表中,删除指针p所指向的结点

          注意:是没有头结点的。

          算法思想:我们无法得到p所指结点的前驱,但是其后继是知道的,当前结点和后继结点的区别是data的不同,我们可以将p所指向结点的后继的值赋给p所指向的结点,将p所指向结点的后继删除,将该后继的后继地址赋给p的next。即

          q=p->next;

          p->data=q->data;

          p->next=q->next;

          free(q);

          注意这里p所指向的结点不能是最后一个结点,否则直接删除后,其前驱的next域无法置为NULL。

          代码如下:

           

    #include "stdafx.h"
    #include<stdio.h>
    #include <malloc.h>
    #define SIZE  100
    #define  INCREMENT_SIZE 10
    typedef struct  LNode
    {
       int data;
       LNode *next;
    }LNode,*LinkList;
    
    //creat a LinkList
    bool creatLinklist(LinkList&L,int n)
    {
    	LinkList p,q,t,s;
    	L=(LNode*)malloc(n*sizeof(LNode));
    	if(!L)
    		return false;
    	q=L;
    	for(int i=1;i<=n;i++)
    	{
    		p=(LNode*)malloc(sizeof(LNode));
    		scanf("%d",&p->data);
    		L->next=p;
    		L=p;
    	}
    	p->next=NULL;
    	L=q;
    	return true;
    }
    
    //delete a Node in a Linklist without headNode
    bool LinkNoHeadlistDelete(LinkList &p)
    {
    	LinkList q;
    	if(!p)
    		return false;
    	q=p->next;
    	if(q)
    	{
    		p->data=q->data ;
    		p->next=q->next;
    		free(q);
    		return true;
    	}
    }
    
    
    void main()
    {
    	LinkList Llist,p,t;
    	int k;
    	int len;
    	int elemet;
    	int position;
    	printf("input the number of LinkList to be created:");
    	scanf("%d",&k);
    	creatLinklist(Llist,k);
    	printf("\n");
    	t=Llist;
    	for(int i=0;i<k-4;i++)
    		t=t->next;// random a Node
    	LinkNoHeadlistDelete(t);
    	printf("output the new LinkList:\n");
    	p=Llist->next;
    	while(p)
    	{
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    	free(Llist);
    }
    运行结果如下:


    展开全文
  • pointer *p,*q=NULL; p=find(head,i+1); cout<<p->data;... 网上的实现方法都是删除p后继结点,我想直接删除p,按照我的想法上述语句应该是正确的,但是执行时候在q->next=p出显示又断点,怎么破 大神救我
  • 在双向链表存储结构中,删除p所指的结点时需修改指针的操作为 p-&gt;next-&gt;prior=p-&gt;prior; p-&gt;prior-&gt;next=p-&gt;next; p-&gt;next=p-&gt;next-&gt;next;p-&...

    在双向链表存储结构中,删除p所指的结点时需修改指针的操作为
    p->next->prior=p->prior; p->prior->next=p->next;
    p->next=p->next->next;p->next->prior=p;
    p->prior->next=p;p->prior=p->prior->prior;
    p->prior=p->next->next;p->next=p->prior->prior;

    答案:A

    展开全文
  • 一般的思路是要遍历链表找到节点P的前驱节点, 然后再删掉节点P, 但是这样效率不是很高, 可以换个思路, P节点的后继节点是可以在O(1) 复杂度下得到的, 可以将P后继节点的数据复制到P节点中, 然后删掉P后继...

    问题:
    只知道指针P指向一个单向非循环链表的节点,不是头节点也不是尾节点,从链表上把 P指向的节点删除…

    思路:

    一般的思路是要遍历链表找到节点P的前驱节点, 然后再删掉节点P, 但是这样效率不是很高, 可以换个思路, P节点的后继节点是可以在O(1) 复杂度下得到的, 可以将P的后继节点的数据复制到P节点中, 然后删掉P的后继节点, 重新接链即可…

    实现如下:

    temp = p->next;

    p->data = p->next->data;

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

    delete temp;

    或者:

    temp=p->next;

    p->data=temp->data;

    p->next=temp->next;

    delete temp;

    这样就通过复制后面一个节点元素的值和next,然后删除后一个节点的方法,把当前p指向的节点间接地快速删除了

    参考的原文连接:

    http://blog.csdn.net/cnnumen/article/details/5804438

    附加:要在链表中插入节点时,思路很简单,只需要考虑两个问题
    1.要插入的节点的next值是什么?
    2.要插入的节点的前一个节点是谁?也就是,把哪个节点的next值设置为指向当前待插入节点的指针?
    考虑好这两个问题,就能把要插入的节点链接到原来的链表中去了。要注意,一般是先要考虑,先处理待插入节点的next值,否则,可能就会导致它的next值对应的节点的指针找不到了。也就是考虑和处理顺序是先后再前。

    展开全文
  • 在双向链表存储结构中,删除p所指的结点时须修改指针()【MOOC选择题】
  • 删除单链表某个结点

    千次阅读 2015-01-13 16:31:45
    题目:删除带头结点的单链表L中的...现在要求时间复杂度为O(1),因为p不是最后一个结点,知道结点p我们可以删除p后继结点,那么我们可以把p的后继结点元素的值赋给p结点元素的值。 ADT定义如下 #define ElemType int
  • [数据结构]双链表删除结点P的操作

    千次阅读 2014-08-14 15:07:05
    算法的思想就是:把P的前驱
  • ,我们知道单向链表是只能单向遍历,题目中只给我们一个p结点,我们是找不到他的前驱的,我们只能删掉他的后继,那么我们想,将p结点与它的后继数据域的值交换一下,删掉后继,是不是变相的删除p所指的结点。...
  • 二叉排序树删除结点

    2021-06-20 22:28:19
    由于删去叶子结点不破坏整棵树的结构,则可以直接删除此子结点。 若p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点f的左子树(当p是左子树)或右子树(当p是右子树)即可,作此修改也不破坏二叉...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    11. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。( )【上海海运学院 1999 一、1(1分)】 12. 数据结构的基本操作的设置的最重要的准则是,实现应用程序与存储结构的独立。( ) 【华南理工大学 2002...
  • 需要三个指针,pre初始值指向头结点,保持指向为p的前驱结点p指向首元结点,用来遍历整个链表。 q用来做删除结点操作指针 Del_x(Linklist &L,Elemtype x){ Lnode *p=L->next,*pre=L,*q; while(p!=NULL){...
  • 删除单链表某个结点(Java版)

    万次阅读 2015-01-17 09:47:59
    题目:删除带头结点的...现在要求时间复杂度为O(1),因为p不是最后一个结点,知道结点p我们可以删除p后继结点,那么我们可以把p的后继结点元素的值赋给p结点元素的值。 ADT定义: //单链表的结点类 class LNo
  • 单链表

    千次阅读 多人点赞 2019-08-05 15:50:59
    带头结点的单链表,头指针head指向头结点,头结点的值域不包含任何信息,从头结点之后的结点开始存储信息。 头指针head不等于NULL,head->next等于NULL时,链表为空。 单链表结点定义 typedef struct ...
  • 转载一篇写的清晰的文章https://www.cnblogs.com/kubixuesheng/p/4390917.html
  • 删除p指向的结点: 思路: 把p的下个结点内容拷贝到p,然后把删除p的下个结点; /* 考虑的情况: 1. p是空 2.p 指向单链表最后一个结点; 3.p 指向单链表的头结点 */ /* input : P,将要删除结点的指针 output :...
  • 动态链表的删除5.动态链表的插入 一、静态链表 静态链表中,所有结点都是在程序中定义的,不是临时开辟的,也不能用完后释放。 例子: #include <stdio.h> struct student { char *name; float score; ...
  • 链表结点删除

    2018-11-19 20:22:22
    (带删除结点的前驱必须有指针,将带删除结点的前驱与带删除结点后继连起来) 例题:设head指向一个非空单项链表,且数据域的值不重复,在链表中删除关键字值为key的结点。 分析: 第一步:查找值为key的结点...
  • 所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 下面直接上代码 public class DulNode { char data; DulNode next; DulNode prior; int ...
  • 文章目录双链表与循环链表双链表单链表 VS 双链表双链表...要访问某个结点的前驱结点(插入、删除操作时),只能从头开始遍历,访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O(n)。为了克服单链表此缺点,
  • 红黑树

    千次阅读 多人点赞 2019-12-03 16:48:25
    2-3-4 树和红黑树是完全等价的,由于绝大多数编程语言直接实现2-3-4树会非常繁琐,所以一般是通过实现红黑树来实现替代2-3-4树,而红黑树本也同样保证在O(lgn)的时间内完成查找、插入和删除操作。 红黑树是每个节点...
  • 一、二叉排序树的定义 二叉排序树是一棵空树;或者是具有下列性质的二叉树: 1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;...待删除结点记为 p,父结点为f,且p为f的左子树 ...
  • p所指结点的值为x,则删除,并让p指向下个结点,否则让pre和p指针同步后移一个结点。解法二: 采用尾插法建立单链表,用p指针扫描L的所有结点,当其值不为x时将其链接到L之后,否则将其释放。我个人的解法更偏向...
  • p扫描递增单链表,若p所指结点的值域等于后继点的值域,则删除后者。 实现代码如下: #include <stdio.h> #include <malloc.h> typedef int ElemType; typedef struct LNode { ElemType data; ...
  • 第1章第2节练习题5 删除重复结点

    千次阅读 2016-01-11 14:50:42
    在一个递增有序的单链表中,有数据相同的结点存在。试设计一个算法,删除数值相同的结点,使表中不再有重复的结点
  • 文章目录题目描述解题思路算法性能分析 题目描述 假设给定链表1→2→3→4→5→6→7中指向第5个元素的指针,要求把结点5...(2)如果不是最后一个结点,则可以通过把其后继结点的数据复制到当前结点中,然后用删除后继
  • 快速删除p指向的节点...

    千次阅读 2010-08-11 15:42:00
    只知道指针P指向一个单向非循环链表的节点,不是头节点也不是尾节点,从链表上把 P指向的节点删除...   思路: 一般的思路是要遍历链表找到节点P的前驱节点, 然后再删掉节点P, 但是这样效率...
  • 2.9 交换双向循环链表的结点p和它的前驱结点 题目描述: 已知p指向双向循环链表中的一个结点,其结点结构为data,prior,next三个域; 写出算法change(p),交换p所指向的结点及其前驱结点的顺序。 交换算法...
  • 3、如果删除结点有两个孩子结点,则先找到该节点的后继结点后继结点的元素值取代删除结点的元素值,再删除后继结点,并让后继结点的父节点的孩子指针指向后继结点的孩子; */ void DeleteNode(Node* head, Node* ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,679
精华内容 8,671
关键字:

删除p的直接后继结点