看 PHP7 底层源码的书，其中提到 PHP7 的数组使用逻辑链表在进行维护，所谓逻辑链表，就是不再使用指针进行管理，而是使用数组这种数据结构，数组中的成员中会维护下一个节点的数组的下标。这样让我想起了数据结构中学到的静态链表。
静态链表使用数组进行管理，数组的第一个元素用来保存第一个空闲的位置，数组的最后一个元素用来保存第一个元素的位置。
当时学数据结构的时候，对静态链表的记忆还是比较好的，不过当时没有写代码。今天写了一下。分享一下代码吧。
代码语言：javascript复制/**
* data：用来保存数据
* cur：用来保存下一个元素所在的下标
*/
typedef struct _StaticLinkList
{
ElemType data;
int cur;
} StaticLinkList, *PStaticLinkList;
/**
* 初始化链表
*/
Status InitList(PStaticLinkList space)
{
int i;
// 将所有存储数据的data赋值为0
// 将存储下一个元素的cur赋值为下一个数组的下标
for (i = 0; i < MAXSIZE - 1; i )
{
space[i].data = 0;
space[i].cur = i 1;
}
// 数组的最后一个元素保存开始位置的下标
space[MAXSIZE - 1].data = 0;
space[MAXSIZE - 1].cur = 0;
return OK;
}
/**
* 查找可以写入的位置
*/
int Malloc_SLL(PStaticLinkList space)
{
// 数组下标0的cur保存了第一个空闲的下标
int i = space[0].cur;
// 如果下标有效，则把空闲元素的cur赋值给数组下标0的cur
if (space[0].cur)
{
space[0].cur = space[i].cur;
}
// 返回空闲的下标
return i;
}
/**
* 计算链表的长度
*/
int ListLength(PStaticLinkList L)
{
int j = 0;
// 从数组最后一个元素的cur中获取链表的开始元素的下标
int i = L[MAXSIZE - 1].cur;
// 遍历链表
while (i)
{
i = L[i].cur;
j ;
}
return j;
}
/**
* 在第i个位置之前插入数据e
*/
Status ListInsert(PStaticLinkList L, int i, ElemType e)
{
int j, k, l;
k = MAXSIZE - 1;
// 插入的位置需要合理
if (i < 1 || i > ListLength(L) 1)
{
return ERROR;
}
// 找到第一个空闲的位置
j = Malloc_SLL(L);
// 判断是否有
if (j)
{
L[j].data = e;
// 查找到插入的位置
for (l = 1; l < i - 1; l )
{
k = L[k].cur;
}
// 改变链表的指针
L[j].cur = L[k].cur;
L[k].cur = j;
return OK;
}
return ERROR;
}
/**
* 让第i个位置成为空闲
* 删除数据后，被删除的位置会成为空闲位置，空闲位置的下标会放入第0个元素的cur当中
*/
void Free_SSL(PStaticLinkList L, int i)
{
L[i].cur = L[0].cur;
L[0].cur = i;
}
/**
* 删除第i个位置的元素
*/
Status ListDelete(PStaticLinkList L, int i)
{
int j, k;
// 判断删除的位置是否合理
if (i < 0 || i > ListLength(L))
{
return ERROR;
}
k = MAXSIZE - 1;
// 查找删除的位置
for (j = 1; j <= i - 1; j )
{
k = L[k].cur;
}
// 改变指针
L[j].data = 0;
j = L[k].cur;
L[k].cur = L[j].cur;
// 让被删除元素成为空闲
Free_SSL(L, j);
return OK;
}
/**
* 打印数组中的每个元素
*/
void print(PStaticLinkList L)
{
printf("===============rn");
for (int i = 0; i < MAXSIZE; i )
{
printf("%d:[%d]->%drn", i, L[i].data, L[i].cur);
}
}
/**
* 遍历链表
*/
void foreach(PStaticLinkList L)
{
printf("===================rn");
int k = L[MAXSIZE-1].cur;
while(k)
{
printf("%d:[%d]->%drn", k, L[k].data, L[k].cur);
k = L[k].cur;
}
}
代码使用 C 语言完成，因为简单，就不进行过多的介绍了。
以上代码在树莓派上用 gcc 编译通过。以前基本都是在 Windows 下使用 VS 来写 C 和 C 的代码。但是，由于机器不够快，每次开 VS 的速度比较慢，就去树莓派上用 vim gcc 进行开发了。以后也打算逐步的了解一下 Linux 平台上 C 和 C 的知识。
我觉得基础知识真的很重要，如果学过数据结构，立刻会想到其设计使用了何种数据结构，可以回忆一下这种数据结构的特性等，而且也可以加深自己对该种数据结构的理解。而如果没有学习过数据结构，那么在遇到代码中使用了某种数据结构，就无法很好的理解代码中为何要使用该种数据结构了，对于代码的理解就不能更加的透彻了。
