数据结构与算法应用教程.ppt

书名：数据结构与算法应用教程 ISBN： 978-7-111-24128-7 作者：高佳琴 出版社：机械工业出版社 本书配有电子课件 数据结构与算法应用教程 高职高专 ppt 课件 数据结构与算法实用教程 主编 高佳琴 数据结构与算法应用教程 高职高专 ppt 课件 第1章 概 述 本章要点： 1)数据、数据元素、数据结构、数据的逻辑结构与物理结构 的概念以及逻辑结构与物理结构 间的关系。 2)算法的定义、特性，算法的时间复杂度和空间复杂度分析 。 3)C语言指针的定义、指针的基本操作、动态分配函数等。 本章难点： 1)数据的逻辑结构和物理结构的关系。 2)算法的时间复杂性和空间复杂性分析。 数据结构与算法应用教程 高职高专 ppt 课件 1)从具体问题分析入手找出解决该问题的方法(数据模型)。 2)设计解决该问题的具体步骤(算法)。 3)选择程序设计语言和数据类型，编写代码(源程序)，源程序经 编译后得到可直接运行的程序(目标程序)。 第1章 概 述 图1-1 计算机解决问题的一般步骤 数据结构与算法应用教程 高职高专 ppt 课件 第1章 概 述 1.1 什么是数据结构 1.2 基本概念和术语 1.3 算法和算法分析 1.4 C语言基础 数据结构与算法应用教程 高职高专 ppt 课件 1.1 什么是数据结构 从一个简单的学生档案管理系统入手，引入数据结构的相 关概念。 问题描述：学生档案管理系统的主要功能包括：输入、修 改、插入、删除、查找学生档案，并进行数据的统计(如统 计男、女生比例等)。 将存储顺序与逻辑顺序保持一致的存储结构就是顺序存储 结构，如图1-2所示，而在用链表存储信息时，信息在内存 中存储的顺序与逻辑顺序不要求一致。它是通过为每一条 记录增加一个存储下一个学生信息地址的信息项来表示学 生的次序，这就是链式存储结构，如图1-3所示。 数据结构与算法应用教程 高职高专 ppt 课件 1.1 什么是数据结构 图1-3 链式存储结构 数据结构与算法应用教程 高职高专 ppt 课件 1.2 基本概念和术语 (1)数据 (2)数据元素 (3)数据项 (4)数据逻辑结构 (5)数据物理结构 (6)数据类型 数据结构与算法应用教程 高职高专 ppt 课件 (1)数据 指所有能输入到计算机中并能被计算机程序处理的符号的 总称。 数据结构与算法应用教程 高职高专 ppt 课件 (2)数据元素 在计算机程序中通常作为一个整体进行考虑和处理的基 本数据单位。一个数据元素可以由若干个数据项组成， 也可以只由一个数据项组成。数据元素又被称为元素、 结点或记录。 数据结构与算法应用教程 高职高专 ppt 课件 (3)数据项 数据项是不可分割的、具有独立意义的最小数据单位，数据项有 时也被称字段或域。 学生档案信息表中每一行记录了一个学生的档案信息，在数据操 作中作为一个整体考虑，对应为一个数据元素。这个记录中包含 有学号、姓名、性别等若干个数据项。数据操作的基本单位是数 据元素，如学生的插入或删除一定是对应于一个学生的全部信息 ，而不是对应于其中的某个数据项。 结论：数据、数据元素、数据项实际上反映了数据组织的三个层 次：数据可由若干个数据元素构成，而数据元素又可以由一个或 若干个数据项组成。 (4)数据逻辑结构 1)线性结构。 2)非线性结构。 树形结构是指该结构中的数据元素之间存在一对多的关系，如图1-5b所示 。其特点是该结构中除了有一个被称为根的结点没有前趋外，其余元素有且 只有一个直接前趋，可以有多个后继。 图形结构(网状结构)是最复杂的数据结构，数据元素之间存在多对多联系， 如图1-5c所示。其特点是该结构中任何元素都可以有多个直接前趋，也可以 有多个后继。 是指数据元素之间的抽象关联方式。数据元素之间存在的一 种或多种特定的关系被称为数据的逻辑结构。 (4)数据逻辑结构 图1-4 例1-2的逻辑结构表示图 图1-5 三种基本逻辑结构 a)线性结构 b)树形结构 c)图形结构 (4)数据逻辑结构 (4)数据逻辑结构 图1-6 例1-3逻辑结构图 (5)数据物理结构 数据在计算机存储器中的存放方式称为数据的物理结构，简称存 储结构。数据元素在计算机中主要有两种不同的存储方法：顺序 存储结构和链式存储结构。 (6)数据类型 在用高级语言编写的程序中，所有的变量、常量或表达式都具有 确定的数据类型。数据类型包含了数据的取值范围及基本操作运 算，可以这样认为：数据类型是程序设计语言中已经实现了的数 据结构。 1.3 算法和算法分析 1.3.1 算法及其描述 1.3.2 算法性能和复杂度分析 1.3.1 算法及其描述 1.算法的定义及其特征 2.算法的描述方法 1.算法的定义及其特征 1) 正确性。算法必须解决具体的问题，完成所期望的功能，给出 正确的输出。 2) 确定性。算法执行的每一步和下一步必须确定，不能有二义性 。 3) 有限性。一个算法必须由有限步组成。无限步组成的算法无法 用计算机程序来实现，因此算法必须可以终止，不能进入死循环 。 4) 输入。一个算法有零个或多个输入。 5) 输出。一个算法有一个或多个输出。 2.算法的描述方法 (1)图形工具 用一些基本符号表示处理、输入、输出等操作，比较流 行的框图有传统流程图和结构化流程图，如图1-7所示，其优点是直观 、易懂。 图1-7 流程图 a)传统流程图 b)结构化流程图 2.算法的描述方法 图1-8 例1-4流程图 a)传统流程图 b)结构化流程图 2.算法的描述方法 (2)伪语言描述 伪语言与高级程序设计语言有些类似，有比较严格的 外语法，如用ifelse表示选择结构，用while表示循环结构，对内语 法如变量定义等无明确要求。 (3) C语言编写的程序或函数 这是可在计算机上运行并获得结果的算 法，使给定问题能在有限时间内被求解，通常这种算法也称程序。 1.3.2 算法性能和复杂度分析 解决一个问题可以有多种算法。例如对一组数据排序，可给出6种甚至更多种 排序算法，有的排序算法适合于元素个数少的序列，有的适合于元素个数多 的序列，有的则适合于基本有序的排序。因此在一个算法设计好以后，还需 要对其进行分析，确定一个“好”的算法。下面讨论算法设计的目标和算法分 析的方法。 1) 正确性。 2) 易读性。 3) 健壮性。 合法输入。当输入的三条边a，b，c满足构成三角形的条件(a+bc，a+cb ，b+ca)时，算法应能得到正常的结果。 非法输入。当输入的三条边a，b，c有不满足构成三角形的条件(a+bc， a+cb，b+ca)时，算法应给出相应的提示信息。 4) 高效率。 1.4 C语言基础 1.4.1 数组 1.4.2 指针 1.4.3 结构体类型 1.4.4 C程序的调试方法 1.4.1 数组 1.一维数组的定义 2.一维数组元素的引用 1.一维数组的定义 1) 数组名的命名规则与普通变量名相同。 2) 常量表达式表示数组元素的个数，用方括号括起来。 3) 定义了一维数组后，系统给该一维数组分配一组连续的存储空间， 数组名表示该段存储空间的首地址。 2.一维数组元素的引用 1) 数组不能整体引用，必须单个引用。 2) 数组元素的下标可以是常量、变量或表达式。 3) C程序规定，数组元素下标的下界为0，上界为数组长度减1。 4) 人们习惯使用单循环(for循环结构)，通过控制循环变量对一维数组 进行访问。 1.4.2 指针 1.指针变量定义 2.指针引用 3.指针与数组 4.指针作为函数参数 1.指针变量定义 1) “ * ”表示其后定义的变量是一个指针变量。 2)基类型表示指针变量所指向的数据类型，即一个指针变量只能存储 同一种数