DS02线性表02顺序存储

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

1、2010-3-3第2章线性表线性表的顺序表示和实现本章内容2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1单链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加线性表的顺序表示顺序表：结点依次存放在线性连续空间中的线性表。假设l：每个结点所占的存储单元数b：第一个结点的存储位置LOC(a1)，称起始位置或基地址则LOC(ai+1)和LOC(ai)的关系为：LOC(ai+1)=LOC(ai)+l第i个数据元素ai的存储位置为：LOC(ai)=LOC(a

2、1)+(i-1)*l12…i…nlengthan…ai…a2a1存储地址内存状态结点位序bb+l…b+(i-1)l…b+(n-1)l…b+(maxlen-1)l空闲llLOC(a1)顺序表内存分布示意图顺序表的描述随机存取：只要确定了顺序表的起始位置，表中任一数据元素都可随机存取，所以顺序表是一种随机存取的存储结构。Q：数组是随机存取的吗？A：是。顺序表的数据排列以及操作方式，与数组非常相似。vector和数组的唯一区别：空间运用的灵活性数组是静态空间，一旦配置了就不能改变。要换个大（或小）一点的房子，可

3、以，一切琐细得有客户端自己来：配置新空间->元素从旧址一一搬往新址->释放旧空间。vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此，vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必因为害怕空间不足而一开始就要求一个大块头数组了，我们可以安心使用vector，吃多少拿多少。所以，我们一般用动态分配的一维数组来定义顺序表类型。千头万绪该如何说起？以客户端程序代码为引导，观察其所得结果并实证源代码，是一个良好的学习路径。例：项目vectorTest

4、动态分配的顺序表存储结构#defineLIST_INIT_SIZE100//存储空间的初始分配量#defineLISTINCREMENT10//存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址intlength;//当前已用空间的长度intlistsize;//当前可用空间的长度}SqList;顺序表基本操作在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。需掌握的基本操作InitList_SqListInsert_SqListDe

5、lete_SqLocateElem_SqMergeList_Sq注意：C语言中的数组下标从“0”开始顺序表基本操作的实现--InitList_Sq思路：初始化SqList的三个成员StatusInitList_Sq(SqList&L){//构造一个空的线性表L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;//空表长度为0L.listsize=LIST

6、_INIT_SIZE;//初始存储容量returnOK;}//InitList_Sq，算法2.3如果一个形参值有可以改变，或者要从函数返回某个值，则设为引用参数。顺序表基本操作的实现--GetElem_SqStatusGetElem_Sq(SqListL,inti,ElemType&e){//初始条件：线性表L已存在，1<=i<=ListLength(L);//操作结果：用e返回L中第i个数据元素的值if(i<1

7、

8、i>L.length)//i值不合法returnERROR;e=L.elem[i-1];r

9、eturnOK;}顺序表的插入顺序表的插入运算是指在表的第i(1<=i<=n+1)个位置之前插入一个新结点e，使长度为n的顺序表(a1，…ai-1，ai，…，an)变成长度为n+1的线性表(a1，…ai-1，e，ai，…，an)顺序表的插入33例：（35，12，24，42），在i=2的位置之前插入33。435122442a1a2a3a401234422412335Q：什么时候不能插入？注意边界条件1.合理的插入位置：1≤i≤L.length+1（i指的是元素的序号）2.表满：L.length>=L.lis

10、tsizeL.lengthL.elem顺序表的插入算法伪码1.如果元素的插入位置不合理，则返回错误信息;2.如果表已满，则增加分配;3.将最后一个元素至第i个元素分别向前移动一个位置；4.将元素x填入位置i处；5.表长加1。线性表的插入P24voidListInsert(SqList&L,inti,ElemTypee){//第i个位置之前插入e，初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1ElemTyp