1.6 静态链表

1.6.1 静态链表的定义

静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，这里的指针是结点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也需要预先分配一块连续的内存空间。

静态链表

1.6.2 静态链表的特点

顺序表：逻辑上连续，物理上连续

静态链表：逻辑上离散，物理上连续

单双链表：逻辑上离散，物理上离散

静态链表比顺序表好。比单双链表差

优点：增加、删除操作不需要移动大量元素

缺点：①不能随机存取。只能从头结点遍历找

​ ②容量不可变

三、静态链表上的操作

静态链表的类型描述

#define MaxSize 50  //静态链表的最大长度
typedef struct SLinkList{
	ElemType data;  //数据元素
	int next;  //下一个元素的数组下标
}SLinkList[MaxSize];

初始化

a[0]的next设为-1

其它的next设为-2

判空

它的next为-2

则此结点为空

插入

①找一个空的结点，存入数据

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

③修改新结点的next

④修改i-1号结点的next

删除

②从头结点出发找到前驱结点

③修改前驱结点的next

④被删除结点的next设为-2

查找

从头结点出发挨个往后遍历结点

求表长

从头结点出发挨个往后遍历结点

遍历

从头结点出发挨个往后遍历结点