第1章(绪论)

NorthChinaElectricPowerUniversity祝同学们新学期愉快学习进步！祝同学们新学期愉快学习进步！华电计算机系NorthChinaElectricPowerUniversity数据结构(DataStructure)教材名称：《数据结构》王翠茹编著中国电力出版社任课教师：牛为华工作单位：计算机系华电教材科有售华电计算机系NorthChinaElectricPowerUniversity开设本课程的必要性以及课程的特点：1.计算机学科综合性的专业基础课之一.2.需要有关“程序设计语言”和“离散数学”的知识作为课程的基础.3.实践性较强.华电计算机系NorthChinaElectricPowerUniversity第一章绪论华电计算机系NorthChinaElectricPowerUniversity1.1课程简介1.2基本概念1.3算法及算法评价1.4算法语言的说明华电计算机系NorthChinaElectricPowerUniversity1.1课程简介算法+数据结构=程序（Algorithm+Datastructure=Program)程序设计：为计算机处理问题编写的一组指令。算法：处理问题的策略。数据结构：问题的数学模型。程序设计的实质是数据的表示和数据处理,为此应提出问题的数学模型和设计相应的算法。华电计算机系NorthChinaElectricPowerUniversity例如1.铺设煤气管道问题ABCDIHGEF32.844.612.18.756.421.341.167.310.585.698.752.579.2(a)居民区示意图ABCDIHGEF32.812.18.721.341.110.579.2(b)铺设煤气管道设计图华电计算机系NorthChinaElectricPowerUniversity例如2.图书馆的书目检索问题登录号书名作者分类号………………172832离散数学樊映川S01…172833理论力学罗远祥S01…172834高等数学华罗庚S01…172835线性代数滦汝书S02………………书名登录号……高等数学172832、172834…理论力学172833…线性代数172835………作者登录号……樊映川172832…华罗庚172834…滦汝书172835………类别登录号……L172833…S172832、172834………华电计算机系NorthChinaElectricPowerUniversity1.2基本概念数据数据是描述客观事物的数、字符以及所有能输入到计算机中并为计算机程序处理的对象的集合。数据元素数据的基本单位，有时一个数据元素也可以由若干个数据项组成。数据项数据处理的最小单位。980604刘晔女188010学号姓名性别年月日组合项原子项出生日期（学生情况）华电计算机系NorthChinaElectricPowerUniversity1.2基本概念数据对象性质相同的数据元素的集合。数据的逻辑结构对数据元素之间逻辑关系的描述。它可以用一个数据元素的集合和定义在这个集合上的若干关系来表示。DataStructure=(D,S)D:数据元素的集合;S:D上关系的集合1）集合：集合中任何两个结点之间都没有逻辑关系，组织形式松散。华电计算机系NorthChinaElectricPowerUniversity2）线性结构：元素之间存在着一对一的关系。依次排列形成一条“锁链”。3）树形结构：数据元素之间存在着一对多的关系，具有分支、层次特性。4）图状结构：数据元素之间存在多对多的关系，元素之间互相缠绕，具有网络特性。华电计算机系NorthChinaElectricPowerUniversity1.2基本概念数据的存储结构逻辑结构及数据元素在计算机中的表示.1）顺序存储方式（向量存储）2）链式存储方式3）索引存储方式4）散列存储方式数据类型是程序设计语言中允许的变量种类，一个值的集合和定义在这个值上的一组操作。分为两类：1）原子类型2）结构类型华电计算机系NorthChinaElectricPowerUniversity1.2基本概念抽象数据类型一个数学模型和定义在这个数学模型的一组操作。特性数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征，其完成的功能以及和外部的接口。数据封装：将实体的外部特性和其内部实现分离，并对外部用户隐藏其内部实现细节。ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据类型名华电计算机系NorthChinaElectricPowerUniversity例如：ADTComplex{数据对象：D={e1,e2|e1,e2∈Realset}数据关系：R1={e1,e2|e1是复数的实数部分、e2是复数的虚数部分}基本操作：InitComplex(v1,v2)；初始化：v1,v2的值赋值DestroyComplex(Z)；销毁复数ZGetReal(Z,realPart)；得到Z的实部GetImag(Z,ImagPart)；得到Z的虚部Add(Z1,Z2,Sum)；复数Z1、Z2相加Subtract(Z1,Z2,Difference)；复数Z1、Z2相减Multiply(Z1,Z2,Product)；复数Z1、Z2相乘}ADTComplex华电计算机系NorthChinaElectricPowerUniversity1.2基本概念数据结构数据结构就是要研究数据之间的结构关系。具体来说，它包括数据的逻辑结构和物理结构，以及在这些结构上定义的相应的运算。按照某种逻辑结构组织的一组数据，按一定的存储方式将它们映射到计算机的存储器中，并且在这些数据上定义了一个运算的集合，运算的结果保持原来的结构。结构结构是指同一数据对象中各数据元素之间存在的关系。华电计算机系NorthChinaElectricPowerUniversity1.研究数据元素之间的客观联系。2.研究具有某种逻辑关系的数据在计算机存储器内的存储方式。3.研究如何在数据的各种结构(逻辑的和物理的)的基础上对数据实施一系列有效的基本操作。逻辑结构存储结构数据结构课程研究的主要内容算法华电计算机系NorthChinaElectricPowerUniversity数据结构举例例1：一系列整数，我们可以用算术运算“+、-、*、/”等进行运算，此时数据对象是整数集合，那么，数据对象整数再加上“+、-、*、/”等符号的运算就构成了一个数据结构的定义。例2：建立一个大学教师档案，逻辑结构如下图，数据对象为教师情况的集合，构成了一种数结构，这种数结构就是其逻辑关系，教师档案这个数据对象再加上查找，删除，插入等操作就构成了一个数据结构的定义。华电计算机系NorthChinaElectricPowerUniversity计算机教研室发电教研室华电电力系动力系计算机系…软件教研室…教师A…………华电计算机系NorthChinaElectricPowerUniversity数据结构课程研究的主要内容三个层次：抽象实现评价主要内容可以归纳为三个层次五个要素：五个要素：逻辑结构存储结构不同结构的基本运算算法比较及分析华电计算机系NorthChinaElectricPowerUniversity1.3算法及算法评价算法概念解决问题的方法和步骤，指为解决一个或一类问题给出的一个确定的、有限长的操作序列。算法特性1、有穷性2、确定性3、可行性4、有输入5、有输出华电计算机系NorthChinaElectricPowerUniversity1.3算法及算法评价算法分类1、程序设计语言描述的算法2、伪语言算法3、非形式算法（自然语言算法）算法评价1、算法的正确性2、算法是否易读、易写、易改3、算法执行速度4、算法所占空间华电计算机系NorthChinaElectricPowerUniversity假如随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则记作T(n)=O(f(n))，称T(n)为算法的时间复杂性时间复杂度频度统计法以语句执行的次数的多少作为算法的时间量度的分析方法称为频度统计法。一条语句的频度是指该语句被执行的次数，而整个算法的频度是指算法中所有语句的频度之和。华电计算机系NorthChinaElectricPowerUniversity•例如：•1）x=x+1：•2）For(i=1;i=n;i++)•x=x+1;••3)For(i=1;i=n;i++)•For(j=1;j=n;j++)x=x+1；•机器只执行一次，则它的频度为一次，即f（n）=1执行时间复杂度为O(1)。其语句执行n次，频度为n次，执行时间与n成正比，f（n）=n，复杂度为O(n）。•其语句执行n²次，频度为n²次，执行时间与n²成正比，f（n）=n²，复杂度为O(n²）。华电计算机系NorthChinaElectricPowerUniversity算法的频度:f(n)=n+1+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+14）voidMATRIX(A,B,C,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]=C[i][j]+A[i][k]B[k][j];}}}--------------------------n+1-------------------n(n+1)----------------------------------n2-----------n2(n+1)----n3华电计算机系NorthChinaElectricPowerUniversity当n→∞时，有f(n)/g(n)=常数≠0，则称函数f(n)与g(n)同阶,或者说，f(n)与g(n)同一个数量级，记作f(n)=O(g(n))称上式为算法的时间复杂度,或称该算法的时间复杂度为O(g(n))。其中,n为问题的规模(大小)的量度。算法的时间复杂度为O(n3)lim(f(n)/g(n))=lim((2n3+3n2+2n+1)/n3)=2n→∞n→∞关于符号O的的数学定义华电计算机系NorthChinaElectricPowerUniversity假如随着问题规模n的增长，算法执行所需存储量的增长率和g(n)的增长率相同，则记作S(n)=O(g(n))，称S(n)为算法的空间复杂性。空间复杂度算法的存储空间1.输入数据所占的空间2.程序本身所占的空间3.辅助变量所占的空间华电计算机系1.4、算法语言的说明1.采用自然语言来描述(1)M除以N，将余数送中间变量R；(2)测试余数R是否等于零？a)若R等于零，求得的最大公因子为当前N的值,算法到此结束。b)若R不等于零，将N送入M，将R送N,重复算法的(1)和(2)。问题：求两个正整数M与N的最大公因子。华电计算机系NorthChinaElectricPowerUniversity2.采用程序流程图的形式来描述开始M除以N的余数送R余数R为0否？输出N的值结束将N送M将R送Nnoyes华电计算机系3.采用某种具体程序语言来描述COMFACTOR(M,N)intM,N;{intR;while(1){R=M%N;if(R==0)returnN;M=N;N=R;}}用C语言描述的求两个正整数最大公因子的算法(C函数)华电计算机系NorthChinaElectricPowerUniversity类C语言4.设计一种既脱离某种具体的程序设计语言，又具有各种程序设计语言的共同特点的形式化语言来描述华电计算机系类C语言简介一、算法的格式Pascal语言PROGRAM程序名(input,output);说明部分；BEGIN语句串；END.C语言函数名(参数表)参数说明；{说明部分；语句串；}procedure过程名(参数表)说明部分；begin语句串；End;华电计算机系北航计算机系类C语言的特点1、算法中使用的辅助变量可以不做变