第一章绪论
第一章 绪论
第一节数据结构讨论的范畴 算法+数据结构=程序设计 ·很多数值计算问题的数学模型通常可用一组线性 或非线性的代数方程组或微分方程组来描述,而 大量非数值计算问题的数学模型正是本门课程要 讨论的数据结构。 例一、求n个整数中的最大值。这似乎不成问 题,但如果这些整数的值有可能达到1012,那么 对32位的计算机来说,就存在一个如何表示的问 题
第一节 数据结构讨论的范畴 • 算法+数据结构 = 程序设计 • 很多数值计算问题的数学模型通常可用一组线性 或非线性的代数方程组或微分方程组来描述，而 大量非数值计算问题的数学模型正是本门课程要 讨论的数据结构。 • 例一、求 n 个整数中的最大值。这似乎不成问 题，但如果这些整数的值有可能达到1012，那么 对32位的计算机来说，就存在一个如何表示的问 题
例 例二、交叉路口的红绿灯管理。如今十字路口 横竖两个方向都有三个红绿灯,分别控制左拐 直行和右拐,那么如何控制这些红绿灯既使交 通不堵塞,又使流量最大呢? 例三、煤气管道的铺设问题。如右图需为城市 的各小区之间铺设煤气管道,对n个小区只 需铺设n-1条管线,由于地理环境不同等因 素使各条管线所需投资不同(如图上所标识) 如何使投资成本最低?myR2 32 12.1 44.6 5.9 9525925.9 79.2 4 21 10.5 6 85.6 98.7 ① ①
例 • 例二、交叉路口的红绿灯管理。如今十字路口 横竖两个方向都有三个红绿灯，分别控制左拐、 直行和右拐，那么如何控制这些红绿灯既使交 通不堵塞，又使流量最大呢？ • 例三、煤气管道的铺设问题。如右图需为城市 的各小区之间铺设煤气管道，对 n 个小区只 需铺设 n-1 条管线，由于地理环境不同等因 素使各条管线所需投资不同(如图上所标识)， 如何使投资成本最低？
什么是数据结构? 计算机的操作对象的关系更加复杂,操作形式 不再是单纯的数值计算,而更多地是对这些具 有一定关系的数据进行组织管理,将此称为非 数值性处理。 ·数据结构是一门讨论“描述现实世界实体的数 学模型牛数值计算及其上的操作在计算机中 如何表示和实现”的学科。 要使计算机能够更有效地进行这些非数值性处 理,就必须弄清楚这些操作对象的特点,在计 算机中的表示方式以及各个操作的具体实现手 段。这些就是《数据结构》这门课程研究的主 要内容
什么是数据结构? • 计算机的操作对象的关系更加复杂，操作形式 不再是单纯的数值计算，而更多地是对这些具 有一定关系的数据进行组织管理，将此称为非 数值性处理。 • 数据结构是一门讨论“描述现实世界实体的数 学模型(非数值计算)及其上的操作在计算机中 如何表示和实现”的学科。 • 要使计算机能够更有效地进行这些非数值性处 理，就必须弄清楚这些操作对象的特点，在计 算机中的表示方式以及各个操作的具体实现手 段。这些就是《数据结构》这门课程研究的主 要内容
121基本概念和术语 数据 是所有能被输入到计算机中,且能被计算 机处理的符号(数字、字符等)集合,它是计 算机操作对象的总称。 数据是个集合,如果用集合的表示方法来写的 话,就是 数据={xx是计算机操作的对象 数据元素 是数据(集合)中的一个个体",在计算机 中通常作为一个整体进行考虑和处理,是数据 结构中讨论的"基本单位
1.2.1 基本概念和术语 • 数据 是所有能被输入到计算机中，且能被计算 机处理的符号(数字、字符等)的集合，它是计 算机操作对象的总称。 • 数据是个集合，如果用集合的表示方法来写的 话，就是 数据={x|x是计算机操作的对象} • 数据元素 是数据(集合)中的一个"个体"，在计算机 中通常作为一个整体进行考虑和处理，是数据 结构中讨论的"基本单位"
两类数据元素 类是不可分割的“原子”型数据元素,如:整 数“5”,字符“N”等 另一类是由多个款项构成的数据元素,其中每个 款项被称为一个“数据项”。 例如描述一个学生的信息的数据元素可由下列6 个数据项组成。 数据项是数据结构中讨论的"最小单位" 出生|入 名号别号日期成绩 厍回
两类数据元素 • 一类是不可分割的“原子”型数据元素，如：整 数“5”，字符 “N” 等 • 另一类是由多个款项构成的数据元素，其中每个 款项被称为一个“数据项”。 • 例如描述一个学生的信息的数据元素可由下列6 个数据项组成。 • 数据项是数据结构中讨论的"最小单位"
·在由多个数据项构成的数据元素中必定存在关键 字。 关键字 指的是能识别一个或多个数据元素的数据项。 若能起唯一识别作用,则称之为“主”关键字, 否则称之为“次”关键字。 数据对象 是具有相同特性的数据元素的集合,如:整 数、实数等。它是数据的一个子集。 在同一个数学模型中的数据元素必然具有相同特 性
• 在由多个数据项构成的数据元素中必定存在关键 字。 • 关键字 指的是能识别一个或多个数据元素的数据项。 若能起唯一识别作用，则称之为 “主” 关键字， 否则称之为 “次” 关键字。 • 数据对象 是具有相同特性的数据元素的集合，如：整 数、实数等。它是数据的一个子集。 • 在同一个数学模型中的数据元素必然具有相同特 性
122数据结构 若在特性相同的数据元素集合中的数据元 素之间存在一种或多种特定的关系,则称 该数据元素的集合为数据结构“ 换句话说,数据结构是带“结构”的数据 元素的集合。 结构”即指数据元素之间存在的关系。 数据结构是一堆数据元素和这些数据元素 之间的关系的总和
1.2.2 数据结构 • 若在特性相同的数据元素集合中的数据元 素之间存在一种或多种特定的关系，则称 该数据元素的集合为"数据结构“ • 换句话说，数据结构是带“结构”的数据 元素的集合。 • “结构”即指数据元素之间存在的关系。 • 数据结构是一堆数据元素和这些数据元素 之间的关系的总和
例 ·可以用下述数据结构来描述2行3列的矩阵:它是 个含6个数据元素{a1a2a3,a4a5,a6}的集合, 且集合上存在“行关系”和“列关系”两个次序 关系,其中行关系为{, a4a5>,},列关系为 a1,a4>,,意为x和y之间存在"x领先于y"的次序 关系。 1a2a3 a 4 a5 a6
例 • 可以用下述数据结构来描述2行3列的矩阵：它是 一个含6个数据元素{a1,a2,a3,a4,a5,a6} 的集合， 且集合上存在“行关系”和“列关系”两个次序 关系，其中行关系为{，， ，}，列关系为 {，，}。 • 意为 x 和 y 之间存在 "x领先于y" 的次序 关系。 4 5 6 1 2 3 a a a a a a
例 某校一个年级有两个班,由一个级主任带班,每 个班按所住宿舍分组,他们之间的关系可如下描 述:{,,,,……} 班主任 班长1 班长2 含长1)(舍长k)长k+)(舍长
例 • 某校一个年级有两个班，由一个级主任带班，每 个班按所住宿舍分组，他们之间的关系可如下描 述：{ ，，，……，,，，……， }