数据结构之线性表-在静态链表中删除结点-学习笔记-20

引入

我们知道了如何初始化一个静态链表，并且知道如何在静态链表中插入一个结点，今天我们来看看如何删除一个结点，并将删除得结点 Free 。

思路

我们先想一下，如果要移除静态链表中的一个结点，会发生什么。

• 该结点的上一个结点找不到移除的这个结点了，链表断了
• 移除的结点内得数据还有，游标指向的是其原来的下个结点
• 移除的结点成了备用链表中的一个结点，0下标的第一个可用结点也需要修改

所以，我们总结如下得思路

• 移除结点，找到前一结点，指向移除结点的后一结点
• 清空移除的结点内的数据
• 移除结点的游标改为0下标指向的第一个可用结点得下标
• 0下标指向的第一个结点为移除的结点

代码

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10

typedef struct {
    int num;
    int data;
}stu[20];

void stu_initialization(stu stu_arr){
    for(int i=0;i<MAXSIZE-1;i++){
        stu_arr[i].num=i+1;
        stu_arr[i].data=0;
    }
    stu_arr[MAXSIZE-1].num=0;
}

int stu_length(stu stu_arr){
    int i=1,n=0;
    while(stu_arr[i].data!=0){
        i=stu_arr[i].num;
        n++;
    }
    return n+1;
}

int stu_first(stu stu_arr){
    int i=stu_arr[0].num;
    if(stu_arr[0].num){
        stu_arr[0].num=stu_arr[i].num;
    }
    return i;
}

int stu_create(stu stu_arr , int i , int data){
    if(i<1 || i>stu_length(stu_arr)+1){
        printf("插入错误！\n");
    }
    
    int j,k;
    j = MAXSIZE-1;  //获取下标尾巴
    k = stu_first(stu_arr);
    stu_arr[k].data=data;
    for(int l=1;l<=i-1;l++){
        j=stu_arr[j].num;
    }
    stu_arr[k].num=stu_arr[j].num;
    stu_arr[j].num=k;
    return 1;
}

int stu_delete(stu stu_arr , int i){
    if(i<1 || i>stu_length(stu_arr)){
        printf("删除错误！\n");
    }
    int j;
    j= MAXSIZE-1;  //获取下标尾巴
    for(int l=1;l<=i-1;l++){
        j=stu_arr[j].num;
    }
    //遍历找到删除结点得前一个结点下标
    stu_arr[j].num=stu_arr[i].num;
    stu_arr[i].data=0;
    stu_arr[i].num=stu_arr[0].num;
    stu_arr[0].num=i;
    return 1;
}

int main(){
    stu student;
    stu_initialization(student);
    stu_create(student,1,111);
    stu_create(student,2,222);
    stu_create(student,3,333);
    stu_delete(student, 3);
    int i=1;
    while(student[i].data){
        printf("下标%d的游标是：%d，数据是：%d\n",i,student[i].num,student[i].data);
        i=student[i].num;
    }
    return 0;
}

输出结果
下标1的游标是：2，数据是：111
下标2的游标是：0，数据是：222

主要就是删除后得一系列操作

• 把链表继续链好
• 把空结点归置到备用链表中去
• 把头结点指向删除的空结点

注意
刚刚发现我上一篇犯了一个错误，我错误的通过下标遍历数组中的 data 是否为0来判断链表得长度和输出链表中得值。
忘记了如果中间某个节点删除了，遍历数组就没意义了，链表一定要顺着链来寻找，不能使用下标遍历的方法。

伪代码实现

Status ListDelete(StaticLInkList L , int i){
int j,k;
if(i <1 || j>ListLength(L)){
return ERROR;
}
k = MAXSIZE-1;
for(j=1;j<=i-1; j++){
k=L[k].cur;
}
//k为删除结点前一个下标
j=L[k].cur;  //把前一个得指向给 j
L[k].cur=L[j].cur;  // 跳过 j，直接让 k 指向 j 的游标

L[j].cur=L[0].cur;  //让删除得指向本来第一个可用的
L[0].cur=j;  // 让第一个可用的指向删除的这个
}

尾巴

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