T2-線性表(順序表)

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

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

線性表的鏈?zhǔn)酱鎯Γㄎ锢斫Y(jié)構(gòu)）一元多項式的表示及相加（應(yīng)用）什么是線性表什么是線性表？線性表的定義線性結(jié)構(gòu)是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。特點：除第一個元素?zé)o直接前驅(qū)、最后一個元素?zé)o直接后繼外，集合中其它每個數(shù)據(jù)元素均有惟一的直接前驅(qū)和惟一的直接后繼。同一性：線性表由同類數(shù)據(jù)元素組成，每一個ai必須屬于同一數(shù)據(jù)對象有窮性：線性表由有限個數(shù)據(jù)元素組成，表長度就是表中數(shù)據(jù)元素的個數(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ù)據(jù)元素線性起點ai的直接前趨ai的直接后繼空表線性終點下標(biāo)，是元素的序號，表示元素在表中的位置n為元素總個數(shù)，即表長線性表的定義a1a2a3a4a5定義：n(n≥0)個類型相同的數(shù)據(jù)元素的有限序列。n>0時，第一個元素?zé)o直接前驅(qū)，最后一個元素?zé)o直接后繼，其余的每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼。n=0時，為空表。表長：表中元素的個數(shù)n。表中元素類型相同。

線性表的邏輯結(jié)構(gòu)圖為線性表的定義線性表的邏輯特征線性表是一種最簡單的數(shù)據(jù)結(jié)構(gòu)，它有如下幾個特征：（1）線性表中有且只有一個開始結(jié)點（頭結(jié)點），這個開始結(jié)點沒有前驅(qū)結(jié)點；（2）線性表中有且只有一個末尾結(jié)點（尾結(jié)點），這個末尾結(jié)點沒有后繼結(jié)點；（3）除去開始結(jié)點與末尾結(jié)點，其它結(jié)點都有一個前驅(qū)結(jié)點和一個后繼結(jié)點。線性表的定義ADTLinearList{ 數(shù)據(jù)元素：D={ai|ai∈D0,i=1,2,…,n,n≥0,D0為某一數(shù)據(jù)對象} 數(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)順序存儲結(jié)構(gòu)順序表非順序存儲結(jié)構(gòu)（鏈?zhǔn)酱鎯Γ﹩捂湵硌h(huán)鏈表雙向鏈表線性表的物理結(jié)構(gòu)不管哪種存儲方式，它們的結(jié)構(gòu)都有如下特點：均勻性：雖然不同數(shù)據(jù)表的數(shù)據(jù)元素可以是各種各樣的，但對于同一個線性表來說，數(shù)據(jù)元素必須具有相同的數(shù)據(jù)類型和長度。有序性：各數(shù)據(jù)元素在線性表中的位置只取決于它們的序號，數(shù)據(jù)元素之間的相對位置是線性的，即存在唯一的“第一個”和“最后一個”數(shù)據(jù)元素，除了第一個和最后一個外，其它元素前面均只有一個數(shù)據(jù)元素（直接前驅(qū)），后面均只有一個數(shù)據(jù)元素（直接后繼）。順序表的定義順序存儲原理是什么？順序表的定義所謂順序存儲，就是在存儲器中分配一段連續(xù)的存儲空間，邏輯上相鄰的數(shù)據(jù)元素，其物理存儲地址也是相鄰的。如圖所示的線性表中，d和b的物理地址為連續(xù)的0x001和0x002，其邏輯編號為連續(xù)的0和1。順序表的定義存儲地址

內(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順序存儲結(jié)構(gòu)示意圖空閑順序表的定義存儲地址

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

邏輯地址

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

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

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

last//記錄線性表中最后一個元素在數(shù)組elem[]中的位置（下標(biāo)值），空表置為-1}ADTSeqList102030405060elem0123456789last順序表的基本操作基本操作初始化查找插入取值刪除15432順序表的基本操作——查找操作查找操作——兩種基本查找運算：按序號查找GetData(L,i)：要求查找線性表L中第i個數(shù)據(jù)元素按內(nèi)容查找Locate(L,e)：要求查找線性表L中與給定值e相等的數(shù)據(jù)元素若在表L中找到與e相等的元素，則返回該元素在表中的序號；若找不到，則返回一個“空序號”，如-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個元素之前插入一個元素“21”需要將第6個位置到第3個位置的元素依次后移一個位置，然后將“21”插入到第3個位置順序表的基本操作——插入操作最好情況：表尾（i=L->last+2）插入元素不需要移動元素，直接在表尾插入最壞情況：在表頭（i=1）插入元素表中所有元素都必須依次后移一個位置（n個）平均移動元素個數(shù)最壞（平均）時間復(fù)雜度為O(n)順序表的基本操作——刪除操作已知，線性表(25,34,57,16,48,09)，將第3個元素刪除，順序表的基本操作——刪除操作最好情況：刪除表尾（i=L->last+1）元素不需要移動元素，僅將表長度減1最壞情況：刪除表頭（i=1）元素表中余下元素都必須依次前移一個位置(n-1個)平均移動元素個數(shù)最壞（平均）時間復(fù)雜度為O(n)順序表的基本操作查找、插入、刪除算法的平均時間復(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

已知

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

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