大学计算机基础及实训教程第13章.ppt

大学计算机基础及实训教程 第13章 基本数据结构与算法 第13章 基本数据结构与算法 数据和数据结构 13.1 算法 13.2 基本的数据结构和算法 13.3 总结 13.4 数据 计算机是信息处理的工具，存储在计算机中的信息表现为数据。也就是说，数据是计算机存储和处理的对象。 计算机能直接识别的数据是“0”和“1”。 13.1 数据和数据结构 数据的类型 一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。如：数值类型，数值类型上的加、减、乘和除 13.1 数据和数据结构 数据结构 是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据的集合。 如: 学生(学号,姓名,性别,学院) 注意：每个学生的学号的值应该来自同一个数据类型，姓名,性别,学院等数据也类似。 13.1 数据和数据结构 数据结构 广义上数据结构的定义: 结构化的数据以及数据上的操作的总称。 如学生(学号,姓名,性别,学院)，以及在该值上进行增、删、改、查等操作。 13.1 数据和数据结构 根据数据的逻辑结构，把结构化的数据分为 线性表 堆栈 队列 树 13.1 数据和数据结构 第13章 基本数据结构与算法 算法 13.2 数据和数据结构 13.1 基本的数据结构和算法 13.3 总结 13.4 算法定义： 是在数据上的具体操作的描述，是为解决特定问题而规定的一系列操作，是描述解决问题的策略机制。如：在学生表上如何进行查询单个学生数据，这个查询操作思想的描述就是一个查询算法。 13.2 算法 常用的算法： 查找、排序等 递推法、递归法、穷举法、贪心算法、 分治法、回溯法等。 13.2 算法 算法性能评价： 算法时间复杂度：算法执行时，时间快慢的评价。 算法空间复杂度：算法执行时，所需存储空间的评价。 13.2 算法 第13章 基本数据结构与算法 基本的数据结构和算法 13.3 算法 13.2 数据和数据结构 13.1 总结 13.4 线性表 是n个类型相同的数据元素的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前件和一个直接后件。 如：英文字母表(A,B,…,Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素，每个元素之间存在唯一的顺序关系。 13.3 基本数据结构与算法 线性表上的常用操作： 查找 插入 删除 13.3 基本数据结构与算法 堆栈 栈又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。 栈顶、栈底 13.3 基本数据结构与算法 堆栈的操作： 入栈 出栈 13.3 基本数据结构与算法 队列 队列简称队，它也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。 13.3 基本数据结构与算法 队列的操作： 入队 出队 13.3 基本数据结构与算法 树的 定义： 树是树型结构的简称。 它是一种重要的非线性数据结构。 空树，即不含有任何结点。 13.3 基本数据结构与算法 树的 定义： 非空树，即至少含有一个结点。在一棵非空树中，它有且仅有一个称作根的结点，其余的结点可分为m棵(m≥0)互不相交的子树(即称作根的子树)，每棵子树(SubTree)又同样是一棵树。 13.3 基本数据结构与算法 树的举例： 13.3 基本数据结构与算法