静态链表

发表于 | 分类于

什么是静态链表

静态链表是使用数组描述的链表，在使用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;
    }
}