《嵌入式Linux C语言程序设计基础教程 教学课件 ppt 作者 华清远见嵌入式学院 冯利美 冯建 第11章 嵌入式linux内核常见数据结构》由会员分享，可在线阅读，更多相关《嵌入式Linux C语言程序设计基础教程 教学课件 ppt 作者 华清远见嵌入式学院 冯利美 冯建 第11章 嵌入式linux内核常见数据结构（30页珍藏版）》请在金锄头文库上搜索。
1、第11章嵌入式linux内核常见数据结构,www.embedu.org,本章的要求,熟悉内核中的链表 熟悉内核中的树 熟悉内核中的哈希表,www.embedu.org,链表,链表是一种常见的重要数据结构，它可以动态地进行存储分配，根据需要开辟内存单元，还可以方便地实现数据的增加和删除。链表中的每个元素都由两部分组成：数据域和指针域。 数据域用于存储数据元素的信息，指针域用于存储该元素的直接后继元素的地址。其整体结构就是用指针链接起来的线性表,www.embedu.org,链表,单向链表 单向链表的每个节点中除数据域以外还有一个指针域，用来指向其后续节点，其最后一个节点的指针域为空（NULL）。
2、 单向链表由头指针唯一确定，因此单向链表可以用头指针的名字来命名，头指针指向单向链表的第一个节点。 在用C语言实现时，首先说明一个结构类型，在这个结构类型中包含一个（或多个）数据成员以及一个指针成员，如下所示。 typedef struct _link_node element_type data; /* element_type为有效数据类型*/ struct _link_node *next; link_node; typedef link_node *link_list;,链表,双向链 在单向链表中，每个节点中只包括一个指向下个节点的指针域，因此要在单向链表中插入一个新节点，就必须从链表
3、头指针开始逐个遍历链表中的节点。双向链表与单向链表不同，它的每个节点中包括两个指针域，分别指向该节点的前一个节点和后一个节点，如下图：,www.embedu.org,5,链表,循环链表 单向链表的最后一个节点的指针域为空（NULL）。如果将这个指针利用起来，以指向单向链表的第一个节点，就能组成一个单向循环链表，如下图,www.embedu.org,6,树,树是由n (n 0)个节点组成的有限集合。如果n = 0，称为空树；如果n0，则 有一个特定的称之为根的节点，它只有直接后继，但没有直接前驱； 除根以外的其他节点划分为m (m 0)个互不相交的有限集合T0, T1, , Tm-1，每个集合又
4、是一棵树，并且称之为根的子树。每棵子树的根节点有且仅有一个直接前驱，但可以有0个或多个直接后继。,www.embedu.org,7,树,与树相关的定义如下。 节点：表示树中的元素，包括数据元素的内容及其指向其子树的分支。 节点的度：节点的分支数。 终端节点（叶子）：度为0的节点。 非终端节点：度不为0的节点。 节点的层次：树中根节点的层次为1，根节点子树的根为第2层，依此类推。,www.embedu.org,8,树,与树相关的定义如下。 树的度：树中所有节点度的最大值。 树的深度：树中所有节点层次的最大值。 有序树、无序树：如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，
5、否则称为无序树。 森林：是m（m0）棵互不相交的树的集合。,www.embedu.org,9,二叉树,二叉树是一种有序树，它是节点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。它的特点是每个节点至多只有两棵子树（即二叉树中不存在度大于2的节点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。,www.embedu.org,10,www.embedu.org,二叉树,二叉树的性质 ： 二叉树第i（i1）层上的节点最多为2i-1个。 深度为k（k1）的二叉树最多有2k1个节点。 在任意一棵二叉树中，树叶的数目比度数为2的节点的数目多一
6、。 总节点数为各类节点之和：n = n0 + n1 + n2 总节点数为所有子节点数加一：n = n1 + 2*n2 + 1 故得：n0 = n2 + 1 ; 满二叉树 ：深度为k（k1）时有2k1个节点的二叉树。 完全二叉树 ：只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。 具有n个节点的完全二叉树的深度为 （log2n）1或log2(n+1)。,www.embedu.org,二叉树,二叉树的存储 ： 顺序存储结构 ：完全二叉树节点的编号方法是从上到下，从左到右，根节点为1号节点。设完全二叉树的节点数为n，某节点编号为i 当i1（不是根节点）时，有父节点，其
7、编号为i/2; 当2*in时，有左孩子，其编号为2*i ,否则没有左孩子，本身是叶节点; 当2*i1n时，有右孩子，其编号为2*i+1 ,否则没有右孩子； 当i为奇数且不为1时，有左兄弟，其编号为i-1,否则没有左兄弟； 当i为偶数且小于n时，有右兄弟，其编号为i1,否则没有右兄弟；,www.embedu.org,二叉树,有n个节点的完全二叉树可以用有n+1个元素的数组进行顺序存储，节点号和数组下标一一对应，下标为零的元素不用。 利用以上特性，可以从下标获得节点的逻辑关系。不完全二叉树通过添加虚节点构成完全二叉树，然后用数组存储，这要浪费一些存储空间。,www.embedu.org,浪费空间,
8、二叉树,www.embedu.org,二叉树,链式存储结构 ： typedef int datatype ; /*定义数据类型*/ typedef struct node; /*定义二叉树节点的内部结构*/ datatype data ; /*数据域*/ struct node *lchild ,*rchild ; /*指向左孩子和右孩子的指针*/ bitree ; /*二叉树节点类型*/ bitree *root ; /*定义指向二叉树的指针*/ 二叉树由根节点指针决定。,www.embedu.org,二叉树,www.embedu.org,二叉树的遍历,二叉树的遍历 遍历 ：沿某条搜索路径周
9、游二叉树，对树中的每一个节点访问一次且仅访问一次。 “遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。,www.embedu.org,二叉树的遍历,由于二叉树的递归性质，遍历算法也是递归的。三种基本的遍历算法如下 ： 先访问树根，再访问左子树，最后访问右子树； 先访问左子树，再访问树根，最后访问右子树； 先访问左子树，再访问右子树，最后访问树根；,www.embedu.org,例如：,先序序列：,中序序列：,后序序列：,A B C D E F
10、 G H K,B D C A E H G K F,D C B H K G F E A,www.embedu.org,二叉树的遍历,先序遍历算法 若二叉树为空树，则空操作；否则 访问根结点 先序遍历左子树 先序遍历右子树,www.embedu.org,二叉树的遍历,先序遍历算法 void PREORDER ( bitree *r) if ( r = = NULL ) return ; /空树返回 printf ( “ %c ”,r-data ) /先访问当前结点 PREORDER( r-lchild ); /再访问该结点的左子树 PREORDER( r-rchild ); /最后访问该结点右子树
11、 ,www.embedu.org,PREORDER ( bitree *r) if ( r = = NULL ) return ; printf ( “ %c “,r-data ); PREORDER ( r-lchild ); PREORDER ( r-rchild ); ,返回,返回,返回,返回,A,C,B,D,返回,先序序列：A B D C,二叉树的遍历,www.embedu.org,二叉树的遍历,中序遍历算法 若二叉树为空树，则空操作；否则 中序遍历左子树 访问根结点 中序遍历右子树,www.embedu.org,二叉树的遍历,中序遍历算法 void INORDER ( bitree
12、*r) if ( r = = NULL ) return ; /空树返回 INORDER( r-lchild ); /先访问该结点的左子树 printf ( “ %c ”,r-data );/再访问当前结点 INORDER( r-rchild ); /最后访问该结点右子树 ,www.embedu.org,二叉树的遍历,后序遍历算法 若二叉树为空树，则空操作；否则 后序遍历左子树 后序遍历右子树 访问根结点,www.embedu.org,二叉树的遍历,后序遍历算法 void POSTORDER ( bitree *r) if ( r = = NULL ) return ; /空树返回 POSTO
13、RDER( r-lchild ); /先访问该结点的左子树 POSTORDER( r-rchild ); /再访问该结点右子树 printf ( “ %c ”,r-data );/最后访问当前结点 ,www.embedu.org,二叉树的遍历,遍历的路径相同，均为从根节点出发，逆时针沿二叉树的外缘移动，每个节点均经过三次。按不同的次序访问可得不同的访问系列，每个节点有它的逻辑前趋（父节点）和逻辑后继（子节点），也有它的遍历前趋和遍历后继（要指明遍历方式）。,www.embedu.org,二叉树的遍历,按编号遍历算法 ： NOORDER ( bitree *r) /*按编号顺序遍历算法*/ in
14、t front, rear; bitree *QN; if ( r = NULL ) return ; /*空树返回*/ for (rear=1;rearN; rear+) Qrear = NULL ; front = rear = 1; Qrear = r; while ( Qfront != NULL ) /*以下部分算法由学生完成设计*/ /*访问当前出队节点*/ /*若左孩子存在则左孩子入队*/ /*若有孩子存在则右孩子入队*/ /* front向后移动*/ ,www.embedu.org,例如： a+b*(c-d)-e/f 的二叉树表示。,先序（前缀表达式）,中序（中缀表达式）,后序（后缀表达式）,-+a*b-cd/ef,a+b*c-d-e/f,abcd-+ef/-,二叉树的遍历,www.embedu.org,实验,1分析Linux内核的链表机制，并编写一个实现简单链表功能的模块，包括链表的创建、插入、删除、查询、修改操作 2. 查找并分析在Linux内核中使用树和哈希表的功能。 3查找并分析在Linux内核中使用队列和堆栈的功能。,
