本系列文章简要介绍链表的相关知识。
本文是系列文章的第三篇，将介绍在单向链表中删除节点的方法，并给出代码示例。
1 概述
在单向链表中删除节点，首先要根据预先确定的节点标志，判断待删除节点是否存在于链表之中，如果链表中不存在该节点，则无需进行删除操作。如果该节点存在于链表之中，在删除该节点时，还需要区分以下两种情况：
- 待删除节点是链表的首节点；
- 待删除节点不是链表的首节点（即该节点是中间节点或末尾节点）。
下面通过伪代码的形式介绍在单向链表中删除节点的算法。
算法：DeleteLinkedlist(list,target)
目的：在单向链表中删除节点
前提：链表和要删除的节点信息
后续：无
返回：新链表
{
if (list == null) // empty list
{
// nothing to do
return
}
cur <- list
while (((*cur).num != (*target).num) && ((*cur).link != null)) // find target node location
{
pre <- cur
cur <- (*cur).link
}
if ((*cur).num == (*target).num) // target node in the list
{
if (list == cur) // target node is the first node
{
list <- (*cur).link
}
else // target node is not the first node
{
(*pre).link <- (*cur).link
}
}
else
{
// target node not found
}
return list
}2 代码示例
根据上述内容，可以编写在单向链表中删除节点的代码示例。
代码示例内容如下：
#include <stdio.h>
#define STRUCT_LEN sizeof(struct student)
struct student
{
int stu_num; /* student number */
float stu_score; /* student score */
struct student* next;
};
int main()
{
/* declaration of func */
struct student * delete(struct student * head, struct student * target_node);
void print(struct student * list);
/* create a static linked list */
struct student * list;
struct student stu_1, stu_2, stu_3;
stu_1.stu_num = 1;
stu_1.stu_score = 88;
stu_2.stu_num = 2;
stu_2.stu_score = 66;
stu_3.stu_num = 3;
stu_3.stu_score = 100;
list = &stu_1;
stu_1.next = &stu_2;
stu_2.next = &stu_3;
stu_3.next = NULL;
/* print linked list before deletion */
printf("before deletion, ");
print(list);
/* create target node that to be deleted from linked list */
struct student stu_del;
stu_del.stu_num = 3;
stu_del.stu_score = 0; /* any value, because this item not compare */
/* delete target node from linked list */
list = delete(list, &stu_del);
/* print linked list after deletion */
printf("after deletion, ");
print(list);
return 0;
}
/*
** this is the delete linked list function.
*/
struct student * delete(struct student * head, struct student * target_node)
{
struct student * cur;
struct student * pre;
struct student * target;
cur = head; /* let cur point first node */
target = target_node; /* let target point the node that to be deleted */
if (NULL == head) /* empty list */
{
printf("list is null!\n");
return head;
}
while (((*target).stu_num != (*cur).stu_num) && ((*cur).next != NULL)) /* find target node location */
{
pre = cur;
cur = (*cur).next;
}
if ((*target).stu_num == (*cur).stu_num) /* target node in the list */
{
if (head == cur) /* target node is the first node */
{
head = (*cur).next;
}
else /* target node is not the first node */
{
(*pre).next = (*cur).next;
}
}
else
{
printf("\ntarget node not found!\n\n");
}
return head;
}
/*
* this is the print linked list content function.
*/
void print(struct student * list)
{
struct student *walker;
walker = list;
printf("the linked list contents(student number and score) as followed:\n");
printf("[student number] [student score]\n");
while (walker != NULL)
{
printf("%d %-f\n", (*walker).stu_num, (*walker).stu_score);
walker = (*walker).next;
}
return;
}
上述代码的编译及运行结果如下：
说明：
- 上述代码中使用了待删除节点的学生学号信息“std_num”作为删除标志，除此之外的待删除节点的其他信息，不影响节点删除逻辑；
- 为了验证在待删除节点是链表首节点、链表中间节点和链表末尾节点的情况，可以通过修改待删除节点的结构体成员“stu_del.stu_num”的值，进行对应的测试；（上面已给出了这几种场景对应的测试结果）
- 为了简化代码内容，上述代码示例使用的是静态链表，即链表的所有节点都是在程序中定义的，节点的存储空间不是临时开辟的。