计算机基础C语言数据结构.ppt

第3章 算法与数据结构 3.1 计算机的问题求解模型 3.2 C语言基础 3.3 算法与数据结构的基本概念 3.4 线性结构 3.5 多维数组和广义表 3.6 树 3.7 图 3.8 查找 3.9 排序 3.10 文件 3.1 计算机的问题求解模型 本节内容： 3.1.1 计算机求解问题的过程 3.1.2 求解过程的概化－－算法 3.1.3 求解过程的实现－－程序 3.1.1 计算机求解问题的过程 有人认为计算机是万能的，只要把任务交给计算机，计算机就会自动完成一切，并且给出正确结果，其实这是一种误解。 计算机对问题的解决，实际上只是按照人们所指定的操作步骤工作的。 从人们拿到一个计算任务，到得到正确的结果，要经过下述的几个阶段的工作，其中的任何阶段出现问题，都会影响到结果的正确性。 (1) 分析问题 (2) 确定处理方案 (3) 设计处理步骤和数据结构 (4) 编写程序代码 (5) 调 试程序和结果检验 (6) 整理结果 3.1.2 求解过程的概化－－算法 当数据处理方案确定以后，算法的选择和设计是问题求解中很重要的一步。 所谓算法，就是问题求解的步骤设计。 (1) 算法的选择： 一个问题的求解，往往有多种方法。不同的方法之间，从处理的效率、结果的精度到程序设计人员的工作量、数学模型的难易程序都有很大的差别。这时就要权衡利弊得失，选择一种最为满意的算法。 (2) 对算法的描述： 可以选择自然语言、流程图、N－S图等多种方法描述算法。在算法的描述过程中应该注意以下几点： (a) 按问题的处理前后顺序描述。 (b) 描述要简明、准确，不能存在二义性的描述。 (c) 在详细的算法描述中，要充分考虑到任何处理细节。 (d) 要考虑到问题处理过程中任何可能发生的情况。 (e) 算法中的运算和处理应能够在有限的时间内结束。 (f) 对于采用模块化设计。模块的划分采用从上向下的顺序逐步细化。 3.1.2 求解过程的概化－－算法 下面看一个求解一元二次方程的根的算法设计过程： (1) 通过自然语言描述算法如下： (a) 输入方程的系数a、b和c； (b) 计算d＝b2-4ac； (c) 如果d小于0，转(g)； (d) 计算两个实根 x1=(-b+sqrt(d))/(2a)和x2=(-b+sqrt(d))/(2a)； (e) 输出两个实根x1和x2； (f) 转(i)； (g) 计算两个复根的实部u=-b/(2a) 和虚部v=sqrt(-d)/(2a)； (h) 输出两个复根x1=u+vi和x2=u-vi； (i ) 停止程序执行。 3.1.2 求解过程的概化－－算法 (2) 通过流程图描述算法如下： 3.1.3 求解过程的实现－－程序 算法的实现只是问题解决的一个步骤，将算法用程序代码描述出来，并且输入到计算机中，让计算机按照设计好的程序完成指定的工作并且得到我们想要的结果，才是我们的目的之所在。 程序（Program）是指用某一种计算机语言编写的计算机可以直接或间接执行的代码序列。 如何才能将算法转换成计算机可能执行的程序呢？ 1. 计算机语言的分类和执行方式 2. 如何用计算机语言描述算法 3. 程序的调试与修改 3.1.3 求解过程的实现－－程序 1. 计算机语言的分类和执行方式 使用某一种语言编程时，这种语言的支持软件、编译程序或解释程序、内部库函数、用户支持环境、各种设计工具以及与编程和程序运行有关的软件，就构成了这种语言的程序设计环境。 程序设计语言可以分为以下三类： (1)机器语言 机器语言（Machine language）是一种面向计算机的程序设计语言，用它所设计的程序是一系列的指令。 计算机的CPU可以直接执行机器语言程序，这种程序称为目标程序（Object program）。 目标程序手工编写非常因难，需要编程者熟悉CPU的指令系统，熟悉CPU的内部结构。另外，机器语言作为面向机器的语言，在不同类型的处理器之间差别很大，即机器语言程序的可移植性较差。 机器语言程序直接用二