【数据结构】【线性表】单链表3—单链表的删除(附C语言源码)
单链表的删除
单链表的删除包括有按位序删除和删除指定结点。
按位序删除
按位序删除，则将链表中第i位的结点删除，由于链表是物理结构为链式存储的线性表，其存储内存不连续，依靠结点中元素数据中的指针数据指向下一结点，因此要删除第i个结点，只需要将第i-1的结点的指针数据指向i+1即可，注意最后释放第i个元素得到空间。
/*功能：单链表删除第i个结点
输入：
&L->单链表结构体
i->要删除的位序i
&e->反馈删除的数据
输出：
flase：删除失败
true ：删除成功
说明：适用于带头结点的单链表
*/
bool ListDelete(LinkList &L,int i,ElemType &e){
if(i<1)//判断i是否在有效
return false;//i无效，插入失败
LNode *p=NUll;//当前结点
int j=0;//当前结点是第几个位置
p=L;//初始化当前节点为头结点
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;//暂存第i个结点
p->next=q->next;//将第i个结点的方向指针给i-1，同时第i个结点从链中断开
e= q->data;//将第i个节点的数据传递给e
free(q);//释放结点的存储空间
return e;//删除成功
}
不带头结点的单链表在i=1时没有i-1的结点，无法进行正常操作，需要特殊处理
/*功能：单链表删除第i个结点
输入：
&L->单链表结构体
i->要删除的位序i
&e->反馈删除的数据
输出：
flase：删除失败
true ：删除成功
说明：适用于不带头结点的单链表
*/
bool ListInsert(LinkList &L,int i,ElemType e){
if(i<1)//i不合法
return false;//删除失败
if(i==1){
LNode *q=p->next;//暂存第i个结点
L=q->next;//L指向第二个结点
e=q->data;//将第一个结点的数据传递给e
free(q);//释放结点内存
return true;//删除成功
}
LNode *p=NUll;//当前结点
int j=0;//当前结点是第几个位置
p=L;//初始化当前节点为头结点
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;//暂存第i个结点
p->next=q->next;//将第i个结点的方向指针给i-1，同时第i个结点从链中断开
e= q->data;//将第i个节点的数据传递给e
free(q);//释放结点的存储空间
return e;//删除成功
}
指定结点删除
指定删除结点p需要找到被删除结点的前驱结点的next指针，将其修改为要被删除结点的next指针。但由于单链表是单向的，因此要找到前驱结点只能通过从头开始遍历结点的方式去找到前驱结点，或者我们可以采用一种特殊的方式偷天换日去实现。
找前驱结点的目的是将前驱结点的next指针更新为p的next，我们不找前驱结点，将p的next指向的结点的数据换到p中，p的next更新为next指向结点的next，完成偷天换日。
/*功能：单链表删除指定结点p
输入：
*p->要被删除的结点p
&e->反馈删除的数据
输出：
flase：删除失败
true ：删除成功
说明：采用偷天换日的方法，但无法删除链表最后一个结点，时间复杂度为O(1)。
*/
bool DeleteNode(LNode *p,ElemType &e){
if(p==NULL)//判断结点合法性
return false;//删除失败
LNode *q=p->next;//暂存要被删除的后续结点
e=p->data;//将要被删除的结点数据传递给e
p->data=q->data;//将后续结点的数据传递给p
p->next=q->next;//将后续结点的next传递给p
/*到此处完成后续结点的所有内容已经换到要被删除的结点了完成偷天换日*/
free(q);
return true;
}
但如果p是单链表中最后一个结点，则该方法无效，依旧需要从表头去遍历链表实现删除。此时我们将模仿按位查找的的方法遍历单链表，将遍历终止条件j<i-1改为s->next == p源码如下：
/*功能：单链表删除指定结点p
输入：
*p->要被删除的结点p
&e->反馈删除的数据
输出：
flase：删除失败
true ：删除成功
说明：适用于单链表的所有结点的删除，时间复杂度为O(n)。
*/
bool DeleteNode(LNode *p,ElemType &e){
LNode *s=NUll;//当前结点
s=p;//初始化当前节点为头结点
while(s!=NULL && s->next!=p)//循环遍历找到删除结点p的前驱结点
s=s->next;
if(s==NULL)//链表遍历出错
return false;//删除失败
if(p->next==NULL)//前驱结点后续没有其他结点
return false;//删除失败
LNode *q=p->next;//暂存删除结点
p->next=q->next;//将暂存结点的next指针给前驱结点，同时结点p从链中断开
e= q->data;//将删除结点p的数据传递给e
free(q);//释放结点的存储空间
return e;//删除成功
}
原文地址：https://blog.csdn.net/weixin_58498967/article/details/143646724
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！