Loading... 【存储方式的分类】顺序存储结构和链式存储结构。 【顺序存储结构】在(子)程序的说明部分就必须加以说明,以便分配固定大小的存储单 元,直到(子)程序结束,才释放空间。因此,这种存储方式又称为静态存储。所定义的变量 相应的称为静态变量。它的优缺点如下: * (1)优点:可以通过一个简单的公式随机存取表中的任一元素,逻辑关系上相邻的两个 元素在物理位置上也是相邻的,且很容易找到前趋与后继元素; * (2)缺点:在线性表的长度不确定时,必须分配最大存储空间,使存储空间得不到充分利 用,浪费了宝贵的存储资源;线性表的容量一经定义就难以扩充;在插人和删除线性表的元 素时,需要移动大量的元素,浪费了时间。 【链式存储结构】在程序的执行过程中,通过两个命令向计算机随时申请存储空间或随 时释放存储空间,以达到动态管理,使用计算机的存储空间,保证存储资源的充分利用。这 样的存储方式称为动态存储。所定义的变量称为动态变量。它的优点如下: 可以用一组任意的存储单元(这些存储单元可以是连续的,也可以是不连续的)存储线 性表的数据元素,这样就可以充分利用存储器的零碎空间。 【概念】为了表示任意存储单元之间的逻辑关系,对于每个数据元素来说,除了要存储它 本身的信息(数据域、data)外,还要存储它的直接后继元素的存储位置(指针域、link 或 next)。我们把这两部分信息合在一起称为一个“结点 node”。 * (1)N 个结点链接在一起就构成了一个链表。N=0时,称为空链表。 * (2)为了按照逻辑顺序对链表中的元素进行各种操作,我们需要定义一个变量用来存储 整个链表的第一个结点的物理位置,这个变量称为“头指针、H 或 head”。也可以把头指针 定义成一个结点,称为“头结点”,头结点的数据域可以不存储任何信息,也可以存储线性表 的长度等附加信息,头结点的指针域(头指针)存储指向第一个结点的指针,若线性表为空 表,则头结点的指针域为空(NIL)。由于最后一个元素没有后继,所以线性表中最后一个结 点的指针域为空(NIL)。 * (3)由于此链表中的每个结点都只包含一个指针域,故称为“线性链表或单链表”。 --- 注:文章参考《信息学奥赛一本通(c++版)》 --- 最后修改:2021 年 03 月 21 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏