数据结构绪论.pptVIP

内 容 安 排 第1章　绪　论 1.1 什么是数据结构 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量 1.1 什么是数据结构 是相互之间存在一种或多种特定关系的数据元素的集合，表示为： 常用术语 【数据】(Data)是对信息的一种符号表示。能被计算机输入、存储、处理和输出的一切信息 【数据元素】(Data Element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。它是数据整体中相对独立的单位,也称节点（node）或记录（record） 【数据项】一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位,也称域(field)。 【数据对象】(Data Object)是性质相同的数据元素的集合。是数据的一个子集。 【数据记录】组织数据的基本单位 【数据结构】(Data Structure)数据及其相互之间的关系 常用术语 【逻辑结构】数据之间的相互联系，通常分为四类基本结构： 集合结构: 结构中的数据元素除了同属于一种类型外，别无其它关系。 线性结构: 结构中的数据元素之间存在一对一的关系。 树结构: 结构中的数据元素之间存在一对多的关系。 图(或网状)结构: 结构中的数据元素之间存在多对多的关系。 【存储结构/物理结构】一种数据结构在存储器中的存储方式 顺序、链接、索引、散列 例 书目自动检索系统 例 人机对奕问题 例 多叉路口交通灯管理问题 1.2 学习数据结构的意义 　　计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 　　数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。 1.3 数据结构涵盖的内容 （1） S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} d1 d5 d2 d4 d3 　　　答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。 答：在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。 1.4 什么是抽象数据类型 1.4.1 数据类型与抽象数据类型的区别 1.4.2 抽象数据类型如何定义 例：给出自然数(Natural Number )的抽象数据类型定义。 1.4.3 抽象数据类型如何表示和实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 1、抽象数据类型表示与实现 抽象数据类型实际上就是对该数据结构的定义。用三元组描述如下： ADT =（D,S,P） 其中：D是数据对象，用结点的有限集合表示；S是D上的关系的集合，用结点间的序偶的集 合来表示；P是对D的基本操作的集合。 ADT 抽象数据类型名 is Data: 数据描述 Operations: 操作声明 End 抽象数据类型名 基本操作的定义格式为： 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 2、类C语言简要说明 2、类C语言简要说明 2、类C语言简要说明 2、类C语言简要说明 2、类C语言简要说明 2、类C语言简要说明 1.5 算法效率的度量 1.5.1 什么是算法？如何评判算法的好坏？ 1.5.2 时间复杂度和空间复杂度如何表示？ 1.5.3 计算举例 1.5.1 什么是算法？如何评判一个算法的好坏？ 时间复杂度T(n)或空间复杂度S(n)按数量级递增顺序为： 3n+2=O(n) 因为 3n+2?4n for n?2 6*2n+n2=O(2n) 因为6*2n+n2 ?7*2n for n?4 1.5.3 计算举例 本章小结 数据结构课程—— 数据结构＋算法＝程序，涉及数学、计算机硬件和软件。 数据结构定义——指互相有关联的数据元素的集合，可用data_Structure=(D,R)表示。 数据结构内容——数据的逻辑结构、存储结构和基本运算 数据结