嵌入式LinuxC語言基礎——ARMLinux內核常見數據結構.ppt

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