静态链表–简简单单做个NPC

定义

分配一整片连续的内存空间，各个结点集中安置。

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

基本操作

初始化

把头结点的游标设为-1，并且将其他结点的游标设为一个默认值 如8848

查找

从头结点出发依次往后遍历结点

插入

插入位序为i的结点

  1. 找到一个空的结点(循环遍历找到那个”8848“)，存入数据元素

  2. 从头结点出发找到位序为i-1的结点

  3. 修改新结点的next

  4. 修改i-1号结点的next

删除

  1. 从头结点出发找到前驱结点
  2. 修改前驱节点的游标
  3. 被删除结点的next设为”8848“

小结

静态链表:用数组的方式实现的链表
优点:增、删操作不需要大量移动元素
缺点:不能随机存取，只能从头结点开始依次往后查找；容量固定不可变

适用场景:①不支持指针的低级语言:②数据元素数量固定不变的场景(如操作系统的文件分配表FAT)