计算机导论 第十章 数据结构

第十章 数据结构 面向职业 体现系统 重视实践 强化应用 计算机导论 扬州职业大学 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 第十章 数据结构 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 学习目标 了解数据结构的基本概念 掌握数据结构的典型应用 熟悉常见的查询和排序算法 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 1： 了解数据结构的基本概念 数据结构的基本概念 算法 算法的基本要素 算法效率的度量 算法设计的要求 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 1： 了解数据结构的基本概念 数据结构的基本概念 数据 数据元素 数据项 数据类型 数据结构 逻辑结构 集合数据 线性结构 树形结构 图形结构 图 10辑结构的基本类型 存储结构 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 1： 了解数据结构的基本概念 算法 算法的概念：是对特定问题求解操作步骤的准确而完整的描述 。 算法的特性： 可行性 确定性 有穷性 输入 输出 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 1： 了解数据结构的基本概念 算法的基本要素 算法对数据的运算和操作 运算和操作有：算术运算 、 逻辑运算 、 关系运算 、 数据传输四类 。 算法的控制结构 算法的功能不仅取决于所选用的操作 ， 还与算法的控制结构有很大关系 。 算法的控制结构指的是算法中各操作之间的执行顺序 。一般一个算法中可以有顺序 、 选择和循环三种基本控制结构组合而成 。 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 1： 了解数据结构的基本概念 算法效率的度量 衡量算法性能的过程叫算法分析 ， 通过对算法的分析可以获知完成同一任务的不同算法的优劣 。 对算法的性能分析主要集中在对算法时间复杂度和空间复杂度的衡量 。 算法的时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量 。 算法的空间复杂度 算法的空间复杂度 ， 一般指执行这个算法所需要的内存空间 。 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 1： 了解数据结构的基本概念 算法设计的要求 正确性 可读性 容错性 高效率和低存储量 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 2： 掌握数据结构的典型应用 线性表 栈 队列 树和二叉树 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 2： 掌握数据结构的典型应用 线性表 线性表概念 线性表特点 线性表的基本运算 线性表的顺序存储结构 顺序表的运算：插入结点的运算；删除结点的运算 线性表链式存储结构 线性链表的运算：线性链表结点的插入；线性链表的结点删除 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 2： 掌握数据结构的典型应用 栈 栈的概念 栈是一种特殊的线性表 ， 栈的插入和删除操作均在线性表的一端进行 。 允许进行插入和删除操作的一端称为栈顶 （ ， 另一端称为栈底 （ 。 栈的顺序存储和运算 入栈 退栈 读取栈顶元素 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 2： 掌握数据结构的典型应用 队列 队列简称队，它也是一种特殊的线性表。队列允许在表的一端进行插入，在表的另一端进行删除，允许插入的一端称为队尾，通常有一个队尾指针 许删除的一端称为队首。 通常有一个队首指针 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 2： 掌握数据结构的典型应用 树和二叉树 树的基本概念：是一种非常重要的非线性结构 。 树的几个特点 树的定义是一个递归定义； 树的根结点没有前件，其他结点有且只有一个前件，称为父结点； 树中任何一个结点，可以有 0个或多个后件，称为子结点。 树的术语 度：在树中 ， 一个节点拥有的后件数称为该结点的度 。 层次：结点的层次表示结点在树中的相对位置 。 树的深度：树的最大层次称为树的深度 。 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 2： 掌握数据结构的典型应用 树和二叉树 二叉树：二叉树是重要的树型结构 。 、 二叉树的特点： 二叉树可以为空树，不含有任何结点； 非空二叉树只有一个根结点； 二叉树是有序树，每个结点最多有两棵子树，分别称为左子树和右子树，允许树只有左或右子树。 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 3： 熟悉常见的查询和排序算法 查找技术 排序技术 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 3： 熟悉常见的查询和排序算法 查找技术 顺序查找 顺序查找是最简单、最基本的查找方法。线性顺序查找方式适用于顺序存储和链接存储的线性表。 二分查找 线性顺序查找方式适用于顺序存储的线性表。 在最坏的情况下，二分查找法需比较 顺序查找需比较 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 3： 熟悉常见的查询和排序算法 排序技术 所谓排序，是把一组无序数据整理成按值递增（或递减）的次序重新排列，使其成为一个按值大小排列的有序序列。 冒泡排序 简单插入排序 简单选择排序 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 3： 熟悉常见的查询和排序算法 冒泡排序 冒泡排序属于交换类排序方法。它是通过相邻数据元素中的比较，使得较小的值上升，较大的值沉到底部，逐步将线性表从无序调整为有序线性表。 冒泡排序方法如下： 对于 2，若逆序（ 2）则交换之，然后比较 直到 n。这时最大值到了最后（第 这称为一趟排序，其进行了 重复，但只比较到第 称为第二趟比较； 共进行 比较，完成整个排序。 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 3： 熟悉常见的查询和排序算法 简单插入排序 简单插入排序属于是插入类排序。所谓插入排序，就是将无序序列中的各个元素插入到已经有序的线性表中。 简单插入排序的基本思路：首先将待排序数据序列中的第一个数据元素作为一个有序表，从第二个数据元素开始，依次将数据元素插入到前边已排好序的序列中，直至全部数据序列有序。在最坏情况下，简单插入排序需要进行 n（ 。 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 任务 3： 熟悉常见的查询和排序算法 简单选择排序 简单选择排序的基本思想是：排序过程中，依次从待排序的数据序列中选择出值最小的元素、值次小的元素、 ，并分别将它们定位到序列左侧的第一个位置、第二个位置、 ，最后剩下一个值最大的数据元素位于序列的最后一个位置，从而使待排序的数据序列成为按值由小到大排列的有序序列。 第十章 数据结构 面向职业 体现系统 重视实践 强化应用 小结： 数据结构和算法是程序设计中两个重要问题。 线性表是最简单、最常用的一种数据结构 。 栈是一种特殊的线性表，采用“先进后出”或者“后进先出”方式操作。 队列是另一种特殊的线性表 ，允许在表的一端进行插入，在表的另一端进行删除。