本文格式為Word版，下載可任意編輯——Java數(shù)據(jù)結(jié)構(gòu)和算法筆記Java數(shù)據(jù)布局和算法筆記

篇一：Java數(shù)據(jù)布局和算法筆記

Java數(shù)據(jù)布局和算法

第0講綜述

參考教材：Java數(shù)據(jù)布局和算法（其次版），[美]Robertlafore

1.數(shù)據(jù)布局的特性

數(shù)據(jù)布局數(shù)組有序數(shù)組棧隊列鏈表二叉樹紅-黑樹2-3-4樹哈希表堆圖

優(yōu)點

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

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

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

缺點

刪除和插入慢，大小固定存取其他項很慢存取其他項很慢查找慢算法繁雜算法繁雜

刪除慢，假設(shè)不知道關(guān)鍵字那么存儲很慢，對存儲空間使用不充分對其他數(shù)據(jù)項存取慢有些算法慢且繁雜

插入快；假設(shè)知道下標，可以分外快地存取查找慢，刪除慢，大小固定

查找、插入、刪除都快（假設(shè)樹保持平衡）刪除算法繁雜

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

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

第一講數(shù)組

1.Java中數(shù)組的根基學(xué)識

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

在Java中把數(shù)組當(dāng)作對象來對待，因此在創(chuàng)造數(shù)組時務(wù)必使用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ū)ο缶幊谭绞?/p>

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

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

測試MyArray類方法：

3.有序數(shù)組

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

有序數(shù)組是一種數(shù)組元素按確定的依次排列的數(shù)組，從而便當(dāng)使用二分查找來查找數(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ù)=中間數(shù)，那么返回中間數(shù)。

測試該二分查找方法：

篇二：數(shù)據(jù)布局面試中常見算法小結(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配套

二叉樹的各遍歷算法：

packagecom.job.basic;

importjava.util.*;

publicclassBinaryTree

//遞歸前序遍歷

publicvoidrPreOrderNoderoot

ifroot!=nullSystem.out.printroot.data;

ifroot.left!=nullrPreOrderroot.left;

ifroot.right!=nullrPreOrderroot.right;

//前序遍歷

publicvoidpreOrderNoderoot

ArrayListstack=newArrayList;//使用ArrayList作為堆棧inttop=-1;//棧指針

Nodecurrent=roo

t;

whiletrue

ifcurrent!=nullSystem.out.printcurrent.data;

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

ifcurrent.right!=null

stack.addcurrent.right;

top++;

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

ifcurrent.left!=null

stack.addcurrent.left;

top++;

//假設(shè)棧內(nèi)還有節(jié)點，棧頂節(jié)點出棧

iftop-1

current=stack.gettop;

stack.removetop--;

else

break;

//遞歸中序遍歷

publicvoidrInOrderNoderoot

ifroot!=null

ifroot.left!=nullrInOrderroot.left;

System.out.printroot.data;

ifroot.right!=nullrInOrderroot.right;

//中序遍歷

publicvoidinOrderNoderoot

ifroot!=null

ArrayListstack=newArrayList;

inttop=-1;

Nodecurrent=root;

whilecurrent!=null||top-1

//一向探索左孩子，將路上節(jié)點都進棧,假設(shè)左孩子為null，返回父節(jié)點，再從右孩子找ifcurrent!=null

stack.addcurrent;

top++;

current=current.left;

else

current=stack.gettop;//取出棧頂節(jié)點，并持續(xù)遍歷右子樹stack.removetop--;

System.out.printcurrent.data;

current=current.right;

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

publicvoidrPostOrderNoderoot

ifroot!=null

ifroot.left!=nullrPostOrderroot.left;

ifroot.right!=nullrPostOrderroot.right;

System.out.printroot.data;

//后序遍歷：可以被遍歷的節(jié)點都要進棧出棧兩次，所以添加其次個棧用來標示進棧次數(shù)publicvoidpostOrderNoderoot

ifroot!=null

ArrayListstack1=newArrayList;

ArrayListstack2=newArrayList;

inttop=-1;

inttag;

Nodecurrent=root;

do

whilecurrent!=null//將全體左子節(jié)點進棧

stack1.addcurrent;

stack2.add1;

top++;

current=current.left;

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

current=stack1.gettop;

tag=stack2.gettop;

stack2.removetop;

iftag==1

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

stack2.add2;

else

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

stack1.removetop;

top--;

System.out.printcurrent.data;

current=null;

whilecurrent!=null||top!=-1;

classNode

publicintdata;

publicNoderight;publicNodeintdatathis.data=data;publicNodeintdata,Nodele,Noderithis.data=data;this.left=le;this.right=ri;

二、排序算法

數(shù)據(jù)布局排序算法：

packagecom.job.basic;

importjava.util.Arrays;

publicclassSort

publicstaticvoidmainString[]args

int[]arrsss=49,38,65,97,76,13,27,14,10;System.out.print1、簡樸選擇排序：;

simpleSelectSortarrsss;

printarrsss;

int[]arris=49,38,65,97,76,13,27,14,10;System.out.print2、直接插入排序：;

Sortarris;

printarris;

int[]arrss=49,38,65,97,76,13,27,14,10;System.out.print3、希爾排序：;

shellSortarrss;

printarrss;

int[]arrbs=49,38,65,97,76,13,27,14,10;System.out.print4、冒泡排序：;

bubbleSortarrbs;

printarrbs;

int[]arrqs=49,38,65,97,76,13,27,14,10;System.out.print5、快速排序：;

quickSortarrqs,0,arrqs.length-1;

printarrqs;

int[]arrhs=49,38,65,97,76,13,27,14,10;System.out.print6、堆排序：;

heapSortarrhs;

printarrhs;

int[]arrms=49,38,65,97,76,13,27,14,10;System.out.print7、歸并排序：;

mergeSortarrms,0,arrms.length-1;

int[]arrmjs=49,38,65,97,76,13,27,14,10;System.out.print8、基數(shù)排序：;jishuSortarrmjs,10,2;printarrmjs;publicstaticvoidprintint[]arrforinti:arrSystem.out.printi+;System.out.println;publicstaticvoidswapint[]arr,inti,intjinttemp=arr[i];arr[i]=arr[j];arr[j]=temp;//1、簡樸選擇publicstaticvoidsimpleSelectSortint[]arrintlen=arr.length;forinti=0;ilen;i++intminIndex=i;forintj=i+1;jlen;j++ifarr[minIndex]arr[j]minIndex=j;ifminIndex!=iswaparr,minIndex,i;//2、直接插入publicstaticvoidSortint[]arrintlen=arr.length;forinti=1;ilen;i++intj=i-1,temp=arr[i];for;j=0;j--ifarr[j]temparr[j+1]=arr[j];elsebreak;arr[j+1]=temp;

篇三：JAVA常用的數(shù)據(jù)布局和算法

JAVA根本數(shù)據(jù)布局和排序算法

Email:[emailprotected]

:448086006

1Java容器類

1.1容器作用和概念

1.1.1數(shù)組

數(shù)組是一種容器，以線性序列放置對象和根本類型數(shù)據(jù)，可快速訪問數(shù)組元素，但不生動，容量務(wù)必事先定義好，不能隨著需求的變化而擴容。基于此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.3List接口

有序的Collection，此接口用戶可以對列表中每個元素的插入位置舉行精確地操縱，用戶可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素，并探尋列表中的元素，與Set不同，列表通常允許重復(fù)的元素，更切當(dāng)?shù)刂v，列表通常允許得志e1.equalse2的元素對e1和e2，并且假設(shè)列表本身允許null元素。其方法主要包括：

//添加

booleanaddEe;

voidaddintindex,Eelement;

booleanaddAllCollectionc;

booleanaddAllintindex,Collectionc;

//刪除

booleanremoveObjecto;

Eremoveintindex;

booleanremoveAllCollectionc;

//獲取某個元素

Egetintindex;

//獲取某個元素的索引

intindexOfObjecto;

intlastIndexOfObjecto;

//是否一致

bool