【数据结构】静态链表的创建和插入操作

  • 1、静态链表:用数组描述的链表。这种描述方法叫做游标实现法。
静态链表:
游标 5 2 3 4 0 6 7 1
数据
A C D E
下标 0 1 2 3 4 5 6 999
约定:
  1. >把未使用的数组元素称为备用链表
  2. >下标为0的游标存放第一个数据为空的元素的下标(存放备用链表的第一个结点的下标),即这里的5;
  3. >最后一个存有数据的元素的游标为0.
  4. >下标为最末的游标存放第一个有数据的元素的下标,相当于单链表中的头结点作用,也即这里的1。
  5. >对数组的第一个和最后一个元素做特殊处理,他们的data不存放数据
  • 1.静态链表的创建:
首先初始化下标为i=0~max-2的游标值,为i+1;(表为空时,备用链表的第一个结点下标为1,所以0元素的游标初始化为1)
然后将下标为max-1的的游标值设为0;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  • 2.静态链表的插入:将B插入表中的第二个位置
插入前:——————想把B插到表中第2个的位置。
游标 5 2 3 4 0 6 7 1
数据
A C D E
下标 0 1 2 3 4 5 6 999
  1. >先由下标为0的元素的游标,找到备用链表的第一个结点(5),在该结点(5)摆放相应数据(B)、他的游标是下一个结点(C)的下标(2)。
  2. >再由下标为max-1(999)的游标(1),找到第一个存放数据的元素(1)【如果要把B放到第n个位置,则要根据第一个元素,先找到第n-1个元素】,把它的游标改为待插入的结点的下标(5)。
  3. >将0元素的游标改为现在备用链表的第一个结点下标(6)。
插入后:
游标 6④ 5③ 3 4 0 2② 7 1
数据
A C D E B①
下标 0 1 2 3 4 5 6 999
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  • 3.静态链表的删除:将C删除
  1. 首先将数据B的游标改为数据C的游标(3),
  2. 再将数据C的元素游标改为原备用链表第一个元素的下标(6)。同时自身变为备用链表第一个元素,起数据C变为垃圾数据,相当于清空。
  3. 令0元素的游标为备用链表第一个结点的下标,也就是刚刚清空的C的下标(2)。
游标 2③ 5 6② 4 0 3① 7 1
数据
A D E B
下标 0 1 2 3 4 5 6 999
总结:
优点:插入删除的时候免去了移动大量数据的麻烦
缺点:没有解决连续存储分配带来的表长难以确定的问题;
            失去了顺序存储结构随机存取的特性。
此条目发表在数据结构与算法分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注