Java數據結構和算法筆記

篇一：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可以像隊列一樣進行操作，同時可以克隆和串化，使其能保存到文件中。