數(shù)據(jù)結(jié)構(gòu)（自考） 課件 第二章線性表

全國高等教育自學(xué)考試指定教材

計算機及應(yīng)用專業(yè)（專科段）數(shù)據(jù)結(jié)構(gòu)第二章線性表學(xué)習(xí)目標(biāo)理解線性表的相關(guān)概念，了解其邏輯定義及基本操作，理解線性表數(shù)據(jù)元素之間的邏輯關(guān)系掌握線性表的順序存儲方式及鏈?zhǔn)酱鎯Ψ绞?，了解各自的特點掌握順序表及鏈表基本操作的實現(xiàn)，并能進行復(fù)雜度分析靈活運用線性表的基本操作，設(shè)計算法解決與線性表相關(guān)的實際問題本章主要內(nèi)容線性表的定義和基本操作12線性表的鏈?zhǔn)酱鎯皩崿F(xiàn)3線性表的順序存儲及實現(xiàn)兩種基本實現(xiàn)方式的比較4單鏈表的應(yīng)用52.1線性表的定義和基本操作線性表是一種線性結(jié)構(gòu)。在這種結(jié)構(gòu)中，存在著唯一的“第1個”元素、唯一的“第2個”元素，依此類推線性表中各個元素依次排列例1.1中給出的某班30名同學(xué)的基本信息（表1.1），就可以組成一個線性表，可以按照學(xué)號排列名單

定義定義2.1一個線性表（linearlist）是由同類型數(shù)據(jù)元素構(gòu)成的有限序列由n(n≥0)個元素組成的線性表LL=(a0,a1,…,an-1)這里，ai(0≤i≤n-1)即是線性表中的數(shù)據(jù)元素，也稱為表項線性表中所有數(shù)據(jù)元素都必須是相同類型的數(shù)據(jù)元素的次序就是它們在表中的排列次序第1個元素是a0，稱為表頭或開始元素第n個也即最后一個元素是an-1，稱為表尾或終端元素元素的個數(shù)n稱為表長n=0時稱為空表，記為()

示例

例2.1將例1.1的學(xué)生基本信息表表示為線性表StudentStudent=

((M2022103001王義平男2004.11.22山東),

(M2022103002陸東男2004.02.05河南),…,

(M2022103030楊志強男2004.10.30陜西))

線性表中常使用非負(fù)整數(shù)表示各元素的位置表頭a0的位置為0a1的位置為1ai(0≤i≤n-1)的位置為i對于元素ai(1≤i≤n-1)，元素aj(0≤j<i)稱為ai的前驅(qū)，其中元素ai-1稱為ai的直接前驅(qū)對于元素ai(0≤i≤n-2)，元素aj(i<j≤n-1)稱為ai的后繼，其中元素ai+1稱為ai的直接后繼

在不引起歧義的情況下，直接前驅(qū)可以簡稱為前驅(qū)，直接后繼可以簡稱為后繼“線性”的含義和特點除表頭a0外，每個元素有且僅有一個直接前驅(qū)除表尾an-1外，每個元素有且僅有一個直接后繼線性表中各元素的次序是固有的，即元素ai(1≤i≤n-2)排在ai-1的后面，且排在元素ai+1的前面

如果線性表中各元素的值可以進行比較，并且表中元素的值按位置順序遞增或遞減排列，即按值的“大小”有序排列，則線性表稱為有序表表中元素的值不滿足按位置順序遞增或遞減關(guān)系的線性表稱為無序表

線性表有3個特點，分別是各元素屬于同一個類型元素個數(shù)是有限的各元素之間不一定有大小關(guān)系，但一定有次序關(guān)系

示例寫出10以內(nèi)（不含10）的非負(fù)偶數(shù)組成的線性表10以內(nèi)（不含10）的非負(fù)偶數(shù)共有5個，可以寫出如下的不同形式L1=(0,2,4,6,8) //遞增有序表L2=(8,6,4,2,0) //遞減有序表L3=(2,6,4,0,8) //無序表線性表的基本操作線性表中有幾個基本操作會涉及到位置position

LinearList中定義的函數(shù)都有返回值操作的幾個示例序號操作操作結(jié)果解釋1initList(&s)()創(chuàng)建空線性表s2for(i=0;i<6;i++)insert(&s,i,2*i)(0,2,4,6,8,10)在空表s的表尾處依次插入6個值3remove(&s,3,&x)(0,2,4,8,10)刪除位置3的值并由x返回該值4setValue(&s,3,-10)(0,2,4,-10,10)給位置3的元素賦值-105find(s,10)返回值是4在s中查找10，10在位置46find(s,9)返回值是-1在s中查找9，沒有找到2.2線性表的順序存儲及實現(xiàn)操作的具體實現(xiàn)需要依賴于線性表的存儲結(jié)構(gòu)。可以使用順序存儲方式和鏈?zhǔn)酱鎯Ψ绞奖４婢€性表，從而得到線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)順序存儲結(jié)構(gòu)使用數(shù)組保存線性表中的各元素，相應(yīng)的線性表稱為順序表鏈?zhǔn)酱鎯Y(jié)構(gòu)使用鏈表保存線性表中的各元素，相應(yīng)的線性表稱為鏈表順序表順序存儲的基本思想是使用一組連續(xù)的存儲單元依次存儲各個元素，將線性表中的各數(shù)據(jù)元素，按照其邏輯次序，依次保存在數(shù)組的各個單元中線性表中邏輯上相鄰的兩個元素，保存在數(shù)組相鄰的兩個單元中

分配一個多大的數(shù)組是個挑戰(zhàn)順序表的顯著特點

分配了數(shù)組空間后，將線性表中的n個元素依次保存在數(shù)組中，從表頭至表尾的各個元素分別對應(yīng)下標(biāo)0到下標(biāo)n-1的位置數(shù)組是內(nèi)存中一片連續(xù)的空間，相鄰的兩個單元在內(nèi)存中的實際地址也是相鄰的，這表明，線性表中邏輯上相鄰的兩個元素，其存儲地址也是相鄰的存儲示意圖假設(shè)線性表L=(a0,a1,a2,a3,a4,a5)，每個元素需要占用2個字節(jié)，分配一個含8個元素的數(shù)組A保存LA在內(nèi)存中的示意圖數(shù)組下標(biāo)與線性表元素的位置相對應(yīng)線性表元素依次存放的特性，決定著表中元素i（i≥0）存儲在數(shù)組的下標(biāo)i處表頭元素保存在位置0處，這個位置也稱為數(shù)組的首地址只要給定數(shù)組下標(biāo)，就能立即計算出相應(yīng)元素的存儲地址，并據(jù)此訪問該元素地址計算

設(shè)LOC(ai)表示元素ai的存儲首地址，每個元素需占用d個存儲單元，則有 LOC(ai)=LOC(ai-1)+d進一步地有 LOC(ai)=LOC(a0)+i

dLOC(a0)即是數(shù)組的首地址示例

例2.4設(shè)順序表的每個元素占8個存儲單元。第1個元素的存儲首地址為100，則第6個元素占用的最后一個存儲單元的地址是A．132 B．139 C．140 D．147解：答案是Dd=8，LOC(a0)=100，第6個元素是a5LOC(a5)=LOC(a0)+5

8=100+40=140即第6個元素占用從140開始的8個存儲單元，那么最后一個存儲單元是147插入和刪除設(shè)給定一個順序表，初始時含有5個元素。在位置2插入元素27，然后刪除位置3的元素初始順序表在位置2插入元素27刪除位置3的元素

11523196

……

1152723196

……

11527196

……

順序表基本運算的實現(xiàn)順序表的定義構(gòu)造空表及清空表判表空、判表滿、求表長插入新元素插入操作中移動元素的平均次數(shù)為n/2刪除操作刪除操作中移動元素的平均次數(shù)為(n-1)/2賦值、取值操作查找測試示例例2.5設(shè)有順序表L，表長為n，保存在數(shù)組A中。實現(xiàn)算法將L逆置，即 L=(a0,a1,…,an-2,an-1)變?yōu)?L=(an-1,an-2,…,a1,a0)將A[0]與A[n-1]進行交換，然后將A[1]與A[n-2]進行交換，依此類推，當(dāng)交換到L中間元素時，算法結(jié)束算法實現(xiàn)intreverse(LinearList*L) //將順序表L逆置{ ELEMTypex; inti,len; len=L->n; if(len==0)return1; //空表，直接返回 for(i=0;i<len/2;i++) swap(&(L->element[i]),&(L->element[len-i-1])); return1;}2.3線性表的鏈?zhǔn)酱鎯皩崿F(xiàn)線性表還可以使用鏈?zhǔn)酱鎯Ψ绞奖４?，即線性表中的各個元素保存在各自的存儲空間中，形成一個個的結(jié)點這些結(jié)點在內(nèi)存中的地址不要求是相鄰的，它們之間通過指針連接起來以這種方式保存的線性表稱為鏈表每個結(jié)點中包含元素值和指向其他結(jié)點的指針，指針的個數(shù)可以是一個，也可能是兩個，從而形成不同形式的鏈表鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種動態(tài)靈活的存儲方式，它不要求預(yù)先分配一塊連續(xù)的存儲空間，而是按需分配，隨時需要隨時分配同時不要求分配的空間必須是相鄰的，而是由系統(tǒng)決定分配的具體位置，既可以相鄰也可以不相鄰所以在執(zhí)行插入及刪除操作時，不再需要移動元素以保證存儲空間的相鄰性單鏈表單鏈表是由一組動態(tài)分配的結(jié)點形成的鏈表，每個結(jié)點保存線性表中的一個元素及一個指針，指針指向保存其后繼元素的結(jié)點保存L的單鏈表示意圖結(jié)點定義單鏈表中結(jié)點及鏈表的定義typedefintELEMType;typedefstructnode{ //單鏈表結(jié)點 ELEMTypedata; //數(shù)據(jù)域 structnode*next; //指針域}LinkNode;typedefLinkNode*LinkList; //單鏈表typedefintposition;示例要在上圖所示的單鏈表L的位置2處插入元素E。當(dāng)前指針為p，指向位置2操作步驟是創(chuàng)建一個新結(jié)點，新結(jié)點中保存值E讓新結(jié)點的next指針指向指針p指向的結(jié)點，這個結(jié)點是當(dāng)前結(jié)點讓當(dāng)前結(jié)點的前驅(qū)結(jié)點的next指針指向新結(jié)點另一種定義方式

帶頭結(jié)點的單鏈表插入在帶頭結(jié)點的單鏈表中實現(xiàn)插入操作刪除在帶頭結(jié)點的單鏈表L中進行刪除示例將下列特性對應(yīng)到順序表和鏈表中，對號入座A．邏輯上相鄰的元素，在內(nèi)存中的存儲位置也相鄰B．不必事先估計存儲空間C．所需空間與元素個數(shù)成正比D．插入、刪除時不需要移動元素E．支持隨機存取F．支持順序存取順序表具有的特性有：A、E和F鏈表具有的特性有：B、C、D和F單鏈表基本操作的實現(xiàn)帶頭結(jié)點的單鏈表中，始終會有一個頭結(jié)點，這個結(jié)點在初始化時創(chuàng)建清空單鏈表判空單鏈表需要判空，通常不需要判滿求長度的兩種實現(xiàn)插入新元素刪除元素賦值、取值查找效率分析如果給定了當(dāng)前指針，則插入操作和刪除操作的時間復(fù)雜度均為O(1)判定鏈表是否為空的時間復(fù)雜度也為O(1)清空表操作的時間復(fù)雜度是O(n)求表長，兩種實現(xiàn)分別是O(1)和O(n)查找操作的時間復(fù)雜度是根據(jù)查找目標(biāo)在鏈表中的位置而定的最優(yōu)情況下為O(1)最壞的情況下為O(n)平均來看是O(n)查找失敗是O(n)循環(huán)鏈表修改單鏈表的定義，將表尾結(jié)點的指針指回頭結(jié)點，從而形成一類新鏈表這樣的鏈表中，從任何一個結(jié)點出發(fā)沿著指針域的指示可以再回到這個結(jié)點，好象轉(zhuǎn)了一個圈一樣，形象地稱這樣的鏈表為循環(huán)鏈表雙向鏈表雙向鏈表中，表結(jié)點及鏈表的定義typedefintELEMType;typedefstructnode{ //雙向鏈表結(jié)點 ELEMTypedata; structnode*next; //指向后繼結(jié)點 structnode*prev; //指向前驅(qū)結(jié)點}DouLinkNode;typedefDouLinkNode*DouLinkList; //雙向鏈表typedefintposition;雙向鏈表雙向鏈表的初始化插入新元素刪除元素雙向循環(huán)鏈表2.4兩種基本實現(xiàn)方式的比較線性表有兩種基本的實現(xiàn)方式，分別是順序?qū)崿F(xiàn)和鏈?zhǔn)綄崿F(xiàn)簡單地說，這兩種實現(xiàn)方式各有優(yōu)勢。在不同的情況下，對應(yīng)于不同的操作，某一種方式可能會優(yōu)于另外一種。但是哪種方式都不能適用于所有情況對比存儲每個數(shù)據(jù)元素時空間比較緊湊，并且是占用連續(xù)的空間數(shù)組的每個單元中只需要保存數(shù)據(jù)本身，沒有額外的開銷鏈表在每個結(jié)點上除存儲數(shù)據(jù)元素外，還要留出空間存放指針。單鏈表中每個結(jié)點包含一個指針，雙向鏈表中每個結(jié)點包含兩個指針。這些指針占用的空間稱為結(jié)構(gòu)性開銷為順序表分配的數(shù)組，通常要寬松一些。通常數(shù)組中會有空閑的空間，此時并沒能充分利用數(shù)組的全部空間鏈表中占用的空間大小與鏈表中的元素個數(shù)成正比，分配的結(jié)點是全部使用的當(dāng)線性表的元素個數(shù)相對較少時，鏈表的實現(xiàn)比順序表的實現(xiàn)更節(jié)省空間當(dāng)線性表中的元素個數(shù)接近分配的最大個數(shù)，數(shù)組的空間存儲效率很高設(shè)n表示線性表中當(dāng)前元素的個數(shù)，D表示最多可以在數(shù)組中存儲的元素個數(shù)，也就是數(shù)組的大小，P表示指針的存儲單元大小，E表示數(shù)據(jù)元素的存儲單元大小順序表的空間需求為D

E單鏈表的空間需求為n

(P+E)n的臨界值n=D

E/(P+E)雙向鏈表比單鏈表中每個結(jié)點的指針數(shù)多1個。所以雙向鏈表的結(jié)構(gòu)性開銷是單鏈表的2倍示例例2.7設(shè)保存線性表L的每個元素需要的空間為10個字節(jié)，指針占2個字節(jié)。若采用單鏈表或含30個元素的數(shù)組保存L。試分析采用哪種方式空間存儲效率更高，僅需要考慮L中元素根據(jù)題意，采用單鏈表保存L時，每個結(jié)點占用的空間為12個字節(jié)示例如果采用數(shù)組保存，則需要的空間是30

10=300個字節(jié)。使用這些空間保存單鏈表中的結(jié)點的話，可以保存300/12=25在不考慮表頭結(jié)點占用的空間的前提下，如果L中元素個數(shù)少于25個，則采用單鏈表更省空間如果多于25個元素，則采用數(shù)組更省空間如果正好是25個元素，則單鏈表和數(shù)組占用的空間是一樣大的如何選擇當(dāng)線性表元素個數(shù)變化較大或者未知時，最好使用鏈表實現(xiàn)如果用戶事先知道線性表的大致長度，則使用順序表的空間效率會更高些還要考慮到，順序表占用的空間是連續(xù)的，而鏈表占用的空間可能是零散的，并且還需要程序員來管理空間的分配及釋放操作的時間復(fù)雜度也要考慮在