DS02_线性表02_顺序存储课件.ppt

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

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

2、OC(a1)+(i-1)*l12…i…nlengthan…ai…a2a1存储地址内存状态结点位序bb+l…b+(i-1)l…b+(n-1)l…b+(maxlen-1)l空闲llLOC(a1)顺序表内存分布示意图第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l这意味着只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，所以线性表的顺序存储结构是一种随机存取的存储结构，即具有按数据元素的序号随机存取的特点。随机存取：即可在O(1)时间内存取数据元素2.2.1线性表的顺序存储结构2顺序表的描述由于C语言中的一维数组也

3、有随机存取的特性，故可以用数组类型来描述顺序表。又因为线性表长度可变，所以我们用动态分配的一维数组来定义顺序表类型。#defineLIST_INIT_SIZE100//存储空间的初始分配量#defineLISTINCREMENT10//存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量}SqList;2.2.2顺序表上实现的基本操作在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，

4、若L是SqList类型的顺序表，则表中第i个元素是L.elem[i-1]。StatusInitList_Sq(SqList&L){//构造一个空的线性表L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_SqStatus(SqListL,inti,ElemType&e){//初始条件：线性表L已存

5、在，1<=i<=ListLength(L);//操作结果：用e返回L中第i个数据元素的值if(i<1

6、

7、i>L.length)exit(ERROR);e=L.elem[i-1];returnOK;}顺序表的插入顺序表的插入运算是指在表的第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。435122442a1a2a3a401234422412335问题：什么时候不能插入？注意边界条件合

8、理的插入位置：1≤i≤length+1（i指的是元素的序号）表满：L.length>=L.listsize顺序表的插入P23图2.3调用ListInsert_Sq,i=？,e=？i=5,e=25算法描述1.如果元素的插入位置不合理，则抛出位置异常;2.如果表已满，则增加分配;3.将最后一个元素至第i个元素分别向前移动一个位置；4.将元素x填入位置i处；5.表长加1。线性表的插入算法2.4P24voidListInsert(SqList&L,inti,ElemTypee){//第i个位置之前插入e，初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1Elem

9、Type*newbase,*q,*p;if(i<1

10、

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