#单链表之静态链表
静态链表是没有指针的 “单链表” ，它用数组进行描述
先来个空的静态链表：
此表的右上方的小方框就类似与指针了，只是把它作为了游标 cur ； 静态链表中的第一个元素和最后一个元素作为特殊处理，且最后一个元素类似于单链表中的头节点。不断插入元素后，最后一个元素的游标就将存入第一个元素的数组下标
接着来一个已经插入了几个元素的静态链表
插入元素后静态链表就与空的链表不同了；在 D 元素的游标为 0，表示 D 左边部分包括本身都已经被使用，而右边部分是备用空间，并且最右边的游标就指向了 1；如果再插入就要开辟备用空间 5 了。
再来个删除第一个元素后的静态链表图
删除一个元素，最右边类似头节点的游标要进行变动，还有所删除的元素所在的位置的游标也要变动
说说它的优点和缺点
优点：在插入和删除元素时，只用修改游标，不用想顺序存储那样移动一大半元素缺点：没有解决连续存储分配带来的表长难以确定的问题；失去了顺序存储结构随机存取的特性。
代码片段
#include <stdio.h>
#define maxsize 100
typedef char ElemType;
typedef struct
{
int cur;
ElemType data;
}StaticLink, StaticLinkList[maxsize];
void InitList(StaticLinkList space)
{
int i;
for (i = 0; i < maxsize - 1; i++)
{
space[i].cur = i + 1;
}
space[maxsize - 1].cur = 0; //Similar to the headnode
}
//This is lnegth of static single linked list
int ListLength(StaticLinkList space)
{
int i = space[maxsize - 1].cur;
int j = 0;
while(i)
{
j++;
i = space[i].cur;
}
return j;
}
//Subscript of the allocated space before inserting the element 插入元素前分配空间的下标
int Malloc(StaticLinkList space)
{
int i = space[0].cur;
if (i)
{
space[0].cur = space[i].cur;
}
return i;
}
//The element is inserted before the index
void ListInsert(StaticLinkList space, int index, ElemType key)
{
if (index < 1 || index > ListLength(space)+1)
{
printf("The \'index\' is error !!\n");
return;
}
int j = Malloc(space);
int k = maxsize - 1;
if (j)
{
space[j].data = key;
for (int l = 1; l <= index - 1; l++)
{
k = space[k].cur;
}
space[j].cur = space[k].cur;
space[k].cur = j;
}
return;
}
//Recycling the node labeled 'k' //将下标为k的空闲结点回收到备用链表中
void Free_List(StaticLinkList space, int k)
{
space[k].cur = space[0].cur;
space[0].cur = k;
}
void List_Traverse(StaticLinkList space)
{
int k = maxsize - 1;
while (space[k].cur)
{
k = space[k].cur;
printf("%c", space[k].data);
}
printf("\n");
}
//Delete the flagth data element
void ListDel(StaticLinkList space, int flag)
{
int j, k;
if (flag < 1 || flag > ListLength(space))
{
printf("The \'index\' is error !!\n");
return;
}
k = maxsize - 1;
for (j = 1; j <= flag - 1; j++)
{
k = space[k].cur;
}
j = space[k].cur;
space[k].cur = space[j].cur;
Free_List(space, j);
}
int main()
{
StaticLinkList space;
InitList(space); //Initialize the static single linked list
int n;
printf("Number of inserted elements: ");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
ElemType a;
int m;
printf("Please enter the element`s location of insert: ");
scanf("%d", &m);
getchar();
printf("Please enter the element of insert: ");
scanf("%c", &a);
ListInsert(space, m, a);
}
List_Traverse(space);
int flag;
printf("Please enter the element`s location of deleted: ");
scanf("%d", &flag);
ListDel(space, flag);
List_Traverse(space);
return 0;
}
