2-3线性表的顺序存储

2-3线性表的顺序存储结构及实现v第二章线性表顺序表的存储结构顺序表的实现学什么？顺序表的类定义、构造函数、析构函数顺序表的判空、取长度操作：Empty、Length顺序表的查找操作：Get、Locate顺序表的插入、删除操作：Insert、Delete2-3-1顺序表的存储结构v第二章线性表顺序表的存储方法顺序表（向量）：线性表的顺序存储结构某些内存单元可能是空吗？例：（34,23,67,43）342367434存储要点用一段地址连续的存储单元依次存储线性表中的数据元素用什么属性来描述顺序表？342367434存储空间的起始位置顺序表的容量（最大长度）顺序表的当前长度例：（34,23,67,43）Page03顺序表的存储方法顺序表（向量）：线性表的顺序存储结构0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

长度数组的长度MaxSize线性表的长度lengthMaxSize≥length（a1,

…,ai-1

,ai,…,an）Page04顺序表的存储方法顺序表（向量）：线性表的顺序存储结构存取访问0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

长度（a1,

…,ai-1

,ai,…,an）如何求得任意元素的存储地址？cLoc(ai)Loc(a1)Loc(ai)=Loc(a1)+(i-1)×cPage07存取时间是O(1)随机存取2-3-2顺序表的实现v第二章线性表顺序表的实现——类定义InitList：表的初始化，建一个空表CreateList：建立具有n个元素的线性表DestroyList：销毁表，释放表所占用的存储空间Length：求表的长度Get：在表中取序号为i

的数据元素Locate：在线性表中查找值等于x

的元素Insert：在表的第i

个位置处插入一个新元素xDelete：删除表中的第i

个元素Empty：判断表是否为空线性表的抽象数据类型定义？constint

MaxSize=100;template<typename

DataType>classSeqList{public:

SeqList();

SeqList(DataTypea[],intn);

~SeqList();

intLength();

DataTypeGet(int

i);

intLocate(DataTypex);

voidInsert(int

i,DataTypex);

DtaTypeDelete(int

i);intEmpty();

intEmpty();

voidPrintList();private:

DataTypedata[MaxSize];

intlength;};顺序表的实现——初始化初始化顺序表的函数原型是什么？InitList

输入：无功能：表的初始化，建一个空表输出：无0…MaxSize-1

0SeqList<DataType>::SeqList(){Length=0;}SeqList<DataType>::SeqList(DataTypea[],intn){

}顺序表L

数组a35122433425if(n>MaxSize)throw“参数非法”;顺序表的实现——建立for(inti=0;i<n;i++)data[i]=a[i];length=n;3512243342顺序表的实现——判空intSeqList<DataType>::Empty(){if(length==0)return1;elsereturn0;}0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

nintSeqList<DataType>::Length(){returnlength;}求顺序表的长度？顺序表的实现——按位查找template<typenameDataType>DataTypeSeqList<DataType>::Get(inti){

if(i<1&&i>length)throw"查找位置非法";elsereturndata[i-1];}按位查找的时间复杂度？0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

lengthO(1)随机存取template<typenameDataType>intSeqList<DataType>::Locate(DataTypex){for(inti=0;i<length;i++)if(data[i]==x)returni+1;//返回其序号i+1return0;//退出循环，说明查找失败}0…i…n-1MaxSize-1a1…x…an

length按值查找的时间复杂度？O(n)顺序表的实现——按值查找顺序表的实现——插入33例1

对于线性表（35，12，24，42），在i=2的位置上插入元素33435122442a1a2a3a4012345什么情况下插入无法进行？注意边界条件表满：length>=MaxSize合理的插入位置：1≤i≤length+1（注意：i

指的是元素的序号）template<typenameDataType>voidSeqList<DataType>::Insert(inti,DataTypex){if(length==MaxSize)throw"上溢";

if(i<1||i>length+1)throw"插入位置错误";for(intj=length;j>=i;j--)data[j]=data[j-1];//第j个元素存在数组下标为j-1处data[i-1]=x;length++;}基本语句？执行多少次？顺序表的实现——插入

for(intj=length;j>=i;j--)data[j]=data[j-1];最好情况（i=n+1）：执行0次，时间复杂度为O(1)最坏情况（i=1）：执行n+1次，时间复杂度为O(n)平均情况（1≤i≤n+1）：时间复杂度为O(n)顺序表的实现——插入