静态链表

/**
 * data：用来保存数据
 * cur：用来保存下一个元素所在的下标
 */
typedef struct _StaticLinkList
{
    ElemType data;
    int cur;
} StaticLinkList, *PStaticLinkList;

/**
 * 初始化链表
 */
Status InitList(PStaticLinkList space)
{
    int i;

    // 将所有存储数据的data赋值为0
    // 将存储下一个元素的cur赋值为下一个数组的下标
    for (i = 0; i < MAXSIZE - 1; i ++)
    {
        space[i].data = 0;
        space[i].cur = i + 1;
    }

    // 数组的最后一个元素保存开始位置的下标
    space[MAXSIZE - 1].data = 0;
    space[MAXSIZE - 1].cur = 0;

    return OK;
}

/**
 * 查找可以写入的位置
 */
int Malloc_SLL(PStaticLinkList space)
{
    // 数组下标0的cur保存了第一个空闲的下标
    int i = space[0].cur;

    // 如果下标有效，则把空闲元素的cur赋值给数组下标0的cur
    if (space[0].cur)
    {
        space[0].cur = space[i].cur;
    }

    // 返回空闲的下标
    return i;
}

/**
 * 计算链表的长度
 */
int ListLength(PStaticLinkList L)
{
    int j = 0;
    // 从数组最后一个元素的cur中获取链表的开始元素的下标
    int i = L[MAXSIZE - 1].cur;

    // 遍历链表
    while (i)
    {
        i = L[i].cur;
        j ++;
    }

    return j;
}

/**
 * 在第i个位置之前插入数据e
 */
Status ListInsert(PStaticLinkList L, int i, ElemType e)
{
    int j, k, l;

    k = MAXSIZE - 1;
    // 插入的位置需要合理
    if (i < 1 || i > ListLength(L) + 1)
    {
        return ERROR;
    }
    // 找到第一个空闲的位置
    j = Malloc_SLL(L);

    // 判断是否有
    if (j)
    {
        L[j].data = e;

        // 查找到插入的位置
        for (l = 1; l < i - 1; l ++)
        {
            k = L[k].cur;
        }

        // 改变链表的指针
        L[j].cur = L[k].cur;
        L[k].cur = j;

        return OK;
    }

    return ERROR;
}

/**
 * 让第i个位置成为空闲
 * 删除数据后，被删除的位置会成为空闲位置，空闲位置的下标会放入第0个元素的cur当中
 */
void Free_SSL(PStaticLinkList L, int i)
{
    L[i].cur = L[0].cur;
    L[0].cur = i;
}

/**
 * 删除第i个位置的元素
 */
Status ListDelete(PStaticLinkList L, int i)
{
    int j, k;

    // 判断删除的位置是否合理
    if (i < 0 || i > ListLength(L))
    {
        return ERROR;
    }

    k = MAXSIZE - 1;

    // 查找删除的位置
    for (j = 1; j <= i - 1; j ++)
    {
        k = L[k].cur;
    }

    // 改变指针
    L[j].data = 0;
    j = L[k].cur;
    L[k].cur = L[j].cur;

    // 让被删除元素成为空闲
    Free_SSL(L, j);

    return OK;
}

/**
 * 打印数组中的每个元素
 */
void print(PStaticLinkList L)
{
    printf("===============\r\n");

    for (int i = 0; i < MAXSIZE; i ++)
    {
        printf("%d:[%d]->%d\r\n", i, L[i].data, L[i].cur);
    }
}

/**
 * 遍历链表
 */
void foreach(PStaticLinkList L)
{
    printf("===================\r\n");

    int k = L[MAXSIZE-1].cur;

    while(k)
    {
        printf("%d:[%d]->%d\r\n", k, L[k].data, L[k].cur);
        k = L[k].cur;
    }
}