静态链表的定义：
静态链表：分配一整片连续的内存空间，各个结点集中安置，逻辑结构上相邻的数据元素，存储在指定的一块内存空间中，数据元素只允许在这块内存空间中随机存放，这样的存储结构生成的链表称为静态链表。也就是说静态链表是用数组来实现链式存储结构，静态链表实际上就是一个结构体数组
举例：通过a[1]中存放的游标变量3可找到存放的数据元素5的后继元素为3，再通过a[3]中存放的游标变量2可找到存放数据元素3的后继数据为2，以此类推，直到某元素的游标变量为0即可停止（注：a[0]为头结点不存储数据元素）
备用链表：
在链表中，我们不可能恰好将所有的位置都使用，那么就会出现空闲的位置，用来连接这些空闲位置的链表，我们就将其称之为备用链表，他的作用为：回收数组中目前没有适用的空间。
那么此时就相当于有两个链表，实现不同的功能，一个用来连接数据，另一个用来连接数组中的空闲空间。
一般情况下，备用链表的表头位于数组下标为0(a[0])的位置，而数据链表的表头位于数据下标为1(a[1])的位置。
如上图所示：备用链表的连接顺序依次是：a[0],a[2],a[4]数据链表的连接顺序依次是a[1],a[3],a[5]
静态链表添加数据的实现过程：
以存储{1,2,3}为例，分析过程如下：
数据未存储前，数据链表当前是不存在的，所有的游标都存在于备用链表中，如下所示：
下面我们要进行的工作是将1存储进去，此时既然要存储数据，因此必须产生数据链表，那么如何产生数据链表呢？方法：备用链表摘除结点，以便存储新数据，而最简便的方法就是摘除a[0]的后继节点，即为下标为1(a[1])的位置。
将1存放进去：
将2存放进去：
将3存放进去：
定义静态链表：
方法一：
#define Maxsize 10//定义静态链表的最大长度 struct Node//定义静态链表结构类型 { ElemType data; int next;//游标：为下一个数据元素的数组下标，类似于指针 }; void testSLinkList() { struct Node a[Maxsize];//数组a作为静态链表 }
方法二：
#define Maxsize 10 struct Node { ElemType data; int next; }; typedef struct Node SLinkList[Maxsize];//这里相当于SLinkList可用来定义为一个数组，数组长度为Maxsize,类型为Node void teastLinkLIst() { SLinkList a;//等价于struct Node a[Maxsize] }
验证其两种方式是否正确：
#include<stdio.h> #define Maxsize 10 struct Node { int data; int next; }; typedef struct { int data; int next; }SLinkList[Maxsize]; void testSLinkList() { struct Node x; printf("sizeX=%d\n", sizeof(x)); struct Node a[Maxsize];//定义了一个数组a，其数组长度为Maxsize,类型为struct Node printf("sizeA=%d\n", sizeof(a)); SLinkList b;//声明变量b,其为数组，数组长度为Maxsize，数组类型为struct类型 printf("sizeB=%d\n", sizeof(b)); } int main() { testSLinkList(); return 0; }
通过输出结果我们会知道两种方法都可以的。
初始化静态链表：
方法：将静态链表0位置的结点设置为头结点，用它来对已申请的结点进行管理。该结点的特点是数据域不存数据，游标为第一个申请结点所对应的下标（如果该静态链表还未申请结点来存放数据，那么该值为-1表示该静态链表为空。）
typedef struct { ELemType data; int next; }ListNode; void InitSLinkList(StaticList& space) { int = 0;//数组下标 for (i = 0; i < Maxsize; i++) { space[i].next = i + 1;//游标的值为下一个数组元素的下标值 space[i].data = 0;//将链表中的每个数据置为0，防止脏数据 } //space[Maxsize - 1]表示链表的表尾元素，表尾元素指向下标为0的数组元素 space[Maxsize - 1].next = 0; }
结点数据的显示：
#define Maxsize 10 struct SLinkList { ElemType data; int next; }; void showSLinkList(StaticList& space) { int i = space[0].cur;//从头结点开始搜索 while (i != -1) { printf("%c-->", space[i].data); i = space[i].next; } print("NUl.\n"); }
结点申请：
int mallocArr(StaticList& space) { int i = space[0].next; //如果备用链表是空链表，那么返回分配结点的下标，否则返回0 if (space[0].next) { space[0].next = space[i].next; } return i; }
静态链表的遍历：
void SL_ergodic(StaticList& space) { int i = space[Maxsize - 1].next; while (i) //通过循环遍历 { printf("%c ", space[i].data);//输出链表中的数据 i = sapce[i].next; } printf("\n"); }
静态链表的清空：
void ClearSL(StaticList& space) { int i; for (i = 0; i < MAXSIZE - 1; i++) space[i].next = i + 1; space[MAXSIZE - 1].next = 0; }
向静态链表中添加元素：
//head表示头结点在数组中的位置，add表示插入元素的位置，num表示要插入的数据 void insertspace(StaticList& space,int head int add,int num) { //使遍历数组的中间变量等于头结点在数组中的位置，也相当于是从头结点开始遍历数组 int temp_head = head; int i = 0, insert = 0; //找到位序为i-1的数据 for (i = 1; i < add; i++)//注意位序从一开始而下标从0开始 { temp_head = space[temp_head].next; } insert = mallocspace(space);//为插入的元素申请空间 space[insert].data = num; space[insert].next = space[temp_head].next;//新插入结点的游标等于其直接前驱结点的游标 space[temp_head].next = insert;//直接前驱结点的游标等于新插入结点所在数组中的下标 } //实现插入数的内存开辟 int malloc_space(StaticList& space) { int i = space[0 ].next; if (space[0].next) { space[0].next = space[i].next; } return i; }
释放空间：
void Free_SP(StaticList& space, int k) { space[k].cur = space[1].cur; space[1].cur = k; }
查找静态链表中的元素：
int selectNum(StaticList &space, int num) { int temp_head = maxSize-1; while (space[temp_head].next != 0)//通过循环遍历数组元素 { if (space[temp_head].data == num) { return temp_head; } temp_head = space[temp_head].next; } //判断表尾结点是否为我们要找的元素 if (space[temp_head].data == num) { return temp_head; } return -1;//表示在链表中没有找到要查找的元素 }
修改静态链表的元素：
void alterElem(StaticList& space, int old_ELem, int new_ELem) { int num=selectnum(space,old_ELem)//修改之前先进行查找 if (num == -1) { printf("没有需要修改的元素"); return; } //直接修改该元素为我们想要修改的 space[add].data = new_Elem; }
静态链表元素的删除：
int deletELem(StaticList& space, int num) { int temp_head=maxSize-1; int del = 0; int new_head = 0; //寻找要删除结点的位置：要删除先查找 while (space[temp_head].data != num) { temp_head = space[temp_head].next; //当tempBody为0时，表示链表遍历结束，说明链表中没有存储该数据的结点 if (temp_head == 0) { printf("链表中没有此数据"); return 0; } } del = temp_head; temp_head = maxSize-1; //删除表首结点 if (del == space[maxSize-1].next) { new_head = space[del].next; space[maxSize-1].next=new_head; freeArr(space, del); } else { //找到要删除元素的前驱结点 while (space[temp_head].next != del) { temp_head = space[temp_head].next; } space[temp_head].next = space[del].next; freeArr(space, del);//释放已经删除元素的内存空间 } }
静态链表和动态链表的关系：
在使用静态链表存储数据之前，需要申请足够大的一整片内存空间，也就是说，静态链表存储的数据元素的个数当申请空间的时候就已经确定，并且此后不能发生改变，静态链表是在固定大小的存储空间内随机存储各个数据元素，这就导致静态链表无法和动态链表那样直接对链表进行操作，因为它包含两条链表，存储数据的和存储空闲位置的。
注：有的静态链表最后一个数组下标存放的是头结点，而有的静态链表最后一个数组下标和普通下标的作用相同。
而使用动态链表存储数据，不需要预先申请内存空间，而是在需要的时候才向内存申请，因此，它存储数据元素的个数是可以改变的，而且在对动态链表进行操作的时候，我们只需要操控一条链表，当表中添加或删除数据元素时，你只需要通过malloc或free函数来申请或释放空间。
