![嵌入式LinuxC语言基础——ARMLinux内核常见数据结构.ppt_第1页](http://file.renrendoc.com/FileRoot1/2019-1/8/b1009070-2773-477a-8f44-8306c9809008/b1009070-2773-477a-8f44-8306c98090081.gif)
![嵌入式LinuxC语言基础——ARMLinux内核常见数据结构.ppt_第2页](http://file.renrendoc.com/FileRoot1/2019-1/8/b1009070-2773-477a-8f44-8306c9809008/b1009070-2773-477a-8f44-8306c98090082.gif)
![嵌入式LinuxC语言基础——ARMLinux内核常见数据结构.ppt_第3页](http://file.renrendoc.com/FileRoot1/2019-1/8/b1009070-2773-477a-8f44-8306c9809008/b1009070-2773-477a-8f44-8306c98090083.gif)
![嵌入式LinuxC语言基础——ARMLinux内核常见数据结构.ppt_第4页](http://file.renrendoc.com/FileRoot1/2019-1/8/b1009070-2773-477a-8f44-8306c9809008/b1009070-2773-477a-8f44-8306c98090084.gif)
![嵌入式LinuxC语言基础——ARMLinux内核常见数据结构.ppt_第5页](http://file.renrendoc.com/FileRoot1/2019-1/8/b1009070-2773-477a-8f44-8306c9809008/b1009070-2773-477a-8f44-8306c98090085.gif)
已阅读5页,还剩14页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
,嵌入式Linux C编程入门(第2版) (By Farsight),/,,第8章 嵌入式Linux C语言基础ARM Linux内核常见数据结构,本章目标 链表的基本概念 链表的基本操作方法 ARM Linux中如何使用链表 二叉树的基本概念 树的遍历方法 森林的基本概念 森林的遍历方法 平衡树的基本概念 ARM Linux中如何实现红黑树 哈希表的概念 哈希表的操作方法 ARM Linux中如何使用哈希表,,链表,链表是一种常见的重要数据结构,它可以动态地进行存储分配,根据需要开辟内存单元,还可以方便地实现数据的增加和删除。链表中的每个元素都由两部分组成:数据域和指针域。,,单链表的组织与存储,单向链表的每个节点中除信息域以外还有一个指针域,用来指向其后续节点,其最后一个节点的指针域为空(NULL)。,,单链表常见操作,节点初始化 测试数据是否存在 链表的插入与删除 将几个单链表合并,,双向链表的组织与存储,双向链表与单向链表不同,它的每个节点中包括两个指针域,分别指向该节点的前一个节点和后一个节点,,双向链表的常见操作,增加节点 删除节点,,循环链表,循环链表的组织结构与单链表非常相似,因此其操作与单链表也是一致的,惟一的差别仅在于在单链表中,算法判端到达链表尾的条件是pnext是否为空,而在双链表中,则是判断pnext是否等于头指针,,ARM Linux中链表使用实例,ARM Linux内核链表 Linux内核链表接口 声明和初始化 插入 删除,,树,树是n(n0)个节点的有限集合。若n=0,则称为空树;否则,有且仅有一个特定的节点被称为根,当n1时,其余节点被分成m(m0)个互不相交的子集T1、T2、.、Tm,每个子集又是一棵树,,二叉树,二叉树是另一种树型结构,它是节点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 它的特点是每个节点至多只有两棵子树(即二叉树中不存在度大于2的节点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。,,二叉树的顺序存储,顺序存储结构 链式存储结构,,二叉树的链式存储,typedef struct BTNode EntryType item; struct BTNode *lchild,*rchlid; BTNode,*BTree;,,二叉树的常见操作,遍历二叉树 统计二叉树中的叶子节点 统计二叉树中的高度,,平衡树,二叉树是一种非平衡树,各个子树之间的高度可能相差很大,这样就会造成平均性能的下降。 平衡树包括很多种类,常见的有B树、AVL树、红黑树等,,红黑树是指满足下列条件的二叉搜索树。 性质1:每个节点要么是红色,要么是黑色(后面将说明)。 性质2:所有的叶节点都是空节点,并且是黑色的。 性质3:如果一个节点是红色的,那么它的两个子节点都是黑色的。 性质4:节点到其子孙节点的每条简单路径都包含相同数目的黑色节点。 性质5:根节点永远是黑色的。,,红黑树插入节点的过程如下。 在树中搜索插入点。 新节点将替代某个已经存在的空节点,并且将拥有两个作为子节点的空节点。 新节点标记为红色,其父节点的颜色根据红黑树的定义确定,如果需要,对树作调整。,,哈希表的构造方法,构造哈希表实际上也就是构造哈希函数以确定关键值的存储位置,并能尽可能地减少
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《锦瑟》教学设计(甘肃省市级优课)语文教案
- 端午节活动幼儿园教案
- 二年级上册美术教案雄伟的塔 人美版
- 粉质仪项目可行性报告
- 年中国电子政务项目可行性报告
- Excel高级数据处理与分析(微课版)-电子教案
- 铁路通信工(线务维护)初级试卷三
- 2024-2029年钢筋弯管机行业市场现状供需分析及市场深度研究发展前景及规划投资研究报告
- 2024-2029年金属接线盒行业市场现状供需分析及市场深度研究发展前景及规划投资研究报告
- 2024-2029年酿造系统行业市场现状供需分析及市场深度研究发展前景及规划投资研究报告
- 盐油糖采购台账制度
- 非煤矿山救援技术竞赛理论考试题库200题(含各题型)
- 【语文】上海市世界外国语小学小学四年级下册期末试卷(含答案)
- 英文金曲“新”赏(一)智慧树知到课后章节答案2023年下青岛滨海学院
- 工伤预防培训服务投标方案
- 校本课程戏曲课程纲要加教案
- 初二学生自我陈述报告(16篇)
- 建设项目审计造价审计及案例分析
- superset用户使用经过流程介绍材料
- 树脂锚杆锚固剂标准及配方课件
- 现代邮政英语(English for Modern Postal Service)-南京邮电大学中国大学mooc课后章节答案期末考试题库2023年
评论
0/150
提交评论