数据结构与算法应用教程.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)基类型表示指针变量所指向的数据类型，即一个指针变量只能存储同一种数据类型变量的地址。,2.指针引用,1)取址运算符&，其作用是获取变量所占用的存储单元的首地址。 2)间接访问运算符，其作用是通过指针变量访问它所指向的变量。,3.指针与数组,数组名代表数组首地址，属指针常量。用指针变量访问数组更加灵活、方便。 用指针变量p访问数组a比较方便，p+2表示数组元素a2的地址， *(p+2)与a2等价,4.指针作为函数参数,指针作为函数参数的作用是将一个变量的地址传递到函数的指针变量形参，共享对应的实参的存储单元，因此形参值的改变将引起实参值的改变。由于数组名代表指针常量，因此指针作函数参数，通常与数组的操作相关。,1.4.3 结构体类型,1.结构体类型的定义 2.结构体变量的定义 3.结构体成员的引用 4.指向结构体的指针变量,1.结构体类型的定义,1) 上述形式定义的结构体类型名为struct student，而非student。 2) 若想为结构体类型定义一个简单的名称，可使用typedef命令。 3) typedef命令的功能是给一种数据类型取个别名，命令格式为： 4)结构体类型在定义时，可直接使用typedef为自定义数据类型取名。,2.结构体变量的定义,如同标准数据类型int一样，自定义数据类型后，并没有在内存开辟存储空间，必须定义变量才能引用其成员数据项。结构体变量占用实际内存的大小可用sizeof(变量名|类型名)函数求出。,3.结构体成员的引用,1) 结构体变量的成员可以看成是与普通变量一样进行各种运算。 2)结构体成员本身是一个结构体类型时，可以通过逐层分解的方法找到最低层的成员。,4.指向结构体的指针变量,指向结构体的指针变量定义格式为： 结构体类型名*指针变量名；,1.4.4 C程序的调试方法,由于程序中存在着分支、循环等结构及复杂数据类型，因此造成了程序运行时的变化规律和其静态结构之间存在着一定的差异。数据结构中所描述的数据及算法比较复杂，程序规模也比一般C语言程序要大，因此仅靠阅读程序很难掌握程序运行过程中各变量值的动态变化，这就给程序调试带来了很大的困难。如果能够在程序运行过程中动态地显示程序执行的流向和各变量的值，将有助于读者了解程序的动态运行情况，从而更好、更快地调试程序。本书附录1介绍了Turbo C集成环境下的调试手段。,1.填空题,线性结构中，元素之间存在_关系；树形结构中，元素之间存在_关系；图形结构(网状结构)中，元素之间存在_关系。 (2) 算法的五个基本特征是：_。 (3) 评价算法的性能从算法效率的角度看主要从_及