静态链表

发表于 分类于 阅读次数：

对于线性链表，也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。

定义

用数组描述的链表，即称为静态链表。
在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标CUR。

实现

初始化操作

首先给出静态链表的存储形式

1
2
3
4
5
6
7
typedef int ElemType;
typedef int Status;
typedef struct
{
    ElemType data;
    int cur;            /*游标（Cursor）, 为0时表示无指向*/
} Component, StaticLinkList[MAXSIZE];

静态链表中，数组第一个元素的cur用来存放备用链表的第一个结点；最后一个元素的cur用来存放第一个插入元素的下标；且对数组第一个元素和和最后一个元素不进行数据存放。
image

1
2
3
4
5
6
7
8
9
// 初始化
Status InitList(StaticLinkList space)
{
    int i;
    for (i = 0; i < MAXSIZE-1; i++)
        space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0; // 目前静态链表为空，最后一个元素的cur为0
    return OK;
}

链表插入

这里我们假设存放了“甲乙丁戊己庚” 6个元素
image
第一个空闲结点下标是7，所以第一个元素的cur为7；第一个插入节点下标为1，所以最后一个元素的cur为1。
插入的步骤：（设k为插入第i个元素之前的元素）
1.找到的第一个空闲节点，存放新数据
2.把k的cur赋给新元素
3.把新元素的下标赋给k的cur

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status ListInsert(StaticLinkList L, int i, ElemType e) // 插入新元素
{
    int j, k, l;
    k = MAXSIZE - 1;   // k 是最后一个元素的下标
    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;              //找到第i个元素之前的元素
        L[j].cur = L[k].cur;  // 把第i个元素之前元素的cur赋给新元素的cur
        L[k].cur = j;    // 把新元素的下标赋给第i个元素之前的元素

        return OK;
    }
    return ERROR;
}

这时我们添加一个“丙”元素，效果如下
image

链表删除

链表删除的步骤：
1.获取删除元素的位置
2.将删除元素的cur赋给前一项元素的cur
3.释放删除元素的存储位置，即设置空闲节点
空闲节点的变化通过Free_SSL()实现，把当前空闲结点的位置赋给删除位置的cur，删除位置下标再赋给第一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status ListDelete(StaticLinkList L, int i) // 删除元素
{
    int j, k;
    if (i < 1 || i > ListLength(L))
        return ERROR;
    k = MAXSIZE - 1;  // k为最后一个元素下标
    for ( j = 1; j <= i-1; j++)   // 如果删除的是第一个元素，循环将被跳过
        k = L[k].cur;
    j = L[k].cur;   // 获取删除元素的下标
    L[k].cur = L[j].cur;  // 删除元素的cur赋给前一项
    Free_SSL(L, j);   // 释放删除元素的存储位置
        
    return OK;
}

现在要删除“甲”这个元素，效果如下：
image

完整代码

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
127
128
129
130
131
/* 结构数组实现静态链表*/
#include <stdio.h>
#define MAXSIZE 1000    /* 假设链表的最大长度是1000 */
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;
typedef int Status;   //作为函数类型，返回状态码,如OK
typedef struct
{
    ElemType data;
    int cur;            /*游标（Cursor）, 为0时表示无指向*/
} Component, StaticLinkList[MAXSIZE];

Status InitList(StaticLinkList space);  //初始化
Status ListInsert(StaticLinkList L, int i, ElemType e); // 插入新元素
Status ListDelete(StaticLinkList L, int i); // 删除元素
int Malloc_SLL(StaticLinkList space);  // 返回空闲空间的下标
int Free_SSL(StaticLinkList space, int k);  // 下标为k的位置收为空闲结点
int ListLength(StaticLinkList L);  // 判断当前列表元b素个数
void showList(StaticLinkList L);

int main(void)
{
    StaticLinkList List;
    InitList(List);
    printf("插入元素:\n");
    ListInsert(List, 1, 11);
    ListInsert(List, 2, 22);
    ListInsert(List, 3, 33);
    ListInsert(List, 4, 44);
    showList(List);
    printf("插入元素:\n");
    ListInsert(List, 1, 55);
    ListInsert(List, 3, 66);
    ListInsert(List, 5, 77);
    ListInsert(List, 8, 88);
    showList(List);
    printf("删除元素:\n");
    ListDelete(List, 4);
    ListDelete(List, 1);
    showList(List);
    
    return 0;
}

Status InitList(StaticLinkList space)
{
    int i;
    for (i = 0; i < MAXSIZE-1; i++)
        space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0; // 目前静态链表为空，最后一个元素的cur为0
    return OK;
}

int Malloc_SLL(StaticLinkList space)  // 返回空闲空间的下标
{
    int i = space[0].cur;    // 当前数组第一个元素的cur存的值，
                            // 就是要返回第一个备用空间的下标
    if (space[0].cur)  // 如果不为空表，即cur不为0
        space[0].cur = space[i].cur;  // 更新cur
    return i;
}

Status ListInsert(StaticLinkList L, int i, ElemType e) // 插入新元素
{
    int j, k, l;
    k = MAXSIZE - 1;   // k 是最后一个元素的下标
    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;              //找到第i个元素之前的元素
        L[j].cur = L[k].cur;  // 把第i个元素之前元素的cur赋给新元素的cur
        L[k].cur = j;    // 把新元素的下标赋给第i个元素之前的元素

        return OK;
    }
    return ERROR;
}

int Free_SSL(StaticLinkList space, int k)  // 下标为k的位置收为空闲结点
{
    space[k].cur = space[0].cur;  // 把当前空闲结点的位置赋给k位置的cur
    space[0].cur = k;    // k的位置再赋给第一个元素
}

Status ListDelete(StaticLinkList L, int i) // 删除元素
{
    int j, k;
    if (i < 1 || i > ListLength(L))
        return ERROR;
    k = MAXSIZE - 1;  // k为最后一个元素下标
    for ( j = 1; j <= i-1; j++)   // 如果删除的是第一个元素，循环将被跳过
        k = L[k].cur;
    j = L[k].cur;   // 获取删除元素的下标
    L[k].cur = L[j].cur;  // 删除元素的cur赋给前一项
    Free_SSL(L, j);
        
    return OK;
}

int ListLength(StaticLinkList L)  // 判断当前列表元素个数
{
    int j=0;
    int i=L[MAXSIZE-1].cur;  // 获得第一个元素的下标
    while(i)
    {
        i=L[i].cur;     // 当元素的cur为0，即最后一个元素，退出循环
        j++;
    }
    return j;   // 返回元素个数
}

void showList(StaticLinkList L)
{
    int i;
    i = L[MAXSIZE-1].cur;
    printf("遍历列表：");
    while (i)
    {
        printf("%4d", L[i].data);
        i = L[i].cur;
    }
    printf("\n");
}

执行结果：

1
2
3
4
5
6
插入元素:
遍历列表：  11  22  33  44
插入元素:
遍历列表：  55  11  66  22  77  33  44  88
删除元素:
遍历列表：  11  66  77  33  44  88

优缺点

优点

  • 在插入和删除操作时，只需修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除需要移动大量元素的缺点

缺点

  • 没有解决连续存储带来的表长难以确定的问题
  • 失去了顺序存储结构随机存储的特性