2万+  知识点  标题检索     全文检索
       线性表
               线性表的定义
               线性表是n个元素的有限序列,通常记为(a1,a2,…,an)。其特点如下。
               .存在唯一的一个称为"第一个"的元素。
               .存在唯一的一个称为"最后一个"的元素。
               .除了表头外,表中的每一个元素均只有唯一的直接前驱。
               .除了表尾外,表中的每一个元素均只有唯一的直接后继。
               线性表的存储结构
               1)顺序存储
               线性表的顺序存储是用一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑关系相邻的两个元素在物理位置上也相邻。在这种存储方式下,存储逻辑关系无须占用额外的存储空间。其优点是可以随机存取表中的元素,缺点是插入和删除操作需要移动大量的元素。
               一般地,在线性表的顺序存储结构中,第i个元素ai的存储位置为
               LOC(ai)=LOC(a1)+(i-1)×L
               式中,LOC(a1)为表中第一个元素的存储位置;L为表中每个元素所占空间的大小。
               2)链式存储
               线性表的链式存储是指用节点来存储数据元素,节点的空间可以是连续的,也可以是不连续的,因此存储数据元素的同时必须存储元素之间的逻辑关系。节点空间只有在需要的时候才申请,无须事先分配。最基本的节点结构如下图所示。
               
               最基本的节点结构
               其中,数据域用于存储数据元素的值,指针域则存储当前元素的直接前驱或直接后继信息,指针域中的信息称为指针(链)。n个节点通过指针连成一个链表,若节点中只有一个指针域,则称为线性链表(单链表)。
               线性表采用链表作为存储结构时,不能进行数据元素的随机访问,但其优点是插入和删除操作不需要移动元素。以下是几种其他链表结构。
               (1)双向链表。每个节点包含两个指针,指明直接前驱和直接后继元素,可在两个方向上遍历链表。
               (2)循环链表。表尾节点的指针指向表中的第一个节点,可在任何位置上开始遍历整个链表。
               (3)静态链表。借助数组来描述线性表的链式存储结构。
               在链式存储结构中,只需要一个指针(头指针)指向第一个节点,就可以顺序访问到表中的任意一个元素。为了简化对链表状态的判定和处理,特别引入一个不存储数据元素的节点,称为头节点,将其作为链表的第一个节点并令头指针指向该节点。
               线性表的插入和删除运算
               1)基于顺序存储结构的运算
               插入元素前要移动元素以挪出空的存储单元,然后再插入元素;删除元素时同样需要移动元素,以填充被删除的存储单元。在等概率下平均移动元素的次数分别是
               
               2)基于链式存储结构的运算
               在链式存储结构下进行插入和删除,其实质都是对相关指针的修改。
               (1)在单向链表中插入节点时,指针的变化情况如下图所示。
               
               单向链表插入节点时的指针变化情况
               (2)在单向链表中删除节点时,指针的变化情况如下图所示。
               
               单向链表删除节点时的指针变化情况
               (3)在双向链表中插入节点时,指针的变化情况如下图所示。
               
               双向链表插入节点时的指针变化情况
               (4)在双向链表中删除节点时,指针的变化情况如下图所示。
               
               双向链表删除节点时的指针变化情况
               注意:以上3图中①为插入运算前的指针走向;②为插入运算后的指针走向;虚线为插入后的指针指向。
 
 相关知识点:
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

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


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

客服

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

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


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