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

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

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

　　第0講 綜述

　　參考教材：Java數(shù)據(jù)結(jié)構(gòu)和算法（第二版），[美] Robert lafore

　　1. 數(shù)據(jù)結(jié)構(gòu)的特性

　　數(shù)據(jù)結(jié)構(gòu) 數(shù)組 有序數(shù)組 棧 隊列 鏈表 二叉樹 紅-黑樹 2-3-4樹 哈希表 堆 圖

　　優(yōu)點

　　比無序的數(shù)組查找快 提供后進先出方式的存取 提供先進先出方式的存取 插入快，刪除快

　　查找、插入、刪除都快；樹總是平衡的 查找、插入、刪除都快；樹總是平衡的；類似的樹對磁盤存儲有用

　　如果關(guān)鍵字已知，則存儲極快；插入快 插入、刪除快；對大數(shù)據(jù)項的存取很快 對現(xiàn)實世界建模

　　缺點

　　刪除和插入慢，大小固定 存取其他項很慢 存取其他項很慢 查找慢 算法復(fù)雜 算法復(fù)雜

　　刪除慢，如果不知道關(guān)鍵字則存儲很慢，對存儲空間使用不充分 對其他數(shù)據(jù)項存取慢 有些算法慢且復(fù)雜

　　插入快；如果知道下標，可以非常快地存取 查找慢，刪除慢，大小固定

　　查找、插入、刪除都快（如果樹保持平衡） 刪除算法復(fù)雜

　　2. 經(jīng)典算法總結(jié)

　　查找算法：線性查找和二分查找 排序算法： 用表展示

　　第一講 數(shù)組

　　1. Java中數(shù)組的基礎(chǔ)知識

　　1）創(chuàng)建數(shù)組

　　在Java中把數(shù)組當(dāng)作對象來對待，因此在創(chuàng)建數(shù)組時必須使用new操作符：

　　一旦創(chuàng)建數(shù)組，數(shù)組大小便不可改變。

　　2）訪問數(shù)組數(shù)據(jù)項

　　數(shù)組數(shù)據(jù)項通過方括號中的下標來訪問，其中第一個數(shù)據(jù)項的下標是0：

　　3）數(shù)組的初始化

　　當(dāng)創(chuàng)建數(shù)組之后，除非將特定的值賦給數(shù)組的數(shù)據(jù)項，否則它們一直是特殊的null對象。

　　2. 面向?qū)ο缶幊谭绞?/strong>

　　1）使用自定義的類封裝數(shù)組

　　2）添加類方法實現(xiàn)數(shù)據(jù)操作

　　測試MyArray類方法：

　　3. 有序數(shù)組

　　1）有序數(shù)組簡介以及其優(yōu)點

　　有序數(shù)組是一種數(shù)組元素按一定的順序排列的數(shù)組，從而方便使用二分查找來查找數(shù)組中特定的元素。有序數(shù)組提高了查詢的效率，但并沒有提高刪除和插入元素的效率。

　　2）構(gòu)建有序數(shù)組

　　將2.1中自定義的類封裝數(shù)組MyArray的方法改為如下：

　　4. 查找算法

　　1）線性查找

　　在查找過程中，將要查找的數(shù)一個一個地與數(shù)組中的數(shù)據(jù)項比較，直到找到要找的數(shù)。在2.1中自定義的類封裝數(shù)組MyArray的queryByValue方法，使用的就是線性查找。

　　2）二分查找

　　二分查找（又稱折半查找），即不斷將有序數(shù)組進行對半分割，每次拿中間位置的數(shù)和要查找的數(shù)進行比較：如果要查找的數(shù)<中間數(shù)，則表明要查的數(shù)在數(shù)組的前半段；如果要查的數(shù)>中間數(shù)，則表明該數(shù)在數(shù)組的后半段；如果要查的數(shù)=中間數(shù)，則返回中間數(shù)。

　　測試該二分查找方法：

　　篇二：數(shù)據(jù)結(jié)構(gòu)面試中常見算法小結(jié)

　　一、二叉樹遍歷思想：

　　1、非遞歸前序遍歷

　　List作棧，top為棧針

　　While循環(huán)

　　當(dāng)前點非空，輸出

　　右子非空，入棧

　　左子非空，入棧

　　棧非空，棧頂為當(dāng)前點，出棧；否則break

　　2、非遞歸中序遍歷

　　List作棧，top為棧針

　　While循環(huán)（但前點非空 或 棧非空）

　　當(dāng)前點非空，入棧，左子為當(dāng)前點；

　　否則，棧頂為當(dāng)前點，出棧；輸出，右子為當(dāng)前點

　　3、非遞歸后序遍歷

　　List1作數(shù)據(jù)棧，list2作標識棧，top為數(shù)據(jù)棧針，tag為標識作判斷用

　　Do循環(huán)

　　While循環(huán)(當(dāng)前點非空)

　　入數(shù)據(jù)棧，標識棧對應(yīng)設(shè)1；左子為當(dāng)前點。（本內(nèi)循環(huán)相當(dāng)于把所有左子入棧）數(shù)據(jù)棧頂為當(dāng)前點，標識棧頂為tag且出棧

　　Tag為1，數(shù)字2進標識棧，右子為當(dāng)前點

　　否則為2，數(shù)據(jù)棧出棧頂，輸出，當(dāng)前點為null；

　　While（當(dāng)前點非空 或 數(shù)據(jù)棧非空）---與do配套

　　二叉樹的各遍歷算法：

　　package com.job.basic;

　　import java.util.*;

　　public class BinaryTree {

　　//遞歸前序遍歷

　　public void rPreOrder(Node root) {

　　if (root != null) System.out.print(root.data);

　　if (root.left != null)rPreOrder(root.left);

　　if (root.right != null) rPreOrder(root.right);

　　}

　　//前序遍歷

　　public void preOrder(Node root) {

　　ArrayListstack = new ArrayList();// 使用ArrayList作為堆棧int top = -1;// 棧指針

　　Node current = roo

　　t;

　　while (true) {

　　if (current != null) System.out.print(current.data);

　　// 右子節(jié)點進棧

　　if (current.right != null) {

　　stack.add(current.right);

　　top++;

　　}

　　// 左子節(jié)點進棧

　　if (current.left != null) {

　　stack.add(current.left);

　　top++;

　　}

　　// 如果棧內(nèi)還有節(jié)點，棧頂節(jié)點出棧

　　if (top > -1) {

　　current = stack.get(top);

　　stack.remove(top--);

　　} else {

　　break;

　　}

　　}

　　}

　　// 遞歸中序遍歷

　　public void rInOrder(Node root) {

　　if (root != null) {

　　if (root.left != null) rInOrder(root.left);

　　System.out.print(root.data);

　　if (root.right != null) rInOrder(root.right);

　　}

　　}

　　// 中序遍歷

　　public void inOrder(Node root) {

　　if (root != null) {

　　ArrayListstack = new ArrayList();

　　int top = -1;

　　Node current = root;

　　while (current != null || top > -1) {

　　// 一直尋找左孩子，將路上節(jié)點都進棧,如果左孩子為null，返回父節(jié)點，再從右孩子找 if (current != null) {

　　stack.add(current);

　　top++;

　　current = current.left;

　　} else {

　　current = stack.get(top);// 取出棧頂節(jié)點，并繼續(xù)遍歷右子樹stack.remove(top--);

　　System.out.print(current.data);

　　current = current.right;

　　}

　　}

　　}

　　}

　　// 遞歸后續(xù)遍歷

　　public void rPostOrder(Node root) {

　　if (root != null) {

　　if (root.left != null) rPostOrder(root.left);

　　if (root.right != null)rPostOrder(root.right);

　　System.out.print(root.data);

　　}

　　}

　　//后序遍歷：可以被遍歷的節(jié)點都要進棧出棧兩次，所以添加第二個棧用來標示進棧次數(shù) public void postOrder(Node root) {

　　if (root != null) {

　　ArrayListstack1 = new ArrayList();

　　ArrayListstack2 = new ArrayList();

　　int top = -1;

　　int tag;

　　Node current = root;

　　do {

　　while (current != null) { //將所有左子節(jié)點進棧

　　stack1.add(current);

　　stack2.add(1);

　　top++;

　　current = current.left;

　　}

　　//取出棧頂節(jié)點，并判斷其標志位

　　current = stack1.get(top);

　　tag = stack2.get(top);

　　stack2.remove(top);

　　if (tag == 1) {

　　// tag為1,表明該節(jié)點第一次進棧，還需要進棧一次，同時修改標志位current = current.right;

　　stack2.add(2);

　　} else {

　　// tag不位0,表明非首次進棧，可以遍歷了。

　　stack1.remove(top);

　　top--;

　　System.out.print(current.data);

　　current = null;

　　}

　　} while (current != null || top != -1);

　　}

　　}

　　}

　　class Node {

　　public int data;

　　} public Node right; public Node(int data) { this.data = data; } public Node(int data, Node le, Node ri) { this.data = data; this.left = le; this.right = ri; }

　　二、排序算法

　　數(shù)據(jù)結(jié)構(gòu)排序算法：

　　package com.job.basic;

　　import java.util.Arrays;

　　public class Sort {

　　public static void main(String[] args) {

　　int[] arrsss = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };System.out.print("1、簡單選擇排序：");

　　simpleSelectSort(arrsss);

　　print(arrsss);

　　int[] arris = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };System.out.print("2、直接插入排序：");

　　Sort(arris);

　　print(arris);

　　int[] arrss = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };System.out.print("3、希爾排序：");

　　shellSort(arrss);

　　print(arrss);

　　int[] arrbs = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };System.out.print("4、冒泡排序：");

　　bubbleSort(arrbs);

　　print(arrbs);

　　int[] arrqs = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };System.out.print("5、快速排序：");

　　quickSort(arrqs, 0, arrqs.length - 1);

　　print(arrqs);

　　int[] arrhs = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };System.out.print("6、堆排序：");

　　heapSort(arrhs);

　　print(arrhs);

　　int[] arrms = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };System.out.print("7、歸并排序：");

　　mergeSort(arrms, 0, arrms.length - 1);

　　int[] arrmjs = { 49, 38, 65, 97, 76, 13, 27, 14, 10 }; System.out.print("8、基數(shù)排序："); jishuSort(arrmjs, 10, 2); print(arrmjs); } public static void print(int[] arr) { for (int i : arr) {System.out.print(i + " "); } System.out.println(); } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // 1、簡單選擇 public static void simpleSelectSort(int[] arr) { int len = arr.length; for (int i = 0; i < len; i++) {int minIndex = i;for (int j = i + 1; j < len; j++) { if (arr[minIndex] > arr[j]) minIndex = j;}if (minIndex != i) swap(arr, minIndex, i); } } // 2、直接插入 public static void Sort(int[] arr) { int len = arr.length; for (int i = 1; i < len; i++) {int j = i - 1, temp = arr[i];for (; j >= 0; j--) { if (arr[j] > temp) { arr[j + 1] = arr[j]; } else { break; }}arr[j + 1] = temp; }

　　篇三：JAVA常用的數(shù)據(jù)結(jié)構(gòu)和算法

　　JAVA基本數(shù)據(jù)結(jié)構(gòu)和排序算法

　　Email: [emailprotected]

　　QQ:448086006

　　1 Java容器類

　　1.1 容器作用和概念

　　1.1.1 數(shù)組

　　數(shù)組是一種容器，以線性序列放置對象和基本類型數(shù)據(jù)，可快速訪問數(shù)組元素，但不靈活，容量必須事先定義好，不能隨著需求的變化而擴容。基于此JAVA中提供容器類。

　　1.1.2 容器的架構(gòu)

　　其層次如下圖，都是從Object派生而來。需要注意的是Set、List、Collcetion和Map都是接口，不是具體的類實現(xiàn)。

　　在Java中提供了Collection和Map接口。其中List和Set繼承了Collection接口；同時用Vector、ArrayList、LinkedList三個類實現(xiàn)List接口，HashSet、TreeSet實現(xiàn)Set接口。直接有HashTable、HashMap、TreeMap實現(xiàn)Map接口。

　　List和set都是放單獨的對象的，map則是方一個名值對，就是通過一個key找到一個value；list存放東西是有序的，set是沒有順序的;list允許重復(fù)存入，set不可以。

　　1.1.3 List接口

　　有序的Collection，此接口用戶可以對列表中每個元素的插入位置進行精確地控制，用戶可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素，并搜索列表中的元素，與Set不同，列表通常允許重復(fù)的元素，更確切地講，列表通常允許滿足e1.equals(e2)的元素對e1和e2，并且如果列表本身允許null元素。其方法主要包括：

　　//添加

　　boolean add(E e);

　　void add(int index, E element);

　　boolean addAll(Collectionc);

　　boolean addAll(int index, Collectionc);

　　//刪除

　　boolean remove(Object o);

　　E remove(int index);

　　boolean removeAll(Collection<> c);

　　//獲取某個元素

　　E get(int index);

　　//獲取某個元素的索引

　　int indexOf(Object o);

　　int lastIndexOf(Object o);

　　//是否相同

　　boolean equals(Object o);

　　//將某個元素指定添加到某個位置

　　E set(int index, E element);

　　//獲取索引范圍之內(nèi)的元素

　　ListsubList(int fromIndex, int toIndex);

　　//迭代器

　　ListIteratorlistIterator();

　　ListIteratorlistIterator(int index);

　　(1) ArrayList

　　底層用數(shù)組實現(xiàn)的List，特點，查詢效率高，增刪效率低，線程不安全。

　　其擴容算法如下：

　　int newCapacity = (oldCapacity * 3)/2 + 1;

　　(2) Vector

　　底層用數(shù)組實現(xiàn)List，其實現(xiàn)方法與ArrayList類似，不同之處在于線程安全。其擴容算法如下： int newCapacity = (capacityIncrement > 0) (oldCapacity+capacityIncrement) : (oldCapacity * 2); capacityIncrement：設(shè)置的擴容步進值。

　　(3) LinkedList

　　底層采用雙向鏈表實現(xiàn)的List，特點，查詢效率低，增刪效率高，線程不安全。鏈表是由若干個稱作節(jié)點的對象組成的一種數(shù)據(jù)結(jié)構(gòu)，每個節(jié)點含有一個數(shù)據(jù)和下一個節(jié)點對象的引用，或含有一個數(shù)據(jù)并含有上一個節(jié)點對象的引用和下一個節(jié)點對象的引用(雙向鏈表)。

　　LinkedList其實內(nèi)部采用一個雙向鏈表，如下圖所示：

　　LinkedList繼承了抽象的序列鏈表類，并實現(xiàn)了List、Queue、Cloneable、Serializable接口，使LinkedList可以像隊列一樣進行操作，同時可以克隆和串化，使其能保存到文件中。