数据结构——静态链表

1.定义：

（1）单链表：各个结点散落在内存中的各个角落，每个结点有指向下一个节点的指针(下一个结点在内存 中的地址);

（2）静态链表：用数组的方式来描述线性表的链式存储结构:  分配一整片连续的内存空间，各个结点集中安置，包括了——数据元素and下一个结点的数组下标(游标)

其中数组下标为0的结点充当"头结点"

游标为-1表示已经到达表尾

若每个数据元素为4B，每个游标为4B，则每个结点共8B；假设起始地址为addr，则数据下标为2的存放地址为：addr+8*2

注意： 数组下标——物理顺序，位序——逻辑顺序； 优点：增、删操作不需要大量移动元素；

缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变！

2.静态链表用代码表示：

也可以这样：

也等同于：

注意：SLinkList a 强调a是静态链表；struct Node a 强调a是一个Node型数组；

3.静态链表基本操作的实现

（1）初始化静态链表：把a[0]的next设为-1

void InitList(StaticLinkedList *list) {
    list->head = -1; // 设置头节点的next为-1表示空链表
    list->size = 0;

    // 初始化所有节点为未使用状态，通常将next设置为下一个节点的索引表示空闲
    for (int i = 0; i < MAXSIZE - 1; i++) {
        list->nodes[i].next = i + 1;
    }
    list->nodes[MAXSIZE - 1].next = -1; // 最后一个节点的next设置为-1
}

（2）查找某个位序（不是数组下标，位序是各个结点在逻辑上的顺序）的结点：从头结点出发挨个往后遍历结点，时间复杂度O=(n)

Index FindByPosition(StaticLinkedList *list, int position) {
    if (position < 0 || position >= list->size) {
        return -1; // 位序无效
    }
    int curPosition = 0;
    Index currentIndex = list->head;
    while (currentIndex != -1 && curPosition < position) {
        currentIndex = list->nodes[currentIndex].next;
        curPosition++;
    }
    return currentIndex;
}

（3）在位序为i上插入结点：① 找到一个空的结点，存入数据元素；② 从头结点出发找到位序为i-1的结点；③修改新结点的next；④ 修改i-1号结点的next；

void Insert(StaticLinkedList *list, ElementType element, int position) {
    if (position < 0 || position > list->size) {
        return; // 位序无效
    }

    // 找到一个空闲节点用于插入新元素
    Index newNodeIndex = list->nodes[0].next; 
    if (newNodeIndex != -1) { // 确保还有空闲节点
        list->nodes[0].next = list->nodes[newNodeIndex].next;
        
        list->nodes[newNodeIndex].data = element; // 存储数据
        
        if (position == 0) { // 如果是在头部插入
            list->nodes[newNodeIndex].next = list->head; // 新节点指向原头节点
            list->head = newNodeIndex; // 头节点更新为新节点
        } else {
            Index prevNodeIndex = FindByPosition(list, position - 1); // 找到前一个节点
            list->nodes[newNodeIndex].next = list->nodes[prevNodeIndex].next; // 新节点指向前节点的下一节点
            list->nodes[prevNodeIndex].next = newNodeIndex; // 前节点指向新节点
        }
        list->size++;
    }
}

（4）删除某个结点：① 从头结点出发找到前驱结点；② 修改前驱节点的游标；③ 被删除节点next设为-2；

4.学习总结：

静态链表使用数组模拟链表，每个元素包含数据和游标（下一个节点的索引）。
初始化时需设置一个头节点，并将所有节点串联起来作为一个空闲节点列表。
查找时需要遍历链表直到达到指定位置。这个操作的时间复杂度为O(n)。
插入操作包括寻找空闲节点、连接与前一个节点以及更新链表大小。
静态链表的操作相较于动态链表来说更为复杂，但是在没有动态内存分配的环境下很有用。
在实践中，应用静态链表需要仔细管理空闲节点列表，避免内存的浪费和碎片化。
静态链表虽然不如动态链表灵活，但在某些限制内存的场景下可能非常有用。