22线性表的顺序存储结构 22.1顺序表结构 线性表的顺序存储结构也称为顺序表。其存储方式为: 在内存中开辟一片连续存储空间,但该连续存储空间 的大小要大于或等于顺序表的长度,然后让线性表中 第一个元素存放在连续存储空间第一个位置,第二个 元素紧跟着第一个之后,其余依此类推
2.2线性表的顺序存储结构 2.2.1 顺序表结构 线性表的顺序存储结构,也称为顺序表。其存储方式为： 在内存中开辟一片连续存储空间，但该连续存储空间 的大小要大于或等于顺序表的长度，然后让线性表中 第一个元素存放在连续存储空间第一个位置，第二个 元素紧跟着第一个之后，其余依此类推
假设线性表中元素为(a1 an),设第一个元 素a1的内存地址为LOC(a1)(在图2-2中表示为b),而 每个元素在计算机内占d个存贮单元,则第个元素a1的 地址为LOC(a1)=LOC(a1)+(i-1)×d(其中1sn) 于是可用C++语言描述为 const int maxsize= maxlen;/ maxlen表示线性表允 许的最大长度 struct sequenlist elemtype a[ maxsize];∥表示线性表(a1,a2,…,an int len len表示线性表的实际长度
假设线性表中元素为（a1，a2，….,an），设第一个元 素a1的内存地址为LOC(a1 )（在图2-2中表示为b），而 每个元素在计算机内占d个存贮单元,则第i个元素ai的 地址为LOC(ai )=LOC(a1 )+(i-1)×d (其中1≤i≤n) 于是可用C++语言描述为: const int maxsize=maxlen； //maxlen表示线性表允 许的最大长度 struct sequenlist { elemtype a[maxsize]; //表示线性表（a1，a2，….,an） int len; //len表示线性表的实际长度 }；
存储地址 内存排列 位置序号 b+(i-1)×da b+(n-1)×d maxlen-1 图2-2顺序存储结构示意图
存储地址 内存排列 位置序号 a1 a2 … ai … an … 0 1 2 … i … n … maxlen-1 b b+d … b+(i-1)×d … b+(n-1)×d 图 2-2 顺序存储结构示意图
222顺序表运算 1.求顺序表的长度 length(U int length( sequenlist L return Llen 该算法的语句频度为1,时间复杂度为0(1)
2.2.2 顺序表运算 1．求顺序表的长度length(L) int length(sequenlist L) { return L.len; } 该算法的语句频度为1，时间复杂度为0(1)
2.插入运算 Insert(&L,x,i) void Insert( sequenlist &l, elemtype x, int 1) Int if(L.len>=maxsize-1) cout<<overflow<<endl else if ((K<D)(i>L.len+1) cout<<position is not correct! <<endl else forGj=L. len; j>=1; j--) La计+1-Lalj,W元素后移 [=x /插入元素 Llen++ ∥表长度增加1
2．插入运算Insert( &L,x,i) void Insert(sequenlist &L,elemtype x,int i) { int j; if(L.len>=maxsize-1) cout<<”overflow”<<endl; else if ((i<1)||(i>L.len+1) cout<<”position is not correct!”<<endl; else { for(j=L.len;j>=i;j--) L.a[j+1]=L.a[j]; //元素后移 L.a[i]=x; //插入元素 L.len++; //表长度增加1 }}