总结归纳
- 顾名思义，静态链表的长度是不可变的。
- 静态链表的定义，实际上是一个 MaxSize 长度的结构体数组，以此来模拟链表。
- 静态链表的 data 存放数据， next 存放下一个结点的位置。当静态链表遍历时，通过 next 指向的位置来进行遍历，依次达到链表的目的。
- 由第 3 条可知，静态链表在物理空间上是连续的，但在逻辑空间上可以不连续。
- 默认用 next 指向 -1 来表示静态链表的最后一个结点；初始化静态链表时，要初始化 data 来清理脏数据，还要将 next 置为一个特殊值，不能与静态链表的访问相冲突。
- 静态链表的优点在于，插入和删除操作不需要大量移动元素，只需要修改 next 的指向就行；缺点在于，不能随机存取，并且容量固定不可变。
- 显然，插入和删除的时间复杂度都是 O(n)。
- 在不支持指针的低级语言中，静态链表十分适合；或者适用于数据元素容量固定不变的场景（例如操作系统的文件分配表 FAT）。
- 这个代码并不严谨，例如：GetValue 函数（随机赋值）中，并没有考虑到如果生成两个一样的 next 的情况，一个方法是置一个 next 数组，每随机生成一个就检查一下是否存在；或者从一个不重复的 next 数组中不重复的提取 next 。不过据说考研很少考静态链表，就在此偷个懒。
代码实现
/*
静态链表
*/
#define MaxSize 10
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;
struct Node {
int data;
int next;
};
typedef Node SLinkList[MaxSize]; // 用SLinkList定义一个长度为MaxSize的Node型数组
// 初始化静态链表
void InitList(SLinkList &L) {
for (int i = 0; i < MaxSize; i++) {
L[i].data = 0;
L[i].next = -2; // 清除脏数据
}
L[0].next = -1; // -1表示表尾
}
// 随机对静态链表赋值
bool GetValue(SLinkList &L) {
int last = 0;
for (int i = 0; i < 6; i++) {
int address = rand() % 10;
int number = rand() % 80;
if (i == 5) {
L[last].next = -1;
} else { // 尾结点的next置为-1
L[last].next = address;
}
L[last].data = number;
last = address;
}
return true;
}
// 按位查找：查找第i个结点的位序
int GetElem(SLinkList &L, int i) {
if (i < 1) {
return -1;
}
int flag = 0;
int j = 0;
while (L[flag].next != -2 && j < i - 1) {
j++;
flag = L[flag].next;
}
return flag;
}
// 得到一个空结点位序
int GetEmptyNode(SLinkList &L) {
Node p = L[0];
for (int i = 0; i < MaxSize; i++) {
if (L[i].next == -2) {
return i;
}
}
return -1;
}
// 按位序插入
bool InserstList(SLinkList &L, int i, int e) {
if (i < 1) { // i值不合法
return false;
}
int q = GetEmptyNode(L); // 找到一个空结点位序
int p = GetElem(L, i - 1); // 找到第i-1个结点
L[q].data = e;
L[q].next = L[p].next;
L[p].next = q;
return true;
}
// 按位序删除
bool DeleteList(SLinkList &L, int i, int &e) {
if (i < 1) { // i值不合法
return false;
}
int p = GetElem(L, i); // 待删除的结点
int q = GetElem(L, i - 1); // 带删除结点的前一个结点
cout << L[p].data << " " <<L[p].next << endl;
cout << L[q].data << " " <<L[q].next << endl;
e = L[p].data;
L[q].next = L[p].next;
L[p].data = 0;
L[p].next = -2;
return true;
}
/*
// 按物理空间遍历静态链表
void TraverseList(SLinkList &L) {
for (int i = 0; i < MaxSize; i++) {
cout << "第" << i << "个：" << L[i].data << " " << L[i].next << endl;
}
}
*/
// 按逻辑空间遍历静态链表
void TraverseList(SLinkList &L) {
for (int i = 0; i < MaxSize; i++) {
if (L[i].next != 0) {
cout << "第" << i << "个：" << L[i].data << " " << L[i].next
<< endl;
}
}
}
int main() {
SLinkList L;
// Node L[MaxSize]; // 最原始的方法，实现同样效果
InitList(L);
GetValue(L);
TraverseList(L);
InserstList(L, 3, 5244);
cout << "插入后的效果：" << endl;
TraverseList(L);
int e = -1;
DeleteList(L, 5, e);
cout << "删除的e值：" << e << endl;
TraverseList(L);
}
