数据结构----静态链表c++

📎个人主页：我的主页
📎小白一枚，欢迎指教👏

---

一、什么是静态链表

• 单链表：各个结点在内存中星罗棋布，离散的分布，每个节点包含一个数据元素和指向下一个结点的指针（地址）。

• 静态链表：分配一整片连续的内存空间，各个结点集中安置。

• 每个数据元素为4B，每个游标4B（每个结点共8B），其首地址为addr

• 如：e1的存放地址为 addr+8*2

---

二、用代码定义一个静态链表

#define MaxSize 10  //静态链表的最大长度
  struct Node  {     //静态链表结构类型的定义
     ElemType data;   //存储数据元素
    int next;      //下一个元素的数组下标
  };
   void testSLinkList(){
     struct Node a[MaxSize];  //数组a作为静态链表
     //......后续代码
   }
1
2
3
4
5
6
7
8
9

---

三、基本操作

• 初始化静态链表，对应单链表，指向NULL在静态链表中就是把a[0]的next设为1。

• 查找：注意是某一位序（各个数组在逻辑上的顺序）的结点，而非数组下标（各个结点在物理上的顺序）的结点

• 插入位序为i的结点：注意如何判读是否为空？可以让next为某个特殊值，比如-2，否则会有脏数据

• 删除某个结点：1.从头出发找到前驱节点；2.修改前驱节点的游标；3.被删除结点next设为-2

---

四、总结

• 适用场景：1.不支持指针的低级语言；2.数据元素数量固定不变的场景（如操作系统的文件分配表FAT）