静态链表

我们都知道C语言的强大在于其有指针可以直接操作内存，因此可以将链表完美的实现出来；但在C语言之前的一些语言并没有指针，于是他们就想出了静态链表。

所谓的静态链表就是指用数组来描述链表，这也称作游标实现法。

原理

静态链表图

以静态单链表举例，我们用数组存储数据，通过游标来模拟指针。每一个数组元素的游标用来存放其直接后继结点的下标，这样就组成了链表。

和之前一样表的0位不放数据用做特殊用途，同时数组的最后一位也不放数据用做特殊用途。

存放数据的数组元素按顺序组成和上篇类似的单链表，并将链表1号结点的下标放到数组最后一位的游标里，也就是说数组最后一位元素相当于链表的头结点；而对于那些未使用的数组元素，我们也将其链起来，称为备用链表，备用链表的首个结点的下标放到数组0位的游标里。

实现

构建结点

/* C语言要加这些，C++不用 */
#include <stdbool.h>
typedef struct Node Node;

typedef int Elem_Type;
#define MAX_SIZE 20
struct Node // 结点
{
    Elem_Type data; // 数据域
    int cursor; // 指针域
} list[MAX_SIZE]; // 声明头指针
typedef struct Node Static_Link_List; // 方便区分代码中使用链表

初始化和清空

因为是通过数组来描述链表，因此初始化和清空操作一样：清空数据域，串联备用链表，将数组的最后一位的指针域指向数组的0位。

void init_list(Static_Link_List list[])
{
    for(int i=0 ; i<MAX_SIZE-1 ; i++) // 全是备用链表
    {
        list[i].data = 0;
        list[i].cursor = i+1; 
    }
    /* 表明空表 */
    list[MAX_SIZE-1].data = 0;
    list[MAX_SIZE-1].cursor = 0;
}

void clear_list(Static_Link_List list[])
{
    init_list(list);
}

判空

数组的最后一位的指针域是否指向数组的0位。

bool list_is_empty(Static_Link_List list[])
{
    if (list[MAX_SIZE-1].cursor == 0)
    {
        return true;
    }
    return false;
}

获取表长

遍历链表获取表长。

int list_length(Static_Link_List list[])
{
    int count = 0; // 计数
    int temp = list[MAX_SIZE-1].cursor; // 下标模拟指针
    /* 遍历计数 */
    while(temp != 0)
    {
        count++;
        temp = list[temp].cursor;
    }
    return count;
}

按值查找

按值查找是采用遍历的方式，因此时间复杂度还是O(n)。

int list_locate_elem(Static_Link_List list[],Elem_Type e)
{
    int temp = list[MAX_SIZE-1].cursor; // 下标模拟指针
    int count = 0;
    /* 定位遍历 */
    while(temp != 0)
    {
        count++;
        if(list[temp].data == e) // 找到目标
        {
            return count;
        }
        temp = list[temp].cursor;
    }
    return 0;
}

按位查找并获取

虽然这是数组来描述的，但按位查找也要遍历，因此时间复杂度同样为O(n)。

bool list_get_elem(Static_Link_List list[],int i,Elem_Type *e)
{
    int count = 1;
    int temp = list[MAX_SIZE-1].cursor; // 下标模拟指针
    /* 定位遍历 */
    while(temp!=0 && count<i)
    {
        temp = list[temp].cursor;
        count++;
    }
    /* 定位失败 */
    if(temp==0 || count>i) // 没找到元素或传入的i<1
    {
        return false;
    }

    *e = list[temp].data;
    return true;
}

插入

插入操作分两大步：

从备用链表中取出空的结点，模仿动态链表的申请空间。
实现插入，参考动态链表的插入操作

静态链表插入图1

bool list_insert(Static_Link_List list[],int i,Elem_Type e)
{
    int count = 1;
    int temp = MAX_SIZE-1; // 要插入的前一个结点
    /* i错误，空间不足 */
    if(count>i || list[0].cursor==MAX_SIZE-1) // 传入的i<1或无空间插入
    {
        return false;
    }
    /* 定位遍历 */
    while(temp!=0 && count<i)
    {
        temp = list[temp].cursor;
        count++;
    }
    /* 定位失败 */
    if(temp==0) // 没找到元素
    {
        return false;
    }
    /* 插入 */
    list[list[0].cursor].cursor = list[temp].cursor; // 尾部连接
    list[temp].cursor = list[0].cursor; // 头部连接
    list[list[0].cursor].data = e; // 填入数据
    list[0].cursor = list[list[0].cursor].cursor; // 从备用链表中删除
    return true;
}

删除

同插入操作，所有删除也分两大步：

找到该结点并从链表中删除，与动态链表的删除同理
将删掉的结点放入备用链表，类似释放空间

静态链表删除图1

bool list_delete(Static_Link_List list[],int i,Elem_Type *e)
{
    int count = 1;
    int temp = MAX_SIZE-1; // 要删除的上一结点的下标
    int delete_node = NULL; // 要删除的结点的下标
    /* 定位遍历 */
    while(temp!=0 && count<i)
    {
        count++;
        temp = list[temp].cursor;
    }
    /* 定位失败 */
    if(temp==0 || count>i) // 没找到元素或传入的i<1
    {
        return false;
    }
    /* 找到要删的结点并取出数据 */
    delete_node = list[temp].cursor;
    *e =list[delete_node].data;
    /* 从链表中删除 */
    list[temp].cursor = list[delete_node].cursor;
    /* 加入备用链表 */
    list[delete_node].cursor = list[0].cursor;
    list[0].cursor = delete_node;

    return true;
}

头插法

/* 方法一 */
void list_push_front(Static_Link_List list[],Elem_Type e)
{
    int push_node = list[0].cursor; // 要插入的
    list[push_node].data = e;
    /* 从备用链表中取出 */
    list[0].cursor = list[push_node].cursor;
    /* 插入链表 */
    list[push_node].cursor = list[MAX_SIZE-1].cursor;
    list[MAX_SIZE-1].cursor = push_node;
}
/* 方法二 */
void list_push_front(Static_Link_List list[],Elem_Type e)
{
    list_insert(list,1,e);
}

尾插法

/* 方法一 */
void list_push_back(Static_Link_List list[],Elem_Type e)
{
    int temp = MAX_SIZE-1; // 找到最后一个结点
    int push_node = list[0].cursor; // 要插入的
    list[push_node].data = e;
    /* 从备用链表中取出 */
    list[0].cursor = list[push_node].cursor;
    /* 插入链表 */
    while(list[temp].cursor != 0)
    {
        temp = list[temp].cursor;
    }
    list[temp].cursor = push_node;
    list[push_node].cursor = 0;
}
/* 方法二 */
void list_push_back(Static_Link_List list[],Elem_Type e)
{
    list_insert(list,list_length(list)+1,e);
}

其他部分

void create_10elem_list(Static_Link_List list[])
{
    for(int i=10 ; i>0 ; i--)
    {
        list_push_front(list,i); // 头插法插入10个元素
    }
}

void print_list(Static_Link_List list[])
{
    int temp = list[MAX_SIZE-1].cursor;
    while(temp != 0)
    {
        if(sizeof(Elem_Type) == 4)
        {
            printf("%d ",list[temp].data);
        }
        temp = list[temp].cursor;
    }
    printf("\n");
}