数据结构 第一章教学课件 .ppt

《数据结构 第一章教学课件 .ppt》由会员分享，可在线阅读，更多相关《数据结构 第一章教学课件 .ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构 第一章教学课件 第一章第一章 概述概述数据结构数据结构数据数据结结构的构的发发展史展史1968年，美国年，美国D.E.Kunth教授开创了数据教授开创了数据结构的最初体系，他的名著结构的最初体系，他的名著计算机程序设计计算机程序设计技巧技巧较为系统地阐述了数据的逻辑结构和存较为系统地阐述了数据的逻辑结构和存储结构及其操作。随着计算机科学的飞速发展储结构及其操作。随着计算机科学的飞速发展和应用领域的不断扩大，到和应用领域的不断扩大，到20世纪世纪80年代初期，年代初期，数据结构的基础研究日臻成熟，已成为一门完数据结构的基础研究日臻成熟，已成为一门完整的学科。整的学科。数据数据结结构的地

2、位构的地位 数据结构是介于数学、计算机硬件和计算数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序数据结构这一门课的内容不仅是一般程序设计（特别是非数值计算的程序设计）的基础，设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和应用程序的重要基础。库系统及其他系统程序和应用程序的重要基础。目目录录第一章第一章第一章第一章概述概述概述概述4 41 12 23 3 数据结构的作用和意义数据结构的作用和意义基本概念和术语基本概念

3、和术语面向对象的数据结构表示面向对象的数据结构表示算法和算法分析算法和算法分析总总体要求体要求了解数据结构的意义，数据结构在计算机领域的地了解数据结构的意义，数据结构在计算机领域的地位和作用；位和作用；掌握数据结构各名词、术语的含义和有关的基本概掌握数据结构各名词、术语的含义和有关的基本概念；数据的逻辑结构和存储结构之间的关系；念；数据的逻辑结构和存储结构之间的关系；了解使用了解使用JAVAJAVA语言对数据结构进行抽象数据类型的语言对数据结构进行抽象数据类型的表示和实现的方法；表示和实现的方法；了解算法的五要素；了解算法的五要素；掌握计算语句频度估算算法时间复杂度的方法；掌握计算语句频度估算

4、算法时间复杂度的方法；1.1数据数据结结构的作用和意构的作用和意义义u计算机处理数据时，必须解决四个方面的问题：计算机处理数据时，必须解决四个方面的问题：一一、如何在计算机中方便、高效地表示和组织数据；如何在计算机中方便、高效地表示和组织数据；二二、如何在计算机存储器（内存和外存）中存储数据；如何在计算机存储器（内存和外存）中存储数据；三三、如何对存储在计算机中的数据进行操作，可以有哪些如何对存储在计算机中的数据进行操作，可以有哪些操作，如何实现这些操作以及如何对同一问题的不同操作操作，如何实现这些操作以及如何对同一问题的不同操作方法进行评价；方法进行评价；四四、理解每种数据结构的性能特征，以

5、便选择一个适合于理解每种数据结构的性能特征，以便选择一个适合于某个特定问题的数据结构。某个特定问题的数据结构。【例例1-1】某公司有某公司有50名员，现在需要设计一个管名员，现在需要设计一个管理系统，完成对员工信息的查找、修改、插入或删理系统，完成对员工信息的查找、修改、插入或删除。除。【例例1-2】计算机和人对弈问题。计算机和人对弈问题。图图1.1 1.1 九宫格方盘对弈九宫格方盘对弈“树树”【例例1-3】田径比赛赛程安排问题。田径比赛赛程安排问题。在一名选手参加多个项目的情况下，这些在一名选手参加多个项目的情况下，这些项目不能同时开始，否则会产生冲突项目不能同时开始，否则会产生冲突。赛程安

6、排示意图赛程安排示意图总结总结1 1、非数值计算问题的数学模型非数值计算问题的数学模型主要主要是诸如表、是诸如表、树、图之类的数据结构树、图之类的数据结构。2 2、数据结构是一门研究非数值计算的程序设计数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系及问题中计算机的操作对象以及它们之间的关系及操作的学科。操作的学科。1.2 基本概念和基本概念和术语术语u1.2.1 基本概念和术语基本概念和术语1.1.数据数据数据数据即信息的载体，是对客观事物的符号表即信息的载体，是对客观事物的符号表示，凡能输入到计算机中并被计算机程序处理的示，凡能输入到计算机中并被计算机程序处理

7、的符号都可称之为符号都可称之为数据数据。图图1.3 1.3 数据范畴数据范畴2.2.数据元素数据元素数据元素数据元素是数据的基本单位，它在计算机处是数据的基本单位，它在计算机处理和程序设计中通常作为独立个体。理和程序设计中通常作为独立个体。数据元素数据元素数据项数据项3.3.数据对象数据对象数据对象数据对象是具有相同特征的数据元素的集合，是具有相同特征的数据元素的集合，是数据的一个子集。是数据的一个子集。数数据据对对象象4.4.数据结构数据结构数据结构数据结构简称简称 DS(Data Structure)DS(Data Structure)，是数据，是数据及数据元素的组织形式。及数据元素的组织

8、形式。四四类类基基本本结结构构集合：集合：数据元素除了同属于一个集合数据元素除了同属于一个集合数据元素除了同属于一个集合数据元素除了同属于一个集合外，它们之间没有其他关系。外，它们之间没有其他关系。外，它们之间没有其他关系。外，它们之间没有其他关系。线性结构：线性结构：一对一一对一一对一一对一。树型结构：树型结构：一对多一对多一对多一对多。图状结构或网状结构：图状结构或网状结构：多对多多对多多对多多对多。图图1.4 1.4 家用电器构成的集合结构家用电器构成的集合结构图图1.6 1.6 某院系组织构成的树型结构某院系组织构成的树型结构图图1.5 1.5 春季节气构成的线性结构春季节气构成的线性

9、结构图图1.7 1.7 学生选课系统中数据库设计采用的图状结构学生选课系统中数据库设计采用的图状结构5.5.数据类型数据类型数据类型数据类型是一组具有相同性质的操作对象以是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。及该组操作对象上的运算方法的集合。1.2.2 数据的数据的逻辑结逻辑结构构 数据的逻辑结构数据的逻辑结构(Logic Structure)Logic Structure)是从具体问是从具体问题抽象出来的数学模型，与数据在计算机中的具体题抽象出来的数学模型，与数据在计算机中的具体存储没有关系。数据的逻辑结构独立于计算机，是存储没有关系。数据的逻辑结构独立于计算机，是

10、数据本身所固有的特性。数据本身所固有的特性。数据逻辑结构数据逻辑结构线性结构线性结构非线性结构非线性结构集合集合树树图图数据结构可以表示成二元组数据结构可以表示成二元组B=(D,R)B=(D,R)。数据元素的集合数据元素的集合DD上的关系集上的关系集【例例1-8】一年四季可表示成一年四季可表示成 B1=(D1,R1)，其中，其中 D1=春春,夏夏,秋秋,冬冬，R1=,；续偶关系续偶关系 表示：春季之后的下一个季节表示：春季之后的下一个季节是夏季，反过来夏季的前一个季节是春季，是夏季，反过来夏季的前一个季节是春季，【例例1-9】某单位的管理关系可表示成某单位的管理关系可表示成B2=(D2,R2)

11、，D2D2=总经理，部门经理总经理，部门经理A A，部门经理，部门经理B B，组长，组长A A，组长，组长B B，组长，组长C C，组长，组长D D，职工，职工A A，职工，职工B B，职，职工工C C，职工，职工D D，职工，职工E E，职工，职工F F，职工，职工GG，R2R2=,A，B，C，D，A，B，C，D，E，F，G；图图1.81.8单位的管理关系单位的管理关系【例例1-10】A某的人际关系可以表示成某的人际关系可以表示成B3=(D3,R3)，其中其中D3D3=A=A某，某，B B某，某，C C某，某，D D某，某，E E某，某，F F某，某，GG某，某，HH某某，R3R3=A=,，

12、B,，C,，F；图图1.9 A1.9 A某人际关系某人际关系1.2.3 数据的物理数据的物理结结构构数据的物理结构数据的物理结构又称存储结构，有又称存储结构，有顺序和链式顺序和链式两两种不同的方式，种不同的方式，例例：一个有序的数字序列一个有序的数字序列（25，34，48，57，63）图图1.10 1.10 顺序存储结构示意图顺序存储结构示意图顺序存储的特点是数顺序存储的特点是数据元素在存储器的相据元素在存储器的相对位置来体现数据元对位置来体现数据元素相互间的逻辑关系素相互间的逻辑关系例例：字符序列：字符序列(a，b，c，d，e，f)图图1.11 链式存储结构示意图链式存储结构示意图链式存储结

13、构是通过链式存储结构是通过一组任意的存储单元一组任意的存储单元来存储数据元素的，来存储数据元素的，而这些存储单元可以而这些存储单元可以是连续的也可以是不是连续的也可以是不连续的。连续的。1.3 面向面向对对象的数据象的数据结结构表示构表示u1.3.1 Java面向对象基础面向对象基础/Circle.javapublic class Circle private double radius;public Circle(double r)radius=r;public double getPerimeter()return Math.PI*radius*2;类的声明类的声明成员变量成员变量定义成员

14、方法定义成员方法public class Test1public static void main(String args)Circle c=new Circle(2.5);System.out.println(c.getPerimeter();在类的外部引用类的成员通常必须使用对象名在类的外部引用类的成员通常必须使用对象名来引用，格式如下：来引用，格式如下：“对象对象.成员名成员名”。类的实例化类的实例化成员方法的引用成员方法的引用抽象类抽象类当类表达的是抽象概念，其运算处理也是抽象的当类表达的是抽象概念，其运算处理也是抽象的。例如例如：针对几何图形针对几何图形Shape类及其周长计算，可使

15、用类及其周长计算，可使用以下代码进行描述。以下代码进行描述。public abstract class Shape public abstract double getPerimeter();关键字关键字抽象类抽象类抽象成员方法抽象成员方法没有方法体没有方法体子类子类例如：例如：使用抽象类使用抽象类Shape定义定义Circle类的代码如下：类的代码如下：public class Circle extends Shapeprivate double radius;public Circle(double r)radius=r;public double getPerimeter(/重写重写Sh

16、ape类计算周长的抽象方法类计算周长的抽象方法return Math.PI*radius*2;父类父类抽象类的子类必抽象类的子类必须实现抽象类的须实现抽象类的抽象成员方法。抽象成员方法。/test2.javapublic class Test2 public static void main(String args)Shape s2=new Circle(3.5);System.out.println(s2.getPerimeter();省略部分代码省略部分代码.可以直接使用可以直接使用s2变量调用变量调用getPerimeter()方法，无须强制类型转换方法，无须强制类型转换为其子类型。为其

17、子类型。泛型类泛型类例如：例如：映射映射Map类就是典型的泛型类类就是典型的泛型类public class Map /指定类型参数指定类型参数 K k;V v;public void set(K key,V value)k=key;v=value;public V get()return v;Map a=new Map();a.set(China,中国中国);System.out.println(a.get();实现英文单词实现英文单词“China”向中向中文词汇文词汇“中国中国”的转换。的转换。u1.3.2 面向对象的抽象数据类型面向对象的抽象数据类型在传统的数据结构教材中，抽象数据类型通常

18、表在传统的数据结构教材中，抽象数据类型通常表示为以下格式。示为以下格式。ADT 抽象数据类型名抽象数据类型名数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT 抽象数据类型名抽象数据类型名本书使用用本书使用用Java泛型类泛型类表示的抽象数据类型表示的抽象数据类型u1.3.3 使用使用Java语言描述数据结构的优势语言描述数据结构的优势1.使用使用Java描述数据结构更加简单描述数据结构更加简单。2.Java的泛型机制更加适合数据结构的抽象的泛型机制更加适合数据结构的抽象表示表示。3.java.util提供多种数据结构，可以加速应用提供多种数据结构，可以加速应用系统开发系统开发

19、。1.4 算法和算法分析算法和算法分析 瑞士著名的计算机科学家、瑞士著名的计算机科学家、Pascal 语言发明者语言发明者沃思沃思(N.Wirth)教授提出：教授提出：程序程序 =算法算法 +数据结构数据结构 算法（算法（Algorithm）是指在有限的时间范围内，）是指在有限的时间范围内，为解决某一问题而采取的方法和步骤的准确完整的为解决某一问题而采取的方法和步骤的准确完整的描述，它是一个有穷的规则序列，这些规则决定了描述，它是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算。解决某一特定问题的一系列运算。u1.4.1 算法的基本概念算法的基本概念一个算法应该具备以下特征：一个

20、算法应该具备以下特征：有穷性、确定性、可行性、输入、输出有穷性、确定性、可行性、输入、输出u1.4.2 算法效率的度量算法效率的度量评价一个算法优劣的主要标准如下：评价一个算法优劣的主要标准如下：正确性、可读性、健壮性、运行时间、占用空间正确性、可读性、健壮性、运行时间、占用空间u1.4.3 算法效率分析算法效率分析1 1、时间复杂度、时间复杂度(1)事后统计的方法事后统计的方法(2)事前分析估算的方法事前分析估算的方法 受受机器的运行速度，编机器的运行速度，编译程序产生的目标代码译程序产生的目标代码的质量，数据的输入等的质量，数据的输入等的影响的影响 通常把算法中基本操作重复执行的次数（频度

21、）通常把算法中基本操作重复执行的次数（频度）作为算法的时间复杂度。记为：作为算法的时间复杂度。记为：算法运行所需时间算法运行所需时间T T表示为表示为n n的函数的函数f(n)是规模为是规模为n n的算法的算法 ，重，重复执行基本操作的次数复执行基本操作的次数 大部分情况下要准确地计算大部分情况下要准确地计算 T(n)T(n)是很困难的，是很困难的，一个算法的一个算法的“运行工作量运行工作量”通常是随问题规模的增长通常是随问题规模的增长而增长，故我们往往研究所谓的而增长，故我们往往研究所谓的“渐进时间复杂度渐进时间复杂度”，即当，即当n n 逐渐增大时逐渐增大时T(n)T(n)的极限情况。的极

22、限情况。一般把这种算法的渐进复杂度简称为时间复杂一般把这种算法的渐进复杂度简称为时间复杂度，常用度，常用数量级数量级的形式来表示，记为：的形式来表示，记为：OrderOrder（数量级）的第一个字母（数量级）的第一个字母表示为表示为【例例1-18】计算下列语句的时间复杂度计算下列语句的时间复杂度（1）x=x+1;（2）for(i=1;i=n;i+)x=x+1;常数阶常数阶线性阶线性阶（3）for(i=1;i=n;i+)for(j=1;j=n;j+)x=x+1;（4）i=1;while(i=n)i=5*i;平方阶平方阶对数阶对数阶常见常见函数函数的时的时间复间复杂度杂度增长增长率率2 2、空间复

23、杂度、空间复杂度 算法整个运行过程所占用的空间称算法的空间算法整个运行过程所占用的空间称算法的空间复杂度。记为：复杂度。记为：算法算法在计算机存储器内占用的存储空间主要算法算法在计算机存储器内占用的存储空间主要分为三部分：算法源代码本身占用的存储空间，算法分为三部分：算法源代码本身占用的存储空间，算法输入输出数据所占用的存储空间，算法运行过程中临输入输出数据所占用的存储空间，算法运行过程中临时占用的存储空间。时占用的存储空间。在对一个算法进行时间复杂度和空间复杂度的分在对一个算法进行时间复杂度和空间复杂度的分析时，往往二者不能兼顾，考虑好的时间复杂度，就析时，往往二者不能兼顾，考虑好的时间复杂

24、度，就得牺牲空间复杂度的性能，反之亦然。得牺牲空间复杂度的性能，反之亦然。性质相同的构成的集合性质相同的构成的集合 _本章是为以后各章讨论的内容作基本知识的准备。本章是为以后各章讨论的内容作基本知识的准备。本章小结：本章小结：数据数据数据数据 数据元素数据元素数据元素数据元素 个体个体_数据对象数据对象数据对象数据对象 加上数据元素加上数据元素 之间的关系之间的关系 数据结构数据结构数据结构数据结构 由关系不同分类由关系不同分类 集合结构集合结构 线性结构线性结构 树形结构树形结构 图状结构图状结构 加上加上 操作操作 抽象数据类型抽象数据类型抽象数据类型抽象数据类型 数据对象数据对象 数据关系数据关系 基本操作基本操作 映像映像 到到 内存内存 存储结构存储结构存储结构存储结构 顺序结构顺序结构顺序结构顺序结构 链式结构链式结构链式结构链式结构 算法算法算法算法 特性：特性：有穷性、确定性、可行性、输入、输出有穷性、确定性、可行性、输入、输出 衡量标准：衡量标准：正确性、可读性、健壮性、效率、存储量需求正确性、可读性、健壮性、效率、存储量需求 时间复杂度时间复杂度时间复杂度时间复杂度 空间复杂度空间复杂度空间复杂度空间复杂度