數(shù)據(jù)結構
定義
我們如何把現(xiàn)實中大量而復雜的問題以特定的數(shù)據(jù)類型和特定的存儲結構保存到主存儲器（內存）中章姓，以及在此基礎上為實現(xiàn)某個功能（比如查找某個元素稍味，刪除某個元素，所對應元素進行排序）而執(zhí)行的相應操作，這個相應的操作也叫算法豫领。
數(shù)據(jù)結構是專門研究數(shù)據(jù)存儲的問題矩屁。
數(shù)據(jù)的存儲包含兩方面：個體的存儲和個體關系的存儲辟宗。
算法是對存儲數(shù)據(jù)的操作。
- 數(shù)據(jù)結構 = 個體和個體之間的關系
- 算法 = 存儲對象的操作
衡量算法的標準
- 時間復雜度：大概程序要執(zhí)行的次數(shù)吝秕，而非執(zhí)行的事件
- 空間復雜度：算法執(zhí)行過程中大概所占用的最大內存
- 難易程度
- 健壯性
線性結構
把所有的節(jié)點用一根線穿起來
數(shù)組（連續(xù)存儲）
什么叫數(shù)組
元素類型相同泊脐，大小相等
數(shù)組的優(yōu)缺點
優(yōu)點：
存儲元素的效率非常高
缺點：
事先必須知道數(shù)組的長度
需要大塊連續(xù)的內存塊
插入刪除元素的效率很低
鏈表（離散存儲）
定義
n個節(jié)點離散分配，彼此通過指針相連烁峭，每個節(jié)點只有一個前驅節(jié)點容客，每個節(jié)點只有一個后續(xù)節(jié)點，首屆點沒有前驅節(jié)點约郁，未見點沒有后續(xù)節(jié)點
- 首節(jié)點：第一個有效節(jié)點
- 尾節(jié)點：最后一個有效節(jié)點
- 頭結點：第一個有效節(jié)點之前的那個節(jié)點缩挑，頭結點并不存放有效數(shù)據(jù)，加頭結點的目的主要是為了方便對鏈表的操作
- 頭指針：指向頭結點的指針變量
- 尾指針：指向尾節(jié)點的指針變量
確定一個鏈表需要幾個參數(shù)
只需要頭指針就可以推算出鏈表的其他所有參數(shù)
分類
- 單鏈表
- 雙向鏈表:每個節(jié)點有兩個指針域
- 循環(huán)鏈表:能通過任何一個節(jié)點找到其他所有節(jié)點
- 非循環(huán)鏈表
算法
- 遍歷
- 查找
- 清空
- 銷毀
- 求長度
- 排序
- 刪除節(jié)點
- 插入節(jié)點
算法：狹義的算法是與數(shù)據(jù)的存儲方式密切相關的
鬓梅，廣義的算法是與數(shù)據(jù)的存儲方式無關
泛型：利用某種技術達到的效果就是不同的存儲方式供置，執(zhí)行的操作是一樣的
鏈表的優(yōu)缺點
優(yōu)點：
空間沒有限制
插入刪除元素很快
缺點：
存儲速度很慢
線性結構的兩種常見應用----棧
定義
一種可以實現(xiàn)“先進后出”的存儲結構，棧類似于箱子
分類
- 靜態(tài)棧
- 動態(tài)棧
算法
- 入棧
- 出棧
應用
- 函數(shù)調用
- 中斷
- 表達式求值
- 內存分配
- 緩沖處理
- 迷宮
線性結構的兩種常見應用----隊列
定義
一種可以實現(xiàn)“先進先出”的存儲結構
分類
- 鏈式隊列（鏈表實現(xiàn)）
- 靜態(tài)隊列（數(shù)組實現(xiàn)）
靜態(tài)隊列通常都必須是循環(huán)隊列
循環(huán)隊列
1.靜態(tài)隊列威懾么必須是循環(huán)隊列
當靜態(tài)隊列不斷入隊出隊的時候绽快，由于隊列特性“先進先出”芥丧，頭尾不斷向前移動，導致隊列中的地址只能使用一次(假溢出)坊罢，所以引入循環(huán)隊列续担。
2.循環(huán)隊列需要幾個參數(shù)確定
front和rear
1).隊列初始化
front和rear的值都是零
2).隊列非空
front代表的是隊列的第一個元素
rear代表的是隊列的最后一個有效元素的下一個元素
3).隊列為空
front和rear的值相等，但不一定為零
3.循環(huán)隊列入隊偽算法
rear = (rear + 1) % 數(shù)組的長度
4.循環(huán)隊列出隊偽算法
front = (front + 1) % 數(shù)組的長度
5.循環(huán)隊列是否為空
如果front和rear的值相等艘绍，隊列一定為空
6.循環(huán)隊列是否為滿
(rear + 1) % 數(shù)組長度?=front
隊列應用
所有和時間有關的操作都與隊列有關
遞歸
定義
一個函數(shù)自己直接或間接調用自己
舉例
- 階乘
- 求和
- 漢諾塔
- 迷宮
遞歸滿足的三個條件
- 遞歸必須有一個明確的終止條件
- 該函數(shù)所處理的數(shù)據(jù)規(guī)模必須在遞減
- 這個轉化必須可解的
遞歸與循環(huán)
遞歸：易于理解赤拒，速度慢，存儲空間大
循環(huán)：不易于理解，速度快挎挖，存儲空間小
遞歸的基本思想
某件規(guī)模為n的事情如果想完成这敬，必須要你借助他n-1的規(guī)模完成。
樹
定義
有且只有一個稱為根的節(jié)點蕉朵，有若干個互不相交的子樹崔涂，這些子樹本身也是樹。
樹是由節(jié)點和邊組成始衅，每個節(jié)點只有一個父節(jié)點但可以有多個子節(jié)點冷蚂，但根節(jié)點沒有父節(jié)點。
深度：從根節(jié)點到最底層節(jié)點的層數(shù)
葉子節(jié)點：沒有子節(jié)點的節(jié)點
非終端節(jié)點：實際就是非葉子節(jié)點
度：子節(jié)點的個數(shù)
分類
一般的樹：任意一個節(jié)點的子節(jié)點的個數(shù)都不受限制
二叉樹：任意一個節(jié)點的子節(jié)點個數(shù)最多只有兩個汛闸，且子節(jié)點的位置不可更改
森林：n個互不相交的樹的集合
存儲
二叉樹存儲：
連續(xù)存儲：如果用數(shù)組的方式存儲蝙茶，必須要是完全二叉樹
- 優(yōu)點：查找某個節(jié)點的父節(jié)點和子節(jié)點
- 缺點：占用內存空間大
鏈式存儲
一般二叉樹的存儲
- 雙親表示法：求父節(jié)點方便
- 孩子表示法：求子節(jié)點方便
- 雙親孩子表示法：求父節(jié)點和子節(jié)點都很方便，但是操作不方便
- 孩子兄弟表示法（二叉樹表示法）：把一個普通樹轉換成二叉樹進行存儲（設法保證任意一個節(jié)點的左指針域指向他的第一個孩子诸老，右指針域指向下一個兄弟隆夯，只要滿足這個條件，就能把一個普通樹轉化成二叉樹）
一個普通的樹轉化成的二叉樹一定沒有右子樹
森林的存儲
- 先把森林轉化成二叉樹别伏，在存儲成二叉樹（把每個樹當做前一個的兄弟）
操作
二叉樹
分類
- 一般二叉樹
- 滿二叉樹：在不增加樹的層數(shù)的前提下蹄衷，無法再多添加一個節(jié)點的二叉樹
- 完全二叉樹：如果只是刪除了滿二叉樹最底層最右邊的連續(xù)若干個節(jié)點，所形成的二叉樹
二叉樹操作
遍歷
- 先序遍歷:
先訪問根節(jié)點
再先序訪問左子樹
再先序訪問右子樹
- 中序遍歷
中序訪問左子樹
再訪問根節(jié)點
中序訪問右子樹
- 后序遍歷
后序訪問左子樹
后序訪問右子樹
再訪問根節(jié)點
已知兩種遍歷序列求原始二叉樹
通過先序和中序或者中序和后續(xù)樂意還原出原始二叉樹厘肮，但是通過先序和后續(xù)無法還原出原始的二叉樹
應用
- 樹誰數(shù)據(jù)庫中數(shù)據(jù)組織的一種重要形式
- 操作系統(tǒng)子父進程的關系本身是一棵樹
- 面向對象語言中類的集成關系本身是一棵樹
- 赫夫曼樹
