数据结构第一章绪论课件

1、数 据 结 构主讲教师陈明 教材 数据结构教程 李春葆等 清华大学出版社 参考教材数据结构 （ C+语言版） 刘清 王琼 电子工业出版社数据结构 （ C语言版） 严蔚敏 吴伟民 清华大学出版社数据结构与程序设计C+语言描述（影印版）Robert L.Kruse，Alexander J.Ryba 高等教育出版社 教学内容 第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串（最后选讲） 第五章 数组和广义表（简 单介绍） 第六章 树 第七章 图 第八章 查找 第九章 排序课程特点及教学方法难度大 综合性强 必须下苦功学习关于教学的几个新观念教学过程以学生为主体, 教师为主导 学生由知识技能

2、的被动接受者向知识技能的主动探求者转变, 教师由传授者向教学活动的设计者、组织者、指导者转变教学目标为使学生在知识、能力、素质方面协调发展能力包括自学能力、知识运用能力、动手能力、创新能力、发现问题能力、分析问题和解决问题能力以及可持续发展能力第一章 绪论1.1 本课程研究的问题计算机的发展 软件 硬件 应用领域数据处理的种类和能力 数据数值数据非数值数据数 (整数,实数) 字符 字符串 文字 图形 图象 声音数据：客观对象的符号表示数学中的整数、实数，课程名，地名、书名程序原始数据结果数据 数值问题与非数值问题1）数值问题例1 已知：游泳池的长len和宽wide，求面积area设计 求解问题

3、的方法 编程1.1 本课程研究的问题 建模型：问题涉及的对象：游泳池的长len 宽wide，面积area；对象之间的关系：area=lenwide1.1 本课程研究的问题例 3 迷宫问题。在迷宫中，每走到一处，接下来可走的通路有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可得一棵“树” 入口 出口城市间交通网问题1.1 本课程研究的问题数据结构的研究问题： 非数值数据之间的结构关系，及如何表示，如何存储，如何处理。本课程讨论的问题： 应用中常用的几种数据间的结构关系，及如何表示,如何存储，如何处理。 例如对C 源程序，数据概念不仅是源

4、程序所处理的数据，相对于编译程序来说，C编译程序相对于源程序是一个处理程序， 它加工的数据是字符流的源程序（.c）， 输出的结果是目标程序(.obj)； 对于链接程序来说，它加工的数据是目标程序(.obj)， 输出的结果是可执行程序(.exe)，如图 1.1 所示。 图1.1 编译程序示意图 源程序目标程度可执行程序C编译程序C链接程序 2. 数据元素（Data Element） 数据元素是组成数据的基本单位, 是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。 表1-1 学 籍 表 学号姓名性别籍贯出生年月住址101赵红玲女河北1983.11北京 数据项记录综上13所述，再分析数据

5、概念： 4. 数据结构（Data Structure） 数据结构是指相互之间存在一种或多种特定关系的数据元素集合， 图1.2 学校组织层次结构图 图1.3 交通流量图 5. 数据类型(Data Type) 数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围，以及该类型中可允许使用的一组运算。例如高级语言中的数据类型就是已经实现的数据结构的实例。 从这个意义上讲，数据类型是高级语言中允许的变量种类， 是程序语言中已经实现的数据结构（即程序中允许出现的数据形式）。在高级语言中，整型类型可能的取值范围是-32 768+32 767， 可

6、用的运算符集合为加、 减、 乘、 除、 乘方、 取模（如C语言中+， -， *， /， %）。 6. 数据抽象与抽象数据类型 ） 数据的抽象 计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如98.65、 9.6E3等, 它们是二进制数据的抽象; 使用者在编程时可以直接使用, 不必考虑实现细节。在高级语言中，则给出更高一级的数据抽象，出现了数据类型， 如整型、 实型、字符型等。到抽象数据类型出现，可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等，这种数据抽象的层次为设计者提供了更有利的手段，使得设计者可以从抽象的概念出发，从整体考虑，然后自顶向下、逐步

7、展开，最后得到所需结果。可以这样看，高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出像栈、队列、树、图等复杂的抽象数据类型。 ） 抽象数据类型 (Abstract Data Type) 抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。从某种意义上讲，抽象数据类型和数据类型实质上是一个概念。整数类型就是一个简单的抽象数据类型实例。“抽象”的意义在于教学特性的抽象。一个

8、ADT定义了一个数据对象，数据对象中各元素间的结构关系，以及一组处理数据的操作。ADT 通常是指由用户定义且用以表示应用问题的数据模型，通常由基本的数据类型组成，并包括一组相关服务操作。 数学模型抽象数据类型数据结构，恰好反应了信息结构转换的三个重要阶段，而在这个转换过程中，数据结构是基础，抽象数据类型是中枢。 一个线性表的抽象数据类型的描述如下： ADT Linear-list 数据元素 所有ai属于同一数据对象，i=1，2，n, n0； 逻辑结构 所有数据元素ai（i=1，2，n-1）存在次序关系，ai无前趋，an无后继； 操作设L为Linear-list: Initial(L): 初始化

9、空线性表; Length(L): 求线性表的表长; Get(L, i): 取线性表的第i个元素； Insert(L, i, b): 在线性表的第i个位置插入元素b； Delete(L, i): 删除线性表的第i个元素。 ） ADT的表示与实现 ADT的定义 ADT的定义格式不唯一, 我们采用下述格式定义一个ADT: ADT 数据对象: 结构关系: 基本操作: ADT 其中数据对象和结构关系的定义采用数学符号和自然语言描述, 而基本操作的定义格式为: (参数表) 操作前提: 操作结果: 关于参数传递 参数表中的参数有两种：第一种参数只为操作提供待处理数据, 又称值参；第二种参数既能为操作提供待处

10、理数据, 又能返回操作结果，也称变量参数。操作前提描述了操作执行之前数据结构和参数应满足的条件, 操作结果描述操作执行之后, 数据结构的变化状况和应返回结果。ADT可用现有计算机语言中已有的数据类型, 即固有数据类型来表示和实现。不同语言的表示和实现方法不尽相同，如ADT中“返回结果的参数”， PASCAL语言用“变参” 实现, C+语言通过“引用型参数”实现, 而C语言用“指针参数”实现。 用标准C+语言表示和实现ADT描述时，主要包括以下两个方面: (1) 通过结构体将int、 float等固有类型组合到一起, 构成一个结构类型, 再用typedef为该类型或该类型指针重新起一个名字。 (

11、2) 用C+语言函数实现各操作。 基本操作主要有以下几种： (1) 插入： 在数据结构中的指定位置上增添新的数据元素； (2) 删除： 删去数据结构中某个指定数据元素； (3) 更新：改变数据结构中某个元素的值， 在概念上等价于删除和插入操作的组合； (4) 查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值)； (5) 排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。 对每种数据结构，主要讨论如下两方面的问题： 1） 数据的逻辑结构，数据结构的基本操作； 2） 数据的存储结构，数据结构基本操作的实现；数据的逻辑结构： 数据之间的

12、结构关系，是具体关系的抽象。数据结构的基本操作： 指对数据结构的加工处理数据的存储结构 (物理结构)： 数据结构在计算机内存中的表示数据结构基本操作的实现： 基本操作在计算机上的实现（方法) 1.3 数据结构的分类及表示 某班学生基本情况登记表，记录了每个学生的学号 姓名 专业 政治 面貌 ，表中的记录是按学生的学号顺序排列的。 学号 姓名 专业 政治面藐 001 王洪 计算机 党员 002 孙文 计算机 团员 003 谢军 计算机 团员 004 李辉 计算机 团员 005 沈祥福 计算机 党员 006 余斌 计算机 团员 007 巩力 计算机 团员 008 孔令辉 计算机 团员学生基本情况登

13、记表的图示 001003002004006005008007学生间学号顺序关系是一种线性结构关系例一 常用的数据结构 1） 集合 2） 线性结构 3） 树结构 4） 图结构 5）其它复杂结构 家族的族谱 假设某家族有10个成员A， B， C， D， E， F， G， H，I， J，他们之间的血缘关系可以用如下图表示。JIACBDHGFE13 数据结构的分类及表示例1. 逻辑结构 图1.5 四类基本数据结构示意 (1) 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。 (2) 线性结构：结构中的数据元素之间存在着一对一的线性关系。 (3) 树形结构：结构中的数据元素之间

14、存在着一对多的层次关系。 (4) 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。 逻辑结构 线性结构线性表、栈、队、字符串、数组、广义表非线性结构树、 图 2. 存储结构 存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。 形式化描述：D要存入机器中，建立一从D的数据元素到存储空间M单元的映象S，DM， 即对于每一个d，dD, 都有唯一的zM，使S（D）=Z, 同时这个映象必须明显或隐含地体现关系R。 逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽象，存储结构是数

15、据结构的实现，两者综合起来建立了数据元素之间的结构关系。 顺序映象 （顺序存储结构） 非顺序映象（非顺序存储结构） 数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合， 就叫做数据结构。 数据结构的表示 图示表示 图示表示是由顶点和边构成的图，其中顶点表示数据 ，边表示数据之间的结构关系； 001003002004006005008007学生基本情况表的图示表示JIACBDHGFE家族树的图示表示13 数据结构的分类及表示学生基本情况表的二元组表示（D，S） 二元组表示

16、二元组表示是用一个二元组（D，S）表示数据结构， 其中 D 是数据元素集合，S 是 D 上关系的集合。D = 001，002，003，004，005，006，007，008S = R R= , , 家族树的二元组表示（D，S） D = A，B，C，D，E，F，G，H，I，J S = R R = A,B, 13 数据结构的分类及表示JIACBDHGFE 00100300200400600500800714 算法与算法分析 1.4 算法与算法分析一 算法的概念 算法是求解问题的操作序列 算法的基本特征：1）输入：0个或多个输入；2）输出：1个或多个输出；3）有穷性：算法必须在有限步内结束；4）确定

17、性：组成算法的操作必须清晰无二义性。5）可行性：组成算法的操作必须能够在计算机上实现。 求两个正整数 m，n 中的最大数MAX的算法 （1）若 m n 则 max=m （2）若 m = n 则 max=n 例描述算法的书写规则所有算法均以函数形式给出, 算法的输入数据来自参数表参数表的参数在算法之前均进行类型说明有关结点结构的类型定义,以及全局变量的说明等均在算法之前进行说明评价算法标准 算法的正确性，可读性，可维护性，健壮性等，1 算法时间复杂度T（n） 本课程采用以求解问题的基本操作（原操作）的执行次数作为算法时间的度量。 14 算法与算法分析O（n3） 称为矩阵相乘算法时间复杂度；O（n

18、3）表示矩阵相乘算法执行时间与n3成正比, 即O（n3）与n3 同一数量级； n 阶矩 阵相乘的算法For ( i = 1; i=n; i+ ) For (j = 1; j=n; j+ ) c i j = 0 ; For (k = 1; k= n; k+ ) c i j += a i k * b k j 乘法 加法执行次数均为 n3 例 矩阵相乘的基本运算：乘法 加法； 有些算法，基本操作执行次数与问题的输入数据有关，这时可考虑 （1） 算法平均时间复杂度 （2） 算法在最坏情况下的时间复杂度算法的时间复杂度 一般来说，设算法中基本操作的执行次数是问题规模n的某个函数f(n)，算法的时间复杂度记作： T(n) = O(f(n) 它表示随问题规模n的增大，算法执行时间的增长率与f(n) 的增长率相同。 14 算法与算法分析算法的时间复杂度为O (N3) 14 算法与算法分析 100元买100支笔, 其中钢笔 3元/支, 圆珠笔 2元/支, 铅笔 0.5元/支. 写算法输出各种组合方案解法1 #define N 100void scheme() int i, j, k, count, money; for (i = 0; i=N; i+ ) for (j = 0; j=N; j+ ) for (k=0; k=N; k+) count=i+j+k;