热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

2.7.静态链表

图片均来自B站王道考研(侵删)1.静态链表:静态链表:分配一整片连续的内存空间,各个节点集中安置静态链表的每个节点,都包含了:数据元素、下一个结点的数组下标(游标),游标充当“指针




图片均来自B站王道考研(侵删)

请添加图片描述


1.静态链表:


  1. 静态链表:分配一整片连续的内存空间,各个节点集中安置
  2. 静态链表的每个节点,都包含了:数据元素、下一个结点的数组下标(游标),游标充当“指针”,单链表中每个节点存放的指针,只不过指针指明了具体的内存地址,而游标指明了下一个元素存放的数组下标
  3. 单链表中的表尾元素的*next指针指向NULL,而在静态链表中如果想表示这个结点是最后一个节点,则可以将它的游标设置为-1(即游标为-1表示已经到达表尾)
  4. 0号结点充当头结点
  5. 设每个元素的大小为4B,每个游标的大小也为4B(每个节点共8B),设起始地址为addr,则头结点指向的下一个结点地址为:addr+8*n(n为接下来的结点的数组下标)

2.用代码定义一个静态链表:

#define MaxSize 10 //静态链表的最大长度
struct Node{ //静态链表结构类型的定义
ElemType data; //存储的数据元素
int next; //下一个元素的数组下标
};
void testSLinkList{
struct Node a[MaxSize]; //数组a作为静态链表
//....
}
//书本代码:
#define MaxSize 10
typedef struct{
ElemType data;
int next;
}SLinkList[MaxSize];
//等价于:
#define MaxSize 10
struct Node{
ElemType data;
int next;
};
typedef struct Node SLinkList[MaxSize]; //可以用SLinkList去定义一个长度为MaxSize的Node型数组;
void testSLinkList{
SLinkList a;
//上面这一行等价于:struct Node a[MaxSize];
//......
}

3.简述基本操作的实现


  1. 初始化静态链表:把a[0]的next设置为-1,将其余的空闲结点的游标设置为-2,以便于后面寻找空余结点时进行判断

  2. 查找:从头结点出发挨个往后遍历节点

  3. 插入位序为i的结点

    ①找到一个空的结点,存入数据元素

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

    ③修改新的结点的next

    ④修改i-1号结点的next

  4. 删除某个节点:

    ①从头结点出发找到前驱节点

    ②修改前驱节点的游标

    ③被删除的结点的游标设置为-2


4.总结:


  1. 静态链表:用数组的方式实现的链表

  2. 优点:增、删操作不需要大连的移动元素,只需要修改相关的结点的游标即可

  3. 缺点:不能随机存取,只能从头结点开始依次往后查找;容量固定不可变

  4. 适用场景:

    ①不支持指针的低级语言

    ②数据元素数量固定不变的场景(如操作系统的文件分配表FAT)



推荐阅读
author-avatar
温德军46867
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有