数据结构（Java语言版）课件 第一章 绪论

数据结构（Java语言版）01为什么要学数据结构（1）如何将数据存储在计算机中---数据结构（2）用什么方法策略来解决问题---算法

为什么要学习数据结构？为什么要学习数据结构？N.Worth（尼古拉斯·沃斯）程序=算法+数据结构

数据结构是程序设计的重要理论基础。它是研究程序中非数值型数据以及它们之间的相互关系与操作的学科。学习其目的是为了能编写更好的“非数值计算”型的程序，理解程序逻辑和高效合理的数据表示。02课程主要内容本课程学习的主要内容1、绪论2、Java基础3、线性表4、栈和队列5、数组6、串7、树与二叉树8、图9、查找10、排序03第一章绪论【知识目标】

掌握数据结构中的常用术语；

熟练掌握线性结构、层次结构和图形结构的概念及特性；

了解算法的定义、特性以及描述规则；

掌握时间复杂度、空间复杂度的分析方法。【能力目标】

理解线性结构、层次结构和图形结构的特性的能力；

具备理解和分析时间复杂度和空间复杂度的能力。数据结构的分类：线性结构：结构中的数据元素之间存在一对一的关系。树形结构（层次结构）：结构中的数据元素之间存在一对多的关系。图形结构（网状结构）：结构中的数据元素之间存在多对多的关系。1.1线性结构【例】学生成绩表。如何将学生信息存储在计算机里并对其进行查找，修改，插入，删除等。【例】图书管理系统。如何将学校图书信息包括图书编号、书名、数量和价格等信息存储在计算机里并对其进行查找，修改，插入，删除等。树形结构（层次结构）【例】树形结构（层次结构）【例】计算机磁盘（以C盘为例）的目录结构如图所示：C盘根目录USERUSER1USER2

WINDOWSJAVADEBUGDOWNLOADSUS1US2WMPUBWMIILOGS图形结构（网状结构）【例】最短路径问题。顶点表示城市，顶点之间的连线和数据表示距离。各顶点之间是多对多的图形结构，如何求从一个顶点到另一个顶点的最短路径？1.2数据结构相关概念2．数据的相关概念数据分为数值型数据和非数值型数据。

数据：可以通过编码输入到计算机并能被计算

机识别、存储和处理的符号。数据结构相关概念数据元素：构成数据的基本单位。

通常在程序中作为一个整体进行考虑和处理。

在不同的条件下，数据元素又可称为记录、结点、顶点等。数据结构相关概念数据项：数据结构中的最小单位。当数据元素由多个项构成时，其每个分项称为数据项。数据结构相关概念数据对象：是指相同性质的数据元素构成的集合。例：学生信息表中的性别为男的各条记录同属于一个数据对象。数据结构相关概念数据结构：是指具有某种联系的数据元素以及元素之间各种关系组成的集合。

1）具有某种联系的数据元素；2）数据元素之间具有的各种关系。

数据结构相关概念数据元素之间的各种关系称为结构。数据的结构可分为数据的逻辑结构、物理结构数据结构相关概念逻辑结构：数据元素相互之间的逻辑关系，它与数据的存储无关，独立于计算机而存在。数据结构相关概念物理结构（存储结构）：数据元素及其关系在计算机中的描述和表示。数据结构的描述数据结构是由两个集合构成的一个二元组<D，R>表示。数据结构的描述数据结构是由两个集合构成的一个二元组<D，R>表示。所有数据元素数据结构的描述数据结构是由两个集合构成的一个二元组<D，R>表示。所有数据元素数据元素的二元关系【例】树型结构中的圆圈代表数据元素，带箭头的连线表示元素之间的关系，试用二元组表示法表示该数树型结构。ABCEFGHIJ解：Tree=<D,R>D={A,B,C,E,F,G,H,I,J};R={<A,B>,<A,C>,<A,E>,<B,F>,<B,G>,<E,H>,<E,I>,<E,J>}数据结构相关概念数据类型（Datatype）:高级语言中为了更好地处理数据，引入不同的数据类型来处理的不同的数据。不同的数据类型有不同的存储空间和不同的操作方式。数据结构相关概念抽象数据类型（AbstractDataType）：对特定数学模型的数学描述。包括操作的数据，数据之间的关系，以及在该关系上可以实现的操作。即数据类型一般由元素、关系及操作三要素组成。数据结构相关概念ADT的一般定义形式是：ADT<抽象数据类型名>{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}数据结构相关概念ADT的一般定义形式是：ADT<抽象数据类型名>{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>描述出数据中包含的数据元素数据结构相关概念ADT的一般定义形式是：ADT<抽象数据类型名>{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>描述出数据中包含的数据元素描述数据元素的逻辑关系【例】写出线性表的抽象数据类型描述：ADTLinear_list{数据对象：所有ai性质相同，i=1，2，…，n（n≥1）逻辑结构：所有数据元素ai存在次序关系（ai，ai+1），a1无前驱，an无后继。基本操作：

InitList（）；/*建立一个空的线性表L*/Insert（L，i，x）；/*表L中的第i个位置处插入数据元素x*/Delete（L，i）；/*删除表L中第i个位置的元素*/……}；1.3算法及描述1.算法的概念算法（Algorithm）是指为完成某项任务或特定问题所设计的一种求解步骤的描述。算法可以理解成指令的有限序列，其中每一条指令可由一个或多个操作组成。1.3算法及描述说明：算法的含义与程序十分相似，但又有区别。算法是解决问题的步骤描述，而程序是算法的具体实现。算法代表了问题的解决方案，程序则是算法在计算机上的具体的实现。输入性、确定性、可执行性、有限性、输出性算法的基本特性算法的基本特性（1）输入性：一个正确的算法必须具有零个或多个数据输入，这些输入可根据具体的算法来实现。（2）确定性：构成算法的每一步必须有确切的含义，不能出现歧义。算法的基本特性（3）可执行性：算法中的每个步骤都可以通过具体的操作步骤来实现，不能设计一些不能实现的操作步骤。（可实现的）（4）有限性：一个算法必须在有限步骤之内结束或完成。（5）输出性：一个算法至少要有一个输出。算法的表示（1）自然语言

自然语言是描述算法最简单的方法，其优点是简单且便于的阅读；

缺点是转换成高级语言困难。算法的表示（2）高级语言 高级语言可以准确描述算法，也可以根据响应情况给出问题的解决方案，

缺点：和人们的自然思维有一定距离。算法的表示（3）类语言

类语言是介于高级程序设计语言和自然语言之间的一种语言。算法的表示（4）流程图

流程图是表示算法比较有效的方法之一，它采用框图形式，形象地描述从实际问题到抽象出的数学模型到最后的算法。1.3算法及描述常见的流程图样式处理框：特定一种操作输入输出框：数据输入或输出箭头：执行方向流程走向描述判断框：判断条件成立与否（决策过程描述）起止框：开始与结束联系描述1.3算法及描述判断是否是闰年程序流程图1.4算法效率分析

算法分析的目的在于选择合适的算法和改进算法。算法的效率主要由两个复杂度来评估：

1、时间复杂度

2、空间复杂度1.4算法效率分析算法执行时间：

等于所有语句执行时间的总和。

每条语句执行一次时间与硬件，语言种类有关，

一般只用语句执行的次数（语句频度）来作为算法执行时间的度量，通过比较语句频度的多少判断算法的优劣。1.4算法效率分析和算法执行时间相关的因素：

1、算法选用的策略2、问题的规模

3、编写程序的语言

4、计算机执行指令的速度

5、编译程序产生的机器代码的质量

2、算法的时间复杂度为了衡量随着问题规模n的增大，算法执行的时间的增大趋势，引入算法的渐进时间复杂度。

T（n）=O(f(n))1.4算法效率分析

voidsum(intn){s=0；

for(i=1;i<=n;i++)s=s+i；

}

/*求1到n的和*/

1.4算法效率分析时间复杂度不是精确的语句执行次数，而是估算的一个数量级，体现随着问题规模n增大，算法执行时间的增大趋势。

时间复杂度体现的是随着问题规模n的增大，算法执行时间的增大趋势，所以只考察受n影响最大的语句执行次数即可。

1.4算法效率分析

voidsum(intn){System.out.println(n)；}时间复杂度：Ο(1)1.4算法效率分析voidsum(intn){for(j=1;j<=n;j++)System.out.println(n)；}时间复杂度：Ο(n)1.4算法效率分析for(j=1;j<=n;j++)for(i=1;i<=n;i++)时间复杂度：Ο(n2)01248163264128256nT(n)10245122561286432168421012481632641282565121024nnlog2n2nn2n3nlog2n随着问题规模n的增大，算法消耗的时间也增大，但增长趋势不同。时间复杂度为n2

算法就比n3的好。1.4算法效率分析通常将Ο(1)称为常数阶，Ο(n)为线性阶，O(n2)为平方阶。算法还可能呈现的复杂度有：

对数阶Ο(log2n)，指数阶Ο(2n)等，不同数量级时间复杂度的关系有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)2、算法的空间复杂度：S(n)=O(g(n))随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。1.4算法效率分析2、算法的空间复杂度算法的存储量包括以下三部分：（1）输入数据所占空间；（2）程序本身所占空间；（3）辅助变量所占空间。练习1、数据结构包括数据的___结构和___结构。逻辑结构和物理结构练习2、数据结构的3种结构___、___、___。线性结构、层次结构（树形结构）、图形结构（网状结构）练习3