引入

我们说过动态链表是使用malloc( ) 和 free( )这两个函数来实现的，动态插入，动态释放。那么静态链表该如何实现这样的功能呢？

静态链表中插入数据

简单来说就是要分清楚哪些没有使用过，哪些已经在使用了。
我们说

备用链表存放的是所有可以用的下标，用游标链接。
数组的第一个元素，存放的是备用链表的第一个可用下标
所以
每次插入新节点，都可以从备用链表取得第一个结点作为待插入结点。

步骤分解
1、先获取0下标指向的备用链表的第一个可写入下标。
2、第一个可写入的结点的游标传递给0下标。
3、判断插入地址是否合法，不能小于1，不能大于结点长度+1的位置。
4、对第一个可写的节点的 data 赋值
5、通过循环从最后一个结点向前找到要插入的节点之前的结点
6、找到之后新结点的游标改成之前结点的游标
7、前一结点的游标指向新节点的下标。

代码实现

我设计了三个函数，静态链表初始化、获取静态链表当前长度、静态链表顺序插入函数。然后再静态链表中插入三个数据，并返回目前链表的情况以及它们的游标。以及下一个可用的下标。

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

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

void init(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 return_usefull(stu stu_arr){
    int i=stu_arr[0].num;
    //获取目前可用的下标
    if(stu_arr[0].num){
        stu_arr[0].num=stu_arr[i].num;
        //将目前可用的下一个下标重新赋值给0下标
    }
    return i;
}
//返回0下标对应的游标

int listlength(stu stu_arr){
    int i=0,n=1;
    while(stu_arr[n].data!=0 && n<MAXSIZE){
        i++;
        n++;
    }
    return i;
}

int insert(stu stu_arr, int i ,int data){
    int k ,j , l;
    if(i<1 || i>listlength(stu_arr)+1){
        return 0;
    }
    j=return_usefull(stu_arr);  //获取第一个可用的下标
    if(j){
        stu_arr[j].data=data;  //给第一个可以用的下标的 data 区域赋值
        k=MAXSIZE-1;  //指向最后一个下标
        for(l=1;l<=i-1;l++){
            //找到第 i-1 个位置就停
            k=stu_arr[k].num;
            //让 k 移动到目前静态链表的第i-1个位置，因为链表的第二个并不知道实际是s哪一个，只能顺藤摸瓜找到该下标。
        }
        stu_arr[j].num=stu_arr[k].num;
        //先把要插入的 j 的游标改成原来 k 指向的游标
        stu_arr[k].num=j;
        //把 k 的游标指向 j
    }
    return 1;
}




int main(){
    stu student;
    init(student);
    insert(student, 1, 111);
    insert(student, 2, 222);
    if(insert(student, 2, 333)==0){
        printf("错误！\n");
    }
    int i=1;
    while(student[i].data!=0){
        printf("%d号下标：%d:%d\n",i,student[i].num,student[i].data);
        i++;
    }
    printf("目前可用下标是%d\n",student[0].num);
    printf("第一个结点是%d\n",student[MAXSIZE-1].num);
}

伪代码

int Malloc_SLL(StaticLinkList space){
int i=space[0].cur;
if(space[0].cur){
space[0].cur=space[i].cur;
//把原来0存储的游标的游标赋值给0，也就是下一个可用下标
}
return i;
}

Status ListInsert(StaticLinkList L ,  int i , ElemeType e){
int j,k,l;  //k是数组最后一位下标、k 是前一结点下标，j 是插入结点下标
k=MAXSIZE-1;  //k为数组最后一位下标
if(i <1 || i>ListLength(L)+1){
return ERROR;
//判断插入位置 i 的合法性，不能小于1，也不能超过当前链表+1得长度
}
j = Malloc_SLL(L);  //j 为插入结点下标，获取得是链表第一个可用结点得下标。

if(j){
L[j].data=e;  //先把 j 这个结点得数据域存上数据
for( int l=1; l<i-1; i++){
k=L[k].cur;  //这个就像是那个链表向后找，指针等于这个指针得指针域
}
//for 循环就是顺着链表的尾巴指向的链表得第一个结点向后找

L[j].cur=L[k].cur;
L[k].cur=j;
//这个就简单了，插入嘛，先把新的等于老的，然后老的指向新的
return OK;
}
return ERROR;
}

尾巴

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