2.2线性表的顺序存情结构 221线性表的顺序存储结构 线性表的顺序存储结构是指用一组连续的存储单 元依次存储线性表中的每个数据元素。如下图2-1所示: 请单赤鼠标左键换页!
2.2 线性表的顺序存储结构 2.2.1 线性表的顺序存储结构 线性表的顺序存储结构是指用一组连续的存储单 元依次存储线性表中的每个数据元素。如下图2-1所示：
存储地址内存单元 d+L d+2L d+(i-1)L a d+(n-1)L 图2-1线性表顺序存储结构示意图 请单鼠标左键换页!
存储地址 内存单元 ... d a1 d+L a2 d+2L a3 ... d+(i-1)L ai ... d+(n-1)L an ... ... 图2-1 线性表顺序存储结构示意图
其中,L为每个数据元素所占据的存储单元数目 相邻两个数据元素的存储位置计算公式 LOC(a d=Loc(ai+L 线性表中任意一个数据元素的存储位置的计算公 式为: LOC(aHd=LOC(a+(i-1)*L 顺序存储结构的特点 (1)利用数据元素的存储位置表示线性表中相邻 数据元素之间的前后关系,即线性表的逻辑结构与存 储结构(物理结构)一致; 请单鼠标左键换页!
其中，L为每个数据元素所占据的存储单元数目。 相邻两个数据元素的存储位置计算公式 LOC(ai+1)=LOC(ai )+L 线性表中任意一个数据元素的存储位置的计算公 式为： LOC(ai+1)=LOC(a1 )+(i-1)*L 顺序存储结构的特点 （1）利用数据元素的存储位置表示线性表中相邻 数据元素之间的前后关系，即线性表的逻辑结构与存 储结构（物理结构）一致；
(2)在访问线性表时,可以利用上述给出的数学 公式,快速地计算出任何一个数据元素的存储地址。 因此,我们可以粗略地认为,访问每个数据元素所花 费的时间相等。这种存取元素的方法被称为随机存取 法,使用这种存取方法的存储结构被称为随机存储结 构义 在C语言中,实现线性表的顺序存储结构的类型定 # define Lst maX length100∥线性表的 最大长度 typedef struct Entry Type *item;∥指向存放线性表中数据元 素的基地址 int length;∥线性表的当前长度 ISQ LIST: 请单赤鼠标左键换页!
（2）在访问线性表时，可以利用上述给出的数学 公式，快速地计算出任何一个数据元素的存储地址。 因此，我们可以粗略地认为，访问每个数据元素所花 费的时间相等。这种存取元素的方法被称为随机存取 法，使用这种存取方法的存储结构被称为随机存储结 构。 在C语言中，实现线性表的顺序存储结构的类型定 义 #define LIST_MAX_LENGTH 100 //线性表的 最大长度 typedef struct { EntryType *item; //指向存放线性表中数据元 素的基地址 int length; //线性表的当前长度 }SQ_LIST；
222典型操作的算法实现 1.初始化线性表L int InitList(SQ LIST*L) L->item=(Entry Type*)malloc( LIST MAX LENGTH sizeof( Entry Type);∥分配空间 if(L->item=NULL) return Error;/若分配空间不 成功,返回 ERROR L->length=0; 将当前线性表长度置0 return OK: ∥成功返回OK 请单赤鼠标左键换页!
2.2.2 典型操作的算法实现 1. 初始化线性表L int InitList(SQ_LIST *L) { L->item=(EntryType*)malloc(LIST_MAX_LENGTH *sizeof(EntryType)); //分配空间 if (L->item==NULL) return ERROR; //若分配空间不 成功，返回ERROR L->length=0; //将当前线性表长度置0 return OK; //成功返回OK }