篇一：Java資料結構和演算法筆記
Java資料結構和演算法
第0講 綜述
參考教材：Java資料結構和演算法（第二版），[美] Robert lafore
1. 資料結構的特性
資料結構 陣列 有序陣列 棧 佇列 連結串列 二叉樹 紅-黑樹 2-3-4樹 雜湊表 堆 圖
優點
比無序的陣列查詢快 提供後進先出方式的存取 提供先進先出方式的存取 插入快，刪除快
查詢、插入、刪除都快；樹總是平衡的 查詢、插入、刪除都快；樹總是平衡的；類似的樹對磁碟儲存有用
如果關鍵字已知，則儲存極快；插入快 插入、刪除快；對大資料項的存取很快 對現實世界建模
缺點
刪除和插入慢，大小固定 存取其他項很慢 存取其他項很慢 查詢慢 演算法複雜 演算法複雜
刪除慢，如果不知道關鍵字則儲存很慢，對儲存空間使用不充分 對其他資料項存取慢 有些演算法慢且複雜
插入快；如果知道下標，可以非常快地存取 查詢慢，刪除慢，大小固定
查詢、插入、刪除都快（如果樹保持平衡） 刪除演算法複雜
2. 經典演算法總結
查詢演算法：線性查詢和二分查詢 排序演算法： 用表展示
第一講 陣列
1. Java中陣列的基礎知識
1）建立陣列
在Java中把陣列當作物件來對待，因此在建立陣列時必須使用new操作符：
一旦建立陣列，陣列大小便不可改變。
2）訪問陣列資料項
陣列資料項通過方括號中的下標來訪問，其中第一個資料項的下標是0：
3）陣列的初始化
當建立陣列之後，除非將特定的值賦給陣列的資料項，否則它們一直是特殊的null物件。
2. 面向物件程式設計方式
1）使用自定義的類封裝陣列
2）新增類方法實現資料操作
測試MyArray類方法：
3. 有序陣列
1）有序陣列簡介以及其優點
有序陣列是一種陣列元素按一定的順序排列的陣列，從而方便使用二分查詢來查詢陣列中特定的元素。有序陣列提高了查詢的效率，但並沒有提高刪除和插入元素的效率。
2）構建有序陣列
將2.1中自定義的類封裝陣列MyArray的方法改為如下：
4. 查詢演算法
1）線性查詢
在查詢過程中，將要查詢的數一個一個地與陣列中的資料項比較，直到找到要找的數。在2.1中自定義的類封裝陣列MyArray的queryByValue方法，使用的就是線性查詢。
2）二分查詢
二分查詢（又稱折半查詢），即不斷將有序陣列進行對半分割，每次拿中間位置的數和要查詢的數進行比較：如果要查詢的數<中間數，則表明要查的數在陣列的`前半段；如果要查的數>中間數，則表明該數在陣列的後半段；如果要查的數=中間數，則返回中間數。
測試該二分查詢方法：
篇二：資料結構面試中常見演算法小結
一、二叉樹遍歷思想：
1、非遞迴前序遍歷
List作棧，top為棧針
While迴圈
當前點非空，輸出
右子非空，入棧
左子非空，入棧
棧非空，棧頂為當前點，出棧；否則break
2、非遞迴中序遍歷
List作棧，top為棧針
While迴圈（但前點非空 或 棧非空）
當前點非空，入棧，左子為當前點；
否則，棧頂為當前點，出棧；輸出，右子為當前點
3、非遞迴後序遍歷
List1作資料棧，list2作標識棧，top為資料棧針，tag為標識作判斷用
Do迴圈
While迴圈(當前點非空)
入資料棧，標識棧對應設1；左子為當前點。（本內迴圈相當於把所有左子入棧）資料棧頂為當前點，標識棧頂為tag且出棧
Tag為1，數字2進標識棧，右子為當前點
否則為2，資料棧出棧頂，輸出，當前點為null；
While（當前點非空 或 資料棧非空）---與do配套
二叉樹的各遍歷演算法：
package c;
import .*;
public class BinaryTree {
//遞迴前序遍歷
public void rPreOrder(Node root) {
if (root != null) t();
if ( != null)rPreOrder();
if (t != null) rPreOrder(t);
}
//前序遍歷
public void preOrder(Node root) {
ArrayListstack = new ArrayList();// 使用ArrayList作為堆疊int top = -1;// 棧指標
Node current = roo
t;
while (true) {
if (current != null) t();
// 右子節點進棧
if (t != null) {
(t);
top++;
}
// 左子節點進棧
if ( != null) {
();
top++;
}
// 如果棧內還有節點，棧頂節點出棧
if (top > -1) {
current = (top);
ve(top--);
} else {
break;
}
}
}
// 遞迴中序遍歷
public void rInOrder(Node root) {
if (root != null) {
if ( != null) rInOrder();
t();
if (t != null) rInOrder(t);
}
}
// 中序遍歷
public void inOrder(Node root) {
if (root != null) {
ArrayListstack = new ArrayList();
int top = -1;
Node current = root;
while (current != null || top > -1) {
// 一直尋找左孩子，將路上節點都進棧,如果左孩子為null，返回父節點，再從右孩子找 if (current != null) {
(current);
top++;
current = ;
} else {
current = (top);// 取出棧頂節點，並繼續遍歷右子樹ve(top--);
t();
current = t;
}
}
}
}
// 遞迴後續遍歷
public void rPostOrder(Node root) {
if (root != null) {
if ( != null) rPostOrder();
if (t != null)rPostOrder(t);
t();
}
}
//後序遍歷：可以被遍歷的節點都要進棧出棧兩次，所以新增第二個棧用來標示進棧次數 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) { //將所有左子節點進棧
(current);
(1);
top++;
current = ;
}
//取出棧頂節點，並判斷其標誌位
current = (top);
tag = (top);
ve(top);
if (tag == 1) {
// tag為1,表明該節點第一次進棧，還需要進棧一次，同時修改標誌位current = t;
(2);
} else {
// tag不位0,表明非首次進棧，可以遍歷了。
ve(top);
top--;
t();
current = null;
}
} while (current != null || top != -1);
}
}
}
class Node {
public int data;
} public Node right; public Node(int data) { = data; } public Node(int data, Node le, Node ri) { = data; = le; t = ri; }
二、排序演算法
資料結構排序演算法：
package c;
import ys;
public class Sort {
public static void main(String[] args) {
int[] arrsss = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };t("1、簡單選擇排序：");
simpleSelectSort(arrsss);
print(arrsss);
int[] arris = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };t("2、直接插入排序：");
Sort(arris);
print(arris);
int[] arrss = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };t("3、希爾排序：");
shellSort(arrss);
print(arrss);
int[] arrbs = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };t("4、氣泡排序：");
bubbleSort(arrbs);
print(arrbs);
int[] arrqs = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };t("5、快速排序：");
quickSort(arrqs, 0, th - 1);
print(arrqs);
int[] arrhs = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };t("6、堆排序：");
heapSort(arrhs);
print(arrhs);
int[] arrms = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };t("7、歸併排序：");
mergeSort(arrms, 0, th - 1);
int[] arrmjs = { 49, 38, 65, 97, 76, 13, 27, 14, 10 }; t("8、基數排序："); jishuSort(arrmjs, 10, 2); print(arrmjs); } public static void print(int[] arr) { for (int i : arr) {t(i + " "); } tln(); } 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 = th; 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 = th; 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常用的資料結構和演算法
JAVA基本資料結構和排序演算法
Email: [emailprotected]
QQ:448086006
1 Java容器類
1.1 容器作用和概念
1.1.1 陣列
陣列是一種容器，以線性序列放置物件和基本型別資料，可快速訪問陣列元素，但不靈活，容量必須事先定義好，不能隨著需求的變化而擴容。基於此JAVA中提供容器類。
1.1.2 容器的架構
其層次如下圖，都是從Object派生而來。需要注意的是Set、List、Collcetion和Map都是介面，不是具體的類實現。
在Java中提供了Collection和Map介面。其中List和Set繼承了Collection介面；同時用Vector、ArrayList、LinkedList三個類實現List介面，HashSet、TreeSet實現Set介面。直接有HashTable、HashMap、TreeMap實現Map介面。
List和set都是放單獨的物件的，map則是方一個名值對，就是通過一個key找到一個value；list存放東西是有序的，set是沒有順序的;list允許重複存入，set不可以。
1.1.3 List介面
有序的Collection，此介面使用者可以對列表中每個元素的插入位置進行精確地控制，使用者可以根據元素的整數索引（在列表中的位置）訪問元素，並搜尋列表中的元素，與Set不同，列表通常允許重複的元素，更確切地講，列表通常允許滿足ls(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);
//獲取索引範圍之內的元素
ListsubList(int fromIndex, int toIndex);
//迭代器
ListIteratorlistIterator();
ListIteratorlistIterator(int index);
(1) ArrayList
底層用陣列實現的List，特點，查詢效率高，增刪效率低，執行緒不安全。
其擴容演算法如下：
int newCapacity = (oldCapacity * 3)/2 + 1;
(2) Vector
底層用陣列實現List，其實現方法與ArrayList類似，不同之處在於執行緒安全。其擴容演算法如下： int newCapacity = (capacityIncrement > 0) (oldCapacity+capacityIncrement) : (oldCapacity * 2); capacityIncrement：設定的擴容步進值。
(3) LinkedList
底層採用雙向連結串列實現的List，特點，查詢效率低，增刪效率高，執行緒不安全。連結串列是由若干個稱作節點的物件組成的一種資料結構，每個節點含有一個數據和下一個節點物件的引用，或含有一個數據並含有上一個節點物件的引用和下一個節點物件的引用(雙向連結串列)。
LinkedList其實內部採用一個雙向連結串列，如下圖所示：
LinkedList繼承了抽象的序列連結串列類，並實現了List、Queue、Cloneable、Serializable介面，使LinkedList可以像佇列一樣進行操作，同時可以克隆和串化，使其能儲存到檔案中。
