青岛理工大学数据结构第一章.ppt

数据结构;;主要内容和学习要点;计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示 信息的处理 而信息的表示和处理又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 ;Q1 ： 什么是数据结构？ Q2 ：学习数据结构有什么用？ Q3 ：数据结构涵盖的主要内容？ ;——针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。 ——是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。;是相互之间存在一种或多种特定关系的数据元??的集合，表示为：; 著名计算机科学家、Pascal语言发明者N.沃思教授提出： 程序 = 算法 + 数据结构 也就是说，计算机按照程序所描述的算法对某种结构的数据进行加工处理。 数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 非数值计算的程序设计问题：信息自动检索、计算机游戏、多岔路口交通灯的管理。;按书名;例2 人机对奕问题; 例3 多叉路口交通灯管理问题;数据（data)：所有能输入到计算机中去的描述客观事物的符号 是计算机处理的信息的某种特定的符号表示形式。它包括数值 型数据和非数值型数据（如字符、图象、声音）。 数据元素（data element）：数据的基本单位，也称结点（node） 或记录（record）。 数据项(data item):有独立含义的数据最小单位，也称域(field)。 数据对象(data object)：性质相同的数据元素的集合，是数据的 一个子集。;;答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。;;集合结构： 仅同属一个集合 线性结构: 一对一（1:1) 树 形结 构: 一对多（1:n) 图 形 结 构: 多对多 (m:n);（1） S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)};该结构是非线性的。;　　　答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。;元素n;1536;答：在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。;Q1： 数据类型与抽象数据类型的区别？ Q2: 抽象数据类型如何定义？ Q3: 抽象数据类型如何表示和实现？ ; 数据类型（data type）： 一个值的集合和定义在这个集合上的一组操作的总称。如C语言中的整型（短整型2个字节表示范围-32768~32767、长整型4个字节）、浮点型（4个字节，带小数点）、字符型（1个字节，用单引号表示，如’a’）、双精度型（8个字节） 抽象数据类型(ADT: Abstract Data Type)： ◆ 由用户定义，用以表示应用问题的数据模型。 ◆ 由基本的数据类型组成, 并包括一组相关的服务（或称操作）。 区别：ADT与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐藏。;Q2 抽象数据类型如何定义？; 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。;ADT Complex {数据对象:D＝{e1,e2｜e1,e2∈RealSet } 数据关系:R＝{e1,e2 | e1是实数部分,e2 是虚数部分 } 基本操作： InitComplex( Z, v1, v2 ) 操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。 DestroyComplex( Z) 操作结果：复数Z被销毁。 GetReal( Z, realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 GetImag( Z, ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。 } ADT Complex;1.4 算法的描