数据结构：静态链表[通俗易懂]首先我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每一个下标都对应一个data和一个cur。数据域data用来存放数据元素，也就是通常我们要处理的数据；而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。我们把这种用数组描述的链表叫做静态链表。数组的第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素
首先我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每一个下标都对应一个data和一个cur。
数据域data用来存放数据元素，也就是通常我们要处理的数据；而游标cur相当于单链表中的next指针，
存放该元素的后继在数组中的下标。我们把这种用数组描述的链表叫做静态链表。
数组的第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的cur
则存放第一个有数值的元素的下标，相当于单链表的头节点作用，当整个链表为空时，则为0，表示无指向。如图3-12-2所示
现在如果我们需要在“乙”和“丁”之间插入一个值为“丙”的元素，只需要将“乙”的cur改为7，表示下一位是“丙”，并将“丙”的cur改为3，表示下一位是丁。
如图3-12-3所示。
现在如果我们删除了第一个元素“甲”，表示现在“甲”这个位置空出来了，如果未来有新人要来则优先考虑这里，所以删除的位置成为第一个优先空位，即首元素的cur为1， 第一个元素位置的cur改为8，而下标为8的位置cur改为9，最后元素位置的cur改为2，如图3-12-4所示。
![数据结构：静态链表[通俗易懂]](https://img-my.csdn.net/uploads/201304/21/1366531324_8846.jpg)
![数据结构：静态链表[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg)
![数据结构：静态链表[通俗易懂]](https://img-blog.csdn.net/20130502085006386)
示例代码：（改编自《大话数据结构》）
C++ Code
|
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;
} |
输出为：
![数据结构：静态链表[通俗易懂]](https://img-my.csdn.net/uploads/201304/21/1366543421_5698.jpg)
静态链表在插入和删除操作时不需要移动元素，只需要修改游标，从而改进了在顺序存储结构中插入和删除操作需要移动
大量元素的缺点；但并没有解决连续分配存储带来的表长难以确定的问题；并且失去了顺序存储结构随机存取的特性。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/222409.html原文链接：https://javaforall.net
