ch1+数据结构-绪论new

《ch1+数据结构-绪论new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构曹迎春yccao@nju.edu.cn第一章绪论【学习目标】熟悉各类文件的特点，构造方法以及如何实现检索，插入和删除等操作。【重点和难点】本章讨论的都是一些基本概念，因此没有难点，重点在于了解有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。【知识点】数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间复杂度。【学习指南】•熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。•了解抽象数据类型的定义、表示和实现方法。•熟

2、悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。•理解算法五个要素的确切含义和对算法正确性的理解。•掌握计算语句频度和估算算法时间复杂度的方法。【课前思考】你过去是否听说过"数据结构"？你知道数据结构是一门讨论什么内容的学科吗？数据结构讨论的范畴•算法+数据结构=程序设计•数值计算问题–一组线性或非线性的代数方程组或微分方程组•非数值计算问题–本课程所讨论的数据结构例一、求n个整数中的最大值。例二、交叉路口的红绿灯管理。例三、煤气管道的铺设问题。数据结构讨论的范畴•数据结构是一门讨论"描述现实世界实体的数学模型(非数值计算

3、)及其上的操作在计算机中如何表示和实现"的学科。基本概念和术语•数据–数据={x

4、x是计算机操作的对象}–计算机处理的信息的某种特定的符号表示形式。•数据元素–不可分割的“原子”型数据元素；–由多个款项构成的数据元素，其中每个款项被称为一个“数据项”。–数据项：组合项、原子项基本概念和术语•关键字–能识别一个或多个数据元素的数据项–主关键字、次关键字•数据对象–具有相同特性的数据元素的集合数据结构•若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为“数据结构”。•线性关系–假设以三个4位的十进制数表示一个含12位十进制数的“

5、长整数”，则可用如下描述的数学模型表示：它是一个含三个数据元素{a1,a2,a3}的集合，且在集合上存在下列次序关系：{，}。–描述2行3列的矩阵：它是一个含6个数据元素{a1,a2,a3,a4,a5,a6}的集合，且集合上存在"行关系"和"列关系"两个次序关系，其中行关系为{，，，}，列关系为{，，}。–描述1行6列的矩阵的数据结构的定义为：它是一个含6个数据元素{a1,a2,a3,a4,a5,a6}的集合，且集合上只存在一个次序关系，即

6、：{，，，，}。数据结构•非线性关系–管道图–某校一个年级有两个班，由一个级主任带班，每个班按所住宿舍分组数据结构数据结构的形式定义为一个二元组：Data_Structures=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集。数据结构•分类数据结构•逻辑结构–对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。•物理结构–数据逻辑结构在计算机中的表示和实现，故又称数据"存储结构"。–存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关

7、系的映象。关系的表示方法•顺序映象•链式映象操作集•不同的数据结构其操作集不同，但下列操作必不可缺：–结构的生成；–结构的销毁；–在结构中查找满足规定条件的数据元素；–在结构中插入新的数据元素；–删除结构中已经存在的数据元素；–遍历。数据类型和抽象数据类型•数据类型–一个"值"的集合和定义在此集合上的"一组操作"的总称。•抽象数据类型（AbstractDataType简称ADT）–一个数学模型以及定义在此数学模型上的一组操作。–特性•数据抽象•数据封装抽象数据类型抽象数据类型的形式描述为：ADT=(D，S，P)其中：D是数据对象，S是D上的关系集，P是D的基本操作

8、集。其中(D，S)即为相应的数据结构的定义。抽象数据类型的定义ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据类型名抽象数据类型的定义•数据对象和数据关系的定义用伪码描述•基本操作的定义格式为：基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。•你以前是否了解“引用参数”这个概念？抽象数据类型“复数”的定义：ADTComplex{D={e1,e2

9、e1,e2RealSet}R1={

10、