数据结构严蔚敏课件第10章

数据结构严蔚敏课件第10章•引言•数据结构基础概念•线性表•栈目•队列•树形结构录contents01引言背景介绍数据结构是计算机科学和软件工程领域的基础知识，是计算机程序设计的重要理论基础数据结构课程是计算机科学与技术专业的核心课程之一，对于培养学生的算法设计能力和解决实际问题的能力具有重要意义本章主要介绍树形结构中的二叉树及其应用，包括二叉树的定义、性质、存储结构、遍历算法以及二叉树的应用等章节目标01020304理解二叉树的遍历算法，学习二叉树在计算机科通过实践练习，培养学掌握二叉树的基本概念、包括前序遍历、中序遍学中的应用，如堆排序、生的算法设计和编程能性质和存储结构历和后序遍历二叉搜索树等力02数据结构基础概念数据结构定义01020304数据结构定义数据结构的组成数据元素数据项数据结构是数据之间的相互关数据结构包括数据元素、数据数据结构中的基本单位，表示数据元素中的具体内容，可以系的集合，包括数据的表示和项、数据类型、数据操作和数数据的最小单位是数值、字符、图像等操作据约束等部分数据类型分类010203基本数据类型自定义数据类型抽象数据类型如整型、浮点型、字符型用户根据需要自定义的数对数据类型的抽象描述，等据类型，如结构体、类等包括数据元素和相关操作数据结构的重要性提高数据存储效率提高软件可维护性合理的数据结构能够减少数据合理的数据结构能够使软件更的存储空间，提高存储效率加模块化、可维护和可扩展提高数据处理速度提高软件可靠性通过合理的数据结构，能够加合理的数据结构能够减少软件快数据的查找、插入、删除等中的错误和漏洞，提高软件的操作的速度可靠性03线性表线性表的定义线性表线性表是一种具有n个元素的有限序列，其中n大于0，每个元素有唯一的位置，即下标从0到n-1线性表的特性线性表具有一对一的映射关系，即每个元素在表中的位置是唯一的，且线性表中的元素个数是有限的线性表的实现方式数组实现链表实现动态数组实现使用数组来存储线性表中使用链表来存储线性表中结合数组和链表的优点，的元素，通过数组下标来的元素，每个元素包含数使用动态内存分配来创建访问和操作元素据域和指针域，通过指针和删除元素，具有更好的来链接各个元素灵活性和效率线性表的应用场景通讯录管理任务调度使用线性表来存储和管理通讯录中的使用线性表来存储和管理任务列表，联系人信息，方便查找、添加、删除按照任务优先级或时间顺序进行排序和修改联系人信息和调度日志管理使用线性表来存储和管理系统日志信息，按照时间顺序排列日志条目，便于查询和审计04栈栈的定义栈的定义栈是一种特殊的线性表，只允许在表的一端栈的特性后进先出（Last InFirst Out，LIFO）进行插入和删除操作栈的表示方法数组、链表等栈的常用操作push（入栈）、pop（出栈）、peek（查看栈顶元素）等栈的性质空栈与非空栈一个空的栈没有任何元素；非空的栈的容量栈至少有一个元素栈的最大容量取决于其实现方式栈的边界栈的插入和删除操作发生在固定的端点，称为栈顶栈的应用场景后进先出数据存储函数调用机制深度优先搜索例如括号匹配、表达式求值等函数调用的参数和返回地址可以使用栈来保存节点访问的状态，通过栈来保存和恢复避免重复访问05队列队列的定义01队列是一种特殊的线性表，只允许在表的前端进行删除操作，在表的后端进行插入操作02队列中的元素遵循先进先出（FIFO）的原则队列的性质队列具有先进先出（FIFO）的性质，队列中的元素不重复，即每个元素在即最早进入队列的元素将最先出队队列中只出现一次队列是一种特殊的线性表，其插入和删除操作分别在表的后端和前端进行，遵循严格的FIFO原则队列的应用场景•任务调度在多任务系统中，可以使用队列来管理任务的执行顺序，按照任务的优先级或到达时间将任务加入队列，然后按照队列的先进先出原则执行任务•网络通信在网络通信中，可以使用队列来管理数据的发送和接收当有新的数据包到达时，将其加入发送队列，按照先进先出的原则逐个发送数据包同时，接收端也可以使用队列来管理接收到的数据包，确保数据包的顺序正确•事件处理在事件驱动的系统中，可以使用队列来管理事件的触发和处理当有新的事件发生时，将其加入事件队列，系统按照先进先出的原则逐个处理事件•缓冲处理在输入输出系统中，可以使用队列作为缓冲区来暂时存储待处理的数据当数据量较大时，可以将数据加入队列进行缓冲，然后按照先进先出的原则逐个处理数据，避免数据丢失或处理不及时的情况发生06树形结构树形结构的定义树形结构是一种层次结构，其中每个节点可以有多个子节点，但只能有一个父节点树形结构通常用于表示具有层次关系的数据，例如组织结构、文件系统等树形结构的分类二叉树多叉树每个节点最多有两个子节点，通常称为左子节点和右子节每个节点可以有多个子节点点平衡树B树在二叉树中，如果每个节点的左子树和右子树的高度差不B树是一种自平衡的多路搜索树，能够保持数据有序，以超过1，则称为平衡树平衡树在查找、插入和删除操作便进行高效的查找、插入和删除操作中具有良好的性能树形结构的应用场景文件系统数据库索引文件系统通常采用树形结构来组织和管理文数据库索引通常采用树形结构来提高查询效件和目录率网页爬虫决策树网页爬虫使用树形结构来跟踪网页之间的链决策树是一种特殊的树形结构，用于表示基接关系于特征的分类或回归模型THANK YOU感谢观看。