嵌入式LinuxC语言基础-ARMLinux内核常见数据结构.ppt

嵌入式LinuxC编程入门（第2版）

(ByFarsight)

http:///第8章嵌入式LinuxC语言基础——ARMLinux内核常见数据结构本章目标链表的基本概念链表的基本操作方法ARMLinux中如何使用链表二叉树的基本概念树的遍历方法森林的基本概念森林的遍历方法平衡树的基本概念ARMLinux中如何实现红黑树哈希表的概念哈希表的操作方法ARMLinux中如何使用哈希表链表链表是一种常见的重要数据结构，它可以动态地进行存储分配，根据需要开辟内存单元，还可以方便地实现数据的增加和删除。链表中的每个元素都由两部分组成：数据域和指针域。单链表的组织与存储单向链表的每个节点中除信息域以外还有一个指针域，用来指向其后续节点，其最后一个节点的指针域为空（NULL）。节点初始化测试数据是否存在将几个单链表合并链表的插入与删除单链表常见操作双向链表的组织与存储双向链表与单向链表不同，它的每个节点中包括两个指针域，分别指向该节点的前一个节点和后一个节点增加节点删除节点双向链表的常见操作循环链表循环链表的组织结构与单链表非常相似，因此其操作与单链表也是一致的，惟一的差别仅在于在单链表中，算法判端到达链表尾的条件是p→next是否为空，而在双链表中，则是判断p→next是否等于头指针AEDBCLinux内核链表接口声明和初始化删除插入ARMLinux内核链表ARMLinux中链表使用实例树树是n（n≥0）个节点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的节点被称为根，当n1时，其余节点被分成m（m0）个互不相交的子集T1、T2、...、Tm，每个子集又是一棵树二叉树01二叉树是另一种树型结构，它是节点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。它的特点是每个节点至多只有两棵子树（即二叉树中不存在度大于2的节点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。02顺序存储结构链式存储结构0102二叉树的顺序存储01typedefstructBTNode{03structBTNode*lchild,*rchlid;02EntryTypeitem;04}BTNode,*BTree;二叉树的链式存储遍历二叉树统计二叉树中的叶子节点统计二叉树中的高度二叉树的常见操作