数据结构：静态链表

什么叫静态链表？

用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法。

如何用数组了描述呢 ？
简单的说，就是我们会先创建一个固定的数组，然后数组中的每一个元素都使用一个结构体，该结构体包括两个元素，一个是要储存的数据，一个是游标。

什么是游标？
游标是用来记录链表的下一个结点的位置（节点所在数组中的下标）。

这都是一些比较抽象的概念，不太好理解，也很容易搞乱，下面我结合这些图简单的说一些。

我的理解

大家可以先建立几个概念，数组和链表可不要搞混了。
首先这个数组，其实就是我们用来储存用的。那链表呢， 我个人的理解，指得是数组已经使用的这一部分（剩余没使用的那部分暂且叫做备用链表）。我们使用这个数组下标为0的这个位置来当做链表的头结点，所以说这个位置不进行实际的储存。

我们在进行存储的时候，是按照数组下标的位置把数据逐一存储进数组的（数组的第0个位置不做实际的存储功能，下面会说到），也就是说我们要把‘甲’，‘乙’，‘丙’，‘丁’，‘戊’，‘己’，‘庚’ 这七个字储存起来，使用的是数组的下标1到6的连续位置，但是在数组中的连续位置，不代表他在链表中的位置，打个比方说，我们要继续存储一个‘辛’这个字，但是我要把它存到甲和乙中间，他的数组的位置就是在下标为7的位置，但是他的链表位置是在甲和乙中间，这是通过游标来体现出来的，下面会说到

好的，我们分析一下
在初始化完这个数组之后，所有的位置上都没有储存数据，然后每个位置的游标表示数组的下一个元素，也就是第0个元素的游标为1，第1个元素的游标为2....
进行了存储之后，如上图，我们看几个比较关键的位置，第0个元素的游标变味了7，第6个元素的游标为0，第999个元素的游标为1，这代表什么意思呢？
我们在进行插入数据操作的时候，第0个元素的游标总是指向下次储存要用的那个位置，数组的最后一个元素也就是999这个位置的元素，他的游标指向链表的第一个节点（不包括头结点的）在数组中的下标。然后链表的最后一个节点的游标要指向0，因为没有下一个了嘛，所以我们看到第6个元素的位置的游标是0。

代码实现

理论差不多说完了，下面该说具体的实现了，网上的实现代码很多，直接找了一份代码，咱们一起看一下代码吧

int main(int argc, const char * argv[]) {  
    StaticLinkList list[MAXSIZE];
    // 初始化数组中的数据
    createLinkList(list);
    
    for (int i = 0; i < 2; i ++) {
        ListInsert(list, 1, 100+i);
    }
    return 0;
}

我们在循环中执行了两次的插入操作，ListInsert方法中的参数1指的是每次都是把数据插在链表的第1个结点之前，我们先推测一下结果。

我们先存了一个100这个数字，又存了101这个数字，因为之前初始化之后并没有进行别的存储，所以完成存储之后，因为按照之前的说法，数组的第1个元素应该放的100，第2个位置才是101，但是我们在储存的时候，是把要插入的数据插入到链表第一个元素的前面，所以从链表的角度看，101应该是第一个节点，100是第二个。那要怎么表现出来呢？结合我们上面说的，999这个位置的游标应该指向链表第一个节点，也就是游标应该为2，数组下标2的元素因为他是链表的第一个节点，所以他的游标应该指向链表第二个节点，也就是数组下标1。链表就两个节点，所以最后一个节点的游标要指向0. 然后数组下标0的位置的游标指向了下一个可用的存储位置3。

结果跟我们之前分析的是一致的。

只要理清楚了这些思路之后，其他的代码看起来也就容易很多了。

比如说下面这个计算链表长度的方法

int linkLength(StaticLinkList list[]) {
    int j = 0;
    int i = list[MAXSIZE-1].cur;
    while (i) {
        i = list[i].cur;
        j ++;
    }
    return j;
}

先拿到数组的最后一个元素游标的数值，如果是0，就说明还没有储存呢，索引链表长度就是0，如果已经储存过了，所以得到i的值就不是0，通过一个while循环，一个个的遍历链表结点，直到链表最后一个结点的游标又是0，跳出循环，然后通过一个j来标识循环次数，也就是链表长度。

关于静态链表就说这么多吧，更多的内容大家可以上网搜一下。

下面我把使用的代码放上，主要是实现了插入操作，删除暂时没做，大家可以看懂了插入然后自己写一下删除，代码上我尽可能详细的做了注释，大家可以看看代码 ~

//  main.c
//  链表
//  Created by sunxiaobin on 2018/6/15.

#include <stdio.h>
#define MAXSIZE 1000
typedef int ElemType;
typedef struct {
    ElemType data;
    int cur;
}StaticLinkList;

// 声明
void createLinkList(StaticLinkList list[]);
int linkLength(StaticLinkList list[]);
int Malloc_SLL(StaticLinkList list[]);
int ListInsert(StaticLinkList L[], int i, ElemType e);

int main(int argc, const char * argv[]) {
    StaticLinkList list[MAXSIZE];
    
    // 初始化数组中的数据
    createLinkList(list);
    
    for (int i = 0; i < 2; i ++) {
        ListInsert(list, 1, 100+i);
    } 
    return 0;
}

void createLinkList(StaticLinkList list[]){
    int i;// i就代表数组下标
    for (i = 0; i < MAXSIZE-1; i ++) {
        list[i].cur = i + 1;  // cur存放的是下一个结点的下标
    }
    list[MAXSIZE-1].cur = 0; //
    
}

// 求链表长度
int linkLength(StaticLinkList list[]) {
    int j = 0;
    int i = list[MAXSIZE-1].cur;
    while (i) {
        i = list[i].cur;
        j ++;
    }   
    return j;
}

// 得到备用链表的第一个元素下标
int Malloc_SLL(StaticLinkList list[]) {
    
    int i = list[0].cur;
    
    if (list[0].cur)
        // 更新头结点的游标, 原来头结点的游标指向i这个位置,
        // 但是这个位置要进行了存储 , 被使用了,
        // 头结点应该把游标更新到新的备用链表的第一个元素, 也就是刚刚使用了这个i位置的元素的游标指向的位置.
        list[0].cur = list[i].cur;
    
    return i;
}

// 在静态链表L中第i个元素之前插入新的数据元素e
int ListInsert(StaticLinkList list[], int i, ElemType e) {
    
    int k = MAXSIZE - 1; // 数组的最后一个元素
    
    //判断要插入的位置是不是合法范围
    if (i<1 || i>linkLength(list)+1) return 0;
    
    int j = Malloc_SLL(list); // 得到备用链表的第一个元素下标
    
    if (j) {  // 如果元素存在,(不存在就说明数组已经满了)
        
        list[j].data = e;// 先把e存进来,然后通过改变某几个结点的游标
        
        // 这个for循环内, 如果是第一次存储的话根本不走
        //
        for (int l = 1; l<=i-1; l++) {
            // 得到第i-1个结点在数组中的下标
            k = list[k].cur;
        }
        
        list[j].cur = list[k].cur; // 将第i-1个元素的cur设置为新加的这个结点的下标，将新加的这个结点的下标设置为之前第i-1个元素存储的cur值
        list[k].cur = j;
    
        return 1;
    } 
    return 0;    
}