目錄
1數(shù)組
2鏈表
3棧和隊(duì)列
4二叉樹(shù)
5堆和堆棧
6散列表
7紅黑樹(shù)
1. 數(shù)組
數(shù)組是一種連續(xù)存儲(chǔ)線性結(jié)構(gòu)供嚎，元素類(lèi)型相同孤页，大小相等医增，數(shù)組是多維的，通過(guò)使用整型索引值來(lái)訪問(wèn)他們的元素裸扶，數(shù)組尺寸不能改變儡蔓。
- 數(shù)組的優(yōu)點(diǎn)：
存取速度快 - 數(shù)組的缺點(diǎn)：
事先必須知道數(shù)組的長(zhǎng)度
插入刪除元素很慢
空間通常是有限制的
需要大塊連續(xù)的內(nèi)存塊
插入刪除元素的效率很低
2. 鏈表
n個(gè)節(jié)點(diǎn)離散分配若锁，彼此通過(guò)指針相連，每個(gè)節(jié)點(diǎn)只有一個(gè)前驅(qū)節(jié)點(diǎn)岁经，每個(gè)節(jié)點(diǎn)只有一個(gè)后續(xù)節(jié)點(diǎn)蔗蹋，首節(jié)點(diǎn)沒(méi)有前驅(qū)節(jié)點(diǎn)何荚，尾節(jié)點(diǎn)沒(méi)有后續(xù)節(jié)點(diǎn)。
確定一個(gè)鏈表我們只需要頭指針猪杭，通過(guò)頭指針就可以把整個(gè)鏈表都能推出來(lái)餐塘。
- 鏈表優(yōu)點(diǎn)
空間沒(méi)有限制
插入刪除元素很快 - 鏈表缺點(diǎn)
存取速度很慢
鏈表又細(xì)分了3類(lèi)：
- 單向鏈表
一個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)。 - 雙向鏈表
一個(gè)節(jié)點(diǎn)有兩個(gè)指針域皂吮。 - 循環(huán)鏈表
能通過(guò)任何一個(gè)節(jié)點(diǎn)找到其他所有的節(jié)點(diǎn)戒傻，將兩種(雙向/單向)鏈表的最后一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)從而實(shí)現(xiàn)循環(huán)税手。
操作鏈表要時(shí)刻記住的是：節(jié)點(diǎn)中指針域指向的就是另一個(gè)節(jié)點(diǎn)！
Java實(shí)現(xiàn)鏈表
首先需纳，我們定義一個(gè)類(lèi)作為節(jié)點(diǎn)芦倒，節(jié)點(diǎn)需要有兩個(gè)屬性：
數(shù)據(jù)域
指針域
public class Node {
//數(shù)據(jù)域
public int data;
//指針域，指向下一個(gè)節(jié)點(diǎn)
public Node next;
public Node() {
}
public Node(int data) {
this.data = data;
}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
如上不翩，一個(gè)鏈表節(jié)點(diǎn)對(duì)象就創(chuàng)建完成了兵扬，但理解鏈表本身并不難，但做相關(guān)的操作卻并非易事口蝠，其算法包括且不限于：
- 插入節(jié)點(diǎn)
- 遍歷
- 查找
- 清空
- 銷(xiāo)毀
- 求長(zhǎng)度
- 排序
- 刪除節(jié)點(diǎn)
- 去重
創(chuàng)建鏈表&增加節(jié)點(diǎn)
創(chuàng)建頭節(jié)點(diǎn)
Node head = new Node(value);
然后找到尾節(jié)點(diǎn)進(jìn)行插入
/**
* 向鏈表添加數(shù)據(jù)
* @param value 要添加的數(shù)據(jù)
* @param head 頭節(jié)點(diǎn)
*/
public static void addData(int value, Node head) {
//初始化要加入的節(jié)點(diǎn)
Node newNode = new Node(value);
//臨時(shí)節(jié)點(diǎn)
Node temp = head;
// 找到尾節(jié)點(diǎn)
while (temp.next != null) {
temp = temp.next;
}
// 已經(jīng)包括了頭節(jié)點(diǎn).next為null的情況了～
temp.next = newNode;
}
遍歷鏈表
上面我們已經(jīng)編寫(xiě)了增加方法器钟，現(xiàn)在遍歷一下，從首節(jié)點(diǎn)開(kāi)始妙蔗，不斷往后面找傲霸，直到后面的節(jié)點(diǎn)沒(méi)有數(shù)據(jù)
/**
* 遍歷鏈表
* @param head 頭節(jié)點(diǎn)
*/
public static void traverse(Node head) {
//臨時(shí)節(jié)點(diǎn)，從首節(jié)點(diǎn)開(kāi)始
Node temp = head.next;
while (temp != null) {
System.out.println("鏈表數(shù)據(jù)：" + temp.data);
//繼續(xù)下一個(gè)
temp = temp.next;
}
}
其他算法略眉反，讀者朋友們可自行練習(xí)昙啄。
3. 棧和隊(duì)列
數(shù)組和鏈表都是線性存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)，棧和隊(duì)列都是線性存儲(chǔ)結(jié)構(gòu)的應(yīng)用寸五。
棧
我們將椄疲可以看成一個(gè)放光盤(pán)的箱子，箱口與略大與光盤(pán)播歼。然后
- 往箱子里面放東西叫做入棧
- 往箱子里面取東西叫做出棧
- 箱子的底部叫做棧底
- 箱子的頂部叫做棧頂
說(shuō)到棧的特性伶跷，有一句經(jīng)典的言語(yǔ)來(lái)概括：先進(jìn)后出，后進(jìn)先出秘狞。
Java實(shí)現(xiàn)棧
- 使用數(shù)組實(shí)現(xiàn)的叫
靜態(tài)棧 - 使用鏈表實(shí)現(xiàn)的叫
動(dòng)態(tài)棧
沿用上一章節(jié)的鏈表對(duì)象Node叭莫，創(chuàng)建一個(gè)棧對(duì)象(棧頂，棧底)：
public class Stack {
// 棧頂
public Node stackTop;
// 棧底
public Node stackBottom;
public Stack(Node stackTop, Node stackBottom) {
this.stackTop = stackTop;
this.stackBottom = stackBottom;
}
public Stack() {
}
}
進(jìn)棧操作
將原本棧頂指向的節(jié)點(diǎn)交由新節(jié)點(diǎn)來(lái)指向烁试，棧頂指向新加入的節(jié)點(diǎn)
/**
* 進(jìn)棧
* @param stack 棧
* @param value 要進(jìn)棧的元素
*/
public static void pushStack(Stack stack, int value) {
// 封裝數(shù)據(jù)成節(jié)點(diǎn)
Node newNode = new Node(value);
// 棧頂本來(lái)指向的節(jié)點(diǎn)交由新節(jié)點(diǎn)來(lái)指向
newNode.next = stack.stackTop;
// 棧頂指針指向新節(jié)點(diǎn)
stack.stackTop = newNode;
}
遍歷棧
只要棧頂元素的指針不指向棧底雇初，那么就一直輸出遍歷結(jié)果
/**
* 遍歷棧
* @param stack
*/
public static void traverse(Stack stack) {
Node stackTop = stack.stackTop;
//棧頂元素的指針不指向棧底，那么就一直輸出遍歷結(jié)果
while (stackTop != stack.stackBottom) {
System.out.println("棧數(shù)據(jù)：" + stackTop.data);
stackTop = stackTop.next;
}
}
出棧操作
在出棧之前看看該棧是否為空减响，不為空才出棧
將棧頂?shù)脑氐闹羔?指向下一個(gè)節(jié)點(diǎn))賦值給棧頂指針(完成出棧)
/**
* 出棧(將棧頂?shù)闹羔樦赶蛳乱粋€(gè)節(jié)點(diǎn))
* @param stack
*/
public static void popStack(Stack stack) {
// 棧不為空才能出棧
if (stack.stackTop != stack.stackBottom) {
//棧頂元素
Node top = stack.stackTop;
// 棧頂指針指向下一個(gè)節(jié)點(diǎn)
stack.stackTop = top.next;
System.out.println("棧數(shù)據(jù)：" + top.data);
}
}
隊(duì)列
隊(duì)列非常好理解靖诗，我們將隊(duì)列可以看成我們平時(shí)排隊(duì)打飯。
- 有新的人加入了 -> 入隊(duì)
- 隊(duì)頭的人打飯了 -> 出隊(duì)
相對(duì)于棧而言支示，隊(duì)列的特性是：先進(jìn)先出刊橘，后進(jìn)后出
- 使用數(shù)組實(shí)現(xiàn)的叫
靜態(tài)隊(duì)列 - 使用鏈表實(shí)現(xiàn)的叫
動(dòng)態(tài)隊(duì)列
這次我就使用數(shù)組來(lái)實(shí)現(xiàn)靜態(tài)隊(duì)列。
[圖片上傳失敗...(image-cefdbb-1540348423645)]
Java實(shí)現(xiàn)隊(duì)列
public class Queue<E> {
private Object[] data=null;
private int maxSize; //隊(duì)列容量
private int front; //隊(duì)列頭颂鸿，允許刪除
private int rear; //隊(duì)列尾促绵，允許插入
//構(gòu)造函數(shù)
public Queue(){
this(5);
}
public Queue(int initialSize){
if(initialSize >=0){
this.maxSize = initialSize;
data = new Object[initialSize];
front = rear =0;
}else{
throw new RuntimeException("初始化大小不能小于0：" + initialSize);
}
}
//判空
public boolean empty(){
return rear==front?true:false;
}
//入隊(duì)
public boolean add(E e){
if(rear== maxSize){
throw new RuntimeException("隊(duì)列已滿，無(wú)法插入新的元素！");
}else{
data[rear++]=e;
return true;
}
}
//出隊(duì)
public E poll(){
if(empty()){
throw new RuntimeException("空隊(duì)列異常败晴！");
}else{
E value = (E) data[front]; //保留隊(duì)列的front端的元素的值
data[front++] = null; //釋放隊(duì)列的front端的元素
return value;
}
}
//隊(duì)列長(zhǎng)度
public int length(){
return rear-front;
}
/**
* 遍歷隊(duì)列
* @param queue
*
*/
public static void traverseQueue(Queue queue) {
// front的位置
int i = queue.front;
while (i != queue.rear) {
System.out.println("隊(duì)列值：" + queue.data[i]);
//移動(dòng)front
i = (i + 1) % queue.data.length;
}
}
}
其他隊(duì)列算法浓冒、循環(huán)隊(duì)列、鏈表結(jié)構(gòu)的隊(duì)列實(shí)現(xiàn)略尖坤，讀者朋友可自行練習(xí)稳懒。
4. 二叉樹(shù)
樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，相對(duì)于線性的數(shù)據(jù)結(jié)構(gòu)(鏈表慢味、數(shù)組)而言僚祷，樹(shù)的平均運(yùn)行時(shí)間更短(往往與樹(shù)相關(guān)的排序時(shí)間復(fù)雜度都不會(huì)高)，
和現(xiàn)實(shí)中的樹(shù)相比贮缕，編程的世界中的樹(shù)一般是“倒”過(guò)來(lái)看，這樣容易我們分析俺榆。
現(xiàn)實(shí)中的樹(shù)是有很多很多個(gè)分支的感昼，分支下又有很多很多個(gè)分支，如果在程序中實(shí)現(xiàn)這個(gè)會(huì)非常麻煩罐脊。因?yàn)楸緛?lái)樹(shù)就是非線性的定嗓，而我們計(jì)算機(jī)的內(nèi)存是線性存儲(chǔ)的，太過(guò)復(fù)雜的話無(wú)法設(shè)計(jì)出來(lái)萍桌。
因此宵溅，就有了簡(jiǎn)單又經(jīng)常用的 -> 二叉樹(shù)，顧名思義上炎，就是每個(gè)分支最多只有兩個(gè)的樹(shù)恃逻，上圖就是二叉樹(shù)。
- 一棵樹(shù)至少會(huì)有一個(gè)節(jié)點(diǎn)(根節(jié)點(diǎn))
-
樹(shù)由節(jié)點(diǎn)組成藕施，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)包括一個(gè)數(shù)據(jù)和兩個(gè)分叉
a空二叉樹(shù), b只有一個(gè)根結(jié)點(diǎn), c只有左子樹(shù), d只有右子樹(shù), e完全二叉樹(shù)
Java實(shí)現(xiàn)二叉樹(shù)
首先寇损，使用Java類(lèi)定義節(jié)點(diǎn)
public class TreeNode {
// 數(shù)據(jù)
private int value;
// 左節(jié)點(diǎn)
private TreeNode leftNode;
// 右節(jié)點(diǎn)
private TreeNode rightNode;
public TreeNode(int value) {
this.value = value;
}
// TODO getter&setter略...
}
我們目標(biāo)是實(shí)現(xiàn)如下圖的樹(shù)
第一步：創(chuàng)建5個(gè)節(jié)點(diǎn)
//根節(jié)點(diǎn)-->10
TreeNode treeNode1 = new TreeNode(10);
//左-->9
TreeNode treeNode2 = new TreeNode(9);
//右-->20
TreeNode treeNode3 = new TreeNode(20);
//20的左-->15
TreeNode treeNode4 = new TreeNode(15);
//20的右-->35
TreeNode treeNode5 = new TreeNode(35);
它們目前的狀態(tài)分散的，需要把這5個(gè)節(jié)點(diǎn)連接起來(lái)
//根節(jié)點(diǎn)的左右節(jié)點(diǎn)
treeNode1.setLefNode(treeNode2);
treeNode1.setRightNode(treeNode3);
//20節(jié)點(diǎn)的左右節(jié)點(diǎn)
treeNode3.setLeftNode(treeNode4);
treeNode3.setRightNode(treeNode5);
遍歷二叉樹(shù)
二叉樹(shù)遍歷有三種方式:
- 中序遍歷
先訪問(wèn)根節(jié)點(diǎn)裳食，然后訪問(wèn)左節(jié)點(diǎn)矛市，最后訪問(wèn)右節(jié)點(diǎn)(根->左->右) - 先序遍歷
先訪問(wèn)左節(jié)點(diǎn)，然后訪問(wèn)根節(jié)點(diǎn)诲祸，最后訪問(wèn)右節(jié)點(diǎn)(左->根->右) - 后序遍歷
先訪問(wèn)左節(jié)點(diǎn)浊吏，然后訪問(wèn)右節(jié)點(diǎn)，最后訪問(wèn)根節(jié)點(diǎn)(左->右->根)
以上面的二叉樹(shù)為例：
如果是中序遍歷：10->9->20->15->35
如果是先序遍歷：9->10->15->20->35
解釋?zhuān)涸L問(wèn)完10節(jié)點(diǎn)過(guò)后救氯，去找的是20節(jié)點(diǎn)找田，但20下還有子節(jié)點(diǎn)，因此先訪問(wèn)的是20的左節(jié)點(diǎn)15節(jié)點(diǎn)着憨。由于15節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)了午阵。所以就返回20節(jié)點(diǎn)，訪問(wèn)20節(jié)點(diǎn)。最后訪問(wèn)35節(jié)點(diǎn)如果是后序遍歷：9->15->35->20->10
解釋?zhuān)合仍L問(wèn)9節(jié)點(diǎn)底桂，隨后應(yīng)該訪問(wèn)的是20節(jié)點(diǎn)植袍，但20下還有子節(jié)點(diǎn)，因此先訪問(wèn)的是20的左節(jié)點(diǎn)15節(jié)點(diǎn)籽懦。由于15節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)了于个。所以就去訪問(wèn)35節(jié)點(diǎn)，由于35節(jié)點(diǎn)也沒(méi)有子節(jié)點(diǎn)了暮顺，所以返回20節(jié)點(diǎn)厅篓，最終返回10節(jié)點(diǎn)
一句話總結(jié)：中序(根->左->右)，先序(左->根->右)捶码，后序(左->右->根)羽氮。如果訪問(wèn)有孩子的節(jié)點(diǎn)，先處理孩子的惫恼，隨后返回
- 每個(gè)節(jié)點(diǎn)的遍歷如果訪問(wèn)有子節(jié)點(diǎn)的節(jié)點(diǎn)档押，先處理子節(jié)點(diǎn)的(邏輯是一樣的)
- 因此遍歷的方法是遞歸
- 遞歸的出口就是：當(dāng)沒(méi)有子節(jié)點(diǎn)了，結(jié)束遍歷
因此祈纯，我們可以寫(xiě)出這樣的中序遍歷代碼：
/**
* 中序遍歷
* @param rootTreeNode 根節(jié)點(diǎn)
*/
public static void inTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//訪問(wèn)根節(jié)點(diǎn)
System.out.println(rootTreeNode.getValue());
//訪問(wèn)左節(jié)點(diǎn)
inTraverseBTree(rootTreeNode.getLeftNode());
//訪問(wèn)右節(jié)點(diǎn)
inTraverseBTree(rootTreeNode.getRightNode());
}
}
先序遍歷和后序遍歷略...
練習(xí)：查找樹(shù)深度令宿、查找最大值、查找樹(shù)節(jié)點(diǎn)數(shù)量腕窥。
這些算法都會(huì)用到了遞歸粒没，讀者朋友練習(xí)這些算法的時(shí)候需要熟練掌握遞歸，遞歸在非線性的數(shù)據(jù)結(jié)構(gòu)中是用得非常多簇爆。
樹(shù)的應(yīng)用也非常廣泛癞松，此篇也只是非常簡(jiǎn)單地說(shuō)明了樹(shù)的數(shù)據(jù)結(jié)構(gòu)。
5. 堆和堆棧
堆內(nèi)存用來(lái)存放由new創(chuàng)建的對(duì)象和數(shù)組入蛆。
在堆中分配的內(nèi)存拦惋，由Java虛擬機(jī)的自動(dòng)垃圾回收器來(lái)管理。
'堆棧' 就是 '棧'安寺，稱(chēng)呼不同而已厕妖。
棧的優(yōu)勢(shì)是，存取速度比堆要快挑庶，僅次于直接位于CPU中的寄存器言秸。但缺點(diǎn)是，存在棧中的數(shù)據(jù)大小與生存期必須是確定的迎捺，缺乏靈活性举畸。另外，棧數(shù)據(jù)可以共享凳枝。
堆的優(yōu)勢(shì)是可以動(dòng)態(tài)地分配內(nèi)存大小抄沮，生存期也不必事先告訴編譯器跋核，Java的垃圾收集器會(huì)自動(dòng)收走這些不再使用的數(shù)據(jù)。但缺點(diǎn)是叛买，由于要在運(yùn)行時(shí)動(dòng)態(tài)分配內(nèi)存砂代，存取速度較慢。
6. 散列表
無(wú)論是Set還是Map率挣，我們會(huì)發(fā)現(xiàn)都會(huì)有對(duì)應(yīng)的-->HashSet,HashMap
首先我們也先得回顧一下數(shù)據(jù)和鏈表：
鏈表和數(shù)組都可以按照人們的意愿來(lái)排列元素的次序刻伊，他們可以說(shuō)是有序的(存儲(chǔ)的順序和取出的順序是一致的)
這會(huì)帶來(lái)缺點(diǎn)：想要獲取某個(gè)元素，就要訪問(wèn)所有的元素椒功，直到找到為止捶箱，會(huì)消耗很多時(shí)間。
所以我們需要另外的存儲(chǔ)結(jié)構(gòu)：不在意元素順序动漾，能快速查找元素丁屎。其中就有一種常見(jiàn)方式：散列表。
散列表工作原理
散列表為每個(gè)對(duì)象計(jì)算出一個(gè)整數(shù)旱眯，稱(chēng)為散列碼晨川。根據(jù)這些計(jì)算出來(lái)的整數(shù)(散列碼)保存在對(duì)應(yīng)的位置上！即键思，散列碼就是索引。
在Java中甫贯，散列表用的是鏈表數(shù)組實(shí)現(xiàn)的吼鳞，每個(gè)列表稱(chēng)之為桶。
7. 紅黑樹(shù)
是一種平衡二叉樹(shù)叫搁，TreeSet赔桌、TreeMap底層都是紅黑樹(shù)來(lái)實(shí)現(xiàn)的。
二叉查找樹(shù)也有個(gè)例(最壞)的情況(線性)：
上面符合二叉樹(shù)的特性渴逻，但是它是線性的疾党，完全沒(méi)樹(shù)的用處，樹(shù)是要“均衡”才能將它的優(yōu)點(diǎn)展示出來(lái)惨奕，比如下面這種:
因此雪位，就有了平衡樹(shù)這么一個(gè)概念~紅黑樹(shù)就是一種平衡樹(shù)，它可以保證二叉樹(shù)基本符合均衡的金字塔結(jié)構(gòu)梨撞。
上圖就是一個(gè)紅黑樹(shù)雹洗，紅黑樹(shù)就字面上的意思，有紅色的節(jié)點(diǎn)卧波，有黑色的節(jié)點(diǎn)时肿。
- 性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色。
- 性質(zhì)2. 根節(jié)點(diǎn)是黑色港粱。
- 性質(zhì)3. 每個(gè)葉節(jié)點(diǎn)（NIL節(jié)點(diǎn)螃成，空節(jié)點(diǎn)）是黑色的。
- 性質(zhì)4. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
- 性質(zhì)5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)寸宏。
紅黑樹(shù)可以說(shuō)是十分復(fù)雜宁炫，這里只介紹個(gè)概念，有興趣的朋友可自行研究击吱。
