2-3線性表的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)v第二章線性表順序表的存儲結(jié)構(gòu)順序表的實(shí)現(xiàn)學(xué)什么？順序表的類定義、構(gòu)造函數(shù)、析構(gòu)函數(shù)順序表的判空、取長度操作：Empty、Length順序表的查找操作：Get、Locate順序表的插入、刪除操作：Insert、Delete2-3-1順序表的存儲結(jié)構(gòu)v第二章線性表順序表的存儲方法順序表（向量）：線性表的順序存儲結(jié)構(gòu)某些內(nèi)存單元可能是空嗎？例：（34,23,67,43）342367434存儲要點(diǎn)用一段地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素用什么屬性來描述順序表？342367434存儲空間的起始位置順序表的容量（最大長度）順序表的當(dāng)前長度例：（34,23,67,43）Page03順序表的存儲方法順序表（向量）：線性表的順序存儲結(jié)構(gòu)0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

長度數(shù)組的長度MaxSize線性表的長度lengthMaxSize≥length（a1,

…,ai-1

,ai,…,an）Page04順序表的存儲方法順序表（向量）：線性表的順序存儲結(jié)構(gòu)存取訪問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)隨機(jī)存取2-3-2順序表的實(shí)現(xiàn)v第二章線性表順序表的實(shí)現(xiàn)——類定義InitList：表的初始化，建一個空表CreateList：建立具有n個元素的線性表DestroyList：銷毀表，釋放表所占用的存儲空間Length：求表的長度Get：在表中取序號為i

的數(shù)據(jù)元素Locate：在線性表中查找值等于x

的元素Insert：在表的第i

個位置處插入一個新元素xDelete：刪除表中的第i

個元素Empty：判斷表是否為空線性表的抽象數(shù)據(jù)類型定義？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;};順序表的實(shí)現(xiàn)——初始化初始化順序表的函數(shù)原型是什么？InitList

輸入：無功能：表的初始化，建一個空表輸出：無0…MaxSize-1

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

}順序表L

數(shù)組a35122433425if(n>MaxSize)throw“參數(shù)非法”;順序表的實(shí)現(xiàn)——建立for(inti=0;i<n;i++)data[i]=a[i];length=n;3512243342順序表的實(shí)現(xiàn)——判空intSeqList<DataType>::Empty(){if(length==0)return1;elsereturn0;}0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

nintSeqList<DataType>::Length(){returnlength;}求順序表的長度？順序表的實(shí)現(xiàn)——按位查找template<typenameDataType>DataTypeSeqList<DataType>::Get(inti){

if(i<1&&i>length)throw"查找位置非法";elsereturndata[i-1];}按位查找的時間復(fù)雜度？0…i-2i-1…n-1MaxSize-1a1…ai-1ai…an

lengthO(1)隨機(jī)存取template<typenameDataType>intSeqList<DataType>::Locate(DataTypex){for(inti=0;i<length;i++)if(data[i]==x)returni+1;//返回其序號i+1return0;//退出循環(huán)，說明查找失敗}0…i…n-1MaxSize-1a1…x…an

length按值查找的時間復(fù)雜度？O(n)順序表的實(shí)現(xiàn)——按值查找順序表的實(shí)現(xiàn)——插入33例1

對于線性表（35，12，24，42），在i=2的位置上插入元素33435122442a1a2a3a4012345什么情況下插入無法進(jìn)行？注意邊界條件表滿：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個元素存在數(shù)組下標(biāo)為j-1處data[i-1]=x;length++;}基本語句？執(zhí)行多少次？順序表的實(shí)現(xiàn)——插入

for(intj=length;j>=i;j--)data[j]=data[j-1];最好情況（i=n+1）：執(zhí)行0次，時間復(fù)雜度為O(1)最壞情況（i=1）：執(zhí)行n+1次，時間復(fù)雜度為O(n)平均情況（1≤i≤n+1）：時間復(fù)雜度為O(n)順序表的實(shí)現(xiàn)——插入