文档介绍：第一章数据结构与算法全国计算机二级考试之公共基础知识 2 前一页下一页休息本章主要内容?算法概述?数据结构?线性表及其顺序存储结构?栈和队列?线性链表?树与二叉树?查找技术?排序技术算法算法的定义算法的设计算法的表示算法的评价 4 前一页下一页休息算法和程序?程序设计?是利用计算机解决问题的全过程?程序设计的过程: 分析抽象分析分析抽象抽象模型求解模型模型求解求解命令编程命令命令编程编程调试程序调试调试程序程序实际问题问题模型求解算法编制程序问题实现问题分析算法设计编程设计测试执行 5 前一页下一页休息计算机求解问题的步骤 1)确定并理解问题; 2)寻找解决问题的方法与步骤,并将其表示成算法(Algorithm) ; 3)使用某种程序设计语言描述该算法(编程), 并进行调试; 4)运行程序,获得问题的解答; 5)进行评估,改进算法和程序算法 6 前一页下一页休息算法和程序?程序设计的第一步是问题分析?问题分析?问题一:统计一个班级的学生考试成绩, 并选出优秀学生?多少科目的成绩? ?优秀的定义(总分?平均分?第一名?前五名?) ?数据如何录入?如何输出? ?这是初学者认为最简单而在实际工程中最难的工作。在软件工程中被称作“需求分析” 7 前一页下一页休息算法和程序?算法设计?算法的概念?要使计算机完成某一问题的解题任务,首先必须针对该问题设计一个解题步骤,然后再据此编写程序。这里所说的解题步骤就是“算法”。?算法与程序不同,它是问题求解规则的一种过程描述。在算法中要精确定义一系列规则,这些规则指定了相应的操作顺序,以便在有限的步骤内得到所求问题的解答。 8 前一页下一页休息算法定义?算法-解决问题的方法和步骤?例:有三个硬币,其中一个是伪造的,另两个是真的,伪币与真币重量略有不同。现在提供一座天平, 如何找出伪币呢? ?分析: ?方法明确而有序?按提供的条件进行操作?任何人均可仿照进行(共享智能)算法开始 C是伪币 B是伪币 A是伪币 A=B? A=C? 是否否是9 前一页下一页休息算法和程序?算法无处不再?例1: Word 如何在文档中查找用户指定的词语? ?例2: EXCEL 中如何将表格内容排序? ?例3:如何把彩色图片转换为灰度(黑白)图片? ?例4:如何在硬盘中找到用户指定的文件? ?例5:媒体播放器如何把 MP3 文件转换成动听的音乐? ?例6:搜索引擎如何找到用户需要的网页? 算法 10 前一页下一页休息算法的通用性?算法所解决的是一类问题而不是一个特定的问题,例如?排序(sort) : ?包括表格内容的排序,文件夹中文件的排序等?排序方式也可以按数字、文字或日期等排序?查找(search) : ?可以在文档中查找某个单词或在硬盘中查找某个文件, 也可在 Web 上查找某个网页等等?开发计算机应用的核心是:根据实际问题给出解题的算法,然后再将该算法在计算机上实现(即开发成为软件)算法