顺序表结构

因为内存中的地址空间是线性的,因此用物理上的相邻实现数据元素之间的逻辑关系相邻是既简单又自然的。

一、顺序表在内存中的表示

设数据元素a1的存储地址为Loc(a1),每个数据元素占用d个存储地址,则第i个数据元素的地址为:Loc(ai) = Loc(a1) + (i - 1) * d,1 ≤ i ≤ n

顺序表结构

二、使用程序语言实现顺序表

在程序设计语言中,一维数组在内存中占用的存储空间就是一组连续的存储区域。因此,用数组来表示顺序表的数据存储区域再合适不过了。

考虑到,顺序表中存在删除、插入等运算,其长度会动态变化。所以,数组的容量要设计到足够大,我们使用MAXSIZE来表示。注意,MAXSIZE和数组长度是有区别的,前者表示最大长度,而后者动态变化,表示实际的长度。

顺序表的数据结构定义如下:

#define MAXSIZE 100

typedef int DataType;

class SequenList
{

	public:

		void Initiate();

		int Length();

		int Insert(DataType x,int i);

		int Deleted(int i);

		int Locate(DataType x);

		DataType Get(int i);

	private:

		DataType data[MAXSIZE];

		int len;
}
用户头像
登录后发表评论