计算机导论第10章数据结构讲述.ppt

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