链式存储结构是用指针勾链来保持数据元素之间的联系关系的。和顺序存储结构下操作实现不同的是，链式存储结构下的操作实现主要是申请新的内存单元空间和用指针勾链。下面以链式存储结构的线性表的插入和删除操作实现方法为例讨论链式存储结构下操作的实现方法。 设线性表中已有若干个数据元素，删除的数据元素保存在变量x中，线性表采用链式存储结构存储，设计链式存储结构的线性表的删除操作算法。......
2023-11-18
链式存储结构：计算机导论精要
【摘要】：在8.1节已讨论过链式存储结构下图书信息表的存储方法，图8-2给出了链式存储结构下图书信息表的存储关系示意，图8-2给出了链式存储结构下某次计算机运行时的内存存储图。图8-6 线性表的链式存储结构示意图高级语言要实现链式存储结构需要具有指针功能和内存空间的动态申请功能。链式存储结构的最大优点是内存资源的使用合理，除附加的指针内存空间外，不会出现太大的内存空间资源浪费，最大缺点是操作的实现方法相对复杂。
链式存储结构就是每当需要新的内存单元时就向系统申请，每次申请的内存空间中除了包括要存储的数据元素的内存空间外，还包括存放下一个数据元素的内存单元地址（称为指针）的内存空间，每次申请的内存空间称为一个结点，所有结点依靠指针链接起来。
在8.1节已讨论过链式存储结构下图书信息表的存储方法，图8-2（a）给出了链式存储结构下图书信息表的存储关系示意，图8-2（b）给出了链式存储结构下某次计算机运行时的内存存储图。
对于一个线性表，假设我们用a0，a1，a2，a3，⋯，an－1来抽象的表示线性表中要存储的n个数据元素，用箭头抽象的表示指针指示的下一个结点的内存单元地址，则链接存储结构下线性表的存储结构示意图如图8-6所示。
图8-6 线性表的链式存储结构示意图
高级语言要实现链式存储结构需要具有指针功能和内存空间的动态申请功能。所谓指针，就是内存单元的地址。对于两个整数类型变量x和y，假设变量x中有数值5，则把变量x赋给变量y就是把变量x中保存的数值5赋给变量y，赋值操作后，变量y中也将保存着数值5。其操作示意图如图8-7（a）所示。
系统在定义一个变量时，同时记录了系统为该变量分配的内存单元地址。假设系统为变量x分配的内存单元地址为1000，变量z为指针类型变量。所谓指针类型的变量，就是该变量用来存储一个内存单元地址。那么，把变量x的地址赋给指针z就是把变量x的地址1000赋给指针z，指针赋值操作后指针z中将保存着数值1000（变量x在内存中的地址）。其操作示意图如图8-7（b）所示。
图8-7 变量赋值和指针赋值比较(www.chuimin.cn)
（a）变量赋值；（b）指针赋值
用户程序向系统申请内存单元空间有两种方法：一种是静态的方法，即在程序编译时系统就根据用户程序中定义的变量和数组，为用户程序分配相应大小的内存单元空间。另一种是动态的方法，即在程序运行时，每当需要新的内存单元空间时，用户程序才向系统申请。
静态方法申请的内存空间是一次性申请的，所以内存单元的地址是连续的，如一个一维数组的内存单元地址就是连续的，系统可以通过用户定义数组时给出的数据类型，计算出任意一个数组元素在内存中的地址。动态方法申请内存空间的时间是随机的，每次只申请本次需要的内存单元空间。由于动态方法不是一次性申请的，所以内存单元的地址是不连续的。因此，要保持数据元素之间的逻辑关系，就需要一个指针把这些数据元素链接起来。
大部分高级语言都支持内存空间的动态申请。例如，C语言、C＋＋语言、PASCAL语言等都支持内存空间的动态申请。
链式存储结构的最大优点是内存资源的使用合理，除附加的指针内存空间外，不会出现太大的内存空间资源浪费，最大缺点是操作的实现方法相对复杂。
有关计算机导论的文章
- 详细阅读
-
顺序存储结构-《计算机导论》简明指南详细阅读
顺序存储结构就是先向系统申请一块地址连续的存储单元，然后把数据按照某种次序存入这块内存单元的相应位置中。顺序存储结构的最大优点是使用方法简单，最大缺点是必须预先分析估计出所需定义数组的最大个数。......
2023-11-18
-
计算机导论（第2版）：数据结构与顺序存储详细阅读
数据元素也称元素、结点、顶点、记录。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。该方法的基本思想是，根据数据元素的关键字直接计算出该结点的存储地址。......
2023-11-25
-
计算机导论：了解虚拟存储技术详细阅读
目前操作系统的存储管理中广泛采用虚拟存储技术。虚拟存储技术可以为用户提供比实际物理内存大得多的可随机访问的内存空间。虚拟存储技术有很多种实现方法，各种方法之间的差别，主要是实现虚地址到实地址的转换方法不同。图5-11 页式存储管理示例除页式存储管理外，虚拟存储技术的实现方法还有段式存储管理、段页式存储管理等。......
2023-11-18
-
计算机硬件结构概述-计算机导论详细阅读
通过第2章和第3章的讨论，我们对计算机硬件的基本结构有了更深一步的了解，图3-6给出了计算机硬件基本结构的概念框图。控制总线的控制信号一般都来自于CPU中的控制器。图3-4给出的CPU的基本构成中也有数据的传送通道，因为CPU是由拇指大小的一个芯片构成的，所以图3-4中的CPU内的数据传送通道称为片内总线。......
2023-11-18
-
计算机导论：网络拓扑结构分类详细阅读
所谓的拓扑结构，是指网络中各种通信设备之间连接的一种抽象形式。按网络的拓扑结构可以将计算机网络分为总线型、星型和环型。总线型网络在总线的两端必须设置电阻器，以防止信号的反射。工作站的接入或退出不影响网络的正常工作。星型网络结构是局域网中经常使用的一种结构，其拓扑结构如图9-4所示。图9-5 环型网络拓扑结构......
2023-11-18
-
计算机导论：文件及其结构详细阅读
我们把外存介质上的一个数据集合称为一个文件。文件的字母编号称为文件的设备号。文件通常用一个小数点符号分开成两部分，小数点前的符号串表示文件的名字，小数点后的符号串表示文件的类型。例如，MyFile1.dat和MyFile2.bmp就是两个类型不同的合法的文件名。图2-17 用户的文件结构图2-17所示的文件是用户视图的文件，这样的文件称为逻辑文件。具体设备上的具体物理存储位置中的0、1符号串称为物理文件。......
2023-11-18
-
计算机导论：递归结构及执行流程详细阅读
递归结构是算法中的另一种重复结构。下面仍然以查找问题和阶乘问题为例，给出递归结构算法的两个例子，然后以阶乘问题递归算法的执行过程为例，讨论递归结构算法的执行流程。的伪码形式的递归算法：PROCEDURE Factorial2{IFTHEN y＝1；ELSE y＝n*Factorial2（n－1）；}2.递归结构算法的执行流程用例6-4算法的执行过程讨论递归结构算法的执行流程。递归算法中的递归调用过程不能无休止的进行，任何递归算法都要考虑递归调用的结束条件，这称作递归出口。......
2023-11-18
相关推荐