线性表的顺序存储结构及实现
1. 顺序存储结构的基本思想：
用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
线性表的顺序存储结构称为顺序表
顺序表是用一段地址连续的存储单元依次存储线性表的数据元素。常用一维数组来实现，线性表的数据元素的序号和存放它的数组的下标有一一对应关系。
线性表中有插入操作，所以数组长度Maxside应大于线性表长度Length。
设顺序表的每个元素占用c个存储单元，则第i个元素（指该元素的序号为i）的存储地址（不是求a1到ai的存储空间的大小）为：
LOC（ai）=LOC（a1）+（i-1）*c；
其递归形式为：
LOC（a i+1）=LOC（a i）+ c；
任一个单元，其偏移地址+基准单元的绝对地址=该单元的绝对地址。
2.顺序存储结构下的线性表的基本操作：
是针对顺序表的操作，不是针对顺序表所在的数组的操作，所以，其中涉及到的表述为第i个元素或第i个位置中的i，均表示顺序表的元素序号。
（1）构造函数
有参构造函数创建长度为n的顺序表时，需检验n是否合法；线性表是存储在数组中的，所以，n应当满足n<=Maxside。
顺序表的定义中定义有线性表的长度length，成功创建完线性表，应将n的值赋给length。
（2）查找操作
按位查找：需判断位置i是否超过线性表的长度length，且i不能小于0
按值查找：若找到需返回序号，注意序号与下标的对应关系
（3）插入操作
在第i个位置插入一个新元素x，若插入成功，则线性表长度+1；
首先找到插入位置：若位置不合理，则抛出异常；（1<=i<=length+1）
找到插入位置后，第i个位置及其后位置的所有元素均后移一位（共有n-i+1个元素需后移）注意移动的先后次序。
插入前需判断的两点： 是否表满，位置是否合理。
（4） 删除操作
判断位置是否合理；
与插入操作相比，删除操作中的第i个元素不需要前移（共有n-i个元素需前移）；
清新
网友评论