文章目录什么是静态链表结构定义初始化查找插入删除什么是静态链表静态链表 用数组模拟链表(用数组的方式实现的链表)普通链表依靠malloc/free在堆上动态分配结点动态链表。静态链表预先开辟一段连续的数组空间数组的每个元素充当结点不用指针使用数组下标游标 cursor模拟指针。适用场景①某些不支持指针的高级语言②数据元素数量固定不变的场景。核心思想用“游标”代替“指针”data存放数据cur游标下一个结点在数组中的下标-1代表结束标记等价于NULL优点增、删操作不需要大量移动元素。缺点不能随机存取只能从头结点开始依次往后查找容量固定不可变。结构定义#includestdio.h#defineMAXSIZE100// 静态链表的最大长度// 静态链表节点结构typedefstruct{intdata;// 数据域intcur;// 游标Cursor为 0 时表示 NULL指向下一个节点的数组下标}SLinkList[MAXSIZE];// 此时 SLinkList 就是一个长度为 MAXSIZE 的结构体数组// 另一种写法 与上面等价typedefstructNode{intdata;intcur;};typedefstructNodeSLinkList[MAXSIZE]SLinkList[MAXSIZE];等价于typedef struct Node SLinkList[MAXSIZE],这是可用SLinkList定义“一个长度为MAXSIZE的Node型数组”。// 这两种也是等价的SLinkList a;// a 是一个静态链表structNodea[MAXSIZE];// a 是一个Node型数组初始化// 初始化备用链表将所有空闲节点连接起来voidInitList(SLinkList space){// i 从 0 循环到 MAXSIZE - 2for(inti0;iMAXSIZE-1;i){space[i].curi1;// 每个节点指向下一个节点的下标space[i].data-2;// -2 表示为空结点}space[MAXSIZE-1].cur-1;// 最后一个节点的 cur 为 -1表示 NULL,结束}查找从头结点出发挨个往后遍历节点时间复杂度为O(n)。插入①找到一个空的结点存入数据元素如何判断结点是否为空可让next(即cur)为某个特殊值如-2②从头结点出发找到位序为i-1的结点③修改新结点的next(即cur)④修改i-1号结点的next(即cur)删除①从头结点出发找到前驱结点②修改前驱结点 的游标③被删除结点的next(即cur)设为-2表示空结点