1 School of Computing and Information Engineering

数据结构 第1讲 绪论（一） 任课教师：杨斌 邮箱: ybcup@126.com 2/

课程地位 人才培养方案 课程地位 数据结构 C/C++语言 数据结构是软件开发的基础 通信软件和互联网应用系统开发 通信或网络基础：操作系统、无线通信 移动通信、通信网络、网络安全、多媒体通信 数据结构 数据结构是软件开发的基础 C/C++语言 3/

课程介绍 课程地位 核心专业课； 课程内容 线性表、栈、队列、串、数组、二叉树、图等典型数据结构的设计方法，各种典型排序和查找算法的性能和设计方法，以及各种典型数据结构的应用等 4/

课程介绍 课程目标 能够根据实际问题设计恰当的逻辑结构、存储结构以及相应的算法； 掌握算法的时间和空间复杂度的分析方法； 具备初步应用数据结构和算法基本理论分析和解决实际问题的能力。 5/

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

课程介绍 参考教材 网络教学资源 考核方式 胡学钢. 数据结构（C语言版）. 高等教育出版社. 严蔚敏, 吴伟民. 数据结构. 清华大学出版社. 网络教学资源 网上教学平台：http://chzu.gj.chaoxing.com/portal 考核方式 平时成绩 20%、实验成绩 30%、期末考试 50% 注意：两次迟到算一次旷课，旷课两次取消考试资格。 7/

第 1 讲 绪言(一)

本讲教学目标 1. 了解数据结构的发展; 2. 掌握数据结构的基本概念和术语; 3. 了解抽象数据类型的概念。

什么是数据结构 程序=数据结构+算法 例1 书目自动检索系统 书目卡片 线性表 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 书目文件 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目卡片 按书名 按作者名

树 例2 人机对奕问题 …….. …...

图 例3 最短路径问题

总结三个例题 三个例题都是非数值计算问题，它们的数学模型分别是线性表(例1)、树(例2)和图(例3)。 《数据结构》是一门研究非数值计算问题中的操作对象，以及它们之间的关系和操作等的学科。 13/19

基本概念和术语 根据数据元素间关系的基本特性，有四种基本数据结构 （集合）——数据元素间除“同属于一个集合”外，无其它关系 数据（data)—所有能输入到计算机中去的描述客观事物的符号 数据元素（data element）—数据的基本单位，也称节点（node）或记录（record） 数据项（data item）—有独立含义的数据最小单位，也称域(field) 数据对象：性质相同的数据元素的集合。 数据结构：数据元素以及数据元素与数据元素之间的关系称为数据结构。其中：数据元素之间的相互关系称为结构。 根据数据元素间关系的基本特性，有四种基本数据结构 （集合）——数据元素间除“同属于一个集合”外，无其它关系 线性结构——一个对一个，如线性表、栈、队列 树形结构——一个对多个，如树 图状结构——多个对多个，如图

数据的逻辑结构—只抽象反映数据元素的逻辑关系 数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现 存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据 元素间的逻辑关系 数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构

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

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

数据的运算：检索、排序、插入、删除、修改等 数据结构的三个方面： 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队列、串 树形结构 图形结构 逻辑结构 唯一 存储结构 不唯一 运算的实现 依赖于

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

基本概念和术语 例已知数据结构的二元组形式表示分别如下所示，判断各数据结构属于哪一种结构。 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>}。

抽象数据类型(ADT) 作用：抽象数据类型可以使我们更容易描述现实世界。例： 用线性表描述学生成绩表，用树或图描述遗传关系。 定义：一个数学模型以及定义在该模型上的一组操作。 关键：使用它的人可以只关心它的逻辑特征，不需要了解它 的存储方式。定义它的人同样不必要关心它如何存储。 例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。 可以有这样一些操作：插入一个元素、删除一个元素等。

抽象数据类型的表示与实现 一、三元组表示：（D，S，P） 其中D是数据对象，S是D上的关系集，P是对D的基本操作集。 二、书中的定义格式： ADT 抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT 抽象数据类型名

抽象数据类型的表示与实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字 符型等）来表示和实现。 　抽象数据类型的表示与实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字 符型等）来表示和实现。 它有些类似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 例题：P10

作业 1. 简述下列术语：数据、数据元素、 数据对象、数据项、数据结构、逻辑结构、存储结构、抽象数据类型。 2. 简述数据逻辑结构与物理结构之间的关系。