总结归纳顾名思义静态链表的长度是不可变的。静态链表的定义实际上是一个 MaxSize 长度的结构体数组以此来模拟链表。静态链表的 data 存放数据 next 存放下一个结点的位置。当静态链表遍历时通过 next 指向的位置来进行遍历依次达到链表的目的。由第 3 条可知静态链表在物理空间上是连续的但在逻辑空间上可以不连续。默认用 next 指向 -1 来表示静态链表的最后一个结点初始化静态链表时要初始化 data 来清理脏数据还要将 next 置为一个特殊值不能与静态链表的访问相冲突。静态链表的优点在于插入和删除操作不需要大量移动元素只需要修改 next 的指向就行缺点在于不能随机存取并且容量固定不可变。显然插入和删除的时间复杂度都是 O(n)。在不支持指针的低级语言中静态链表十分适合或者适用于数据元素容量固定不变的场景例如操作系统的文件分配表 FAT。这个代码并不严谨例如GetValue 函数随机赋值中并没有考虑到如果生成两个一样的 next 的情况一个方法是置一个 next 数组每随机生成一个就检查一下是否存在或者从一个不重复的 next 数组中不重复的提取 next 。不过据说考研很少考静态链表就在此偷个懒。代码实现代码语言javascriptAI代码解释/* 静态链表 */ #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); }