T2-線性表(順序表)

順序表第二章：線性表主講：周翔回顧請(qǐng)簡述一下你對(duì)數(shù)據(jù)結(jié)構(gòu)的理解請(qǐng)思考：在設(shè)計(jì)一個(gè)算法時(shí)需要考慮到哪些因素預(yù)習(xí)檢查請(qǐng)概括一下線性表的概念請(qǐng)描述一下線性表的插入與刪除操作本章目標(biāo)3約瑟夫環(huán)重點(diǎn)了解掌握2線性的概念線性表的順序存儲(chǔ)線性表的鏈?zhǔn)酱鎯?chǔ)1什么是線性表主要學(xué)習(xí)內(nèi)容：線性表的概念及運(yùn)算（邏輯結(jié)構(gòu)）

線性表的順序存儲(chǔ)（物理結(jié)構(gòu)）

線性表的鏈?zhǔn)酱鎯?chǔ)（物理結(jié)構(gòu)）一元多項(xiàng)式的表示及相加（應(yīng)用）什么是線性表什么是線性表？線性表的定義線性結(jié)構(gòu)是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。特點(diǎn)：除第一個(gè)元素?zé)o直接前驅(qū)、最后一個(gè)元素?zé)o直接后繼外，集合中其它每個(gè)數(shù)據(jù)元素均有惟一的直接前驅(qū)和惟一的直接后繼。同一性：線性表由同類數(shù)據(jù)元素組成，每一個(gè)ai必須屬于同一數(shù)據(jù)對(duì)象有窮性：線性表由有限個(gè)數(shù)據(jù)元素組成，表長度就是表中數(shù)據(jù)元素的個(gè)數(shù)有序性：線性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系<ai,ai+1>線性表是一種具有線性結(jié)構(gòu)的抽象數(shù)據(jù)類型。線性表的定義線性表：用數(shù)據(jù)元素的有限序列表示（a1,a2,…ai-1，ai,ai＋1

，…,an）n=0時(shí)稱為數(shù)據(jù)元素線性起點(diǎn)ai的直接前趨ai的直接后繼空表線性終點(diǎn)下標(biāo)，是元素的序號(hào)，表示元素在表中的位置n為元素總個(gè)數(shù)，即表長線性表的定義a1a2a3a4a5定義：n(n≥0)個(gè)類型相同的數(shù)據(jù)元素的有限序列。n>0時(shí)，第一個(gè)元素?zé)o直接前驅(qū)，最后一個(gè)元素?zé)o直接后繼，其余的每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。n=0時(shí)，為空表。表長：表中元素的個(gè)數(shù)n。表中元素類型相同。

線性表的邏輯結(jié)構(gòu)圖為線性表的定義線性表的邏輯特征線性表是一種最簡單的數(shù)據(jù)結(jié)構(gòu)，它有如下幾個(gè)特征：（1）線性表中有且只有一個(gè)開始結(jié)點(diǎn)（頭結(jié)點(diǎn)），這個(gè)開始結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)；（2）線性表中有且只有一個(gè)末尾結(jié)點(diǎn)（尾結(jié)點(diǎn)），這個(gè)末尾結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)；（3）除去開始結(jié)點(diǎn)與末尾結(jié)點(diǎn)，其它結(jié)點(diǎn)都有一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。線性表的定義ADTLinearList{ 數(shù)據(jù)元素：D={ai|ai∈D0,i=1,2,…,n,n≥0,D0為某一數(shù)據(jù)對(duì)象} 數(shù)據(jù)關(guān)系：S={<ai,ai+1>|ai,ai+1∈D0，i=1,2,…,n-1｝ 基本操作： （1）InitList（L）將L初始化為空表。 （2）DestroyList(L)將L銷毀。 （3）ClearList(L)將表L置為空表。

………}ADTLinearList線性表的抽象數(shù)據(jù)類型定義線性表的物理結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)順序表非順序存儲(chǔ)結(jié)構(gòu)（鏈?zhǔn)酱鎯?chǔ)）單鏈表循環(huán)鏈表雙向鏈表線性表的物理結(jié)構(gòu)不管哪種存儲(chǔ)方式，它們的結(jié)構(gòu)都有如下特點(diǎn)：均勻性：雖然不同數(shù)據(jù)表的數(shù)據(jù)元素可以是各種各樣的，但對(duì)于同一個(gè)線性表來說，數(shù)據(jù)元素必須具有相同的數(shù)據(jù)類型和長度。有序性：各數(shù)據(jù)元素在線性表中的位置只取決于它們的序號(hào)，數(shù)據(jù)元素之間的相對(duì)位置是線性的，即存在唯一的“第一個(gè)”和“最后一個(gè)”數(shù)據(jù)元素，除了第一個(gè)和最后一個(gè)外，其它元素前面均只有一個(gè)數(shù)據(jù)元素（直接前驅(qū)），后面均只有一個(gè)數(shù)據(jù)元素（直接后繼）。順序表的定義順序存儲(chǔ)原理是什么？順序表的定義所謂順序存儲(chǔ)，就是在存儲(chǔ)器中分配一段連續(xù)的存儲(chǔ)空間，邏輯上相鄰的數(shù)據(jù)元素，其物理存儲(chǔ)地址也是相鄰的。如圖所示的線性表中，d和b的物理地址為連續(xù)的0x001和0x002，其邏輯編號(hào)為連續(xù)的0和1。順序表的定義存儲(chǔ)地址

內(nèi)存空間狀態(tài)

邏輯地址

Loc(a1)a11Loc(a1)+(2-1)ka2

2………loc(a1)+(i-1)kai

i………loc(a1)+(n-1)kan

n...

loc(a1)+(maxlen-1)k順序存儲(chǔ)結(jié)構(gòu)示意圖空閑順序表的定義存儲(chǔ)地址

內(nèi)存空間狀態(tài)

邏輯地址

假設(shè)為1000‘e’01001‘g’11002‘r’21003‘s’31004‘n’41005‘k’5空閑順序表的定義實(shí)際應(yīng)用中應(yīng)根據(jù)實(shí)際需要定義表中元素的數(shù)據(jù)類型，如int、char、float或是一種結(jié)構(gòu)類型注意區(qū)分元素的序號(hào)和數(shù)組的下標(biāo)，如a1的序號(hào)為1，而其對(duì)應(yīng)的數(shù)組下標(biāo)為0ADTSeqList{maxsize

100//線性表可能達(dá)到的最大長度ElemType

elem[maxsize] //線性表占用的數(shù)組空間int

last//記錄線性表中最后一個(gè)元素在數(shù)組elem[]中的位置（下標(biāo)值），空表置為-1}ADTSeqList102030405060elem0123456789last順序表的基本操作基本操作初始化查找插入取值刪除15432順序表的基本操作——查找操作查找操作——兩種基本查找運(yùn)算：按序號(hào)查找GetData(L,i)：要求查找線性表L中第i個(gè)數(shù)據(jù)元素按內(nèi)容查找Locate(L,e)：要求查找線性表L中與給定值e相等的數(shù)據(jù)元素若在表L中找到與e相等的元素，則返回該元素在表中的序號(hào)；若找不到，則返回一個(gè)“空序號(hào)”，如-1。順序表的基本操作——查找操作253457

164809

012345tablei253457

164809

i253457

164809

i253457

164809

i查找成功i=4查找數(shù)字16順序表的基本操作——查找操作2534571648

01234tablei2534571648

i2534571648

i2534571648

i2534571648

i查找失敗i=-1查找數(shù)字50順序表的基本操作——插入操作已知，線性表(25,34,57,16,48,09)，需在第3個(gè)元素之前插入一個(gè)元素“21”需要將第6個(gè)位置到第3個(gè)位置的元素依次后移一個(gè)位置，然后將“21”插入到第3個(gè)位置順序表的基本操作——插入操作最好情況：表尾（i=L->last+2）插入元素不需要移動(dòng)元素，直接在表尾插入最壞情況：在表頭（i=1）插入元素表中所有元素都必須依次后移一個(gè)位置（n個(gè)）平均移動(dòng)元素個(gè)數(shù)最壞（平均）時(shí)間復(fù)雜度為O(n)順序表的基本操作——?jiǎng)h除操作已知，線性表(25,34,57,16,48,09)，將第3個(gè)元素刪除，順序表的基本操作——?jiǎng)h除操作最好情況：刪除表尾（i=L->last+1）元素不需要移動(dòng)元素，僅將表長度減1最壞情況：刪除表頭（i=1）元素表中余下元素都必須依次前移一個(gè)位置(n-1個(gè))平均移動(dòng)元素個(gè)數(shù)最壞（平均）時(shí)間復(fù)雜度為O(n)順序表的基本操作查找、插入、刪除算法的平均時(shí)間復(fù)雜度為：O(n)顯然，順序表的空間復(fù)雜度S(n)=O(1)（沒有占用輔助空間）順序表的基本操作——合并操作0821254962下標(biāo):0

1

2

3

4

0

1

2

3

4

5LA08LC16212537495462728290163754728290LB下標(biāo):

0

1

2

3

4

5

6

7

8

9

10

已知

：有兩個(gè)順序表LA和LB，其元素均為非遞減有序排列，編寫一個(gè)算法，將它們合并成一個(gè)順序表LC，要求LC也是非遞減有序排列順序表的基本操作——合并操作算法思想：設(shè)表LC是一個(gè)空表設(shè)兩個(gè)指針i、j分別指向表LA和LB中的元素LB的元素小（LA.elem[i]>LB.elem[j]）：將LB.elem[j]插入到表LC中LA的元素?。↙A.elem[i]≤LB.elem[j]）：將LA.elem[i]插入到表LC中如此進(jìn)行下去，直到其中一個(gè)表被掃描完畢，然后再將未掃描完的表中剩余的所有元素放到表LC中順序表的基本操作——合并操作0821254962下標(biāo):0

1

2

3

4

0

1

2

3

4

5LA08<1608LCij21>161621<372125<372549>373749<544962>545462<7262處理剩余元素728290163754728290LBK下標(biāo):

0

1

2

3

4

5

6

7

8

9

10

順序表的特點(diǎn)順序表（順序存儲(chǔ)結(jié)構(gòu)）的特點(diǎn)利用數(shù)據(jù)元素的存儲(chǔ)位置表示線性表中相鄰數(shù)據(jù)元素之間的前后關(guān)系，即線性表的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)一致在訪問線性表時(shí)，可以快速地計(jì)算出任何一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址。因此可以粗略地認(rèn)為，訪問每個(gè)元素所花時(shí)間相等順序表的優(yōu)缺點(diǎn)順序表（順序存儲(chǔ)結(jié)構(gòu)）的優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外