单链表的插入、删除操作详解（C语言）

大家好，我是讯享网，很高兴认识大家。

一、插入操作

（一）按位序插入（带头结点）

ListInsert(&L,i,e)：插入操作。在表L的第i个位置上插入指定元素e。
找到第i-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; //1.malloc申请新的结点空间 LNode *s = (LNode *)malloc(sizeof(LNode)); //2.将参数e存入新结点里面 s -> data = e; //3.将s指向新结点e的next指针指向p结点next指向的位置 s -> next = p -> next; //4.将p结点的next指针指向新的结点 p -> next = s; //将结点s连到p之后 return true;//插入成功 }

讯享网

分析：
①、如果i=1（插在表头）
注意：要先复制p结点next曾经指向的位置，然后再让p结点next指向新的结点。顺序不能颠倒。
②、如果i=3（插在表中）

讯享网while(p!=NULL && j<i-1){ 
   //循环找到第2个结点 p = p -> next; j++; }

③、如果i=5（插在表尾）
④、如果i=6（i > Length）
运行动态图:

（二）按位序插入（不带头结点）

ListInsert(&L,i,e)：插入操作。在表L的第i个位置上插入指定元素e。
找到第i-1个结点，将新结点插入其后。
不存在“第0个”结点，因此i=1时需要特殊处理。
②、如果i>1…

1. 指定结点的后插操作

typedef struct LNode{ 
    ElemType data; struct LNode *next; }LNode, *LinkList; //后插操作：在p结点之后插入元素e bool InsertNextNode(LNode *p, ElemType e){ 
    if(p==NULL) return false; //1.malloc申请空间 LNode *s = (LNode *)malloc(sizeof(LNode)); if(s == NULL) //内存分配失败 return false;z //2.将数据元素e填到新结点当中 s -> data = e; //用结点s保存数据元素e //3.将p的next指向下一个元素赋值给新数据元素e的next指向下一个元素 s -> next = p -> next; //4.将p的next指向新数据元素e p -> next = s; //将结点s连接到p之后 return true; }

在这里插入图片描述

2. 指定结点的前插操作

如何找到p结点的前驱结点？

（1）通过传入头指针的方式实现

在这里插入图片描述

（2）通过复制插入位置的结点方式实现

在这里插入图片描述

二、删除操作

（一）按位序删除（带头结点）

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

讯享网typedef struct LNode{ 
    ElemType data; struct LNode *next; }LNode, *LinkList; 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; //删除成功 }

删除的结点如果i=4：

（二）指定结点的删除

//删除指定结点 p bool DeleteNode(LNode *p)

在这里插入图片描述

删除结点p，需要修改其前驱结点的 next 指针

1. 传入头指针，循环寻找 p 的前驱结点

在这里插入图片描述

动态运行图：
如果p是最后一个结点：

单链表的插入、删除操作详解（C语言）

一、插入操作

（一）按位序插入（带头结点）

（二）按位序插入（不带头结点）

1. 指定结点的后插操作

2. 指定结点的前插操作

（1）通过传入头指针的方式实现

（2）通过复制插入位置的结点方式实现

二、删除操作

（一）按位序删除（带头结点）

（二）指定结点的删除

1. 传入头指针，循环寻找 p 的前驱结点

相关推荐