引入

我们知道如何在单链表中插入一个结点，那么现在就再看看如何删除一个结点，删除结点需要注意什么呢？

思考删除单链表中的结点

我们知道链表是一环扣一环，一个压一个。所以，要删除其中的某个结点，只需要将其前一个结点的 next 指针域指向该结点的下一结点即可。

  • p->next=p->next->next;
  • q=p->next , p->next=q->next
  • 上面两种方式都是可以的，思路都是跳过要删除的这个，直接将前一个的指向指向后一个的地址。

删除单链表元素的算法

我们根据上面的思路，来看看用代码如何实现：

  • **指向：**声明一个节点 p 指向链表中的第一个结点
  • **遍历：**初始化 j=1，j<i ，P 的指针不断向后移动，j++
  • **失败：**到了链表末尾，p 为空，表示第 i 个元素不存在
  • **成功：**成功，将需要删除的结点 p->next 赋值给 q
  • 然后执行 p->next = q->next
  • 最后 free 掉即可。

代码实现

还是用 C 语言来动态生成单链表，然后再删除其第二个结点

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct Student)

struct Student{
    int num;
    char name[20];
    float score;
    struct Student * next;
};

struct Student * create(void){
    struct Student *a , *b , *head;
    a=b=(struct Student * )malloc(LEN);
    printf("请输入考生信息：\n");
    scanf("%d %s %f",&a->num , a->name , &a->score);
    int n=0;
    while(a->num!=0){
        n=n+1;
        if(n==1){
            head=a;
        }else{
            b->next=a;
            b=a;
        }
        a=(struct Student *)malloc(LEN);
        scanf("%d %s %f", &a->num , a->name , &a->score);
    }
    b->next=NULL;
    return head;
}

void print(struct Student *p){
    while(p!=NULL){
        printf("第%d位%s的成绩是：%3.1f\n", p->num , p->name , p->score);
        p=p->next;
    }
}

void LinkDelete(struct Student * del_p , int i){
    struct Student *q;
    int j=1;
    while( del_p && j<i-1){
        del_p=del_p->next;
        j++;
    }
    q=del_p->next;
    del_p->next=q->next;
    free(q);
}

int main(){
    struct Student *stu_p;
    stu_p=create();
    LinkDelete(stu_p,2);
    print(stu_p);
}

伪代码实现

#define ERROR 0
#define OK 1
typedef int Elemtype
struct Node{
Elemtype data;
struct Node * next;
};
//构建单链表
typedef struct Node* LinkList;

status DeleteLink( LinkList L , int i , Elemtype *e){
int j=1;
LinkList q,old;
q=L;

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

if(!q || j>i){
return ERROR;
}

old=q->next; //获取要删除的
q->next=old->next; // 将要删除的下一个地址赋值给原来指向要删除结点的结点
*e = old->data;  //获取删除的data 数据域
free(old); //将删除的结点释放掉
return OK;  
}

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。