《嵌入式LinuxC语言基础-ARMLinux内核常见数据结构》由会员分享，可在线阅读，更多相关《嵌入式LinuxC语言基础-ARMLinux内核常见数据结构（19页珍藏版）》请在金锄头文库上搜索。
1、嵌入式Linux C编程入门（第2版） (By Farsight) 第8章 嵌入式Linux C语言基础ARM Linux内核 常见数据结构 本章目标 链表的基本概念 链表的基本操作方法 ARM Linux中如何使用链表 二叉树的基本概念 树的遍历方法 森林的基本概念 森林的遍历方法 平衡树的基本概念 ARM Linux中如何实现红黑树 哈希表的概念 哈希表的操作方法 ARM Linux中如何使用哈希表 链表 链表是一种常见的重要数据结构，它可以动态地 进行存储分配，根据需要开辟内存单元，还可以 方便地实现数据的增加和删除。链表中的每个元 素都由两部分组成：数据域和指针域。 单链表的组织与存储
2、 单向链表的每个节点中除信息域以外还有一个指 针域，用来指向其后续节点，其最后一个节点的 指针域为空（NULL）。 单链表常见操作 节点初始化 测试数据是否存在 链表的插入与删除 将几个单链表合并 双向链表的组织与存储 双向链表与单向链表不同，它的每个节点中包括 两个指针域，分别指向该节点的前一个节点和后 一个节点 双向链表的常见操作 增加节点 删除节点 循环链表 循环链表的组织结构与单链表非常相似，因此其 操作与单链表也是一致的，惟一的差别仅在于在 单链表中，算法判端到达链表尾的条件是pnext 是否为空，而在双链表中，则是判断pnext是否 等于头指针 ARM Linux中链表使用实例 A
3、RM Linux内核链表 Linux内核链表接口 声明和初始化 插入 删除 树 树是n（n0）个节点的有限集合。若n=0，则称为 空树；否则，有且仅有一个特定的节点被称为根 ，当n1时，其余节点被分成m（m0）个互不相 交的子集T1、T2、.、Tm，每个子集又是一棵树 二叉树 二叉树是另一种树型结构，它是节点的一个有限 集合，该集合或者为空，或者是由一个根节点加 上两棵分别称为左子树和右子树的、互不相交的 二叉树组成。 它的特点是每个节点至多只有两棵子树（即二叉 树中不存在度大于2的节点），并且，二叉树的子 树有左右之分，其次序不能任意颠倒。 二叉树的顺序存储 顺序存储结构 链式存储结构 二叉
4、树的链式存储 typedef struct BTNode EntryType item; struct BTNode *lchild,*rchlid; BTNode,*BTree; 二叉树的常见操作 遍历二叉树 统计二叉树中的叶子节点 统计二叉树中的高度 平衡树 二叉树是一种非平衡树，各个子树之间的高度可 能相差很大，这样就会造成平均性能的下降。 平衡树包括很多种类，常见的有B树、AVL树、红 黑树等 红黑树是指满足下列条件的二叉搜索树。 性质1：每个节点要么是红色，要么是黑色（后 面将说明）。 性质2：所有的叶节点都是空节点，并且是黑色 的。 性质3：如果一个节点是红色的，那么它的两个 子节点都是黑色的。 性质4：节点到其子孙节点的每条简单路径都包 含相同数目的黑色节点。 性质5：根节点永远是黑色的。 红黑树插入节点的过程如下。 在树中搜索插入点。 新节点将替代某个已经存在的空节点，并且将拥有两 个作为子节点的空节点。 新节点标记为红色，其父节点的颜色根据红黑树的定 义确定，如果需要，对树作调整。 哈希表的构造方法 构造哈希表实际上也就是构造哈希函数以确定关 键值的存储位置，并能尽可能地减少哈希冲突的 个数。 直接定址法 数字分析法 折叠法 除留余数法 随机数法 哈希表的处理冲突方法 开放定址法 再哈希法 链地址法 建立一个公共溢出区
