數(shù)據(jù)結(jié)構(gòu)與算法 課件 第二章線性表

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

計(jì)算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第二章線性表學(xué)習(xí)目標(biāo)理解線性表的相關(guān)概念，了解其邏輯定義及基本操作，理解線性表數(shù)據(jù)元素之間的邏輯關(guān)系掌握線性表的順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式，了解各自的特點(diǎn)掌握順序表及鏈表基本操作的實(shí)現(xiàn)，并能進(jìn)行復(fù)雜度分析掌握靜態(tài)鏈表基本操作的實(shí)現(xiàn)，并能進(jìn)行復(fù)雜度分析能夠設(shè)計(jì)與線性表相關(guān)的數(shù)據(jù)結(jié)構(gòu)，靈活運(yùn)用線性表的基本操作，設(shè)計(jì)算法解決與線性表相關(guān)的實(shí)際問題本章主要內(nèi)容線性表的定義和基本操作12線性表的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)3線性表的順序存儲(chǔ)及實(shí)現(xiàn)進(jìn)一步討論兩種基本實(shí)現(xiàn)方式4單鏈表的應(yīng)用5第一節(jié)

線性表的定義和基本操作線性表是一種線性結(jié)構(gòu)。在這種結(jié)構(gòu)中，存在著唯一的“第一個(gè)”元素、唯一的“第二個(gè)”元素，依此類推線性表中各個(gè)元素依次排列例1-1中給出的某班30名同學(xué)的基本信息（表1-1），就可以組成一個(gè)線性表，可以按照學(xué)號(hào)排列名單

定義定義2-1一個(gè)線性表（linearlist）是由同類型數(shù)據(jù)元素構(gòu)成的有限序列由n(n≥0)個(gè)元素組成的線性表L，可以表示為L=(a0,a1,…,an-1)這里，ai(0≤i≤n-1)即是線性表中的數(shù)據(jù)元素，也稱為表項(xiàng)線性表中所有數(shù)據(jù)元素都必須是相同類型的數(shù)據(jù)元素的次序就是它們?cè)诒碇械呐帕写涡虻谝粋€(gè)元素是a0，稱為表頭或開始元素第n個(gè)也即最后一個(gè)元素是an-1，稱為表尾或終端元素元素的個(gè)數(shù)n稱為表長n=0時(shí)稱為空表，記為()

示例

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

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

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

(M2022103030楊志強(qiáng)男2004.10.30陜西))

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

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

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

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

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

LinearList中定義的函數(shù)都有返回值LinearList中定義的操作都有返回值，有些返回值代表操作的執(zhí)行結(jié)果，另外一些僅表示操作是否已正確執(zhí)行。例如length返回的是線性表的當(dāng)前長度，即線性表所含元素的個(gè)數(shù)find返回的是要查找的元素x在表中第一次出現(xiàn)的位置。如果表中不包含x，則返回-1當(dāng)表為空時(shí)，isEmpty返回1，否則返回0。當(dāng)表已滿時(shí)，isFull返回1，否則返回0操作的幾個(gè)示例序號(hào)操作操作結(jié)果解釋1initList(&s)()創(chuàng)建空線性表s2for(i=0;i<6;i++)insertList(&s,i,2*i)(0,2,4,6,8,10)在空表s的表尾處依次插入6個(gè)值3removeList(&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，查找失敗第二節(jié)

線性表的順序存儲(chǔ)及實(shí)現(xiàn)操作的具體實(shí)現(xiàn)需要依賴于線性表的存儲(chǔ)結(jié)構(gòu)?？梢允褂庙樞虼鎯?chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式保存線性表，從而得到線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)使用數(shù)組保存線性表中的各元素，相應(yīng)的線性表稱為順序表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)使用鏈表保存線性表中的各元素，相應(yīng)的線性表稱為鏈表順序表順序存儲(chǔ)的基本思想是使用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)各個(gè)元素，將線性表中的各數(shù)據(jù)元素，按照其邏輯次序，依次保存在數(shù)組的各個(gè)單元中線性表中邏輯上相鄰的兩個(gè)元素，保存在數(shù)組相鄰的兩個(gè)單元中

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

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

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

dLOC(a0)即是數(shù)組的首地址例2-4

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

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

11523196

…

1152723196

…

11527196

…

程序中使用的常量#defineTRUE1#defineFALSE0#defineERROR-1#ifndefmaxSize#definemaxSize100#endif順序表基本運(yùn)算的實(shí)現(xiàn)順序表的定義構(gòu)造空表及清空表判表空、判表滿、求表長插入新元素插入操作中移動(dòng)元素的平均次數(shù)為n/2刪除操作刪除操作中移動(dòng)元素的平均次數(shù)為(n-1)/2賦值、取值操作查找測(cè)試?yán)?-5設(shè)有順序表L，表長為n，保存在數(shù)組A中。實(shí)現(xiàn)算法將L逆置，即 L=(a0,a1,…,an-2,an-1)變?yōu)?L=(an-1,an-2,…,a1,a0)將A[0]與A[n-1]進(jìn)行交換，然后將A[1]與A[n-2]進(jìn)行交換，依此類推，當(dāng)交換到L中間元素時(shí)，算法結(jié)束算法實(shí)現(xiàn)第三節(jié)

線性表的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)線性表還可以使用鏈?zhǔn)酱鎯?chǔ)方式保存，即線性表中的各個(gè)元素保存在各自的存儲(chǔ)空間中，形成一個(gè)個(gè)的結(jié)點(diǎn)這些結(jié)點(diǎn)在內(nèi)存中的地址不要求是相鄰的，它們之間通過指針連接起來以這種方式保存的線性表稱為鏈表每個(gè)結(jié)點(diǎn)中包含元素值和指向其他結(jié)點(diǎn)的指針，指針的個(gè)數(shù)可以是一個(gè)，也可能是兩個(gè)，從而形成不同形式的鏈表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種動(dòng)態(tài)靈活的存儲(chǔ)方式，它不要求預(yù)先分配一塊連續(xù)的存儲(chǔ)空間，而是按需分配，隨時(shí)需要隨時(shí)分配同時(shí)不要求分配的空間必須是相鄰的，而是由系統(tǒng)決定分配的具體位置，既可以相鄰也可以不相鄰所以在執(zhí)行插入及刪除操作時(shí)，不再需要移動(dòng)元素以保證存儲(chǔ)空間的相鄰性單鏈表單鏈表是由一組動(dòng)態(tài)分配的結(jié)點(diǎn)形成的鏈表，每個(gè)結(jié)點(diǎn)保存線性表中的一個(gè)元素及一個(gè)指針，指針指向保存其后繼元素的結(jié)點(diǎn)保存L的單鏈表示意圖結(jié)點(diǎn)定義單鏈表中結(jié)點(diǎn)及鏈表的定義示例要在上圖所示的單鏈表L的位置2處插入元素E。當(dāng)前指針為p，指向位置2操作步驟是創(chuàng)建一個(gè)新結(jié)點(diǎn)，新結(jié)點(diǎn)中保存值E讓新結(jié)點(diǎn)的next指針指向指針p指向的結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)是當(dāng)前結(jié)點(diǎn)讓當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)另一種定義方式

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

E單鏈表的空間需求為n

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

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

10=300個(gè)字節(jié)。使用這些空間保存單鏈表中的結(jié)點(diǎn)的話，可以保存300/12=25在不考慮表頭結(jié)點(diǎn)占用的空間的前提下，如果L中元素個(gè)數(shù)少于25個(gè)，則采用單鏈表更省空間如果多于25個(gè)元素，則采用數(shù)組更省空間如果正好是25個(gè)元素，則單鏈表和數(shù)組占用的空間是一樣大的如何選擇當(dāng)線性表元素個(gè)數(shù)變化較大或者未知時(shí)，最好使用鏈表實(shí)現(xiàn)如果用戶事先知道線性表的大致長度，則使用順序表的空間效率會(huì)更高些還要考慮到，順序表占用的空間是連續(xù)的，而鏈表占用的空間可能是零散的，并且還需要程序員來管理空間的分配及釋放操作的時(shí)間復(fù)雜度也要考慮在順序表中是直接定位的，可以實(shí)現(xiàn)隨機(jī)訪問，操作的時(shí)間復(fù)雜度是O(1)單鏈表不能隨機(jī)訪問指定的元素，平均時(shí)間復(fù)雜度和最差時(shí)間復(fù)雜度均為O(n)在給出指向鏈表的當(dāng)前指針后，在單鏈表內(nèi)進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度也可以達(dá)到O(1)順序表的插入和刪除操作，平均和最差時(shí)間復(fù)雜度均為O(n)空閑單元鏈表鏈表中，當(dāng)需要在鏈表中插入一個(gè)結(jié)點(diǎn)時(shí)，需要調(diào)用malloc函數(shù)分配相應(yīng)的空間當(dāng)在鏈表中刪除一個(gè)結(jié)點(diǎn)時(shí)，需要調(diào)用delete函數(shù)釋放空間。如果在鏈表中頻繁進(jìn)行插入、刪除結(jié)點(diǎn)的操作，則頻繁調(diào)用這些函數(shù)的時(shí)間開銷會(huì)是非?？捎^的可以針對(duì)實(shí)際應(yīng)用的每類鏈表，定義一個(gè)“伙伴鏈表”，表結(jié)點(diǎn)的結(jié)構(gòu)與所使用的鏈表結(jié)構(gòu)一致伙伴鏈表用來管理暫時(shí)不用的結(jié)點(diǎn)，可以將伙伴鏈表稱為空閑單元鏈表假設(shè)，保存數(shù)據(jù)的單鏈表為L當(dāng)從鏈表L中刪除一個(gè)結(jié)點(diǎn)時(shí)，將這個(gè)結(jié)點(diǎn)插入到freelist中當(dāng)需要申請(qǐng)新的結(jié)點(diǎn)空間時(shí)，先查看鏈表freelist。如果freelist不空，則從freelist中獲取一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)中保存相應(yīng)的值，并將該結(jié)點(diǎn)插入到L的相應(yīng)位置，否則調(diào)用malloc函數(shù)分配新的空間，并完成后續(xù)的插入操作插入操作的實(shí)現(xiàn)刪除操作的實(shí)現(xiàn)清空表的操作靜態(tài)鏈表靜態(tài)鏈表的特點(diǎn)保存在數(shù)組中兼具順序表和鏈表特性，空間不零碎，插入刪除不需要移動(dòng)元素鏈表及靜態(tài)鏈表在前一個(gè)靜態(tài)鏈表中插入元素E后的靜態(tài)鏈表刪除元素D后的靜態(tài)鏈表類型定義初始化靜態(tài)鏈表清