高职数据结构课件

第1章绪论学习目标与要求：了解数据、数据元素、数据项、数据对象、数据类型及抽象数据类型等根本概念。掌握数据结构和算法的概念。掌握数据结构的逻辑结构、存储结构和数据操作(运算)3个方面的概念及其相互之间的关系。掌握算法的评价标准。分析算法的时间复杂度，评价一个算法的好坏。21.1引言1968年美国唐·欧·克努特(DonaldE.Knuth)开创了数据结构的最初体系。数据结构是一门介于数学、计算机硬件和计算机软件三者之间的核心课程(如图1.1所示)。31.1引言为了使读者对数据结构有一个感性的认识，下面给出几个数据结构的例如，读者可以通过这些例如去理解数据结构的概念。【例如1】职工根本情况表。参见教材P2【例如2】井字棋对弈问题。【例如3】教学方案编排问题。41.2根本概念与术语数据(Data)是对客观事物的一种符号表示，是指所有能输入到计算机中并被计算机程序加工处理的符号的总称。数据元素(DataElement)是组成数据的根本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项(DataItem)是数据不可分割的、具有独立意义的最小数据单位，是对数据元素属性的描述。数据、数据元素、数据项反映了数据组织的3个层次，即数据可以由假设干个数据元素组成，数据元素又由假设干个数据项组成。数据对象(DataObject)是性质相同的数据元素的集合。数据类型(DataType)是指一组结构相同的值构成的值集(类型)和定义在这个值集(类型)上的操作集。数据结构(DataStructure)是指数据元素之间的逻辑关系和这种关系在计算机中的存储表示，以及在这种结构上定义的运算。51.2根本概念与术语1.逻辑结构(1) 线性结构。(2) 集合结构。(3) 树形结构。(4) 图状结构。数据的四种根本逻辑结构如图1.4所示。61.2根本概念与术语2.存储结构(1) 顺序存储结构是指把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来表达。(2) 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，结点之间的逻辑关系由附加的指针域来表达。(3) 索引存储结构是用结点的索引号来确定结点的存储地址。71.2根本概念与术语3.数据的运算对几种常用的运算进行简要介绍。(1)检索：即在数据结构里查找满足一定条件的结点，一般是给定某字段的值，找具有该字段值的结点。(2)插入：即往数据结构里增加新的结点。(3)删除：把指定的结点从数据结构里去掉。(4)更新：改变指定结点的一个或多个字段的值。81.3抽象数据类型首先我们了解一下在程序设计语言中出现的各种数据类型。91.3.1数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称。在高级程序设计语言中，数据类型可分为两类：一类是原子类型，另一类那么是结构类型。在某种意义上，数据结构可以看成是“一组具有相同结构的值”，而数据类型那么可被看成是由一种数据结构和定义在其上的一组操作所组成的。101.3.2抽象数据类型概述抽象数据类型(AbstractDataType，ADT)，是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描述。111.3.2抽象数据类型概述抽象数据类型的形式化定义如下：ADT=(D,S,P)D={数据对象}S={D上的关系集}P={对D的根本操作集}定义形式：ADT抽象数据类型名称{数据对象：…数据关系：…根本操作：操作名1：…操作名n：}ADT抽象数据类型名称121.4算法和算法分析在计算机领域，一个算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构的根底上实施的一种运算。由于数据的逻辑结构和存储结构不是唯一的，所以处理同一个问题的算法也不是唯一的；即使对于具有相同逻辑结构和存储结构的问题而言，由于设计思想和设计技巧不同，编写出来的算法也不大相同。学习数据结构这门课程的目的，就是要学会根据实际问题的需要，为数据选择适宜的逻辑结构和存储结构，进而设计出合理和实用的算法。131.4.1算法的根本概念1.算法2.算法的特征(1) 有穷性。(2) 确定性。(3) 可行性。(4) 有输入。(5) 有输出。3.算法与程序的区别(1) 一个算法必须在有穷步之后结束，一个程序不一定满足有穷性。(2) 程序中的指令必须是机器可执行的，而算法中的指令那么无此限制。(3) 算法代表了对问题的求解过程，而程序那么是算法在计算机上的实现。(4) 算法和数据结构是相辅相成的。141.4.1算法的根本概念4.算法的设计目标(1) 正确性。(2) 可读性。(3) 健壮性。(4) 高效率。(5) 低存储量需求。151.4.1算法的根本概念5.算法的描述(1) 自然语言(2) 流程图(3) 高级程序设计语言(4) 类语言161.4.2算法的时间复杂度一个程序的时间复杂度(TimeComplexity)是指程序运行从开始到结束所需要的时间。一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。定义(大O记号)：如果存在两个正常数c和n0，使得对所有的n,n≥n0，有：f(n)≤cg(n)那么有：f(n)＝Ο(g(n))使用大O记号表示的算法的时间复杂度，称为算法的渐近时间复杂度(AsymptoticComplexity)。171.4.3算法的空间复杂度算法的空间复杂度(SpaceComplexity)是指算法从开始运行到运行结束所需的存储空间，即算法执行过程中所需的最大存储空间。类似于算法的时间复杂度，算法的空间复杂度通常也是采用一个数量级来度量。记作：S(n)=O(g(n))，称S(n)为算法的渐近空间复杂度。算法运行所需的存储空间包括以下两局部：(1) 固定局部。(2) 可变局部。18本章小结(1) 数据结构研究的三方面内容是数据的逻辑结构、数据的存储结构和对数据的运算。数据的逻辑结构可分为集合、线性、树和图四种根本结构。数据的存储结构有顺序、链式、索引和散列四种存储结构。(2) 算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法具有有穷性、确定性、可行性、输入、输出特性。(3) 一个好的算法