精华内容
下载资源
问答
  • 单链表的插入和删除
    2022-04-22 21:07:06

    单链表:先回顾单链表的特点  逻辑相邻 物理上不一定相连

    首先初始化单链表,其中主要保存的是该节点自身的值以及下个节点的地址。

    有效节点结构体设计:
    ​
    struct Node{
    ​
    int data;//数据域
    ​
    struct Node* next;//指针域
    ​
    }

    以下是单链表的插入以及删除操作:

    (一)插入操作

    单链表的插入主要分为头插,尾插,以及按位置插入这三种来进行操作。

    (1)头插

    bool Insert_head(PNode pn, int val)
    {
    	assert(pn!=NULL);//判断不为空
    
    	//1.申请新节点
    	struct Node* pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
    	assert(pnewnode != NULL);
    	pnewnode->data = val;
    	pnewnode->next = NULL; // 这里可写可不写
    
    
    	//2.找到合适的插入
    	//头插时插入在头结点的后边,所以不用找
    
    	//3.插入
    	pnewnode->next = p->next;//先让C指向B  (不能先断开AB中间的线  不然找不到B)
    	p->next = pnewnode;//此时再让A指向C
    	return true;
    }
    

    (2)尾插

    bool Inseret_tail(PNode pn, int val)
    {
    	//1.申请新节点
    	struct Node* pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
    	assert(pnewnode != NULL);
    	pnewnode->data = val;
    	pnewnode->next = NULL; // 这些步骤都与前面的一样
    
    	//2.找到合适的插入位置(尾插,需要一个临时指针p指向尾结点)
    	struct Node* p = pn;
    	for (p; p->next != NULL; p = p->next);
    
    	//3.插入
    	pnewnode->next = p->next;
    	p->next = pnewnode;
    
    	return true;
    }

    (3)按位置插入(将C插入到AB)

    bool Inseret_pos(PNode pn, int pos, int val)
    {
    	
    	assert(pos >= 0 && pos <= Get_length(pn));
    
    	//1.申请新节点
    	struct Node* pnewnode = (struct Node*)malloc(1 * sizeof(struct Node));
    	assert(pnewnode != NULL);//确保申请成功
    	pnewnode->data = val;//传入val
    	pnewnode->next = NULL; // 
    
    	//2.找到合适的插入位置(按位置插入AB之间,在这里发现规律,pos等于几则让指向头结点的指针p向后走pos步,此时p指向AB的A)
    	struct Node* p = pn;
    	for (int i = 0; i < pos; i++)
    	{
    		p = p->next;
    	}
        //3.插入
    	pnewnode->next = p->next;//先让C指向B  (不能先断开AB中间的线  不然找不到B)
    	p->next = pnewnode;//此时再让A指向C
    
    	return true;
    }

    按位置插入这里改变pos的值便可以实现头插和尾插。

    (二)删除操作

    (1)头删

    bool Del_head(PNode pn)
    {
    	//assert
    	if (IsEmpty(pn))
    	{
    		return false;
    	}
    
    	struct Node* p = pn->next;//pn是头结点 pn->next则是第一个有效节点地址  即头删的节点   则此时p指向待删除节点
    	//将待删除节点跨越指向(让带删除节点上家的next域指向下家的地址,而下家的地址在待删节点p的next中)
    	pn->next = p->next;
    	free(p);
    	p = NULL;
    
    	return true;
    }

    (2)尾删

    bool Del_tail(PNode pn)
    {
    	//assert
    	if (IsEmpty(pn))
    	{
    		return false;
    	}
    
    	//找到待删除节点用p指向(尾删的待删除节点就是倒数第一个节点)
    	struct Node* p = pn;
    	for (p; p->next != NULL; p = p->next);//当P指向的next域为空停下来
    
    	//q指向倒数第二个节点
    	struct Node* q = pn;
    	for (q; q->next != p; q = q->next);
    
    	q->next = pn;//q->next = p->next;
    	free(p);
    
    	return true;
    
    }
    

    (3)按位置删    同样这里改变pos的值能实现头删和尾删

    bool Del_pos(PNode pn, int pos)
    {
    	//assert
    	assert(pos >= 0 && pos < Get_length(pn));
    	if (IsEmpty(pn))//注意这里的判空操作在后面有定义
    	{
    		return false;
    	}
    
    	//先找到待删除节点的上一个节点,用q指向  规律:pos等于几 q就向后走几步
    	struct Node* q = pn;
    	for (int i = 0; i < pos; i++)
    	{
    		q = q->next;
    	}
    	//此时 q指向待删除节点的上一个节点
    	//接下来 再让p指向待删除节点 待删除节点在q的next中
    	struct Node* p = q->next;
    
    	//跨越指向,再释放
    	q->next = p->next;
    	free(p);//删除待删除节点
    
    	return true;
    }
      bool IsEmpty(PNode pn)
    {
    	return pn->next == NULL;
    }
    

    (4)按值删

    bool Del_val(PNode pn, int val)
    {
    	//assert
    	if (IsEmpty(pn))
    	{
    		return false;
    	}
    
    	struct Node* p = Search(pn, val);//判断value是否存在
    	if (p == NULL)//search返回的地址为空代表没找到
    	{
    		return false;
    	}
    	//此时待删除节点存在,  且用指针p指向
    
    	struct Node* q = pn;
    	for (q; q->next != p; q = q->next);
    	//再申请一个临时指针q  让q指向p的上一个节点
    
    
    	q->next = p->next;
    	free(p);
    	//跨越指向,和释放
    	return true;
    }
    
    //查找
    struct Node* Search(PNode pn, int val)
    {
    	//assert
    	for (struct Node* p = pn->next; p != NULL; p = p->next)
    	{
    		if (p->data == val)
    		{
    			return p; //找到 则扔出去
    		}
    	}
    
    	return NULL; //没找到,返回NULL地址
    }
    

    以上便是一些单链表的相关操作,简单可直接拿去使用。

    更多相关内容
  • 1.在第i个元素之前插入元素数据e: while(p && j<i-1){p=p->next;++j} while循环中找到第i-1个结点,此时p代表第i-1个结点的地址。仅判断p不为null。不需要判断p->next,p->next是否为null与...

    1.在第i个元素之前插入元素数据e:

                 while(p && j<i-1){p=p->next;++j}

    while循环中找到第i-1个结点,此时p代表第i-1个结点的地址。仅判断p不为null。不需要判断p->next,p->next是否为null与需求无关,因为p->next为null,则在该链表最后加入一个结点,若不为null,则在链表中间的某处加入一个结点。

    若刚好最后一个结点为第i-1个结点,此时第i个元素为链表长度+1个结点,第i-1个结点的指针域为null,(即在链表最后插入一个数据域为e的结点,p->next为null),则插入完成后,刚插入的元素的指针域为null。

     

                  if(!p||j>i-1)return ERROR;

          if条件判断,若p为null或者i的值小于1,返回ERROR;\

     

    2.将第i个数据元素删除

                 while(p->next && j<i-1){p=p->next;++j}

          while循环中找到第i-1个结点,此时p代表第i-1个结点的地址。

    若刚好最后一个结点为第i-1个结点,此时第i个元素为链表长度+1个结点,第i-1个结点的指针域为null,则删除无意义。

    所以要判断p->next是否为null,因为删除的是第i个数据元素,而p->next代表的是第i个数据元素的地址。

    if((!p->next )||j>i-1)return ERROR;

    判断若第i个元素的地址为空,或者i的值小于1,返回ERROR

     

    展开全文
  • 单链表插入和删除

    2014-03-27 22:55:36
    单链表的实现的插入和删除,可以上机执行的!适合初学者!
  • 单链表插入和删除

    2022-04-27 22:30:48
    1.单链表插入 ListInsert(&L,i,e):插入操作。在表L中的第 i 个位置上插入指定元素 e。(找到第 i-1个结点,将新结点插入其后) 1.1按位序插入(带头结点) typedef struct LNode{ ElemType data; ...

    1.单链表的插入

            ListInsert(&L,i,e):插入操作。在表L中的第 i 个位置上插入指定元素 e。(找到第 i-1个结点,将新结点插入其后)

    1.1按位序插入(带头结点)

    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode,*LinkList;
    
    //在第i个位置插入元素e(带头结点)
    bool ListInsert(LinkList &L,int i,ElemType e){
        if(i<1)
            return false;
        LNode *p;            //指针p指向当前所扫描到的结点
        int j=0;            //当前p指向的是第几个结点
        p=L;            //L指向头结点,头结点是第0个结点
        while(p!=NULL && j<i-1){        //循环找到第i-1个结点
            p=p->next;
            j++;
        }
        if(p==NULL)        //i值不合法
            return false;
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->data=e;
        s->next=p->next;
        p->next=s;            //将结点s连在p之后
        return true;            //插入成功
    }

      平均时间复杂度O(n)

    1.2按位序插入(不带头结点)

    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode,*LinkList;
    
    //在第i个位置插入元素e(带头结点)
    bool ListInsert(LinkList &L,int i,ElemType e){
        if(i<1)
            return false;
        if(i==1){        //插入第1个结点的操作与其他结点的操作不同
            LNode *s=(LNode *)malloc(sizeof(LNode));
            s->data=e;
            s->next=L;
            L=s;            //头指针指向新结点
            return true;
        }
        LNode *p;            //指针p指向当前所扫描到的结点
        int j=1;            //当前p指向的是第几个结点
        p=L;            //L指向头结点,头结点是第0个结点
        while(p!=NULL && j<i-1){        //循环找到第i-1个结点
            p=p->next;
            j++;
        }
        if(p==NULL)        //i值不合法
            return false;
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->data=e;
        s->next=p->next;
        p->next=s;            //将结点s连在p之后
        return true;            //插入成功
    }

      结论:不带头结点写代码更不方便,推荐用带头结点    

    1.3指定结点的后插操作   

    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode,*LinkList;
    
    //后插操作:在p结点之后插入数据元素e
    bool InsertNextLNode(LNode *p,ElemType e){
        if(p==NULL)
            return false;
        LNode *s=(LNode *)malloc(sizeof(LNode));
        if(s==NULL)            //内存分配失败
            return false;
        s->data=e;            //用结点s保存数据元素e
        s->next=p->next;
        p->next=s;            //将结点s接到p之后
        return true;
    }

    平均时间复杂度O(1)

    1.4指定结点的前插操作

    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode,*LinkList;
    
    //前插操作:在p结点之前插入数据元素e
    bool InsertPriorLNode(LNode *p,ElemType e){
        if(p==NULL)
            return false;
        LNode *s=(LNode *)malloc(sizeof(LNode));
        if(s==NULL)            //内存分配失败
            return false;
        s->next=p->next;
        p->next=s;            //将新结点s连到p之后
        s-data=p->data;        //将p中元素复杂到s中
        p->data=e;            //p中元素覆盖为e
        return true;
    }

    2.单链表的删除

            ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。(找到第i-1个结点,将其指针指向第i+1个结点,并释放第i个结点)

    2.1按位序删除(带头结点)

    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode,*LinkList;
    
    //在第i个位置插入元素e(带头结点)
    bool ListDelete(LinkList &L,int i,ElemType &e){
        if(i<1)
            return false;
        LNode *p;            //指针p指向当前所扫描到的结点
        int j=0;            //当前p指向的是第几个结点
        p=L;            //L指向头结点,头结点是第0个结点
        while(p!=NULL && j<i-1){        //循环找到第i-1个结点
            p=p->next;
            j++;
        }
        if(p==NULL)        //i值不合法
            return false;
        if(p->next==NULL)        //第i-1个结点之后已无其他结点
            return false;
        LNode *q=p->next;        //令q指向被删除的结点
        e=q->data;                //用e返回元素的值
        p->next=q->next;        //将*q结点从链中断开
        free(q);                //释放结点的存储空间
        return true;            //删除成功
    }

     最坏、平均时间复杂度为O(n)

    最好时间复杂度为O(1)

    2.2指定结点的删除

    //删除指定结点p
    bool DeleteNode(LNode *p){
        if(p==NULL)
            return false;
        LNode *q=p->next;            //令q指向*p的后继结点
        p->data=p->next->data;        //和后继结点交换数据域
        p-next=q->next;            //将*q结点从链中断开
        free(q);                    //释放后继结点的存储空间
        return true;
    }

    单链表的局限性:无法逆向检索,有时候不太方便。

    tips:

            1.这些代码都要会写,都重要

            2.打牢基础,慢慢加速

            3.体会带头结点和不带头结点的区别

            4.体会封装的好处

    展开全文
  • int delete(sqlist *L,int i,elemtype *y) ... printf("删除位置不正确!\n"); return 0; } else { *y=(*L).v[i-1]; for(j=i;j<(*L).len;j++) (*L).v[j-1]=(*L).v[j]; (*L).len=(*L).len-1; return 1; } }
  • 关于单链表插入和删除实验的程序与报告,可以了解掌握线性表的逻辑结构存储结构; 掌握单链表的基本算法及相关的时间性能分析
  • 单链表插入删除

    千次阅读 2021-01-06 20:48:52
    本期推文主要给大家介绍数据结构中单链表插入删除操作的原理以及其具体的实现过程,学会单链表的创建以及其具体操作实现 建立单链表 1) 头插法建表 将新结点逐个插入链表的头结点之后来创建链表,所以,得到的...

    内容概要

    本期推文主要给大家介绍数据结构中单链表的插入与删除操作的原理以及其具体的实现过程,学会单链表的创建以及其具体操作实现

    建立单链表

    1) 头插法建表
    将新结点逐个插入链表的头结点之后来创建链表,所以,得到的单链表的逻辑顺序与输入元素顺序相反。

    2)尾插法建表
    将新结点逐个插入到链表的尾部来创建链表,因为每次是将新结点插入到链表尾部,需加入一个指针r,用来始终指向链表中的尾结点,以便将新结点插入到链表的尾部。
    在这里插入图片描述

    单链表的插入运算

    1)在指针p所指向结点之后插入新元素。插入操作如下图所示
    ①s->next = p->next ②p->next=x
    在这里插入图片描述
    2)在指针p所指向结点之前插入新元素。插入操作如下图所示
    ①s->next =q->next ②q->next = s
    在这里插入图片描述
    插入算法代码实现

    LinkList Insert_List (LinkList L,int i,ElemType x) {
     //带头结点的单链表L的第i个位置插入x的元素
         LNode *q,*s; 
         int j = 0; 
         q = L; 			       //q为前驱结点 
          while(q&&j<i-1){
              q = q->next;                         //查找第i个位置的前驱结点 
               j++;
          }          
         s = (Linklist)malloc(sizeof(Lnode));           //插入的结点为s
         s->data = x; 
         s->next = q->next;
         q->next = s;
         return L;        
    } 
    

    单链表的删除

    要删除单链表中指定位置的元素,首先应该找到该位置的直接前驱结点。
    要实现对结点q的删除,首先要找到q结点的前驱结点p,然后完成指针的操作即可。
    操作如下图所示:
    在这里插入图片描述
    删除算法代码实现

    LinkList Delete_List (LinkList L,ElemType x) {   
     //在链表中删除值为x的元素
      LNode *p,*q;                  	 
      q = L->next;        //p为前驱结点,q为查找的结点
      while(q->data != x&&q!=NULL)    {     //查找值为x的元素 
             p = q; 
             q = q->next;
        }
        p->next = q->next;  //删除操作,将其前驱next指向其后继
        free(q);
        return L;
    }
    
    
    展开全文
  • 单链表插入删除操作的时间复杂度

    万次阅读 2019-11-10 10:31:23
    单链表相比数组的优势在于插入删除元素快,不需要移动大量的元素,只需要改变指针的指向,那么插入删除操作的时间复杂度应该是O(1),但是这是不对的,应该分情况讨论。 单链表结构体声明: typedefstruct LNode { ...
  • 单链表插入删除.c

    2019-09-27 17:34:28
    实现单链表的建立、结点的插入删除操作,上机调试程序直到算法运行正确
  • 单链表中的插入操作: Status ListInsert(LinkList &L,int i,Elemtype e){ cout<<"在第"<<i<<"个位置插入元素"<<e<<"后:"<<endl; //查找操作 LinkList p=L; int j=0;...
  • 数据结构单链表插入删除和修改实验报告 一、实验目的 1.理解数据结构中带头结点单链表的定义逻辑图表示方法。 2.掌握单链表中结点结构的JAVA描述。 3.熟练掌握单链表的插入、删除和查询算法的设计与JAVA实现...
  • 1.插入操作 在第i个结点前面,插入一个e结点。 分析: <1>.s->next = p->next; 如果想在第i个结点之前插入一个e结点,必须找到i结点前的i-1结点,在i-1结点以后插入e结点。 如上图:可以看出左边...
  • 1 引言 在单链表中,插入和删除结点是最常用的操作,它是建立单链表和相关基础运算算法的基础。2 问题描述对一个长度为n的链表在第i后面插入一个结点,再在m结点后面删除一个结点(n>i,n>m)。3 方法使用p结点...
  • 创建单链表,并输出链表,插入/删除结点元素。
  • 要实现对单链表中节点的插入删除与查找的功能,就要先进行的单链表的初始化、创建遍历,进而实现各功能,以下是对单链表节点的插入删除、查找功能的具体实现: #include #include #include typedef int ...
  • 实现单链表的一些基本操作:链表初始化--〉尾插--〉尾删--〉头插--〉头删--〉查找值为data的结点,返回该结点在链表中的位置--〉在链表pos位置后插入结点data,删除链表pos位置上的结点--〉销毁单链表--〉求链表中...
  • 实现单链表插入删除,能运行出来,还有完整实验报告
  • 由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表顺序表相应的时间复杂度分别是O(logn)O(1)。...
  • 单链表插入和删除实验报告.docx单链表插入和删除实验报告.docx单链表插入和删除实验报告.docx单链表插入和删除实验报告.docx单链表插入和删除实验报告.docx单链表插入和删除实验报告.docx单链表插入和...
  • 单链表插入和删除实验报告.pdf单链表插入和删除实验报告.pdf单链表插入和删除实验报告.pdf单链表插入和删除实验报告.pdf单链表插入和删除实验报告.pdf单链表插入和删除实验报告.pdf单链表插入和删除...
  • c 语言数据结构之单链表1,定义一个单链表1,不带头结点的单链表2,带头结点的单链表2,单链表的基本操作1,插入1,按位序插入(ListInsert(&L,i,e))2,指定结点的后插操作(InsertNextNode(LNode *p,ElemType ...
  • 单链表查找 算法思路: 声明一个节点 p 指向链表的第一个节点,初始化 j 作为计数器,从 1 开始 2. 当 j<i 的时候,遍历链表,让 p 不断向后移动,计数器 j+1 查找成功时,返回节点 当到了链表的末尾即 p 为空时...
  • 单链表插入删除节点 public class 链表插入和删除节点 { public static void main(String[] args) { List<Node> list = new LinkedList<>(); for (int i = 0; i < 10; i++) { Node no...
  • 单链表插入和删除实验报告 (2).docx单链表插入和删除实验报告 (2).docx单链表插入和删除实验报告 (2).docx单链表插入和删除实验报告 (2).docx单链表插入和删除实验报告 (2).docx单链表插入和删除实验...
  • 单链表插入和删除实验报告 (2).pdf单链表插入和删除实验报告 (2).pdf单链表插入和删除实验报告 (2).pdf单链表插入和删除实验报告 (2).pdf单链表插入和删除实验报告 (2).pdf单链表插入和删除实验报告 (2)...
  • 1.按位序插入: 带头节点的,定义指针P指向头节点,头节点是第0个节点,然后定义j表示当前p指向的是第几个节点,通过循环找到第i-1个节点,然后在第i个节点上插入...不带头节点的,插入第一个节点的操作其他节点不.
  • 单链表插入删除操作

    千次阅读 2021-05-23 05:39:49
    [c]代码库//单链表插入删除#include#includetypedef struct node{char data;struct node *next;}LNode;//创建单链表LNode *create(){LNode *head,*p,*q;char x;head=(LNode*)malloc(sizeof(LNode));head->...
  • 删除样例 插入样例 只会用C难搞啊 #include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef struct link //构建一个单链表 { int data; struct link *next; //存储下一个...
  • 单链表的基本操作之插入 ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。 即将插入位置的前一个节点的指针指向插入节点,插入节点的指针指向原来第i个位置的节点 插入前: 插入后: //在...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 74,437
精华内容 29,774
关键字:

单链表的插入和删除

友情链接: 18110178_MDI.zip