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

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

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

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

　　查找、插入、刪除都快；樹(shù)總是平衡的 查找、插入、刪除都快；樹(shù)總是平衡的；類似的樹(shù)對(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)，可以非常快地存取 查找慢，刪除慢，大小固定

　　查找、插入、刪除都快（如果樹(shù)保持平衡） 刪除算法復(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ù)組提高了查詢的效率，但并沒(méi)有提高刪除和插入元素的效率。

　　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àn)算法小結(jié)

　　一、二叉樹(shù)遍歷思想：

　　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配套

　　二叉樹(shù)的各遍歷算法：

　　package com.job.basic;

　　import java.util.*;

　　public class BinaryTree {

　　/pic/p>

　　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);

　　}

　　/pic/p>

　　public void preOrder(Node root) {

　　ArrayListstack = new ArrayList();/pic/pic/p>

　　Node current = roo

　　t;

　　while (true) {

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

　　/pic/p>

　　if (current.right != null) {

　　stack.add(current.right);

　　top++;

　　}

　　/pic/p>

　　if (current.left != null) {

　　stack.add(current.left);

　　top++;

　　}

　　/pic/p>

　　if (top > -1) {

　　current = stack.get(top);

　　stack.remove(top--);

　　} else {

　　break;

　　}

　　}

　　}

　　/pic/p>

　　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);

　　}

　　}

　　/pic/p>

　　public void inOrder(Node root) {

　　if (root != null) {

　　ArrayListstack = new ArrayList();

　　int top = -1;

　　Node current = root;

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

　　/pic/p>

　　stack.add(current);

　　top++;

　　current = current.left;

　　} else {

　　current = stack.get(top);/pic/p>

　　System.out.print(current.data);

　　current = current.right;

　　}

　　}

　　}

　　}

　　/pic/p>

　　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);

　　}

　　}

　　/pic/p>

　　if (root != null) {

　　ArrayListstack1 = new ArrayList();

　　ArrayListstack2 = new ArrayList();

　　int top = -1;

　　int tag;

　　Node current = root;

　　do {

　　while (current != null) { /pic/p>

　　stack1.add(current);

　　stack2.add(1);

　　top++;

　　current = current.left;

　　}

　　/pic/p>

　　current = stack1.get(top);

　　tag = stack2.get(top);

　　stack2.remove(top);

　　if (tag == 1) {

　　/pic/p>

　　stack2.add(2);

　　} else {

　　/pic/p>

　　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; } /pic/pic/p>

　　篇三：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是沒(méi)有順序的;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元素。其方法主要包括：

　　/pic/p>

　　boolean add(E e);

　　void add(int index, E element);

　　boolean addAll(Collectionc);

　　boolean addAll(int index, Collectionc);

　　/pic/p>

　　boolean remove(Object o);

　　E remove(int index);

　　boolean removeAll(Collection<> c);

　　/pic/p>

　　E get(int index);

　　/pic/p>

　　int indexOf(Object o);

　　int lastIndexOf(Object o);

　　/pic/p>

　　boolean equals(Object o);

　　/pic/p>

　　E set(int index, E element);

　　/pic/p>

　　ListsubList(int fromIndex, int toIndex);

　　/pic/p>

　　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í)可以克隆和串化，使其能保存到文件中。