第02章線性表(Java版)

1、數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）第第2章章 線性表線性表2.1 線性表抽象數(shù)據(jù)類型線性表抽象數(shù)據(jù)類型2.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)l2.3 線性表的鏈式表示和實現(xiàn)線性表的鏈式表示和實現(xiàn) l2.4 線性表的應(yīng)用：多項式的表示及運算線性表的應(yīng)用：多項式的表示及運算數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）目的和要求目的和要求 目的：目的：實現(xiàn)線性表抽象數(shù)據(jù)類型。實現(xiàn)線性表抽象數(shù)據(jù)類型。 內(nèi)容：內(nèi)容：將線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)將線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu) 實現(xiàn)分別封裝成順序表類、單鏈表類、循環(huán)實現(xiàn)分別封裝成順序表類、單鏈表類、循環(huán) 雙鏈表類等，比較這兩種實現(xiàn)的特點以及各

2、雙鏈表類等，比較這兩種實現(xiàn)的特點以及各 種基本操作算法的效率。種基本操作算法的效率。 要求：要求：理解線性表抽象數(shù)據(jù)類型，掌握順序和鏈式理解線性表抽象數(shù)據(jù)類型，掌握順序和鏈式 存儲結(jié)構(gòu)實現(xiàn)線性表的方法。存儲結(jié)構(gòu)實現(xiàn)線性表的方法。 重點：重點：順序表、單鏈表、循環(huán)雙鏈表等線性表的設(shè)順序表、單鏈表、循環(huán)雙鏈表等線性表的設(shè) 計訓(xùn)練。計訓(xùn)練。 難點：難點：使用指針實現(xiàn)鏈式存儲結(jié)構(gòu)，通過指針操作使用指針實現(xiàn)鏈式存儲結(jié)構(gòu)，通過指針操作 改變結(jié)點間的鏈接關(guān)系。改變結(jié)點間的鏈接關(guān)系。 實驗：實驗：掌握單鏈表的遍歷、插入、刪除、復(fù)制等操掌握單鏈表的遍歷、插入、刪除、復(fù)制等操 作算法，熟悉循環(huán)單鏈表、雙鏈表和循環(huán)

3、雙作算法，熟悉循環(huán)單鏈表、雙鏈表和循環(huán)雙 鏈表的結(jié)構(gòu)和基本操作。掌握鏈表的結(jié)構(gòu)和基本操作。掌握MyEclipse集集 成開發(fā)環(huán)境的程序調(diào)試技術(shù)。成開發(fā)環(huán)境的程序調(diào)試技術(shù)。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2.1 線性表的抽象數(shù)據(jù)類型線性表的抽象數(shù)據(jù)類型LinearList=(a0，a1，an1) public interface LList /線性表接口，泛型參數(shù)線性表接口，泛型參數(shù)T表示數(shù)據(jù)元素的數(shù)據(jù)類型表示數(shù)據(jù)元素的數(shù)據(jù)類型 boolean isEmpty(); /判斷線性表是否空判斷線性表是否空 int length(); /返回線性表長度返回線性表長度 T get(int i); /返回

4、第返回第i（i0）個元素）個元素 void set(int i, T x); /設(shè)置第設(shè)置第i個元素值為個元素值為x void insert(int i, T x); /插入插入x作為第作為第i個元素個元素 void append(T x); /在線性表最后插入在線性表最后插入x元素元素 T remove(int i); /刪除第刪除第i個元素并返回被刪除對象個元素并返回被刪除對象 void removeAll(); /刪除線性表所有元素刪除線性表所有元素 T search(T key); /查找，返回首次出現(xiàn)的關(guān)鍵字為查找，返回首次出現(xiàn)的關(guān)鍵字為key元素元素public class Seq

5、List implements LList /順序表類順序表類public class SinglyLinkedList implements LList /單鏈表類單鏈表類數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)1.線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu) ciaLocaLoci)()(0數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）public class SeqList implements LList /順序表類，實現(xiàn)線性表接口順序表類，實現(xiàn)線性表接口 protected Object element; /對象數(shù)組對象數(shù)組 protected int le

6、n; /順序表長度，記載元素個數(shù)順序表長度，記載元素個數(shù)2. 順序表類順序表類數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）4. 順序表的刪除操作順序表的刪除操作 3. 順序表的插入操作順序表的插入操作 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）【例例2.1】 使用順序表類求解約使用順序表類求解約瑟夫環(huán)問題。瑟夫環(huán)問題。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）順序表的靜態(tài)特性很好，動態(tài)特性很差，具體說明如下。順序表的靜態(tài)特性很好，動態(tài)特性很差，具體說明如下。 順序表元素的物理存儲順序直接反映線性表元素的邏順序表元素的物理存儲順序直接反映線性表元素的邏輯順序，順序表是一種隨機存取結(jié)構(gòu)。輯順序，順序表是一種隨機存取結(jié)構(gòu)。get(

7、)、set()方法時間復(fù)雜度是方法時間復(fù)雜度是 O(1)。 插入和刪除操作效率很低。如果在各位置插入元素的插入和刪除操作效率很低。如果在各位置插入元素的概率相同概率相同，則有則有5.順序表操作的效率分析順序表操作的效率分析niniinOnnnninnpin00)(22) 1(11)(11)(數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）6. 順序表的淺拷貝與深拷貝順序表的淺拷貝與深拷貝 一個類的拷貝構(gòu)造方法聲明格式如下：一個類的拷貝構(gòu)造方法聲明格式如下： 類類(類類 對象對象)（1）順序表的淺拷貝）順序表的淺拷貝public SeqList(SeqList list)/淺拷貝構(gòu)造方法淺拷貝構(gòu)造方法 this

8、.element = list.element; /數(shù)組引用賦值，兩個變量共用一個數(shù)組，錯誤數(shù)組引用賦值，兩個變量共用一個數(shù)組，錯誤 this.len = list.len;數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）執(zhí)行拷貝構(gòu)造方法執(zhí)行拷貝構(gòu)造方法SeqList listb = new SeqList(lista);數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）（2）順序表的深拷貝）順序表的深拷貝 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）7.順序表比較相等順序表比較相等 兩個順序表相等是指，它們各對應(yīng)元素相等兩個順序表相等是指，它們各對應(yīng)元素相等并且長度相同。并且長度相同。 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2.3 線性表的鏈

9、式表示和實現(xiàn)線性表的鏈式表示和實現(xiàn)2.3.1 線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)2.3.2 單鏈表單鏈表2.3.3 雙鏈表雙鏈表數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2.3.1 線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）1. 單鏈表結(jié)點類單鏈表結(jié)點類 public class Node /單鏈表結(jié)點類單鏈表結(jié)點類 public T data; /數(shù)據(jù)域，保存數(shù)據(jù)元素數(shù)據(jù)域，保存數(shù)據(jù)元素 public Node next; /地址域，引用后繼結(jié)點地址域，引用后繼結(jié)點Node p,q;p=new Node(A, null ); q=new Node(B, null )

10、; p.next=q;2.3.2 單鏈表單鏈表數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2. 單鏈表的遍歷操作單鏈表的遍歷操作 Node p = head;while (p!=null) System.out.print(p.data.toString()+ ); /執(zhí)行訪問執(zhí)行訪問p結(jié)點的相關(guān)操作結(jié)點的相關(guān)操作 p = p.next;數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）如果語句如果語句p=p.next寫成寫成p.next=p數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）3. 單鏈表的插入操作單鏈表的插入操作 （1）空表插入）空表插入/頭插入頭插入if (head = null) /空表插入空表插入 head = new

11、 Node(x, null); else /頭插入頭插入 Node q = new Node(x, null); q.next = head; head = q; 即即head = new Node(x, head);數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）（2）中間插入）中間插入/尾插入尾插入Node q = new Node(x, null);q.next = p.next;/q的后繼結(jié)點應(yīng)是的后繼結(jié)點應(yīng)是p的原后繼結(jié)點的原后繼結(jié)點p.next = q; /q作為作為p的后繼結(jié)點的后繼結(jié)點即即p.next = new Node(x, p.next);數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）如果上述后兩條語

12、句次序顛倒，如果上述后兩條語句次序顛倒，則產(chǎn)生錯誤則產(chǎn)生錯誤Node q = new Node(x, null);p.next = q; q.next = p.next;數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）4. 單鏈表的刪除操作單鏈表的刪除操作 頭刪除頭刪除head = head.next; 中間中間/尾刪除尾刪除if (p.next!=null) p.next = p.next.next;數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）5.帶頭結(jié)點的單鏈表帶頭結(jié)點的單鏈表 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）【例例2.2】 采用單鏈表求解約瑟采用單鏈表求解約瑟夫環(huán)問題。夫環(huán)問題。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）6.

13、 單鏈表操作的效率分析單鏈表操作的效率分析1. isEmpty()方法的時間復(fù)雜度是方法的時間復(fù)雜度是O(1)。2. length()方法要遍歷單鏈表，時間復(fù)雜度是方法要遍歷單鏈表，時間復(fù)雜度是O(n)。 3. get(i)和和set(i)方法的時間復(fù)雜度是方法的時間復(fù)雜度是O(n)，不是隨機存取結(jié)構(gòu)。不是隨機存取結(jié)構(gòu)。 4. insert(i,x)和和remove(i)時間復(fù)雜度是時間復(fù)雜度是O(n)。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）1. 在在p結(jié)點之前插入結(jié)點結(jié)點之前插入結(jié)點q 2. 刪除結(jié)點刪除結(jié)點p要尋找其前驅(qū)結(jié)點要尋找其前驅(qū)結(jié)點front 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）7.提高單鏈

14、表操作效率的措施提高單鏈表操作效率的措施 public boolean append(T x) return insert(this.length(), x); /需遍歷單鏈表兩次，效率較低需遍歷單鏈表兩次，效率較低return insert(Integer.MAX_VALUE, x); /遍歷一次遍歷一次數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）作用于順序表的時間復(fù)雜度是作用于順序表的時間復(fù)雜度是O(n)，但作用于單鏈表的時間復(fù)雜度則是但作用于單鏈表的時間復(fù)雜度則是public String toString() String str=(; if (this.length()!=0) for(int

15、i=0; ithis.length()-1; i+) str += this.get(i).toString()+, ; str += this.get(this.length()-1).toString(); return str+);)(2nO數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）例例2.3 求整數(shù)單鏈表的平均值。求整數(shù)單鏈表的平均值。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）【例例2.4】 單鏈表逆轉(zhuǎn)。單鏈表逆轉(zhuǎn)。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）8.單鏈表的淺拷貝與深拷貝單鏈表的淺拷貝與深拷貝 public SinglyLinkedList(SinglyLinkedList list) /拷貝構(gòu)造函數(shù)，

16、淺拷貝拷貝構(gòu)造函數(shù)，淺拷貝 this.head = list.head; /導(dǎo)致兩個引用變量指向同一個結(jié)點導(dǎo)致兩個引用變量指向同一個結(jié)點 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）8.單鏈表的深拷貝單鏈表的深拷貝 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）9.9.單鏈表比較相等單鏈表比較相等兩條單鏈表相等是指，它們各對應(yīng)元素相兩條單鏈表相等是指，它們各對應(yīng)元素相等并且長度相同。等并且長度相同。數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）10. 排序單鏈表排序單鏈表數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）11. 循環(huán)單鏈表循環(huán)單鏈表 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2.3.3 雙鏈表雙鏈表1. 雙鏈表結(jié)構(gòu)雙鏈表結(jié)構(gòu)p = p.next

17、.pred = p.pred.next數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2.雙鏈表的插入和刪除操作雙鏈表的插入和刪除操作(1)插入插入在在p結(jié)點之前插入值為結(jié)點之前插入值為x結(jié)點結(jié)點 q = new DLinkNode(x, p.pred, p);p.pred.next = q;p.pred = q;數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）在在p結(jié)點之后插入值為結(jié)點之后插入值為x結(jié)點結(jié)點 q = new DLinkNode(x, p, p.next); /當當p.next=null時，尾插入時，尾插入if (p.next!=null) p.next.pred = q; /中間插入時執(zhí)行中間插入時執(zhí)行p.

18、next = q;數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）（2）雙鏈表的刪除操作）雙鏈表的刪除操作 p.pred.next = p.next; /有有p.pred!=nullif (p.next!=null) p.next.pred = p.pred;數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）3. 循環(huán)雙鏈表循環(huán)雙鏈表 數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）4.排序循環(huán)雙鏈表排序循環(huán)雙鏈表數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2.4 線性表的應(yīng)用：多項式的表示線性表的應(yīng)用：多項式的表示及運算及運算2.4.1 一元多項式的表示及運算一元多項式的表示及運算2.4.2 二元多項式的表示及運算二元多項式的表示及運算數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2.4.1 一元多項式的表示及運算一元多項式的表示及運算miiimmmxaxaxaxaaxA02210)(niiinnnxbxbxbxbbxB02210)(),max(0)()()(nmiiiinmxbaxBxA數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）1. 一元多項式的順序存儲結(jié)構(gòu)一元多項式的順序存儲結(jié)構(gòu)97427292)(xxxxxxAn數(shù)據(jù)結(jié)構(gòu)（Java版）（第3版）2. 一元多項式的鏈式存儲結(jié)構(gòu)一元多項式的鏈式存儲