首页 > 知识点讲解
       线性表的存储结构
知识路径: > 计算机系统基础知识 > 计算机软件知识 > 数据结构与算法知识 > 链表 > 线性表 > 
被考次数:2次     被考频率:低频率     总体答错率:53%     知识难度系数:     
考试要求:掌握      相关知识点:3个      
        1)顺序存储
        线性表的顺序存储是用一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑关系相邻的两个元素在物理位置上也相邻。在这种存储方式下,存储逻辑关系无须占用额外的存储空间。其优点是可以随机存取表中的元素,缺点是插入和删除操作需要移动大量的元素。
        一般地,在线性表的顺序存储结构中,第i个元素ai的存储位置为
        LOC(ai)=LOC(a1)+(i-1)×L
        式中,LOC(a1)为表中第一个元素的存储位置;L为表中每个元素所占空间的大小。
        2)链式存储
        线性表的链式存储是指用节点来存储数据元素,节点的空间可以是连续的,也可以是不连续的,因此存储数据元素的同时必须存储元素之间的逻辑关系。节点空间只有在需要的时候才申请,无须事先分配。最基本的节点结构如下图所示。
        
        最基本的节点结构
        其中,数据域用于存储数据元素的值,指针域则存储当前元素的直接前驱或直接后继信息,指针域中的信息称为指针(链)。n个节点通过指针连成一个链表,若节点中只有一个指针域,则称为线性链表(单链表)。
        线性表采用链表作为存储结构时,不能进行数据元素的随机访问,但其优点是插入和删除操作不需要移动元素。以下是几种其他链表结构。
        (1)双向链表。每个节点包含两个指针,指明直接前驱和直接后继元素,可在两个方向上遍历链表。
        (2)循环链表。表尾节点的指针指向表中的第一个节点,可在任何位置上开始遍历整个链表。
        (3)静态链表。借助数组来描述线性表的链式存储结构。
        在链式存储结构中,只需要一个指针(头指针)指向第一个节点,就可以顺序访问到表中的任意一个元素。为了简化对链表状态的判定和处理,特别引入一个不存储数据元素的节点,称为头节点,将其作为链表的第一个节点并令头指针指向该节点。
 
本知识点历年真题:
隶属试卷 题号/题型 题干 难度系数/错误率
   2024年上半年
   软件设计师
   上午试卷 综合知识
第1题
选择题
关于链表操作中,说法正确的是(   )。

50%
   2020年下半年
   软件设计师
   上午试卷 综合知识
第58题
选择题
通过元素在存储空间中的相对位置来表示数据元素之间的逻辑关系,是( )的特点。

56%
 
 相关知识点:
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。


工作时间:9:00-20:00

客服

点击这里给我发消息 点击这里给我发消息 点击这里给我发消息

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2023 All Rights Reserved 软考在线版权所有