數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表課件

1、數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表1每課一貼： 有一位表演大師上場前，他的弟子告訴他鞋帶松了。大師點(diǎn)頭致謝，蹲下來仔細(xì)系好。等到弟子轉(zhuǎn)身后，又蹲下來將鞋帶解松。有個(gè)旁觀者看到了這一切，不解地問：“大師，您為什么又要將鞋帶解松呢？”大師回答道：“因?yàn)槲绎椦莸氖且晃粍诶鄣穆谜?，長景涉讓他的鞋事松開，可以通過這個(gè)細(xì)節(jié)表現(xiàn)他的勞累憔悴.”“那你為什么不直接告訴你的弟子呢？”“他能細(xì)心地發(fā)現(xiàn)我的鞋帶松了，并且熱心地告訴我，我一定要保護(hù)他這種熱情的積極性，及時(shí)地給他鼓勵(lì)，至于為什么要將鞋帶解開，將來會(huì)有更多的機(jī)會(huì)教他表演，可以下一次再說啊?！比艘粋€(gè)時(shí)間只能做一件事，懂抓重點(diǎn)，才是真正的人才.數(shù)據(jù)結(jié)構(gòu)四次課-第2

2、章線性表2上堂課要點(diǎn)回顧上堂課要點(diǎn)回顧線性結(jié)構(gòu)線性結(jié)構(gòu)( (包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)：包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)： 僅一個(gè)首、尾結(jié)點(diǎn)，其余元素僅一個(gè)直接前驅(qū)和一僅一個(gè)首、尾結(jié)點(diǎn)，其余元素僅一個(gè)直接前驅(qū)和一個(gè)直接后繼。個(gè)直接后繼。2. 2. 線性表線性表邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)：“一對(duì)一一對(duì)一” ” 或或 1:11:1存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)剑喉樞颉㈡準(zhǔn)竭\(yùn)運(yùn) 算算：修改、插入、刪除：修改、插入、刪除3.3.順序存儲(chǔ)順序存儲(chǔ)特征：特征：邏輯上相鄰，物理上也相鄰；邏輯上相鄰，物理上也相鄰；優(yōu)點(diǎn)：優(yōu)點(diǎn)：隨機(jī)查找快隨機(jī)查找快 O(1)O(1)缺點(diǎn)：缺點(diǎn)：插入、刪除慢插入、刪除慢 O(n)O

3、(n)數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表32.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1 鏈表的表示鏈表的表示2.3.2 鏈表的實(shí)現(xiàn)鏈表的實(shí)現(xiàn)2.3.3 鏈表的運(yùn)算效率分析鏈表的運(yùn)算效率分析鏈表小結(jié)鏈表小結(jié)數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表42.3.1 鏈表的表示鏈表的表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：其結(jié)點(diǎn)在存儲(chǔ)器中的其結(jié)點(diǎn)在存儲(chǔ)器中的位置是位置是隨意隨意的，的，即邏輯上相鄰的數(shù)據(jù)元素邏輯上相鄰的數(shù)據(jù)元素在物理上在物理上不一定不一定相鄰相鄰。如何實(shí)現(xiàn)？通過來實(shí)現(xiàn)注意：注意：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分： 數(shù)據(jù)域數(shù)據(jù)域和和指針域指針域數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表

4、5與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語：與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語：1、結(jié)點(diǎn)：、結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2、鏈表：、鏈表： n 個(gè)結(jié)點(diǎn)由個(gè)結(jié)點(diǎn)由指針鏈指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)浇M成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像存儲(chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3、單鏈表、雙鏈表、多鏈表、循環(huán)鏈表、單鏈表、雙鏈表、多鏈表、循環(huán)鏈表： 結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表單鏈表或或線性鏈表線性鏈表；有兩個(gè)指針域的鏈表，稱為有兩個(gè)指針域的鏈表，稱為雙鏈表雙鏈表；有多個(gè)指針域的鏈表，稱為有多個(gè)

5、指針域的鏈表，稱為多鏈表多鏈表；首尾相接的鏈表稱為首尾相接的鏈表稱為循環(huán)鏈表循環(huán)鏈表。a1heada2anhead循環(huán)鏈表示意圖：循環(huán)鏈表示意圖：數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表64、頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)、頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn) 示意圖如下：示意圖如下：頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn)首元結(jié)點(diǎn)首元結(jié)點(diǎn)a1heada2infoan頭指針頭指針是指向鏈表中是指向鏈表中第一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針；的指針；頭結(jié)點(diǎn)頭結(jié)點(diǎn)是在鏈表的是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息只放空表標(biāo)志和表長等信息

6、; ;首元結(jié)點(diǎn)首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素a a1 1的結(jié)點(diǎn)。的結(jié)點(diǎn)。 數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表7一個(gè)線性表的邏輯結(jié)構(gòu)為：一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問其請(qǐng)問其頭指針頭指針的的值值是多少？是多少？存儲(chǔ)地址存儲(chǔ)地址數(shù)據(jù)域數(shù)據(jù)域指針域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZH

7、OU25例例：答：答：頭指針頭指針是指向是指向鏈表中第一個(gè)結(jié)點(diǎn)鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵的指針，因此關(guān)鍵是要尋找是要尋找第一個(gè)結(jié)第一個(gè)結(jié)點(diǎn)的地址點(diǎn)的地址。7ZHAOH31頭指針的值是頭指針的值是31數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表8上例鏈表的邏輯結(jié)構(gòu)示意圖有以下上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式兩種形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH區(qū)別：區(qū)別： 無頭結(jié)點(diǎn)無頭結(jié)點(diǎn) 有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表9答：答：討論1. 在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？討論2. 如何表示空表空表？頭結(jié)點(diǎn)頭結(jié)點(diǎn)即

8、在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)進(jìn)行操作時(shí)，可以對(duì)空表、非空表空表、非空表的情況以及對(duì)的情況以及對(duì)首元結(jié)點(diǎn)首元結(jié)點(diǎn)進(jìn)行進(jìn)行統(tǒng)一處理，編程更方便。統(tǒng)一處理，編程更方便。答：答：無頭結(jié)點(diǎn)時(shí)，無頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空當(dāng)頭指針的值為空時(shí)表示空表；時(shí)表示空表；有頭結(jié)點(diǎn)時(shí)，有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭债?dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。時(shí)表示空表。頭指針頭指針頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn)無頭結(jié)點(diǎn)無頭結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)四次課

9、-第2章線性表10討論2. 頭結(jié)點(diǎn)的數(shù)據(jù)域內(nèi)裝的是什么？ 頭結(jié)點(diǎn)的頭結(jié)點(diǎn)的數(shù)據(jù)域數(shù)據(jù)域可以為空，也可存放線性表可以為空，也可存放線性表長度長度等附加信息，但此結(jié)點(diǎn)不能計(jì)入鏈表長度值。等附加信息，但此結(jié)點(diǎn)不能計(jì)入鏈表長度值。答：答：討論3. 鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡單數(shù)據(jù)類型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，所以要采用因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，所以要采用結(jié)構(gòu)結(jié)構(gòu)數(shù)數(shù)據(jù)類型。據(jù)類型。答：答：什么是結(jié)構(gòu)類型？如何書寫表達(dá)？什么是結(jié)構(gòu)類型？如何書寫表達(dá)？ 頭結(jié)點(diǎn)的數(shù)據(jù)域頭結(jié)點(diǎn)的數(shù)據(jù)域H數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表11 實(shí)現(xiàn)實(shí)現(xiàn)結(jié)點(diǎn)接口結(jié)點(diǎn)接口Public interface Nod

10、epublic Object getData( );/獲取結(jié)點(diǎn)數(shù)據(jù)域獲取結(jié)點(diǎn)數(shù)據(jù)域Public void setData(Object object);/設(shè)置結(jié)點(diǎn)數(shù)據(jù)域設(shè)置結(jié)點(diǎn)數(shù)據(jù)域3. 線性鏈表的實(shí)現(xiàn)線性鏈表的實(shí)現(xiàn) 定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫，也叫，也叫單鏈表單鏈表Public class SLNode implements Node private Object element; private SLNode next; public SLNode this(null,null); public SLNode(Object ele, SLnode

11、next) this.element=ele; this.next=next; public SLNode getNext( ) return next; public void setNext(SLNode next) this.next =next; public Object getData( ) return element; public void setData(Object obj) element=obj; 數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表12 用一組用一組任意任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素 利用利用指針指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上實(shí)現(xiàn)了

12、用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素相鄰的元素 每個(gè)數(shù)據(jù)元素每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)，除存儲(chǔ)本身信息本身信息外，還需存儲(chǔ)其外，還需存儲(chǔ)其直接后繼直接后繼的地址的地址 結(jié)點(diǎn)結(jié)點(diǎn) 數(shù)據(jù)域：元素本身信息數(shù)據(jù)域：元素本身信息 指針域：指示直接后繼的存儲(chǔ)位置指針域：指示直接后繼的存儲(chǔ)位置數(shù)據(jù)域數(shù)據(jù)域 指針域指針域結(jié)點(diǎn)結(jié)點(diǎn)簡單總結(jié)：線性表的鏈?zhǔn)奖硎镜幕咎卣鳎汉唵慰偨Y(jié)：線性表的鏈?zhǔn)奖硎镜幕咎卣鳎簲?shù)據(jù)結(jié)構(gòu)四次課-第2章線性表134. 單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算While循環(huán)中語句頻度為循環(huán)中語句頻度為若找到結(jié)點(diǎn)若找到結(jié)點(diǎn)X，為結(jié)點(diǎn)，為結(jié)點(diǎn)X在表中的序號(hào)在表中的序號(hào)否則，為否則，為n nOnT 算法

13、評(píng)價(jià)算法評(píng)價(jià)v 查找：查找單鏈表中是否存在結(jié)點(diǎn)查找：查找單鏈表中是否存在結(jié)點(diǎn)X查找、插入、刪除、查找、插入、刪除、創(chuàng)建、原地逆序創(chuàng)建、原地逆序 算法描述算法描述類似算法：清空、求長度等，類似算法：清空、求長度等，舉一反三舉一反三p=head; /p是頭結(jié)點(diǎn)的引用是頭結(jié)點(diǎn)的引用while(p.getNext( )!=null)if(x=p.getData( ) return true;else p= p.getNext( );return false;數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表14pabxs 插入插入: 在線性表在線性表兩個(gè)數(shù)據(jù)元素兩個(gè)數(shù)據(jù)元素a和和b間間插入插入x，已知已知p指向指向a 1O

14、nT 算法描述算法描述 算法評(píng)價(jià)算法評(píng)價(jià)注意注意前插入和前插入和后插入后插入的區(qū)別的區(qū)別s.setNext(p.getNext( );p.setNext(s);數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表15算法描述算法描述pabc 1OnT算法評(píng)價(jià)算法評(píng)價(jià)刪除刪除：單鏈表中刪除：單鏈表中刪除b，設(shè)，設(shè)p指向指向ap.setNext(p.getNext( ).getNext( );數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表16 nOnT 動(dòng)態(tài)建立單鏈表算法動(dòng)態(tài)建立單鏈表算法：設(shè)線性表：設(shè)線性表n個(gè)元素已存?zhèn)€元素已存放在數(shù)組放在數(shù)組a中，建立一個(gè)單鏈表，中，建立一個(gè)單鏈表，h為頭指針為頭指針h頭結(jié)點(diǎn)頭結(jié)點(diǎn)an 0h頭結(jié)點(diǎn)頭結(jié)

15、點(diǎn)an-10an a2.h頭結(jié)點(diǎn)頭結(jié)點(diǎn)an-10an ha1a2頭結(jié)點(diǎn)頭結(jié)點(diǎn)an .0h頭結(jié)點(diǎn)頭結(jié)點(diǎn)0h.setData(0); h.setNext(NULL); /依次在鏈表頭部插入結(jié)點(diǎn)，次序是先插入最后一個(gè)，然依次在鏈表頭部插入結(jié)點(diǎn)，次序是先插入最后一個(gè)，然后再插入前面元素后再插入前面元素for(i=n;i0;i-) /注意注意i的變化的變化 s=new SLNode( ); s.setData(ai-1); s.setNext(h.getNext( ); h.setNext(s);算法描述算法描述算法評(píng)價(jià)算法評(píng)價(jià)數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表17單鏈表單鏈表原地逆序原地逆序算法算法：設(shè)線性

16、表：設(shè)線性表n個(gè)元素已存放個(gè)元素已存放在鏈表在鏈表a中，要求在不改變其元素位置的條件下中，要求在不改變其元素位置的條件下將鏈表逆序排列，將鏈表逆序排列，h為頭為頭指針指針ha1a2頭結(jié)點(diǎn)頭結(jié)點(diǎn)an .0hanan-1頭結(jié)點(diǎn)頭結(jié)點(diǎn)a1 .0數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表18 nOnT單鏈表單鏈表原地逆序原地逆序算法算法：設(shè)線性表：設(shè)線性表n個(gè)元素已存放個(gè)元素已存放在鏈表在鏈表a中，要求在不改變其元素位置的條件下中，要求在不改變其元素位置的條件下將鏈表逆序排列，將鏈表逆序排列，h為頭為頭指針指針 算法描述算法描述 算法評(píng)價(jià)算法評(píng)價(jià)prv=NULL; /prv指示新鏈表的首元結(jié)點(diǎn)指示新鏈表的首元結(jié)點(diǎn)/

17、pt是變化的未逆序部分鏈表的第一個(gè)結(jié)點(diǎn)是變化的未逆序部分鏈表的第一個(gè)結(jié)點(diǎn)pt=h.getNext( );while(pt!=NULL) tmp=pt.getNext( ); /取下一個(gè)結(jié)點(diǎn)取下一個(gè)結(jié)點(diǎn) pt.setNext(prv); /當(dāng)前結(jié)點(diǎn)指針指向自己前當(dāng)前結(jié)點(diǎn)指針指向自己前一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn) prv=pt; /prv保存當(dāng)前結(jié)點(diǎn)指針保存當(dāng)前結(jié)點(diǎn)指針 pt=tmp; /pt指向下個(gè)結(jié)點(diǎn)指向下個(gè)結(jié)點(diǎn)h.setNex(prv); /頭指針指向新鏈表頭指針指向新鏈表數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表19答：能。只要定義一個(gè)結(jié)構(gòu)類型（含答：能。只要定義一個(gè)結(jié)構(gòu)類型（含數(shù)據(jù)域數(shù)據(jù)域和和指示指示域域）數(shù)組，

18、就可以完全描述鏈表，這種鏈表稱為）數(shù)組，就可以完全描述鏈表，這種鏈表稱為靜靜態(tài)鏈表態(tài)鏈表。注：數(shù)據(jù)域含義注：數(shù)據(jù)域含義與前面相同，與前面相同，指示域指示域相當(dāng)于前面的相當(dāng)于前面的指針域。指針域。討論討論1 1： 用一維數(shù)組也能存放鏈表嗎？怎樣實(shí)現(xiàn)？用一維數(shù)組也能存放鏈表嗎？怎樣實(shí)現(xiàn)？靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動(dòng)元素，只需修改指示器不需要移動(dòng)元素，只需修改指示器就可以了。就可以了。數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表20討論討論2 2： 鏈表能不能首尾相連？怎樣實(shí)現(xiàn)？鏈表能不能首尾相連？怎樣實(shí)現(xiàn)？答：能。只要將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)

19、答：能。只要將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)即可點(diǎn)即可 ( (P.setNext(head);P.setNext(head);) ) 。這種形成環(huán)路的鏈表。這種形成環(huán)路的鏈表稱為稱為循環(huán)鏈表循環(huán)鏈表。討論討論3 3： 單鏈表只能查找結(jié)點(diǎn)的直接后繼，能不能單鏈表只能查找結(jié)點(diǎn)的直接后繼，能不能查找直接前驅(qū)？如何實(shí)現(xiàn)？查找直接前驅(qū)？如何實(shí)現(xiàn)？答：答：能能。只要把單鏈表再多開一個(gè)指針域即可。只要把單鏈表再多開一個(gè)指針域即可( (例例如用如用nextnext和和pre;pre;) ) 。雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。predatanext

20、這種有兩個(gè)指針的鏈表稱為這種有兩個(gè)指針的鏈表稱為雙向鏈表雙向鏈表。其特點(diǎn)是。其特點(diǎn)是可以雙向查找表中結(jié)點(diǎn)?？梢噪p向查找表中結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表21 循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)p的指針指向頭結(jié)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀點(diǎn)，使鏈表構(gòu)成環(huán)狀 p.setNext(head);p.setNext(head); 特點(diǎn)特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率點(diǎn)，提高查找效率 操作與單鏈表基本一致操作與單鏈表基本一致,循環(huán)條件不同循環(huán)條件不同 單鏈表單鏈表p=h.getNext( ); p!=NULL 循環(huán)鏈表

21、循環(huán)鏈表p=h.getNext( ); p!=hhh空表空表 循環(huán)鏈表循環(huán)鏈表(circular linked list)數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表22 雙向鏈表雙向鏈表（double linked list）單鏈表具有單向性的缺點(diǎn)單鏈表具有單向性的缺點(diǎn)Public class DLNode implements Node private Object element; private DLNode pre; private DLNode next; public DLNode( ) this(null,null,null); public DLNode( Object ele, DLNod

22、e pre, DLNode next) this.element=ele; this.pre=pre; this.next=next; public DLNode getNext( ) return next; public void setNext(DLNode next) this.next=next; public DLNode getPre( ) return pre; public void setPre(DLNode pre) this.pre=pre; public Object getData( ) return element; public void setData(Obj

23、ect obj ) element=obj;preelementnextv結(jié)點(diǎn)定義數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表23 雙向鏈表雙向鏈表（double linked list）單鏈表具有單向性的缺點(diǎn)單鏈表具有單向性的缺點(diǎn)preelementnextL空雙向循環(huán)鏈表：v結(jié)點(diǎn)定義非空雙向循環(huán)鏈表： LABbcap(p.getPre( ).getNext( )= p= (p.getNext( ).getPre( );數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表24bcaP(p.getPre( ).setNext(p.getNext( );(p.getNext( ).setPre(p.getPre( ); 刪除 算法描述

24、 算法評(píng)價(jià)：T(n)=O(1)(p.getPre( ).setNext(p.getNext( );(p.getNext( ).setPre(p.getPre( );數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表25 算法描述 算法評(píng)價(jià)：T(n)=O(1)xSbaP 插入數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表265. 鏈表的運(yùn)算效率分析鏈表的運(yùn)算效率分析1. 查找查找 因線性鏈表因線性鏈表不能順序存取不能順序存取，即在查找時(shí)要，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為從頭指針找起，查找的時(shí)間復(fù)雜度為 O(n)。時(shí)間效率分析2. 插入和刪除插入和刪除 因線性鏈表不需要移動(dòng)元素，只要修因線性鏈表不需要移動(dòng)元素，只要修改指針

25、，一般情況下時(shí)間復(fù)雜度為改指針，一般情況下時(shí)間復(fù)雜度為 O(1)。 但是，如果要在單鏈表中進(jìn)行但是，如果要在單鏈表中進(jìn)行前插前插或或刪除刪除操作，操作，由由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為 O(n)。數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表27練：練：空間效率分析鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間，相當(dāng)于總鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間，相當(dāng)于總共增加了共增加了n 個(gè)變量，空間復(fù)雜度為個(gè)變量，空間復(fù)雜度為 O(n)。在在n n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)P P，需找到它，需找到它的的 ，其時(shí)間復(fù)雜度為，其時(shí)間復(fù)雜度為 。 前驅(qū)

26、結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)O O(n)(n)數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表28線性表的實(shí)現(xiàn)與表示方法小結(jié)：線性表的實(shí)現(xiàn)與表示方法小結(jié)： 線性表邏輯結(jié)構(gòu)特點(diǎn)是線性表邏輯結(jié)構(gòu)特點(diǎn)是，只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；，只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；除首尾結(jié)點(diǎn)外其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。除首尾結(jié)點(diǎn)外其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。簡言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一（簡言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一（1:11:1）的。的。問問1：線性表的邏輯結(jié)構(gòu)特點(diǎn)是什么？其順序存儲(chǔ)線性表的邏輯結(jié)構(gòu)特點(diǎn)是什么？其順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是什么？結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是什么？答：答： 順序存儲(chǔ)順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。關(guān)系的指針。數(shù)據(jù)結(jié)構(gòu)四次課-第2章線性表29 順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大(