静态链表——数据结构预习

其实一般有单链表的话，应该用不着静态链表。然而并不是什么编程语言都有指针，这时静态链表可以起到单链表的作用。静态链表的思考方式还蛮巧妙。
特点：
1、静态链表是一个足够大的结构体数组，大概是分成数据+游标的形式。数组里面有数据的为一部分（姑且叫数据域吧），没有数据的（即未使用的数组元素）叫做备用链表。
2、数组的第0个和最后1个元素作特殊处理，它们的data不存放数据。
3、数组的第0个元素的游标存放备用链表第1个节点的下标。
4、数组的最后一个元素的游标存放数据域第1个节点的下标（相当于单链表的头节点）

优点：和动态链表一样，删除和插入元素时间复杂度低
不足：和数组一样，需要提前分配一块较大的空间、
可以参考一下这篇文章https://www.cnblogs.com/dongry/p/10210609.html
额……建议画图理解，图画得步骤较多，不是很难画，自己动手吧。👀
强烈推荐这篇https://blog.csdn.net/qq_37668436/article/details/104519005?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-1写得很棒，但是不自己动手写是学不会的。主要参考这篇文章做笔记。

image.png

#include <iostream>
#include<stdlib.h>
using namespace std;
constexpr auto maxsize = 7;//本来是#define maxsize 7，被vs建议修改为这样

typedef struct node
{
    char data;//数据
    int cur;//游标，模拟链表的指针
}Node[maxsize];
void init(Node L);//创建备用链表
int getlength(Node L);//不包括头尾节点，求链表元素个数/数据域长度
int get(Node L);//提取空闲变量，分配下标
void insert(Node L,int i,char newdata);//静态链表中i位置插入一个元素
void Free(Node L, int k);//释放节点
bool Delete(Node L, int i, char* key);//删除第i个元素
void Traverse(Node L);//遍历

int main()
{
    Node L;
    cout << "初始化链表：";
    init(L);
    cout << "初始化后链表长度：" << getlength(L) << endl;
    cout << "插入a、b、c、d、e" << endl;
    insert(L, 1, 'a');
    insert(L, 1, 'b');
    insert(L, 1, 'c');
    insert(L, 1, 'd');
    insert(L, 1, 'e');
    cout << "插入后的长度：" << getlength(L) << ",遍历链表得各元素分别为：";
    Traverse(L);
    char key;
    Delete(L, 2, &key);
    cout << "删除的元素值为：" << key<<endl;
    cout << "插入后的长度：" << getlength(L) << ",遍历链表得各元素分别为：";
    Traverse(L);

    return 0;
}
void init(Node L)
{
    for (int i = 0; i < maxsize - 1; i++)
    {
        L[i].cur = i + 1;//将每个数组分量链接到一起,最后一个元素指向的是尾节点
    }
    L[maxsize - 1].cur = 0;//备用链表的最后一个空元素的cur指向0，这一行不能省。
}
int getlength(Node L)
{
    int i = L[maxsize - 1].cur;//从倒数第一个数据域元素开始遍历，很想单链表的
    int j = 0;
    while (i)
    {
        j++;
        i = L[i].cur;//相当于就是p = p->next
    }
    return j;
}
int get(Node L)//新插入一个元素之后需要重新修改L[0].cur的值
{
    //若备用链表非空，则返回分配的结点下标，否则返回 0（当分配最后一个结点时，该结点的游标值为 0）即特点3的体现
    int i = L[0].cur;//获取可以插入的位置 
    if (i)//如果不是空表
    {
        L[0].cur = L[i].cur;//更新L[0]为刚才插入位置的cur，用来记录当前链表新的可插入位置 
    }
    return i;//返回可插入位置 
}
void insert(Node L, int i, char newdata)
{
    if (i<1 || i>getlength(L) + 1)//判断插入点是否合理
    {
        exit(1);
    }
    //找可插入的地方 
    int j = get(L);// ！！！修改了上文说的第一个数，文章见链接
    int k = maxsize - 1; //找链表头 
    if (j)
    {//定位到插入的位置的前一个位置k 
        for (int l = 1; l <= i - 1; l++)
        {
            k = L[k].cur;//相当于就是p = p->next
        }
        //插入操作 
        L[j].data = newdata;
        L[j].cur = L[k].cur;
        L[k].cur = j;
    }
}
void Free(Node L, int k)
{
    L[k].cur = L[0].cur;//这应该是游标不能重复，换一下
    L[0].cur = k;//被删除元素已经变成了备用链表的第一个节点了
}
//删除第i个元素

bool Delete(Node L, int i, char* key)
{
    if (i < 1 || i > getlength(L))
    {
        return false;
    }
    //找链表头 
    int k = maxsize - 1;
    //定位到删除的地方的前一个 
    for (int l = 1; l <= i - 1; l++)
    {
        k = L[k].cur;
    }
    int j = L[k].cur;//由k找到j，像链表的next域，上一个找到下一个的寻法
    *key = L[j].data;
    L[k].cur = L[j].cur;//换一下游标免得重复
    Free(L, j);
    return true;
}

//遍历
void Traverse(Node L)
{
    int k = maxsize - 1;
    while (L[k].cur)
    {
        k = L[k].cur;
        cout<<L[k].data<<" ";
    }
    printf("\n");
}