数据结构之静态链表

静态链表的定义：

静态链表：分配一整片连续的内存空间，各个结点集中安置，逻辑结构上相邻的数据元素，存储在指定的一块内存空间中，数据元素只允许在这块内存空间中随机存放，这样的存储结构生成的链表称为静态链表。也就是说静态链表是用数组来实现链式存储结构，静态链表实际上就是一个结构体数组

举例：通过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作为静态链表
}
1
2
3
4
5
6
7
8
9
10
11
12

方法二：

#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]
}
1
2
3
4
5
6
7
8
9
10
11
12
13

验证其两种方式是否正确：

#include
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20