C/C++：使用数组模拟链表
链表中每一个node都由两部分组成：
1.真实的数据；
2.下一个数据的位置；
通常的实现可以使用指针作为指示下一个数据的位置的方式，当没有一个合法的数据存在，就将指针部分置为NULL，这个NULL是一个不在有效范围内的值。
链表不仅可以使用指针来实现，也可以使用数组来实现，区别（思路）在于：
指示下一个数据的位置的实现，使用一个整型int值来指明，而不是一个指针。
现在有两个数组：
int data[100], right[100];data用来保存数据，right用来指明当前数据的下一个数据所在data中的位置。
注意，data不一定是个整型数组，可以是任意数组，毕竟没有谁规定数据只能是整型。
上面的话有点绕，但是仔细想想指针的实现，不也是，当前的指针值，指明下一个节点所在内存空间中的地址吗？
对比两者：
之前的整个内存空间，映射到了现在的right的100个整型数组空间中；
之前的指针，映射到了right的一个整型变量；
由指针指明的地址，现在变成了由right[pos]指明地址；
之前的地址是一个指针，现在的地址是一个整型数
…等等。
right和指针的相同之处在于，他们都指明了下一个节点的位置（这个位置是一个整型数或者是一个指针来保存的）。
下面先看一个Demo：
#include <>
#include <>
int main()
{
// 定义100个node
int data[100], right[100];
for (int i = 0; i < 100; i++)
{
data[i] = 0;
right[i] = -1;
}
// serial:0 5 9 13 56 78 97
// 我想要将上面的数字按序存储到模拟链表中
// 将数字0存储到0位置的node
data[0] = 0;
// 我想要将数字5存储到数字0的下一个节点，这里可以是1
// 思考：这里可以是别的吗？
// 回答：当然可以，可以是2，可以是3...
right[0] = 1;
data[right[0]] = 5;
right[right[0]] = 2;
data[right[1]] = 9;
right[right[1]] = 3;
data[right[2]] = 13;
// 注意，这里将下一个数字存储到了位置50
right[right[2]] = 50;
// 这里实际存储的是数组中位置50处
data[right[3]] = 56;
right[right[3]] = 4;
data[right[50]] = 78;
right[right[50]] = 24;
data[right[4]] = 97;
right[right[4]] = -1;
int next = 0;
while (next != -1)
{
printf("%d ", data[next]);
next = right[next];
}
printf("\n");
return 0;
}[test1280@localhost ~]$ !g
gcc -o main -std=c99
[test1280@localhost ~]$ ./main
0 5 9 13 56 78 97程序主要由两部分组成，一部分是赋值，一部分是遍历输出。
上面的程序在执行完赋值部分后，数组应该是这样子的：
data 0 5 9 13 78 97 56
right 1 2 3 50 24 -1 4
index 0 1 2 3 4 24 50注意index指明了实际的数组中的位置。
先把上面的程序，动手画一下，写一写，看明白了再往下~
上面的程序并没有按序排放，我们当然可以按照序列顺序来进行：
#include <>
#include <>
int main()
{
// serial:0 5 9 13 56 78 97
// 我想要将上面的数字按序存储到模拟链表中
int original[7] = {0, 5, 9, 13, 56, 78, 97};
int ori_len = 7;
// 定义100个node
int data[100], right[100];
for (int i = 0; i < 100; i++)
{
data[i] = 0;
right[i] = -1;
}
int next = 0;
for (int i = 0; i < ori_len; i++)
{
data[next] = original[i];
right[next] = i + 1;
next = i + 1;
}
// 最后一个手工去置为-1
right[next - 1] = -1;
next = 0;
while (next != -1)
{
printf("%d ", data[next]);
next = right[next];
}
printf("\n");
return 0;
}[test1280@localhost ~]$ ./main
0 5 9 13 56 78 97想一想为什么最后一个手动置-1？哈哈。可以画图看一看。
（题外话：之前的初始化时不严密的，我应该规定合法数据是大于0的，初始化为-1，下面修正。）
下面我们看一看完整的插入和删除：
注意：我对数据的结构有了优化，使用了一个链表结构体来代表一个链表对象，其中next代表链表起始位置，当然，这个位置是相对于data成员来说的，否则无意义。
#include <>
#include <>
struct LinkList
{
int *data;
int *right;
// 当next为负代表链表中无数据，否则代表起始节点的绝对位置
int next;
// 链表的最大长度
int maxLen;
};
/**********************************************************************************************************
* 函数名称：init
* 参数列表：linkList-指向一个链表对象；data-数据指针；right-下标指针；data_len-data的长度；original-源数据指针；ori_len-源数据长度
* 函数描述：使用一个数组初始化一个链表
* 返回值 ：负数代表初始化失败
* 备注 ：对data/right的读写合法性由主调函数保证（故可能出现越界读写）
* Author ：test1280
* History ：2017/05/14
* *******************************************************************************************************/
int init(struct LinkList *linkList, int *data, int *right, int data_len, int *original, int ori_len)
{
// 入参校验
if (linkList == NULL || data == NULL || right == NULL || original == NULL || data_len < 0 || ori_len < 0)
{
return -1;
}
linkList->data = data;
linkList->right = right;
// 即使data_len比实际的data/right长度短也无所谓，因为是主调函数栈上的空间
linkList->maxLen = data_len;
linkList->next = -1;
int i;
for (i = 0; i < data_len; i++)
{
// 初始化为-1，任何数据非负才是合法的数据
linkList->data[i] = -1;
// 初始化为-1，任何下标非负才是合法的下标
linkList->right[i] = -1;
}
// 使用init函数初始化链表都将从0位置开始赋值
int next = 0;
for (i = 0; i < ori_len; i++)
{
linkList->data[next] = original[i];
linkList->right[next] = i + 1;
next = i + 1;
}
// 若初始化后链表中有数据，对linkList->next进行修改
// 若能进入之前的for循环，必能进入此处的if块
if (ori_len > 0)
{
linkList->right[next - 1] = -1;
linkList->next = 0;
}
return 0;
}
/**********************************************************************************************************
* 函数名称：insert
* 参数列表：linkList-指向一个链表对象；obj-要插入的数据
* 函数描述：插入一个合法数据（非负）到一个逻辑上从小到大的有序链表中
* 返回值 ：若插入成功则返回插入的绝对位置；若插入失败则为负值
* 备注 ：假定此链表在逻辑上已经由小到大排好序了；插入一个不合法的数据将失败
* Author ：test1280
* History ：2017/05/14
* *******************************************************************************************************/
int insert(struct LinkList *linkList, int obj)
{
// 入参校验：注意，linkList->next<0是合法的入参
if (linkList == NULL || obj < 0)
{
return -1;
}
// 注意这里隐含了对next<0的处理
int next = 0;
// linkList->next >= 0
if (linkList->next > 0)
{
next = linkList->next;
}
// prePos指向不大于要插入的数据（obj）的最大值的绝对位置
int prePos = -1;
// 如果尚未达到尾边界
while (linkList->data[next] >= 0)
{
// 如果大于obj
if (linkList->data[next] > obj)
{
break;
}
prePos = next;
next = linkList->right[next];
}
// nowPos指明当前的节点的绝对位置
int nowPos = 0;
// 找一个空槽放入数据（空槽的判断标准是是否数据非负）
while (nowPos < linkList->maxLen && linkList->data[nowPos] >= 0)
{
nowPos ++;
}
// 遍历完所有的data[nowPos]发现都有数据，即链表已满，插入失败
if (nowPos == linkList->maxLen)
{
return -1;
}
// 将要插入的数据放置在空槽中
linkList->data[nowPos] = obj;
// 如果插入到非首节点处
if (prePos >= 0)
{
// 将当前的位置的right修改为前驱节点的right值
linkList->right[nowPos] = linkList->right[prePos];
// 将前驱节点的right值修改为当前节点的绝对位置
linkList->right[prePos] = nowPos;
}
// 插入到首节点有两种情况：第一种是插入到非空链表中；第二种是插入到空链表中
else
{
// 插入到非空链表中还需要将后面的链起来
if (linkList->next >= 0)
{
linkList->right[nowPos] = linkList->next;
}
linkList->next = nowPos;
}
return nowPos;
}
/**********************************************************************************************************
* 函数名称：delete
* 参数列表：next-指明起始下标；data-数据指针；right-下标指针；obj-要删除的数据
* 函数描述：从链表中删除一个数据；如果被删除的数据在链表中不存在则认为删除失败
* 返回值 ：若删除成功则返回起始节点的绝对位置；若删除失败则为负值
* 备注 ：
* Author ：test1280
* History ：2017/05/14
* *******************************************************************************************************/
int delete(struct LinkList *linkList, int obj)
{
// 参数校验：不为NULL、链表中有数据、被删除的是一个合法的数据
if (linkList == NULL || linkList->next < 0 || obj < 0)
{
return -1;
}
int start = linkList->next;
int next = start;
int prePos = -1;
while (next != -1)
{
if (linkList->data[next] == obj)
{
break;
}
prePos = next;
next = linkList->right[next];
}
// 未在链表中找到obj
if (next == -1)
{
return -1;
}
// 如果是第一个节点
if (next == start)
{
// 数据域置-1
linkList->data[start] = -1;
// 修改起始位置
linkList->next = linkList->right[start];
// 下标域置-1
linkList->right[start] = -1;
}
// 如果要删除的不是第一个节点
else
{
linkList->right[prePos] = linkList->right[next];
linkList->data[next] = -1;
linkList->right[next] = -1;
}
return linkList->next;
}
/**********************************************************************************************************
* 函数名称：traversal
* 参数列表：next-指明起始下标；data-数据指针；right-下标指针；
* 函数描述：编译输出一个链表的所有值
* 返回值 ：返回0代表成功
* 备注 ：
* Author ：test1280
* History ：2017/05/14
* *******************************************************************************************************/
int traversal(struct LinkList *linkList)
{
int next = linkList->next;
printf("start traversal...\n");
while (next >= 0)
{
printf("%d ", linkList->data[next]);
next = linkList->right[next];
}
printf("\n");
printf("end traversal...\n");
return 0;
}
int main()
{
// serial:0 5 9 13 56 78 97
// 我想要将上面的数字按序存储到模拟链表中
int original[7] = {4, 5, 9, 13, 56, 78, 97};
int ori_len = 7;
// 定义100个node
int data[100], right[100];
int data_len = 100;
struct LinkList linkList;
init(&linkList, data, right, data_len, original, ori_len);
traversal(&linkList);
insert(&linkList, 65);
traversal(&linkList);
insert(&linkList, 0);
traversal(&linkList);
insert(&linkList, 97);
insert(&linkList, 98);
traversal(&linkList);
printf("delete ...\n");
int start = 0;
start = delete(&linkList, 65);
traversal(&linkList);
start = delete(&linkList, 78);
traversal(&linkList);
start = delete(&linkList, 4);
traversal(&linkList);
start = delete(&linkList, 0);
traversal(&linkList);
start = delete(&linkList, 98);
traversal(&linkList);
start = delete(&linkList, 97);
start = delete(&linkList, 97);
traversal(&linkList);
return 0;
}额，代码略微有点长。但是就核心代码来说就那么几句：
insert:
插入的时候可以随便（从前到后）找一个空位置（如何判空）来放置要插入的数据，然后需要修改right域：如果新插入的数作为首节点该如何处理；如果新插入的数不是作为首节点又该如何处理。其实无非就是将该链接的连接起来，将链表的起始位置（next成员）修改修改等等。
delete:
删除一个元素将这个元素的前后链接起来，记得将当前的节点的数据域与指针域置-1，如果要是删除头节点，还需要修改next域数据…
无论如何吧，其实都和指针实现的链表非常相似。
对以上代码来说，这只是一个初步的模型，还有很多后续可以优化的地方去处理~
里面也可能有很多的Bug，大家看的时候千万别太相信我~哈哈。
大家可以自己测试测试，有问题留言~我来Debug。
真心想说一句：数组模拟实现链表感觉还没有指针实现链表简洁易懂。。。
其他资料：
1./jianxin1009/article/details/7952069
2./rakerichard/archive/2010/03/16/
3./ly_624/article/details/51273541
4./student-note/p/
好吧，刚刚看了下其他说法，有一种叫静态链表，实际和上面用数组模拟链表差不多。
只不过它的特点是每个Node都是独立的，额，可以有很明显的对象界定，而不像我们上面介绍的两个数组来维护…
静态链表的结构体定义：
struct Node
{
// 数据域
int data;
// 游标域（下标域）
int cur;
};其实不论是指针也好，数组模拟也罢，还有静态链表，归根结底都是一个数据域一个指针域，指针域用来保存逻辑上下一个节点的位置，至于这里的指针域用什么办法来指明下一个节点的位置，就可以分为真正的指针以及数字游标…
其实上面的用数组来模拟链表，不也是一种静态链表吗？