文档介绍：第4章算法与数据结构16学时算法与数据结构目的与要求:掌握算法与算法设计基本方法掌握数据结构的表示与基本操作重点与难点: (表、树、图) 2学时本章内容2学时算法历史小知识算法的中文名称出自周髀算经;-Khwarizmi,。他写的书《al-jabrw’almuqabalah》(代数学)演变成为现在中学的代数教科书。Ad-Khwarizmi强调求解问题是有条理的步骤。如果他能活到今天的话,他一定会被以他的名字而得名的方法的进展所感动。“算法”原为“algorism”,意思是阿拉伯数字的运算法则,在18世纪演变为“algorithm”。第一次编写算法是AdaByron于1842年为巴贝奇分析机编写求解解伯努利方程的程序,因此AdaByron被大多数人认为是世界上第一位程序员。20世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,,是解题过程的精确描述。算法是由若干条指令组成的有穷序列。即由有限条可完全执行的,有确切含义的指令(或命令,语句)所构成。算法通俗说法算法严格说法算法五大特征有穷性一个算法必须总是在执行有穷步后结束, 且每一步都可在有穷时间内完成;确定性算法中的每一个指令比须有明确的含义, 不能有二义性;可行性算法中描述的操作都是可通过已经实现的 基本运算、执行有限次实现的;输入一个算法应有0个或多个输入;输出一个算法应有1个或多个输出。算法的表示自然语言流程图特定的表示算法的图形符号伪语言包括程序设计语言的三大基本结构及自然语言的一种语言类语言类似高级语言的表示,例如类PASCAL、 类C语言算法的描述插入排序Insertion-Sort(A)1 forj=1ton-12 key=A[j]3 i=j-14 whilei>=0andA[i]>key5 A[i+1]=A[i]6 i=i-17 A[i+1]=keyj=1j=2j=3j=4j=5245613245613245663245563244563224563124563A[0]A[1]A[2]A[3]A[4]A[5]算法的分析与评价1)正确性(Correctness)2)可读性(Readability)3)健壮性(robustness)4)高效率与低存储量算法的评价标准应具有容错处理功能。当输入非法数据时,算法应对其作出反应,而不是产生莫名其妙的输出结果。处理速度快;存储容量小。时间和空间是矛盾的、实际问题的求解往往是求得时间和空间的统一、折中。算法的第一目的是为了阅读和交流;可读性有助于对算法的理解;可读性有助于对算法的调试和修改。程序不含语法错误;程序对几组输入数据程序对精心选择的、典型的、苛刻的、带有刁难性的几组输入数据;程序对一切合法的输入数据能产生满足规格要求的结果