第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) ❖物理结构就是逻辑结构到存储器的一个映射。 ❖四种存储结构：顺序存储、链接存储、索引存储、 散列存储