3. 线性表 - 静态链表

3.1 静态链表概念

静态链表即定义一个结构体数组，结构体包含以下 2 部分信息：
- 数据域：用于存储数据元素的值；
- 游标：储存直接后继元素所在数组中的位置，其实就是数组下标
静态链表实际上包含2条链表
- 备用链表 ：还未使用的链表
- 数据链表 ：已经存储数据的链表

3.2 静态链表的基本操作方法

静态链表的创建，使用方法如下：

#include<stdio.h>
#include<stdint.h>
#include <stdlib.h>
#define maxSize 6
typedef struct {
    uint8_t data;      // 数据域
    uint8_t position;  // 游标 ：后继元素存储的位置
}component;

void printArr(component* array) {
    printf("*******************\n");
    for (uint8_t i = 0; i < maxSize; i++) {
        printf("%x --> [ %x, %d ]\n",i, array[i].data, array[i].position);
    }
    printf("*******************\n");
}

// 创建备用链表
void reserveArr(component* array) {
    for (uint8_t i = 0; i < maxSize; i++) {
        array[i].position = i + 1; // 将每个数组链接到一起
        array[i].data = 0xff;
    }
    array[maxSize - 1].position = 0; // 链表最后一个结点的游标值为0
}

// 提取分配空间
uint8_t mallocArr(component* array) {
    //若备用链表非空，则返回分配的结点下标，否则返回 0（最后一个结点的游标值为 0）
    uint8_t i = array[0].position;
    if (array[0].position) {
        array[0].position = array[i].position;
    }
    return i;
}

//初始化静态链表
uint8_t initArr(component* array) {
    reserveArr(array);                // 创建备用链表
    uint8_t body = mallocArr(array);  // 数据链表的头
    array[body].data = 1;             // 头赋值
    array[body].position = 0;
    uint8_t tempBody = body;
    for (uint8_t i = 2; i < 4; i++) {
        uint8_t j = mallocArr(array); // 从备用链表中拿出空闲位置
        array[tempBody].position = j; // 将申请的空闲位置链接在链表的最后一个结点后面
        array[j].data = i;            // 给新申请的数据域初始化
        tempBody = j;                 // 将指向链表最后一个结点的指针后移
    }
    array[tempBody].position = 0;// 新的链表最后一个结点的指针设置为0
    return body;
}

void displayArr(component* array, uint8_t body) {
    uint8_t tempBody = body;   // tempBody准备做遍历使用
    while (array[tempBody].position) {
        printf("%x ", array[tempBody].data);
        tempBody = array[tempBody].position;
    }
    printf("%x\n", array[tempBody].data);
}

// 向链表中插入数据，body : 表示链表的头结点位置，add : 插入的位置，num : 要插入的数据
void insertArr(component* array, uint8_t body, uint8_t add, uint8_t num) {
    uint8_t tempBody = body;   //  tempBody做遍历结构体数组使用
    // 找到要插入位置的上一个结点在数组中的位置
    for (uint8_t i = 1; i < add - 1; i++) {
        tempBody = array[tempBody].position;
    }
    int insert = mallocArr(array); // 申请空间，准备插入
    if (insert == 0) {
        printf("链表存储空间已满,操作失败!!!\n");
        return;
    }
    array[insert].data = num;
    array[insert].position = array[tempBody].position; // 新插入结点的游标等于其直接后继结点的游标
    array[tempBody].position = insert; // 直接前驱结点的游标等于新插入结点所在数组中的下标
}

// 备用链表回收空间的函数，其中array为存储数据的数组，k表示未使用节点所在数组的下标
void freeArr(component* array, uint8_t k) {
    array[k].position = array[0].position;
    array[k].data = 0xff;
    array[0].position = k;
}

// 删除结点函数，num 表示被删除结点中数据域存放的数据
void deletArr(component* array, uint8_t body, uint8_t num) {
    uint8_t tempBody = body;
    while (array[tempBody].data != num) {       // 找到被删除结点的位置
        tempBody = array[tempBody].position;
        // 当tempBody为0时，表示链表遍历结束，说明链表中没有存储该数据的结点
        if (tempBody == 0) {
            printf("链表中没有此数据");
            return;
        }
    }
    uint8_t del = tempBody;   // 运行到此，证明有该结点
    tempBody = body;          // 找到该结点的上一个结点，做删除操作
    while (array[tempBody].position != del) {
        tempBody = array[tempBody].position;
    }
    // 将被删除结点的游标直接给被删除结点的上一个结点
    array[tempBody].position = array[del].position;
    freeArr(array, del); // 回收被摘除节点的空间
}

// 在以body作为头结点的链表中查找数据域为elem的结点在数组中的位置
uint8_t selectElem(component* array, int body, char elem) {
    uint8_t tempBody = body;
    //当游标值为0时，表示链表结束
    while (array[tempBody].position != 0) {
        if (array[tempBody].data == elem) {
            return tempBody;
        }
        tempBody = array[tempBody].position;
    }
    if (array[tempBody].data == elem) {   // 最后一个结点需要单独判断
        return tempBody;
    }
    return 0; // 返回0，表示在链表中没有找到该元素
}

// 在以body作为头结点的链表中将数据域为oldElem的结点，数据域改为newElem
void amendElem(component* array, uint8_t body, uint8_t oldElem, uint8_t newElem) {
    int add = selectElem(array, body, oldElem);
    if (add == 0) {
        printf("无更改元素!!!");
        return;
    }
    array[add].data = newElem;
}

int main() {       
    component array[maxSize];  // 定义一个静态链表存储空间
    uint8_t body = initArr(array);
    printArr(array);
    printf("静态链表为 ：");
    displayArr(array, body);
    insertArr(array, body, 2, 4);
    printArr(array);
    printf("在静态链表的第2位置上插入数据4 ：");
    displayArr(array, body);
    deletArr(array, body, 2);
    printArr(array);
    printf("删除静态链表数据2 ：");
    displayArr(array, body);
    uint8_t position = selectElem(array, body, 3);
    printf("静态链表中数据 3 所在位置为 ：%d", position);
    amendElem(array, body, 4, 2);
    printArr(array);
    printf("将静态链表数据 4 替换成 2 ：");
    displayArr(array, body);
    return 0;
}