在編程過程中，通常會遇到的一個問題就是，性能瓶頸。很多時候考慮的都是怎么去做橫向擴展，但偏偏忽略掉了最基本的問題就是系統(tǒng)是否真的已經(jīng)達到了瓶頸？
性能瓶頸通常的表象是資源消耗過多外部處理系統(tǒng)的性能不足；或者資源消耗不多但程序的響應(yīng)速度卻仍達不到要求。
而調(diào)優(yōu)的方式就是 尋找過度消耗資源的代碼 和 尋找未充分使用資源但程序執(zhí)行慢的原因和代碼。很多人覺得基本的數(shù)據(jù)結(jié)構(gòu)及操作已經(jīng)在高級語言中封裝,都可以直接調(diào)用庫函數(shù)，那么到底有沒有必要好好學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？
所謂算法是指在有限步驟內(nèi)求解某類問題所使用的一組定義明確的規(guī)則。算法重在用一個統(tǒng)一的方法有步驟地解決一類問題，但它不是唯一的，一個好的算法應(yīng)該用較少的便于實現(xiàn)的步驟去有效的解決問題。
一、 數(shù)據(jù)結(jié)構(gòu)簡介?
1 什么是數(shù)據(jù)結(jié)構(gòu)
簡單地說，數(shù)據(jù)結(jié)構(gòu)是以某種特定的布局方式存儲數(shù)據(jù)的容器。這種“布局方式”決定了 數(shù)據(jù)結(jié)構(gòu)對于某些操作是高效的，而對于其他操作則是低效的。所以我們需要理解各種數(shù)據(jù) 結(jié)構(gòu)，才能在處理實際問題時選取最合適的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)=邏輯結(jié)構(gòu)+物理結(jié)構(gòu)（順序、鏈?zhǔn)?、索引、散列?邏輯結(jié)構(gòu)：數(shù)據(jù)元素間抽象化的相互關(guān)系 物理結(jié)構(gòu)：（存儲結(jié)構(gòu)），在計算機存儲器中的存儲形式?
2 數(shù)據(jù)結(jié)構(gòu)邏輯分類
數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：
2.1線性結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)中的元素存在一對一的相互關(guān)系；
常見的線性結(jié)構(gòu)： 線性表，棧，隊列，串(一維數(shù)組)等。
2.2樹形結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)中的元素存在一對多的相互關(guān)系；
常見樹形結(jié)構(gòu)： 二叉樹，紅黑樹，B 樹，哈夫曼樹等。
2.3圖形結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)中的元素存在多對多的相互關(guān)系；
常見圖形結(jié)構(gòu)： 有向圖，無向圖，簡單圖等。
二、 線性結(jié)構(gòu)
1 棧結(jié)構(gòu)?
1.1棧的定義
棧是一種只能從一端存取數(shù)據(jù)且遵循 "后進先出(LIFO)" 原則的線性存儲結(jié)構(gòu)。?
1.2實現(xiàn)棧容器?
1.2.1 創(chuàng)建棧容器類
2 鏈表結(jié)構(gòu)?
2.1鏈表結(jié)構(gòu)的定義?
2.1.1 什么是鏈表?
鏈表結(jié)構(gòu)是由許多節(jié)點構(gòu)成的，每個節(jié)點都包含兩部分：
? 數(shù)據(jù)部分：保存該節(jié)點的實際數(shù)據(jù)。?
? 地址部分：保存的是上一個或下一個節(jié)點的地址。
2.1.2 鏈表分類
? 單向鏈表?
? 雙向鏈表?
? 雙向循環(huán)鏈表?
2.1.3 鏈表的特點?
? 結(jié)點在存儲器中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。?
? 訪問時只能通過頭或者尾指針進入鏈表，并通過每個結(jié)點的指針域向后或向前掃描 其余結(jié)點，所以尋找第一個結(jié)點和最后一個結(jié)點所花費的時間不等。 鏈表的優(yōu)缺點：?
? 優(yōu)點：數(shù)據(jù)元素的個數(shù)可以自由擴充 、插入、刪除等操作不必移動數(shù)據(jù)，只需修 改鏈接指針，修改效率較高。
? 缺點：必須采用順序存取，即存取數(shù)據(jù)元素時，只能按鏈表的順序進行訪問，訪問 節(jié)點效率較低。?
2.2單向鏈表結(jié)構(gòu)?
2.2.1 單向鏈表定義?
單向鏈表（單鏈表）是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問 要通過從頭部開始順序讀取。
2.3雙向鏈表結(jié)構(gòu)
2.3.1 雙向鏈表定義?
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直 接前驅(qū)和直接后繼
2.3.2 實現(xiàn)雙向鏈表
2.3.2.1 創(chuàng)建雙向鏈表類
三、 樹形結(jié)構(gòu)
1 樹形結(jié)構(gòu)簡介?
樹結(jié)構(gòu)是一種非線性存儲結(jié)構(gòu)，存儲的是具有“一對多”關(guān)系的數(shù)據(jù)元素的集合
2 樹的相關(guān)術(shù)語?
2.1結(jié)點(Node) 使用樹結(jié)構(gòu)存儲的每一個數(shù)據(jù)元素都被稱為“結(jié)點”。?
2.2結(jié)點的度(Degree of Node) 某個結(jié)點所擁有的子樹的個數(shù)。
2.3樹的深度(Degree of Tree) 樹中結(jié)點的最大層次數(shù)。?
2.4葉子結(jié)點(Leaf Node) 度為 0 的結(jié)點，也叫終端結(jié)點。?
2.5分支結(jié)點(Branch Node) 度不為 0 的結(jié)點，也叫非終端結(jié)點或內(nèi)部結(jié)點。?
2.6孩子(Child) 也可稱之為子樹或者子結(jié)點，表示當(dāng)前結(jié)點下層的直接結(jié)點。?
2.7雙親(Parent) 也可稱之為父結(jié)點，表示當(dāng)前結(jié)點的直接上層結(jié)點。?
2.8根節(jié)點(Root Node) 沒有雙親結(jié)點的結(jié)點。在一個樹形結(jié)構(gòu)中只有一個根節(jié)點。 2.9祖先(Ancestor) 從當(dāng)前結(jié)點上層的所有結(jié)點。?
2.10子孫(Descendant) 當(dāng)前結(jié)點下層的所有結(jié)點。
2.11兄弟(Brother) 同一雙親的孩子。
3?二叉樹簡介
二叉樹（Binary Tree）是樹形結(jié)構(gòu)的一個重要類型。許多實際問題抽象出來的數(shù)據(jù)結(jié)構(gòu) 往往是二叉樹形式，即使是一般的樹也能簡單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲結(jié)構(gòu)及其 算法都較為簡單，因此二叉樹顯得特別重要。二叉樹特點是每個結(jié)點最多只能有兩棵子樹， 且有左右之分。?
3.1二叉樹分類?
3.1.1 滿二叉樹 滿二叉樹指除最后一層外，每一層上的所有節(jié)點都有兩個子節(jié)點。
3.1.2 完全二叉樹
完全二叉樹，除最后一層可能不滿以外，其他各層都達到該層節(jié)點的最大數(shù)，最后一層 如果不滿，該層所有節(jié)點都全部靠左排。
3.2二叉樹遍歷?
二叉樹遍歷的方式：?
? 前序遍歷：根-左-右?
? 中序遍歷：左-根-右?
??后序遍歷：左-右-根
? 層序遍歷：從上至下逐層遍歷
3.2.1 前序遍歷
前序遍歷順序：根-左-右
3.2.2 中序遍歷
中序遍歷順序：左-根-右
3.2.3 后序遍歷
后序遍歷順序：左-右-根
3.2.4 層序遍歷
層序遍歷順序：?從根節(jié)點出發(fā)，依次訪問左右孩子結(jié)點，再從左右孩子出發(fā)，依次它們的孩子結(jié)點，直 到節(jié)點訪問完畢。
3.3二叉樹排序?
3.3.1 二叉樹排序分析
利用二叉樹結(jié)構(gòu)以及遍歷方式可以實現(xiàn)基于二叉樹的元素排序處理。
3.3.2 二叉樹排序?qū)崿F(xiàn)
3.3.2.1 創(chuàng)建二叉樹排序器類
4 自定義樹形結(jié)構(gòu)容器
4.1樹形結(jié)構(gòu)定義
能夠找到當(dāng)前結(jié)點的父結(jié)點
能夠找到當(dāng)前結(jié)點的子結(jié)點
能夠找到當(dāng)前結(jié)點的兄弟結(jié)點
能夠找到當(dāng)前結(jié)點的祖先結(jié)點
能夠找到當(dāng)前結(jié)點的子孫節(jié)點
