数据结构与软件工程ppt课件

.,1,数据结构与软件工程,信息科学与技术学院郝矿荣E-mail:krhao,2,数据结构与软件工程,教材及参考书目：数据结构（C语言版）严蔚敏等编清华大学出版社数据结构习题集（C语言版）严蔚敏等编清华大学出版社数据结构C+语言描述刘卫东等译清华大学出版社,3,数据结构与软件工程,预备知识：C语言程序设计的基本技术离散数学概率论,4,数据结构与软件工程,计算机三级偏硬：计算机原理60%数据结构30%Internet等10%研究生入学考试的核心课程,5,数据结构与软件工程,“数据结构”所处的地位,6,数据结构与软件工程,要求：上课认真听课作业按时完成上机实习认真，按质按量完成,7,数据结构与软件工程,第一章绪论第六章树与二叉树第二章线性表第七章图第三章栈和队列第八章动态存储管理第四章串第九章查找第五章数组与广义表第十章内部排序,8,第一章绪论,目的：了解数据结构的背景掌握一些基本概念和术语掌握抽象数据类型的定义、表示与实现描述算法的类C语言掌握算法分析的一些基本方法,9,第一章绪论,重点：有关数据结构的基本概念和术语掌握抽象数据类型ADT的定义、表示与实现熟悉类C语言的书写规范理解算法五个要素的确切含义掌握估算时间复杂度的方法，了解空间复杂度的度量方法,10,第一章绪论,难点：抽象数据类型ADT的表示与实现算法复杂度的分析方法,11,第一章绪论,1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求,12,一、数据结构形成和发展背景计算机是一门研究用计算机进行信息表示和处理的科学两个问题：1）信息的表示和组织：直接关系到处理信息的程序的效率；2）信息的处理：面向系统程序和应用程序的大规模和复杂结构,1.1什么是数据结构,13,一、数据结构形成和发展背景计算机的飞速发展及其应用范围的迅速扩展计算机处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据编制“好”的程序要求分析待处理的对象以及各处理对象之间存在的关系,1.1什么是数据结构,14,二、数据结构1、用计算机解决问题的步骤：具体问题建立数学模型设计算法编制程序测试和调整最终答案建立数学模型（关键）：分析问题、提取操作对象、找出对象间关系，对此用数学语言加以描述算法设计：利用建立的数学模型，根据具体问题，设计出解决问题的方法,1.1什么是数据结构,15,二、数据结构NiklausWirth：Algorithms+DataStructures=Programs程序设计:为计算机处理问题编制一组指令集算法：处理问题的策略数据结构：问题的数学模型,1.1什么是数据结构,16,二、数据结构从数学模型上分：数值问题（数学方程），如：桥梁结构的应力分析模型线性方程组人口增长模型微分方程全球天气预报环流模式方程非数值问题（集合、线性表、树、图等）无法用数学方程加以描述,1.1什么是数据结构,17,二、数据结构非数值计算的程序设计问题例1:求一组(n个)整数中的最大值算法:基本操作是“比较两个数的大小”例2：计算机对弈算法：对弈的规则和策略例3：协会会员注册系统算法：需要管理的项目？如何管理？用户界面？模型：？,1.1什么是数据结构,18,二、数据结构2、数据结构主要关心的：结构中各元素之间逻辑关系（数学模型）线性结构：如图书馆的书目索引树形结构：见后面例子图形结构：见后面例子结构中各元素的存储方式结构具有的行为特征（其上的操作）在计算机中的表示和实现,1.1什么是数据结构,19,例1.电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1,b1)(a2,b2)(an,bn)其中，ai,bi(i=1,2,n)分别表示某人的名字和对应的电话号码要求：设计算法，给定某人的名字，打印出此人的电话号码；如果无此人，则报告无此人的标志,1.1什么是数据结构,20,算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构数据的结构，直接影响算法的选择和效率上述问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量1)假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai,bi)，1in2)数据结构还要提供每种结构类型所定义的各种运算的算法,1.1什么是数据结构,21,例2.图书馆的书目检索系统自动化问题（线性结构）图书馆的一本图书由书名、作者、出版社等数据来描述，根据需要我们选择其中的若干项组成一个数据元素来对应一本书图书馆的编目表反映了书与书之间的关系，是数据元素之间的结构。当然我们还应注意到书是具体地放在某个书架上的，它是编目表的物理实现图书馆从两方面管理图书：物理的藏书和逻辑的编目表。这就是图书馆的结构。和图书馆一样计算机管理数据，也有两个方面：即物理的存储和逻辑的关系,1.1什么是数据结构,22,1.1什么是数据结构,23,例3：学生选课系统模型（图结构）,1.1什么是数据结构,24,例3：学生选课系统模型（图结构）,1.1什么是数据结构,25,例3：学生选课系统模型（图结构）,选课单包含如下信息学号课程编号成绩时间学生选课系统中实体构成的网状关系,1.1什么是数据结构,26,例4：下棋问题,1.1什么是数据结构,27,例5.多叉路口交通灯的管理（图结构）,1,1,1,1,2,2,2,3,3,4,4,1,1,1.1什么是数据结构,28,问题模型结构分析线性方程组人口预报微分方程优化问题线性规划、非线性规划震动问题矩阵分析；特征值、特征向量信息管理二维数据表下棋树型结构城市路径图型结构DOS目录树型结构家谱树型结构排队队列（线性）,1.1什么是数据结构,29,数据的逻辑结构按关系分为线性结构（关系是线性的）和非线性结构（关系是非线性的）,1.1什么是数据结构,30,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间相互关系和操作等的学科对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型,1.1什么是数据结构,31,1.2基本概念和术语,数据：数据是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合数值性数据/非数值性数据数据元素：数据基本单位，通常作为一个整体来考虑，如：“树”中的一个棋盘格局；学生信息表，一个数据元素（记录）含若干个数据项等数据项是数据的不可分割的最小单位,32,1.2基本概念和术语,数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。数据对象可以是有限的，也可以是无限的整数数据对象:N=0,1,2,英文字符类型的数据对象:A，B，C，D，E，F，学生数据对象：数据表数据、数据元素和数据对象之间的关系：数据数据元素数据项,33,1.2基本概念和术语,34,1.2基本概念和术语,数据结构与数据对象之间的区别和联系？数据对象仅仅是数据元素的集合，不涉及这些元素之间的关系描述数据结构不仅要描述数据对象，而且要描述元素彼此之间的关系,35,1.2基本概念和术语,数据结构描述Data-Structure=(D,S)D数据集；S关系集例：学科研究课题小组Group=(P,R)其中：P=T,G1,G2,Gn,S11,S12,SnmR=R1,R2R1=|i=1,2,3R2=|i=1,2,3,j=1,2,36,1.2基本概念和术语,数据结构描述例：复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关系C1，C2,37,1.2基本概念和术语,数据的逻辑结构逻辑结构：数据结构描述的元素间的逻辑“关系”，独立于计算机按集合的观点，数据的逻辑结构有两个要素：一是数据元素，二是关系数据元素间的关系表示1）顺序映象：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系2）非顺序映象：借助指示元素存储地址的指针表示数据元素之间的逻辑关系,38,1.2基本概念和术语,数据的逻辑结构顺序映象：x和y存储位置的相对关系表示有序对最简单的方法就是使y和x的存储位置之间差一个常量C,例如：(a1,a2,a3),39,1.2基本概念和术语,数据的逻辑结构链式映象：x和y的存储位置随意，则需要用一个和x在一起的附加信息指示y的存储位置，这个附加信息和x绑定在一起，此时，两者合在一起作为x的存储映象,40,1.2基本概念和术语,数据的物理（存储）结构物理结构：数据结构中数据元素间的关系在存储器中的存储方法（表现和实现）物理结构中的基本定义：1）位：二进制中的一位；信息表示的最小单位2）元素（结点）：由若干位组合起来形成的一个位串，可看成是数据元素在计算机中的映象3）数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串,41,1.2基本概念和术语,按照物理结构的不同分为：1）顺序存储结构：利用在存储器中的物理关系来表示逻辑关系。逻辑上相邻的数据元素存储在物理位置上相毗邻的存储单元里，元素的关系由存储单元的邻接关系来体现2）链式存储结构：数据元素可以在计算机内任意位置上存放（它不要求逻辑上相邻的元素在物理位置上也相邻)，用在存储器中附加指针的方式来表示逻辑关系。将数据元素存放的存储单元分为两个部分，分别存放数据和指针，称为数据域和指针域,42,1.2基本概念和术语,数据的逻辑结构和物理结构的关系：逻辑结构只抽象地描述数据元素逻辑关系（简称数据结构）物理结构是一个逻辑结构映像到计算机中所得到的存储表示算法的设计：取决于选定的数据逻辑结构算法的实现：依赖于采用的存储结构,43,1.2基本概念和术语,数据类型用以刻画（程序）操作对象的特性。一个值的集合（整型变量）+该集合上定义的一组操作(不体现值间关系)（加、减等操作）类型明显或隐含地规定了：在程序执行期间变量或表达式所有可能的取值范围以及在这些值上允许进行的操作,44,1.2基本概念和术语,数据类型例1.在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义例2.在FORTRAN语言中变量的数据类型有整型、实型、和复数型,45,1.2基本概念和术语,数据类型按“值”的不同特性可分为：1）非结构的原子类型：其值是不可分解的；2）结构类型：其值是由若干成分按某种结构组成的，是可分解的；且它的成分可以是非结构的，也可以是结构的。,46,1.2基本概念和术语,抽象数据类型：数据结构+定义在此结构上的一组操作（和其在计算机上的表示和实现无关）。不再局限于前述各处理器中已定义并实现的数据类型，还包括用户自定义的数据类型按“值”的不同特性可分为：1）原子类型：其值是不可分解的；2）固定聚合类型：其值由给定数目的成分按某种结构组成；3）可变聚合类型：其值的成分的数目不确定。,47,1.2基本概念和术语,抽象数据类型1）一个含抽象数据类型的软件模块包含：定义、表示和实现2）三元组表示（D,S,P）D：数据对象，S：D上的关系集，P：D上的基本操作集,48,1.2基本概念和术语,抽象数据类型定义：ADT抽象数据类型名数据对象：数据关系：基本操作：ADT抽象数据类型名其中：1）数据对象和数据关系的定义用伪码表示；,49,1.2基本概念和术语,抽象数据类型定义：2）基本操作的定义：基本操作名（参数表）初始条件：（初始条件描述）操作结果：（操作结果描述）基本操作有两种参数：赋值参数：为操作提供输入值引用参数：以s=0;将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶例2.for(i=1;i=n;+i)+x;s+=x;语句频度为：2n其时间复杂度为：O(n)即时间复杂度为线性阶,69,1.4算法和算法分析,算法的时间度量计算累加和程序程序步数计算工作表格,70,1.4算法和算法分析,算法的时间度量例3.for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;语句频度为：2n2其时间复杂度为：O(n2)即时间复杂度为平方阶。,71,1.4算法和算法分析,算法的时间度量例4.两个N*N矩阵相乘的算法for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k1,最好情况：0次最坏情况：1+2+3+n-1=n(n-1)/2平均时间复杂度为:O(n2),74,1.4算法和算法分析,算法的存储空间需求1）空间复杂度：所需存储空间是问题规模n的某个函数f(n)S(n)=O(f(n)2）算法执行过程中所需的最大空间估算方法：输入数据所占空间+程序所占空间+辅助变量所占空间3)在难以精确计算所需存储空间的情况下，只需求出它关于n的增长率或阶即可4）当所需存储空间随问题的输入数据集变化时，计算平均空间复杂度或最坏情况下的上界,75,小结,有关数据结构的基本概念和术语抽象数据类型ADT的表示与实现类C语言的书写规范算法五个要素的确切含义估算时间复杂度的方法，了解空间复杂度的度量方法,76,作业,1.解释下列术语数据、数据元素、数据对象、数据类型、抽象数据类型、原子数据类型、结构数据类型、逻辑结构、存储结构、数据结构、顺序存储结构、链式存储结构、算法2.