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