数据结构:静态链表[通俗易懂]首先我们让数组的元素都是由两个数据域组成,data和cur。也就是说,数组的每一个下标都对应一个data和一个cur。数据域data用来存放数据元素,也就是通常我们要处理的数据;而游标cur相当于单链表中的next指针,存放该元素的后继在数组中的下标。我们把这种用数组描述的链表叫做静态链表。数组的第一个元素,即下标为0的元素的cur就存放备用链表的第一个结点的下标;而数组的最后一个元素
大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46,售后保障稳定
首先我们让数组的元素都是由两个数据域组成,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所示。
示例代码:(改编自《大话数据结构》)
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; } |
输出为:
静态链表在插入和删除操作时不需要移动元素,只需要修改游标,从而改进了在顺序存储结构中插入和删除操作需要移动
大量元素的缺点;但并没有解决连续分配存储带来的表长难以确定的问题;并且失去了顺序存储结构随机存取的特性。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/222409.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】:
Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】:
官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...