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ù)組 棧 隊(duì)列 鏈表 二叉樹 紅-黑樹 2-3-4樹 哈希表 堆 圖

　　優(yōu)點(diǎn)

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

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

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

　　缺點(diǎn)

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

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

　　插入快；如果知道下標(biāo)，可以非�？斓卮嫒� 查找慢，刪除慢，大小固定

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

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

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

　　第一講 數(shù)組

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

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

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

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

　　2）訪問(wèn)數(shù)組數(shù)據(jù)項(xiàng)

　　數(shù)組數(shù)據(jù)項(xiàng)通過(guò)方括號(hào)中的下標(biāo)來(lái)訪問(wèn)，其中第一個(gè)數(shù)據(jù)項(xiàng)的下標(biāo)是0：

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

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

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

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

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

　　測(cè)試MyArray類方法：

　　3. 有序數(shù)組

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

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

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

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

　　4. 查找算法

　　1）線性查找

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

　　2）二分查找

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

　　測(cè)試該二分查找方法：

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

　　一、二叉樹遍歷思想：

　　1、非遞歸前序遍歷

　　List作棧，top為棧針

　　While循環(huán)

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

　　右子非空，入棧

　　左子非空，入棧

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

　　2、非遞歸中序遍歷

　　List作棧，top為棧針

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

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

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

　　3、非遞歸后序遍歷

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

　　Do循環(huán)

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

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

　　Tag為1，數(shù)字2進(jìn)標(biāo)識(shí)棧，右子為當(dāng)前點(diǎn)

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

　　While（當(dāng)前點(diǎn)非空 或 數(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é)點(diǎn)進(jìn)棧

　　if (current.right != null) {

　　stack.add(current.right);

　　top++;

　　}

　　// 左子節(jié)點(diǎn)進(jìn)棧

　　if (current.left != null) {

　　stack.add(current.left);

　　top++;

　　}

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

　　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é)點(diǎn)都進(jìn)棧,如果左孩子為null，返回父節(jié)點(diǎn)，再?gòu)挠液⒆诱?if (current != null) {

　　stack.add(current);

　　top++;

　　current = current.left;

　　} else {

　　current = stack.get(top);// 取出棧頂節(jié)點(diǎn)，并繼續(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é)點(diǎn)都要進(jìn)棧出棧兩次，所以添加第二個(gè)棧用來(lái)標(biāo)示進(jìn)棧次數(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é)點(diǎn)進(jìn)棧

　　stack1.add(current);

　　stack2.add(1);

　　top++;

　　current = current.left;

　　}

　　//取出棧頂節(jié)點(diǎn)，并判斷其標(biāo)志位

　　current = stack1.get(top);

　　tag = stack2.get(top);

　　stack2.remove(top);

　　if (tag == 1) {

　　// tag為1,表明該節(jié)點(diǎn)第一次進(jìn)棧，還需要進(jìn)棧一次，同時(shí)修改標(biāo)志位current = current.right;

　　stack2.add(2);

　　} else {

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

　　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、簡(jiǎn)單選擇排序：");

　　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、簡(jiǎn)單選擇 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ù)組是一種容器，以線性序列放置對(duì)象和基本類型數(shù)據(jù)，可快速訪問(wèn)數(shù)組元素，但不靈活，容量必須事先定義好，不能隨著需求的變化而擴(kuò)容�；�于此JAVA中提供容器類。

　　1.1.2 容器的架構(gòu)

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

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

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

　　1.1.3 List接口

　　有序的Collection，此接口用戶可以對(duì)列表中每個(gè)元素的插入位置進(jìn)行精確地控制，用戶可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問(wèn)元素，并搜索列表中的元素，與Set不同，列表通常允許重復(fù)的元素，更確切地講，列表通常允許滿足e1.equals(e2)的元素對(duì)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);

　　//獲取某個(gè)元素

　　E get(int index);

　　//獲取某個(gè)元素的索引

　　int indexOf(Object o);

　　int lastIndexOf(Object o);

　　//是否相同

　　boolean equals(Object o);

　　//將某個(gè)元素指定添加到某個(gè)位置

　　E set(int index, E element);

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

　　ListsubList(int fromIndex, int toIndex);

　　//迭代器

　　ListIteratorlistIterator();

　　ListIteratorlistIterator(int index);

　　(1) ArrayList

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

　　其擴(kuò)容算法如下：

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

　　(2) Vector

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

　　(3) LinkedList

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

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

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