计算机软件及应用chapter是.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,Teaching Material,Text Book,Data Structure And Algorithms In C,+second edition,.Adam.Drozdek,Reference Book,王红梅,.,数据结构（,C,版）,.,清华大学出版社,Mark Allen Weiss.Data Structures&algorithm analysis in C+(second edition),严蔚敏,.,数据结构,.,清华大学出版社,.1997,Study Highlight,Time Complexity(,算法与时间复杂度,),kmpleksiti,Linear List,(,线性表,),Stack and Queue,(,栈和队列）,General List,(,广义线性表,),Tree and Binary Tree(,树与二,叉,树,),Graph(,图,),Search,ing,(,查找,),Sorting(,排序,),算法与数据结构是计算机科学的两大支柱,计算机科学早期定义为：研究算法的科学,近期定义为：研究数据的科学,数据结构是程序设计的基础,是计算机科学中一门综合性专业课程,尼克劳斯沃思（,Niklaus Wirth,）,:,瑞士计算机科学家。,PASCAL,之父，结构化程序设计的首创者，获得,1984,年图灵奖。,Program=,Data Structure,+,Algorithm,使用最适当的,【,数据结构,】,，才能够设计出最有效率的,【,算法,】,，进而转换成为有效率的,【,程序,】,。,qual to,这句话从此就成了计算机学科的一句名言，数据结构是一门和程序设计密切相关的课程,Data Structure Mainly Content,87352545,电子商务学院电话号码,130012,长春工程学院邮编,510103780618748,身份证号码,例1：87352545,130012,510103780618748,结论1.,杂乱的数据不能表达和交流信息,例2:电话号码簿(,a,1,，,b,1,)(a,2,，,b,2,)(a,n,，,b,n,),其中：,a,i,为某人姓名，,b,i,为该人的电话号码。,要求：设计一个算法，给定一个姓名时，能查出此人的电话号码。,如果姓名和电话号码的排列次序无规律，,则只能逐一比较姓名进行查找,如果姓名按字典顺序组织，则查找就快捷多了,结论2.数据之间是有联系的,这些联系常常影响算法的选择和效率。,DS,就是要研究数据之间的联系。,Data Structure Mainly Content,例3：大学学生管理机构,长春工程学院,土木电信,09,级,10,级,11,级,本科,专科,张三 李四,结论数据之间是有结构的,例中数据之间呈分层结构（,Tree,）,DS,就是要研究数据之间的各类结构。,Data Structure Mainly Content,例：图书目录管理,设每个书目含：书名，作者，登录号，分类，出版年月,对图书目录常有如下操作：,查找：某书在书库中是否存在？,插入：购进新书时的登录；,删除：报废或丢失的书，需从目录中去掉；,结论在某种数据结构上可定义一组运算,DS,要研究各类数据结构上的各种运算。,Data Structure Mainly Content,综上所述：,DS,主要研究内容：,数据的各种逻辑结构和物理结构，以及它们之间的相应关系；,对每种结构定义相适应的各种运算；,设计出相应的算法；,分析算法的效率。,常见的数据结构有：表(,linear list)、,数组(,array)、,串(,string),、栈(,stack)、,队列(,queue)、,树(,tree)、,图(,graph),等。,方法：查找（,search）、,排序(,sort),Study Purpose about Data Structure,数据结构课程的三级标准,1.掌握各类基本数据结构类型和相应的存储结构,2.提高阅读和编写算法的能力,3.能针对给定问题，选择相适应的数据结构，并能设计和分析算法,C+,语言 数据结构 软件工程,掌握基本编程方法,掌握数据组织和数据处理的方法,掌握大型软件开发方法,学习识字,学习写作文,学习写小说,基本要求,课程关系,与语文学习过程类比,本课程在计算机专业课程中所处的地位,课程性质,数据结构是计算机专业的专业基础课,公共基础课、专业基础课、专业方向课、专业选修课,在教学计划中的地位：核心专业基础课、承上启下,前导课：高等数学、离散数学、程序设计语言,后续课：数据库、操作系统、编译原理,属于武术中的“练功”科目,“练武不练功，到头一场空”,考研,需要大家课后自己复习的内容：,第,0,章 预备知识,学习目标,掌握基本的数据结构,工具箱复用、修改、重组,培养算法设计能力、程序设计能力,算法,程序的灵魂,问题求解过程：问题想法算法程序,培养算法分析能力,评价算法、改进算法,学习要求,循序渐进，切忌心浮气躁,提高课外学习的时间和内容,理解科学而不是背诵科学读书,正确对待考试,作习题,华罗庚：“学数学不做习题等于入宝山而空返”,作实验,计算机学科是一门,科学性与工程性,并重的学科，表现为理论和实践紧密结合的特征。,成绩组成,平时成绩,10,：出勤作业,实验成绩,20,：出勤程序报告,期末考试成绩,70,Chapter 1:Introduction,History of Data Structure,Research objects,Basic concepts,Algorithm and algorithm analysis,basic content,：,1938,年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著：,The Art of Computer Programming,他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年仅36岁。,数据结构的创始人,克努思,1.1,History,程序设计的实质是什么?,data presentation,：,将数据存储在计算机中,data processing,：,处理数据，求解问题,数据结构问题起源于程序设计,实例：学生成绩管理系统,数据结构随着程序设计的发展而发展,计算机学科的飞速发展是其他任何学科所无法比拟的。,No structure stage,:20,世纪,4060,年代,计算机主要用于科学计算,.,Application Field,：科学计算；,Processed data,：数值型数据,The relationship among data,：数学方程或数学模型,1.1,History,2.,Structured stage,：数据结构算法程序,Application Fields,：,科学计算与非数值处理；,Processed data,：,数值型数据和非数值型数据,The relationship among data,：,产生了数据结构，提出了程序,结构模块化,，开始注意数据表示和操作的结构化。,drawback,：以数据为中心，不易应对变化,1.1,History,3.Object-oriented stage,：,(,数据结构算法,)=,程序,Application Fields,：,更多地应用于非数值处理；,Processed data,：,更多地处理非数值型数据,The relationship among data,：数据结构发展到面向对象阶段,类和数据结构之间的对应关系：,1.1,History,类,属性,方法,数据结构,数据之间的关系,基本操作,对应,数据结构的发展并未终结,1.2,Research Objects of DS,steps for solving problems with computer,:,A,problem,Abstract a problem model,Find out the solution of this model,Problem,Numerical,problem,and non-,numerical problem,Numerical,problem,Mathematical Equation,non-,numerical problem,DS,Known,length and wide of a swimming pool,then,find out,area of the pool.,Build a model,问题涉及的,对象,：游泳池的长,len,、宽,wide,和面积,area,对象之间的,关系,The relationship among objects,：,area=len,wide,设计求解问题的方法,Design the method of solving the problem,编程,programming,nun,ri,example,一、,Numerical Problems and non-,numerical problem,Numerical problem,Known,length and wide of a swimming pool,then,find out,area of the pool.,Build a model,问题涉及的,对象,：,length,wide and area.,对象之间的,关系,:,area=len,wide,Design the method of solving the problem,programming,example,一、,Numerical Problems and non-,numerical problem,Numerical problem,#include,void main(),int len,wide,area;,cinlenwide;,area=len*wide;,coutarea=areaendl;,1.1,数据结构讨论的范畴,2,）,non-numerical problem,play chess,.,.,.,.,.,.,Build model,问题涉及的对象：,the object of,problem,involved:,对弈过程中可能出现的棋盘格局；,Checkerboard pattern that may occur in the chess process,checkerboard patterns,树,即是一种数据结构,1.1,数据结构讨论的范畴,Build model,问题涉及的对象,:,对弈过程中可能出现的棋盘格局；,棋盘格局之间的关系：由比赛规则决定。,对弈的过程就是从树根沿树杈到某个叶子的过程。,The process of chess is from the root to a leaf along the crotch,.,1.1,数据结构讨论的范畴,棋盘格局之间的关系：,The relationship among the checkerboard patterns,由比赛规则决定。,Determined by the rules of the game,对弈的过程就是从树根沿树杈到某个叶子的过程。,The process of chess is from the root to a leaf along the crotch.,2,）非数值问题,酒店管理系统的客房分配问题,Rooms allocated for hotel management system,建模型,：,build model,问题涉及的对象,the object of,problem,involved:,：房间；,room,房间之间的关系：,The relationship between the rooms,线性关系，一对一的关系,每个房间之间的磨损应该是相同的,front,rear,a,1,a,2,a,3,a,n,入队列,出队列,线性结构,1.1,数据结构讨论的范畴,2,）非数值问题,Rooms allocated for a hotel,lukeit,build a model,：,问题涉及的对象：,room,对象之间的关系：,The relationship between the rooms,线性关系，一对一的关系,每个房间之间的磨损应该是相同的,front,rear,a,1,a,2,a,3,a,n,入队列,出队列,Linear list,1.1,数据结构讨论的范畴,非数值问题,terminal examinations,已知研究生选课情况，安排课程考试的日程,要求在尽可能短的时间内完成考试。,研究生选课情况表,姓 名,选修课,1,选修课,2,选修课,3,杨润生,算法分析,A,形式语言,B,计算机网络,E,石 磊,计算机图形学,C,模式识别,D,魏庆涛,计算机图形学,C,计算机网络,E,人工智能,F,马耀先,模式识别,D,人工智能,F,算法分析,A,齐砚生,形式语言,B,人工智能,F,1.1,数据结构讨论的范畴,建立模型：,问题涉及的,对象,：,elective course,课程之间的,关系,：同一研究生选修的课程之间有,“,冲突,”,关系。,(,同一个研究生选修的课程不能安排在同一时间内考试,),conflict,C,D,E,A,B,F,顶点：表示课程,同一研究生选修的,课程用边连接,有边连接的课程不能,安排在同一时间考试,1.1,数据结构讨论的范畴,每一种颜色代表一个考试时间，着上相同颜色的顶点是可以安排在同一时间考试的课程；,用尽可能少的颜色为图的顶点着色，使相邻的顶点着上不同的颜色；,D,B,A,E,F,C,F,B,E,A,C,D,课程考试可用图的着色法求解问题,第一天,the first day,算法分析,(A),计算机图形学,(C),第二天,the second day,形式语言,(B),模式识别（,D),第三天,计算机网络,(E),第四天,人工智能,(F),设计求解问题的方法,求解,考试日程的流程,设,G,表示课程关系图，,V,是图,G,中所有尚未着色的顶点集合。,NEW,表示可以用新颜色着色的顶点集合。,i=1,；,V=,图中所有顶点的集合,若,V,非空,DO ,置,NEW,为空集合；,在,V,中找出所有,“,不相邻,”,的顶点，将这些顶点加入,NEW,从,V,中去掉这些顶点。,i=i+1,；,若,V,空,结束。,D,B,A,E,F,C,第,i,天考试课程为,NEW,中顶点所对应的课程）以某种形式输出,NEW,中顶点所对应的课程；,1.1,数据结构讨论的范畴,多叉路口交通灯管理问题,C,E,D,A,B,AB,AC,AD,BA,BC,BD,DA,DB,DC,EA,EB,EC,ED,graph,每个圆圈代表一条通路,黄灯亮的时候，只有,DA,DB,两条路可通行,建模型,：,问题涉及的对象：,每个圆圈（即每条通路）；,圆圈之间的关系：,圆圈之间的冲突关系。,设计求解问题的方法：同上,数值问题,numerical problems,*对象,objects,：,len,wide,area,用数值表示,*对象之间的关系,The relationship among the objects,：,area=len,wide,可用,方程或函数,表示,*数据存储,data storage,：可用程序设计语言中的实型变量存储数据；,*问题求解方法：用某种计算方法求解；,kmprisn,非数值问题,non-numerical problems,*对象,objects,：课程,-,用课程名表示,*对象之间的关系：课程间有,“,冲突,”,关系,*数据及数据之间的关系存储,*问题求解方法,不能用数值表示,课程之间的这种关系,不能用方程或函数表示,二、数值问题与非数值问题的比较,a,comparison,between the numerical problems and non-numerical problems,1.1,数据结构讨论的范畴,numerical problems,*,objects,：,length,wide,area,用数值表示,*,The relationship among objects,：,area=len,wide,可用,方程或函数,表示,*,data storage,：可用程序设计语言中的实型变量存储数据；,*,problem solving,：用某种计算方法求解；,non-numerical problems,*,objects,：,course-,用课程名表示,*,The relationship among objects,：,课程间有,“,冲突,”,关系,*,data storage and relationship among objects storage,*,problem solving,不能用数值表示,课程之间的这种关系,不能用方程或函数表示,二、,comparison,between numerical problem and non-numerical problem,数据结构是研究,非数值,问题中计算机的,操作对象,以及它们之间的,关系,和,操作,的学科。,data structure is a course,which research operation object of computer,the relations between them and operation about non-numericalproblem,1.2,research objects,数值问题,是计算数学所要研究的问题。计算数学是研究数值计算方 法的设计、分析和有关理论基础的数学分支。,Data Structure,is a subject of studying the computer operational objects,their relationships among them and operation in the non-numerical problem.,P30,1.2,research objects,数值问题,是计算数学所要研究的问题。计算数学是研究数值计算方 法的设计、分析和有关理论基础的数学分支。,1.3,basic concepts,（,1,）,data,：所有能,输入,到计算机中并能被计算机程序,识别和处理,的符号集合。,计算机能处理的数据集和是随着计算机的,发展而发展,的，,numerical data,：整数、实数等,non-numerical data,：图形、图象、声音、文字等,（一）,basic concepts,1.3,basic concepts,（,1,）,data,：所有能,输入,到计算机中并能被计算机程序,识别和处理,的符号集合。,Data,the set of numbers,characters,which describe the external objects,and all information which can be input into the computer and processed by computer programs.,Symbol Set which,can be input into the computer and be,identified and,processed by computer programs.,计算机能处理的数据集和是随着计算机的,发展而发展,的，,数值数据：整数、实数等,非数值数据：图形、图象、声音、文字等,（一）,basic concepts,(2),data element,数据中的一个“个体”，,an individual in data,是数据结构中讨论的,基本单位,。但不是最小单位。,Is the basic unit of data,but is not the smallest Unit;also called node or record.Each data element can be consist of several Data Items(the minimal unit of Data).,数据项,（,data item,）,数据结构中讨论的,最小单位,。,(the minimal unit of Data).,数据元素是数据项的集合,例如：一个学生的信息（数据元素）,学 号,姓 名,性 别,出生日期,政治面貌,0001,陆 宇,男,1986/09/02,团员,0002,李 明,男,1985/12/25,党员,0003,汤晓影,女,1986/03/26,团员,(2),data element,数据中的一个“个体”,是数据结构中讨论的,基本单位,。但不是最小单位。,data item,数据结构中讨论的,最小单位。,数据元素是数据项的集合,例如：一个学生的信息（数据元素）,学 号,姓 名,性 别,出生日期,政治面貌,0001,陆 宇,男,1986/09/02,团员,0002,李 明,男,1985/12/25,党员,0003,汤晓影,女,1986/03/26,团员,data object,：是性质相同的数据元素的集合，是数据的一个子集。,Data Object,the set of data elements with same attribute.It is the subset of Data and can be either finite or infinite.,例如：整数数据对象的集合：,N=0,1,2,字母字符数据对象的集合：,C=,A,B,Z,data object,：是性质相同的数据元素的集合，是数据的一个子集。,例如：整数数据对象的集合：,N=0,1,2,字母字符数据对象的集合：,C=,A,B,Z,relationships among data,data element and data item,包含关系：数据是由数据元素组成，数据元素是由数据项组成。,数据元素,是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。,数据结构,：相互之间存在一定,关系,的数据元素的集合。,Data Structure,the set of data elements with some special relationships.,按照视点的不同，数据结构分为,逻辑结构和存储结构,。,According to the different viewpoint,data structure is divided into logical structure and storage structure,逻辑结构：指数据元素之间,逻辑关系,的整体。,Logical Structure,关联方式或邻接关系,数据的逻辑结构是从具体问题抽象出来的,数据模型,酒店管理问题中，客房之间的逻辑关系指的是什么？,人机对弈问题中，格局之间的逻辑关系指的是什么？,考试计划编排问题中，课程之间的逻辑关系指的是什么？,Data Structure,the set of data elements with some special relationships.,P31,data structure is divided into logical structure and storage structure,Logical Structure,：指数据元素之间,逻辑关系,的整体。,数据的逻辑结构是从具体问题抽象出来的,数据模型,酒店管理问题中，客房之间的逻辑关系指的是什么？,人机对弈问题中，格局之间的逻辑关系指的是什么？,考试计划编排问题中，课程之间的逻辑关系指的是什么？,数据的逻辑结构是从具体问题抽象出来的,数据模型,Logical structure of data is a,data model which is abstracted from the specific issues.,二、,Logical Structure,数据元素之间的,逻辑关系,）,(1),数据的逻辑结构可归结为以下四类：,Set,数据元素间除,“,同属于一个集合,”,外，无其它关系,Linear list,one-to-one,，如线性表、栈、队列,Tree,one-to-many,graph,多,many-to-many,1.2,基本概念,非线性结构,Logical Structure,1)Set,2)Linear list,3)Trees,4)Graphs,Storage Structure,1)Sequential Storage,2)Linked Storage,3)Indexed Storage,4)Hashing Storage,(2),数据,逻辑,结构的形式定义,formal definition of logical structure,二元组表示法,t,wo-tuples notation,D,ata_,S,tructure=(,D,S,),其中：,D,-,数据元素的有限集合。,finite set of data element,S,-,定义在,D,上的关系的有限集合。,finite set of relationship which defined in D,S,=r,r,是,D,上的一个二元关系,r is a,binary relation in D,1.2,基本概念,(2),数据,逻辑,结构的形式定义,二元组表示法,D,ata_,S,tructure=(,D,S,),其中：,D,-,数据元素的有限集合。,S,-,定义在,D,上的关系的有限集合。,S,=r,r,是,D,上的一个二元关系,1.2,基本概念,L=(D,S),其中：,D=a,1,a,2,a,3,.,a,n,L=(D,S),其中：,D=a,1,a,2,a,3,.,a,n,S=r,r=,例,1,a,n,a,i+1,a,i-1,a,i,a,2,a,1,Linear list,set,例,2,a,n,a,i+1,a,i-1,a,i,a,2,a,1,T=(D,R),D=A,，,B,，,C,，,D,，,E,，,F,，,G,，,H,，,I,，,J R=r r=A,B,tree,例,3,J,I,A,C,B,D,H,G,F,E,G1=(V1,E1),V1=v,0,v,1,v,2,v,3,v,4,E1=(v,0,v,1,),(v,0,v,3,),(v,1,v,2,),(v,1,v,4,),(v,2,v,3,)(v,2,v,4,),V0,V4,V3,V1,V2,V0,V1,V2,V3,G2=(V2,E2),V2=v,0,v,1,v,2,v,3,E2=,Graph,Exmp 4,无向图,有无向图,P46,5,题,数据结构,：相互之间存在一定,关系,的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。,逻辑结构：指数据元素之间,逻辑关系,的整体。,存储结构：又称为物理结构，是数据及其逻辑结构在,计算机,中的表示。,Also known as the physical,Is representation of the data with its logical structure in the computer.,1.3 数据结构的基本概念,数据结构的基本概念,内存,memory,存储结构实质上是内存分配，,在具体实现时，依赖于计算机语言。,数据结构,：相互之间存在一定,关系,的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。,逻辑结构：指数据元素之间,逻辑关系,的整体。,存储结构：又称为物理结构，是数据及其逻辑结构在,计算机,中的表示。,1.3 数据结构的基本概念,数据结构的基本概念,内存,存储结构实质上是内存分配，,在具体实现时，依赖于计算机语言。,三、,Storage Structure,数据的逻辑结构在计算机,存储器中,的实现,Sequential Storage,用一组连续的内存单元依次存放数据,元素。通过元素的存储顺序反映数据元素,之间的逻辑关系,a,1,a,2,a,i-1,a,i,a,i+1,a,n,Linked Storage,用内存中任意一组单元存放数据元素,通过保存元素的存储位置来表示数据元素之间的逻辑关系。,a,1,a2,a,i-1,ai,an,四、,Data operations,common operations,建立数据结构,清除数据结构,插入一个新数据元素,删除某个数据元素,修改某个数据元素,排序,检索,Insert delete update select sort,1.2,基本概念,1.3,数据结构的基本概念（小结）,数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。,数据的逻辑结构,只抽象反映数据元素的,逻辑关系,数据的,存储（物理）结构,数据的逻辑结构在计算机,存储器中的实现,数据的逻辑结构与存储结构密切相关,算法设计 逻辑结构 （取决于）,算法实现 存储结构（依赖于）,存储结构分为：,顺序,存储结构,借助元素在存储器中的,相对位置,来表示,数据元素间的逻辑关系,链式,存储结构,借助指示元素存储地址的,指针,表示数据,元素间的逻辑关系,1.2,基本概念,数据的逻辑结构,数据的存储结构,数据的运算：检索、排序、插入、删除、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面：,1.2,基本概念,五、,data type,and,Abstract Data Type,1,、,data type,一个值的集合和定义在这个值集上的一组操作的总称。,all the data categories that each variable possessed defined in one program design language.,例如：整形变量，其值为某个区间上的整数，定义在其上的操作可以为加减乘除和取模等算术运算。,数据类型,原子类型（,int,float,char,）结构类型（数组，结构体）,五、,data type,and,Abstract Data Type,1,、,data type,一个值的集合和定义在这个值集上的一组操作的总称。,例如：整形变量，其值为某个区间上的整数，定义在其上的操作可以为加减乘除和取模等算术运算。,data type,原子类型（,int,float,char,）结构类型（数组，结构体）,2,、,Abstract Data Type(ADT),指一个数据结构以及定义在该结构上的一组操作的总称,.,1.2,基本概念,2,、,Abstract Data Type(ADT),指一个数据结构以及定义在该结构上的一组操作的总称,.,a mathematic model and the set of all operations defined on it.,（其定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。）,1.2,基本概念,Abstract Data Type(ADT),a mathematic model and the set of all operations defined on it.,ADT can be presented by a triplet(,D,S,P,),while,D,is data objects,S,is set of relationship on,D,P,is operations in,D,Definition:,ADT name,Data objects:,Data relationships:,Elementary operations:,ADT name,Elementary operation name(parameter list),initial condition:description,result of operation:description,P50,ADT,可理解为对数据类型的进一步抽象,抽象数据类型比数据类型的范畴更广，它不再局限于固有数据类型，还包括用户自己定义的数据类型,ADT,逻辑结构,操作集合,数据结构,存储结构,算法设计,(a),使用视图,ADT,的定义,(b),设计视图,ADT,的设计,(c),实现视图,ADT,的实现,图,1,-,7,ADT,的不同视图,类,成员变量,成员函数,本书对,ADT,的定义包括抽象数据类型名、数据元素之间逻辑关系的定义、每种基本操作的接口。,形式如下：,ADT,抽象数据类型名,Data,数据元素之间逻辑关系的定义,Operation,操作,1,前置条件：执行此操作前数据所必须的状态,输入：执行此操作所需要的输入,功能：该操作将完成的功能,输出：执行该操作后产生的输出,后置条件：执行该操作后数据的状态,操作,2,操作,n,1.4,算法和算法的分析,Algorithm and Algorithm Analysis,一、算法,（,algorithm,）,的概念,算法是求解问题的操作序列。,Algorithm is the operation sequence for solving problem,For example,：求两个正整数,m,，,n,中的最大数,MAX,的算法,若,m n,则,max=m ,若,m n then,max=m if,m=n then,max=n,求正整数,m,，,n,中的最大数的算法,Characteristic of algorithms,：,1,Finiteness,对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在,有限时间,内完成。,2,Doubtlessness,对,于每种情况下所应执行的操作，在算法中都有确切的规定。读者不会产生,二义性,。,3,feasibility,算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之。,4,input,任何算法都有输入，有些在程序运行过程当中需要输入数据，有些虽然没有输入，但其实已经把输入嵌入了算法当中,5,output,。,What is a good algorithm?,1 correctness:,火车站怎么走 往北,2 readability:,易于人的阅读和理解,多个人合作软件时候。,3 robustness:,输入数据非法时候，算法能做出相应反应。,4 high Efficiency,：,Time and Space,效率指算法的执行时间，存储量是执行算法所需要最大存储空间。,1.4,算法和算法的分析,三、,Description of algorithms,There are several common methods to describe algorithms as follows:,Natural Language,P,seudocode,P,rogramming language,Flow Chart,Pseudocode based on C+language is used to describe algorithms in our text book.,本书采用基于,C+,语言的伪代码来描述。,There are two method to measure the execution time of a program,Estimate in advance,Test after the events,1,事后统计的方法,缺点：,必须先运行依据算法编制的程序,所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣,四、,Mea