数据结构第1章概论.ppt

《数据结构第1章概论.ppt》由会员分享，可在线阅读，更多相关《数据结构第1章概论.ppt（50页珍藏版）》请在三一办公上搜索。

1、数据结构Data Structure,计算机科学与技术系主讲教师：路游,2,学时数：64（44讲课+20上机）学分：4教材：数据结构（C语言版）严蔚敏 吴伟民 编著 清华大学出版社参考书：数据结构题集(C语言版)严蔚敏、吴伟民著 数据结构课程设计苏仕华等编著 机械工业出版社 数据结构题集(C语言篇)习题与解析（修订版）李春葆编著 清华大学出版社上机：第5-14周，星期一，1-2节，3教-404,内容安排,4,第1章 序 论,1.1 计算机基本概念（复习）1.2 数据结构基本概念1.3 抽象数据类型概念1.4 算法效率的度量,作业,5,1.1 计算机基本概念(复习）,计算机系统,硬件系统软件系统

2、,Q1 硬件系统由哪几部分组成？Q2 微型计算机与其他计算机的区别？Q3 内存与外存的不同之处是？Q4 计算机内常用到哪些数制？Q5 计算机主要技术指标有哪些?,硬件概念复习,软件概念复习,Q1 软件系统包含哪些软件？Q2 什么是系统软件和应用软件？Q3 机器语言、汇编语言、高级语言的区别？,6,Q1：计算机硬件系统由哪几部分组成？,答：计算机硬件系统由 部分组成：,也可浓缩为3部分：,人脑：感受 判断 计算 记忆 反应,电脑：输入 控制 运算 存储 输出,主 机,5,7,Q2：微型计算机与一般意义上的计算机有什么区别？,其本质特征是,答：,运算器和控制器集成在一块IC芯片上,这种CPU简称M

3、PU,8,Q3：内存与外存是一回事吗？,能被CPU直接控制（BUS直连）的存储器称为内存通过I/O接口才能被CPU控制的存储器称为外存,答：不是一回事。它们的区别是：,9,Q4：计算机内常用到哪些数制？,A.（11011001）BB.（75）DC.（37）OD.（2A）H,答案：,C,2进制(B)8进制(O)10进制(D)16进制(H),例3：下列四种不同进制的无符号数中，最小的数是,例2：下列数据中，有可能是八进制数的是 A.238 B.764 C.396 D.789,例1：10(B)D 10(O)D 10(H)D,2 8 16,10,Q5：计算机主要技术指标有哪些？,CPU一次能处理的二进

4、制位数，它与数据总线的根数有关，如8位机，16位机、32位机等等运算器做一次“加”动作的最小可靠时间，如奔4 机器主频2.8G（Hz）CPU每秒能执行加法指令的次数（MIPS）bit，Byte，KB，MB，GB，TB,练：微机中1K字节表示的二进制位数是：,1B=8bit 1KB=210B 1MB=210KB 1GB=210MB,A.1000 B.81000 C.1024 D.81024,答案：,D,字 长主 频运算速度主存容量,11,Q1：软件系统包含哪些软件？,裸机,系统软件,操作系统,支援软件,应用软件,答：包含系统软件和应用软件两大类,12,Q2：什么是系统软件？什么是应用软件？,答：

5、,系统软件管理计算机系统各部分，使之高效工作，同时为上层提供服务。,应用软件处于系统软件的上层，帮助计算机用户完成特定领域的工作。,系统软件中最重要的是操作系统（Operating System），它是一个大型的、优秀的程序，管理着计算机的全部软、硬件资源，并提供人机交互的界面。,13,Q3：机器语言、汇编语言、高级语言的区别？,用二进制代码直接表示的语言，是计算机唯一能识别、执行的语言 符号化了的机器语言（即用助记符来写程序，靠汇编程序翻译成机器码才能执行）接近自然英语和数学公式的语言（要通过编译或解释程序翻译成机器码）,答：,低级语言 面向机器，执行速度快，效率高；高级语言 面向问题，易理

6、解，易移植。,机器语言汇编语言高级语言,14,1.2 数据结构基本概念,Q1 什么是数据结构？Q2 学习数据结构有什么用？Q3 数据结构涵盖的主要内容？,讨论：,15,Q1：什么是数据结构？,16,“学生”表格,17,“课程”表格,18,选课单包含如下信息 学号 课程编号 成绩 时间 学生选课系统中实体构成的网状关系,学生(学号,姓名,性别,籍贯),课程(课程号,课程名,性别,籍贯),选课(学号,课程号,成绩),19,UNIX文件系统的系统结构图,/(root),bin,lib,user,etc,math,ds,sw,yin,tao,xie,Stack.cpp,Queue.cpp,Tree.c

7、pp,20,术语：数据、数据元素和数据项,（见教材P4定义）：数据(data)所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(data element)是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Data item)构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。,三者之间的关系：数据 数据元素 数据项,例：班级通讯录 个人记录 姓名、年龄,21,Q1：什么是数据结构？,答:(见教材P5)是相互之间存在一种或多种特定关系的数据元素的集合，表示为：,（数值或非数值）,Data_Struct

8、ure=（D,S）,或：是指同一数据元素类中各元素之间存在的关系。,亦可表示为：S（D,R）或 B=（K,R）,元素有限集,关系有限集,22,数据：数据是信息的载体，是描述客观事物的数字、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据非数值性数据数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象 N=0,1,2,学生数据对象,23,Q2：学习数据结构有什么用？,答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。,程序

9、设计实质好算法好结构,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,24,逻辑结构数据结构 物理（存储）结构 数据运算,Q3：数据结构涵盖的内容？,25,解释1：什么叫数据的逻辑结构？,答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类：,集合结构：仅同属一个集合线性结构:一对一（1:1)树 结 构:一对多（1:n)图 结 构:多对多(m:n),非线性,线 性,26,例：用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。,（1）S=(D,R)D=a,b,c,d,e,f R=(a,e),(b,c)

10、,(c,a),(e,f),(f,d),解：上述表达式可用图形表示为：,b c a e f d,此结构为线性的。,27,（2）S=(D,R)D=di|1i5 R=(di,dj),ij,d1 d5 d2 d4 d3,该结构是非线性的。,解：上述表达式可用图形表示为：,28,解释2：什么叫数据的物理结构？,答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。包括数据元素的表示和关系的表示。,存储结构可分为4大类：,例：（见教材P6）复数3.02.3i 的两种存储方式：,顺序、链式、索引、散列,法1：地址 内容,法2：地址 内容,2字节,借助元素在存储器中的相对

11、位置来表示元素之间的逻辑关系,借助指针来表示元素之间的逻辑关系,29,如何描述存储结构？,用高级语言提供的数据类型来描述如：用一维数组来描述顺序存储结构 用指针来描述链式存储结构数据类型明显或隐含地规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许进行的操作。,30,解释3：什么是数据的运算？,答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。,最常用的数据运算有5种：,插入、删除、修改、查找、排序,31,1.3 抽象数据类型概念,Q1 数据类型与抽象数据类型的区别？Q2 抽象数据类型如何定义？Q3 抽象数据类型如何表示和实现？,讨论：,提示：教材中例1-6和

12、例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请试阅读。,32,Q1 数据类型与抽象数据类型的区别？,数据类型：是一个值的集合和定义在该值上 的一组操作的总称。,抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）,它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。,33,数据类型 定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称.C语言中的数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值,34,Q2 抽象数据

13、类型如何定义？,抽象数据类型可以用以下的三元组来表示：ADT=（D，S，P）数据对象 D上的关系集 D上的操作集,ADT抽象数据类型名 数据对象：数据关系：基本操作：ADT抽象数据类型名,ADT常用定义格式,35,例：给出自然数(Natural Number)的抽象数据类型定义。,ADT Natural_Number isobjects:一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数(MAX INT)functions:对于所有的 x,y Natural_Number；TRUE,FALSE Boolean；+,-,=,=等都是可用的服务。Zero()：Natural Number

14、 返回 0IsZero(x)：Boolean if(x=0)返回TRUE else 返回 FALSEAdd(x,y)：Natural Number if(x+y=MAX INT)返回 x+y else 返回MAX INTSubtract(x,y):Natural Number if(xy)返回0 else 返回x-yEqual(x,y):Boolean if(x=y)返回TRUE else 返回FALSESuccessor(x):Natural Number if(x=MAX INT)返回x else 返回x+1end Natural_Number,36,Q3 抽象数据类型如何表示和实现？,抽

15、象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。,注1：它有些类似C语言中的结构（struct)类型，但增加了相关的服务。注2：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。其描述语法见P10-11。,但上机时要用具体语言实现，如C或C+等,37,1.4 算法效率的度量,Q1.什么是算法？Q2.如何评判一个算法的好坏？Q3.算法的效率如何度量？Q4.算法的存储空间需求,讨论：,38,Q1.什么是算法？,答：算法是解决某一特定类型问题的有限运算序列。是一系列输入转换为输出的计算步骤。,算法有5个基本特性：,有穷性,确定性,可行性,输入,输出,对于任意一组合法输

16、入值，在执行有穷步骤之后一定能结束，而且每一步都能在有限时间内完成。,算法中每一条指令必须有确切的含义，不应该具有二义性。并且在任何条件下，算法都只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。,算法中描述的操作都可以通过已经实现的基本操作执行有限次来实现,一个算法有0个或多个输入，这些输入都是来自某个特定的对象的集合。,一个算法有1个或多个输出，这些输出都是与输入有着某些特定关系的值。,39,Q2.如何评判一个算法的好坏？,正确性：算法应满足求解具体问题的需求。对正确性的理解，有如下4种不同的程度：1.不含语法错误；2.对几组输入数据能够得到满足规格需求的解；3.对精心选择的典型

17、数据能够得到满足规格需求的解；4.对一切合法的输入数据都能得到满足规格需求的解。,可读性：算法要便于交流，要有助于别人对算法的理解。晦涩 难读的程序往往隐藏了很多的错误。,健壮性：对于非法的输入，算法要能给出适当的反映，而不会出 现莫名其妙的错误。处理出错的方法不应是中断程序的 执行，而应是返回一个表示错误或错误性质的值。,好的时空性：算法的效率要高，同时所占的存储量要低。,通常以第3层意义的正确性作为衡量一个程序是否合格的标准。,常用时间复杂度来衡量,常用空间复杂度来衡量,40,Q3.算法的效率如何度量？,通常有两种衡量算法效率的方法:,事后统计法,事前分析估算法,缺点：1必须执行程序 2其

18、它因素可能会掩盖算法本质,效率指的是运行时间，与算法执行时间相关的因素如下：1算法选用的策略 2问题的规模 3编写程序的语言 4编译程序产生的机器代码的质量 5计算机执行指令的速度,衡量算法的效率通常采用的方法，为此，需要引进一个时间复杂度的概念。,41,如何估算一个算法的时间复杂度？,一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数 n 表示），或者说，它是问题规模的函数。一个算法的组成通常由控制结构（顺序、分支、循环）与原操作（固有数据类型的操作）两部分组成，所以算法的运行工作量也就取决于这两者的综合效果,事前分析估算方法的基本思路是：从算法中选取一种对于所研究的问题来说

19、是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。,由于基本操作的执行时间通常囿界于一个常数，所以算法的执行时间 与 基本操作执行次数之和 成正比。,42,算法的时间的渐近表示,假设某算法的执行时间是T(n)，其中变量 n 可以是输入或输出量，也可以是两者之和，还可以是它们之一的某种测度(例如，数组的维数，图的边数等)。f(n)是在事前分析中确定的某个形式很简单的函数，例如，nm，log2n，2n，n!等。它是独立于机器和语言的函数，而T(n)则与机器和语言有关。假如随着问题规模n的增长，算法执行时间T(n)的增长率和f(n)的增长率相同，则可记作：T(n)=O

20、(f(n)称f(n)为算法的渐近时间复杂度，简称时间复杂度。,大写符号给出了函数T的一个上限。大写符号的定义如下：T(n)(f(n)，当且仅当存在正的常数c和n0，使得对于所有的nn0，有 T(n)c*f(n),43,3n+2=O(n)/*3n+24n for n2*/3n+3=O(n)/*3n+34n for n3*/100n+6=O(n)/*100n+6101n for n10*/10n2+4n+2=O(n2)/*10n2+4n+211n2 for n5*/6*2n+n2=O(2n)/*6*2n+n2 7*2n for n4*/,例：,算法的时间的渐近表示（续）,44,多项式关系：(1)(

21、log2n)(n)(nlog2n)(n2)(nn),指数关系：(2n)(n!)(nn)，且对于任意的m0，有2nnm,45,估算一个算法的时间复杂度（示例）,例1：两个矩阵相乘的算法void mult(int a,int b,int/for/mult,基本操作:乘法操作ai,k*bk,j算法执行次数：是最高幂次为3的多项式时间复杂度:O(n3),46,估算一个算法的时间复杂度（示例）,例2：选择排序void select_sort(int if(j!=i)aj ai,基本操作:比较(数据元素)操作ak aj 算法执行次数：是最高幂次为2的多项式时间复杂度:O(n2),47,例3：分析以下程序段

22、的时间复杂度。i=1;while(i=n)i=i*2;,解：,分析：显然，语句的频度是1。设语句2的频度是f(n)，则有：,即f(n)log2n，取最大值f(n)=log2n,所以该程序段的时间复杂度T(n)=1+f(n)=1+log2n=O(log2n),总结：算法的时间复杂度是由嵌套最深层语句的频度决定的。,估算一个算法的时间复杂度（示例）,48,算法的存储空间需求,算法的空间复杂度作为算法所需存储空间的一种度量，记作,它表示随着问题规模 n 的增大，算法运行所需存储量的增长率与g(n)的增长率相同。,S(n)=O(g(n),算法的存储量包括:,1输入数据所占空间,2程序本身所占空间,3辅

23、助变量所占空间,若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。,49,本章学习要点,1.熟悉各名词、术语的 含义，掌握基本概念。,2.理解算法五个要素的 确切含义。掌握算法 设计的几个基本原则。,3.掌握计算语句频度和 估算算法时间复杂度 的方法。,50,作业：,请在下次课前完成第1章自测卷全部内容；复习C语言，重点是结构类型和递归概念请试做配套习题集的1.8题和1.12题，另外，在看懂教材例1-6和例1-7的基础上，可试做1.4题。,