教材：
朱战立编著，数据结构 —— 使用 C
语言（第 3版），西安交通大学出版
社,2003年
数 据 结 构
2
课前的话 —— 计算机系列课程之间的联系
计算机概论与上机操作 （对 21 世纪公民要求）
?
程序设计与算法语言 （ B A S I C F O R T R A N P A S C A L C 等，怎样使用计算机）
?
计算机组成原理 （所有计算机的共性）
?
微机原理及应用 （特定机型介绍，单片机或 8086 P C 机，怎样应用计算机）
控制之路 数据处理之路
? ?
汇编语言程序设计 数据结构
? ?
单片机技术 / 微机接口 操作系统
? ?
软件技术基 础 数据库理论
? ?
计算机网络 软件工程
? ?
应用系统设计 计算机网络
3
数据结构课程的地位
它是计算机专业及相关专业的 核心课
程 之一，是计算机及相关专业的 重要骨干
基础课程 。
它针对非数值计算的程序设计问题，
研究计算机的操作对象以及它们之间的关
系和操作。即其研究目的是研究有效地组
织和处理非数值类型数据的理论、技术和
方法。
4
数据结构的核心研究内容
数据的逻辑结构, 存储结构及它们之
间的关系和相应的基本操作运算的定义和
实现 。
本书围绕数据结构的三种基本结构：
线性结构 （ 第 2-5章 ）, 树形结构 （ 第 7章 ）
和图形结构 （ 第 8章 ） 展开讨论, 研究解
决如下问题：一个具体问题的逻辑数据结
构是什么？ 适宜选用什么样的存储结构？
采用什么样的操作实现算法效率更高？
5
学时数,64（ 52学时授课＋ 12学时上机）
学 分,3.5
教材：朱战立编著，数据结构（使用 C语言）第
3版，西 安交通大学出版社, 2003年
参考书：
[1]严蔚敏等，数据结构（ C语言版），清华大
学出版社
[2] 数据结构学习指导与典型题解，朱战立等编
著，西安交通大学出版社, 2002年
6
内 容 安 排
章 内 容 学时 章 内 容 学时
1 绪 论 3 7 树和二叉树 10
2 线性表 9 8 图 4
3 栈和队列 6 9 排序 6
4 串 3 10 查找 6
5 数组 3 11 上机（共六次） 12
6 递归算法 2 合计 1264
7
1、上课认真听讲，适当做好笔记，按时交作业。
2、考试成绩分两部分：平时成绩（包括出勤和上机实验）占
30%，期末成绩占 70%。
3、课后需要多读课文和参考书，上网查看相关内容，在理解
基本内容的基础上，多看、多做习题。
4、上机实验十分重要，一定要在上机前做好充分准备，多采
用不同的数据存储结构和不同的实现算法解决一个问题。
对学生的几点要求
8
第 1章 绪 论
讨论 5个问题：
1.1 数据结构 的基本概念
1.2 学习数据结构的意义
1.3 数据结构涵盖的主要内容
1.4 什么是抽象数据类型
1.5 算法效率的度量
9
1.1 数据结构的基本概念
1、举例
建立一个学生档案。学生表包括学号、姓名、性别、
籍贯。要求：查找, 王红, 是否存在。
解决的方法步骤：
1) 如何记录所有学生记录 （ 及选择何种逻辑数据结
构 ）？
2) 选择何种存储结构？
? 若把所有记录依次存储在一个数组中 —— 采用
顺序存储结构
? 若采用指针链表 —— 采用链式存储结构
10
2、基本术语
(1)数据,所有能被计算机识别、存储和处理的符号的集合（包
括数字、字符、声音、图像等信息 ）。
(2)数据元素,是数据的基本单位, 具有完整确定的实际意义 。
在计算机程序中通常作为一个整体进行考虑和处理 。 一个数
据元素可由若干个数据项组成 。
(3)数据项,构成数据元素的项目 。 它是数据不可分割的最小单
位 。
(4)数据类型,指一个类型和定义在这个类型上的操作集合 。 例：
C语言 （ 基本类型：整型, 浮点型, 字符型等构造类型：数组,
结构, 联合, 指针, 枚举等 ）
(5)抽象数据元素,抽象定义的, 没有实际含义的数据元素 。
(6)抽象数据类型,用户自己定义的数据类型 。
11
2、基本术语 (续）
(7)数据结构,是相互之间存在一种或多种特定关系的数据元素
的集合。或按照一定逻辑关系组织，并按一定存储方法存储
的数据的集合，且需要定义一系列运算。逻辑结构、存储结
构和运算合称为三要素。表示为：
Data_Structure=（ D,R）
其中,D— 元素有限集,R— 关系有限集
12
程序设计＝好算法＋好结构
同样的数据对象，用不同的数据结构来表
示，运算效率可能有明显的差异。
1.2 学习数据结构的意义
计算机内的数值运算依靠方程式, 而非数值运算
（ 如表, 树, 图等 ） 则要依靠数据结构 。
数据结构是一门学科, 针对非数值计算的程序设计
问题, 研究计算机的操作对象以及它们之间的关系和操
作等等 。
13
1.3 数据结构涵盖的内容
14
集合结构,仅同属一个集合
线性结构, 一对一（ 1:1)
树 结 构, 一对多（ 1:n)
图 结 构, 多对多 (m:n)
非线性
线 性
逻辑结构可细分为 4类：
答：指数据元素之间的逻辑关系。即从逻辑关系上描述
数据，它 与数据的存储无关,是 独立于计算机 的。
解释 1,什么叫数据的逻辑结构？
15
（ 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
此结构为 线性 的。
例,用图形表示下列数据结构，并指出它们是属于线
性结构还是非线性结构。
16
d1
d5 d2
d4 d3
该结构 是非线性 的。
解,上述表达式可用图形表示为：
（ 2） S=(D,R)
D={di | 1≤i≤5}
R={(di,dj ),i<j}
17
答：物理结构亦称 存储结构, 是数据的逻辑结构在计
算机存储器内的表示 （ 或映像 ） 。 它 依赖于计算机 。
存储结构可分为 4大类：
例,复数 3.0－ 2.3i 的两种存储方式：
顺序、链式、索引、散列
－ 2.30302
3.00300
04150302
3.00300
0415 － 2.3
法 1,地址 内容 法 2,地址 内容
2字节
解释 2：什么叫数据的物理结构？
18
答：在数据的逻辑结构上定义的操作算法 。
它 在数据的存储结构上实现 。
最常用的数据运算有 5 种：
插入、删除、修改、查找、排序
解释 3：什么是数据的运算？
19
1.4 什么是抽象数据类型
1 数据类型与抽象数据类型的区别？
2 抽象数据类型如何定义？
3 抽象数据类型如何表示和实现？
讨论：
20
1 数据类型与抽象数据类型的区别
数据类型,是一个 值的集合 和定义在该值上的
一组操作 的总称。
抽象数据类型,由 用户定义,用以表示应用问题的数
据模型。它由基本的数据类型构成，并包括一组相关
的 服务 （或称操作）
它与数据类型实质上是一个概念，但其特征是 使用
与 实现分离,实行 封装 和 信息隐蔽 （独立于计算机）
21
2 抽象数据类型如何定义
抽象数据类型 可以用以下的三元组来表示：
ADT = （ D,R,P）
ADT抽象数据类型名 {
数据 对象, <数据对象的定义 >
数据 关系, <数据关系的定义 >
基本 操作, <基本操作的定义 >
} ADT抽象数据类型 名
ADT
常用
定义
格式
数据对象 D上的关系集 D上的操作集
例,给出自然数 (Natural Number )的抽象数据类型定义。
ADT Natural_Number is
objects,一个整数的有序子集合，它开始于 0，结束于机器能
表示的最大整数 (MAX INT)
functions,对于所有的 x,y ? Natural_Number； TRUE,
FALSE ? Boolean； +,-,<,= =,=等都是可用
的服务。
Zero ( ),Natural Number 返回 0
IsZero(x),Boolean if (x==0) 返回 TRUE else 返回 FALSE
Add(x,y),Natural Number if (x+y <= MAX INT)返回 x+y
else 返回 MAX INT
Subtract(x,y),Natural Number if (x<y)返回 0 else 返回 x-y
Equal(x,y),Boolean if (x== y)返回 TRUE else 返回 FALSE
Successor(x), Natural Number if (x == MAX INT)返回 x else 返回 x+1end
Natural_Number
23
1.4.3 抽象数据类型如何表示和实现
抽象数据类型可以通过 固有的 数据类型（如整型、
实型、字符型等）来表示和实现。
（参看课本 P28，线性表的抽象数据类型，思考用
具体 C语言如何实现）
注意,上机时要必须用具体语言实现, 如
C或 C++等
24
1.5 算法效率的度量
1 什么是算法？如何评判算法的好坏？
2 时间复杂度和空间复杂度如何表示？
3 计算举例
讨论：
25
1 什么是算法？如何评判一个算法的好坏？
常用 时间复杂度 来衡量
算法的基本特性：
算法评价指标：
有穷性、确定性、可行性、必有输出
正确性、可读性、健壮性、高效率与低存储量需求 (见课本 P20)
常用 空间复杂度 来衡量
好的程序设计：好算法＋好结构
算法,是对特定问题求解步骤的一种描述，它是指令
的有限序列，是一系列输入转换为输出的计算步骤。
26
注：
1） O（）为渐近符号。
2） 空间复杂度 S(n)按数量级递增顺序也与上表类似。
复杂度高复杂度低
时间复杂度 T(n)按数量级递增顺序为：
2 时间复杂度和空间复杂度如何表示？
多项式阶
27
3n+2=O(n) 因为 3n+2?4n for n?2
6*2n+n2=O(2n) 因为 6*2n+n2 ?7*2n for n?4
例：
渐进符号 （ O）的定义,当且仅当存在一个正的常
数 C，使得对所有的 n ? n0,有 f(n) ? Cg(n)，
则,f(n) = O(g(n))
28
该算法的运行时间由程序中所有语句的 频度 （即该语
句重复执行的次数） 之和 构成。
解：
分析,显然，语句①的频度是 1。设语句 2的频度是 f(n)，则有：
算法的时间复杂度由嵌套最深层语句的频度决定
例,分析以下程序段的时间复杂度。
i=1; ①
while(i<=n)
i=i*2; ②
即 f(n)≤log2n,取最大值 f(n)=log2n
所以该程序段的时间复杂度 T(n)=1+f(n)=1+ log2n= O( log2n)
()2 fn n?
3 计算举例
29
本章小结
数据结构课程 —— 数据结构＋算法＝程序，涉及数
学、计算机硬件和软件。
数据结构定义 —— 指互相有关联的数据元素的集合，
可用 data_Structure=(D,R)表示。
数据结构内容 —— 数据的逻辑结构、存储结构和基
本运算 。
数据结构描述工具 —— 抽象数据类型和 C语言。
算法效率 —— 时间效率和空间效率 。
30
作业：
① 课本 P25 1.2,1.3,1.4,1.7,1.10,1.11题 。
② 建议独立完成辅导材料 —— 第 1章自测卷 。
③ 复习 C语言, 重点是 结构类型, 指针和数组概念 等 。
朱战立编著，数据结构 —— 使用 C
语言（第 3版），西安交通大学出版
社,2003年
数 据 结 构
2
课前的话 —— 计算机系列课程之间的联系
计算机概论与上机操作 （对 21 世纪公民要求）
?
程序设计与算法语言 （ B A S I C F O R T R A N P A S C A L C 等，怎样使用计算机）
?
计算机组成原理 （所有计算机的共性）
?
微机原理及应用 （特定机型介绍，单片机或 8086 P C 机，怎样应用计算机）
控制之路 数据处理之路
? ?
汇编语言程序设计 数据结构
? ?
单片机技术 / 微机接口 操作系统
? ?
软件技术基 础 数据库理论
? ?
计算机网络 软件工程
? ?
应用系统设计 计算机网络
3
数据结构课程的地位
它是计算机专业及相关专业的 核心课
程 之一，是计算机及相关专业的 重要骨干
基础课程 。
它针对非数值计算的程序设计问题，
研究计算机的操作对象以及它们之间的关
系和操作。即其研究目的是研究有效地组
织和处理非数值类型数据的理论、技术和
方法。
4
数据结构的核心研究内容
数据的逻辑结构, 存储结构及它们之
间的关系和相应的基本操作运算的定义和
实现 。
本书围绕数据结构的三种基本结构：
线性结构 （ 第 2-5章 ）, 树形结构 （ 第 7章 ）
和图形结构 （ 第 8章 ） 展开讨论, 研究解
决如下问题：一个具体问题的逻辑数据结
构是什么？ 适宜选用什么样的存储结构？
采用什么样的操作实现算法效率更高？
5
学时数,64（ 52学时授课＋ 12学时上机）
学 分,3.5
教材：朱战立编著，数据结构（使用 C语言）第
3版，西 安交通大学出版社, 2003年
参考书：
[1]严蔚敏等，数据结构（ C语言版），清华大
学出版社
[2] 数据结构学习指导与典型题解，朱战立等编
著，西安交通大学出版社, 2002年
6
内 容 安 排
章 内 容 学时 章 内 容 学时
1 绪 论 3 7 树和二叉树 10
2 线性表 9 8 图 4
3 栈和队列 6 9 排序 6
4 串 3 10 查找 6
5 数组 3 11 上机（共六次） 12
6 递归算法 2 合计 1264
7
1、上课认真听讲，适当做好笔记，按时交作业。
2、考试成绩分两部分：平时成绩（包括出勤和上机实验）占
30%，期末成绩占 70%。
3、课后需要多读课文和参考书，上网查看相关内容，在理解
基本内容的基础上，多看、多做习题。
4、上机实验十分重要，一定要在上机前做好充分准备，多采
用不同的数据存储结构和不同的实现算法解决一个问题。
对学生的几点要求
8
第 1章 绪 论
讨论 5个问题：
1.1 数据结构 的基本概念
1.2 学习数据结构的意义
1.3 数据结构涵盖的主要内容
1.4 什么是抽象数据类型
1.5 算法效率的度量
9
1.1 数据结构的基本概念
1、举例
建立一个学生档案。学生表包括学号、姓名、性别、
籍贯。要求：查找, 王红, 是否存在。
解决的方法步骤：
1) 如何记录所有学生记录 （ 及选择何种逻辑数据结
构 ）？
2) 选择何种存储结构？
? 若把所有记录依次存储在一个数组中 —— 采用
顺序存储结构
? 若采用指针链表 —— 采用链式存储结构
10
2、基本术语
(1)数据,所有能被计算机识别、存储和处理的符号的集合（包
括数字、字符、声音、图像等信息 ）。
(2)数据元素,是数据的基本单位, 具有完整确定的实际意义 。
在计算机程序中通常作为一个整体进行考虑和处理 。 一个数
据元素可由若干个数据项组成 。
(3)数据项,构成数据元素的项目 。 它是数据不可分割的最小单
位 。
(4)数据类型,指一个类型和定义在这个类型上的操作集合 。 例：
C语言 （ 基本类型：整型, 浮点型, 字符型等构造类型：数组,
结构, 联合, 指针, 枚举等 ）
(5)抽象数据元素,抽象定义的, 没有实际含义的数据元素 。
(6)抽象数据类型,用户自己定义的数据类型 。
11
2、基本术语 (续）
(7)数据结构,是相互之间存在一种或多种特定关系的数据元素
的集合。或按照一定逻辑关系组织，并按一定存储方法存储
的数据的集合，且需要定义一系列运算。逻辑结构、存储结
构和运算合称为三要素。表示为：
Data_Structure=（ D,R）
其中,D— 元素有限集,R— 关系有限集
12
程序设计＝好算法＋好结构
同样的数据对象，用不同的数据结构来表
示，运算效率可能有明显的差异。
1.2 学习数据结构的意义
计算机内的数值运算依靠方程式, 而非数值运算
（ 如表, 树, 图等 ） 则要依靠数据结构 。
数据结构是一门学科, 针对非数值计算的程序设计
问题, 研究计算机的操作对象以及它们之间的关系和操
作等等 。
13
1.3 数据结构涵盖的内容
14
集合结构,仅同属一个集合
线性结构, 一对一（ 1:1)
树 结 构, 一对多（ 1:n)
图 结 构, 多对多 (m:n)
非线性
线 性
逻辑结构可细分为 4类：
答：指数据元素之间的逻辑关系。即从逻辑关系上描述
数据，它 与数据的存储无关,是 独立于计算机 的。
解释 1,什么叫数据的逻辑结构？
15
（ 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
此结构为 线性 的。
例,用图形表示下列数据结构，并指出它们是属于线
性结构还是非线性结构。
16
d1
d5 d2
d4 d3
该结构 是非线性 的。
解,上述表达式可用图形表示为：
（ 2） S=(D,R)
D={di | 1≤i≤5}
R={(di,dj ),i<j}
17
答：物理结构亦称 存储结构, 是数据的逻辑结构在计
算机存储器内的表示 （ 或映像 ） 。 它 依赖于计算机 。
存储结构可分为 4大类：
例,复数 3.0－ 2.3i 的两种存储方式：
顺序、链式、索引、散列
－ 2.30302
3.00300
04150302
3.00300
0415 － 2.3
法 1,地址 内容 法 2,地址 内容
2字节
解释 2：什么叫数据的物理结构？
18
答：在数据的逻辑结构上定义的操作算法 。
它 在数据的存储结构上实现 。
最常用的数据运算有 5 种：
插入、删除、修改、查找、排序
解释 3：什么是数据的运算？
19
1.4 什么是抽象数据类型
1 数据类型与抽象数据类型的区别？
2 抽象数据类型如何定义？
3 抽象数据类型如何表示和实现？
讨论：
20
1 数据类型与抽象数据类型的区别
数据类型,是一个 值的集合 和定义在该值上的
一组操作 的总称。
抽象数据类型,由 用户定义,用以表示应用问题的数
据模型。它由基本的数据类型构成，并包括一组相关
的 服务 （或称操作）
它与数据类型实质上是一个概念，但其特征是 使用
与 实现分离,实行 封装 和 信息隐蔽 （独立于计算机）
21
2 抽象数据类型如何定义
抽象数据类型 可以用以下的三元组来表示：
ADT = （ D,R,P）
ADT抽象数据类型名 {
数据 对象, <数据对象的定义 >
数据 关系, <数据关系的定义 >
基本 操作, <基本操作的定义 >
} ADT抽象数据类型 名
ADT
常用
定义
格式
数据对象 D上的关系集 D上的操作集
例,给出自然数 (Natural Number )的抽象数据类型定义。
ADT Natural_Number is
objects,一个整数的有序子集合，它开始于 0，结束于机器能
表示的最大整数 (MAX INT)
functions,对于所有的 x,y ? Natural_Number； TRUE,
FALSE ? Boolean； +,-,<,= =,=等都是可用
的服务。
Zero ( ),Natural Number 返回 0
IsZero(x),Boolean if (x==0) 返回 TRUE else 返回 FALSE
Add(x,y),Natural Number if (x+y <= MAX INT)返回 x+y
else 返回 MAX INT
Subtract(x,y),Natural Number if (x<y)返回 0 else 返回 x-y
Equal(x,y),Boolean if (x== y)返回 TRUE else 返回 FALSE
Successor(x), Natural Number if (x == MAX INT)返回 x else 返回 x+1end
Natural_Number
23
1.4.3 抽象数据类型如何表示和实现
抽象数据类型可以通过 固有的 数据类型（如整型、
实型、字符型等）来表示和实现。
（参看课本 P28，线性表的抽象数据类型，思考用
具体 C语言如何实现）
注意,上机时要必须用具体语言实现, 如
C或 C++等
24
1.5 算法效率的度量
1 什么是算法？如何评判算法的好坏？
2 时间复杂度和空间复杂度如何表示？
3 计算举例
讨论：
25
1 什么是算法？如何评判一个算法的好坏？
常用 时间复杂度 来衡量
算法的基本特性：
算法评价指标：
有穷性、确定性、可行性、必有输出
正确性、可读性、健壮性、高效率与低存储量需求 (见课本 P20)
常用 空间复杂度 来衡量
好的程序设计：好算法＋好结构
算法,是对特定问题求解步骤的一种描述，它是指令
的有限序列，是一系列输入转换为输出的计算步骤。
26
注：
1） O（）为渐近符号。
2） 空间复杂度 S(n)按数量级递增顺序也与上表类似。
复杂度高复杂度低
时间复杂度 T(n)按数量级递增顺序为：
2 时间复杂度和空间复杂度如何表示？
多项式阶
27
3n+2=O(n) 因为 3n+2?4n for n?2
6*2n+n2=O(2n) 因为 6*2n+n2 ?7*2n for n?4
例：
渐进符号 （ O）的定义,当且仅当存在一个正的常
数 C，使得对所有的 n ? n0,有 f(n) ? Cg(n)，
则,f(n) = O(g(n))
28
该算法的运行时间由程序中所有语句的 频度 （即该语
句重复执行的次数） 之和 构成。
解：
分析,显然，语句①的频度是 1。设语句 2的频度是 f(n)，则有：
算法的时间复杂度由嵌套最深层语句的频度决定
例,分析以下程序段的时间复杂度。
i=1; ①
while(i<=n)
i=i*2; ②
即 f(n)≤log2n,取最大值 f(n)=log2n
所以该程序段的时间复杂度 T(n)=1+f(n)=1+ log2n= O( log2n)
()2 fn n?
3 计算举例
29
本章小结
数据结构课程 —— 数据结构＋算法＝程序，涉及数
学、计算机硬件和软件。
数据结构定义 —— 指互相有关联的数据元素的集合，
可用 data_Structure=(D,R)表示。
数据结构内容 —— 数据的逻辑结构、存储结构和基
本运算 。
数据结构描述工具 —— 抽象数据类型和 C语言。
算法效率 —— 时间效率和空间效率 。
30
作业：
① 课本 P25 1.2,1.3,1.4,1.7,1.10,1.11题 。
② 建议独立完成辅导材料 —— 第 1章自测卷 。
③ 复习 C语言, 重点是 结构类型, 指针和数组概念 等 。
