静态链表

发表于 |

静态链表可以给没有指针的编程语言设计一种实现单链表功能的方法。思想非常巧妙。其每个数组中的元素结构是由数据域data和游标cur组成，数据域就是需要存放的数据，游标相当于单链表中的 next 指针。cur中存放该元素的后继在数组中的下标。这种数组描述的链表叫做静态链表。

静态链表必须满足下面两个规则：

  • 数组的第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标。
  • 数组的最后一个元素的 cur 则存放第一个有数值的元素的下标，相当于单链表的头节点作用，当整个链表为空时，则为0，表示无指向。

如下图，cur 代表存放后继元素在数组中的下标。第 0 个下标的元素的 cur 存放备用链表的第一个节点的下标。最后一个元素的 cur 存放第一个有数值元素的下标。这样就构成一个链式存储结构。

现在在已、丁之间插入丙元素。需要将已的 cur 改为 7，丙的 cur 改为 3。这时候，链表中的头的 cur 就应该改为 8。如下图：

如果现在需要删除甲，那么甲处于的位置为空，如果有新的元素待插入，那么此位置将会优先考虑。所以删除的位置称为第一个优先空位。即首元素 cur 为1，末尾元素 cur 为 2。而游标为 2 的位置（参考上图）则指向下一个备用链表下标，即为 8。修改后的链表如下图所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
using namespace std;

#define MAXSIZE 100

typedef int ElemType;
/* 线性表的静态链表存储结构 */
typedef struct Node
{
    ElemType data;
    int cur; //为0时表示无指向
} StaticLinkList[MAXSIZE];

/* 将一维数组array中各分量链成一个备用链表，array[0].cur为头指针，"0"表示空指针 */
bool InitList(StaticLinkList array)
{
    cout << "InitList..." << endl;
    for (int i = 0; i < MAXSIZE - 2; i++)
    {
        array[i].cur = i + 1;
    }
    array[MAXSIZE - 2].cur = 0;  /* 最后一个元素也是不可用的，倒数第二个元素的cur为0 */
    array[MAXSIZE - 1].cur = 0;   /* 目前静态链表为空，最后一个元素的cur为0 */

    return true;
}
/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
int Malloc_SLL(StaticLinkList array)
{
    int k = array[0].cur;
    if (k)
        array[0].cur = array[k].cur;/* 下一个分量用来做备用 */

    return k;
}
/*  将下标为pos的空闲结点回收到备用链表 */
void Free_SLL(StaticLinkList array, int pos)
{
    array[pos].cur = array[0].cur; /* 把第一个元素的cur值赋给要删除的分量cur */
    array[0].cur = pos; /* 把要删除的分量下标赋值给第一个元素的cur */
}

int ListLength(StaticLinkList array)
{
    int i = array[MAXSIZE - 1].cur;
    int j = 0;
    while(i)
    {
        i = array[i].cur;
        ++j;
    }
    return j;
}
/*  在array中第pos个元素之前插入新的数据元素Elem  */
bool ListInsert(StaticLinkList array, int pos, ElemType Elem)
{
    cout << "Insert List from pos: " << pos << " Item " << Elem << endl;
    if (pos < 1 || pos > ListLength(array) + 1)
        return false;

    int k = MAXSIZE - 1;
    int i = Malloc_SLL(array); /* 获得空闲分量的下标 */

    if (i)
    {
        array[i].data = Elem;

        for (int l = 1; l <= pos - 1; l++)
            k = array[k].cur;

        array[i].cur = array[k].cur;/* 把第pos个元素之前的cur赋值给新元素的cur */
        array[k].cur = i;/* 把新元素的下标赋值给第pos个元素之前元素的cur */
        return true;
    }

    return false;
}
/*  删除在array中第pos个数据元素   */
bool ListDelete(StaticLinkList array, int pos)
{
    cout << "Delete List from pos: " << pos << endl;
    if (pos < 1 || pos > ListLength(array))
        return false;

    int k = MAXSIZE - 1;

    for (int l = 1; l <= pos - 1; l++)
        k = array[k].cur;

    int j = array[k].cur;
    array[j].cur = array[pos].cur;

    Free_SLL(array, j);

    return true;
}

bool ListTraverse(StaticLinkList array)
{
    cout << "List Traverse : " << endl;
    int k = MAXSIZE - 1;
    while (array[k].cur != 0)
    {
        k = array[k].cur;
        cout << array[k].data << ' ';
    }

    cout << endl;
    return true;
}


int main(void)
{
    StaticLinkList SSL;
    InitList(SSL);
    for (int i = 1; i < 5; i++)
        ListInsert(SSL, i, i);
    ListTraverse(SSL);

    ListDelete(SSL, 3);
    ListTraverse(SSL);
    cout << "List Length : " << ListLength(SSL) << endl;

    return 0;
}

静态链表的优缺点：

优点：

  • 在插入和删除操作时，只移动游标，不需要移动元素。改变了在顺序存储结构中的插入和删除需要移动大量元素的缺点。
    缺点：
  • 失去了顺序存储结构随机存取的特性。
  • 没有解决连续存储分配（数组）带来的表长难以确定的问题。

参考

《大话数据结构》