王平数据结构第一章课件.ppt

数 据 结 构 参考资料 《数据结构题集》严蔚敏 清华大学出版社 《《数据结构》算法实现及解析》高一凡 西安电子科技大学出版社 《数据结构课程设计》苏仕华 机械工业出版社 第一章 绪论 主要知识点 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 教学要求 1、熟悉数据结构用到的一些基本术语、名词的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系，分清哪些是逻辑结构的性质，哪些是物理结构的性质。 2、了解抽象数据类型的定义、表示和实现方法。 3、理解算法五个要素（特性）的确切含义。 4、掌握计算语句频度和估算算法时间复杂度的方法以及算法分析中O(f(n))符号的含义。 5、熟悉一种算法描述语言（类C）的书写规范，特别要注意输入、输出的方法以及错误处理方式。 教学重点 数据结构的概念； 算法分析； 1.1 什么是数据结构 明确计算机解决问题的几个步骤 理解数据结构的含义 1.1 什么是数据结构 1.1 什么是数据结构 1.1 什么是数据结构 例子1-1 书目检索系统 例子1-2人机对奕问题 例子1-3 多叉路口交通灯问题 例子1-1 书目检索系统 例子1-2人机对奕问题 例子1-3 多叉路口交通灯问题 1.1 什么是数据结构 1.1 什么是数据结构 数据结构所处的地位P4 1.2 基本概念和术语 ?数据：客观对象的符号表示。 ?数据元素：数据的基本单位。相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。 ?数据对象：性质相同的数据元素的集合. 例如: 所有班名相同的记录集。 1.2 基本概念和术语 1.2 基本概念和术语 数据结构有两个要素： 数据元素的集合 关系的集合。 数据结构的形式定义为：数据结构是一个二元组： Data_Structure ＝（D，R） 其中，D是数据元素的有限集，R是D上关系的有限集。 1.2 基本概念和术语 例1-4：复数的数据结构 Complex=(C，R) 其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。 例1-5：研究课题小组的数据结构 数据的逻辑结构有两个要素:数据元素和关系. 1.2 基本概念和术语 对每种数据结构，主要讨论如下两方面的问题： 1） 数据的逻辑结构，数据结构的基本操作； 2） 数据的存储结构，数据结构基本操作的实现； 数据的存储（物理）结构 数据元素的表示 用位串在内存中实现数据结构的数据元素 数据元素之间关系的表示 顺序存储结构 借助元素在存储器中的相对位置来表示数据元素间的逻辑关系 链式存储结构 借助指示元素存储地址的指针表示数据元素间的逻辑关系 例子：复数的存储结构 存储结构的描述 借用高级语言的“数据类型”来描述 顺序存储结构：数组 链式存储结构：指针 数据类型 数据结构密切相关，最早出现在高程，用以刻画操作对象的特性； 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 高级语言的数据类型 例子：C语言中 基本数据类型：int, char, float, double等， 整型 取值范围：16位 操作：+、-、*、/、MOD、DIV 构造数据类型：数组、结构体、共用体、枚举 指针类型 空(void)类型 用户也可用typedef 自己定义数据类型 数据类型的分类 原子类型 原子类型的值是不可分解的。如C语言中整型、字符型、浮点型、双精度型等基本类型，分别用保留字int、char、float、double标识。 结构类型 结构类型是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。 抽象数据类型 是指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。 注意：抽象数据类型和数据类型实质是一个概念 抽象数据类型的分类 原子类型 例子：整数，实数，字符 结构类型 固定聚合类型 例子：复数 可变聚合类型 例子：有序整数序列 抽象数据类型的形式定义 （D，S，P） D：数据对象 S：D上的关系集 P：对D的基本操作集 ADT 抽象数据类型名 { 数据对象：{数据对象的定义} 数据关系：{数据关系的定义} 基本操作：{基本操作的定义} } ADT 抽象数据类型名 基本操作的定义格式 基本操作名 （参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉