静态链表

1.用数组描述的链表叫做静态链表，每个元素由数据域data和游标cur组成
2.对数组第一个元素和第二个元素特殊处理，不存数据。通常把未被使用的数组元素称为备用链表。
3.数组第一个元素，即下标为0的元素的cur存放备用链表第一个结点的下标；数组最后一个元素的cur存放第一个有数值的元素的下标，相当于链表中的头结点作用(遍历时先从以此结点为开始)
4.当整个链表为空时，则最后一个元素的cur为0
5.插入时为了辨明数组中哪些分量未被使用，解决办法是将所有未被使用过的即已被删除的分量用游标链成一个备用的链表,每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点
一个空的静态链表如下图所示：

静态链表
当存入数据时，其各个结点的cur如下图所示：
image.png
解释：
“甲”存有下一元素“乙”的游标，而乙为最后一个有值元素，所以它的cur为0，因为“甲”为第一个有值元素，所以最后一个元素的游标cur为1，而第一个元素因空闲空间的第一个元素下标为7，所以它的cur为7

StaticLinkList.h

#pragma once
// 函数结果状态代码
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2
#define MAXSIZE 100     //链表最大长度

//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;

//数据类型
typedef int ElemType;

typedef struct SNode
{
    ElemType data;
    int cur;        //游标（cursor），为0时表示无指向
}StaticLinkList;

//将一维数组space中各分量链成一个备用链表
//space[0].cur为头指针，“0”表示空指针
Status InitList(StaticLinkList L[MAXSIZE]);

//若备用链表非空，则返回分配的结点下标，否则返回0
int Malloc_SLL(StaticLinkList L[MAXSIZE]);

//返回链表长度
int ListLength(StaticLinkList L[]);

//在第i个结点前插入新的数据元素e
Status ListInsert(StaticLinkList L[], int i, ElemType e);

//将第i个结点回收到备用链表
void free_SSL(StaticLinkList L[], int i);

//删除静态链表第i个数据元素e
Status ListDelete(StaticLinkList L[], int i);

//遍历
void ListTraverse(StaticLinkList L[]);

优缺点：
1.在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除元素操作需要移动大量元素的缺点
2.未解决连续存储分配带来的表长难以确定的问题，失去了顺序存储结构随机存取的特性

StaticLinkList.cpp

#include "StaticLinkList.h"
#include <iostream>
using namespace std;

//将一维数组space中各分量链成一个备用链表
//space[0].cur为头指针，“0”表示空指针
Status InitList(StaticLinkList L[MAXSIZE])
{
    int i;
    for (i = 0; i < MAXSIZE - 1; i++)
    {
        L[i].cur = i + 1;
    }
    L[MAXSIZE - 1].cur = 0; //目前静态链表为空，最后一个元素的cur为0
    cout << "初始化成功" << endl;
    return OK;
}

//若备用链表非空，则返回分配的结点下标，否则返回0
int Malloc_SLL(StaticLinkList L[MAXSIZE])
{
    int i = L[0].cur;           //数组第一个元素的cur存的值，即第一个备用空闲的下标
    if (L[0].cur)
        L[0].cur = L[i].cur;//原来第一个备用的空闲要被使用了，则将其下一个分量作为备用空闲的下标

    return i;
}

//返回链表长度
int ListLength(StaticLinkList L[])
{
    int i = MAXSIZE - 1;        //最后一个元素的下标，该元素的cur存了链表第一个元素的下标
    int length = 0;
    while (L[i].cur)
    {
        i = L[i].cur;
        length++;
    }

    return length;
}

//在第i个结点前插入新的数据元素e
Status ListInsert(StaticLinkList L[], int i, ElemType e)
{
    if (i<1 || i>ListLength(L) + 1)
    {
        return ERROR;
    }
    int j = Malloc_SLL(L);          //找到第一个备用空闲下标，并将新的备用空闲下标更新

    if (j)
    {
        L[j].data = e;              //将数据赋值给新插入结点的data

        int pre = MAXSIZE - 1;          //最后一个元素的下标
        for (int k = 1; k <= i - 1; k++)
        {
            pre = L[pre].cur;       //找到第i个元素之前的位置的下标
        }
        L[j].cur = L[pre].cur;      //第i个元素之前的cur赋值给新元素的cur
        L[pre].cur = j;             //新元素的下标赋值给第i个元素之前元素的cur

        return OK;
    }
    return ERROR;

}

//将第i个结点回收到备用链表（类似一个插入操作，即将此结点插入到备用空闲链表中）
void free_SSL(StaticLinkList L[], int i)
{
    L[i].cur = L[0].cur;            //将第一个元素curcur值赋给要删除的分量cur，让原来的备用空闲结点排在现在要回收的结点的后面
    L[0].cur = i;                   //把要删除的分量下标赋值为第一个元素的cur，让此结点成为备用空闲结点
}

//删除静态链表第i个数据元素e：找到删除结点的前一个结点，让此结点的cur等于删除结点的cur即可
Status ListDelete(StaticLinkList L[], int i)
{
    if (i<1 || i>ListLength(L))
    {
        return ERROR;
    }
    int h = MAXSIZE - 1;
    for (int i = 1; i <= i - 1; i++)
    {
        h = L[h].cur;               //找到要删除结点的前一个结点
    }
    int j = L[h].cur;               //要删除的结点
    L[h].cur = L[j].cur;
    free_SSL(L, j);                 //将删除的结点回收到备用链表

    return OK;
}

//遍历
void ListTraverse(StaticLinkList L[])
{
    int i = MAXSIZE - 1;        //最后一个元素的下标，该元素的cur存了链表第一个元素的下标
    while (L[i].cur)
    {
        i = L[i].cur;
        cout << L[i].data << " ";
    }
    cout << endl;
}

main.cpp

测试：

#include <iostream>
#include "StaticLinkList.h"

using namespace std;

int main(int argc, char** argv)
{
    StaticLinkList L[MAXSIZE];
    InitList(L);                //初始化

    ListInsert(L, 1, 1);        //在第一个位置插入1
    ListInsert(L, 2, 2);
    ListInsert(L, 3, 3);
    ListTraverse(L);            //遍历

    cout << "链表长度:" << ListLength(L) << endl;   //链表长度

    ListInsert(L, 2, 4);        //插入
    ListInsert(L, 3, 5);

    ListTraverse(L);
    cout << "链表长度:" << ListLength(L) << endl;
    ListDelete(L, 1);           //删除
    ListDelete(L, 1);

    ListTraverse(L);            //遍历
    cout << "链表长度:" << ListLength(L) << endl;

    return 0;
}