模块7 数据结构与算法思维.pptxVIP

中国水利水电出版社大学计算机基础（第二版）/softdown//course/202341818.html

单位名称：主讲老师：模块7数据结构与算法思维

学习目标3认知目标能够掌握线性列表、堆栈、队列、树等结构的基本概念与特征能够了解并掌握算法的概念、特征、复杂度以及算法的三种基本结构情感目标培养学生的逻辑思维能力和实践能力。认识算法思维的重要性。提高今后学习相应课程的兴趣。技能目标能实现二叉树的前序遍历、中序遍历与后序遍历能够掌握线性列表、堆栈与队列与二叉树的主要应用

单元1数据结构单元2算法基础知识学习内容

单元1数据结构知识1数据结构基本概念知识2线性表知识3栈和队列知识4树和二叉树5

知识1数据结构基本概念6数据结构是相互之间存在一种或多种特定关系的数据元素的集合。通常有下列四类基本结构： （1）集合； （2）线性结构； （3）树形结构； （4）图状结构或网状结构。

知识1数据结构基本概念7数据结构有逻辑结构和物理结构之分：逻辑上的数据结构反映成分数据之间的逻辑关系；物理上的数据结构反映成分数据在计算机内部的存储安排，它是数据结构的实现形式。数据结构作为一门学科，研究的内容主要包括数据的逻辑结构、数据的物理存储结构及对数据的操作（或算法）三个方面。

知识2线性表8线性表是一个含有n≥0个结点（数据元素）的有限序列，其中的结点，有且仅有一个开始结点和一个终端结点，其他结点有且仅有一个前驱和一个后继结点。

知识2线性表9线性表中必存在唯一的一个“第一元素（Element1）”。集合中必存在唯一的一个“最后元素（Element4）”。除最后一个元素之外，均有唯一的后继。除第一个元素之外，均有唯一的前驱。

知识2线性表10线性表可分为广义线性表与限制线性表。 广义线性表：可以在任何位置插入与删除数据； 限制线性表：只能在列表两端增加与删除数据，如堆栈与队列。

知识3栈和队列11堆栈是一种限制性线性表，该列表数据元素的添加与删除只能在列表的一端完成，这一端被称为栈顶。堆栈中的数据元素具有一个特性，最后一个放入堆栈中的物体总是被最先拿出来，这个特性通常称为后进先出（LastInFirstOut，LIFO）。数据元素n…………数据元素4数据元素3数据元素2数据元素1栈顶指示器

知识3栈和队列12队列可以看做是一种限制线性表，队列列表只允许在数据表的前端进行删除操作，而在数据列表的后端进行插入操作。在队列中，进行插入操作的端称为队尾（rear），进行删除操作的端称为队头（front）。队列具有先进先出（FirstInFirstOut，FIFO）的特点。

知识3栈和队列13入列操作出列操作

知识4树和二叉树树是一种数据结构，它是由n（n≥0）个有限结点组成一个具有层次关系的数据集合。

知识4树和二叉树与结点相连的分支数目称为结点的度。指向结点的分支称为入度分支，离开结点的分支称为出度分支。入度与出度分支的总和就是结点的度。图中的B的出度，E的入度，F的度各是多少呢？

知识4树和二叉树二叉树——概念每个结点最多有两个子树的有序树，这两个子树分别称为左子树和右子树，而每一棵子树又是二叉树。16空二叉树仅有根节点的二叉树右子树为空的二叉树左子树为空的二叉树左右字数均非空的二叉树

知识4树和二叉树17性质1：二叉树的第i层上至多有2i-1（i?1）个结点。性质2：深度为H的二叉树中至多2H-1个结点。性质3：具有n个结点的二叉树的最小高度H为[log2n]+1。

知识4树和二叉树18前序遍历访问根结点前序遍历左子树前序遍历右子树中序遍历中序遍历左子树访问根结点中序遍历右子树后序遍历后序遍历左子树后序遍历右子树访问根结点

知识4树和二叉树19前序遍历：ABCDEF

知识4树和二叉树20中序遍历：CBDAEF

知识4树和二叉树21后序遍历：CDBFEA

单元2算法基础知识知识1算法基本概念知识2算法的基本特征与设计原则知识3算法复杂度知识4算法的基本结构知识5常用算法介绍22

知识1算法基本概念算法（Algorithm）是指解决问题的方法和步骤，是对解决某一问题方案的准确描述。如：求圆的面积问题（s=πr2），把这个问题交给计算机来处理，过程为先输入圆的半径，然后按面积计算公式计算，最后输出计算结果。输入圆的半径计算圆的面积，利用S=π*r2输出圆的面积

知识2算法的基本特征与设计原则算法的基本特征与设计原则：

知识3算法复杂度时间