数据结构chapter1绪论剖析

《数据结构chapter1绪论剖析》由会员分享，可在线阅读，更多相关《数据结构chapter1绪论剖析（44页珍藏版）》请在金锄头文库上搜索。

1、1,数据结构 (Data Structure),2,数据结构,计算机相关专业的专业必修课。 学习操作系统等后续课程的基础。,课程性质：,通过研究各种数据结构的特点，学会为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法。 培养数据抽象能力，提高设计复杂程序的能力。,考核方式：,学习目标 ：,总成绩=平时成绩（40%）+考试成绩（60%） 平时成绩： 作业及实验（50%）+出勤（50%）,数据结构(C语言版) 严蔚敏编著 清华大学出版社,教材：,3,目 录（Content）,第1章 绪论 (Introduction) 第2章 线性表 (Linear lists) 第3章 栈和队列 (Sta

2、ck and Queue) 第4章 串 (String) 第5章 数组 (Arrays) 第6章 树 (Tree) 第7章 图 (Graph) 第9章 查找 (Searching) 第10章 内部排序 (Sorting),4,第1章 绪 论(Introduction),1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法（Algorithm） 1.4.2 算法设计的要求 1.4.3 算法效率的度量,5,数据结构是一门研究用计算机进行信息表示和处理的学科。这里面涉及到两个问题： 信息的表示（Express） 信息的处理（Man

3、age） 而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。,第1章 绪 论(Introduction),6,1.1 什么是数据结构（Data Structure） 计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。 例1、电话号码查询系统 设有一个

4、电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)(an，bn) 其中ai，bi(i=1，2n) 分别表示某人的名字和对应的电话号码。 现要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。,7,算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。 数据的结构，直接影响算法的选择和效率。 上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。 假定名字和其电话号码逻辑上已安排成N

5、元向量的形式，它的每个元素是一个数对(ai，bi)， 1in 数据结构还要提供每种结构类型所定义的各种运算的算法。,8,例2、图书馆的书目检索系统自动化问题 例3、计算机与人博弈的问题 例4、多叉路口交通灯的管理问题 通过以上几例可以直接地认为：数据结构 就是研究数据的逻辑结构和物理结构以及它们 之间相互关系，并对这种结构定义相应的运算， 而且确保经过这些运算后所得到的新结构仍然 是原来的结构类型。,9,1.2 数据结构的基本概念和术语(Concepts and Idioms),1.2.1 引例 首先分析学籍档案类问题。设一个班级有50个学生，这个班级的学籍表如表1.1所示。,表1.1 学 籍

6、 表,10,我们可以把表中每个学生的信息看成一个记录，表中的每个记录又由7个数据项组成。该学籍表由50个记录组成，记录之间是一种顺序关系。这种表通常称为线性表，数据之间的逻辑结构称为线性结构，其主要操作有检索、查找、插入或删除等。,11,数据(data)是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。除了数字、字符之外，还有用英文、汉字或其他语种字母组成的词组、语句，以及表示图形、图像和声音等的信息，这些也可称为数据。 数据元素(Data Element)是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。例如，表1.1中每个学生的学籍信息

7、作为一个数据元素，在表中占一行。每个数据元素由序号、学号、姓名、性别、英语成绩等7个数据项组成。数据项是有独立含义的数据的最小单位，有时也称为字段(Field)。,12,数据对象(Data Object)是具有相同性质的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N=0，1, 2,，字母字符数据对象是集合C=A, B, , Z。本节表1.1中的学籍表也可看成一个数据对象。 数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。它是指数据元素之间的相互关系，即数据的组织形式。我们把数据元素间的逻辑上的联系，称为数据的逻辑结构。常见的数据结构有前文

8、所介绍的线性结构、树型结构、图型结构。数据的逻辑结构体现数据元素间的抽象化相互关系，并不涉及数据元素在计算机中具体的存储方式，是独立于计算机的。,13,然而，讨论数据结构的目的是为了在计算机中实现对数据的操作，因此还需要研究如何在计算机中表示数据。数据的逻辑结构在计算机存储设备中的映像被称为数据的存储结构，也可以说数据的存储结构是逻辑结构在计算机存储器中的实现，又称物理结构。数据的存储结构是依赖于计算机的。常见的存储结构有顺序存储结构、链式存储结构等。,14,数据结构主要指逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常分为四类基本结构： 一、集合（Set）结构中的数据元素除了同属于一

9、种类型外，别无其它关系。 二、线性结构（Linear Structure）结构中的数据元素之间存在一对一的关系。 三、树型结构 （Tree Structure） 结构中的数据元素之间存在一对多的关系。 四、图状结构或网状结构（Graph Structure） 结构中的数据元素之间存在多对多的关系。,15,数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 例 复数的数据结构定义如下： Complex=(C，R) 其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关

10、系C1，C2。 数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。,16,数据对象可以是有限的，也可以是无限的。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。 数据结构在计算机中有两种不同的表示方法： 顺序表示和非顺序表示 由此得出两种不同的存储结构： 顺序存储结构和链式存储结构,17,顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 链式存储结构：在每一个数据元素中增加一个存放地址的指针（Pointer），用此指针来表示数据元素之间的逻辑关系。,18,数据类型（Data Type）：是一

11、个值的集合和定义在这个值集上的一组操作的总称 例1、 在FORTRAN语言中，变量的数据类型有整型、实型、和复数型。 例2、在C语言中 数据类型：基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义 数据对象（Data Object）：某种数据类型元素的集合。 例3、整数的数据对象是-3，-2，-1，0，1，2，3，英文字符类型的数据对象是A，B，C，D，E，F，。,19,抽象数据类型（ADT） 抽象数据类型：一个数学模型以及定义在该模型上的一组操作。 抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算

12、法。 用三元组描述如下： （，）,其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。,20,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,其中基本操作的定义格式为:,基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述,21,（参数表）中的参数： 赋值参数 只为操作提供输入值。 引用参数 以&打头，除可提供输入值外，还将返回操作结果。,初始条件： 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。,操作结果： 说明了操作正常完成之后，

13、数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。,22,例如，抽象数据类型复数的定义：,数据对象： De1,e2e1,e2RealSet 数据关系： R1 | e1是复数的实数部分 | e2 是复数的虚数部分 ,ADT Complex ,23,基本操作：,AssignComplex( &Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部分别被赋以参数 v1 和 v2 的值。,DestroyComplex( &Z) 操作结果：复数Z被销毁。,GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。,24,Get

14、Imag( Z, &ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。,Add( z1,z2, &sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1, z2 的和值。, ADT Complex,25,typedef struct float realpart； float imagpart； complex；,/ -存储结构的定义,/ -基本操作的函数原型说明,void Assign( complex &Z, float realval, float imagval )； / 构造复数 Z,其实部和虚部分别被赋以参数 /

15、realval 和 imagval 的值,26,float GetReal( cpmplex Z )； / 返回复数 Z 的实部值,float GetImag( cpmplex Z )； / 返回复数 Z 的虚部值,void Add( complex z1, complex z2, complex &sum )； / 以 sum 返回两个复数 z1, z2 的和,27,/ -基本操作的实现,void Add( complex z1, complex z2, complex , 其它省略 ,28,假设:z1和z2是上述定义的复数,则 Add(z1, z2, z3) 操作的结果,z3 = z1 +

16、 z2,即为用户企求的结果,29,ADT 有两个重要特征:,数据抽象,用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。,数据封装,将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。,30,类C语言,类C语言是C语言的一个子集，同时作了一些扩充、修改，参见P10 .,抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 由于我们用抽象数据类型来描述数据结构及其基本操作，因此这里所说的抽象数据类型的表示就是把相应数据结构在计算机中表示出来，通过前面的讨论可知，可借助一维数组或指针来表示。,抽象数据类型的实现就是写出相应基本操作的实现算法，这些算法当然可用C语言加以描述。但是，为了使我们的讨论既不拘泥于C语言的细节，又容易转换为C或C+程序，教材采用了类C语言来描述算法。,预定