數(shù)據(jù)結(jié)構(gòu)第次課第二章線性表順序表

數(shù)據(jù)結(jié)構(gòu)第次課第二章線性表順序表第一頁，共四十二頁，編輯于2023年，星期三2.1線性表的邏輯結(jié)構(gòu)線性表：由n(n≧0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2，…an組成的有限序列。其中數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長度。當(dāng)n=0時(shí)稱為空表，常常將非空的線性表(n>0)記作：(a1，a2，…an)這里的數(shù)據(jù)元素ai(1≦i≦n)只是一個(gè)抽象的符號，其具體含義在不同的情況下可以不同。例1、26個(gè)英文字母組成的字母表（A，B，C、…、Z）例2、某校從1978年到1983年各種型號的計(jì)算機(jī)擁有量的變化情況。（6，17，28，50，92，188）線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集。這里的序不是指一定要是數(shù)值上的次序關(guān)系。第二頁，共四十二頁，編輯于2023年，星期三…….…….…….……..……..神經(jīng)衰弱17男790634張立立健康21男790633劉建平一般20女790632陳紅健康18男790631王小林健康情況年齡性別學(xué)號姓名例3、學(xué)生健康情況登記表如下：第三頁，共四十二頁，編輯于2023年，星期三

從以上例子可看出線性表的邏輯特征是：(1)對非空的線性表，有且僅有一個(gè)開始結(jié)點(diǎn)a1，它沒有直接前趨，而僅有一個(gè)直接后繼a2；(2)有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒有直接后繼，而僅有一個(gè)直接前趨an-1；(3)其余的內(nèi)部結(jié)點(diǎn)ai(2≦i≦n-1)都有且僅有一個(gè)直接前趨ai-1和一個(gè)直接后繼ai+1。

線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。第四頁，共四十二頁，編輯于2023年，星期三抽象數(shù)據(jù)類型線性表的定義如下：ADTList{

數(shù)據(jù)對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{稱n

為線性表的表長;

稱n=0

時(shí)的線性表為空表。}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{設(shè)線性表為(a1，a2,...，ai，...，an),

稱i為ai在線性表中的位序。}

基本操作：…

…}ADTList關(guān)系：相鄰元素的有序?qū)Φ谖屙摚菜氖?，編輯?023年，星期三

InitList(&L)操作結(jié)果：構(gòu)造一個(gè)空的線性表L。DestroyList(&L)初始條件：操作結(jié)果：線性表L已存在。銷毀線性表L。構(gòu)造n=0的線性表初始條件：操作前狀態(tài)第六頁，共四十二頁，編輯于2023年，星期三

ListEmpty(L)初始條件：操作結(jié)果：線性表L已存在。若L為空表，則返回TRUE，否則FALSE。（線性表判空）第七頁，共四十二頁，編輯于2023年，星期三ListLength(L)初始條件：操作結(jié)果：線性表L已存在。返回L中元素個(gè)數(shù)。（求線性表的長度）第八頁，共四十二頁，編輯于2023年，星期三

PriorElem(L,cur_e,&pre_e)初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。（求數(shù)據(jù)元素的前驅(qū)）當(dāng)不是第一個(gè)元素時(shí)，則存在，否則不存在該元素或是表的第一個(gè)元素，無定義。第九頁，共四十二頁，編輯于2023年，星期三NextElem(L,cur_e,&next_e)初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，則用next_e返回它的后繼，否則操作失敗，next_e無定義。（求數(shù)據(jù)元素的后繼）第十頁，共四十二頁，編輯于2023年，星期三GetElem(L,i,&e)

初始條件：

操作結(jié)果：線性表L已存在，用

e返回L中第i

個(gè)元素的值。（求線性表中某個(gè)數(shù)據(jù)元素）且1≤i≤LengthList(L)第十一頁，共四十二頁，編輯于2023年，星期三LocateElem(L,e,compare())初始條件：操作結(jié)果：線性表L已存在，e

為給定值，

compare()是元素判定函數(shù)。返回L中第1個(gè)與e滿足關(guān)系

compare()的元素的位序。若這樣的元素不存在，則返回值為0。（定位函數(shù)）第十二頁，共四十二頁，編輯于2023年，星期三

ListTraverse(L,visit())初始條件：操作結(jié)果：線性表L已存在。visit()為某個(gè)訪問函數(shù)。依次對L中每個(gè)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。（遍歷線性表）引用性操作不改變原表的結(jié)構(gòu)第十三頁，共四十二頁，編輯于2023年，星期三ClearList(&L)初始條件：操作結(jié)果：線性表L已存在。將L重置為空表。（線性表置空）第十四頁，共四十二頁，編輯于2023年，星期三PutElem(&L,i,&e)初始條件：操作結(jié)果：線性表L已存在，L中第i個(gè)元素賦值e。（改變數(shù)據(jù)元素的值）且1≤i≤LengthList(L)第十五頁，共四十二頁，編輯于2023年，星期三

ListInsert(&L,i,e)初始條件：操作結(jié)果：線性表L已存在，在L的第i個(gè)元素之前插入新的元素e，L的長度增1。（插入數(shù)據(jù)元素）且1≤i≤LengthList(L)+1改變了元素之間的關(guān)系第十六頁，共四十二頁，編輯于2023年，星期三ListDelete(&L,i,&e)初始條件：操作結(jié)果：線性表L已存在且非空，刪除L

的第

i

個(gè)元素，并用e返回其值，L的長度減1。（刪除數(shù)據(jù)元素）1≤i≤LengthList(L)第十七頁，共四十二頁，編輯于2023年，星期三利用上述定義的線性表類型可以實(shí)現(xiàn)其它更復(fù)雜的操作例

2-1第十八頁，共四十二頁，編輯于2023年，星期三

假設(shè):有兩個(gè)集合A和B分別用兩個(gè)線性表LA和LB表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員?，F(xiàn)要求一個(gè)新的集合A＝A∪B。例2-1

第十九頁，共四十二頁，編輯于2023年，星期三要求對線性表作如下操作：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表

LA中的數(shù)據(jù)元素插入到線性表LA

中去。上述問題可演繹為：AUB，相同的元素只有一個(gè)A和B本身也是集合，所以各自不含有重復(fù)元素第二十頁，共四十二頁，編輯于2023年，星期三1．從線性表LB中依次察看每個(gè)數(shù)據(jù)元素;2．依值在線性表LA中進(jìn)行查訪;3．若不存在，則插入之。GetElem(LB,i)→e

LocateElem(LA,e,equal())

ListInsert(LA,n+1,e)(n表示線性表LA當(dāng)前長度)操作步驟：第二十一頁，共四十二頁，編輯于2023年，星期三

GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和e相同的數(shù)據(jù)元素，則插入之

La_len=ListLength(La);//求線性表的長度

Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}//for}//unionvoidunion(List&La,ListLb){第二十二頁，共四十二頁，編輯于2023年，星期三思考已知一個(gè)非純集合B（集合中可能含有重復(fù)元素），試構(gòu)造一個(gè)純集合A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。第二十三頁，共四十二頁，編輯于2023年，星期三2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1線性表

把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡稱順序表。假設(shè)線性表的每個(gè)元素需占用m個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置作為參考點(diǎn)。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置Loc(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置Loc(ai)之間滿足下列關(guān)系：

Loc(ai+1)=Loc(ai)+maiai+1Loc(ai+1)m個(gè)字節(jié)Loc(ai)線性表數(shù)據(jù)類型的實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)有兩種映像方法：順序和鏈?zhǔn)?。第二十四頁，共四十二頁，編輯?023年，星期三線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為:a1a2aianLoc(a1)i-1個(gè)元素Loc(ai)=(i-1)*m+Loc(a1)=Loc(a1)-m+i*m由于Loc(a1)和m都是已知的所以：V0=Loc(a1)-mLoc(ai)=V0+i*m第二十五頁，共四十二頁，編輯于2023年，星期三

由于在高級語言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組類型來描述順序表。又因?yàn)槌擞脭?shù)組來存儲(chǔ)線性表的元素之外，順序表還應(yīng)該用一個(gè)變量來表示線性表的長度屬性，利用C++語言的結(jié)構(gòu)類型來定義順序表類型。

#defineListSize100//表容量

typedefintDataType;//以int為例

structSqlist{DataTypedata[ListSize];intlength;//當(dāng)前表中元素?cái)?shù)};或structSqlist{DataType*elem;//存儲(chǔ)空間基址intListsize;//當(dāng)前分配的存儲(chǔ)容量intlength//當(dāng)前表中元素?cái)?shù)}length………..SqlistdataListSize個(gè)第二十六頁，共四十二頁，編輯于2023年，星期三2.2.2順序表上實(shí)現(xiàn)的基本操作在順序表存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個(gè)元素的訪問。注意：C/C++語言中的數(shù)組下標(biāo)從“0”開始，因此，若L是Sqlist類型的順序表，則表中第i個(gè)元素位置是L.data[i-1]。線性表的基本操作在順序表中的實(shí)現(xiàn)InitList(&L)//結(jié)構(gòu)初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i)//刪除元素第二十七頁，共四十二頁，編輯于2023年，星期三Status

InitList_Sq(SqList&L,intmaxsize)

{//構(gòu)造一個(gè)最大容量為maxsize的順序表

}//InitList_Sq算法時(shí)間復(fù)雜度：O(1)L.elem=newElemType[maxsize];

//

為順序表分配大小為maxsize的數(shù)組空間if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=maxsize;returnOK;New和delete運(yùn)算符分別用于為指針變量動(dòng)態(tài)分配內(nèi)存空間和動(dòng)態(tài)回收指針?biāo)赶虻脙?nèi)存空間。使用new得格式為：Intn;cin>>n;Float*p;P=newfloat[n];Deletep;第二十八頁，共四十二頁，編輯于2023年，星期三例如：順序表23754138546217L.elemL.length=7L.listsize第二十九頁，共四十二頁，編輯于2023年，星期三線性表操作

ListInsert(&L,i,e)的實(shí)現(xiàn)：首先分析:插入元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？第三十頁，共四十二頁，編輯于2023年，星期三

(a1,…,ai-1,ai,…,an)改變?yōu)閍1a2

…ai-1ai

…ana1a2

…ai-1

…ai

ean<ai-1,ai><ai-1,e>,<e,ai>表的長度增加(a1,…,ai-1,e,ai,…,an)第三十一頁，共四十二頁，編輯于2023年，星期三2118307542568721183075例如：ListInsert(L,5,66)

L.length-1087564266第三十二頁，共四十二頁，編輯于2023年，星期三voidListInsert(&L,i,e)//在線性表L中第i個(gè)位置插入元素e{if(i<1||i>L.length+1){cout<<“插入序號錯(cuò)誤”<<endl;returnERROR;}if(L.length>=ListSize)溢出處理；else{for(j=L.length-1;j>=i-1;j--)//第i個(gè)元素（下標(biāo)為i-1)開始

L.data[j+1]=L.data[j];//順序后移

L.data[i-1]=e;L.length++;}}

過程演示第三十三頁，共四十二頁，編輯于2023年，星期三算法分析設(shè)表的長度為n。該算法的時(shí)間主要花費(fèi)在循環(huán)的結(jié)點(diǎn)后移語句上，該語句的執(zhí)行次數(shù)（即移動(dòng)結(jié)點(diǎn)的次數(shù)）是n-i+1。由此，所需移動(dòng)結(jié)點(diǎn)的次數(shù)依賴于(1)表的長度(2)插入位置。當(dāng)=n+1時(shí)，不移動(dòng)->最好情況；當(dāng)=1時(shí)，需移動(dòng)表中所有結(jié)點(diǎn)->最壞情況，a1，…ai-1，ai，…，anx移動(dòng)數(shù)據(jù)：n-i+1第三十四頁，共四十二頁，編輯于2023年，星期三算法的平均移動(dòng)

由于插入可能在表中任何位置上進(jìn)行，在長度為n的線性表中第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)，令Eis(n)表示移動(dòng)結(jié)點(diǎn)的期望值（即移動(dòng)的平均次數(shù)），則在第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i+1。Pi代表在第i個(gè)位置插入概率，則

Eis(n)=p1*

n+p2*(n-1)+….+pn*1+pn+1*0

若表中任何位置(1≦i≦n+1)上插入結(jié)點(diǎn)的概率是均等的，則

p1=p2=p3=…=pn+1=1/(n+1)因此，在等概率插入的情況下：

Eis(n)=1/(n+1)[n+(n-1)+…+1+0]=n/2結(jié)論a1，…ai-1，ai，…，an可能的插入點(diǎn)有n+1處第三十五頁，共四十二頁，編輯于2023年，星期三結(jié)論：在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長n較大時(shí)，算法的效率相當(dāng)?shù)?。雖然Eis(n)中n的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。因此算法的平均時(shí)間復(fù)雜度為O(n)。第三十六頁，共四十二頁，編輯于2023年，星期三線性表操作

ListDelete(&L,i,&e)的實(shí)現(xiàn)：首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？第三十七頁，共四十二頁，編輯于2023年，星期三

(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)閍i+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長度減少a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

(a1,…,ai-1,ai+1,…,an)第三十八頁，共四十二頁，編輯于2023年，星期三21183