静态链表

什么是静态链表

静态链表是使用数组描述的链表,在使用C语言中的结构体数组定义时,结构体变量中包括数据data和游标cur。

1
2
3
4
5
6
7
//---------线性表的静态单链表存储结构--------
#define MAXSIZE 100
typedef struct
{
ElemType data;
int cur;
}SLinkList[MAXSIZE];

对数组的特殊处理

  • 数组的第一个和最后一个元素做特殊处理,他们的data不存放数据。
  • 通常把未使用的数组元素称为备用链表。
  • 数组的第一个元素,即下标为0的那个元素cur就存放备用链表的第一个节点的下标。
  • 数组的最后一个元素,及下标为MAXSIZE-1的cur则存放的第一个有数值的元素的下标,相当于单链表中的头结点作用。
  • 已使用的链表的最后一个元素游标为0。
下标 0 1 2 3 4 5 6 999
数据 A C D E
游标 5 2 3 4 0 6 7 1

如上表,下标为0的元素中数据为空,游标为5,指向备用链表的首元素,下标为1,2,3,4的元素数据不为空,游标指向后继元素;最后一个元素下标为999,数据为空,游标指向首链表首元素下表为1。

Java实现相关操作

1
2
3
4
5
6
7
8
9
10
//初始化静态链表
public StaticLink[] init(int length){
StaticLink [] staticLinks = new StaticLink[length];
for (int i=0;i<length-1;i++){
staticLinks[i].cur = i+1;
}
staticLinks[length-1].cur = 0;
return staticLinks;
}
1
2
3
4
5
6
7
8
//分配链表空间
private int mallocStaticLink(StaticLink[] staticLinks){
int i = staticLinks[0].cur;
if(i != 0)
staticLinks[0].cur = staticLinks[i].cur;
return i;
}
1
2
3
4
5
//释放链表空间
public void freeStaticLink(StaticLink[] staticLinks,int index){
staticLinks[index].cur = staticLinks[0].cur;
staticLinks[0].cur = index;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//向静态链表中插入元素
public void insert(StaticLink[] staticLinks,int local,char data){
int length = staticLinks.length;
int k = 1;
int index = staticLinks[length-1].cur;
if(local<1 || local>length-1){
return;
}
int j = this.mallocStaticLink(staticLinks);
if (j != 0){
while (k<local-1){
index = staticLinks[index].cur; //获取插入指定位置的前一个元素的下标
k++;
}
staticLinks[j].data = data;
staticLinks[j].cur = staticLinks[index].cur;
staticLinks[index].cur = index;
}
}