任课教师：赵玉艳 电话：18019817962 邮箱: zhyy@chzu.edu.cn 数据结构 第1章 绪论（一） 任课教师：赵玉艳 电话：18019817962 邮箱: zhyy@chzu.edu.cn 1/

课程介绍 为什么要学习数据结构 编程基础 计算机及相关专业考研考博课程 计算机等级考试课程 程序员考试课程 2/

课程介绍 课程特点：内容抽象、概念性强、内容灵活、不易掌握 1.提前预习、认真听课、按时完成书面及上机作业 2.注意先修课程的知识准备 离散数学、C语言 3.注意循序渐进： 基本概念、基本思想、基本步骤、算法设计 4.注意培养算法设计的能力 理解所讲算法、对此多做思考：若问题要求不同，应如何选择数据结构，设计有效的算法

课程介绍 网络教学资源 考核方式 参考教材 毕博网上教学平台： http://bb.chzu.edu.cn 平时成绩 20% 胡学钢. 数据结构（C语言版）. 高等教育出版社. 严蔚敏, 吴伟民. 数据结构. 清华大学出版社. 网络教学资源 毕博网上教学平台： http://bb.chzu.edu.cn 考核方式 平时成绩 20% 实验成绩 30% 期末考试 50% 4/

教学内容 什么是数据结构 基本概念和术语 抽象数据类型的表示与实现 5/

什么是数据结构 计算机的用途 早期 后来： 主要用于数值计算。 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。 1946年2月14日，世界上第一台电脑ENIAC在美国宾夕法尼亚大学诞生。 　　第二次世界大战期间，美国军方要求宾州大学莫奇来（Mauchly）博士和他的 学生爱克特（Eckert） 设计以真空管取代继电器的"电子化"电脑--ENIAC （Electronic Numerical Integrator and Calculator）， 电子数字积分器与计 算器）， 目的是用来计算炮弹弹道。 数据结构 6/

什么是数据结构 计算机解决一个具体问题一般需要的步骤 从具体问题抽象出一个适合的数学模型 设计或选择一个解此数学模型的算法 编写出程序进行调试、测试 解答 建模：将一个具体的问题用共性的形式描述出来，包括所描述问题的数据对象及其关系的描述、问题求解的要求及方法等。如工资表和学生成绩表，查询，修改的操作都是相似的。 7/

什么是数据结构 非数值计算问题 例1：电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1, b1)，(a2, b2)，…(an, bn)，其中ai, bi(i=1，2…n) 分别表示某人的名字和电话号码。 本问题是一种典型的表格问题。如表1-1，数据与数据成简单的一对一的线性关系。 要求编写一个计算机程序，查询计算机学院所有学生的电话号码，查找到，就输出号码，否则，输出没有电话。思考，怎么编写（用c语言数组） 数值计算问题 全球天气预报 ——环流模式方程 （球面坐标系） 姓名 电话号码 陈海 13612345588 李四锋 13056112345 。。。 表1-1 线性表结构 8

例2：磁盘目录文件系统 本问题是一种典型的树型结构问题，数据与数据成一对多的关系，是一种典型的非线性关系结构—树形结构。 图1-1 树形结构 磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推： 图1-1 树形结构

例3：交通网络图 从一个地方到另外一个地方可以有多条路径。本问题是一种典型的网状结构问题，数据与数据成多对多的关系，是一种非线性关系结构。 佛山 惠州 广州 中山 东莞 深圳 珠海 图1-2 网状结构 其他例子： 图书馆的书目检索系统自动化问题 教师资料档案管理系统 多叉路口交通灯的管理问题 10

什么是数据结构 求解非数值计算的问题 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？ 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 11/

什么是数据结构 学习数据结构的意义 更好地使用计算机来解决实际问题。 算法+数据结构=程序（尼古拉斯·沃斯） 数据结构是介于数学、计算机硬件和软件三者之间的一门核心课程。 尼古拉斯·沃斯（Niklaus Wirth，1934年2月15日—），生於于瑞士温特图尔，是瑞士计算机科学家 凡是学过一点计算机的人大概都知道“算法+数据结构=程序”这一著名公式。提出这一公式并以此作为其一本专著书名的瑞士计算机科学家尼克劳斯·威茨（Niklaus Wirth）于1984 年获得了图灵奖。这是瑞士学者中唯一获此殊荣的人。 交换机里一般在做链路聚合的时候每创建一个聚合组后都会创建一个和这个聚合组对应的哈希表。 12/

《数据结构》所处的地位： 介于数学、计算机硬件和计算机软件三者之间的一门核心课程

数据结构在计算机学科中的地位 北京林业大学信息学院 04:46

课程目的 能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存贮结构及其相应的算法； 学习一些常用的算法； 复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读； 初步掌握算法的时间分析和空间分析技术

基本概念和术语 几个概念 数据(Data): 是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并能被计算机程序处理的符号的总称。 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。在不同的条件下,数据元素又可称为元素、结点、顶点、记录等。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。 以信息学院人员基本信息表 为例，讲解数据（基本信息）、数据元素（记录）、数据项（属性）、数据对象（学生、教师）、数据结构的概念。 一本书的书目信息为一个数据元素，而书目信息的每一项（如书名、作者名等）为一个数据项。 16/

基本概念和术语 数据结构(Data Structure)是指数据元素之间的相互关系，即数据的组织形式。 一般包括三个方面的内容： 数据元素之间的逻辑关系，即数据的逻辑结构。 数据元素及逻辑关系在计算机存储器内的表示方式，即数据的存储结构。 数据的运算，即对数据施加的操作。 17/

基本概念和术语 逻辑结构 集合 线性结构 非线性结构: 树形结构、图状结构 与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型，只抽象反映数据元素的逻辑关系。 18/

集合——数据元素间除“同属于一个集合”外，无其它关系 线性结构——一个对一个，如线性表、栈、队列 树形结构——一个对多个，如树 图状结构——多个对多个，如图 19/

基本概念和术语 数据结构的形式定义 Data_Structure = （D, R） 的有限集合。 例 复数的数据结构定义如下： Complex=(C，R) 其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实和 虚部。R={ P }，P是定义在集合C上的一种关系{〈C1，C2〉}。 20/

基本概念和术语 例已知数据结构的二元组形式表示分别如下所示，判断各数据结构属于哪一种结构。 A=（K，R） 其中：K={a，b，c，d，e，f，g，h}，R={r}，r={<a，b>，<b，c>，<c，d>，<d，e>，<e，f>，<f，g>，<g，h>}。 C=（K，R） 其中：K={ a，b，c，d，e ,f}，R={r}，r={<a，b>，<a，c>，<b，d>，<b，e>，<c，f>}。 E=（K，R） 其中：K={1，2，3，4，5，6，7}，R={r}，r={<1，2>，<2，1>，<1，4>，<4，1>，<2，3>，<3，2>，<3，4>，<4，3>，<1，3>，<3，1>}。 21/

基本概念和术语 物理结构（存储结构） 存储结构两方面的内容 基本的存储结构 数据元素及其关系在计算机存储器中的存储方式; 是逻辑结构用计算机语言的实现，它依赖于计算机语言。 存储结构两方面的内容 数据元素自身值的表示。 数据元素间逻辑关系的表示。 基本的存储结构 顺序存储结构 链式存储结构 22/

顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据 数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 23/

顺序存储 元素n …….. 元素i 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容 Loc(元素i)=Lo+（i-1)*m 顺序存储 24/

h h ∧ 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. 元素2 1536 元素3 1345 链式存储 1345 h 元素1 1400 元素2 1536 元素3 1346 元素4 ∧ 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. 元素2 1536 元素3 25/

数据的运算：检索、排序、插入、删除、修改等 基本概念和术语 小结 数据的逻辑结构、存储结构和数据的运算构成了数据结构三个方面的含义。 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队列、串 树形结构 图形结构 逻辑结构 唯一 存储结构 不唯一 运算的实现 依赖于 26/

数据类型 程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。 定义：一个值的集合和在这个集合上定义的一组操作的总称。 按值的不同特性，数据类型可分为 非结构的原子类型: C语言中，提供int, char, float, double等基本数据类型 结构类型:数组、结构体、共用体、枚举等 查找：顺序查找 二分查找（先排序） 线性结构 树形结构 数据结构和数据类型之间的关系 数据结构 = 数据元素 + 数据关系； 数据类型 = 数据结构 + 数据操作； 所以数据类型的范畴是大于数据结构的。 数据类型的范畴和类有点相似。其实类也是一种数据类型。 int,char基本类型 同样可以抽象成数据结构和数据元素的模型，只是这里的数据元素是规定内存分配大小。只要定义了一个变量或者一个对象，这个变量或者对象就应该是有值的，因为内存单元是实实在在存在的，只要有内存单元就会有值，然后我们可以初始化这个变量或者对象，然后对其进行操作。 27/

抽象数据类型 (ADTs: Abstract Data Types) 更高层次的数据抽象 由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的操作

抽象数据类型可以用以下的三元组来表示： ADT = （D，S，P） ADT抽象数据类型名{ 数据对象：<数据对象的定义> 数据对象 D上的关系集 D上的操作集 ADT抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作 ：<基本操作的定义> } ADT抽象数据类型名 ADT常用定义格式

信息隐蔽和数据封装，使用与实现相分离 查找　插入　 删除 修改 抽象数据类型 接口或用户界面 线性表 数据类型的物理实现封装

1.3 抽象数据类型的表示与实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 1.3 　抽象数据类型的表示与实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 它有些类似C语言中的结构（struct)类型，但增加了相关的操作 教材中用的是类C语言（介于伪码和C语言之间）作为描述工具 但上机时要用具体语言实现，如C或C++等

(1) 预定义常量及类型 //函数结果状态代码 // Status是函数返回值类型，其值是函数结果状态代码。 #define OK 1 #define ERROR 0 #define OVERFLOW -2 // Status是函数返回值类型，其值是函数结果状态代码。 typedef int Status;

(2)数据元素被约定为ElemType 类型，用户需要根据具体情况，自行定义该数据类型。 (3)算法描述为以下的函数形式： 函数类型 函数名（函数参数表） { 语句序列； }

（4）内存的动态分配与释放 （5）赋值语句 （6）选择语句 （7）循环语句 使用new和delete动态分配和释放内存空间

（8）使用的结束语句形式有： 函数结束语句 return 循环结束语句 break; 异常结束语句 exit（异常代码）；

（9）输入输出语句形式有： 输入语句 cin (scanf( )) 输出语句 cout (printf( )) （10）扩展函数有： 求最大值 max 求最小值 min

作业 1.名词解释：数据、数据元素、数据对象、抽象数据类型 2.描述数据结构、逻辑结构、存储结构和运算的有关概念及其相互之间的关系。 3.输入10个学生的学号、姓名和成绩，输出学生的成绩等级和不及格人数。 每个学生的记录包括学号、姓名、成绩和等级 要求定义和调用函数set_grade根据学生成绩设置等级，并统计不及格人数 等级设置： A ：85－100；B：70－84；C：60－69；D：0－59 37/