第1章绪论 ·1.1数据结构 1.2基本概念和术语 ·1.3抽象数据类型 1.4算法和算法分柝
第1章 绪论 • 1.1 数据结构 • 1.2 基本概念和术语 • 1.3 抽象数据类型 • 1.4 算法和算法分析
引论 对于一个课题,在计算机领域,一般遵循下面的解 决原则: 需求分析→总体设计→模块分割→建立数学模型 解数学模型的算法→程序编制→调试→结果 数据结构涉及到:数学模型的建立和对该模型具体 实现的对应的算法。 数据结构的地位:数学、硬件、软件之间。核心专 业基础课
引 论 ▪ 对于一个课题，在计算机领域，一般遵循下面的解 决原则： 需求分析 总体设计 模块分割 建立数学模型 解数学模型的算法 程序编制 调试 结果 ▪ 数据结构涉及到：数学模型的建立和对该模型具体 实现的对应的算法。 ▪ 数据结构的地位：数学、硬件、软件之间。核心专 业基础课
1.1数据结构的基本概念和术语 1.基本术语 (1)数据:描述客观事物的数字、字符以及所有 输入到计算机中并被计算机程序处理的符号的 集合。(数字、字符、声音、图形、图像等等) (2)数据元素:数据的基本单位,在计算机程序中 常常作为一个整体进行考虑和处理,如纪录/结 构 (3)数据项:数据的不可分割的最小单位,如结构 中的域。 (4)数据对象:性质相同的数据元素的集合,是数 据的一个子集
1.1数据结构的基本概念和术语 1. 基本术语 （1）数据：描述客观事物的数字、字符以及所有能 输入到计算机中并被计算机程序处理的符号的 集合。（数字、字符、声音、图形、图像等等） （2）数据元素：数据的基本单位，在计算机程序中 常常作为一个整体进行考虑和处理，如纪录/结 构。 （3）数据项：数据的不可分割的最小单位，如结构 中的域。 （4）数据对象：性质相同的数据元素的集合，是数 据的一个子集
2.数据结构 (1)定义:是相互之间存在一种或多种特定关系的 数据元素的集合。 数据之间不是相互独立的,他们之间有某种特定的 关系,这种数据元素之间的关系,称为“结构” 结构=关系+实体 另一种定义:按照逻辑关系组织起来的一批数据, 按一定的存储方法把它存储在计算机中,并在这些 数据上定义了一个运算的集合。 形式定义:二元组(D,S)其中D是数据元素的有限 集,S是D上关系的有限集
2. 数据结构 （1）定义：是相互之间存在一种或多种特定关系的 数据元素的集合。 ▪ 数据之间不是相互独立的，他们之间有某种特定的 关系，这种数据元素之间的关系，称为“结构” 结构=关系+实体 ▪ 另一种定义：按照逻辑关系组织起来的一批数据, 按一定的存储方法把它存储在计算机中, 并在这些 数据上定义了一个运算的集合。 ▪ 形式定义：二元组 (D,S) 其中D是数据元素的有限 集，S是D上关系的有限集
(2)四种基本结构(逻辑结构)p5 集合:元素仅属于同一个集体,没有其他关系 线性结构:存在一对一关系,序列相邻,次序关系。 树型结构:存在一对多关系,层次关系。 图状结构(网状结构):存在多对多关系,任意性 ☆存储器模型:一个存储器M是一系列固定大小的存 储单元,每个单元U有一个唯一的地址A(U),该地 址被连续地编码。每个单元U有一个唯一的后继单 元U=succ(U) 物理结构就是逻辑结构到存储器的一个映射 ◇四种存储结构:顺序存储、链接存储、索引存储、 散列存储
（2）四种基本结构（逻辑结构） p5 ▪ 集合：元素仅属于同一个集体，没有其他关系。 ▪ 线性结构：存在一对一 关系，序列相邻，次序关系。 ▪ 树型结构：存在一对多关系，层次关系。 ▪ 图状结构（网状结构） ：存在多对多关系，任意性 ❖存储器模型：一个存储器M是一系列固定大小的存 储单元，每个单元U有一个唯一的地址A(U)，该地 址被连续地编码。每个单元U有一个唯一的后继单 元U’=succ(U) ❖物理结构就是逻辑结构到存储器的一个映射。 ❖四种存储结构：顺序存储、链接存储、索引存储、 散列存储
(3)实例:P1-P3例1-1 例1-3 表:计算机系人事表 工号 姓名 性别职务 教研室工作时间发表论文 01 系主任 软件 1981.1A,B 02 教研室主任软件 19851BCE,F 03 教师 软件 1990.8 C D 04 教师 应用 19878AG 05 教师 用 19759E 06 教师 应用 19922F,J 07 教师 软件 19838D,L 08 教研室主任应用 1986.7G,H 09 教师 用 19958H,,,K 10 教 软件 19892L,K
（3）实例：P1-P3 例1-1 —— 例1-3 表：计算机系人事表 工号 姓名 性别 职务 教研室 工作时间 发表论文 01 系主任 软件 1981.1 A,B 02 教研室主任 软件 1985.1 B,C,E,F 03 教师 软件 1990.8 C,D 04 教师 应用 1987.8 A,G 05 教师 应用 1975.9 E,I 06 教师 应用 1992.2 F,J 07 教师 软件 1983.8 D,L 08 教研室主任 应用 1986.7 G,H 09 教师 应用 1995.8 H,I,J,K 10 教师 软件 1989.2 L,K
3.数据结构的划分 (1)按数据结构的性质划分 数据的逻辑结构—数据元素之间的逻辑关系 (设计算法数学模型) 数据的物理结构—数据结构在计算机中的 映像 (存储结构,算法的实现)
3. 数据结构的划分 （1）按数据结构的性质划分 ▪ 数据的逻辑结构——数据元素之间的逻辑关系 （设计算法—— 数学模型） ▪ 数据的物理结构——数据结构在计算机中的 映像 （存储结构，算法的实现）
3.数据结构的划分 (2)按数据结构在计算机内的存储方式来划分 顺序存储结构—借助元素在存储器的相 对位置来表示数据元素之间的逻辑关系。 链式存储结构—借助指示元素存储地址 的指针表示数据元素之间的逻辑关系
3. 数据结构的划分 （2）按数据结构在计算机内的存储方式来划分 ▪ 顺序存储结构——借助元素在存储器的相 对位置来表示数据元素之间的逻辑关系。 ▪ 链式存储结构——借助指示元素存储地址 的指针表示数据元素之间的逻辑关系
3.数据结构的划分 (2)按数据结构在计算机内的存储方式来划分 索引存储方法:在存储结点的同时,还建立 附加的索引表,索引表中的每一项称为索引 项,形式为:关键字,地址 散列存储方法:根据结点的关键字直接计算 出该结点的存储地址。 说明:四种存储方法可结合起来对数据结构进 行存储映像
3. 数据结构的划分 （2）按数据结构在计算机内的存储方式来划分 ▪ 索引存储方法：在存储结点的同时，还建立 附加 的索引表，索引表中的每一项称为索引 项，形式为：关键字，地址。 ▪ 散列存储方法：根据结点的关键字直接计算 出该结点的存储地址。 说明：四种存储方法可结合起来对数据结构进 行存储映像
3.数据结构的划 (3)按数据结构的操作来划分 静态结构——经过操作后,数据的结构特征 保持不变(如数组) 半静态结构——经过操作后,数据的结构特 性只允许很小变迁(如栈、队列)。 动态结构——经过操作后,数据的结构特性 变化比较灵活,可随机地重新组织结构(如 指针)
3. 数据结构的划分 （3）按数据结构的操作来划分 ▪ 静态结构——经过操作后，数据的结构特征 保持不变（如数组）。 ▪ 半静态结构——经过操作后，数据的结构特 性只允许很小变迁（如栈、队列）。 ▪ 动态结构——经过操作后，数据的结构特性 变化比较灵活，可随机地重新组织结构（如 指针）
