线性表的顺序存储结构.ppt

《线性表的顺序存储结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.1线性表的类型定义2.3线性表的链式表示和实现2.4一元多项式的表示及相加2.2线性表的顺序表示和实现第二章线性表2.2线性表的顺序表示和实现线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。￡2.2线性表的顺序存储结构（1）线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。如下图2.1所示：线性表的这种机内表示称做线性表的顺序存储结构或顺序映像(sequentialmapping)。通常称这种存储结构的线性表为顺序表。特点：以元素在计算机内“物理位置相

2、邻”来表示线性表中数据元素之间的逻辑关系存储地址内存状态数据元素在线性表中的位序ba11b+la22………b+(i-1)laii………b+(n-1)lannb+nl…空闲b+(maxlen-1)l（2）求址公式假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。线性表中第i＋1个数据元素的存储位置和第i个数据元素的存储位置之间满足下列关系：线性表的第i个数据元素ai的存储位置为：式中是线性表的第一个数据元素的存储位置，通常称做线性表的起始位置或基地址。只要确定

3、了存储线性表的起始位置，线性表中任一数据元素都可随机存取。线性表的顺序存储结构是一种随机存取的存储结构。顺序映像的C语言描述typedefstruct{}SqList;//俗称顺序表ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量//(以sizeof(ElemType)为单位)#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量St

4、atusInitList_Sq(SqList&L,intmaxsize){//构造一个最大容量为maxsize的顺序表}//InitList_Sq算法时间复杂度：O(1)L.elem=newElemType[maxsize];//为顺序表分配大小为maxsize的数组空间if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=maxsize;returnOK;序号数据元素序号数据元素序号数据元素序号数据元素1121121121122132132132133213

5、21321321424424424428528525528530630628630642742730742777877842877977(a)(b)(a)(b)图2.2线性表插入前后的情况图2.3线性表删除前后的情况(a)插入前n＝8(a)删除前n＝8(b)插入后n＝9(b)删除后n＝7插入25删除24（4）线性表的插入和删除运算StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表L中第i个位置之前插入新的元素e，//i的合法值为1≤i≤ListL

6、ength_Sq(L)+1if(i<1

7、

8、i>L.length+1)returnERROR;//i值不合法if(L.length>=L.listsize){//当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;

9、//增加存储容量}q=&(L.elem[i－1]);//q为插入位置for(p=&(L.elem[L.length－1]);p>=q;――p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增1returnOK;}//ListInsert_Sq插入运算算法2.3如下：StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在顺序线性表L中删除第i个元素，并用e返回其值//i的合法值为1≤i≤ListLength_

10、Sq(L)if(i<1

11、

12、i>L.length)returnERROR;//i值不合法p=&(L.elem[i－1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length－1;//表尾元素的位置for(++p;p<=q;++p)*(p－1)=*p;//被删除元素之后的元素左移――L.length;//表长减1returnOK;}//ListDelete_Sq删除运算算法2.4如下：（5）时间复杂度从上述算法可见，