同济大学计算机编程.ppt

《同济大学计算机编程.ppt》由会员分享，可在线阅读，更多相关《同济大学计算机编程.ppt（70页珍藏版）》请在装配图网上搜索。

1、什么是数据结构抽象数据类型及面向对象概念数据结构的抽象层次算法定义模板性能分析与度量,第一章绪论,“学生”表格,“课程”表格,“选课单”包含如下信息学号课程编号成绩时间学生选课系统中实体构成的网状关系,学生(学号,姓名,性别,籍贯),课程(课程号,课程名,学分),选课(学号,课程号,成绩),UNIX文件系统的系统结构图,/(root),bin,lib,user,etc,math,ds,sw,yin,tao,xie,Stack.cpp,Queue.cpp,Tree.cpp,数据（data）,数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。

2、数值性数据非数值性数据,数据元素(dataelement),数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(DataItem)组成。数据项是具有独立含义的最小标识单位。数据元素又称为元素、结点、记录。,数据对象(dataobject),数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象N=0,1,2,学生数据对象,什么是数据结构,定义:由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure=D,R其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。,N个网点之间的连通关系,树形关系,

3、网状关系,1,5,2,4,3,6,1,5,2,4,3,6,数据结构是数据的组织形式,数据元素间的逻辑关系，即数据的逻辑结构；数据元素及其关系在计算机存储内的表示，即数据的存储表示；数据的运算，即对数据元素施加的操作。,数据的逻辑结构,数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；数据的逻辑结构可以看作是从具体问题抽象出来的数据模型；数据的逻辑结构与数据元素本身的形式、内容无关；数据的逻辑结构与数据元素的相对位置无关。,数据的逻辑结构分类,线性结构线性表非线性结构树图（或网络）,线性结构,树形结构,树二叉树二叉搜索树,14,13,12,11,2,3,4,5,6,7,8,9,10,3,1,

4、5,8,7,10,11,9,9,8,7,4,5,6,6,2,3,13,1,bin,dev,etc,lib,user,1,堆结构,“最大”堆“最小”堆,12,3,5,4,8,7,11,10,2,9,1,6,4,10,12,11,5,1,2,3,6,9,8,7,图结构网络结构,1,2,5,6,4,3,1,2,5,4,3,6,11,33,18,14,6,6,5,16,19,21,数据的存储结构,数据的存储结构是逻辑结构用计算机语言的实现；数据的存储结构依赖于计算机语言。顺序存储表示链接存储表示索引存储表示散列存储表示,主要用于内存的存储表示,主要用于外存(文件)的存储表示,抽象数据类型及面向对象概念

5、,数据类型定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称.C语言中的数据类型charintfloatdoublevoid字符型整型浮点型双精度型无值,构造数据类型由基本数据类型或构造数据类型组成。构造数据类型由不同成分类型构成。基本数据类型可以看作是计算机中已实现的数据结构。数据类型就是数据结构，不过它是从编程者的角度来使用的。数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。,抽象数据类型(ADTs:AbstractDataTypes),由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现

6、相分离,抽象数据类型,查找登录删除修改,符号表,自然数的抽象数据类型定义,ADTNaturalNumberisobjects:一个整数的有序子集合,它开始于0,结束于机器能表示的最大整数(MaxInt)。Function:对于所有的x,yNaturalNumber;False,TrueBoolean,+、-、=、=等都是可用的服务。Zero():NaturalNumber返回自然数0,IsZero(x):if(x=0)返回TrueBooleanelse返回FalseAdd(x,y):if(x+y=MaxInt)返回x+yNaturalNumberelse返回MaxIntSubtract(x,y

7、):if(xy)返回0NaturalNumberelse返回x-yEqual(x,y):if(x=y)返回TrueBooleanelse返回FalseSuccessor(x):if(x=MaxInt)返回xNaturalNumberelse返回x+1endNaturalNumber,面向对象的概念,面向对象=对象类继承通信对象在应用问题中出现的各种实体、事件、规格说明等由一组属性值和在这组值上的一组服务（或称操作）构成,类(class)，实例(instance)具有相同属性和服务的对象归于同一类，形成类类中的对象为该类的实例,属性,aPoint1aPoint2aPoint3aPoint4,服务

8、,Draw()move(x,y)contains(aPoint),属性值,属性值,quadrilateral1,quadrilateral2,(35,10)(50,10)(35,25)(50,25),(45,65)(50,45)(65,66)(60,70),Draw()move(x,y)contains(aPoint),Draw()move(x,y)contains(aPoint),服务,服务,四边形类及其对象,quadrilateral,继承派生类：四边形，三角形，子类特化类(特殊化类)基类：多边形父类泛化类(一般化类)通信消息传递,Draw()move(x,y)contains(aPoin

9、t),Polygon,referencePointVertices,Polygon类,referencePointVertices,Draw()move(x,y)contains(aPoint),Polygon的子类Quadrilateral类,Quadrilateral,线性结构直接存取类数组,文件顺序存取类表,栈,队列,优先队列广义索引类线性索引,搜索树非线性结构层次结构类树,二叉树,堆群结构类集合,图,数据结构的抽象层次,算法定义,定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列特性：输入有0个或多个输入输出有一个或多个输出(处理结果)确定性每步定义都是确切无歧义的有

10、穷性算法应在执行有穷步后结束有效性每一条运算应足够基本,事例学习：选择排序问题明确问题：递增排序解决方案：逐个选择最小数据算法框架：for(inti=0;in-1;i+)/n-1趟从ai检查到an-1;若最小整数在ak,交换ai与ak;细化程序：程序SelectSort,算法设计自顶向下，逐步求精,voidselectSort(inta,constintn)/对n个整数a0,a1,an-1按递增顺序排序for(inti=0;in-1;i+)intk=i;/从ai查到an-1,找最小整数,在akfor(intj=i+1;jn;j+)if(ajak)k=j;inttemp=ai;ai=ak;ak=

11、temp;,模板(template),定义适合多种数据类型的类定义或算法，在特定环境下通过简单地代换，变成针对具体某种数据类型的类定义或算法,用模板定义用于排序的数据表类#ifndefDATALIST_H#defineDATALIST_H#includetemplateclassdataListprivate:Type*Element;intArraySize;voidSwap(intm1,intm2);intMaxKey(intlow,inthigh);,public:dataList(intsize=10):ArraySize(size),Element(newTypeSize)dataL

12、ist()deleteElement;voidSort();friendostream#endif,类中所有操作作为模板函数的实现#ifndefSELECTTM_H#defineSELECTTM_H#include“datalist.h”templatevoiddataList:Swap(intm1,intm2)/交换由m1,m2为下标的数组元素的值Typetemp=Elementm1;Elementm1=Elementm2;Elementm2=temp;,templateintdataList:MaxKey(intlow,inthigh)/查找数组Elementlow到Elementhigh

13、/中的最大值，函数返回其位置intmax=low;for(intk=low+1,k=high,k+)if(ElementmaxElementk)max=k;returnmax;,templateostream,templateistream,templatevoiddataList:Sort()/按非递减顺序对ArraySize个关键码/Element0到ElementArraySize-1排序for(inti=ArraySize-1;i0;i-)intj=MaxKey(0,i);if(j!=i)swap(j,i);#endif,使用模板的选择排序算法的主函数#include“selecttm

14、.h”constintSIZE=10;intmain()dataListTestList(SIZE);cinTestList;coutTestListendl;TestList.Sort();coutTestListendl;return0;,性能分析与度量,算法的性能标准算法的后期测试算法的事前估计,算法的性能标准,正确性可使用性可读性效率健壮性,算法的后期测试,在算法中的某些部位插装时间函数time()测定算法完成某一功能所花费时间,顺序搜索(SequenialSearch)intseqsearch(inta,intn,intx)/在a0,an-1中搜索xinti=0;while(in,插

15、装time()的计时程序doublestart,stop;time(,算法的事前估计,空间复杂度时间复杂度,空间复杂度度量,存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间,时间复杂度度量,编译时间运行时间程序步语法上或语义上有意义的一段指令序列执行时间与实例特性无关例如：声明语句：程序步数为0;表达式：程序步数为1,程序步确定方法插入计数全局变量count建表，列出个语句的程序步,例以迭代方式求累加和的函数

16、floatsum(floata,intn)floats=0.0;for(inti=0;in;i+)s+=ai;returns;在求累加和程序中加入count语句floatsum(floata,intn),floats=0.0;count+;/count统计执行语句条数for(inti=0;in;i+)count+;/针对for语句s+=ai;count+;/针对赋值语句count+;/针对for的最后一次count+;/针对return语句returns;执行结束得程序步数count=2*n+3,程序的简化形式voidsum(floata,intn)for(inti=0;in;i+)count

17、+=2;count+=3;,注意：一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。例如：赋值语句x=sum(R,n)本身的程序步数为1；一次执行对函数sum(R,n)的调用需要的程序步数为2*n+3；一次执行的程序步数为1+2*n+3=2*n+4,计算累加和程序程序步数计算工作表格,时间复杂度的渐进表示法,例求两个n阶方阵的乘积C=AB,voidMatrixMultiply(intAnn,intBnn,intCnn)for(inti=0;in;i+)n+1for(intj=0;jn;j+)n(n+1)Cij=0;n2for(intk=0;kn;k+)n2(n+1)Cij=Cij

18、+Aik*Bkj;n3,2n3+3n2+2n+1,时间复杂度的渐进表示法,算法中所有语句的频度之和是矩阵阶数n的函数T(n)=2n3+3n2+2n+1一般地，称n是问题的规模。则时间复杂度T(n)是问题规模n的函数。当n趋于无穷大时，把时间复杂度的数量级（阶）称为算法的渐进时间复杂度T(n)=O(n3)-大O表示法,时间复杂度的渐进表示法,加法规则针对并列程序段T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)各种函数的增长趋势clog2nnnlog2nn2n32n3nn!,变量计数,x=0;y=0;for(intk=0;kn;k+)x+;for(inti=0;in;i+)f

19、or(intj=0;jn;j+)y+;,T1(n)=O(1),T2(n)=O(n),T3(n)=O(n2),T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2)=O(n2),乘法规则针对嵌套程序段T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)渐进的空间复杂度S(n)=O(f(n)两个并列循环的例子,voidexam(floatx,intm,intn)floatsum;for(inti=0;im;i+)/x中各行sumi=0.0;/数据累加for(intj=0;jn;j+)sumi+=xij;for(i=0;im;i+)/打印各行数据和couti“:”sumie

20、ndl;渐进时间复杂度为O(max(m*n,m),template/起泡排序voiddataList:bubbleSort()/对表逐趟比较,ArraySize是表当前长度inti=1;intexchange=1;/当exchange为0则停止排序while(iArraySize/一趟比较,templatevoiddataList:BubbleExchange(inti,int/做“发生交换”标志,渐进时间复杂度O(f(n)*g(n)=O(n2),BubblrSortn-1趟,BubbleExchange()n-i次比较,有时,算法的时间复杂度不仅依赖于问题规模n，还与输入实例的初始排列有关。

21、在数组An中查找给定值k的算法：inti=n-1;while(i=0算法的语句i-的频度不仅与n有关，还与A中各元素的取值，以及k的取值有关。,例：设有两个算法在同一机器上运行，其执行时间分别为100n2和2n，问：要使前者快于后者，n至少要取多大？解答：问题是找出满足100n22n=8192n=14时，100n2=196002n=16384n=15时，100n2=225002n=32764取n=15满足要求。,出错处理问题举例,试编写一个函数计算n!*2n的值，结果存放于数组AarraySize的第n个数组元素中(0narraySize)若设计算机中允许的整数的最大值为maxInt，则当na

22、rraySize或者对于某一个k(0kn)，使得k!*2kmaxInt时，应按出错处理。,可有如下三种不同的出错处理方式：,用cerr及exit(1)语句来终止执行并报告错误；用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某中错误返回。,#includeiostream.h#definearraySize100#defineMaxInt0 x7fffffffintcalc(intT,intn)inti,value=1;if(n!=0)for(i=1;iMaxInt/n/2)return0;/直接判断i!*2iMaxInt是危险的,value*=n*2;Tn=value;return1;/n!*2nTnvoidmain()intAarraySize,i;for(i=0;iarraySize;i+)if(!calc(A,i)coutfailedatiendl;break;,