軟件技術(shù)基礎(chǔ)課件

19-12.2線性表及其順序存儲(chǔ)結(jié)構(gòu)19-22.2.1

線性表及其運(yùn)算1.什么是線性表是由n（n≥0）個(gè)若干個(gè)具有線性結(jié)構(gòu)的數(shù)據(jù)元素a1,a2,a3,…,an的有限序列。是一種最常用、最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，每個(gè)元素具有相同類型，可以是數(shù)字、符號(hào)、記錄等。例：①（0，1，2，3，…，9）②（a，b，c，…，z）③文件：含有大量記錄（數(shù)據(jù)元素） 的線性表19-3非空線性表結(jié)構(gòu)特征：有且只有一個(gè)根結(jié)點(diǎn)a1，它無(wú)前件。有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件。除根結(jié)點(diǎn)和終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。19-4線性表的形式定義：含有n個(gè)數(shù)據(jù)元素的線性表是一個(gè)數(shù)據(jù)結(jié)構(gòu)：

Linear_list=(D,R)其中：D={ai|ai∈D0,i=1,2,…,n,n≥0}，R={N}，N={<ai-1,ai>|ai-1,ai∈D0,i=2,3,…,n}；1、D是具有相同特性數(shù)據(jù)元素的有限集，2、R是D上關(guān)系的有限集；關(guān)系N是序偶的集合,元素之間的相鄰關(guān)系，即ai-1領(lǐng)先于ai，ai領(lǐng)先于ai+1（直接前驅(qū)，直接后繼）；3、數(shù)據(jù)個(gè)數(shù)n（n≥0）稱作線性表的長(zhǎng)度，n=0為空表；4、線性表的表示：（a1,a2,a3,…,ai,…,an）19-52線性表的順序存貯結(jié)構(gòu)兩種方式表示線性表（計(jì)算機(jī)內(nèi)部）：①用一組地址連續(xù)的存貯單元依次存貯線性表的每個(gè)元素；

——

順序存貯結(jié)構(gòu)，順序映象。②用一組任意的存貯單元（可連續(xù)、可不連續(xù)）存貯線性表的每個(gè)元素。 ——非順序存貯結(jié)構(gòu)，鏈?zhǔn)接诚蟆?9-6什么是順序存貯結(jié)構(gòu)1.

所有元素所占的存儲(chǔ)空間是連續(xù)的。2.邏輯關(guān)系上相鄰的元素在物理位置上也相鄰。(邏輯上的順序關(guān)系R通過(guò)位置上的順序關(guān)系映射）3.確定了起始位置，任一元素都可隨機(jī)存取(位置可解析）

。

順序存貯結(jié)構(gòu)的線性表稱為順序表。設(shè)每個(gè)元素占用k個(gè)存貯單元，則存貯位置滿足以下關(guān)系：

ADR(ai)=ADR(a1)+(i―1)＊k

1<=i<=na1

a2

…a

i………an12…i………n

aa+C…a+(i-1)*k………a+(n-1)*k

null19-7線性表順序存貯結(jié)構(gòu)C++描述usingnamespacestd;template<typenameT>//模版申明，T為類型參數(shù)voidinit_sq_LList(T*v,intm,int*n){ v=newT(m); //動(dòng)態(tài)申請(qǐng)m個(gè)存儲(chǔ)空間 *n=0; //線性表長(zhǎng)度*n置0 return;}19-8線性表的基本操作：1、初始化，設(shè)置一個(gè)空表。2、求長(zhǎng)度，返回表L中的元素個(gè)數(shù)3、求序號(hào)為i的元素值。4、求值為x的元素在表L中的位置序號(hào)。5、在第i個(gè)元素前插入元素x。6、刪除表L中第i個(gè)元素。刪除給定值的元素7、取元素ai的前趨。8、取元素ai的后繼。其它：求判空表操作，合并、拆分、復(fù)制、排序、逆轉(zhuǎn)等。注意：每個(gè)操作的條件判斷。19-93.順序表的插入運(yùn)算1、插入：在第i個(gè)元素ai

之前插入元素b即：(a1,a2,…,ai-1,ai,…,an) (a1,a2,…,ai-1,b,ai,…,an) 長(zhǎng)度nn+1將第n個(gè)至第i個(gè)共（n―i+1）個(gè)元素后移一個(gè)位置。19-10插入運(yùn)算的實(shí)現(xiàn)圖示基本操作的實(shí)現(xiàn)插入操作

i48插入b后移15234616571064

12345678nm12345678nm0123456715234616571064

4819-11插入運(yùn)算的異常處理1、當(dāng)存儲(chǔ)空間已滿（n=m）時(shí)為“上溢”錯(cuò)誤，不能插入，算法結(jié)束。2、當(dāng)i>n時(shí)，認(rèn)為在最后一個(gè)元素之后插入。3、當(dāng)i<1時(shí)，認(rèn)為在第一個(gè)元素之前插入。19-12插入運(yùn)算的C++描述#include<iostream>usingnamespacestd;template<classT>//模版申明，T為類型參數(shù)voidins_sq_LList(T*v,intm,int*n,inti,

Tb){ intk; if(*n==m) //存儲(chǔ)空間已滿，上溢錯(cuò)誤 {cout<<“overflow!”<<endl;return;}if(i>*n)i=*n+1; //默認(rèn)為在最后一個(gè)元素之后插入if(i<1)i=1; //默認(rèn)為在第一個(gè)元素之前插入 for(k=*n;k>=i;k--)v[k]=v[k-1]; //從后往前移動(dòng)元素v[i-1]=b;//插入新元素*n=*n+1;//增加線性表長(zhǎng)度return;}注：元素在數(shù)組中的存放

v[0]…v[*n-1]元素序號(hào)：1……..*n19-13效率分析基本操作：移動(dòng)元素for(k=*n;k>=i;k--)v[k]=v[k-1];

，

移動(dòng)次數(shù)：n－i+1插入位置概率：pi=1/(n+1)(包括最后位置)則平均次數(shù)（期望值）：

即平均移動(dòng)一半元素，時(shí)間復(fù)雜度為O(n)。19-14刪除：刪除第i個(gè)元素ai即(a1,a2,…,ai-1,ai,ai+1,…,an) (a1,a2,…,ai-1,ai+1,…,an)長(zhǎng)度nn－1將第i+1個(gè)至第n個(gè)共(n－i)個(gè)元素前移一個(gè)位置。時(shí)間復(fù)雜度為：O((n－1)/2)

O(n)

4.順序表的刪除運(yùn)算19-15刪除操作的實(shí)現(xiàn)圖示刪除操作

i15234616571064

12345678nm16刪除e01234567152346571064

1234567nm前移異常處理：1、當(dāng)線性表為空（n=0）時(shí)為“下溢”錯(cuò)誤，不能刪除，算法結(jié)束。2、當(dāng)i<1或i>n時(shí)，認(rèn)為在最后一個(gè)元素之后刪除，刪除無(wú)效。（P26有誤）19-16用數(shù)組實(shí)現(xiàn)線性表（順序存儲(chǔ)）線性表元素：a1、a2、a3、a4....數(shù)組元素：v[0]、v[1]、v[2]、v[3]….線性關(guān)系：a1a2a3a4數(shù)組下標(biāo)大小19-17刪除運(yùn)算的C++描述Include<iostream>usingnamespacestdtemplate<classT>//模版申明，T為類型參數(shù)voiddel_sq_LList(T*v,intm,int*n,inti){ intk; if(*n==0) //線性表為空，下溢錯(cuò)誤 {cout<<“underflow!”<<endl;return;}if((i<1)||

(i>*n)) //線性表中沒(méi)有這個(gè)元素 {cout<<“Nothiselementinthelist!”<<endl;return;} for(k=i;k<*n;k++)v[k-1]=v[k]; //從i開(kāi)始前移動(dòng)元素*n=*n-1;//線性表長(zhǎng)度-1return;}19-18順序表操作的注意事項(xiàng)表結(jié)構(gòu)的定義最大表空間的定義表空間的溢出處理非法位置的判斷節(jié)點(diǎn)移動(dòng)長(zhǎng)度修改19-195.順序表類sq_LListENDInclude<iostream>（P28-29）usingnamespacestdtemplate<classT>//模版申明，數(shù)據(jù)元素虛擬類型為T(mén)classsq_LList//順序表類{private:intmm;//數(shù)據(jù)成員:存儲(chǔ)空間容量intnn;//順序表長(zhǎng)度T*v;//順序表存儲(chǔ)空間首地址public://成員函數(shù)

sq_LList(){mm=0;nn=0;return} //構(gòu)造函數(shù)sq_LList(int)；//創(chuàng)建