25
关系的映象方法： 表示< >的方法） 关系的映象方法： 表示<x, y>的方法） （ 顺序映象： 顺序映象： 以相对的存储位置表示后继关系。 以相对的存储位置表示后继关系。 例如: 例如:令 y 的存储位置和 x 的存储位置之间 差一个常量 C C是一个隐含值，整个存储结构中只含数据元 是一个隐含值， 素本身的信息。 素本身的信息。
x
y
26
链式映象： 链式映象： 以附加信息(指针) 以附加信息(指针)表示后继关系
需要用一个和 x 在一起的附加信息 指示 y 的存储位置
y
x
27
两种不同的存储结构: 两种不同的存储结构:
顺序存储结构 链式存储结构
例：复数3.0－2.3i 的两种存储方式： 复数3.0－ 的两种存储方式： 3.0
9
1.1 数据结构讨论的范畴 Niklaus Wirth
Algorithm + Data Structures = Programs
程序设计: 为计算机处理问题编制 程序设计: 一组指令集 算法: 算法 处理问题的策略 数据结构: 数据结构 问题的数学模型
10
非数值计算的程序设计问题
例一: 求一组(n (n个 例一: 求一组(n个)整数中的最大值
14
数据元素也可以由若干款项构成。 数据元素也可以由若干款项构成。
例如： 例如： 描述一个学生的数据元素 其中每个款项称为一个“数据项” 其中每个款项称为一个“数据项” 数据项是数据结构中讨论的最小单位
姓 名学 号班 号性别出生日期入学成绩 年月日 原子项 称之为组合项
15
三者之间的关系： 三者之间的关系： 个人记录 > 姓名 数据项 姓名、年龄… 例：班级通讯录 > 数据 > 数据元素 > 、年龄
col = {<a1,a4>,<a2,a5>,<a3,a6>}
a1 a3 a5 a2 a4 a6
a1 a2 a3 a4 a5 a6
19
例3，在一维数组 {a1, a2, a3, a4, a5, a6} 的 个数据元素之间存在如下的次序关系: 6 个数据元素之间存在如下的次序关系:
{<ai, ai+1>| i=1, 2, 3, 4, 5}
造就一种新文化 形成一个新产业
信息产 业
产生一门新学科
计算机科学与技术学科
2
培
养
模
式
程序设计教学模式
基 提 础 训 能 层 力 面 用 练 高 展 应 拓 践 实
3
大 学 生 信 息 素 质 与 创 新 能 力 培 养 模 式 基 本 思 路
4
基础训练
程序设计基础训练课 •入门课程 •基本技能 程序设计能力提高课 •典型的程序设计方法 •构造性思维的训练 •抽象能力的培养
上述表达式可用图形表示为： 解：上述表达式可用图形表示为： d1 d5 d4 d3
23
d2
该结构是非线性的 该结构是非线性的。 非线性
解释2：什么叫数据的物理结构？ 解释 ：什么叫数据的物理结构？ 答：物理结构亦称存储结构，是数据的逻辑结构 在计算机存储器内的表示（或映像）。它依赖于 计算机。 存储结构详解： 存储结构详解：16来自1.1 什么是数据结构
是相互之间存在一种或多种特定关系的数据 元素的集合，表示为：
Data_Structure=（ R） Data_Structure=（D, R）
（数值或非数值）
元素有限集 关系有限集
——是指同一数据元素类型中各元素之间存在的 是指同一数据元素类型中各元素之间存在的 关系。 关系。
12
概括地说， 概括地说，
数据结构是一门讨论“ 数据结构是一门讨论“描述现 实世界实体的数学模型(非数值计 实世界实体的数学模型( 算)及其上的操作在计算机中如何 表示和实现”的学科。 表示和实现”的学科。
13
1.2
基本概念
一、数据与数据结构 数据:所有能被输入到计算机中， 数据:所有能被输入到计算机中，且能被计算机处理 的符号(数值、字符等)的集合。 的符号(数值、字符等)的集合。 是计算机操作的对象的总称。 是计算机操作的对象的总称。 是计算机处理的信息的某种特定的符号表示形式。 是计算机处理的信息的某种特定的符号表示形式。 数据元素:是数据（集合）中的一个“个体”,在计算 数据元素:是数据（集合）中的一个“个体” 机中通常作为一个整体进行考虑和处理。 机中通常作为一个整体进行考虑和处理。是数据结构 中讨论的基本单位。 中讨论的基本单位。 整数“ ,字符“ 等 如:整数“5”,字符“N”等。 ----是不可分割的 原子” 是不可分割的“ ----是不可分割的“原子”
17
用三个4 例1: 用三个4位的十进制数表示一个含 12 位数的 十进制数。 十进制数。
3214,6587,9345 ─ a1(3214),a2(6587),a3(9345)
则在数据元素 a1、a2 和 a3 之间存在着 、 次序” “次序”关系 <a1,a2>、<a2,a3> > > 3214，6587，9345 6587，3214，9345 ≠ a2 a1 a2 a3 a1 a3
7
第1章 绪
• 知 • • • 难 • • 要 •
论
识点 数据结构中常用的基本概念和术语 算法描述和分析方法 点 算法复杂性的分析方法 求 了解数据的逻辑结构和物理结构，算法的基 本概念，它们对于程序设计的重要性以及相互 关系 • 掌握算法复杂性的概念及分析方法
8
讨论4个问题：
1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实 现 1.4 算法和算法分析
数 据 结 构
授课教师：孙挺（副教授、博士生） 授课教师：孙挺（副教授、博士生） E_mail: sunting@
60多年的发展 60 多年的发展 ， 计算机对社会发展有着广 多年的发展， 泛而深远的影响， 泛而深远的影响，其应用要求也显著提高
信息时 代
开辟一个新时代
计算机文 化
基本操作是“比较两个数的大小” 算法: 算法: ? 基本操作是“比较两个数的大小” 模型：？ 模型：？ 取决于整数值的范围
例二： 例二：计算机对弈
算法： 算法：? 模型： 模型：?
对弈的规则和策略 棋盘及棋盘的格局
11
例三： 例三：铺设城市的煤气管道 算法： 算法：? 模型： 模型：? 如何规划使得总投资花费最少？ 如何规划使得总投资花费最少？ 图
“数据元素”的映象 数据元素” 数据元素 “关系”的映象 关系” 关系
24
数据元素的映象方法： 数据元素的映象方法： 用二进制位(bit)的位串表示数据元素 用二进制位(bit)的位串表示数据元素 (bit)
(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2
（1） S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)}
上述表达式可用图形表示为： 解： 上述表达式可用图形表示为： b c a e f d
此结构为线性的 此结构为线性的。 线性
22
（2） S=(D, R) ） D={di | 1≤i≤5} R={(di , dj ), i<j}
18
例2，在2行3列的二维 行 列的二维 数组{a1, a2, a3, a4, a5, 数组 a6}中六个元素之间存 中六个元素之间存 在两个关系: 在两个关系
a1 a4
a2 a5
a3 a6
行的次序关系: 行的次序关系
row = {<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}
列的次序关系: 列的次序关系:
数学 软件 硬件
对象 关系 操作
5
目
第 1章 第 2章 第 3章 第 4章 第 5章 第 6章 第 7章 第 9章 10章 第10章
录
绪论 线性表 栈和队列 串 数组和广义表 树和二叉树 图 查找 排序
6
数据结构的学习重点
•如何描述一种新的抽象数据类型？ 如何描述一种新的抽象数据类型？ 如何描述一种新的抽象数据类型 •如何分析算法的优劣？ 如何分析算法的优劣？ 如何分析算法的优劣 •线性表的主要特征。 线性表的主要特征。 线性表的主要特征 •线性表的存储表示（顺序表示、单向链表、循 线性表的存储表示（ 线性表的存储表示 顺序表示、单向链表、 环链表、双向链表） 环链表、双向链表） •特殊的线性表：栈、队列、串 特殊的线性表： 队列、 特殊的线性表 •二叉树的定义、性质、存储结构、遍历算法 二叉树的定义、 二叉树的定义 性质、存储结构、 •图的定义、术语、存储结构 图的定义、 图的定义 术语、 •静态查找表、二叉排序树、哈希函数的构造及 静态查找表、二叉排序树、 静态查找表 冲突处理方法。 冲突处理方法。 •插入排序、快速排序、选择排序 插入排序、 插入排序 快速排序、
可见，不同的“关系”构成不同的“结构” 可见，不同的“关系”构成不同的“结构”
数据结构是相互之间存在着某种逻辑 关系的数据元素的集合。 关系的数据元素的集合。
20
解释1： 什么叫数据的逻辑结构？ 解释 ： 什么叫数据的逻辑结构？ 指数据元素之间的逻辑关系。 答：指数据元素之间的逻辑关系。即从逻辑关 系上描述数据， 与数据的存储无关， 系上描述数据，它与数据的存储无关，是独立于计 算机的。 算机的。
提高能力
课 程
• • • 训练 设课程设计 训练 训练 的能力 程序设计能力
• •提高
数据结构课程的地位
——针对非数值计算的程序设计问题，研究计算机 针对非数值计算的程序设计问题，
