嵌入式LinuxC語言基礎(chǔ)——ARMLinux內(nèi)核常見數(shù)據(jù)結(jié)構(gòu).pptVIP

,嵌入式Linux C編程入門（第2版） (By Farsight),/,,第8章 嵌入式Linux C語言基礎(chǔ)ARM Linux內(nèi)核常見數(shù)據(jù)結(jié)構(gòu),本章目標(biāo) 鏈表的基本概念 鏈表的基本操作方法 ARM Linux中如何使用鏈表 二叉樹的基本概念 樹的遍歷方法 森林的基本概念 森林的遍歷方法 平衡樹的基本概念 ARM Linux中如何實(shí)現(xiàn)紅黑樹 哈希表的概念 哈希表的操作方法 ARM Linux中如何使用哈希表,,鏈表,鏈表是一種常見的重要數(shù)據(jù)結(jié)構(gòu)，它可以動(dòng)態(tài)地進(jìn)行存儲分配，根據(jù)需要開辟內(nèi)存單元，還可以方便地實(shí)現(xiàn)數(shù)據(jù)的增加和刪除。鏈表中的每個(gè)元素都由兩部分組成：數(shù)據(jù)域和指針域。,,單鏈表的組織與存儲,單向鏈表的每個(gè)節(jié)點(diǎn)中除信息域以外還有一個(gè)指針域，用來指向其后續(xù)節(jié)點(diǎn)，其最后一個(gè)節(jié)點(diǎn)的指針域?yàn)榭眨∟ULL）。,,單鏈表常見操作,節(jié)點(diǎn)初始化 測試數(shù)據(jù)是否存在 鏈表的插入與刪除 將幾個(gè)單鏈表合并,,雙向鏈表的組織與存儲,雙向鏈表與單向鏈表不同，它的每個(gè)節(jié)點(diǎn)中包括兩個(gè)指針域，分別指向該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn),,雙向鏈表的常見操作,增加節(jié)點(diǎn) 刪除節(jié)點(diǎn),,循環(huán)鏈表,循環(huán)鏈表的組織結(jié)構(gòu)與單鏈表非常相似，因此其操作與單鏈表也是一致的，惟一的差別僅在于在單鏈表中，算法判端到達(dá)鏈表尾的條件是pnext是否為空，而在雙鏈表中，則是判斷pnext是否等于頭指針,,ARM Linux中鏈表使用實(shí)例,ARM Linux內(nèi)核鏈表 Linux內(nèi)核鏈表接口 聲明和初始化 插入 刪除,,樹,樹是n（n0）個(gè)節(jié)點(diǎn)的有限集合。若n=0，則稱為空樹；否則，有且僅有一個(gè)特定的節(jié)點(diǎn)被稱為根，當(dāng)n1時(shí)，其余節(jié)點(diǎn)被分成m（m0）個(gè)互不相交的子集T1、T2、.、Tm，每個(gè)子集又是一棵樹,,二叉樹,二叉樹是另一種樹型結(jié)構(gòu)，它是節(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根節(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。 它的特點(diǎn)是每個(gè)節(jié)點(diǎn)至多只有兩棵子樹（即二叉樹中不存在度大于2的節(jié)點(diǎn)），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。,,二叉樹的順序存儲,順序存儲結(jié)構(gòu) 鏈?zhǔn)酱鎯Y(jié)構(gòu),,二叉樹的鏈?zhǔn)酱鎯?typedef struct BTNode EntryType item; struct BTNode *lchild,*rchlid; BTNode,*BTree;,,二叉樹的常見操作,遍歷二叉樹 統(tǒng)計(jì)二叉樹中的葉子節(jié)點(diǎn) 統(tǒng)計(jì)二叉樹中的高度,,平衡樹,二叉樹是一種非平衡樹，各個(gè)子樹之間的高度可能相差很大，這樣就會造成平均性能的下降。 平衡樹包括很多種類，常見的有B樹、AVL樹、紅黑樹等,,紅黑樹是指滿足下列條件的二叉搜索樹。 性質(zhì)1：每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色（后面將說明）。 性質(zhì)2：所有的葉節(jié)點(diǎn)都是空節(jié)點(diǎn)，并且是黑色的。 性質(zhì)3：如果一個(gè)節(jié)點(diǎn)是紅色的，那么它的兩個(gè)子節(jié)點(diǎn)都是黑色的。 性質(zhì)4：節(jié)點(diǎn)到其子孫節(jié)點(diǎn)的每條簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。 性質(zhì)5：根節(jié)點(diǎn)永遠(yuǎn)是黑色的。,,紅黑樹插入節(jié)點(diǎn)的過程如下。 在樹中搜索插入點(diǎn)。 新節(jié)點(diǎn)將替代某個(gè)已經(jīng)存在的空節(jié)點(diǎn)，并且將擁有兩個(gè)作為子節(jié)點(diǎn)的空節(jié)點(diǎn)。 新節(jié)點(diǎn)標(biāo)記為紅色，其父節(jié)點(diǎn)的顏色根據(jù)紅黑樹的定義確定，如果需要，對樹作調(diào)整。,,哈希表的構(gòu)造方法,構(gòu)造哈希表實(shí)際上也就是構(gòu)造哈希函數(shù)以確定關(guān)鍵值的存儲位置，并能盡可能地減少