1
数据结构
主讲教师 邢振祥
总学时：60\r讲课学时：50\r实验学时：10\r教材： 《数据结构C语言版》严蔚敏、吴伟民\r -----清华大学出版社\r 《数据结构C语言篇》习题与解析 李春葆\r -----清华大学出版社
课程安排
课程要求
课前请做好预习\r保持课堂安静，头脑清醒，思维活跃\r认真、独立、按时完成并提交作业\r重视上机实践，有效利用宝贵的上机时间
上机安排\r上机地点：机房\r上机时间：\r上机内容：\r要求:\r所有作业必须独立完成\r算法作业必须经上机调试通过\r上机考勤3次缺席，按不及格处理\r发现上机时间上网，按缺席一次处理
课程重要性
核心基础课程\r编程基础\r考研课程\r计算机等级考试课程\r程序员考试课程\r
请同学们把本课程的学习重视起来！！！
1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示和实现 1.4 算法和算法分析
第一章 绪论
教学目的： （1）了解数据结构及算法的概念； （2）掌握计算语句频度和估算算法时间复杂度的方法。 教学的重点和难点：估算算法时间复杂度。
第一章 绪论
1.1 什么是数据结构\r什么是程序、软件？\r N.沃思（Niklaus Wirth)教授提出：\r 程序=算法 数据结构\r 程序设计:为计算机处理问题编制一组指令集\r算法:处理问题的策略\r数据结构:问题的数学模型 \r 软件=程序 文档（软件工程的观点）
电子计算机的主要用途：\r?早期：\r 主要用于数值计算。\r?后来：\r 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。
数值计算解决问题的一般步骤：\r数学模型→选择计算机语言→编出程序→测试→最终解答。\r数值计算的关键是：如何得出数学模型（方程）？\r程序设计人员比较关注程序设计的技巧。\r非数值计算问题：\r数据元素之间的相互关系一般无法用数学方程加以描述
例1 学籍管理问题——表结构
完成什么功能?各表项之间是什么关系？
例2 人机对弈问题——树结构
如何实现对弈?各格局之间是什么关系？
例3 教学计划编排问题——图结构
如何表示课程之间的先修关系？
求解非数值计算的问题：\r 主要考虑的是设计出合适的数据结构及相应的算法。\r即：首先要考虑对相关的各种信息如何表示、组织和存储？\r因此，可以认为：数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。
数据结构课程的形成和发展：\r形成阶段：\r60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。\r发展阶段：\r数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。\r70年代后期，我国高校陆续开设该课程。\r\r
《数据结构课程》所处的地位：\r
1.2 基本概念和术语\r数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。\r数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。\r 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。\r三者之间的关系：数据 > 数据元素 > 数据项\r例：班级通讯录 > 个人记录 > 姓名、年龄……\r数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。
\r序偶：由两个具有给定次序的元素x和y所组成的序列,记为
数据结构：
带结构的数据元素的集合
假设用三个 4 位的十进制数表示一个含 12 位数的十进制数。
3214,6587,9345 ─ a1(3214),a2(6587),a3(9345)
则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 ?a1,a2?、?a2,a3?
3214，6587，9345 \r a1 a2 a3
6587，3214，9345\r a2 a1 a3
≠
例如:
又例，在2行3列的二维数组{a1, a2, a3, a4, a5, a6}\r中六个元素之间\r存在两个关系:
行的次序关系:\r\r列的次序关系:
row = {
col = {
a1 a3 a5\r a2 a4 a6
a1 a2 a3\ra4 a5 a6
再例，在一维数组 {a1, a2, a3, a4, a5, a6} 的数据元素之间存在如下的次序关系:
{
或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。
可见，不同的“关系”构成不同的“结构”
具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算
数据的逻辑结构
逻辑结构：指数据元素之间逻辑关系的整体。
数据的逻辑结构是从具体问题抽象出来的数据模型
逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
数据的逻辑结构
数据结构从逻辑上分为四类：\r⑴ 集合：数据元素之间就是\r “属于同一个集合” ；
数据的逻辑结构
数据结构从逻辑上分为四类：\r⑴ 集合：数据元素之间就是 “属于同一个集合” ；\r⑵ 线性结构：数据元素之间 存在着一对一的线性关系；
数据的逻辑结构
数据结构从逻辑上分为四类：\r⑴ 集合：数据元素之间就是 “属于同一个集合” ；\r⑵ 线性结构：数据元素之间存在着一对一的线性关系；\r⑶ 树结构：数据元素之间存在着一对多的层次关系；
数据的逻辑结构
数据结构从逻辑上分为四类：\r⑴ 集合：数据元素之间就是 “属于同一个集合” ；\r⑵ 线性结构：数据元素之间存在着一对一的线性关系；\r⑶ 树结构：数据元素之间存在 着一对多的层次关系；\r⑷ 图结构：数据元素之间存在 着多对多的任意关系。
数据结构的形式定义为:
数据结构是一个二元组
Data_Structures = (D, S)
其中:D 是数据元素的有限集，\r S 是 D上关系的有限集。
例：用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。
（1） S=(D, R)\r D={ a, b, c, d, e, f }\r R={
解： 上述表达式可用图形表示为：
b c a e f d
此结构为线性的。
（2） S=(D, R) D={di | 1≤i≤5} R={ d1\r\r d5 d2\r\r\r d4 d3\r 该结构是非线性的。 解：上述表达式可用图形表示为： 数据的物理结构 物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。 例：（见教材P6）复数3.0－2.3i 的两种存储方式： 法1：地址 内容 法2：地址 内容 2字节 在不同的编程环境中， 存储结构可有不同的描述方法。 当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。 例如: 以三个带有次序关系的整数表示一个长整数时，可利用 C 语言中提供的整数数组类型。 typedef int Long_int [3] 定义长整数为: 逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。\r\r 一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。 数据的运算(算法) 在数据的逻辑结构上定义的操作算法。\r它在数据的存储结构上实现。 最常用的数据运算有5种： 插入、删除、修改、查找、排序 数据类型：是一个值的集合和定义在该值上\r 的一组操作的总称。 抽象数据类型：是用户在数据类型基础上新定义的数据类型。是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型定义包括数据组成和对数据的处理操作。 它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 例 C语言中，提供int, char, float, double等基本\r 数据类型，数组、结构体、共用体、枚举\r 等构造数据类型，还有指针、空(void)类\r 型等。用户也可用typedef 自己定义数据类型 抽象数据类型可以用以下的三元组来表示：\r ADT = （D，S，P）\r\r 数据对象 D上的关系集 D上的操作集 ADT抽象数据类型名{ \r 数据对象：<数据对象的定义>\r 数据关系：<数据关系的定义> \r 基本操作 ：<基本操作的定义> \r } ADT抽象数据类型名 ADT常用定义格式 数据对象和数据关系的定义用伪码描述,基本操作定义格式为 基本操作名(参数表)\r 初始条件:<初始条件描述>\r 操作结果:<操作结果描述> 例如，抽象数据类型复数的定义： 数据对象：\r D＝{e1,e2｜e1,e2∈RealSet }\r 数据关系：\r R1＝{ ADT Complex { 基本操作： AssignComplex(