数据结构 使用创语言(第4版) 朱战立 电子工业出版社 2009.1
数 据 结 构 使用C语言(第4版) 朱战立 电子工业出版社 2009.1
第1章绪论 数据结构的基本概念 主 要」抽象数据类型和软件构造 知 识)方法 算法和算法的时间复杂度
第1章 绪论 主 要 知 识 点 数据结构的基本概念 抽象数据类型和软件构造 方法 算法和算法的时间复杂度
1.1数据结构的基本概念 基本术语 (1)数据:人们利用文字符号、数字符号以及其他规定的符号 对现实世界的事物及其活动所做的抽象描述。 (2)数据元素:表示一个事物的一组数据。 (3)数据项:构成数据元素的数据。 例如,学生信息可包括学生的学号、姓名、性别、年龄等 数据。这些数据构成学生情况的描述的数据项;包括学号、 姓名、性别、年龄等数据项的一组数据就构成学生信息的 个数据元素
1.1 数据结构的基本概念 基本术语 (1)数据：人们利用文字符号、数字符号以及其他规定的符号 对现实世界的事物及其活动所做的抽象描述。 (2)数据元素：表示一个事物的一组数据。 (3)数据项：构成数据元素的数据。 例如，学生信息可包括学生的学号、姓名、性别、年龄等 数据。这些数据构成学生情况的描述的数据项；包括学号、 姓名、性别、年龄等数据项的一组数据就构成学生信息的 一个数据元素
基本术语 (4)抽象数据元素:没有实际含义的数据元素。 (5)抽象数据元素的类型:没有确切定义的数据类型。 (6)数据的逻辑结构:数据元素之间的相互联系方式。 (7)数据的存储结构:数据元素在计算机中的存储方式。 (8)数据的操作:对一种数据类型的数据进行的某种处理。 (9)数据的操作集合:对一种数据类型的数据进行的所有操 作
基本术语 (4)抽象数据元素：没有实际含义的数据元素。 (5)抽象数据元素的类型：没有确切定义的数据类型。 (6)数据的逻辑结构：数据元素之间的相互联系方式。 (7)数据的存储结构：数据元素在计算机中的存储方式。 (8)数据的操作：对一种数据类型的数据进行的某种处理。 (9)数据的操作集合：对一种数据类型的数据进行的所有操 作
线性结构:除第一个和最后一个数据元素外,每个 数(数据元素只有一个前驱和一个后继数据元素 据的逻辑结 树结构:除根结点外,每个数据元素只有一个前驱 数据元素,可有0个或若干个后继数据元素。 构(图结构:每个数据元素可有0个或若干个前驱数据 元素和0个或若干个后继数据元素
数 据 的 逻 辑 结 构 线性结构：除第一个和最后一个数据元素外，每个 数据元素只有一个前驱和一个后继数据元素。 树结构：除根结点外，每个数据元素只有一个前驱 数据元素，可有０个或若干个后继数据元素。 图结构：每个数据元素可有０个或若干个前驱数据 元素和０个或若干个后继数据元素
线性结构 树结构 图结构
线性结构 树结构 图结构
顺序存储结构:把数据元素存储在一块连续地址空 问的内存中,其特点是逻辑上相邻的数据元素在物 理上也相邻,数据间的逻辑关系表现在数据元素存 数储位置关系上 据的存储结构 指针是指向物理存储单元地址的变量。由数据元素 拉和指针域组成的一个结构体称为结点。 链式存储结构:使用指针把相互直接关联的结点 (即直接前驱结点或直接后继结点)链接起来,其特 点是逻辑上相邻的数据元素在物理上不一定相邻 数据间的逻辑关系表现在结点的链接关系上
数 据 的 存 储 结 构 顺序存储结构：把数据元素存储在一块连续地址空 间的内存中，其特点是逻辑上相邻的数据元素在物 理上也相邻，数据间的逻辑关系表现在数据元素存 储位置关系上。 指针是指向物理存储单元地址的变量。由数据元素 域和指针域组成的一个结构体称为结点。 链式存储结构：使用指针把相互直接关联的结点 (即直接前驱结点或直接后继结点)链接起来，其特 点是逻辑上相邻的数据元素在物理上不一定相邻， 数据间的逻辑关系表现在结点的链接关系上
, a 顺序存储结构 n-2 n-1 ead an1∧ 链式存储结构
head ... 0 a 1 a n−1 a2 a ∧ ... 0 a 1 a 2 a n−1 an−2 a 0 1 2 n-2 n-1 (a) (b) 顺序存储结构 链式存储结构
从抽象角度,数据的操作主要讨论某种数据类型 数数据应具备的操作的逻辑功能,抽象角度下的操 据)作一般和数据的逻辑结构一起讨论; 的 操具体来说,数据的操作主要讨论操作的具体实现 作算法。具体问题的操作实现必须在数据的存储结 构确定后才能进行。 数据结构课程主要讨论表、堆栈、队列、串 数组、树、二叉树、图等典型的常用数据结构 在讨论这些典型数据结构时,主要从它们的逻辑 结构、存储结构和数据操作三个方面进行分析讨 论
数 据 的 操 作 从抽象角度，数据的操作主要讨论某种数据类型 数据应具备的操作的逻辑功能，抽象角度下的操 作一般和数据的逻辑结构一起讨论； 具体来说，数据的操作主要讨论操作的具体实现 算法。具体问题的操作实现必须在数据的存储结 构确定后才能进行。 数据结构课程主要讨论表、堆栈、队列、串、 数组、树、二叉树、图等典型的常用数据结构。 在讨论这些典型数据结构时，主要从它们的逻辑 结构、存储结构和数据操作三个方面进行分析讨 论
12抽象数据类型和软件构造方法 类型是一组值的集合。 数据类型是指一个类型和定义在这个类型上的操作集 合。 抽象数据类型是指一个逻辑概念上的类型和这个类型 上的操作集合 数据类型和抽象数据类型的不同之处仅仅在于数 据类型指的是高级程序设计语言支持的基本数据类型 而抽象数据类型指的是在基本数据类型支持下用户新 设计的数据类型
1.2 抽象数据类型和软件构造方法 类型是一组值的集合。 数据类型是指一个类型和定义在这个类型上的操作集 合。 抽象数据类型是指一个逻辑概念上的类型和这个类型 上的操作集合。 数据类型和抽象数据类型的不同之处仅仅在于数 据类型指的是高级程序设计语言支持的基本数据类型， 而抽象数据类型指的是在基本数据类型支持下用户新 设计的数据类型