數(shù)據(jù)結(jié)構(gòu)第二章 線性表-跟ppt完全對(duì)應(yīng)

1、【學(xué)習(xí)目標(biāo)】1. 了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線性表簡(jiǎn)稱為順序表，用后者表示的線性表簡(jiǎn)稱為鏈表。2. 熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。3. 能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。4. 結(jié)合線性表類型的定義增強(qiáng)對(duì)抽象數(shù)據(jù)類型的理解?！局攸c(diǎn)和難點(diǎn)】鏈表是本章的重點(diǎn)和難點(diǎn)。扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求，分清鏈表中指針 p 和結(jié)點(diǎn) *p 之間的對(duì)應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點(diǎn)、頭指針

2、和首元結(jié)點(diǎn)的不同所指以及循環(huán)鏈表、雙向鏈表的特點(diǎn)等?！局R(shí)點(diǎn)】線性表、順序表、鏈表、有序表【學(xué)習(xí)指南】正如課程概況中所提，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目標(biāo)是為了編出質(zhì)量更高的程序，因此重在"實(shí)踐"。本章討論的線性表是學(xué)習(xí)的第一種也是最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)，是整個(gè)課程的基礎(chǔ)，特別是熟練掌握鏈表的操作對(duì)以后各章的學(xué)習(xí)將有很大幫助。本章要求必須完成的算法設(shè)計(jì)題為：2.11，2.21，2.19，2.22，2.24，2.27，2.28，2.38。其中 2.11 和 2.19 可以在學(xué)完順序表之后練習(xí)，其余都建議在學(xué)完全章的內(nèi)容之后進(jìn)行?！菊n前思考】1. 抽象數(shù)據(jù)類型的定義由哪幾部分組成？2. 按數(shù)據(jù)

3、元素之間的邏輯關(guān)系不同，數(shù)據(jù)結(jié)構(gòu)有哪幾類？3. 你能舉出幾個(gè)你熟悉的"序列"的例子來(lái)嗎？課時(shí)安排：第一課時(shí)：線性結(jié)構(gòu)、線性表的邏輯結(jié)構(gòu)、線性表的抽象數(shù)據(jù)類型定義第二課時(shí)：線性表的順序存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)的表示：定義、元素地址計(jì)算方法、特點(diǎn)、實(shí)現(xiàn)基本操作：插入：定義和分析、算法、算法圖示、算法時(shí)間復(fù)雜度分析刪除：定義和分析、算法、算法圖示、算法時(shí)間復(fù)雜度分析第三四課時(shí)：順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表 定義、c語(yǔ)言實(shí)現(xiàn)、指針、頭結(jié)點(diǎn)、基本操作查找：定義、算法描述、算法評(píng)價(jià)插入：定義、算法描述、算法評(píng)價(jià)刪除：定義、算法描述、算法評(píng)價(jià)例子：動(dòng)態(tài)建立單鏈表：算法描述、算法評(píng)價(jià)

4、單鏈表的特點(diǎn)第五六課時(shí)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)循環(huán)鏈表雙向鏈表雙向循環(huán)鏈表從第二章開始，我們將開始討論第一章里面提到的四種數(shù)據(jù)結(jié)構(gòu)。這一章我們討論一種最簡(jiǎn)單的線性結(jié)構(gòu)線性表。l 線性結(jié)構(gòu)什么是線性結(jié)構(gòu)？線性結(jié)構(gòu)數(shù)據(jù)元素之間存在什么樣的關(guān)系，簡(jiǎn)單地說(shuō)，線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集合。這里的 "有序" 僅指在數(shù)據(jù)元素之間存在一個(gè) "領(lǐng)先" 或 "落后" 的次序關(guān)系，而非指數(shù)據(jù)元素 "值" 的大小可比性。它有四個(gè)基本特征：1集合中必存在唯一的一個(gè)"第一元素"；2集合中必存在唯一的一個(gè)"

5、;最后元素"；3除最后元素之外，其它數(shù)據(jù)元素均有唯一的"后繼"；4除第一元素之外，其它數(shù)據(jù)元素均有唯一的"前驅(qū)"。l 線性表的邏輯結(jié)構(gòu)線性表的類型定義線性表是一種最簡(jiǎn)單的線性結(jié)構(gòu)。通常可以下列" n 個(gè)數(shù)據(jù)元素的序列"表示線性表 (Linear_List)通?？梢赃@樣表示線性表中的數(shù)據(jù)元素可以是各種各樣的，只要是屬于同一個(gè)集合即可。例如，26個(gè)小寫英文字母是一個(gè)線性表(a,b,z)同一花色的13張撲克牌(2,3,4,5,6,7,8,9,10,J,Q,K,A)可以構(gòu)成一個(gè)線性表。例 英文字母表（A,B,C,.Z)是一個(gè)線性表學(xué)

6、號(hào)姓名年齡001張三18002李四19例 特征：1序列中數(shù)據(jù)元素的個(gè)數(shù) n 為線性表的一個(gè)屬性，定義為線性表的表長(zhǎng)；n=0 時(shí)的線性表被稱為空表。2.由于線性表是一個(gè)序列，所以每一個(gè)元素在線性表中都有一個(gè)固定的位置，稱為線性表中第i個(gè)元素，稱 i 為在線性表中的位序。3.1<i<n時(shí)ai的直接前驅(qū)是ai-1，a1無(wú)直接前驅(qū)ai的直接后繼是ai+1，an無(wú)直接后繼4.元素同構(gòu)，是屬于同一個(gè)對(duì)象的，也就是具有相同的特性，且不能出現(xiàn)缺項(xiàng)l 線性表的抽象數(shù)據(jù)類型定義其抽象數(shù)據(jù)類型的定義如下：（ppt上沒有，但書上有，可以講）ADT List 數(shù)據(jù)對(duì)象：Dai |ai ElemSet, i=

7、1,2,.,n, n0 線性表由n個(gè)元素構(gòu)成，其中n0。數(shù)據(jù)關(guān)系：R1 <ai-1 ,ai >| ,D, i=2,.,n 其中數(shù)據(jù)元素之間的關(guān)系表現(xiàn)為n個(gè)有序?qū)Α；静僮鳎?線性表的操作有多種類型，總的來(lái)說(shuō)可以歸納為四類。結(jié)構(gòu)初始化InitList( &L ) 操作結(jié)果：構(gòu)造一個(gè)空的線性表 L 。任何數(shù)據(jù)結(jié)構(gòu)在被使用之前都必須進(jìn)行"初始化" ，它類似于編程中使用的變量都必須先有定義。銷毀結(jié)構(gòu)DestroyList( &L ) 初始條件：線性表 L 已存在。操作結(jié)果：銷毀線性表 L 。任何數(shù)據(jù)結(jié)構(gòu)不再使用時(shí)都必須進(jìn)行"結(jié)構(gòu)銷毀"

8、 ，其實(shí)質(zhì)為"釋放"它所占有的存儲(chǔ)空間。引用型操作ListEmpty( L ) 判定線性表是否為空表。初始條件：線性表L已存在。操作結(jié)果：若 L 為空表，則返回 TRUE，否則返回 FALSE。ListLength( L ) 求得線性表的長(zhǎng)度，即線性表中所含數(shù)據(jù)元素的個(gè)數(shù)。初始條件：線性表 L 已存在。操作結(jié)果：返回 L 中元素個(gè)數(shù)。PriorElem( L, cur_e, &pre_e ) 求線性表中某個(gè)元素的前驅(qū)。若該元素cur_e是線性表 L 中第一個(gè)數(shù)據(jù)元素，則它的前驅(qū) pre_e 為"空元素"。初始條件：線性表 L 已存在。操作結(jié)果：若

9、 cur_e 是 L 中的數(shù)據(jù)元素，則用 pre_e 返回它的前驅(qū)，否則操作失敗，pre_e 無(wú)定義。NextElem( L, cur_e, &next_e ) 求線性表中某個(gè)元素的后繼。若該元素 cur_e 是線性表 L 中最后一個(gè)數(shù)據(jù)元素，則它的后繼 next_e 為"空元素"。初始條件：線性表 L 已存在。操作結(jié)果：若 cur_e 是 L 中的數(shù)據(jù)元素，則用 next_e 返回它的后繼，否則操作失敗，next_e 無(wú)定義。GetElem( L, i, &e ) 求線性表中第i個(gè)元素初始條件：線性表 L 已存在，1iLengthList(L)。操作結(jié)果：

10、用 e 返回 L 中第 i 個(gè)元素的值。此操作的結(jié)果是求得線性表 L 中和位序 i 相對(duì)應(yīng)的數(shù)據(jù)元素，因此，只有當(dāng) i 的值在線性表的長(zhǎng)度范圍內(nèi)才有意義。LocateElem( L, e, compare( ) )初始條件：線性表 L 已存在，compare( ) 是元素判定函數(shù)。操作結(jié)果：返回 L 中第1個(gè)與 e 滿足關(guān)系 compare( ) 的元素的位序。若這樣的元素不存在，則返回值為0。這是和上一個(gè)操作"相對(duì)"的操作，通常稱為"定位函數(shù)"，定位到滿足某個(gè)判定條件的元素，這是一種廣義的定位函數(shù)寫法，以 compare() 作為判定的條件，參數(shù) e

11、和線性表中數(shù)據(jù)元素具有相同類型。較多場(chǎng)合是以"相等"作為判定條件，此時(shí)可省略函數(shù)參數(shù)，且操作結(jié)果為：若線性表中存在多個(gè)滿足條件的數(shù)據(jù)元素，則返回第一個(gè)這樣的元素在表中的位序，若線性表中不存在滿足條件的數(shù)據(jù)元素，則返回函數(shù)值為0。ListTraverse(L, visit( ) 對(duì)線性表進(jìn)行遍歷初始條件：線性表 L 已存在，visit( ) 為元素的訪問函數(shù)。操作結(jié)果：依次對(duì) L 的每個(gè)元素調(diào)用函數(shù) visit( )。一旦 visit( ) 失敗，則操作失敗。visit() 亦為函數(shù)參數(shù)，常見的情況是"依次輸出表中元素的值"，同樣在這種情況下，通常的寫法也

12、是省略函數(shù)參數(shù)。這些操作有個(gè)共同特性，線性表不會(huì)發(fā)生任何改變，無(wú)論是數(shù)據(jù)元素還是元素之間的關(guān)系都沒有發(fā)生改變，所以把這些操作叫做引用型的操作加工型操作以下四個(gè)操作的結(jié)果或修改表中的數(shù)據(jù)元素，或修改元素之間的關(guān)系，被稱為"加工型"的操作，ClearList( &L )初始條件：線性表 L 已存在。操作結(jié)果：將 L 重置為空表。值得注意的是，在進(jìn)行了 DestroyList(L) 操作之后，線性表 L 不再存在，即不能在以后的程序中再引用它，而在對(duì)線性表L進(jìn)行 ClearList(L) 操作之后，僅是刪除表中所有元素，在以后的程序中仍可對(duì)它進(jìn)行某些"合法&qu

13、ot;操作，如判空、插入等PutElem( &L, i, &e )初始條件：線性表L已存在，1iLengthList(L)。操作結(jié)果：L 中第 i 個(gè)元素賦值同 e 的值和GetElem操作相同，i 的值必須在線性表的長(zhǎng)度范圍內(nèi)。ListInsert( &L, i, e )初始條件：線性表 L 已存在，1iLengthList(L)+1。操作結(jié)果：在 L 的第 i 個(gè)元素之前插入新的元素 e，L 的長(zhǎng)度增1?？稍诰€性表中任意一個(gè)元素之前插入一個(gè)新的數(shù)據(jù)元素，i=1 意為在第一個(gè)元素之前插入一個(gè)新的數(shù)據(jù)元素，i=LengthList(L)+1 則為在最后一個(gè)元素之后插入一

14、個(gè)新的數(shù)據(jù)元素。換句話說(shuō)，操作結(jié)果是使新插入的數(shù)據(jù)元素成為插入之后的線性表中第 i 個(gè)數(shù)據(jù)元素，顯然，插入位置 i 的合法值應(yīng)為1iLengthList(L)+1。ListDelete( &L, i, &e )初始條件：線性表 L 已存在且非空，1iLengthList(L)。操作結(jié)果：刪除 L 的第 i 個(gè)元素，并用 e 返回其值，L 的長(zhǎng)度減1。被刪除的元素必須是當(dāng)前線性表中存在的元素，因此被刪元素的位序應(yīng)滿足條件1iLengthList(L)。l 線性表的順序存儲(chǔ)結(jié)構(gòu)2.2線性表的順序存儲(chǔ)結(jié)構(gòu)-順序表若要在實(shí)際的程序設(shè)計(jì)中真正引用線性表的基本操作，首先必須實(shí)現(xiàn)線性表類型。

15、即在計(jì)算機(jī)中確定它的存儲(chǔ)結(jié)構(gòu)并在此存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)類型中定義的所有基本操作。本節(jié)將討論它的順序存儲(chǔ)結(jié)構(gòu)以及在順序存儲(chǔ)結(jié)構(gòu)中基本操作的實(shí)現(xiàn)。線性表順序存儲(chǔ)的表示何謂順序存儲(chǔ)表示？順序存儲(chǔ)是指以數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。n 定義：對(duì)線性表來(lái)說(shuō)，它指的是，"用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素"，并以表中第一個(gè)元素的存儲(chǔ)位置作為線性表的起始地址，稱作線性表的基地址。如下圖所示。n 元素地址計(jì)算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中：¡ L一個(gè)元素占用的存儲(chǔ)單元個(gè)數(shù)&

16、#161; LOC(ai)線性表第i個(gè)元素的地址n 特點(diǎn)： 實(shí)現(xiàn)邏輯上相鄰物理地址相鄰 實(shí)現(xiàn)隨機(jī)存取n 實(shí)現(xiàn)：在高級(jí)語(yǔ)言程序設(shè)計(jì)中，由于數(shù)組也是采用連續(xù)的地址單元來(lái)存放數(shù)據(jù)元素，所以可用一維數(shù)組實(shí)現(xiàn)順序表。具體圖示和c語(yǔ)言的編程實(shí)現(xiàn)見ppt。 順序表中基本操作的實(shí)現(xiàn)從順序表的存儲(chǔ)結(jié)構(gòu)定義容易看出，由于順序表的"長(zhǎng)度"是個(gè)"顯值"，且由于第i個(gè)元素恰好存儲(chǔ)在數(shù)組的第 i 個(gè)分量(數(shù)組下標(biāo)為 i-1)中，因此其"求長(zhǎng)"、"判空"以及"存取第 i 個(gè)數(shù)據(jù)元素"等操作都很容易實(shí)現(xiàn)。下面重點(diǎn)討論順序表類型

17、定義中五個(gè)操作的實(shí)現(xiàn)：初始化操作、元素定位操作、插入元素操作、刪除元素操作、銷毀結(jié)構(gòu)操作。插入元素操作（ppt上面有，需要詳細(xì)講的）首(a1,a2, ,ai-1,ai, , ,an)改變?yōu)?（a1，a2, , ,ai-1,x,ai, , ,an）先分析，"插入元素"使線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？假設(shè)在線性表的第i個(gè)元素之前插入一個(gè)元素e，使得線性表即：(1) 改變了表中元素之間的關(guān)系，使< ai-1,ai > 改變?yōu)?lt;x,ai >和< x,ai >(2) 表長(zhǎng)增1由于順序表是以"存儲(chǔ)位置相鄰" 表示"元素之

18、間的前驅(qū)和后繼關(guān)系"，則必須"移動(dòng)元素"來(lái)體現(xiàn)"元素之間發(fā)生的變化"。需將第i至第n共（n-i+1)個(gè)元素后移.見ppt算法ch2_1.txt算法時(shí)間復(fù)雜度的分析：算法中的基本操作是"移動(dòng)元素"，for 循環(huán)的執(zhí)行次數(shù)在最壞的情況下pos=1（即插入在第一個(gè)元素之前時(shí))為 移動(dòng)元素的次數(shù)為n。最好的情況是pos=n+1(即插入到線性表的最末端)，無(wú)需移動(dòng)元素。兩者的概率一樣，平均次數(shù)為n/2，可見n越大，效率越低。刪除元素操作（ppt上面有，需要詳細(xì)講的）首(a1,a2, ,ai-1,ai, , ,an)改變?yōu)?（a1，a2

19、, , ,ai-1,ai+1, , ,an）同樣首先分析，"刪除元素"使線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？假設(shè)刪除線性表中第i個(gè)元素，使得線性表即：1) 改變了表中元素之間的關(guān)系(2) 表長(zhǎng)減1對(duì)順序表而言，需要改變從第 i+1 個(gè)元素起到第 n 個(gè)元素的存儲(chǔ)位置，即進(jìn)行"從第 i+1 到第 n 個(gè)元素往前移動(dòng)一個(gè)位置"。見ppt算法ch2_2.txt此算法的時(shí)間復(fù)雜度為：O (ListLength(L)算法時(shí)間復(fù)雜度的分析：算法中的基本操作是"移動(dòng)元素"，for循環(huán)的執(zhí)行次數(shù)在最壞的情況下(pos=1即刪除第一個(gè)元素時(shí))移動(dòng)n-1次，最

20、好的情況(pos=n)下移動(dòng)0次，概率一樣，平均移動(dòng)次數(shù)為(n-1)/2?？梢妌越大，效率越低。第5個(gè)學(xué)時(shí)：n 回顧 前面所學(xué)習(xí)的內(nèi)容；n 然后從數(shù)據(jù)結(jié)構(gòu)的角度去分析，做幾個(gè)練習(xí)。同時(shí)加上演示效果。n 完成一個(gè)對(duì)整體線性表的演示。第6個(gè)學(xué)時(shí)：l 順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)l 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)前面已經(jīng)提到，由于在順序表中插入或刪除一個(gè)數(shù)據(jù)元素，平均約需移動(dòng)表中一半元素。因此，對(duì)于需要經(jīng)常進(jìn)行插入和刪除操作、表中元素相對(duì)不穩(wěn)定的線性表，不應(yīng)該采用順序存儲(chǔ)表示，而應(yīng)該采用鏈?zhǔn)酱鎯?chǔ)表示。何謂"鏈?zhǔn)酱鎯?chǔ)表示"？線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的表示：鏈?zhǔn)酱鎯?chǔ)表示指的是以"附加信息(指針)

21、" 表示數(shù)據(jù)元素之間的邏輯關(guān)系。特點(diǎn)：n 用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素(這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）)n 每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息。n 利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素。為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來(lái)說(shuō)，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置）。因?yàn)榫€性表的最后一個(gè)數(shù)據(jù)元素沒有后繼，因此最后一個(gè)結(jié)點(diǎn)中的"指針"是一個(gè)特殊的值 "NULL" （在圖上用表示），通常稱它為

22、"空指針"。n 結(jié)點(diǎn)數(shù)據(jù)域：元素本身信息（設(shè)域名為data）指針域：指示直接后繼的存儲(chǔ)位置（設(shè)域名為next）。稱做指針或鏈。數(shù)據(jù)域 data指針域 next圖示：見pptl 單鏈表（線性鏈表）由分別表示a1，a2，。an的N 個(gè)結(jié)點(diǎn)依次相鏈構(gòu)成的鏈表，稱為線性表的鏈?zhǔn)酱鎯?chǔ)表示，由于此類鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，故又稱單鏈表或線性鏈表，如下圖所示：為了便于處理一些特殊情況，在第一個(gè)結(jié)點(diǎn)之前附加一個(gè)"頭結(jié)點(diǎn)"，令該結(jié)點(diǎn)中指針域的指針指向第一個(gè)元素結(jié)點(diǎn)，并令頭指針指向頭結(jié)點(diǎn)，該頭節(jié)點(diǎn)中的數(shù)據(jù)域沒有意義，如下圖所示。通常稱這類單鏈表為"帶頭結(jié)

23、點(diǎn)的單鏈表"。值得注意的是，若線性表為空，在不帶頭結(jié)點(diǎn)的情況下，頭指針為空(NULL)，但在帶頭結(jié)點(diǎn)的情況下，鏈表的頭指針不為空，而是其頭結(jié)點(diǎn)中指針域的指針為空，如下圖所示。單鏈表（線性鏈表）的實(shí)現(xiàn)：在高級(jí)程序設(shè)計(jì)中是怎樣描述或表示線性鏈表的。在c語(yǔ)言中就是用結(jié)構(gòu)指針來(lái)描述鏈表結(jié)構(gòu)的。typedef struct node datatype data; struct node *link;JD;JD *h,*p;datalinkkp結(jié)點(diǎn)（*p）(*p)表示p所指向的結(jié)點(diǎn)。若 p 的值非空，則表明 p 指向某個(gè)結(jié)點(diǎn)(*p).dataÛp->data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域

24、(*p).linkÛp->link表示p指向結(jié)點(diǎn)的指針域。若非空，則表明其有"后繼"結(jié)點(diǎn)。指針型變量只能作同類型的指針賦值與比較操作。并且，指針型變量的"值"除了由同類型的指針變量賦值得到外，都必須用 C 語(yǔ)言中的動(dòng)態(tài)分配函數(shù)得到。例如，p = new LNode; 表示在運(yùn)行時(shí)刻系統(tǒng)動(dòng)態(tài)生成了一個(gè) LNode 類型的結(jié)點(diǎn)，并令指針 p "指向"該結(jié)點(diǎn)。反之，當(dāng)指針 p 所指結(jié)點(diǎn)不再使用，可用 delete p; 釋放此結(jié)點(diǎn)空間。注意：一旦執(zhí)行了delete p; 的語(yǔ)句，(*p)不再存在，自然 p->data

25、和 p->link 也就沒有意義了。第7、8個(gè)學(xué)時(shí)：?jiǎn)捂湵恚ň€性鏈表）的基本運(yùn)算：查找：查找單鏈表中是否存在結(jié)點(diǎn)X，若有則返回指向X結(jié)點(diǎn)的指針；否則返回NULL算法描述：見ch2_3.txt算法評(píng)價(jià)：While循環(huán)中語(yǔ)句頻度為：若找到結(jié)點(diǎn)X，為結(jié)點(diǎn)X在表中的序號(hào)否則，為nT(n)=O(n)插入：插入效果示例見ppt算法見pptch2_4.txt算法時(shí)間復(fù)雜度的分析：在插入算法中，修改指針的時(shí)間復(fù)雜度僅為O(1)刪除:見ppt例：動(dòng)態(tài)建立單鏈表算法：見ppt由于鏈表是一種動(dòng)態(tài)存儲(chǔ)管理的結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)占用的存儲(chǔ)空間不需預(yù)先分配劃定，而是在運(yùn)行時(shí)刻由系統(tǒng)應(yīng)需求即時(shí)生成，因此，建立鏈表的過(guò)

26、程是一個(gè)動(dòng)態(tài)生成的過(guò)程。即從 "空表"起，依次建立結(jié)點(diǎn)，并逐個(gè)插入鏈表。l 單鏈表的特點(diǎn)n 它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用n 不需預(yù)先分配空間n 指針占用額外存儲(chǔ)空間n 不能隨機(jī)存取，查找速度慢第9、10個(gè)學(xué)時(shí)：l 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)從對(duì)鏈表的各種操作的討論可知，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)勢(shì)在于：優(yōu)勢(shì)：(1) 能有效利用存儲(chǔ)空間；因?yàn)樗莿?dòng)態(tài)存儲(chǔ)分配的結(jié)構(gòu)，不需要預(yù)先為線性表分配足夠大的空間，而是向系統(tǒng)"隨用隨取"，并且在刪除元素時(shí)可同時(shí)釋放空間。(2) 用"指針"指示數(shù)據(jù)元素之間的后繼關(guān)系，便于進(jìn)行"插入"

27、、"刪除"等操作；插入或刪除時(shí)只需要修改指針，而不需要進(jìn)行大量元素的移動(dòng)。劣勢(shì)：而其劣勢(shì)則是不能隨機(jī)存取數(shù)據(jù)元素。同時(shí)，它還丟失了一些順序表有的長(zhǎng)處，如線性表的"表長(zhǎng)"和數(shù)據(jù)元素在線性表中的"位序"，在上述的單鏈表中都看不見了。又如，不便于在表尾插入元素，需遍歷整個(gè)表才能找到插入的位置。當(dāng)插入位置在表尾時(shí)不需要移動(dòng)元素，所需時(shí)間是個(gè)常量，由于鏈表進(jìn)行插入操作只需要修改指針本是個(gè)優(yōu)點(diǎn)，然而為了查找插入位置卻要遍歷整個(gè)表，所需時(shí)間反而多。為了更突出鏈表的優(yōu)勢(shì)，需改進(jìn)單鏈表結(jié)構(gòu)的定義。除了保留指向頭結(jié)點(diǎn)的指針外，還應(yīng)增設(shè)"尾指針"和"表長(zhǎng)"兩個(gè)屬性，同時(shí)，我們從上面討論的鏈表基本操作的實(shí)現(xiàn)算法