《嵌入式Linux C语言开发 教学课件 ppt 华清远见嵌入式学院 曾宏安 第4章 嵌入式linux内核常见数据结构》由会员分享，可在线阅读，更多相关《嵌入式Linux C语言开发 教学课件 ppt 华清远见嵌入式学院 曾宏安 第4章 嵌入式linux内核常见数据结构（62页珍藏版）》请在金锄头文库上搜索。
1、,嵌入式linux内核常见数据结构,www.embedu.org,课程目标,内核中的链表 内核中的树 内核中的哈希表,www.embedu.org,本章内容,4.1 链表 4.2 树、二叉树、平衡树 4.3 哈希表 本章小结,www.embedu.org,4.1 链表,链表是一种常见的重要数据结构，它可以动态地进行存储分配，根据需要开辟内存单元，还可以方便地实现数据的增加和删除。链表中的每个元素都由两部分组成：数据域和指针域。 其中，数据域用于存储数据元素的信息，指针域用于存储该元素的直接后继元素的位置。,www.embedu.org,4.1.1 单向链表,单链表的组织与存储 单向链表的每个节
2、点中除信息域以外还有一个指针域，用来指向其后续节点，其最后一个节点的指针域为空（NULL）。 单向链表由头指针惟一确定，因此单向链表可以用头指针的名字来命名，头指针指向单向链表的第一个节点。,www.embedu.org,4.1.1 单向链表,单链表常见操作 （1）节点初始化,int init_link(link_list *list) /*用malloc分配函数分配节点*/ *list = (link_list)malloc(sizeof(link_node); /*若分配失败，返回*/ if (!list) return -1; /*初始化链表节点的数据域*/ memset( ,www.e
3、mbedu.org,4.1.1 单向链表,单链表常见操作 （2）数据查询,int get_element(link_list list, int i, element_type *elem) /* list为带头节点的单链表的头指针 */ /*当第i个元素存在时，其值赋给elem并返回*/ link_list p = NULL; int j = 0; /*初始化，指向链表的第一个节点，j为计数器*/ p = list-next; /* 为防止i过大，通过判断p是否为空来确定是否到达链表的尾部 */ while (j+ next); /* 若第i个元素不存在，返回 */ if (!p | (j
4、data; return 0; ,www.embedu.org,4.1.1 单向链表,单链表常见操作 （3）链表的插入与删除,int link_insert(link_list list, int i, element_type elem) /* list为带头节点的单链表的头指针 */ /* i为要插入的元素位置，elem为要插入的元素*/ link_list p = list, new_node; int j = 0; /* 找到第i位 */ while (j+ next); if (!p | (j data = elem; /*将s插入链表，并修改原先的指针*/ new_node-nex
5、t = p-next; p-next = new_node; return 1; ,www.embedu.org,4.1.1 单向链表,单链表常见操作 （4）其他操作（将几个单链表合并）,www.embedu.org,4.1.2 双向链表,双向链表的组织与存储 双向链表与单向链表不同，它的每个节点中包括两个指针域，分别指向该节点的前一个节点和后一个节点 定义双向链表的节点结构为： struct link_node element_type data; /*element_type为有效数据类型*/ struct link_node *next; struct link_node *priv;
6、;,www.embedu.org,4.1.2 双向链表,双向链表的常见操作 （1）增加节点,www.embedu.org,4.1.2 双向链表,双向链表的常见操作 （2）删除节点,www.embedu.org,4.1.3 循环链表,单向链表的最后一个节点的指针域为空（NULL）。如果将这个指针利用起来，以指向单向链表的第一个节点，就能组成一个单向循环链表 。,www.embedu.org,4.1.3 循环链表,www.embedu.org,4.1.4 ARM Linux中链表使用实例,1）ARM Linux内核链表概述 在ARM Linux中，链表是最为基本的数据结构，也是最为常用的数据结构。
7、2.4内核中的链表结构和2.6并没有太大区别。二者不同之处在于2.6扩充了两种链表数据结构：链表的读拷贝更新（rcu）和HASH链表（hlist）。 链表数据结构的定义很简单： struct list_head struct list_head *next, *prev; ;,www.embedu.org,4.1.4 ARM Linux中链表使用实例,2）Linux内核链表接口 （1）声明和初始化 这里是使用LIST_HEAD()这个宏来构建的。 #define LIST_HEAD_INIT(name) ,www.embedu.org,4.1.4 ARM Linux中链表使用实例,2）Linu
8、x内核链表接口 （1）插入 对链表的插入操作有两种：在表头插入和在表尾插入。Linux为此提供了两个接口： static inline void list_add(struct list_head *new, struct list_head *head); static inline void list_add_tail(struct list_head *new, struct list_head *head);,www.embedu.org,4.1.4 ARM Linux中链表使用实例,2）Linux内核链表接口 （1）删除 Linux中删除的代码也是类似的，通过_list_del来实现
9、list_del接口，读者可以自行分析以下代码段： static inline void _list_del(struct list_head * prev, struct list_head * next) next-prev = prev; prev-next = next; static inline void list_del(struct list_head *entry) _list_del(entry-prev, entry-next); entry-next = LIST_POISON1; entry-prev = LIST_POISON2; ,www.embedu.org,4
10、.2 树、二叉树、平衡树,4.2.1 树的定义 4.2.2 二叉树 4.2.3 平衡树 4.2.4 ARM Linux中红黑树使用实例,www.embedu.org,4.2.1 树的定义,树是由 n (n 0) 个结点组成的有限集合。如果 n = 0，称为空树；如果 n 0，则 有一个特定的称之为根的结点，它只有直接后继，但没有直接前驱；,除根以外的其它结点划分为 m (m 0) 个 互不相交的有限集合T0, T1, , Tm-1，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。,www.embedu.org,4.2.1 树的定义,节点
11、：表示树中的元素，包括数据元素的内容及其指向其子树的分支。 节点的度：节点的分支数。 终端节点（叶子）：度为0的节点。 非终端节点：度不为0的节点。 节点的层次：树中根节点的层次为1，根节点子树的根为第2层，以此类推。 树的度：树中所有节点度的最大值。 树的深度：树中所有节点层次的最大值。 有序树、无序树：如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。,www.embedu.org,4.2.1 树的定义,森林：是m（m0）棵互不相交的树的集合。 在树结构中，节点之间的关系又可以用家族关系描述，定义如下。 孩子、双亲：某个节点的子树的根称为这个节点的孩子，
12、而这个节点又被称为孩子的双亲。 子孙：以某节点为根的子树中的所有节点都被称为该节点的子孙。 祖先：从根节点到该节点路径上的所有节点。 兄弟：同一个双亲的孩子之间互为兄弟。 堂兄弟：双亲在同一层的节点互为堂兄弟。,www.embedu.org,4.2.2 二叉树,1）二叉树的定义 二叉树是一种有序树，它是节点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。它的特点是每个节点至多只有两棵子树（即二叉树中不存在度大于2的节点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。,www.embedu.org,4.2.2 二叉树,1）二叉树的定
13、义 （1）满二叉树 一棵深度为k且有2k1个节点的二叉树称为满二叉树。 （2）完全二叉树 若设二叉树的高度为h，则共有h层。除第h层外，其他各层（0h1）的节点数都达到最大个数，第h层从右向左连续缺若干节点，这就是完全二叉树。,二叉树可以采用两种存储方式： 顺序存储结构和链式存储结构,www.embedu.org,4.2.2 二叉树,2）二叉树的顺序存储 这种存储结构适用于完全二叉树，其存储形式为：用一组连续的存储单元按照完全二叉树的每个节点编号的顺序存放节点内容。,#define MAX_TREE_NODE_SIZE 100 typedef struct entry_type itemMAX
14、_TREE_NODE_SIZE; /* 根存储在下标为1的数组单元中 */ int n; /* 当前完全二叉树的节点个数 */ qb_tree;,这种存储结构的特点是空间利用率高、寻找孩子和双亲比较容易，但是插入和删除节点不方便。,www.embedu.org,4.2.2 二叉树,2）二叉树的链式存储 常见的二叉树节点结构： 其中，lchild和rchild是分别指向该结点左孩子和右孩子的指针，item是数据元素的内容，在C语言中的类型定义为： typedef struct _bt_node entry_type item; struct bt_node *lchild,*rchlid; bt
15、_node,*b_tree;,www.embedu.org,4.2.2 二叉树,2）二叉树的链式存储 通过非递归的方式构建一个顺序二叉树，二叉树中每个节点都是一个char型的数据，这个二叉树遵循以下规则。图4.14 实例构建的二叉树 所有右孩子的数值大于根节点。 所有左孩子的数值小于根节点。,这样，为了方便起见，先设定一个数据集合及构建顺序，如下所示（数据的构建顺序自左向右）：e、f、h、g、a、c、b、d。与此相对应的二叉树如图4.14所示。,www.embedu.org,4.2.2 二叉树,/*二叉树节点的结构体*/ struct _tree_node char data; struct
16、tree_node *lchild; struct tree_node *rchild; ; typedef struct _tree_node tree_node; /* 初始化二叉树的每个节点，在此处要注意将该节点的左右孩子都赋值为NULL */ void tree_init(tree_node *node) *node = (tree_node *)malloc(sizeof(tree_node); (*node)-lchild = (*node)-rchild = NULL; (*node)-data = 0; ,www.embedu.org,4.2.2 二叉树,/* 二叉树构建函数，data是要构建的节点的数值，node是根节点 */ void construct(char data, tree_node *node) int i; Node *temp_node = *node; while(temp_
