顺序存储下的操作实现方法

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

【摘要】：下面以顺序存储结构的线性表的插入和删除操作实现方法为例讨论顺序存储结构下操作的实现方法。设线性表的最大数据元素个数为m，当前线性表中已有n（n≤m）个数据元素，要插入的数据元素保存在变量x中，线性表采用顺序存储结构存储。试设计顺序存储结构线性表的插入操作算法。

前面我们说过，顺序存储结构是采用数组存储数据元素的，用数组存储数据结构的数据元素集合时，只要用户程序给出数组的下标，系统就可以计算出该数组元素的地址。下面以顺序存储结构的线性表的插入和删除操作实现方法为例讨论顺序存储结构下操作的实现方法。

【例8-1】设线性表的最大数据元素个数为m，当前线性表中已有n（n≤m）个数据元素，要插入的数据元素保存在变量x中，线性表采用顺序存储结构存储。试设计顺序存储结构线性表的插入操作算法。

设计思想说明：为说明算法设计思想，我们假设线性表的数据元素类型为整数，存储当前线性表的数组为a，数组a中已有n＝6个数据元素，线性表的数据元素集合为{10，11，12，14，15，16}，则该线性表在内存中的存储示意图如图8-8（a）所示。假设我们要在线性表的第i（i＝3）个数据元素前插入一个新的数据元素13，则必须首先把包括第i个数据元素在内的第i个数据元素后的所有数据元素依次后移一个位置，其示意图如图8-8（b）所示。然后再把新的数据元素13插入到已空出的第i个数据元素位置，其示意图如图8-8（c）所示。

图8-8 数组存储下线性表的插入过程

（a）插入前；（b）后移；（c）插入

算法设计：设数组为a，数组的个数为m，当前数组中已有的数据元素个数为n，要插入的新的数据元素位置为数组下标i（i从0开始计数），要插入的数据元素保存在变量x中，则算法如下：

（1）IF（n＝＝m）THEN该线性表已满，无法再插入新的数据元素，插入失败返回；

（2）ELSE

FOR（j＝n＋1；j＞i；j＝j－1）a[j]＝a[j－1]； //逐个元素后移

n＝n＋1； //元素个数加1

a[ji]＝x； //新元素插入

（3）插入成功返回。(www.chuimin.cn)

【例8-2】设线性表线性表中有n（n≥0）个数据元素，删除的数据元素保存在变量x中，线性表采用顺序存储结构存储。试设计顺序存储结构线性表的删除操作算法。

设计思想说明：为说明算法设计思想，和例8-1类同，我们假设线性表的数据元素类型为整数，存储当前线性表的数组为a，数组a中已有n＝7个数据元素，线性表的数据元素集合为{10，11，12，13，14，15，16}，则该线性表在内存中的存储示意图如图8-9（a）所示。假设我们要删除线性表的第i（i＝3）个数据元素，则必须首先把第i个数据元素保存到变量x中，其示意图如图8-9（b）所示。然后把不包括第i个数据元素在内的第i个数据元素后的所有数据元素依次前移一个位置，其示意图如图8-9（c）所示。

图8-9 数组存储下线性表的删除过程

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

算法设计：设数组为a，当前数组中已有的数据元素个数为n，要删除的数据元素位置为数组下标i（i从0开始计数），删除后的数据元素保存在变量x中，则算法如下：

（1）IF（n＝＝0）THEN该线性表已空，没有数据元素可删除，删除失败返回；

（2）ELSE

x＝a[i]； //保存数据

FOR（j＝i＋1；j＜n；j＝j＋1）a[j－1]＝a[j]； //逐个元素前移

（3）删除成功返回。