程序设计基础2.ppt

第第5 5章章 程序设计基础程序设计基础 主讲教师 郭松涛主讲教师 郭松涛 EmailEmail： 本章教学计划本章教学计划 理论教学（课堂教学）：理论教学（课堂教学）：4 4学时学时 实验教学（上机实习）：实验教学（上机实习）：2 2学时学时 本章教学重点本章教学重点 1. 1. 程序的翻译方式程序的翻译方式 2. 2. 算法描述及数据结构算法描述及数据结构 3. 3. 程序设计基本过程程序设计基本过程 4. 4. 程序设计基本思想程序设计基本思想 第第 5 5 章 程章 程 序序 设设 计计 基基 础础 本章首先介绍程序设计语言的基本知识 本章首先介绍程序设计语言的基本知识 ，包括程序设计语言的发展、分类及程序的，包括程序设计语言的发展、分类及程序的 3 3种翻译方式，然后介绍算法与数据结构的种翻译方式，然后介绍算法与数据结构的 基本知识，程序设计的基本过程以及程序设基本知识，程序设计的基本过程以及程序设 计的基本思想。计的基本思想。 第第 5 5 章 程章 程 序序 设设 计计 基基 础础 5.15.1 程序设计语言概述程序设计语言概述 5.25.2 算法与数据结构算法与数据结构 5.35.3 程序设计基本过程程序设计基本过程 5.4 5.4 程序设计的基本思想程序设计的基本思想 第第 5 5 章 程章 程 序序 设设 计计 基基 础础 5.1 5.1 程序设计语言概述程序设计语言概述 .1 程序设计语言的发展 程序设计语言的发展 程序是程序设计中最基本的概念， 程序是程序设计中最基本的概念，“程序程序”一词来一词来 自生活，通常指完成某些事务的一种既定方式和过程。自生活，通常指完成某些事务的一种既定方式和过程。 程序在计算机发明之前很久就有了，例如，食谱、乐谱程序在计算机发明之前很久就有了，例如，食谱、乐谱 、工作步骤等都是程序，泛指得到一个结果需要的步骤、工作步骤等都是程序，泛指得到一个结果需要的步骤 ，比如演出节目单、课程表等。，比如演出节目单、课程表等。 计算机程序是对计算任务的处理对象和处理规则的 计算机程序是对计算任务的处理对象和处理规则的 描述。任何以计算机为处理工具的任务都是计算任务；描述。任何以计算机为处理工具的任务都是计算任务； 而处理对象指数据，如数字、文字、图像、声音等多媒而处理对象指数据，如数字、文字、图像、声音等多媒 体以及诸如温度、电压等物理状态；处理规则指处理动体以及诸如温度、电压等物理状态；处理规则指处理动 作和步骤。计算机程序由计算机语言进行描述。作和步骤。计算机程序由计算机语言进行描述。 5.1 5.1 程序设计语言概述程序设计语言概述 .1 程序设计语言的发展 程序设计语言的发展 在过去的几十年里，人们根据描述问题的需要而设计 在过去的几十年里，人们根据描述问题的需要而设计 了数千种专用的和通用的计算机语言，据不完全统计大约了数千种专用的和通用的计算机语言，据不完全统计大约 有有2 5002 500种，绝大多数是高级语言，通过网址：种，绝大多数是高级语言，通过网址： //nkinners/LangList/Extras/langlist.htmnkinners/LangList/Extras/langlist.htm 可以看到其列表和简介，另外：可以看到其列表和简介，另外： /lang//lang/ 搜集了大约搜集了大约5050种极具代表性的语言的故事和资料，其中，种极具代表性的语言的故事和资料，其中， 有的语言是为了编写系统软件而重在提高效率，如有的语言是为了编写系统软件而重在提高效率，如C C语言等语言等 ；有的语言是为了提高程序设计速度，面向商业应用，如；有的语言是为了提高程序设计速度，面向商业应用，如 COBOLCOBOL等；还有些语言是用于教学，如等；还有些语言是用于教学，如BASICBASIC等。这些语言等。这些语言 中只有少部分得到了比较广泛的应用，其中影响最大、寿中只有少部分得到了比较广泛的应用，其中影响最大、寿 命最长的是命最长的是C C语言。语言。 5.1 5.1 程序设计语言概述程序设计语言概述 .1 程序设计语言的发展 程序设计语言的发展 程序设计语言的发展大致经历了代。 程序设计语言的发展大致经历了代。 1) 1) 第第1 1代语言（大约从代语言（大约从19461946年开始）年开始） 第 第1 1代程序设计语言是由代程序设计语言是由“0”“0”和和“1”“1”这样的二进制编码这样的二进制编码 指令组表示的，通常称为机器语言，是能够被计算机直接接指令组表示的，通常称为机器语言，是能够被计算机直接接 受和执行的计算机语言。受和执行的计算机语言。 2 2）第）第2 2代语言（大约从代语言（大约从19501950年早期开始）年早期开始） 为了让用机器语言编写的程序更易理解，程序员使用了 为了让用机器语言编写的程序更易理解，程序员使用了 一种类似英语缩略词且带有助记性符号的语言，例如一种类似英语缩略词且带有助记性符号的语言，例如addadd、 sub(subtract)sub(subtract)和和loadload等，这种语言被称为汇编语言。这种语等，这种语言被称为汇编语言。这种语 言与特定的机器和言与特定的机器和CPUCPU指令集有关，而且不能被机器直接接受指令集有关，而且不能被机器直接接受 ，必须用一种翻译器将程序中的每条语句翻译成机器语言。，必须用一种翻译器将程序中的每条语句翻译成机器语言。 5.1 5.1 程序设计语言概述程序设计语言概述 .1 程序设计语言的发展 程序设计语言的发展 3 3）第）第3 3代语言（大约从代语言（大约从19501950年中期开始）年中期开始） 第 第3 3代语言称为高级语言，因为它更接近自然语言。第代语言称为高级语言，因为它更接近自然语言。第3 3代代 语言是过程化的，每一条语句一般被编译成语言是过程化的，每一条语句一般被编译成5 51010条机器代码指条机器代码指 令，编写的程序容易理解、容易维护，具有很强的进程能力和令，编写的程序容易理解、容易维护，具有很强的进程能力和 数据结构能力。这类语言在数据结构能力。这类语言在19701970年以后，提出了结构化的程序年以后，提出了结构化的程序 控制，进一步规范了程序设计方法。控制，进一步规范了程序设计方法。 4 4）第）第4 4代语言（大约从代语言（大约从2020世纪世纪8080年代开始）年代开始） 第 第4 4代语言（代语言（4GL4GL）称为超高级语言，是非过程化语言。这）称为超高级语言，是非过程化语言。这 类语言的一条语句一般被编译成类语言的一条语句一般被编译成30305050条机器代码，进一步提条机器代码，进一步提 高了编码效率，并使程序更易理解、更易维护。第高了编码效率，并使程序更易理解、更易维护。第4 4代语言包括代语言包括 很宽范围的软件工具，如数据库查询、报表生成、数据处理、很宽范围的软件工具，如数据库查询、报表生成、数据处理、 屏幕交互和定义、代码生成、高级图形以及表格处理等。屏幕交互和定义、代码生成、高级图形以及表格处理等。 5.1 5.1 程序设计语言概述程序设计语言概述 .2 程序设计语言的分类 程序设计语言的分类 ）低级语言）低级语言 低级语言主要是机器语言和汇编语言。它的特点是与特 低级语言主要是机器语言和汇编语言。它的特点是与特 定的机器有关，功效高，但使用复杂、难记忆、难书写、编定的机器有关，功效高，但使用复杂、难记忆、难书写、编 程困难、可读性差、易出差错，可移植性极差。程困难、可读性差、易出差错，可移植性极差。 机器语言是表示成数码形式的机器基本指令集，或者是 机器语言是表示成数码形式的机器基本指令集，或者是 操作码经过符号化的基本指令集，是计算机能直接执行的指操作码经过符号化的基本指令集，是计算机能直接执行的指 令集。令集。 汇编语言是为了克服机器语言的缺点，用助记码和符号 汇编语言是为了克服机器语言的缺点，用助记码和符号 地址代替机器指令中的操作码和操作数，是机器语言符号化地址代替机器指令中的操作码和操作数，是机器语言符号化 的结果。但计算机不能直接执行汇编语言程序，必须要用汇的结果。但计算机不能直接执行汇编语言程序，必须要用汇 编程序翻译成机器指令后才能在计算机上执行，同时汇编语编程序翻译成机器指令后才能在计算机上执行，同时汇编语 言比机器语言好理解，比其他高级语言执行效率高。言比机器语言好理解，比其他高级语言执行效率高。 5.1 5.1 程序设计语言概述程序设计语言概述 .2 程序设计语言的分类 程序设计语言的分类 ）高级语言）高级语言 高级语言的表示方法要比低级语言更接近于待解问题的 高级语言的表示方法要比低级语言更接近于待解问题的 表示方法，大量引入数学表示形式，其特点是与具体机器无表示方法，大量引入数学表示形式，其特点是与具体机器无 关，易学、易用、易维护、易移植，但计算机不能直接执行关，易学、易用、易维护、易移植，但计算机不能直接执行 ，需要翻译工具。一般说来，当高级语言程序翻译成相应的，需要翻译工具。一般说来，当高级语言程序翻译成相应的 低级语言程序时，一个高级语言程序单位要对应多条机器指低级语言程序时，一个高级语言程序单位要对应多条机器指 令，相应的编译程序所产生的目标程序往往效率较低。令，相应的编译程序所产生的目标程序往往效率较低。 第一个高级程序设计语言第一个高级程序设计语言FORTRAN (Formula Translation)FORTRAN (Formula Translation) 公式翻译程序设计语言，是由美国计算机科学家约翰公式翻译程序设计语言，是由美国计算机科学家约翰巴巴 克斯（克斯（John BackusJohn Backus）领导的小组于）领导的小组于1954195719541957年间，在年间，在IBMIBM 公司的公司的704704系列计算机上开发的。系列计算机上开发的。FORTRANFORTRAN一直被选作为科学一直被选作为科学 和工程的计算语言。和工程的计算语言。 5.1 5.1 程序设计语言概述程序设计语言概述 .2 程序设计语言的分类 程序设计语言的分类 ）高级语言）高级语言 C C语言于语言于1969197319691973年产生，它是年产生，它是BCPL(Basic Combined BCPL(Basic Combined Programming Language)Programming Language)和和B B语言的后继，故取名语言的后继，故取名C C语言。语言。C C语语 言是第一个成功实现系统软件开发的高级语言，是一种受到言是第一个成功实现系统软件开发的高级语言，是一种受到 专业程序员欢迎的程序语言，它由贝尔电话实验室的专业程序员欢迎的程序语言，它由贝尔电话实验室的Dennis Dennis M.RitchieM.Ritchie在在PDPPDP 1111计算机上首先实现，并用它重写了计算机上首先实现，并用它重写了UNIXUNIX操操 作系统。从那时起，操作系统和作系统。从那时起，操作系统和C C语言的关系就紧密联系起来语言的关系就紧密联系起来 了。了。C C语言是很简洁的语言，例如，语言是很简洁的语言，例如，PascalPascal中用中用beginbegin和和endend来来 定义语句块，而在定义语句块，而在C C语言中用来代替。语言中用来代替。C C语言支持移位操语言支持移位操 作和按位逻辑操作等作和按位逻辑操作等CPUCPU的基本指令。另外，的基本指令。另外，C C语言还支持指语言还支持指 针，指针实质上是符号化的内存地址。针，指针实质上是符号化的内存地址。C C语言支持多种数据结语言支持多种数据结 构，具有很高的可移植性。构，具有很高的可移植性。 5.1 5.1 程序设计语言概述程序设计语言概述 .3 程序的 程序的3 3种翻译方式种翻译方式 只有用机器语言编写的程序才能被计算机直接执行， 只有用机器语言编写的程序才能被计算机直接执行， 而其他任何语言编写的程序都需要通过中间的翻译过程，而其他任何语言编写的程序都需要通过中间的翻译过程， 用语言处理程序翻译成机器语言程序。用语言处理程序翻译成机器语言程序。 语言处理程序是指把较高级语言的程序等价转换为较 语言处理程序是指把较高级语言的程序等价转换为较 低级语言程序的系统程序。一般将程序设计语言编写的程低级语言程序的系统程序。一般将程序设计语言编写的程 序称为序称为“源程序源程序”；源程序经过语言处理程序产生的结果；源程序经过语言处理程序产生的结果 称为称为“目标程序目标程序”；由机器指令组成的、可以直接在；由机器指令组成的、可以直接在CPUCPU中中 执行并得到运行结果的程序称为执行并得到运行结果的程序称为“可执行程序可执行程序”。常见的。常见的 语言处理程序有语言处理程序有汇编程序、编译程序和解释程序汇编程序、编译程序和解释程序。 如高级语言 如高级语言FORTRANFORTRAN、COBOLCOBOL、PASCALPASCAL、C C等都是编译型等都是编译型 语言，而语言，而LISPLISP、BASICBASIC等都是解释型语言。等都是解释型语言。 5.1 5.1 程序设计语言概述程序设计语言概述 ）汇编程序）汇编程序 汇编程序又称汇编系统，它的功能是将汇编语 汇编程序又称汇编系统，它的功能是将汇编语 言程序翻译成机器语言程序。由于汇编语言的指令言程序翻译成机器语言程序。由于汇编语言的指令 与机器语言的指令基本保持了一一对应关系，所以与机器语言的指令基本保持了一一对应关系，所以 汇编的过程比较简单，效率非常高。汇编的基本步汇编的过程比较简单，效率非常高。汇编的基本步 骤如下：骤如下： 将指令助记符转换为机器操作码。将指令助记符转换为机器操作码。 将符号操作数转换为地址码。将符号操作数转换为地址码。 将操作码和操作数构成机器指令。将操作码和操作数构成机器指令。 汇编程序是为特定的 汇编程序是为特定的CPUCPU指令系统设计的，因此指令系统设计的，因此 没有互换性。不同的没有互换性。不同的CPUCPU指令集有不同的汇编程序。指令集有不同的汇编程序。 5.1 5.1 程序设计语言概述程序设计语言概述 2 2）编译程序）编译程序 编译程序又称为编译系统，它的主要功能是将高级语言 编译程序又称为编译系统，它的主要功能是将高级语言 编写的程序翻译成等效的机器语言程序，以便直接运行程序编写的程序翻译成等效的机器语言程序，以便直接运行程序 。编译程序主要执行下列步骤：。编译程序主要执行下列步骤： 编译 首先把源程序编译成等效的汇编代码，然后再编译 首先把源程序编译成等效的汇编代码，然后再 由汇编程序将汇编代码翻译成可重新定位的目标程序，目标由汇编程序将汇编代码翻译成可重新定位的目标程序，目标 程序是由浮动的机器语言程序模块和相关的信息表所组成，程序是由浮动的机器语言程序模块和相关的信息表所组成， 连接 将若干可重新定位的目标程序连接在一起，构连接 将若干可重新定位的目标程序连接在一起，构 成一个完整的可重新定位的目标程序。成一个完整的可重新定位的目标程序。 加载 将完整的可重新定位的目标程序装入主存储器加载 将完整的可重新定位的目标程序装入主存储器 中，并对目标程序重新定位，成为可在机器上直接执行的机中，并对目标程序重新定位，成为可在机器上直接执行的机 器语言程序。器语言程序。 5.1 5.1 程序设计语言概述程序设计语言概述 ）解释程序）解释程序 解释程序又称解释系统。所谓解释实际上是对源程序的 解释程序又称解释系统。所谓解释实际上是对源程序的 每一可能的行为，都以机器语言编写一个子程序，用来模拟每一可能的行为，都以机器语言编写一个子程序，用来模拟 这一行为。因此对高级语言程序的解释，实际上是调用一系这一行为。因此对高级语言程序的解释，实际上是调用一系 列的子程序来完成的。列的子程序来完成的。 解释程序重复执行下列步骤：解释程序重复执行下列步骤： 取下一个语句。取下一个语句。 确定被执行的活动。确定被执行的活动。 执行这一活动。执行这一活动。 解释程序按源程序中语句的动态顺序逐句进行分析翻译 解释程序按源程序中语句的动态顺序逐句进行分析翻译 ，并调用子程序执行程序功能，不产生目标程序。同编译程，并调用子程序执行程序功能，不产生目标程序。同编译程 序相比，解释程序的本身编写较容易，但解释程序的执行效序相比，解释程序的本身编写较容易，但解释程序的执行效 率比编译程序要低得多。率比编译程序要低得多。 5.1 5.1 程序设计语言概述程序设计语言概述 编译过程编译过程解释过程解释过程 5.15.1 程序设计语言概述程序设计语言概述 5.25.2 算法与数据结构算法与数据结构 5.35.3 程序设计基本过程程序设计基本过程 5.4 5.4 程序设计的基本思想程序设计的基本思想 第第 5 5 章 程章 程 序序 设设 计计 基基 础础 5.2 5.2 算法与数据结构算法与数据结构 .1 什么是算法 什么是算法 人类求解问题通常有 人类求解问题通常有2 2种方式：一种是推理方式，另一种种方式：一种是推理方式，另一种 是算法方式。推理方式是从已知的定理、公理系统出发，一是算法方式。推理方式是从已知的定理、公理系统出发，一 步一步地推理，用数学演绎的方法，推导出问题的解答；算步一步地推理，用数学演绎的方法，推导出问题的解答；算 法方式则是法方式则是“构造构造”出一个基本操作的序列，按照一定的顺出一个基本操作的序列，按照一定的顺 序，经过一步一步地序，经过一步一步地“机械机械”执行操作的过程，得到问题的执行操作的过程，得到问题的 解答。算法方式特别适合计算机求解问题。解答。算法方式特别适合计算机求解问题。 ) )算法的基本概念算法的基本概念 一个问题经过适当说明和分析之后，必须建立一个能够 一个问题经过适当说明和分析之后，必须建立一个能够 在计算机上求解的操作序列，这个操作序列就是算法，或者在计算机上求解的操作序列，这个操作序列就是算法，或者 说，在程序中对数据实施的操作即是算法。比较精确完整的说，在程序中对数据实施的操作即是算法。比较精确完整的 定义是：算法是一个过程，这个过程由一组清楚的规则所组定义是：算法是一个过程，这个过程由一组清楚的规则所组 成，这些规则指定了一个操作顺序，以便用有限的步骤，提成，这些规则指定了一个操作顺序，以便用有限的步骤，提 供对特定类型问题的解答。供对特定类型问题的解答。 5.2 5.2 算法与数据结构算法与数据结构 一般来说，在求解一个问一般来说，在求解一个问 题时，一个高质量的算法题时，一个高质量的算法 设计出来后，将其转换为设计出来后，将其转换为 对应的程序代码是一件非对应的程序代码是一件非 常容易的事情常容易的事情 5.2 5.2 算法与数据结构算法与数据结构 2)2)算法的基本特征算法的基本特征 一个在计算机上实现的算法必须同时满足以下 一个在计算机上实现的算法必须同时满足以下5 5个重要特个重要特 性。性。 有穷性有穷性 一个算法必须能够在算法所涉及的每一种情况 一个算法必须能够在算法所涉及的每一种情况 下，都能在执行有穷步操作之后结束。算法的有穷性特征是下，都能在执行有穷步操作之后结束。算法的有穷性特征是 算法和计算方法之间最明显的区别，例如求正弦函数值的公算法和计算方法之间最明显的区别，例如求正弦函数值的公 式：式： 没有表示出计算到何时为止，所以这样的描述只是计算方法没有表示出计算到何时为止，所以这样的描述只是计算方法 而不是算法。当以某种方式表述了计算到多少项为止的时候而不是算法。当以某种方式表述了计算到多少项为止的时候 （例如，某一项的绝对值小于（例如，某一项的绝对值小于1010-5 -5时停止计算）才能称之为 时停止计算）才能称之为 算法。算法。 5.2 5.2 算法与数据结构算法与数据结构 2)2)算法的基本特征算法的基本特征 确定性确定性 对于每种情况应该执行的操作，在算法中 对于每种情况应该执行的操作，在算法中 都有确切的规定，使算法的执行者或阅读者都能明确都有确切的规定，使算法的执行者或阅读者都能明确 其含义及如何执行；在任何条件下，算法都只有一条其含义及如何执行；在任何条件下，算法都只有一条 执行路径，不能有任何歧义，无论使用何种符号、何执行路径，不能有任何歧义，无论使用何种符号、何 种数据、何种操作都必须保证其唯一确定的意义。种数据、何种操作都必须保证其唯一确定的意义。 有效性有效性 算法所描述的每一步操作都必须是可行的 算法所描述的每一步操作都必须是可行的 ，即必须是可以付诸实施并能够具体实现的基本操作，即必须是可以付诸实施并能够具体实现的基本操作 。例如，若。例如，若b=0b=0，则执行，则执行a/ba/b是不能有效执行的。是不能有效执行的。 有输入有输入（有零个或多个输入数据）（有零个或多个输入数据） 有输出有输出（有一个或多个输出数据）（有一个或多个输出数据） 5.2 5.2 算法与数据结构算法与数据结构 3)3)算法的基本结构算法的基本结构 由于需要解决的问题是各种各样的，所以算法的构造 由于需要解决的问题是各种各样的，所以算法的构造 是千变万化的，其形式也是千姿百态的。但算法的最基本是千变万化的，其形式也是千姿百态的。但算法的最基本 的组成形式和构造成分只有的组成形式和构造成分只有3 3种基本结构，任何复杂的算法种基本结构，任何复杂的算法 都是这都是这3 3种基本结构的组合，这种基本结构的组合，这3 3种基本结构是种基本结构是顺序结构、顺序结构、 选择（分支）结构、循环结构选择（分支）结构、循环结构。 5.2 5.2 算法与数据结构算法与数据结构 4)4)算法设计的原则算法设计的原则 设计算法时，通常应考虑达到以下目标： 设计算法时，通常应考虑达到以下目标： （1 1）正确性）正确性 程序中不含语法错误。程序中不含语法错误。 程序对于几组输入数据能够得出满足要求的结果。程序对于几组输入数据能够得出满足要求的结果。 程序对于精心选择的、典型的、苛刻而带有刁难性的几程序对于精心选择的、典型的、苛刻而带有刁难性的几 组输入数据能够得出满足要求的结果。组输入数据能够得出满足要求的结果。 程序对于一切合法的输入数据都能得出满足要求的结果程序对于一切合法的输入数据都能得出满足要求的结果 。通常以第。通常以第3 3层意义的正确性作为衡量一个算法是否合格的标准层意义的正确性作为衡量一个算法是否合格的标准 。（2 2）可读性）可读性 （3 3）健壮性）健壮性 （4 4）高效率与低存储量）高效率与低存储量 5.2 5.2 算法与数据结构算法与数据结构 .2 算法的描述方法 算法的描述方法 人的思想需要用各种自然语言来表达，算法也是 人的思想需要用各种自然语言来表达，算法也是 一样，需要用各种形式来表示。除自然语言外，常用一样，需要用各种形式来表示。除自然语言外，常用 于描述算法的工具有程序流程图、盒图（于描述算法的工具有程序流程图、盒图（NSNS图）和图）和 伪代码等。伪代码等。 ）用自然语言描述算法）用自然语言描述算法 用自然语言描述算法通俗易懂，如例 用自然语言描述算法通俗易懂，如例5.15.1和例和例5.25.2 。但是，自然语言具有二义性，容易产生歧义，且语。但是，自然语言具有二义性，容易产生歧义，且语 句冗长，不够精炼，此外，对算法的循环、选择等控句冗长，不够精炼，此外，对算法的循环、选择等控 制结构也难以表示清楚，因此，除了特别简单的问题制结构也难以表示清楚，因此，除了特别简单的问题 ，一般不用自然语言表示算法。，一般不用自然语言表示算法。 5.2 5.2 算法与数据结构算法与数据结构 自然语言描述自然语言描述 算法算法 5.2 5.2 算法与数据结构算法与数据结构 2 2）用程序流程图描述算法）用程序流程图描述算法 程序流程图简称流程图，又称程序框图，使用一 程序流程图简称流程图，又称程序框图，使用一 些图形符号来表示算法中的各个执行或判断过程，使些图形符号来表示算法中的各个执行或判断过程，使 用流程线（有向线段）来表示算法执行中每一个步骤用流程线（有向线段）来表示算法执行中每一个步骤 在执行上的时间顺序，如图在执行上的时间顺序，如图5.25.2所示。所示。 5.2 5.2 算法与数据结构算法与数据结构 用流程框图表示用流程框图表示 程序的种结构程序的种结构 5.2 5.2 算法与数据结构算法与数据结构 求和算法的流程求和算法的流程 图描述图描述 5.2 5.2 算法与数据结构算法与数据结构 .2 算法的描述方法 算法的描述方法 ）用）用NSNS图描述算法图描述算法 NSNS图与程序流程图的主要区别在于去掉图与程序流程图的主要区别在于去掉 了程序流程图中的流程线，全部算法写在一个了程序流程图中的流程线，全部算法写在一个 矩形框内，在该框内还可以包含其他从属于它矩形框内，在该框内还可以包含其他从属于它 的框，利用的框，利用NSNS图表示算法就像堆积木一样，图表示算法就像堆积木一样， 它十分适合结构化程序设计。解决了使用程序它十分适合结构化程序设计。解决了使用程序 流程图容易设计出非结构化算法的问题，强制流程图容易设计出非结构化算法的问题，强制 算法设计者使用结构化程序设计思想。算法设计者使用结构化程序设计思想。 5.2 5.2 算法与数据结构算法与数据结构 N-SN-S图表示的程图表示的程 序种结构序种结构 求和算法的求和算法的N-SN-S 图表示图表示 5.2 5.2 算法与数据结构算法与数据结构 ）用伪代码描述算法）用伪代码描述算法 用程序流程图或 用程序流程图或NSNS图来描述算法虽然形象直观，图来描述算法虽然形象直观， 但在算法设计过程中使用起来并不十分方便，画图时很但在算法设计过程中使用起来并不十分方便，画图时很 费事，特别是当算法稍微复杂一点时，不易修改。费事，特别是当算法稍微复杂一点时，不易修改。 在实际的算法设计中，为了清晰方便地描述算法， 在实际的算法设计中，为了清晰方便地描述算法， 常常使用自然语言或计算机语言或类计算机语言来描述常常使用自然语言或计算机语言或类计算机语言来描述 。这里的类计算机语言是一种非计算机语言，借用了一。这里的类计算机语言是一种非计算机语言，借用了一 些高级语言的某些成分，没有加入严格的规则，而且不些高级语言的某些成分，没有加入严格的规则，而且不 能够被计算机所接受，称其为能够被计算机所接受，称其为“伪代码伪代码”。其功能是使。其功能是使 程序员像使用英语或汉语那样，非常自然地表达程序逻程序员像使用英语或汉语那样，非常自然地表达程序逻 辑的思想，以便集中精力考虑解题算法而不受形式上的辑的思想，以便集中精力考虑解题算法而不受形式上的 约束。约束。 5.2 5.2 算法与数据结构算法与数据结构 伪代码法表示的伪代码法表示的 程序种结构程序种结构 5.2 5.2 算法与数据结构算法与数据结构 伪代码法描述求伪代码法描述求 和算法和算法 5.2 5.2 算法与数据结构算法与数据结构 伪代码法描述选伪代码法描述选 择计算算法择计算算法 5.2 5.2 算法与数据结构算法与数据结构 .3 算法与数据结构的关系 算法与数据结构的关系 一个程序应该包含 一个程序应该包含2 2个方面的内容：一是程序要处个方面的内容：一是程序要处 理的对象，人们用数据和数据之间的关系来表示，即理的对象，人们用数据和数据之间的关系来表示，即 数据结构；二是对这些对象的处理方法，即操作步骤数据结构；二是对这些对象的处理方法，即操作步骤 ，人们用算法来描述。著名计算机科学家沃思（，人们用算法来描述。著名计算机科学家沃思（ Niklaus WirthNiklaus Wirth）提出了一个公式：）提出了一个公式： 程序程序 = = 数据结构数据结构 + + 算法算法 诠释了程序设计中的本质，揭示了算法与数据结 诠释了程序设计中的本质，揭示了算法与数据结 构的关系。构的关系。 5.2 5.2 算法与数据结构算法与数据结构 1 1）数据结构的定义）数据结构的定义 数据与数据之间彼此的相互关系称为结构。为了进一步理解 数据与数据之间彼此的相互关系称为结构。为了进一步理解 什么是数据结构，我们来看一个具体的例子：图书馆是大家所熟什么是数据结构，我们来看一个具体的例子：图书馆是大家所熟 悉的，一本图书由书名、作者、出版社等数据来描述，根据需要悉的，一本图书由书名、作者、出版社等数据来描述，根据需要 ，我们选择其中的若干项组成一个数据元素来对应一本书，图书，我们选择其中的若干项组成一个数据元素来对应一本书，图书 馆的编目表反映了书与书之间的关系，是数据元素之间的结构。馆的编目表反映了书与书之间的关系，是数据元素之间的结构。 书是具体地放在某个书架上的，它是编目表的物理实现。这样图书是具体地放在某个书架上的，它是编目表的物理实现。这样图 书馆从书馆从2 2个方面管理图书：物理的藏书和逻辑的编目表。和图书馆个方面管理图书：物理的藏书和逻辑的编目表。和图书馆 一样，计算机管理数据也有一样，计算机管理数据也有2 2个方面：即物理的存储和逻辑的关系个方面：即物理的存储和逻辑的关系 。 数据结构是相互之间存在一种或多种特定关系的数据元素的 数据结构是相互之间存在一种或多种特定关系的数据元素的 集合。集合。数据结构是信息的组织形式数据结构是信息的组织形式，即一个数据由哪些数据元素，即一个数据由哪些数据元素 构成、以什么方式构成、呈现什么结构，数据结构指的是数据之构成、以什么方式构成、呈现什么结构，数据结构指的是数据之 间的结构关系。间的结构关系。 数据的逻辑结构包括线性结构（如线性表、栈、队列）和非 数据的逻辑结构包括线性结构（如线性表、栈、队列）和非 线性结构（如树、二叉树和图）；数据的物理结构指数据元素在线性结构（如树、二叉树和图）；数据的物理结构指数据元素在 存储器中的表示，即存储结构（如向量、链表）。存储器中的表示，即存储结构（如向量、链表）。 5.2 5.2 算法与数据结构算法与数据结构 2 2）数据结构的分类）数据结构的分类 一般情况下，数据元素之间不是孤立的，常常存在某些逻辑 一般情况下，数据元素之间不是孤立的，常常存在某些逻辑 上的联系，这些联系与它们在计算机中的存储位置无关，是独立上的联系，这些联系与它们在计算机中的存储位置无关，是独立 于计算机的。我们把客观事物本身的数据元素之间抽象化的相互于计算机的。我们把客观事物本身的数据元素之间抽象化的相互 关系，即对数据元素之间的逻辑关系的描述称为数据的逻辑结构关系，即对数据元素之间的逻辑关系的描述称为数据的逻辑结构 。 。 数据的逻辑结构按数据元素之间的相互关系，可以把数据结 数据的逻辑结构按数据元素之间的相互关系，可以把数据结 构分为构分为4 4种基本结构。种基本结构。 5.2 5.2 算法与数据结构算法与数据结构 数据结构分类数据结构分类 5.2 5.2 算法与数据结构算法与数据结构 3)3)数据的存储结构数据的存储结构 数据要能被计算机处理，就必须存储在计算机内，我们把 数据要能被计算机处理，就必须存储在计算机内，我们把 这种数据元素及其关系（数据结构）在计算机内的存储表示称这种数据元素及其关系（数据结构）在计算机内的存储表示称 为数据的为数据的存储结构，也称为物理结构存储结构，也称为物理结构，它是数据的逻辑结构在，它是数据的逻辑结构在 计算机存储器里的映像。映像就是对给定的逻辑结构，找出恰计算机存储器里的映像。映像就是对给定的逻辑结构，找出恰 当的与其对应的存储结构，以便在计算机中存储。数据的存储当的与其对应的存储结构，以便在计算机中存储。数据的存储 结构，按关系的映像分为顺序存储结构和链式存储结构。结构，按关系的映像分为顺序存储结构和链式存储结构。 一般情况下，一个结点所占用的空间并不止一个存储单元 一般情况下，一个结点所占用的空间并不止一个存储单元 ，不同类型的结点所占用的存储单元数量也各不相同。数据结，不同类型的结点所占用的存储单元数量也各不相同。数据结 构包括结点的值及结点之间的关系，其存储结构除了必须存储构包括结点的值及结点之间的关系，其存储结构除了必须存储 结点的值外，还得能以直接或隐含的方式体现出结点之间的关结点的值外，还得能以直接或隐含的方式体现出结点之间的关 系。一种逻辑结构通过映像便得到它相应的存储结构，同一种系。一种逻辑结构通过映像便得到它相应的存储结构，同一种 逻辑结构可以映像成不同的内部存储结构，反过来，数据的存逻辑结构可以映像成不同的内部存储结构，反过来，数据的存 储结构一定要反映数据之间的逻辑关系。储结构一定要反映数据之间的逻辑关系。 5.2 5.2 算法与数据结构算法与数据结构 3)3)数据的存储结构数据的存储结构 数据的存储结构中应该有 数据的存储结构中应该有2 2方面的内容：数据元素方面的内容：数据元素 自身值的表示（数据域）和该结点与其他结点关系的自身值的表示（数据域）和该结点与其他结点关系的 域（链域）。域（链域）。 (1)(1)数据元素的映像方法数据元素的映像方法 用二进制位 用二进制位(bit)(bit)的位串表示数据元素：的位串表示数据元素： 5.2 5.2 算法与数据结构算法与数据结构 3)3)数据的存储结构数据的存储结构 (2)(2)关系的映像方法关系的映像方法 数据元素之间的关系在计算机中有顺序映像和非 数据元素之间的关系在计算机中有顺序映像和非 顺序映像顺序映像2 2种表示方法，并由此得到顺序存储结构和链种表示方法，并由此得到顺序存储结构和链 式存储结构式存储结构2 2种存储结构。种存储结构。 顺序存储结构顺序存储结构是逻辑上相邻的数据元素存储在物是逻辑上相邻的数据元素存储在物 理位置上相邻的存储单元里，元素的关系由存储单元理位置上相邻的存储单元里，元素的关系由存储单元 的邻接关系来体现；的邻接关系来体现；链式存储结构链式存储结构是数据元素可以在是数据元素可以在 计算机内任意位置上存储（它不要求逻辑上相邻的元计算机内任意位置上存储（它不要求逻辑上相邻的元 素在物理位置上也相邻素在物理位置上也相邻) )，它们的逻辑关系用指针来链，它们的逻辑关系用指针来链 接。链式存储结构将数据元素存放的存储单元分为接。链式存储结构将数据元素存放的存储单元分为2 2个个 部分，分别存放数据和指针，称为数据域和指针域。部分，分别存放数据和指针，称为数据域和指针域。 5.2 5.2 算法与数据结构算法与数据结构 数据结构分类数据结构分类 5.2 5.2 算法与数据结构算法与数据结构 3)3)数据的存储结构数据的存储结构 链式存储结构中，每个结点除了元素信息本身的 链式存储结构中，每个结点除了元素信息本身的 数据外，还必须增加一个指针域数据外，还必须增加一个指针域(link)(link)，用来存放该，用来存放该 元素逻辑上的后继元素所占存储空间的首地址，这样元素逻辑上的后继元素所占存储空间的首地址，这样 ，存储结构中的结点可以表示为下图所示。，存储结构中的结点可以表示为下图所示。 链式存储结构中链式存储结构中 结点的组成结点的组成 5.15.1 程序设计语言概述程序设计语言概述 5.25.2 算法与数据结构算法与数据结构 5.35.3 程序设计基本过程程序设计基本过程 5.4 5.4 程序设计的基本思想程序设计的基本思想 第第 5 5 章 程章 程 序序 设设 计计 基基 础础 5.3 5.3 程序设计基本过程程序设计基本过程 程序设计主要有 程序设计主要有2 2个方面的任务：首先是将需要用计算机处个方面的任务：首先是将需要用计算机处 理的实际问题抽象为数学模型，并设计出解决这个问题所需要理的实际问题抽象为数学模型，并设计出解决这个问题所需要 的方法和步骤，即算法设计；其次选用适合的计算机程序设计的方法和步骤，即算法设计；其次选用适合的计算机程序设计 语言，对所设计的算法进行编码处理，即程序编制。语言，对所设计的算法进行编码处理，即程序编制。程序设计程序设计 步骤一般分为问题定义、算法设计、程序编制和调试运行等步步骤一般分为问题定义、算法设计、程序编制和调试运行等步 骤。骤。 .1 问题定义 问题定义 通过计算机来解决问题，必须要对交给计算机的任务做出明确通过计算机来解决问题，必须要对交给计算机的任务做出明确 定义，并最终翻译成计算机能识别的语言。当问题复杂时，问定义，并最终翻译成计算机能识别的语言。当问题复杂时，问 题定义会变得非常复杂，就需要借助于一些原则、方法和工具题定义会变得非常复杂，就需要借助于一些原则、方法和工具 。问题定义一般包括以下。问题定义一般包括以下3 3个方面：个方面： 输入输入 即已知什么条件。 即已知什么条件。 处理处理 即希望计算机对输入信息做什么加工。 即希望计算机对输入信息做什么加工。 输出输出 即希望得到什么结果。 即希望得到什么结果。 5.3 5.3 程序设计基本过程程序设计基本过程 .2 算法设计 算法设计 问题定义确定了未来程序的输入、处理、输出， 问题定义确定了未来程序的输入、处理、输出， 但并没有具体说明处理的步骤，而算法则是对解决问但并没有具体说明处理的步骤，而算法则是对解决问 题步骤的描述，即设计一个题步骤的描述，即设计一个“如何做如何做”的算法，然后的算法，然后 按算法编出程序。按算法编出程序。 算法是一个有限长度的、步骤可执行的操作序列 算法是一个有限长度的、步骤可执行的操作序列 的集合。算法是根据问题定义中的信息得来的，是对的集合。算法是根据问题定义中的信息得来的，是对 问题处理过程的进一步细化，但它不是计算机可以直问题处理过程的进一步细化，但它不是计算机可以直 接执行的，只是编制程序代码前对处理思想的一种描接执行的，只是编制程序代码前对处理思想的一种描 述。一般而言，运算结果的精确度及运算速度均与算述。一般而言，运算结果的精确度及运算速度均与算 法有着密切的关系。法有着密切的关系。 5.3 5.3 程序设计基本过程程序设计基本过程 .3 程序编制 程序编制 问题定义和算法描述已经为程序设计规划好了蓝本，接下 问题定义和算法描述已经为程序设计规划好了蓝本，接下 来就是用真正的计算机语言表达了。编写程序前，应先选定一来就是用真正的计算机语言表达了。编写程序前，应先选定一 种程序设计语言，一个良好的、又适合于该具体问题的语言，种程序设计语言，一个良好的、又适合于该具体问题的语言， 可以使得程序的结构清晰、简洁，可以正确而方便地描述所需可以使得程序的结构清晰、简洁，可以正确而方便地描述所需 解决的问题，同时还可以正确地表示过程，以便数据的抽象化解决的问题，同时还可以正确地表示过程，以便数据的抽象化 和模块化。一个高质量的程序，应具备以下条件和模块化。一个高质量的程序，应具备以下条件: : 建立正确的数学模型和确立有效的计算方法。建立正确的数学模型和确立有效的计算方法。 运行结果必须是正确的，且在精度和其他各方面均满足运行结果必须是正确的，且在精度和其他各方面均满足 要求。要求。 程序本身具有良好的结构，逻辑清楚，易读易懂。程序本身具有良好的结构，逻辑清楚，易读易懂。 程序运行时间尽可能短，同时尽可能合理地使用内存。程序运行时间尽可能短，同时尽可能合理地使用内存。 便于检查、修正、移植和维护。便于检查、修正、移植和维护。 5.3 5.3 程序设计基本过程程序设计基本过程 .4 调试运行 调试运行 程序编制完成后，最终要输入到计算机，并经过调试。程序进行 程序编制完成后，最终要输入到计算机，并经过调试。程序进行 检查和调试，目的是查找和改正程序中存在的错误，使程序能顺利地检查和调试，目的是查找和改正程序中存在的错误，使程序能顺利地 执行。执行。 程序调试的首要任务是查错，发现程序中的语法和逻辑错误并将 程序调试的首要任务是查错，发现程序中的语法和逻辑错误并将 其消除。程序的错误一般可以分为编译错误、执行错误和逻辑错误。其消除。程序的错误一般可以分为编译错误、执行错误和逻辑错误。 程序经过编译未发现错误不等于程序在执行过程中无错，程序在执行程序经过编译未发现错误不等于程序在执行过程中无错，程序在执行 过程中无错不等于程序在逻辑上就一定是正确的。过程中无错不等于程序在逻辑上就一定是正确的。 调试是一项复杂而富有挑战性的工作，有时为了改正一个小错误 调试是一项复杂而富有挑战性的工作，有时为了改正一个小错误 ，可能要花费很长的时间。测试程序的方法包括：，可能要花费很长的时间。测试程序的方法包括： 书写检查，通过仔细阅读源程序代码修正错误。书写检查，通过仔细阅读源程序代码修正错误。 手工调试，使用采样数据手工调试程序。手工调试，使用采样数据手工调试程序。 编译调试，使用编译软件测试程序。编译调试，使用编译软件测试程序。 采样数据测试，使用采样数据在计算机上执行程序以发现错误。采样数据测试，使用采样数据在计算机上执行程序以发现错误。 用户测试，通过程序用户的