数据结构与算法设计PPT (6).pdf

《数据结构与算法设计PPT (6).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (6).pdf（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2 2章章 线性表线性表1.21.2 线性表的顺序存储结构线性表的顺序存储结构顺序存储结构的主要特性顺序存储结构的主要特性顺序表的定义顺序表的定义顺序表相关操作的实现顺序表相关操作的实现顺序表的特点顺序表的特点主要内容3线性表的顺序表示线性表的顺序表示n用一组地址连续的空间存放线性表的数据元素，用一组地址连续的空间存放线性表的数据元素，数据元素按其逻辑关系次序依次存放数据元素按其逻辑关系次序依次存放n采用顺序存储结构存储的线性表又称顺序表采用顺序存储结构存储的线性表又称顺序表n顺序表的特点顺序表的特点n逻辑上相邻的数据元素，物理位置也相邻逻辑上相邻的数据元素，物理位置也相邻n元素之间的逻辑

2、关系通过物理位置的先后来元素之间的逻辑关系通过物理位置的先后来体现体现4设计存储结构的一般原则设计存储结构的一般原则n能够按照需要保存所有元素n逻辑关系的正确表示n便于操作的实现n存储空间效率高线性表的顺序存储方式线性表的顺序存储方式整数线性表整数线性表（35,27,49,18,60,54,77,83,41,0235,27,49,18,60,54,77,83,41,02）存储的形式）存储的形式关系的表示关系的表示位置相邻的元素具有前驱后继关系位置相邻的元素具有前驱后继关系存储空间的大小一旦确定不能改变存储空间的大小一旦确定不能改变线性表的顺序存储方式线性表的顺序存储方式使用静态或者动态的一维数

3、组存储数据元素使用静态或者动态的一维数组存储数据元素LOC LOC(i i)=)=LOC LOC(i i-1)+1)+l l=LOC(a1)+LOC(a1)+i i*l l=+i i*l la1a2a3a4a5aLOC(a3)LOC(a4)顺序表顺序表(SeqListSeqList)类的定义类的定义template template classclassSeqList Type Type*data;/顺序表存储数组顺序表存储数组int int MaxSize;/最大允许长度最大允许长度intintlast;/当前最后元素下标当前最后元素下标/遵从遵从C+C+的约定，从的约定，从0 0开始存储开

4、始存储，用，用-1 1表示不存在位置表示不存在位置public:public:SeqList(intintMaxSize=defaultSize);SeqList()delete delete data;intintLength()constconst return returnlast+1;intintFind(TypeType&x)const;const;intintIsIn(TypeType&x);intintInsert(Type&Type&x,intinti);intintRemove(TypeType&x);int int Next(TypeType&x);int int Prio

5、r(TypeType&x);int int IsEmpty()return returnlast=-1;intintIsFull()return return last=MaxSize-1;TypeTypeGet(intinti)returnreturni last？NULL:datai;SeqListSeqList L;L;a1a2 a3 a4 a5L.dataL.lastL.MaxSize-1TypeTypeGet(intinti)returnreturni last？NULL:datai;算法时间复杂度算法时间复杂度 O O（1 1）具有随机存取特性具有随机存取特性顺序表部分公共操作的实

6、现顺序表部分公共操作的实现存储结构：采用动态数组存储结构：采用动态数组template template SeqList:SeqList(int int sz)/构造函数构造函数if if(sz 0)MaxSize=sz;last=-1;data=new Typenew TypeMaxSize;if if(data=NULL)MaxSize=0;0;last=-1;return;return;LlastLlast=-1 1L.data顺序搜索图示x x=48 =48 x x=50=50template template intintSeqList:Find(TypeType&x)const c

7、onst/搜索函数：在表中从前向后顺序查找搜索函数：在表中从前向后顺序查找x xint int i=0;whilewhile(i last)returnreturn-1；/没有找到时返回没有找到时返回-1 1 else returnelse returni;从前向后：数组的下标由小向大从前向后：数组的下标由小向大搜索成功搜索成功ACN=ACN=%若搜索概率相等，则若搜索概率相等，则CAN=CAN=%+=(1+2+n)(1+2+n)=搜索不成功搜索不成功数据比较数据比较n n次次顺序搜索性能分析线性表的插入插入位置在什么范围内合法？插入位置在什么范围内合法？如何移动？下面的移动方法正确吗？如何移

8、动？下面的移动方法正确吗？for(for(intintj=j=i i;j=lastj=last;j+j+)datadata j+1j+1=data=data j j;15线性表的插入过程n检查插入的参数i是否合法，要求0=i=last+1n判断表中是否有空闲空间存放新的元素n修改最后一个数据元素的位置为last+n将an到ai数据元素依次后移一个位置n将新元素放到下标为i的位置上template template intintSeqList:Insert(TypeType&x,intinti)/在表中第在表中第i i个位置插入新元素个位置插入新元素x xif if(i last+1|last=

9、MaxSize-1)returnreturn0;/插入不成功插入不成功else else last+;for for(intintj=last;j i;j-)dataj=dataj-1;datai=x;returnreturn1;/插入成功插入成功 线性表的插入的实现顺序表插入性能分析AMN=AMN=(n+n(n+n-1+1+0)1+1+0)=平均移动表长一半的数据元素！平均移动表长一半的数据元素！删除位置在什么范围内合法？删除位置在什么范围内合法？如何移动？如何移动？for(for(intintj=i+1j=i+1;j=lastj=last;j+j+)datadata j j=data=da

10、ta j+1 j+1;lastlast-;线性表的删除过程线性表的删除过程19线性表的删除过程步骤n检查删除的参数检查删除的参数i i是否合法，要求是否合法，要求 0=0=i i=last=lastn将将ai+1ai+1到到alastalast数据元素依次前移一个位置数据元素依次前移一个位置n修改最后一个数据元素的位置为修改最后一个数据元素的位置为lastlast-template template intintSeqList:Remove(TypeType&x)/在表中删除已有元素在表中删除已有元素x xintinti=Find(x);/在表中搜索在表中搜索x xif if(i=0)last

11、-;for for(intintj=i;j=last;j+)dataj=dataj+1;returnreturn1;/成功删除成功删除 returnreturn0;/表中没有表中没有x x 线性表的删除过程实现顺序表删除性能分析 允许的删除位置为0，1，2，lastAMN=AMN=(n(n-1+n1+n-2+1)2+1)=%平均移动表长一半的数据元素！平均移动表长一半的数据元素！template template intintSeqList:Next(TypeType&x)/Gets the next element in list./Gets the next element in list

12、.intinti=Find(x);/find x/find xif if(i=0&i last)return return i+1;else returnelse return-1;/failurefailure template template int int SeqListSeqList:Prior(Type&x):Prior(Type&x)/gets the predecessor/gets the predecessorint int i i=Find(x);=Find(x);/find x/find xif(if(i i 0&0&i i=last)return=last)return i i-1;1;else return else return-1;1;线性表顺序存储结构的特点1.1.通过元素的存储顺序反映线性表中通过元素的存储顺序反映线性表中数据元素之间的逻辑关系；数据元素之间的逻辑关系；2.2.可随机存取顺序表的元素；可随机存取顺序表的元素；3.3.顺序表的插入、删除操作要通过移动元素顺序表的插入、删除操作要通过移动元素实现，效率较实现，效率较低低；4.4.元素较元素较少少时存储空间的时存储空间的利利用率较用率较低。低。