链式存储结构操作实现方法

2023-11-18 理论教育版权反馈

【摘要】：链式存储结构是用指针勾链来保持数据元素之间的联系关系的。和顺序存储结构下操作实现不同的是，链式存储结构下的操作实现主要是申请新的内存单元空间和用指针勾链。下面以链式存储结构的线性表的插入和删除操作实现方法为例讨论链式存储结构下操作的实现方法。设线性表中已有若干个数据元素，删除的数据元素保存在变量x中，线性表采用链式存储结构存储，设计链式存储结构的线性表的删除操作算法。

链式存储结构是用指针勾链来保持数据元素之间的联系关系的。和顺序存储结构下操作实现不同的是，链式存储结构下的操作实现主要是申请新的内存单元空间和用指针勾链。下面以链式存储结构的线性表的插入和删除操作实现方法为例讨论链式存储结构下操作的实现方法。

【例8-3】设线性表中已有若干个数据元素，要插入的数据元素保存在变量x中，线性表采用链式存储结构存储。试设计链式存储结构的线性表的插入操作算法。

设计思想说明：为说明算法设计思想，我们假设线性表的数据元素类型为整数，线性表的数据元素集合为{10，11，12，14，15，16}，则该链式存储结构的线性表在内存中的存储示意图如图8-10（a）所示；假设要在线性表的第i＝3个数据元素前插入一个新的数据元素13，则必须首先申请一个新的结点空间，并把变量x的数值13赋给该结点的数据元素域，其示意图如图8-10（b）所示；然后从链表的起始指针h（称作头指针）开始，寻找到第i－1个结点的指针，让新结点的指针域指向第i－1个结点，让第i－1个结点的指针域指向新结点，完成新结点链入到链表中，其示意图如图8-10（c）所示。

图8-10 链式存储下线性表的插入过程

（a）插入前；（b）新结点赋值；（c）链入

算法设计：设链表的头指针为h，要插入的新的结点位置为i（i从0开始计数），要插入的数据元素保存在变量x中，则算法如下：

（1）动态申请一个新的结点空间，设该结点由指针s指示；

（2）把变量x的数值赋给新结点的数据元素域；

（3）从头指针h开始找到链表的第i－1个结点；

（4）让新结点的指针域指向第i－1个结点；(www.chuimin.cn)

（5）让第i－1个结点的指针域指向新结点。

【例8-4】设线性表中已有若干个数据元素，删除的数据元素保存在变量x中，线性表采用链式存储结构存储，设计链式存储结构的线性表的删除操作算法。

设计思想说明：为说明算法设计思想，和例8－3类同，我们假设线性表的数据元素类型为整数，线性表的数据元素集合为{10，11，12，13，14，15，16}，则该线性表在内存中的存储示意图如图8-11（a）所示。假设要删除线性表的第i（i＝3）个数据元素，则必须首先从指针h开始找到第i－1结点，并把第i结点中的数据元素赋值到变量x，其示意图如图8-11（b）所示；然后把第i－1结点的指针域指向第i＋1结点，完成所指结点从链表的删除，其示意图如图8-11（c）所示。

图8-11 链式存储下线性表的删除过程

（a）删除前；（b）保存；（c）删除

算法设计：设链表的头指针为h，要删除的结点位置为i，删除结点的数据元素保存到变量x中，则算法如下：

（1）从头指针h开始找到链表的第i－1个结点；

（2）把第i个结点的数据元素赋给变量x；

（3）把第i－1结点的指针域指向第i＋1结点。

链式存储结构操作实现方法

相关推荐