静态链表及相关函数

静态链表：用数组描述的链表
静态链表的节点分为两部分，数据域和游标，游标保存下一个元素的下标，相当于链表的指针域，每次通过游标找到下一个元素。
静态链表第一个元素和最后一个元素特殊处理不存数据（非有效元素），静态链表的第一个元素的游标保存备用链表第一个元素的下标（备用链表就是没有用到的元素，在插入时使用备用链表），最后一个元素的游标保存数组第一个有效元素的下标（静态链表空时为0，否则不是0，因为首元素不是有效元素），最后一个有效元素的游标为0。
代码作用有详细注释

main函数和相关头文件，及其相关函数的声明，及其函数的作用

# include <stdio.h>
# include <stdlib.h>
# include <stdbool.h>

# define MAXSIZE 1000

typedef char ElemType;

typedef struct
{
   
    ElemType data;
    int cur;
}Component, StaticLinkList[MAXSIZE];

bool visit(ElemType c); //输出静态链表的一个元素
bool InitList(StaticLinkList space); //静态链表初始化，游标为下一个元素的下标，最后一个元素的下标为第一个有效元素的下标，所以为0
int Malloc_SSL(StaticLinkList space); //找到静态链表第一个空闲元素的下标
int ListLength(StaticLinkList L); //求静态链表的长度
bool ListInsert(StaticLinkList L, int i, ElemType e); //在静态链表第i个元素前插入e
bool ListDelete(StaticLinkList L, int i); //删除静态链表第i个元素
void Free_SSL(StaticLinkList L, int i); //将第i个元素的空间回收，当作下一次分配的第一个空闲元素
bool ListTraverse(StaticLinkList L); //输出静态链表的元素

int main()
{
   
    StaticLinkList L;
    bool i;
    i=InitList(L);
    printf("初始化L后：L.length=%d\n",ListLength(L));

    i=ListInsert(L,1,'F');
    i=ListInsert(L,1,'E');
    i=ListInsert(L,1,'D');
    i=ListInsert(L,1,'B');
    i=ListInsert(L,1,'A');

    printf("\n在L的表头依次插入FEDBA后：\nL.data=");
    ListTraverse(L); 

    i=ListInsert(L,3,'C');
    printf("\n在L的“B”与“D”之间插入“C”后：\nL.data=");
    ListTraverse(L); 

    i=ListDelete(L,1);
    printf("\n在L的删除“A”后：\nL.data=");
    ListTraverse(L); 

    printf("\n");

    return 0;
}

输出静态链表的一个元素

//输出静态链表的一个元素
bool visit(ElemType c)
{
   
    printf("%c", c);
    return true;
}

静态链表初始化，游标为下一个元素的下标，最后一个元素的下标为第一个有效元素的下标，所以为0

//静态链表初始化，游标为下一个元素的下标，最后一个元素的下标为第一个有效元素的下标，所以为0
bool InitList(StaticLinkList space)
{
   
    int i;

    for (i = 0; i < MAXSIZE; ++i)
    {
   
        space[i].cur = i+1; //让每个元素指向下一个元素串成一串
    }
    space[MAXSIZE-1].cur = 0; //最后一个元素保存第一个有效元素下标，目前无有效元素，所以为0

    return true;
}

找到静态链表第一个空闲元素的下标

//找到静态链表第一个空闲元素的下标
int Malloc_SSL(StaticLinkList space)
{
   
    int i;

    i = space[0].cur;
    if (space[0].cur)
    {
   
        space[0].cur = space[i].cur; //将space[0].cur下移一个(即将space[0].cur更新为下一个空闲元素的下标)，即space[0].cur = space[space[0].cur].cur
    }

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

求静态链表的长度

//求静态链表的长度
int ListLength(StaticLinkList L)
{
   
    int i = L[MAXSIZE-1].cur; //i为第一个有效元素的下标
    int j = 0;

    while (i) //当i不为0时，进入循环(因为最后一个有效元素的游标为0，判断是否到了最后一个元素)
    {
   
        j++; //j每次加1，计数
        i = L[i].cur; //更新i
    }

    return j;
}

在静态链表第i个元素前插入e

//在静态链表第i个元素前插入e
bool ListInsert(StaticLinkList L, int i, ElemType e)
{
   
    int j, k, l;
    
    if (i < 1 || i > ListLength(L) + 1)
        return false; //可以在1 - ListLength(L)+1之间插入，在ListLength(L)+1插入，即在最后一个元素后面插入
    k = L[MAXSIZE-1].cur; //让k指向第一个元素
    j = Malloc_SSL(L); //找到静态链表第一个空闲元素的下标

    if (j) //j不为0进入
    {
   
        for (l = 1; l < i - 1; ++l)
        {
   
            k = L[k].cur; //循环i-2次，让k为第i-1个元素的下标
        }
        L[j].data = e; //让j的数据域保存e
        L[j].cur = L[k].cur; //j的游标为k的游标，即第i个与元素的下标
        L[k].cur = j; //更新k的游标为插入元素的下标
        return true;
    }

    return false;
}

删除静态链表第i个元素

//删除静态链表第i个元素
bool ListDelete(StaticLinkList L, int i)
{
   
    int j, k;

    if (i < 1 || i > ListLength(L))
    {
   
        return false;
    }
    k = MAXSIZE - 1;

    for (j = 1; j <= i - 1; ++j)
    {
   
        k = L[k].cur;
    }
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SSL(L, j); //回收第下标为j的这个元素

    return true;
}

将第i个元素的空间回收，当作下一次分配的第一个空闲元素

//将第i个元素的空间回收，当作下一次分配的第一个空闲元素
void Free_SSL(StaticLinkList L, int i)
{
   
    L[i].cur = L[0].cur;
    L[0].cur = i;
}

输出静态链表的元素

//输出静态链表的元素
bool ListTraverse(StaticLinkList L)
{
   
    int i;
    if ( !(ListLength(L)) )
        return false;

    i = L[MAXSIZE-1].cur;
    while (i)
    {
   
        visit(L[i].data);
        i = L[i].cur;
    }
    printf("\n");

    return true;
}