數(shù)據(jù)結(jié)構(gòu)的概述

定義

我們?nèi)绾伟熏F(xiàn)實(shí)中大量而反復(fù)的問(wèn)題以特定的數(shù)據(jù)類型和特定的存儲(chǔ)結(jié)構(gòu)保存到主存儲(chǔ)器(內(nèi)存)中，以及在此基礎(chǔ)上為實(shí)現(xiàn)某個(gè)功能（比如查找某個(gè)元素，刪除某個(gè)元素，對(duì)所有元素進(jìn)行排序）而執(zhí)行的相應(yīng)的操作，這個(gè)相應(yīng)的操作也叫做算法。
　　數(shù)據(jù)結(jié)構(gòu) = 個(gè)體+個(gè)體的關(guān)系
　　算法 = 對(duì)存儲(chǔ)數(shù)據(jù)的操作

狹義：

數(shù)據(jù)結(jié)構(gòu)是專門(mén)研究數(shù)據(jù)存儲(chǔ)的問(wèn)題
數(shù)據(jù)的存儲(chǔ)包含兩方面：個(gè)體的存儲(chǔ) + 個(gè)體關(guān)系的存儲(chǔ)

廣義：

數(shù)據(jù)結(jié)構(gòu)既包含數(shù)據(jù)的存儲(chǔ)也包含數(shù)據(jù)的操作
對(duì)存儲(chǔ)數(shù)據(jù)的操作就是算法

算法

狹義：

算法是和數(shù)據(jù)的存儲(chǔ)方式密切相關(guān)

廣義：

算法和數(shù)據(jù)的存儲(chǔ)方式無(wú)關(guān)，這就是泛型思想

衡量算法的標(biāo)準(zhǔn)：

（1） 時(shí)間復(fù)雜度
大概程序要執(zhí)行的次數(shù)，而并非是執(zhí)行的時(shí)間（因?yàn)橥怀绦蛟诓煌瑱C(jī)器上執(zhí)行的時(shí)間是不一樣的，有差異）
（2） 空間復(fù)雜度
算法執(zhí)行過(guò)程中大概所占用的最大內(nèi)存
（3） 難易程度
（4） 健壯性

數(shù)據(jù)結(jié)構(gòu)的地位：

數(shù)據(jù)結(jié)構(gòu)是軟件中最核心的課程
程序 = 數(shù)據(jù)的存儲(chǔ) + 數(shù)據(jù)的操作 + 可以被計(jì)算機(jī)執(zhí)行的語(yǔ)言

泛型

對(duì)于同一種邏輯結(jié)構(gòu)，無(wú)論該邏輯結(jié)構(gòu)的物理存儲(chǔ)是什么樣子的，我們可以對(duì)它執(zhí)行相同的操作。

數(shù)據(jù)的存儲(chǔ)有幾種：

1. 線性：

• 連續(xù)存儲(chǔ)：【數(shù)組】

元素類型相同，大小相等（數(shù)組傳參，只要傳進(jìn)去首地址和長(zhǎng)度就行）
　優(yōu)點(diǎn)：
　　存取速度快
　缺點(diǎn)：
　　事先必須知道數(shù)組的長(zhǎng)度
　　插入刪除元素很慢
　　空間通常是有限的
　　需要大塊連續(xù)的內(nèi)存塊

• 離散存儲(chǔ)【鏈表】

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)。
　優(yōu)點(diǎn)：
　　空間沒(méi)有限制
　　插入刪除元素很快
　缺點(diǎn)：
　　存取速度很慢
　概念：
　　首節(jié)點(diǎn)：第一個(gè)有效節(jié)點(diǎn)
　　尾節(jié)點(diǎn)：最后一個(gè)有效節(jié)點(diǎn)
　　頭節(jié)點(diǎn)：頭結(jié)點(diǎn)的數(shù)據(jù)類型和首節(jié)點(diǎn)的類型一樣沒(méi)有存放有效數(shù)據(jù)，最最前面的，是在首節(jié)點(diǎn)之前的，主要是為了方便對(duì)鏈表的操作。
　　頭指針：（指向頭）指向頭節(jié)點(diǎn)的指針變量
　　尾指針：指向尾節(jié)點(diǎn)的指針
　分類：
　　 單鏈表：每一個(gè)節(jié)點(diǎn)有一個(gè)指針域
　　 雙鏈表：每一個(gè)節(jié)點(diǎn)有兩個(gè)指針域
　　 循環(huán)鏈表：能通過(guò)任何一個(gè)節(jié)點(diǎn)找到其他所有的節(jié)點(diǎn)
　 　非循環(huán)鏈表：非循環(huán)鏈表尾指針為空

線性結(jié)構(gòu)的兩種常見(jiàn)應(yīng)用：
棧和隊(duì)列是一種特殊的線性結(jié)構(gòu)，是連續(xù)存儲(chǔ)或離散存儲(chǔ)的一種應(yīng)用

棧

定義：
　　一種可以實(shí)現(xiàn)“先進(jìn)后出“的存儲(chǔ)結(jié)構(gòu)，類似于箱子
　分類：
　　靜態(tài)棧
　　動(dòng)態(tài)棧
　算法：
　　出棧
　　壓棧
　應(yīng)用：
　　緩沖處理，表達(dá)式求值，中斷，內(nèi)存分配，迷宮，函數(shù)調(diào)用

int main(void)
{
  int p;                          
  int * m = (int *)malloc(100);
}

// 如靜態(tài)變量p和m是在棧中分配，有操作系統(tǒng)自動(dòng)分配和釋放。而(int *)malloc(100);執(zhí)行后，將在堆中分配一塊100字節(jié)的內(nèi)存，由程序員手動(dòng)分配。

棧的示意圖

image.png

隊(duì)列

定義：
　　一種可以實(shí)現(xiàn)“先進(jìn)先出”的存儲(chǔ)結(jié)構(gòu)
　分類：
　　鏈?zhǔn)疥?duì)列： -----用鏈表實(shí)現(xiàn)（比較簡(jiǎn)單）
　　靜態(tài)隊(duì)列： -----用數(shù)組實(shí)現(xiàn) 靜態(tài)隊(duì)列通常都必須是循環(huán)隊(duì)列
　應(yīng)用：
　　所有和時(shí)間有關(guān)的事件都有隊(duì)列的影子
　隊(duì)列算法：
　　入隊(duì)
　　出隊(duì)
循環(huán)隊(duì)列的講解
　　（1）靜態(tài)隊(duì)列為什么必須是循環(huán)隊(duì)列

image.png

　　　　現(xiàn)在如果一個(gè)數(shù)組里面存了四個(gè)元素，那么front就只想第一個(gè)有效元素，而real指向最后一個(gè)元素的下一個(gè)元素，當(dāng)增加元素時(shí)，只能在rear一端增加，即rear向上移。刪除元素時(shí)，只能在front一端刪除元素，即front向上移。但是如果一直增增刪刪，那么就會(huì)造成rear端溢出，而front端浪費(fèi)，所以對(duì)于這種情況，可以采用循環(huán)隊(duì)列的形式，即當(dāng)rear已經(jīng)指向數(shù)組最后一個(gè)元素時(shí)，那么就可以轉(zhuǎn)而將rear指向數(shù)組的第一個(gè)空出來(lái)的空間。
　　（2）循環(huán)隊(duì)列需要幾個(gè)參數(shù)來(lái)確定
　　　　　需要2個(gè)參數(shù)來(lái)確定：front 和 rear
　?。?）循環(huán)隊(duì)列各個(gè)參數(shù)的含義：
　　　　　2個(gè)參數(shù)在不同場(chǎng)合有不同的含義
　　　　　- 隊(duì)列初始化
　　　　　　front和rear的值都為零
　　　　　- 隊(duì)列非空
　　　　　　front代表的是隊(duì)列的第一個(gè)元素
　　　　　　rear代表的是隊(duì)列的最后一個(gè)有效元素的下一個(gè)元素
　　　　　- 隊(duì)列為空
　　　　　　front和real的值相等，但不一定為零
　?。?）循環(huán)隊(duì)列入隊(duì)偽算法講解：
　　　　　兩步完成：
　　　　　　- 將值存入rear所代表的位置
　　　　　　- 錯(cuò)誤的寫(xiě)法 ：rear = rear+1;
　　　　　正確的寫(xiě)法是：rear = (rear+1)%數(shù)組的長(zhǎng)度
　　（5）循環(huán)隊(duì)列出隊(duì)偽算法講解
　　　　　 Front =（front +1）%數(shù)組的長(zhǎng)度
　　(6) 如何判斷循環(huán)隊(duì)列是否為空
　　　　　如果front與rear的值相等，則該隊(duì)列就一定為空
　　（7）如何判斷循環(huán)隊(duì)列是否已滿
　　　　　因?yàn)閒ront的值可能比rear大，也可能比他小，也可能相等
　　　　　所以有兩種方式:
　　　　　　-多增加一個(gè)標(biāo)識(shí)是否滿的參數(shù)
　　　　　　-少用一個(gè)元素【通常用此種方式】
　　　　　如果front和rear的值相差1，且front>rear,則證明隊(duì)列已滿。
　　　　　用C語(yǔ)言偽算法表示為：

       if ((rear+1)%數(shù)組長(zhǎng)度==front)
           已滿
       else
           未滿

遞歸：

知識(shí)點(diǎn)一：函數(shù)的調(diào)用
　當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行被調(diào)函數(shù)之前，系統(tǒng)需要完成三件事：
　　　　將所有的實(shí)際參數(shù)，返回地址等信息傳遞給被調(diào)函數(shù)。
　　　　為被調(diào)函數(shù)的局部變量（也包括形參）分配存儲(chǔ)空間
　　　　將控制轉(zhuǎn)移到被調(diào)函數(shù)的入口
　從被調(diào)函數(shù)返回主調(diào)函數(shù)之前，系統(tǒng)也要完成三件事：
　　　　保存被調(diào)函數(shù)的返回結(jié)果
　　　　釋放被調(diào)函數(shù)所占的存儲(chǔ)空間
　　　　依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)

當(dāng)有多個(gè)函數(shù)相互調(diào)用時(shí)，按照“后調(diào)用先返回”的原則，上述函數(shù)之間信息傳遞和控制轉(zhuǎn)移必須借助“?！眮?lái)實(shí)現(xiàn)，即系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需的數(shù)據(jù)空間安排在一個(gè)棧中，每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，將在棧頂分配一個(gè)存儲(chǔ)區(qū)，進(jìn)行壓棧操作，每當(dāng)一個(gè)函數(shù)退出時(shí)，就釋放它的存儲(chǔ)區(qū)，就進(jìn)行出棧操作，當(dāng)前運(yùn)行的函數(shù)永遠(yuǎn)都在棧頂位置。
A函數(shù)調(diào)用A函數(shù)和A函數(shù)調(diào)用B函數(shù)在計(jì)算機(jī)看來(lái)是沒(méi)有任何區(qū)別的，只不過(guò)用我們?nèi)粘５乃季S方式比較怪異而已。

知識(shí)點(diǎn)二：遞歸必須滿足的三個(gè)條件
　　　　遞歸必須得有一個(gè)明確的終止條件
　　　　該函數(shù)所處理的數(shù)據(jù)規(guī)模必須在遞減
　　　　這個(gè)轉(zhuǎn)化必須是可解的
知識(shí)點(diǎn)三：遞歸和循環(huán)的優(yōu)缺點(diǎn)比較
　　遞歸：
　　　　易于理解
　　　　速度慢
　　　　存儲(chǔ)空間大
　　循環(huán)：
　　　　不易理解
　　　　速度快
　　　　存儲(chǔ)空間小
知識(shí)點(diǎn)四：遞歸的應(yīng)用
　　　　樹(shù)和森林就是以遞歸的方式定義的
　　　　樹(shù)和圖的很多算法都是以遞歸來(lái)實(shí)現(xiàn)的
　　　　很多數(shù)學(xué)公式就是以遞歸的方式定義的
斐波拉契序列：1 2 3 5 8 13 21 34

2. 非線性：

• 樹(shù)

定義：
　專業(yè)定義：
　　1. 有且只有一個(gè)稱為根的節(jié)點(diǎn)
　　2. 有若干個(gè)互不相交的子樹(shù)，這些子樹(shù)本身也是一棵樹(shù)。
　通俗的定義：
　　1. 樹(shù)是由節(jié)點(diǎn)和邊組成。
　　2. 每個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)但可以有多個(gè)子節(jié)點(diǎn)
　　3. 但有一個(gè)節(jié)點(diǎn)例外，該節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)，此節(jié)點(diǎn)稱為根節(jié)點(diǎn)
樹(shù)相關(guān)的專業(yè)術(shù)語(yǔ)：

• 節(jié)點(diǎn)
• 根節(jié)點(diǎn)
• 父節(jié)點(diǎn)
• 子節(jié)點(diǎn)
  有直接父子關(guān)系的才能叫子節(jié)點(diǎn)
• 子孫節(jié)點(diǎn)
• 堂兄弟節(jié)點(diǎn)
  　其父節(jié)點(diǎn)是兄弟節(jié)點(diǎn)的為堂兄弟節(jié)點(diǎn)
• 深度
  　從根節(jié)點(diǎn)到對(duì)底層節(jié)點(diǎn)的層數(shù)稱之為深度根節(jié)點(diǎn)是第一層
• 葉子節(jié)點(diǎn)
  　沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)
• 非終端節(jié)點(diǎn)
  　實(shí)際就是非葉子節(jié)點(diǎn)
• 度
  　子節(jié)點(diǎn)的個(gè)數(shù)稱為度，整個(gè)樹(shù)的度就是所有節(jié)點(diǎn)的度數(shù)中，度數(shù)最大的那個(gè)為整個(gè)樹(shù)的度數(shù)
  樹(shù)的分類：
• 一般樹(shù)
  　任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的個(gè)數(shù)都不受限制，子節(jié)點(diǎn)的順序可以更改也可以不能更改，能更改的樹(shù)為無(wú)序一般樹(shù)，不能更改的為有序一般樹(shù)
• 二叉樹(shù)
  　任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)最多兩個(gè)，且子節(jié)點(diǎn)的位置不可更改，即左子樹(shù)和右子樹(shù)的位置不可更改。

二叉樹(shù)分類：

1. 一般二叉樹(shù)
2. 滿二叉樹(shù)
   　　在不增加樹(shù)的層數(shù)的前提下，無(wú)法再多添加一個(gè)節(jié)點(diǎn)的二叉樹(shù)就是滿二叉樹(shù)，及所有的節(jié)點(diǎn)都是兩個(gè)度數(shù)（兩個(gè)子節(jié)點(diǎn)）
3. 完全二叉樹(shù)
   　　如果只是刪除了滿二叉樹(shù)最底層最右邊的連續(xù)若干個(gè)節(jié)點(diǎn)，這樣形成的二叉樹(shù)就是完全二叉樹(shù)。滿二叉樹(shù)只是完全二叉樹(shù)的一個(gè)特例。

• 森林
  n個(gè)互不相交的樹(shù)的集合
  樹(shù)的存儲(chǔ)：

1. 二叉樹(shù)的存儲(chǔ)

• 連續(xù)存儲(chǔ) 用數(shù)組存儲(chǔ)【適用于完全二叉樹(shù)，不是完全二叉樹(shù)的樹(shù)補(bǔ)充為完全二叉樹(shù)】
  　　優(yōu)點(diǎn):查找某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)（也包括判斷有沒(méi)有子節(jié)點(diǎn)）方便快速
  　　缺點(diǎn)：耗用內(nèi)存空間過(guò)大
• 鏈?zhǔn)酱鎯?chǔ) 兩個(gè)指針域分別指向兩個(gè)子節(jié)點(diǎn)，沒(méi)有子節(jié)點(diǎn)的為空
  　　優(yōu)點(diǎn)：耗用內(nèi)存空間小
  　　缺點(diǎn)：查找父節(jié)點(diǎn)不方便

2. 一般樹(shù)的存儲(chǔ)

• 雙親表示法

  
  
  image.png

• 孩子表示法

  
  
  image.png

• 雙親孩子表示法

  
  
  image.png
• 二叉樹(shù)表示法
  先把一個(gè)普通樹(shù)轉(zhuǎn)換為二叉樹(shù)，再存儲(chǔ)二叉樹(shù)。
  　具體轉(zhuǎn)換方法：
  　　設(shè)法保證任意一個(gè)節(jié)點(diǎn)的
  　　 　左指針域指向它的第一個(gè)孩子
  　　　右指針域指向它的下一個(gè)兄弟
  　　只要能滿足條件，就可以把一個(gè)普通樹(shù)轉(zhuǎn)化為二叉樹(shù)。
  　　一個(gè)普通樹(shù)轉(zhuǎn)化成的二叉樹(shù)一定沒(méi)有右子樹(shù)

3. 森林的存儲(chǔ)
   先把森林轉(zhuǎn)化為二叉樹(shù)，再存儲(chǔ)二叉樹(shù)
   　具體轉(zhuǎn)換方法：
   　　將森林中的每個(gè)樹(shù)的節(jié)點(diǎn)當(dāng)做兄弟存儲(chǔ)；
   　　設(shè)法保證任意一個(gè)節(jié)點(diǎn)的
   　　　左指針域指向它的第一個(gè)孩子,
   　　　右指針域指向它的下一個(gè)兄弟
   　　只要滿足條件，就可以把一個(gè)森林轉(zhuǎn)化為二叉樹(shù)

   
   
   image.png

二叉樹(shù)的遍歷：
　先序遍歷【先訪問(wèn)根節(jié)點(diǎn)】
　　方法：(1)先訪問(wèn)根節(jié)點(diǎn)
　　　　　(2)再先序訪問(wèn)左子樹(shù)
　　　　　(3)再先序訪問(wèn)右子樹(shù)

image.png

　中序遍歷【中間訪問(wèn)根節(jié)點(diǎn)】
　方法：(1)中序遍歷左子樹(shù)
　　　　(2)再訪問(wèn)根節(jié)點(diǎn)
　　　　(3)再中序遍歷右子樹(shù)

image.png

　后序遍歷【最后訪問(wèn)根節(jié)點(diǎn)】
　方法：(1)先中序遍歷左子樹(shù)
　　　　(2)在中序遍歷右子樹(shù)
　　　　(3)再訪問(wèn)根節(jié)點(diǎn)

image.png

已知兩種遍歷序列求原始二叉樹(shù)
　(1)****先序，中序和后序三種遍歷中，只知道其中任意一個(gè)，是無(wú)法還原其原始的樹(shù)結(jié)構(gòu)的。
　 (2)****通過(guò)先序和中序****或者****中序和后序****兩種方式我們可以還原原始的二叉樹(shù)。但是通過(guò)先序和后序是無(wú)法還原原始的二叉樹(shù)的。
　換種說(shuō)法只有通過(guò)先序和中序****或者****通過(guò)中序和后序我們才能唯一的確定一個(gè)二叉樹(shù)的。

已知先序和中序求后序例子
　示例****1****：
　　先序：****ABCDEFGH****（排在前面的為根節(jié)點(diǎn)）
　　中序：****BDCEAFHG
　　求后序：****DECBHGFA
　示例****2****：
　　先序：****ABDGHCEFI
　　中序：****GDHBAECIF
　　求后序：****GHDBEIFCA

已知后序和中序求后序例子
　示例****1****：
　　中序：****BDCE A FHG
　　后序：****DECB HGF A****（排在后面的為根節(jié)點(diǎn)）
　　求先序：****A BCDE FGH

樹(shù)的應(yīng)用
　(1)樹(shù)是數(shù)據(jù)庫(kù)中數(shù)據(jù)組織的一種重要形式**
　(2)操作系統(tǒng)父子進(jìn)程的關(guān)系本身就是一棵樹(shù)**
　(3)面向?qū)ο笳Z(yǔ)言中類的繼承關(guān)系本身就是一棵樹(shù)**
　(4)赫夫曼樹(shù)**