Java數(shù)據(jù)結(jié)構(gòu)和算法筆記

1、Java數(shù)據(jù)結(jié)構(gòu)和算法第0講 綜述參考教材：Java數(shù)據(jù)結(jié)構(gòu)和算法（第二版），美 Robert lafore1. 數(shù)據(jù)結(jié)構(gòu)的特性數(shù)據(jù)結(jié)構(gòu)優(yōu)點缺點數(shù)組插入快；如果知道下標，可以非?？斓卮嫒〔檎衣瑒h除慢，大小固定有序數(shù)組比無序的數(shù)組查找快刪除和插入慢，大小固定棧提供后進先出方式的存取存取其他項很慢隊列提供先進先出方式的存取存取其他項很慢鏈表插入快，刪除快查找慢二叉樹查找、插入、刪除都快（如果樹保持平衡）刪除算法復雜紅-黑樹查找、插入、刪除都快；樹總是平衡的算法復雜2-3-4樹查找、插入、刪除都快；樹總是平衡的；類似的樹對磁盤存儲有用算法復雜哈希表如果關鍵字已知，則存儲極快；插入快刪除慢，如果不知

2、道關鍵字則存儲很慢，對存儲空間使用不充分堆插入、刪除快；對大數(shù)據(jù)項的存取很快對其他數(shù)據(jù)項存取慢圖對現(xiàn)實世界建模有些算法慢且復雜2. 經(jīng)典算法總結(jié)查找算法：線性查找和二分查找排序算法：用表展示第一講 數(shù)組1. Java中數(shù)組的基礎知識1） 創(chuàng)建數(shù)組在Java中把數(shù)組當作對象來對待，因此在創(chuàng)建數(shù)組時必須使用new操作符：int intArr = new int10;一旦創(chuàng)建數(shù)組，數(shù)組大小便不可改變。2） 訪問數(shù)組數(shù)據(jù)項數(shù)組數(shù)據(jù)項通過方括號中的下標來訪問，其中第一個數(shù)據(jù)項的下標是0： intArr0 = 123;3） 數(shù)組的初始化當創(chuàng)建數(shù)組之后，除非將特定的值賦給數(shù)組的數(shù)據(jù)項，否則它們一直是特殊的n

3、ull對象。 int intArr = 1, 2, 3, 4, 5;等效于下面使用new來創(chuàng)建數(shù)組并初始化：int intArr = new int5;intArr0 = 1;intArr1 = 2;intArr2 = 3;intArr3 = 4;intArr4 = 5;2. 面向?qū)ο缶幊谭绞?） 使用自定義的類封裝數(shù)組MyArray類：public class MyArray private long arr;private int size;/記錄數(shù)組的有效長度public MyArray() arr = new long10;public MyArray(int maxSize) arr

4、 = new longmaxSize;/向數(shù)組中插入數(shù)據(jù)public void insert(long element) arrsize = element;size+;/顯示數(shù)組中的數(shù)據(jù)public void show() for(int i=0; i<size; i+) if(i=0) System.out.print("" + arri + ", "); else if(i=size-1) System.out.println(arri + ""); else System.out.print(arri + ",

5、 ");/根據(jù)值查找索引（出現(xiàn)該值的第一個位置）：線性查找public int queryByValue(long element) int i;for(i=0; i<size; i+) / linear search if(arri = element) break;if(i = size) return -1; else return i;/根據(jù)索引查找值public long queryByIndex(int index) if(index >= size | index < 0) throw new ArrayIndexOutOfBoundsExceptio

6、n(); else return arrindex;/刪除數(shù)據(jù)public void delete(int index) if(index >= size | index < 0) throw new ArrayIndexOutOfBoundsException(); else /當size=maxSize，刪除最后一個數(shù)時，不會執(zhí)行forfor(int i=index; i<size-1; i+) arrindex = arrindex + 1; System.out.println("for");size-;/更新數(shù)據(jù)public void updat

7、e(int index, long value) if(index >= size | index < 0) throw new ArrayIndexOutOfBoundsException(); else arrindex = value;2） 添加類方法實現(xiàn)數(shù)據(jù)操作測試MyArray類方法：public void testMyArray() throws Exception MyArray myArray = new MyArray();myArray.insert(123);myArray.insert(456);myArray.insert(789);myArray.sho

8、w();/123, 456, 789System.out.println(myArray.queryByValue(111);/-1System.out.println(myArray.queryByIndex(2);/789myArray.delete(2);myArray.show();/123, 456myArray.update(0, 0);myArray.show();/0, 4563. 有序數(shù)組1） 有序數(shù)組簡介以及其優(yōu)點有序數(shù)組是一種數(shù)組元素按一定的順序排列的數(shù)組，從而方便使用二分查找來查找數(shù)組中特定的元素。有序數(shù)組提高了查詢的效率，但并沒有提高刪除和插入元素的效率。2） 構(gòu)建有

9、序數(shù)組將2.1中自定義的類封裝數(shù)組MyArray的insert方法改為如下：/向有序數(shù)組中插入數(shù)據(jù)，按大小從前往后排列public void insert(long element) int i;for(i=0; i<size; i+) / find where it goesif(element<arri) break;for(int j=size; j>i; j-) / move bigger ones uparrj = arrj-1;arri = element;size+;得到有序數(shù)組的類封裝MyOrderedArray類，測試該類中的insert方法： public

10、 void testMyOrderedArray() throws Exception MyOrderedArray myOrderedArray = new MyOrderedArray();myOrderedArray.insert(999);myOrderedArray.insert(555);myOrderedArray.insert(777);myOrderedArray.show();/555, 777, 9994. 查找算法1） 線性查找在查找過程中，將要查找的數(shù)一個一個地與數(shù)組中的數(shù)據(jù)項比較，直到找到要找的數(shù)。在2.1中自定義的類封裝數(shù)組MyArray的queryByValue

11、方法，使用的就是線性查找。2） 二分查找二分查找（又稱折半查找），即不斷將有序數(shù)組進行對半分割，每次拿中間位置的數(shù)和要查找的數(shù)進行比較：如果要查找的數(shù)<中間數(shù)，則表明要查的數(shù)在數(shù)組的前半段；如果要查的數(shù)>中間數(shù)，則表明該數(shù)在數(shù)組的后半段；如果要查的數(shù)=中間數(shù)，則返回中間數(shù)。在有序數(shù)組的類封裝類MyOrderedArray中添加binarySearch方法 /根據(jù)值二分查找索引（前提：有序）public int binarySearch(long value) int middle = 0;int left = 0;int right = size - 1;while(true) m

12、iddle = (left + right) / 2;if(arrmiddle = value) return middle;/ found it else if(left > right) return -1;/ can't found it else / divide rangeif(arrmiddle > value) right = middle - 1;/in lower half else left = middle + 1;/ in upper half測試該二分查找方法： public void testMyOrderedArray() throws Exc

13、eption MyOrderedArray myOrderedArray = new MyOrderedArray();myOrderedArray.insert(999);myOrderedArray.insert(555);myOrderedArray.insert(777);myOrderedArray.insert(333);System.out.println(myOrderedArray.binarySearch(333);/0第二講 簡單排序本講提到的排序算法都假定了數(shù)組作為數(shù)據(jù)存儲結(jié)構(gòu)，本講所有算法的時間復雜度都是。在大多數(shù)情況下，假設當數(shù)據(jù)量比較小或基本上有序時，插入排序算法

14、是三種簡單排序算法中最好的選擇，是應用最多的。對于更大數(shù)據(jù)量的排序來說，后面講到的快速排序通常是最快的方法。1. 冒泡排序1） 基本思想在要排序的一組數(shù)中，對當前還未排好序的范圍內(nèi)的全部數(shù)，自下而上對相鄰的兩個數(shù)依次進行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換。2） 算法實現(xiàn)冒泡排序的Java代碼：/ bubble sortpublic static void bubbleSort(long arr) long temp;for(int i=0; i<arr.length-1; i+) /outer loop (fo

15、rward)for(int j=arr.length-1; j>i; j-) /inner loop (backward)if(arrj < arrj-1) / swap themtemp = arrj;arrj = arrj-1;arrj-1 = temp;測試冒泡排序及輸出結(jié)果： public void testBubbleSort() throws Exception long arr = 79, 91, 13, 52, 34;Sort.bubbleSort(arr);System.out.println(Arrays.toString(arr);/13, 34, 52, 7

16、9, 912. 選擇排序1） 基本思想在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換；然后在剩下的數(shù)當中再找最小的與第二個位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。與冒泡排序相比，選擇排序?qū)⒈匾慕粨Q次數(shù)從O(N*N)減少到O(N)，但比較次數(shù)仍然保持為O(N*N)。2） 算法實現(xiàn)選擇排序的Java代碼：/ select sortpublic static void selectSort(long arr) long temp;for(int i=0; i<arr.length-1; i+) /outer loopint k = i; / location of

17、 minimumfor(int j=i+1; j<arr.length; j+) /inner loopif(arrj < arrk) k = j; / a new minimum locationtemp = arri;arri = arrk;arrk = temp;測試選擇排序及輸出結(jié)果：public void testSelectSort() throws Exception long arr = 79, 91, 13, 52, 34;Sort.selectSort(arr);System.out.println(Arrays.toString(arr);/13, 34, 5

18、2, 79, 913. 插入排序1） 基本思想在要排序的一組數(shù)中，假設前面(n-1)n>=2個數(shù)已經(jīng)是排好順序的（局部有序），現(xiàn)在要把第n個數(shù)插到前面的有序數(shù)中，使得這n個數(shù)也是排好順序的。如此反復循環(huán)，直到全部排好順序。在插入排序中，一組數(shù)據(jù)僅僅是局部有序的；而冒泡排序和選擇排序，一組數(shù)據(jù)項在某個時刻是完全有序的。2） 算法實現(xiàn)插入排序的Java代碼：/ insert sortpublic static void insertSort(long arr) long temp;for(int i=1; i<arr.length; i+) / i is marked location

19、temp = arri; / remove marked itemint j = i; / start shifts at iwhile(j>=1 && arrj-1>temp) / until one is smallerarrj = arrj-1; / shift item rightj-; / go left one positionarrj = temp; / insert marked item測試插入排序以及輸出結(jié)果：public void testInsertSort() throws Exception long arr = 79, 91, 13,

20、52, 34, 34;Sort.insertSort(arr);System.out.println(Arrays.toString(arr); /13, 34, 34, 52, 79, 91第三講 棧和隊列棧和隊列都是抽象數(shù)據(jù)類型（abstract data type，ADT），它們既可以用數(shù)組實現(xiàn)，又可以用鏈表實現(xiàn)。1. 棧1） 棧模型棧（Stack，又LIFO：后進先出）是一種只能在固定的一端進行插入和刪除的數(shù)據(jù)結(jié)構(gòu)。棧只允許訪問一個數(shù)據(jù)項：即最后插入的數(shù)據(jù)項，移除這個數(shù)據(jù)項后才能訪問倒數(shù)第二個插入的數(shù)據(jù)項，以此類推。?？梢杂脭?shù)組來實現(xiàn)，也可以用鏈表來實現(xiàn)。2） 棧的數(shù)組實現(xiàn)棧的Java

21、代碼：public class MyStack private long arr; /底層使用數(shù)組實現(xiàn)private int top;public MyStack() arr = new long10;top = -1;public MyStack(int maxSize) arr = new longmaxSize;top = -1;/ put item on top of stackpublic void push(long value) arr+top = value;/ take item from top of stackpublic long pop() return arrtop

22、-;/ peek at top of stack public long peek() return arrtop;/ ture if stack is emptypublic boolean isEmpty() return (top = -1);/ ture if stack is fullpublic boolean isFull() return (top = arr.length-1);測試棧的特性：public void testMyStack() throws Exception MyStack myStack = new MyStack(4);myStack.push(12);

23、myStack.push(34);myStack.push(56);myStack.push(78);System.out.println(myStack.isFull(); / truewhile(!myStack.isEmpty() System.out.print(myStack.pop(); /78, 56, 34, 12if(!myStack.isEmpty() System.out.print(", ");System.out.println();System.out.println(myStack.isFull(); / false2. 隊列1） 隊列模型隊列

24、（Queue，又FIFO：先進先出）是一種插入時在一端進行而刪除時在另一端進行的數(shù)據(jù)結(jié)構(gòu)。為解決順序隊列假溢出問題，而采用循環(huán)隊列：即讓隊頭、隊尾指針在達到尾端時，又繞回到開頭。2） 隊列的數(shù)組實現(xiàn)隊列的Java代碼：public class MyQueue private long arr;private int size;private int front;private int rear;public MyQueue() arr = new long10;size = 0;front = 0;rear = -1;public MyQueue(int maxSize) arr = new

25、longmaxSize;size = 0;front = 0;rear = -1;/ put item at rear of queuepublic void insert(long value) if(isEmpty() / throw exception if queue is fullthrow new ArrayIndexOutOfBoundsException(); if(rear = arr.length-1) /deal with wraparound (環(huán)繞式處理)rear = -1;arr+rear = value; / increment rear and insertsi

26、ze+; / increment size/ take item from front of queuepublic long remove() long value = arrfront+; / get value and increment frontif(front = arr.length) / deal with wraparoundfront = 0;size-; / one less itemreturn value;/ peek at front of queuepublic long peek() return arrfront;/ true if queue is empt

27、ypublic boolean isEmpty() return (size = 0);/ true if queue is fullpublic boolean isFull() return (size = arr.length);測試隊列的特性：public void testMyQueue() throws Exception MyQueue myQueue = new MyQueue(4);myQueue.insert(12);myQueue.insert(34);myQueue.insert(56);myQueue.insert(78);System.out.println(myQ

28、ueue.isFull(); / truewhile(!myQueue.isEmpty() System.out.print(myQueue.remove(); /12, 34, 56, 78if(!myQueue.isEmpty() System.out.print(", ");System.out.println();System.out.println(myQueue.isEmpty(); / truemyQueue.insert(99);System.out.println(myQueue.peek(); / 99第四講 鏈表1. 鏈結(jié)點一個鏈結(jié)點（Link，或稱結(jié)

29、點）是某個類的對象，該對象中包含對下一個鏈結(jié)點引用的字段（通常叫next）。而鏈表本身的對象中有一個字段指向?qū)Φ谝粋€鏈結(jié)點的引用。Link類的定義：public class Link public long data; / data itempublic Link next; / next link in listpublic Link(long data) this.data = data;public void displayLink() / display ourselfSystem.out.print(data + "-> ");2. 單鏈表（LinkList

30、）LinkList類顯示了一個單鏈表，該鏈表可以進行的操作有：l 在鏈表頭插入一個數(shù)據(jù)（insertFirst）：設置新添加的結(jié)點的next設為原來的頭結(jié)點，再將新添加的結(jié)點設為頭結(jié)點。l 在鏈表頭刪除一個數(shù)據(jù)（deleteFirst）：將第二個結(jié)點設為頭結(jié)點。l 遍歷鏈表顯示所有數(shù)據(jù)（displayList）：使用臨時指針current，從頭結(jié)點開始，沿著鏈表先前移動，依次遍歷每個節(jié)點。LinkList類：public class LinkList private Link first; / reference to first link on listpublic LinkList() t

31、his.first = null;/ insert at start of listpublic void insertFirst(long value) Link newLink = new Link(value);newLink.next = first; / newLink -> old firstfirst = newLink; / first -> newLink/ delete first itempublic Link deleteFirst() if(first = null) return null;Link temp = first; first = first

32、.next; / delete it: first -> old nextreturn temp; / return deleted linkpublic void displayList() Link current = first; / start at beginning of listwhile(current != null) / until end of listcurrent.displayLink();current = current.next; / move list to next linkSystem.out.println();測試LinkList類的方法：pu

33、blic void testLinkList() throws Exception LinkList linkList = new LinkList();linkList.insertFirst(88);linkList.insertFirst(66);linkList.insertFirst(44);linkList.insertFirst(22);linkList.displayList(); /22-> 44-> 66-> 88->linkList.deleteFirst();linkList.displayList(); /44-> 66-> 88-

34、>3. 查找和刪除指定鏈結(jié)點此外，還能對指定的結(jié)點值進行查找和刪除：l 查找指定結(jié)點（find）：類似于之前的displayList方法。l 刪除指定結(jié)點（delete）：在刪除指定結(jié)點時，必須把前一個結(jié)點和后一個結(jié)點連接在一起，所以需要一個臨時指針（previous）來保存對前一個結(jié)點的引用。向LinkList類中添加查找（find）和刪除（delete）方法：/ find link with given keypublic Link find(long key) Link current = first; / start at 'first'while(current

35、.data != key) if(current.next = null) / didn't find itreturn null; else / go to next linkcurrent = current.next;return current;/ delete link with given keypublic Link delete(long key) Link current = first; / search for expected linkLink previous = first;while(current.data != key) if(current.next

36、 = null) return null; / didn't find it else previous = current;current = current.next; / go to next link/ find itif(current = first) / if first link, change firstfirst = first.next; else / otherwise, bypass itprevious.next = current.next;return current;測試添加的find和delete方法：public void testLinkList

37、() throws Exception LinkList linkList = new LinkList();linkList.insertFirst(88);linkList.insertFirst(66);linkList.insertFirst(44);linkList.insertFirst(22);linkList.displayList(); /22-> 44-> 66-> 88->linkList.find(44).displayLink(); / 44->System.out.println();linkList.delete(44).displa

38、yLink(); / 44->System.out.println();linkList.displayList(); /22-> 66-> 88->第五講 雙端鏈表和雙向鏈表1. 雙端鏈表鏈表中保存著對最后一個鏈結(jié)點的引用l 從頭部進行插入（insertFirst）：要對鏈表進行判斷，如果鏈表為空，則設置尾結(jié)點為新添加的結(jié)點。l 從尾部進行插入（insertLast）：如果鏈表為空，則直接設置頭結(jié)點為新添加的結(jié)點，否則設置尾結(jié)點的后一個節(jié)點為新添加的結(jié)點。l 從頭部進行刪除（deleteFirst）：判斷頭結(jié)點是否有下一個結(jié)點，如果沒有則設置尾結(jié)點為null。雙端鏈表

39、FirstLastList類：public class FirstLastList private Link first; / reference to first linkprivate Link last; / reference to last linkpublic FirstLastList() this.first = null;this.last = null;public boolean isEmpty() / true if no linksreturn first = null;/ insert at front of listpublic void insertFirst(

40、long value) Link newLink = new Link(value);if(isEmpty() / if empty listlast = newLink; / newLink <- lastnewLink.next = first; / newLink -> old firstfirst = newLink; / first -> newLink/ insert at end of listpublic void insertLast(long value) Link newLink = new Link(value);if(isEmpty() / if e

41、mpty listfirst = newLink; / first -> newLink else last.next = newLink; / old last -> newLinklast = newLink; / newLink <- last/ delete first linkpublic Link deleteFirst() Link temp = first;if(first.next = null) / if only one itemlast = null; / null <- lastfirst = first.next; / first ->

42、 old nextreturn temp;public void displayList() Link current = first; / start at beginning of listwhile(current != null) / until end of listcurrent.displayLink();current = current.next; / move list to next linkSystem.out.println();測試FirstLastList類及輸出結(jié)果：public void testFirstLastList() throws Exception

43、 FirstLastList list = new FirstLastList();list.insertLast(24);list.insertFirst(13);list.insertFirst(5);list.insertLast(46);list.displayList(); /5-> 13-> 24-> 46->list.deleteFirst();list.displayList(); /13-> 24-> 46->2. 雙向鏈表雙向鏈表既允許向后遍歷，也允許向前遍歷整個鏈表。即每個節(jié)點除了保存了對下一個節(jié)點的引用，同時后保存了對前一個節(jié)點

44、的引用。l 從頭部進行插入（insertFirst）：要對鏈表進行判斷，如果為空，則設置尾結(jié)點為新添加的結(jié)點；如果不為空，還需要設置頭結(jié)點的前一個結(jié)點為新添加的結(jié)點。l 從尾部進行插入（insertLast）：如果鏈表為空，則直接設置頭結(jié)點為新添加的結(jié)點，否則設置尾節(jié)點的后一個結(jié)點為新添加的結(jié)點。同時設置新添加的結(jié)點的前一個結(jié)點為尾結(jié)點。l 從頭部進行刪除（deleteFirst）：判斷頭結(jié)點是否有下一個結(jié)點，如果沒有則設置尾結(jié)點為null；否則設置頭結(jié)點的下一個結(jié)點的previous為null。l 從尾部進行刪除（deleteLast）：如果頭結(jié)點后沒有其他結(jié)點，則設置頭結(jié)點為null。否則

45、設置尾結(jié)點的前一個結(jié)點的next為null。設置尾結(jié)點為其前一個結(jié)點。l 在指定結(jié)點后插入（insertAfter）：l 刪除指定結(jié)點（deleteKey）：不再需要在使用一個臨時的指針域指向前一個結(jié)點。雙向鏈表的鏈接點Link類的定義：public class DoubleLink public long data; / data itempublic DoubleLink next; / next link in listpublic DoubleLink previous; / previous link in listpublic DoubleLink(long data) this.

46、data = data;public void displayLink() / display ourselfSystem.out.print(data + "<=> ");雙向鏈表DoublyLinkedList類：public class DoublyLinkedList private DoubleLink first; / reference to first linkprivate DoubleLink last; / reference to last linkpublic DoublyLinkedList() this.first = null;t

47、his.last = null;public boolean isEmpty() / true if no linksreturn first = null;/ insert at front of listpublic void insertFirst(long value) DoubleLink newLink = new DoubleLink(value);if(isEmpty() / if empty listlast = newLink; / newLink <- last else first.previous = newLink; / newLink <- old f

48、irstnewLink.next = first; / newLink -> old firstfirst = newLink; / first -> newLink/ insert at end of listpublic void insertLast(long value) DoubleLink newLink = new DoubleLink(value);if(isEmpty() / if empty listfirst = newLink; / first -> newLink else last.next = newLink; / old last ->

49、newLinknewLink.previous = last; /old last <- newLinklast = newLink; / newLink <- last/ delete first linkpublic DoubleLink deleteFirst() DoubleLink temp = first;if(first.next = null) / if only one itemlast = null; / null <- last else first.next.previous = null; / null <- old nextfirst = f

50、irst.next; / first -> old nextreturn temp;/delete last linkpublic DoubleLink deleteLast() DoubleLink temp = last;if(first.next = null) / if only one itemfirst = null; / first -> null else last.previous.next = null; /old previous -> nulllast = last.previous; / old previous <- lastreturn temp; / insert data just after ke