數據結構四次課-第2章線性表課件

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

2、章線性表2上堂課要點回顧上堂課要點回顧線性結構線性結構( (包括表、棧、隊、數組）的定義和特點：包括表、棧、隊、數組）的定義和特點： 僅一個首、尾結點，其余元素僅一個直接前驅和一僅一個首、尾結點，其余元素僅一個直接前驅和一個直接后繼。個直接后繼。2. 2. 線性表線性表邏輯結構邏輯結構：“一對一一對一” ” 或或 1:11:1存儲結構存儲結構：順序、鏈式：順序、鏈式運運 算算：修改、插入、刪除：修改、插入、刪除3.3.順序存儲順序存儲特征：特征：邏輯上相鄰，物理上也相鄰；邏輯上相鄰，物理上也相鄰；優(yōu)點：優(yōu)點：隨機查找快隨機查找快 O(1)O(1)缺點：缺點：插入、刪除慢插入、刪除慢 O(n)O

3、(n)數據結構四次課-第2章線性表32.3 線性表的鏈式表示和實現線性表的鏈式表示和實現2.3.1 鏈表的表示鏈表的表示2.3.2 鏈表的實現鏈表的實現2.3.3 鏈表的運算效率分析鏈表的運算效率分析鏈表小結鏈表小結數據結構四次課-第2章線性表42.3.1 鏈表的表示鏈表的表示鏈式存儲結構特點：鏈式存儲結構特點：其結點在存儲器中的其結點在存儲器中的位置是位置是隨意隨意的，的，即邏輯上相鄰的數據元素邏輯上相鄰的數據元素在物理上在物理上不一定不一定相鄰相鄰。如何實現？通過來實現注意：注意：每個存儲結點都包含兩部分：每個存儲結點都包含兩部分： 數據域數據域和和指針域指針域數據結構四次課-第2章線性表

4、5與鏈式存儲有關的術語：與鏈式存儲有關的術語：1、結點：、結點：數據元素的存儲映像。由數據域和指針域兩部分組成；數據元素的存儲映像。由數據域和指針域兩部分組成；2、鏈表：、鏈表： n 個結點由個結點由指針鏈指針鏈組成一個鏈表。它是線性表的鏈式組成一個鏈表。它是線性表的鏈式存儲映像存儲映像，稱為線性表的鏈式存儲結構稱為線性表的鏈式存儲結構。3、單鏈表、雙鏈表、多鏈表、循環(huán)鏈表、單鏈表、雙鏈表、多鏈表、循環(huán)鏈表： 結點只有一個指針域的鏈表，稱為結點只有一個指針域的鏈表，稱為單鏈表單鏈表或或線性鏈表線性鏈表；有兩個指針域的鏈表，稱為有兩個指針域的鏈表，稱為雙鏈表雙鏈表；有多個指針域的鏈表，稱為有多個

5、指針域的鏈表，稱為多鏈表多鏈表；首尾相接的鏈表稱為首尾相接的鏈表稱為循環(huán)鏈表循環(huán)鏈表。a1heada2anhead循環(huán)鏈表示意圖：循環(huán)鏈表示意圖：數據結構四次課-第2章線性表64、頭指針、頭結點和首元結點、頭指針、頭結點和首元結點 示意圖如下：示意圖如下：頭指針頭指針頭結點頭結點首元結點首元結點a1heada2infoan頭指針頭指針是指向鏈表中是指向鏈表中第一個結點第一個結點（或為頭結點或為首元結點）（或為頭結點或為首元結點）的指針；的指針；頭結點頭結點是在鏈表的是在鏈表的首元結點之前附設的一個結點首元結點之前附設的一個結點；數據域內；數據域內只放空表標志和表長等信息只放空表標志和表長等信息

6、; ;首元結點首元結點是指鏈表中存儲線性表是指鏈表中存儲線性表第一個數據元素第一個數據元素a a1 1的結點。的結點。 數據結構四次課-第2章線性表7一個線性表的邏輯結構為：一個線性表的邏輯結構為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存），其存儲結構用單鏈表表示如下，儲結構用單鏈表表示如下，請問其請問其頭指針頭指針的的值值是多少？是多少？存儲地址存儲地址數據域數據域指針域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZH

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

8、在鏈表的首元結點之前附設的一個結點，該結即在鏈表的首元結點之前附設的一個結點，該結點的數據域中不存儲線性表的數據元素，其作用是為了對鏈表點的數據域中不存儲線性表的數據元素，其作用是為了對鏈表進行操作時，可以對進行操作時，可以對空表、非空表空表、非空表的情況以及對的情況以及對首元結點首元結點進行進行統一處理，編程更方便。統一處理，編程更方便。答：答：無頭結點時，無頭結點時，當頭指針的值為空當頭指針的值為空時表示空表；時表示空表；有頭結點時，有頭結點時，當頭結點的指針域為空當頭結點的指針域為空時表示空表。時表示空表。頭指針頭指針頭指針頭指針頭結點頭結點無頭結點無頭結點有頭結點有頭結點數據結構四次課

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

10、epublic Object getData( );/獲取結點數據域獲取結點數據域Public void setData(Object object);/設置結點數據域設置結點數據域3. 線性鏈表的實現線性鏈表的實現 定義：結點中只含一個指針域的鏈表叫定義：結點中只含一個指針域的鏈表叫，也叫，也叫單鏈表單鏈表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; 數據結構四次課-第2章線性表12 用一組用一組任意任意的存儲單元存儲線性表的數據元素的存儲單元存儲線性表的數據元素 利用利用指針指針實現了用不相鄰的存儲單元存放邏輯上實現了

12、用不相鄰的存儲單元存放邏輯上相鄰的元素相鄰的元素 每個數據元素每個數據元素ai，除存儲，除存儲本身信息本身信息外，還需存儲其外，還需存儲其直接后繼直接后繼的地址的地址 結點結點 數據域：元素本身信息數據域：元素本身信息 指針域：指示直接后繼的存儲位置指針域：指示直接后繼的存儲位置數據域數據域 指針域指針域結點結點簡單總結：線性表的鏈式表示的基本特征：簡單總結：線性表的鏈式表示的基本特征：數據結構四次課-第2章線性表134. 單鏈表的基本運算單鏈表的基本運算While循環(huán)中語句頻度為循環(huán)中語句頻度為若找到結點若找到結點X，為結點，為結點X在表中的序號在表中的序號否則，為否則，為n nOnT 算法

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

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

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

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

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

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

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

20、這種有兩個指針的鏈表稱為這種有兩個指針的鏈表稱為雙向鏈表雙向鏈表。其特點是。其特點是可以雙向查找表中結點。可以雙向查找表中結點。數據結構四次課-第2章線性表21 循環(huán)鏈表是表中最后一個結點循環(huán)鏈表是表中最后一個結點p的指針指向頭結的指針指向頭結點，使鏈表構成環(huán)狀點，使鏈表構成環(huán)狀 p.setNext(head);p.setNext(head); 特點特點：從表中任一結點出發(fā)均可找到表中其他結從表中任一結點出發(fā)均可找到表中其他結點，提高查找效率點，提高查找效率 操作與單鏈表基本一致操作與單鏈表基本一致,循環(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)數據結構四次課-第2章線性表22 雙向鏈表雙向鏈表（double linked list）單鏈表具有單向性的缺點單鏈表具有單向性的缺點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結點定義數據結構四次課-第2章線性表23 雙向鏈表雙向鏈表（double linked list）單鏈表具有單向性的缺點單鏈表具有單向性的缺點preelementnextL空雙向循環(huán)鏈表：v結點定義非空雙向循環(huán)鏈表： LABbcap(p.getPre( ).getNext( )= p= (p.getNext( ).getPre( );數據結構四次課-第2章線性表24bcaP(p.getPre( ).setNext(p.getNext( );(p.getNext( ).setPre(p.getPre( ); 刪除 算法描述

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

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

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