精华内容
下载资源
问答
  • 删除单链表第i个节点

    千次阅读 2019-01-06 17:53:14
    单链表的删除操作是将单链表的第i个节点删去。具体步骤如下:  (1)找到节点ai-1的存储位置p,因为在单链表中节点ai的存储地址是在其直接前趋节点ai-1的指针域next中;  (2)令p->next指向ai的直接后继...

    单链表的删除操作是将单链表的第i个节点删去。具体步骤如下: 
    (1)找到节点ai-1的存储位置p,因为在单链表中节点ai的存储地址是在其直接前趋节点ai-1的指针域next中; 
    (2)令p->next指向ai的直接后继节点ai+1; 
    (3)释放节点ai的空间; 

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
    {
        int data;
        struct node *next;
    } NODE;
    
    
    // 尾插法创建单链表(带头节点)
    NODE *createEnd(int arr[], int len)
    {
        NODE *head = (NODE *)malloc(sizeof(NODE)); // 生成头节点
        head->next = NULL;
        NODE *end = head;  // 尾指针初始化
    
        for (int i = 0; i < len; i++) {
    
            NODE *p = (NODE *)malloc(sizeof(NODE)); // 为每个数组元素建立一个节点
            p->data = arr[i];
            end->next = p;  // 将节点p插入到终端节点之后
            end = p;
        }
    
        end->next = NULL;  // 单链表建立完毕,将终端节点的指针域置空
    
        return head;
    }
    
    
    // 删除单链表中第i个节点
    NODE *delete(NODE *head, int i)
    {
        NODE *p = head;
    
        int j = 1;
        while (p->next && j < i) {
            p = p->next;
            ++j;
        }
    
        if (p->next == NULL || j > i) { // 经过循环,若最终p为空,或i为0或负数时,都说明位置不合理;
            printf("Position Error\n");
            return 0;
        }
    
    
        NODE *temp = p->next;
        p->next = temp->next;
    
        free(p);
    
        return head;
    }
    // 注: (1)设单链表的长度为n,则单链表删除第i个节点时,必须保证 1<= i <= n,否则不合法;
    //     (2)当 i=n+1 时,虽然被删除节点不存在,但其前趋节点却存在,它是终端节点;所以,被删节点的直接前趋*p存在,并不意味着被删节点就一定存在,仅当*p存在(即p != NULL)且*p不是终端节点(即p->next != NULL)同时满足 j <= i时,才能确定被删节点存在。此时,算法的时间复杂度是O(n)。
    
    
    // 单链表打印
    void print(NODE *head)
    {
        if (head == NULL) return;
    
        NODE *p = head->next;
        while (p != NULL) {
            printf("%d\n", p->data);
            p = p->next;
        }
    }
    
    int main(void)
    {
        int arr[] = {1,2,3,4,5,6,7};
        int len = sizeof(arr)/sizeof(int);
    
        NODE *head = createEnd(arr, len);
    
        // 删除前
        print(head);
    
    
        delete(head, 5);
        // 删除后
        print(head);
    
        return 0;
    }
    

     

    展开全文
  • 如何删除单链表第i个节点? 先来看看删除原理:因为数据结构是单链表,要想删除第i个节点,就要找到第i个节点;要想找到第i个节点,就要找到第i-1个节点;要想找到第i-1个节点,就要找到第i-2个节点......于是...

    如何删除单链表中第i个节点?

    先来看看删除的原理:因为数据结构是单链表,要想删除第i个节点,就要找到第i个节点;要想找到第i个节点,就要找到第i-1个节点;要想找到第i-1个节点,就要找到第i-2个节点......于是就要从第一个节点开始找起,一直找到第i-1个节点。如何找?让一个指针从头结点开始移动,一直移动到第i-1个节点为止。这个过程中可以用一个变量j从0开始计数,一直自增到i-1。


    之后呢?我们把第i-1个节点找到了,就让它的指针域指向第i+1个节点,这样就达到了删除的目的。而第i+1个节点的地址又从第i个节点获得,第i个节点的地址又是第i-1个节点的后继。因此我们可以这样做:先让一个指针指向第i-1个节点的后继,(保存i+1节点的地址),再让i-1节点的后继指向第i个节点的后继,这样就将第i个节点删除了。

    再来看看删除的时候会遇到什么意外情况:
    1.有可能单链表一开始就为空。这样的话连第i-1个元素都找不到。


    2.有可能找不到第i个节点,原因是第i-1的后继为空。

    3.有可能删除的位置不合理,比如删除第-1个节点。



    如何删除单链表中数据域为x的前驱节点?

    这个删除操作其实和上面的类似。关键是要知道三个地址,p->第i-2个节点的地址,q->第i-1个节点的地址,r->元素为x的第i个节点的地址。(为什么?因为我们要删除的是第i-1个节点。要想删除它,就既要找到第i-2个节点,又要找到元素为x的第i个节点)


    假设三个指针,p,q,r。p=L(L为头结点的地址)。q=p->next;(这里要注意先判断q是否为空?如果q为空,意味着L->next为空。空链表,不予受理!!!!!!) r=q->next;(这样子,三个指针就连续了)

    当r->data!=X,并且r!=null时(最前面的指针指向的节点数据域不是x,并且这个指针有节点去指向)
    让指针移动,p=q;q=r;r=r->next;这样就找到了满足条件的三个地址。


    找到了地址,下一步是删除。要注意的一点是,什么时候可以删除?只有当r!=null,才能删。否则不满足题目一开始的条件了。
    删除操作:p->next=q->next;free(q);
    展开全文
  • 单链表的删除第i个元素

    千次阅读 2019-08-28 18:11:13
    单链表第i个数据删除结点算法思路: 1.声明结点p指向链表第一个结点,初始化j=1; 2.当j<i时,就遍历链表,让P指针向后移动,不断指向下一个结点,j累加1; 3.若到链表末尾p为空,则说明第i个元素不存...

    单链表的删除

    删除操作图示
    里插入图片描述
    a2的节点q,要实现q的删除,就是让他的前继节点p绕过a2直接指向后继节点a3。
    p->next=p->next->next;

    单链表第i个数据删除结点的算法思路:
    1.声明结点p指向链表第一个结点,初始化j=1;
    2.当j<i时,就遍历链表,让P的指针向后移动,不断指向下一个结点,j累加1;
    3.若到链表末尾p为空,则说明第i个元素不存在;否则查找成功,将欲删除结点p->next赋值给q
    4.单链表的删除标准语句p->next=q->next,将q结点中的数据赋值给e,作为返回;释放q结点。

    typedef int Status;
    //可以用C语言结构指针来描述单链表:
    typedef struct Node
    {
    	ElemType data;   //数据城
    	struct Node*Next;//指针域
    }Node  :
    typedef struct Node* LinkList;
    LinkList p;
    Status DeletElemLinklist(LinkList l,int i, int  e)
    {
    	int j;
    	LinkList s;
    	p=p->Next;        	//p指向表头
    	for (j = 1; j < i; ++j)
    	{
    		p=p->Next;        //p指向第i个节点
    		if (p==Null)
    		{
    			return err;
    		}
    	}
    	p->Next =p->Next->Next;
    	free(p);
    	e=p->Next->data;									 	
     	return success;
    }
    

    无论是单链表插入还是删除算法,它们都是由两个部分组成:第一部分就是遍历查找第i元素,第二部分就是实现插入和删除元素。从整个算法来说,我们很容易可以推出他们的肘间复杂度都是0(n)。再详细点分析:如果在我们不知道第i个元素的指针位置,单链表数据结构在插入和删除操作上与线性表的顺序存储结构是没有太大优势的。
    但如果,我们希望从第i个位置开始,插入连续10个元素,对于顺序存储结构意味看,每一次插入都需要移动n-i个位置,所以每次都是0(n)。而单链表,我们只需要在第一次时,找到第i个位置的指针,此时为0(n),接下来只是简单地通过赋值移动指针而已,时间复杂度都是0(1)。显然对于插入或删除数据越频繁的操作,单链表的效率优势就越是明显

    展开全文
  • 单链表中从第一个结点出发,顺指针next域逐个往下搜索,直到找到第i个结点为止,否则返回最后一个结点指针域NULL。 按序号查找结点值算法如下: LNode GetElem(LinkList L,int i){ //本算法取出单链表L...

     

     

     

     

     

     

     

    本节讲解一下单链表中节点的查找、插入、删除、求单链表长度等操作。

    按序号查找结点值

    在单链表中从第一个结点出发,顺指针next域逐个往下搜索,直到找到第i个结点为止,否则返回最后一个结点指针域NULL。

    按序号查找结点值的算法如下:

    
     
    1. LNode GetElem(LinkList L,int i){
    2. //本算法取出单链表L(带头结点)中第i个位置的结点指针
    3. int j=1; //计数,初始为1
    4. LNode *p = L->next; //头结点指针赋给p
    5.  
    6. if(i==0)
    7. return L; //若i等于0,则返回头结点
    8. if(i<1)
    9. return NULL; //若 i 无效,则返回 NULL
    10.  
    11. while( p && j<i ) { //从第1个结点开始找,查找第i个结点
    12. p=p->next;
    13. j++;
    14. }
    15.  
    16. return p; //返回第i个结点的指针,如果i大于表长,p=NULL,直接返回p即可
    17. }

    按序号查找操作的时间复杂度为O(n)。

    按值查找表结点

    从单链表第一个结点开始,由前往后依次比较表中各结点数据域的值,若某结点数据域的值等于给定值e,则返回该结点的指针。若整个单链表中没有这样的结点,则返回NULL。按值查找结点的算法如下:

    
     
    1. LNode *LocateElem (LinkList L, ElemType e) {
    2. //本算法查找单链表 L (带头结点)中数据域值等于e的结点指针,否则返回NULL
    3. LNode *p=L->next;
    4. while( p!=NULL && p->data!=e) //从第1个结点开始查找data域为e的结点
    5. p=p->next;
    6.  
    7. return p; //找到后返回该结点指针,否则返回NULL
    8. }

    按值查找操作的时间复杂度为O(n)。

    插入结点操作

    插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性,然后找到待插入位置的前驱结点,即第i-1个结点,再在其后插入新结点。

    算法首先调用上面的按序号查找算法GetElem(L,  i-1),查找第i-1个结点。假设返回的第i-1个结点为*p,然后令新结,点*s的指针域指向*p的后继结点,再令结点*p的指针域指向新插入的结点*s。其操作过程如图2-6所示。
     


    图2-6  单链表的插入操作


    实现插入结点的代码片段如下:

    
     
    1. p=GetElem(L, i-1) ; // 语句①,查找插入位置的前驱结点
    2. s->next=p->next; // 语句②,图 2-6 中辑作步骤 1
    3. p->next=s; // 语句③,图2-6中操作步骤2

    算法中,语句②③的顺序不能颠倒,否则,当先执行p->next=s后,指向其原后继的指针就不存在了,再执行s->next = p->next时,相当于执行了 s->next=s,显然是错误的。本算法主要的时间开销在于查找第i-1个元素,时间复杂度为O(n)。若是在给定的结点后面插入新结点,则时间复杂度仅为O(1)。

    扩展:对某一结点进行前插操作

    前插操作是指在某结点的前面插入一个新结点,后插操作的定义刚好与之相反,在单链表插入算法中,通常都是釆用后插操作的。

    以上面的算法为例,首先调用函数GetElem()找到第i-1个结点,即待插入结点的前驱结点后,再对其执行后插操作。由此可知,对结点的前插操作均可以转化为后插操作,前提是从单链表的头结点开始顺序查找到其前驱结点,时间复杂度为O(n)。

    此外,可以釆用另一种方式将其转化为后插操作来实现,设待插入结点为*s,将插入到*p的前面。我们仍然将*s插入到*p的后面,然后将p->data与s->data交换即可,这样既满足了逻辑关系,又能使得时间复杂度为O(1)。算法的代码片段如下:

    
     
    1. //将结点插入到*P之前的主要代码片段
    2. s->next = p->next; //修改指针域,不能颠倒
    3. p->next = s;
    4. temp = p->data; //交换数据域部分
    5. p->data=s->data;
    6. s->data=temp;

    删除结点操作

    删除操作是将单链表的第i个结点删除。先检查删除位置的合法性,然后查找表中第i-1个结点,即被删结点的前驱结点,再将其删除。其操作过程如图2-7所示。
     


    图2-7  单链表结点的删除


    假设结点*p为找到的被删结点的前驱结点,为了实现这一操作后的逻辑关系的变化,仅需修改*p的指针域,即将*p的指针域next指向*q的下一结点。

    实现删除结点的代码片段如下:

    
     
    1. p=GetElem(L,i-1); //查找删除位置的前驱结点
    2. q=p->next; //令q指向被删除结点
    3. p->next=q->next //将*q结点从链中“断开”
    4. free (q) ; //释放结点的存储空间

    和插入算法一样,该算法的主要时间也是耗费在查找操作上,时间复杂度为O(n)。

    扩展:删除结点*p

    要实现删除某一个给定结点*p,通常的做法是先从链表的头结点开始顺序找到其前驱结点,然后再执行删除操作即可,算法的时间复杂度为O(n)。

    其实,删除结点*p的操作可以用删除*p的后继结点操作来实现,实质就是将其后继结点的值赋予其自身,然后删除后继结点,也能使得时间复杂度为O(1)。

    实现上述操作的代码片段如下:

    
     
    1. q=p->next; //令q 向*p的后继结点
    2. p->data=p->next->data; //和后继结点交换数据域
    3. p->next=q->next; //将*q结点从链中“断开”
    4. free (q) ; //释放后继结点的存储空间

    求表长操作

    求表长操作就是计算单链表中数据结点(不含头结点)的个数,需要从第一个结点开始顺序依次访问表中的每一个结点,为此需要设置一个计数器变量,每访问一个结点,计数器加1,直到访问到空结点为止。算法的时间复杂度为O(n)。

    需要注意的是,因为单链表的长度是不包括头结点的,因此,不带头结点和带头结点的单链表在求表长操作上会略有不同。对不带头结点的单链表,当表为空时,要单独处理。

    单链表是整个链表的基础,读者一定要熟练掌握单链表的基本操作算法,在设计算法时,建议先通过图示的方法理清算法的思路,然后再进行算法的编写。

    展开全文
  • 单链表节点的删除】: ...//pos从1开始计算,1表示删除head后的第个节点 node *delete_node(node *head, int pos) { node *item = NULL; node *p = head->next; int i = 0; if(p == NULL)
  • 该函数在带头节点的单链表L中删除第i个节点删除的节点数据保持在px指向指针中。 如果删除成功,返回1,否则返回0。 请注意,本题有预置代码,只需提交所要求函数定义...
  • 单链表--删除第i个结点

    千次阅读 2014-03-29 21:13:10
    int listdelete (linklist &l, int i){ ... while (p -> next && j < i - 1){ //p指向第i个节点的前驱 p = p -> next; j++; } if(!(p -> next) || i ){ return error; } node * q = p ->
  • 单链表的删除

    2020-05-14 19:46:47
    链表的删除 源代码片段 typedef struct Node { int data;...//删除第pos个节点的后一个节点 bool delete——list(PNODE pHead, int pos, int * pVal) { int i = 0; PNODE p = pHead; while (NULL
  • 头结点:在单链表的第一个结点前附设的一个结点 单链表的读取数据元素 获得第 i 个节点的数据 声明第一个节点指针p指向链表的第一个结点a1,初始化 j 从1开始 当 j < i 时,遍历链表,让 p 的指针向后...
  • 单链表的插入删除

    2021-04-21 16:26:44
    L,i,e):插入操作,在表L中的第i个位置上插入指定元素e,(找到第i-1个结点,将新节点插入其后) 按位序插入(带头结点) 存在第0个结点 //在第i个位置插入元素e(带头结点) bool LIstInsert(LinkList &L,int i,...
  • 单链表

    2018-10-17 23:42:33
    建立一个空的带头节点的单链表 采用头插法在单链表中插入n个元素 ...删除单链表的第i个元素 实现单链表按关键字查找操作 计算单链表的表长并输出单链表 销毁单链表 在这里插入代码片 ...
  • 3 //缺点,比起线性表,找出第i个元素很困难,时间复杂度为o(n),线性表只要直接下标获取,时间复杂度为O(1) 4 //优点,单链表的插入和删除时非常方便的,时间复杂度为o(1),线性表的插入和删除最后情况是...
  • 平时我们在计算单链表的第i个节点删除时间复杂度时一般认为是O(n),过程如下 1.先从头节点开始遍历链表,找到第i-1个节点 2.将第i-1节点next指向第i个节点的next 可以看到时间主要花在了遍历链表上 如果我们...
  • 单链表的读取,插入与删除

    千次阅读 多人点赞 2018-05-07 20:16:21
    一:单链表的读取 获得链表第i个数据,...i时,说明第i个节点不存在; 4.若查找成功,返回结点p的数据。二:单链表的插入 单链表第i 个数据插入结点的算法思路: 1.声明一指针p 指向链表头结点,初始化从1开始...
  • 实现获得单链表第i个元素方法; 实现在第i个位置之前插入元素方法; 逆位序输入n个元素值,建立带表头节点的单链表L; 删除在第i(不包括头节点)个位置之前那个元素方法; 实现获得单链表第i个元素...
  • 定义单链表的结构体 ...单链表的插入操作:(例如:在单链表L中第 i 个位置插入新的数据元素e,或者说在第i个位置之前插入新的数据元素e,都是一样的意思,自己慢慢琢磨),下面让我们分步进行操作。 ...
  • 单链表插入删除

    2016-04-18 15:00:13
    在链表的插入删除操作上理解起来比顺序表更为容易,其不需要变动在i位置前的所有的...将s的后缀改为p的后缀,p的后缀是原来的第i个点的指针域,将其给s的后缀说明此时的s是第i个节点的前一个节点。 p->next=s;;将p的后
  • 数据结构单链表的基本操作的实现 1.1单链表的初始化 1.2 判断链表是否为空 1.3单链表的销毁 清空单链表 ...求单链表的表长 ...删除第i个节点 单链表的建立----头插法 单链表的创建----尾插法 ...
  • (1) 声明一个结点 p 指向链表第一个结点(这里是存储数据的第个节点,不是头结点),初始化 j 从 1 开始; (2) 当 j &lt; i 时,就遍历链表,让 p 的指针向后移动,不断指向下一结点, j 累加 1; (3) 若到...
  • 初学数据结构,刚学到单链表,增删改查删除这一步我在书上了解到是一个用两个变量保存要删除的结点和他前一个结点,所以我写了一个删除函数,后来我想理论上可以不用保存前一个结点也可以删除个节点。...
  • 单链表的基础操作

    2017-04-21 21:20:00
    单链表节点的查找、插入、删除、求单链表长度等操作。 按序号查找结点值 在单链表中从第一个结点出发,顺指针next域逐个往下搜索,直到... //本算法取出单链表L(带头结点)中第i个位置结点指针 int j=1; /...
  • 单链表的插入

    2021-04-22 21:43:07
    ```cpp //按位序删除(带头结点) ...//找到第i-1个节点 LNode *p;//指针p指向当前扫描节点 int j = 0;//当前p指向是第几个节点 p = L;//L指向头结点,头结点是第0个节点(不存数据) while (p != NULL.
  • 简单的单链表操作,权当复习练手,高手请绕过。 单链表的查找运算: LinkList Find_List(LinkList L,.../*初始时,令p指向元素节点i为元素计数器*/ while(p&&i){/*顺指针向后查找,直到p指向
  • Day 13 作业总结Day12 作业是删除链表中某个节点node,Day13 遍历获得链表的第i个节点,至此相信大家对链表的基本操作已经掌握。获得长度为n 头节点为head链表的第i个节点,代码如下:defgetiNode(head,n,i):ifi0ori...
  • 1、单链表 单链表分为带头结点和不带头节点两种 不带头节点,空表判断:L==NULL。写代码不方便 带头结点,空表判断:L->next==NULL。写代码更方便 ...在表L中的第i个位置上插入指定元素e。(找
  • 单链表插入和删除

    2020-09-28 21:56:17
    while()里面主要是找到第i-1个结点 j:当前p指向第几个结点 指定元素后插操作 前插操作有两种方法: 第一种是:传入头指针,然后去遍历; 第二种是:先在p后面后插一个节点s,然后去交换data; p前继结点找不到,...
  • next,因为插入删除时可以是在有效数据节点之前,此时j要保持j=0; #include<stdio.h> #include<stdlib.h> #define OK 1 #define FALSE 0 typedef int Status; typedef float ElemType; typedef

空空如也

空空如也

1 2 3 4 5 6
收藏数 120
精华内容 48
关键字:

删除单链表的第i个节点