[工学]数据结构 课件 第一章绪论

《[工学]数据结构 课件 第一章绪论》由会员分享，可在线阅读，更多相关《[工学]数据结构 课件 第一章绪论（52页珍藏版）》请在金锄头文库上搜索。

1、数据结构,薛琳,学时数：64 （48+16） 学 分：3.5 教 材：严蔚敏等，数据结构（C语言版），清华大学出版社，1997年4月第1版 （配题集）,1张乃孝，算法与数据结构-C语言描述(第2版) ，高等教育出版社， 2006年1月。 2 李春葆，数据结构习题与解析（第二版），清华大学出版社，2003年12月 3 李春葆，数据结构程序设计题典，清华大学出版社，2002年7月,参考书,4耿国华， 数据结构-C语言描述，高教出版社，2005年7月 5陈慧南，数据结构：C语言描述 ，西安电子科技大学出版社 2003年8月,参考书,教师联系方式： 电话： 15653976369 邮箱： ,联系方式,

2、学习目的,理解数据结构的概念； 掌握设计数据结构与算法的主要原理和方法； 比较不同数据结构的特点。 提高学生使用计算机解决问题的能力。,数据结构的研究对象,我们生活在一个物质的世界，计算机工作者又面对着数字的世界，如果将物质世界中的事与物数字化，那么它们在计算机中的表现均为数据。这些数据来源于现实，表征着具体的意义，而且在计算机中有着统一的表示方法，因而成为被计算机程序处理的符号集合。研究数据在计算机中的表示方法、关联方法、存储方法以及在其上的典型处理方法，就构成了数据结构课程的主要内容。,性质与地位,由于数据是计算机处理的对象，使用计算机的过程就是对数据进行加工处理的过程，因而数据的组织与结

3、构被确立为计算机科学中最为基本内容。 80年代初, 数据结构课程就已成为国内计算机专业教学计划中的核心课程。,性质与地位,数据结构是重要的专业基础课，是计算机科学的核心课程，是计算机理论与技术的重要基石。 该课程具有承上启下的重要作用，既要对前一年学习的软件技术进行总结提高，又要为后续专业课程提供基础。它贯通始终，是计算机科学与技术人才素质培养框架中的中坚课程，对学生的软件开发能力培养有至关重要的作用，将为学生今后的专业生涯打下牢固基础。,性质与地位,数据结构的学习过程，是算法构造性思维方法的训练过程，技能培养的重要程度不亚于知识传授。本门课程教学难点在于让学生理解、习惯算法构造思维方法。培养

4、学生的数据抽象能力，算法设计能力以及创造性思维方法，才能够举一反三、触类旁通，从而达到应用知识解决复杂问题的目的。,课程讲述的主要内容,本课程将分别讲述数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。,内容安排,上课认真听讲；有问题找老师或同学答疑； 仔细阅读教材中的大量例题，从而体会并最终掌握数据结构中的基本概念；学会自己总结各个知识点。 独立完成每个章节后面的练习题。独立及时完成作业；,课程的学习方法,第一章 绪论,学时：3 学时,1、数据结构学科的概念及其所研究的主要内容 2、数据结构中涉及的基本概念和术语 3、本教材使用的描述工具 4、 算法的

5、概念、特点、要求表示以及效率评价方法,本章内容,1、数据结构、数据类型、ADT、算法等重要概念。 2、算法的描述方法以及评价标准与方法,本章重点和难点：,基本概念数据,数据(Data): 是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。,基本概念数据元素,数据元素(Data Element): 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。,基本概念数据对象,数据对象(Data Object)： 是性质相同的数据元素的集合。是数据的一个子集。,基本概念数据结构,

6、数据结构(Data Structure)： 是相互之间存在一种或多种特定关系的数据元素的集合。,基本概念数据结构,（数值或非数值）,Data_Structure=（D, R）,是指同一数据元素类型中各元素之间存在的关系。,元素有限集,关系有限集,相互之间存在一种或多种特定关系的数据元素的集合称为数据结构，可表示为：,基本概念逻辑结构,逻辑结构： 是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。,集合结构： 仅同属一个集合 线性结构: 一对一（1:1) 树 结 构: 一对多（1:n) 图 结 构: 多对多 (m:n),非线性,线 性,逻辑结构可细分为4类

7、：,基本概念逻辑结构,例1 S=(D, R) ， D= a, b, c, d, e, f ， R=(a,b), (b,c), (c,d), (d,e), (e,f),基本概念逻辑结构,d1 d5 d2 d4 d3,该结构是非线性的。,例2 设 S=(D, R) D=di | 1i5， R=(di , dj ), ij,基本概念逻辑结构,物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。,物理结构：,基本概念物理结构,例：复数3.02.3i 的两种存储方式：,法1：地址 内容,法2：地址 内容,2字节,基本概念物理结构,数据结构在计算机中有两种不同的表示方法

8、： 顺序表示和非顺序表示 由此得出两种不同的存储结构：顺序存储结构和链式存储结构,基本概念物理结构,顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。,基本概念物理结构,在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。,运算,运算,最常用的数据运算有 5 种：,插入、删除、修改、查找、排序,运算,数据结构三要素：,逻辑结构: 指数学模型中的基本元素 和元素之间的相互关系。 存储结构: 指数学模型的具体表示方式，包 括结点的表示和关系的表示。 操 作: 指各种行为在

9、存储结构上的具体实现（算法）。,数据类型是性质相同的一组值的集合以及定义在这组值上的操作的总称。,基本概念数据类型,数据类型,例如：整数作为一个数据类型是指在计算机上所能表示的（不是数学意义上任意大小的）所有整数和语言中定义的对于这些整数的全部操作（整数的加、减、乘、除、取余等）。,基本概念数据类型,基本概念抽象数据类型,抽象数据类型（Abstract Data Type 简称为ADT）可以定义作具有一定行为(操作)的抽象（数学）类型。 它不关心类型中值的具体表示方式和数据类型中定义的各种操作的具体实现方法，是所有可能的值的具体表示和各种操作的具体实现的抽象。,意义和作用（1）,抽象数据类型的

10、实质是抽象出了数据类型的使用要求，而把它的具体表示方式和运算的实现细节都隐藏起来。 抽象数据类型仅仅规定了数据类型应该具有的行为（操作）。一旦抽象数据类型被正确实现，就好像程序设计语言中所提供的数据类型那样，可以被自由使用。,意义和作用（2）,抽象数据类型支持数据类型的实现与使用分离的原则，允许独立地考虑数据类型的外部接口和内部的实现。 这使应用程序只要按抽象数据类型的接口统一其使用界面；可以不管其是否已经实现，也不管它是如何实现的。 对于系统的分解、设计、维护和修改均十分有利。,例1抽象数据类型圆,ADT Circle is operations area 计算圆的面积 circumfere

11、nce 计算圆的周长 getRadius 获取圆的半径 setRadius 设置圆的半径 end ADT Circle,例2集合抽象数据类型,ADT Set is Operations isEmpty 判断集合是否是空集合 add 给集合增加一个元素 remove 删除集合中的一个元素 isIn 判断一个元素是否在当前集合中 end ADT Set,抽象数据类型如何定义,抽象数据类型可以用以下的三元组来表示： ADT = （D，R，P）,ADT抽象数据类型名 数据对象： 数据关系： 基本操作 ： ADT抽象数据类型名,ADT常用定义格式,数据对象,D上的关系集,D上的操作集,算法定义： 是对特

12、定问题求解步骤的一种描述 算法是指令的有限序列，其中每一条指令表示一个或多个操作。,基本概念算法,算法五个特性： （1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 （2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。,算法特征,（3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 （4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 （5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。,算法特征,算法设计的要求 评价一个好的算法有以下

13、几个标准: (1) 正确性(Correctness ) 算法应满足具体问题的需求。 (2)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解。,算法设计的要求,(3)健状性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 (4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。,算法设计的要求,算法描述工具,类C语言描述,算法性能评价,算法评价指标：,正确性、可读性、健壮性、效率与低存储量需求,常用时间复杂度来衡量,常用空间复杂度来衡

14、量,3n+2=O(n) 因为 3n+24n for n2 6*2n+n2=O(2n) 因为6*2n+n2 7*2n for n4,例：,渐进符号（O）的定义：当且仅当存在一个正的常数 C，使得对所有的 n n0 ，有 f(n) Cg(n)，则： f(n) = O(g(n),算法的时间复杂度,该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。,解,分析：显然，语句的频度是1。设语句2的频度是f(n)，则有：,算法的时间复杂度由嵌套最深层语句的频度决定,即f(n)log2n，取最大值f(n)=log2n,所以该程序段的时间复杂度T(n)=1+f(n)=1+ log2n= O( log2n),算法的时间复杂度,算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作 T(n)=O(f(n) 表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。,注： 1） O（）为渐近符号。 2） 空间复杂度S(n)按数量级递增顺序也与上表类似。,复杂度高,复杂度低,时间复杂度T(n)按数量级递增顺序为：,多项式阶,算法的时间复杂度,空间复杂度: 算法所需存储空间的度量，记作: S(n)=O(f(n) 其中n为问题的规模(或大小),算法的空间复杂度,