|
顺序表 顺序表的定义 () 顺序存储方法 即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法 () 顺序表(Sequential List) 用顺序存储方法存储的线性表简称为顺序表(Sequential List) 结点a i 的存储地址 不失一般性设线性表中所有结点的类型相同则每个结点所占用存储空间大小亦相同假设表中每个结点占用c个存储单元其中第一个单 元的存储地址则是该结点的存储地址并设表中开始结点a 的存储地址(简称为基地址)是LOC(a )那么结点a i 的存储地址LOC(a i )可通过下式计算 LOC(a i )= LOC(a )+(i)*c ≤i≤n 注意 在顺序表中每个结点a i 的存储地址是该结点在表中的位置i的线性函数只要知道基地址和每个结点的大小就可在相同时间内求出任一结 点的存储地址是一种 随机存取结构 顺序表类型定义 #define ListSize //表空间的大小可根据实际需要而定这里假设为 typedef int DataType; //DataType的类型可根据实际情况而定这里假设为int typedef struct { DataType data[ListSize];//向量data用于存放表结点 int length;//当前的表长度 }SeqList; 注意 ① 用向量这种顺序存储的数组类型存储线性表的元素外顺序表还应该用一个变量来表示线性表的长度属性因此用结构类型来定义顺序表类 型 ② 存放线性表结点的向量空间的大小ListSize应仔细选值使其既能满足表结点的数目动态增加的需求又不致于预先定义过大而浪费存储 空间 ③ 由于C语言中向量的下标从开始所以若L是SeqList类型的顺序表则线性表的开始结点a 和终端结点a n 分别存储在Ldata[]和 LData[Llength]中 ④ 若L是SeqList类型的指针变量则a 和a n 分别存储在L>data[]和L>data[L>length]中 顺序表的特点 顺序表是用向量实现的线性表向量的下标可以看作结点的相对地址因此顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻 |
