数据结构 徐虹 http:/jwc.cuit.edu.cn/jxgl/ HomePage/Default. asp 说明 据>总学时: 构 80(学时)=60(课时)+20(机时) 行课时间从第1周开始,每周4学时 上机安排待定 >考试时间:课程结束 第8、11、12章的内容为自学内容; 目录中标有*的内容不作要求
1 数据结构 徐 虹 http://jwc.cuit.edu.cn/Jxgl/ HomePage/Default.asp 数 据 结 构 之 绪 论 2 说明 ¾ 总学时： 80(学时)= 60（课时）+20（机时） ¾ 行课时间从第 1 周 开始，每周 4 学时 ¾ 上机安排待定 ¾ 考试时间：课程结束 ¾ 第8、11、12 章的内容为自学内容； ¾ 目录中标有 ** 的内容不作要求
教材与参考书 据>严蔚敏,《数据结构》,清华大学出版社 结 构> Clifford A. Shaffer,《数据结构与算法 分析》,电子工业出版社 > Sartaj Sahni,,《数据结构、算法与应用》 机械工业出版社 论>严蔚敏,《数据结构题集》,清华大学出 版社 目录 据 第一章:绪论 构 第二章:线性表 第三章:栈和队列 第四章:串 第五章:数组和广义表 绪 第六章:树和二叉树 第七章:图 第八章:查找 第九章:内部排序
2 数 据 结 构 之 绪 论 3 教材与参考书 ¾ 严蔚敏，《数据结构》，清华大学出版社 ¾ Clifford A. Shaffer, 《数据结构与算法 分析》，电子工业出版社 ¾ Sartaj Sahni, 《数据结构、算法与应用》, 机械工业出版社 ¾ 严蔚敏，《数据结构题集》，清华大学出 版社 数 据 结 构 之 绪 论 4 目录 第一章：绪论 第二章：线性表 第三章：栈和队列 第四章：串 第五章：数组和广义表 第六章：树和二叉树 第七章：图 第八章：查找 第九章：内部排序
第一章绪论 什么是数据结构 算法和算法分析 1.1什么是数据结构 数据结构的引论 据 例1图书馆的书目检索系统自动化问题 构 在书目自动检索系统中可以建立一张按等录顺序号 排列的书目文件和三张分别按书名、作者名和分类号 顺序排列的索引表,如下所示: 绪 001高等数学樊映川 002理论力学罗远祥L01 003高等数学华罗庚s0 004线形代数栾汝书sn2|…
3 第一章 绪论 什么是数据结构 算法和算法分析 数 据 结 构 之 绪 论 6 1. 1 什么是数据结构 ¾ 数据结构的引论 ¾ 例1 图书馆的书目检索系统自动化问题 在书目自动检索系统中可以建立一张按等录顺序号 排列的书目文件和三张分别按书名、作者名和分类号 顺序排列的索引表，如下所示： 001 002 003 004 ... ... ... ... 高等数学 理论力学 高等数学 线形代数 樊映川 罗远祥 华罗庚 栾汝书 S01 L01 S01 S02 . . . . . . .
按书名排列 按作者排列 据高等数学0010 樊映川 结 理论力学 华罗庚003,… 线形代数 004 栾汝书 按索引号排列 论 特点:计算机按某个特定的要 001,003·· 求进行奎询.处理对象之间存在 一种简单的线形关系,这类模型 可以称为简单的线形数据结构 >例2:计算机和人的对弈问题 对奕的过程是在一定的规则下随机进行的因此计算 据 机必须对对弈过程之中可能发生的情况以及相应 的对策都考虑周全这个关系不是线形的,从 构 棋盘可以派生出几个格局如下图 (a)棋盘格式示例 (b)并字棋对奔树的局部 树根”是对奕开始之前的棋盘格局而所有的“叶子”是可能出现 的结局对奕的过程就是从树根沿树叉到达某个叶子的过程
4 数 据 结 构 之 绪 论 7 高等数学 理论力学 线形代数 001,003, … 002, … 004, … ... . . . L S 002, 001, 003 ... ... . . . . . . 特点：计算机按某个特定的要 求进行查询.处理对象之间存在 一种简单的线形关系,这类模型 可以称为简单的线形数据结构. 按书名排列 樊映川 华罗庚 栾汝书 001, 003, 004, ... ... ... . . . . . . 按作者排列 按索引号排列 数 据 结 构 之 绪 论 8 ¾ 例2: 计算机和人的对弈问题 对奕的过程是在一定的规则下随机进行的,因此,计算 机必须对对弈过程之中可能发生的情况以及相应 的对策都考虑周全.这个关系不是线形的,从一个 棋盘可以派生出几个格局,如下图: “树根”是对奕开始之前的棋盘格局,而所有的“叶子”是可能出现 的结局,对奕的过程就是从树根沿树叉到达某个叶子的过程. * * * * * * * * * * * * * * * * * * (a) 棋盘格式示例 (b)井字棋对弈树的局部
据结构 例3:多叉路口交通灯的管理问题 以把这类交通道路的问题当作一种“图”的结构:一个顶点表 示一条通道而通道之间的矛盾的关系以两个顶点之间的连 线表示如下图所示 B (a)五叉路口 数据结构 结论:综合上面三个例子描述这类非数值计算性问 题的数学模型不再是数学方程而是诸如表、树和图之 类的数据结构. 数据结构定义: 数据结构是一门非数值计算的程序设计问题中计 绪 算机的操作对象以及它们之间的关系和操作等等的学 科
5 数 据 结 构 之 绪 论 9 ¾ 例3: 多叉路口交通灯的管理问题 可以把这类交通,道路的问题当作一种“图”的结构：一个顶点表 示一条通道,而通道之间的矛盾的关系以两个顶点之间的连 线表示.如下图所示: A E D C B (a) 五叉路口 数 据 结 构 之 绪 论 10 ¾ 结论：综合上面三个例子,描述这类非数值计算性问 题的数学模型不再是数学方程,而是诸如表、树和图之 类的数据结构. ¾ 数据结构定义: 数据结构是一门非数值计算的程序设计问题中计 算机的操作对象以及它们之间的关系和操作等等的学 科
数据结构的地位 《数据结构》是计算机科学中一门综合性的专业基础课 数据结构 数据结构的研究不仅涉及计算机的硬件的研究范围 而且和计算机软件的研究有着更为密切的关系,无论 是编译程序还是操作系统,都涉及数据元素在存储器 中的分配问题。可以认为数据结构是介于数学、计算 机硬件、计算机软件三者之间的一门核心课程。 数学 代数系统 「数 字关系 数据表示法,运第 存储装置数据结构件系 硬件 机器组信息检素 软件 1.2基本概念 数据结构 数据(Data 客观事物的符号表示,能输入到计算机中并被计算 机中程序处理的符号的总称。 >数据元素( Data element) 数据的基本单位,可由数据项组成。 >数据类型( Data Type) 是和数据结构密切相关的一个概念,在高级语言中, 用以刻画(程序)操作对象的特性。是一个值的集合 和定义在这个值集上的一组操作的总称
6 数 据 结 构 之 绪 论 11 ¾ 数据结构的地位 《数据结构》是计算机科学中一门综合性的专业基础课。 数据结构的研究不仅涉及计算机的硬件的研究范围， 而且和计算机软件的研究有着更为密切的关系，无论 是编译程序还是操作系统，都涉及数据元素在存储器 中的分配问题。可以认为数据结构是介于数学、计算 机硬件、计算机软件三者之间的一门核心课程。 数 据 结 构 之 绪 论 12 1. 2 基本概念 ¾ 数据（Data) 客观事物的符号表示，能输入到计算机中并被计算 机中程序处理的符号的总称。 ¾ 数据元素 (Data element) 数据的基本单位，可由数据项组成。 ¾ 数据类型 (Data Type) 是和数据结构密切相关的一个概念，在高级语言中， 用以刻画（程序）操作对象的特性。是一个值的集合 和定义在这个值集上的一组操作的总称
据>数据对象( Data object 结 性质相同的数据元素的集合,是数据的子集。 >数据结构( Data structure) 相互之间存在一种或多种特定关系的数据元素的集 合。数据元素之间的相互关系称为结构。有下列四种 基本结构: (1)集合(2)线形结构(3)树形结构(4)图状结构(网状 结构) 数据结构 ○○○○○ 集合 性 绪
7 数 据 结 构 之 绪 论 13 ¾ 数据对象 (Data Object) 性质相同的数据元素的集合，是数据的子集。 ¾ 数据结构 (Data Structure) 相互之间存在一种或多种特定关系的数据元素的集 合。数据元素之间的相互关系称为结构。有下列四种 基本结构： （1）集合（2）线形结构（3）树形结构（4）图状结构(网状 结构）。 数 据 结 构 之 绪 论 14 集合 线 性 图 树
数据结构类型 据数据结构又可以分为两种:物理结构、逻辑结构 结 其基本类型用关系图描述如下: 数据结构的形式定义: Data Structure=D,SI 其中:D是数据元素的有限集 S是上下关系的有限集 数据的存储结构:位、元素和数据域 数据结构的存储形式有: >顺序存储 >链式存储 虚拟存储结构 数据类型综述 据 数据类型可以分为 构原子类型值不可以分解 结构类型值由若干成分按某种结构组成。 之抽象数据类型(AD)是一个值的集合和定义 在这个值集上的一组操作的总称包括 论原子类型、固定聚合类型和可变聚合类型。 抽象数据类型可通过固有数据类型来表示和实现 借助高级语言实现的三种情况:封装、继承、 多型
8 数 据 结 构 之 绪 论 15 ¾ 数据结构类型 数据结构又可以分为两种：物理结构、逻辑结构 其基本类型用关系图描述如下： ¾ 数据结构的形式定义： Data_Structure=[D,S] 其中： D是数据元素的有限集 S是上下关系的有限集 ¾ 数据的存储结构：位、元素和数据域 ¾ 数据结构的存储形式有： ¾顺序存储 ¾链式存储 ¾ 虚拟存储结构 数 据 结 构 之 绪 论 16 ¾ 数据类型综述 数据类型可以分为： 原子类型——值不可以分解 结构类型——值由若干成分按某种结构组成。 抽象数据类型（ADT）是一个值的集合和定义 在这个值集上的一组操作的总称。包括： 原子类型、固定聚合类型和可变聚合类型。 抽象数据类型可通过固有数据类型来表示和实现， 借助高级语言实现的三种情况：封装、继承、 多型
数据操作描述 数据的基本操作: 精插入:在数据结构的指定位置添加新的数据元素 拆除:去掉数据结构中某个指定的数据元素 更新:改变数据结构中某个数据元素的值 查找:在数据结构中寻找某个满足特定要求的数据元素。 排序:重新安排数据元素的逻辑顺序关系,使之值按从 小到大或从大到小的顺序排列 数据结构 操作的分类 >加工型操作操作改变了(操作之前 的)结构的值。 引用型操作不改变值,只是查询或 求得结构的值。 绪 操作的描述
9 数 据 结 构 之 绪 论 17 ¾ 数据操作描述 ¾ 数据的基本操作： 插入：在数据结构的指定位置添加新的数据元素。 拆除：去掉数据结构中某个指定的数据元素。 更新：改变数据结构中某个数据元素的值。 查找：在数据结构中寻找某个满足特定要求的数据元素。 排序：重新安排数据元素的逻辑顺序关系，使之值按从 小到大或从大到小的顺序排列。 数 据 结 构 之 绪 论 18 ¾ 操作的分类 ¾加工型操作——操作改变了（操作之前 的）结构的值。 ¾引用型操作——不改变值，只是查询或 求得结构的值。 ¾ 操作的描述
1.3抽象数据类型的表示与实现 据结构 语言的描述 预定义常量和类型 f define true f define false 0 define OK f define Error 0 Status是函数的类型,其值是函数结果状态代码 typedef int Status 数据结构的表示用类型定义( typedef)描述,数 据元素类型约定为 ElemType,可以是C语言中任 何数据类型。 >基本操作的算法用以下形式函数来描述 函数类型函数名(函数参数表) 数据结构 { ∥算法说明 语句序列 函数名 C语言中操作的描述 赋值语句 绪 循环语句 选择语句 注释 结束语句 输入和输出语句 逻辑运算约定
10 数 据 结 构 之 绪 论 19 1. 3 抽象数据类型的表示与实现 ¾ 语言的描述 ¾ 预定义常量和类型 # define TRUE 1 # define FALSE 0 # define OK 1 # define ERROR 0 Status是函数的类型，其值是函数结果状态代码 typedef int Status ¾ 数据结构的表示用类型定义（typedef）描述，数 据元素类型约定为ElemType，可以是C语言中任 何数据类型。 数 据 结 构 之 绪 论 20 ¾ 基本操作的算法用以下形式函数来描述 函数类型 函数名（函数参数表） { // 算法说明 语句序列 } //函数名 ¾ C语言中操作的描述 ¾ 赋值语句 ¾ 循环语句 ¾ 选择语句 ¾ 注释 ¾ 结束语句 ¾ 输入和输出语句 ¾ 逻辑运算约定