计算机导论 ——软件部分 巢爱棠 atchao@yeah.net 办公室：1208

软件部分 第2章 计算机的基础知识（2.4～2.6） 第4章 计算机系统软件与工具软件 第5章 计算机应用软件（自学）

基本要求：理解程序设计、算法与数据结构的基本知识，注意养成良好的程序设计风格和习惯，为学习本书的以下各章和后续软件课程打好基础。 第2章 计算机的基础知识 基本要求：理解程序设计、算法与数据结构的基本知识，注意养成良好的程序设计风格和习惯，为学习本书的以下各章和后续软件课程打好基础。

第2章 计算机的基础知识 程序设计基础 算法基础 数据结构基础

程序设计语言 结构化程序设计 良好的程序设计风格 人与计算机交互的工具 3个发展阶段 结构化程序设计方法 3种基本结构 2.4 程序设计基础 程序设计语言 人与计算机交互的工具 3个发展阶段 结构化程序设计 结构化程序设计方法 3种基本结构 单入口单出口的控制成分 良好的程序设计风格 编写程序按照规范化方法进行

机器语言：由计算机的指令系统组成，使用机器语言编写的程序计算机能够直接理解并执行，但编程和理解都十分的困难。 程序设计语言 机器语言：由计算机的指令系统组成，使用机器语言编写的程序计算机能够直接理解并执行，但编程和理解都十分的困难。 汇编语言：使用“助忆符”来表示指令的操作码，并使用存储单元或寄存器的名字表示地址码，以便于记忆和书写。

面向过程程序设计语言 面向对象程序设计语言 高级程序设计语言：是一种与机器的指令系统无关、表达形式更接近于被描述的问题的程序设计语言，便于程序的编写。使用高级程序设计语言编写的程序称为源程序，它必须经过程序设计语言翻译系统的处理后才能执行。 面向过程程序设计语言 面向对象程序设计语言

结构化程序设计 程序设计 广义的程序设计 需求分析 总体设计 详细设计 编码 测试 运行与维护 是一个使用程序设计语言产生一系列的指令以告诉计算机该做什么的过程。 需求分析 总体设计 详细设计 编码 测试 运行与维护

结构化程序设计 1、结构化程序设计方法 采取以下方法来保证得到结构化的程序 自顶向下；逐步细化； 模块化设计；结构化编码。 自顶向下、逐步求精（细化）的设计方法 把一个复杂问题的求解过程 分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。 要点：先全局后局部、先整体后细节、先抽象后具体。

结构化程序设计 用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。

结构化程序设计 自顶向下，逐步细化方法的优点： 考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程序。这就是用工程的方法设计程序。

结构化程序设计 模块设计的方法： 模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。 在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。 子模块一般不超过50行。 划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。

结构化程序设计 2.结构化程序的基本结构 A A B B A T F 条件 （c）循环结构 （a）顺序结构 T F 条件

结构化程序设计 顺序结构例

结构化程序设计 分支结构例

结构化程序设计 循环结构例:我国有13亿人口，按人口年增长0.8%计算，多少年后我国人口超过26亿。

3.单入口单出口的控制成分 结构化程序设计 要点：程序中只能使用顺序、分支和循环3种基本结构；不能使用GOTO语句随意地进行控制转移。 优越性：程序的静态结构与动态执行情况比较一致；容易保证程序的正确性；易阅读、理解、测试、修改。

编写程序必须按照规范化方法进行,应养成良好的程序设计风格 标识符：按意命名、保留字用大写字母、使用统一的缩写规则。 表达式：使用括号、使用库函数、条件化简

函数与过程:一个大型程序分解为多个模块,每个模块是一个函数或过程。 良好的程序设计风格 函数与过程:一个大型程序分解为多个模块,每个模块是一个函数或过程。 模块的独立性（高内聚、低耦合） 模块的规模（适中）

程序行的排列格式：排列格式美观、层次分明、使用统一的缩进格式，同一嵌套深度并列的语句对齐。 良好的程序设计风格 程序行的排列格式：排列格式美观、层次分明、使用统一的缩进格式，同一嵌套深度并列的语句对齐。 注释：添加必要的注释，以说明程序、过程和语句等的功能及注意事项。

2.5 算法基础 计算机解决简单问题的步骤 1.问题分析 2.算法设计 3.程序设计 4.测试

2.5 算法基础 一个程序应包括两个方面的内容: 著名计算机科学家沃思提出一个公式:  数据结构 + 算法 = 程序 对数据的描述：数据结构(data structure) 对操作的描述：算法(algorithm) 著名计算机科学家沃思提出一个公式:  数据结构 + 算法 = 程序 完整的程序设计应该是: 数据结构＋算法＋程序设计方法＋语言工具

2.5 算法基础 广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。 对同一个问题，可有不同的解题方法和步骤 例： 求 例： 求 方法1：1+2，+3，+4，一直加到100 加99次 方法2：100+(1+99)+(2+98)+…+(49 +51)+50 = 100 + 49×100 +50 加51次

2.5 算法基础 为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。希望方法简单，运算步骤少。 计算机算法可分为两大类别： 数值运算算法：求数值解，例如求方程的根、求函数的定积分等。 非数值运算：包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理等。

2.5 算法基础 太繁琐 算法设计举例1—— 求 5！=1×2×3×4×5 步骤1：先求1×2，得到结果2 求 5！=1×2×3×4×5 步骤1：先求1×2，得到结果2 步骤2：将步骤1得到的乘积2再乘以3，得到结果6 步骤3：将6再乘以4，得24 步骤4：将24再乘以5，得120 太繁琐 如果要求1×2×…×1000，则要写999个步骤

2.5 算法基础 可以设两个变量：一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设p为被乘数，i为乘数。用循环算法来求结果, 算法可改写： S1：使p=1。 S2：使i=2。 S3：使p×i，乘积仍放在变量p中。 S4：使i的值加1。 S5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。

2.5 算法基础 算法简练 如果题目改为：求1×3×5×……×1001算法只需作很少的改动： 该算法的步骤用文字表述如下： S1：使p=1 S2：使i=3 S3：使p×i，乘积仍放在变量p中 S4：使i的值增加2 S5：若i≤1001，返回S3以及其后的步骤S4和S5。否则，结束。 算法简练

〖例2-32〗若给定两个正整数m和n，试写出求它们的最大公因子（即能同时整除m和n的最大整数）的算法。 2.5 算法基础 算法设计举例2—— 欧几里德算法（Euclid’s Algorithm） 〖例2-32〗若给定两个正整数m和n，试写出求它们的最大公因子（即能同时整除m和n的最大整数）的算法。

欧几里德算法（Euclid’s Algorithm） ——转辗相除法 该算法的步骤用文字表述如下： 第1步：读入两个正整数m和n（设m>n） 第2步：求m和n的余数r＝mod（m,n） 第3步：用n的值取代 m，用r的值取代n 第4步：判别r的值是否为零，如果r＝0，则m为最大公因子；否则返回 第2步 第5步：输出m的值，即为最大公因子

2.5 算法基础 一个算法应该具有以下特点： 有穷性：包含有限的操作步骤。 确定性：算法中的每一个步骤都应当是确定的。 有零个或多个输入：输入是指在执行算法时需要从外界取得必要的信息。 有一个或多个输出：算法的目的是为了求解，“解” 就是输出。 有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果 。

2.5 算法基础 常用算法描述方法： 自然语言 流程图 算法描述语言 N-S流程图

2.5 算法基础 用自然语言表示算法 自然语言就是人们日常使用的语言，可以是汉语或英语或其它语言。用自然语言表示通俗易懂，但文字冗长，容易出现“歧义性”。自然语言表示的含义往往不大严格，要根据上下文才能判断其正确含义，描述包含分支和循环的算法时也不很方便。因此，除了那些很简单的问题外，一般不用自然语言描述算法。 如前述例子

2.5 算法基础 用流程图表示算法 美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号： 起止框 判断框 处理框 输入/输出框 注释框 流向线 连接点

2.5 算法基础 求5!的算法用流程图表示 如果需要将最后结果打印出来，可在菱形框的下面加一个输出框。

2.5 算法基础 欧几里得算法（转辗相除法求两个正整数的最大公因子）用流程图表示

2.5 算法基础 用算法描述语言表示算法 欧几里得算法（转辗相除法求两个正整数的最大公因子）用 C语言程序表示 void main() { int m,n,r; scanf("%d%d",&m,&n); r=m%n; while(r!=0) { m=n; n=r; } printf("\n the greatest common divisor is:%d",n);

2.5 算法基础 怎样衡量算法的优劣 判断算法好坏的四个标准 正确性、易读性、健壮性、时空特性 算法的时空特性即 时间特性 空间特性

算法的时间特性 是指依据算法编制成程序后在计算机中执行时所耗费的时间大小。 2.5 算法基础 算法的时间特性 是指依据算法编制成程序后在计算机中执行时所耗费的时间大小。 所耗费的时间取决于程序运行时输入的数据量、对源程序编译所需要的时间、执行每条指令所需的时间以及程序中语句重复执行的次数。

2.5 算法基础 算法的时间特性求解 例如，某算法的语句频度为2n3+3n2+2n+1 则：T（n）=O(n3) 计算算法中主要语句执行的次数——语句频度 用时间复杂度—T(n)表示 当问题规模n→∞时，算法执行时间增长率。 用大“O”表示法。记作T(n)=O(f(n))（ f(n) ：为语句频度之和的最高次项的数量级） 问题规模—n 算法求解问题的输入量 （或初始数据量）。 例如，某算法的语句频度为2n3+3n2+2n+1 则：T（n）=O(n3)

算法的空间特性 2.5 算法基础 讨论算法中除正常占用内存开销外的辅助存储单元规模。 用空间复杂度—S(n)表示 当问题规模n→∞时，算法所需的辅助空间随n变化的规律。 记作S(n)=O(f(n)) （ f(n) ：为辅助空间最高次项的数量级）

重要性：数据的结构直接影响算法的选择和程序的效率。 2.6 数据结构基础 重要性：数据的结构直接影响算法的选择和程序的效率。 数据：描述客观事物的数、字符以及所有能输入到计算机并被计算机程序处理的符号的集合，如数值、字符、图形、图像、声音等。数据集合中的每一个个体称为数据元素，它是数据的基本单位。

内容包括：线性表、栈、队、串、数组和广义表、树、图；查找和排序技术。 2.6 数据结构基础 数据结构：带有结构的数据元素的集合，结构反映了数据元素相互之间存在的某种联系。 （1）从学科的角度来看，数据结构是计算机科学技术的一个分支，它主要研究非数值计算的程序设计问题中数据的逻辑结构和物理结构以及它们之间的关系，并对这种结构定义相应的运算，设计出实现这些运算的算法。 （2）从课程的角度来看，数据结构是计算机科学技术专业的一门重要的专业基础课，是教学计划中的核心课程之一。 内容包括：线性表、栈、队、串、数组和广义表、树、图；查找和排序技术。

数据结构研究的三个方面： 逻辑结构唯一 存储结构不唯一 运算的实现依赖于存储结构

四种基本数据结构： （a）集合结构 （b）线性结构 （c）树型结构 （d）图型结构 四类基本结构的示意图

数据元素:数、符号、记录。 定义：一个线 性 表是n个数据元素的有限序列。 线 性 表 学生成绩表 姓名 学号 班级 计算机导论 离散数学 数字逻辑 计算机组成原理 操作系统 编译原理 张维 760401 计04 92 79 87 65 80 82 李强 760402 72 88 78 王捷 760403 70 62 75 68 钱芹 760404 86 90 84 77 69 …

线性表的运算：设L为一个线性表 置空表SETNULL（L） 求表的长度LENGTH（L） 取表元素GET（L，i） 线 性 表 线性表的运算：设L为一个线性表 置空表SETNULL（L） 求表的长度LENGTH（L） 取表元素GET（L，i） 在表中查找特定元素LOCATE（L，x） 插入新元素INSERT（L，i，b） 删除表元素DELETE（L，i）

顺序存储结构：使用一批地址连续的存储单元依次存放线性表的数据元素。计算长度操作比较简单，但插入和删除不便。 线 性 表 线性表的存储结构： 顺序存储结构：使用一批地址连续的存储单元依次存放线性表的数据元素。计算长度操作比较简单，但插入和删除不便。 学生成绩表 姓名 学号 班级 计算机导论 离散数学 数字逻辑 计算机组成原理 操作系统 编译原理 张维 760401 计04 92 79 87 65 80 82 李强 760402 72 88 78 王捷 760403 70 62 75 68 钱芹 760404 86 90 84 77 69 … n个数据元素 每个数据元素包含m个数据项 共需m×n个存储单元

链式存储结构：使用不一定连续的存储单元存放线性表，又称为链表。 线 性 表 线性表的存储结构： 链式存储结构：使用不一定连续的存储单元存放线性表，又称为链表。 还需要存储一个指示其直接后继元素的指针，增加存储空间开销。 data 指针域 数据域 可充分利用零星的存储单元，可高效地实现插入、删除。

堆 栈 堆栈（stack）定义： 一种受限的线性表，即只能在表的一端（表尾）进行插入和删除操作。进栈和退栈操作按“后进先出”（Last In First Out，LIFO）的原则进行。… … 栈底 栈顶 进栈 退栈 a1 a2 an

设S为一个堆栈 堆栈的运算： 堆栈的存储结构：一般采用顺序存储结构 置空栈SETNULL（S） 进栈PUSH（S，x） 退栈POP（S） 堆 栈 堆栈的运算： 设S为一个堆栈 置空栈SETNULL（S） 进栈PUSH（S，x） 退栈POP（S） 取栈顶元素TOP（S） 判断堆栈是否为空EMPTY（S） 堆栈的存储结构：一般采用顺序存储结构

一般采用顺序存储结构 堆栈的应用：表达式的计算、子程序的调用、迷宫求解、列车编组等。 堆 栈 堆栈的存储结构示例 top=2 top=3 A B top=3 C top=4 D top=0 top=1 堆栈的应用：表达式的计算、子程序的调用、迷宫求解、列车编组等。

队 列 队列（queue）的定义：也是一种受限的线性表,只能在表的一端（队尾）进行插入，在表的另一端（队首）进行删除操作。进、出队列操作按“先进先出”（First In First Out，FIFO）的原则进行。 a1 a2 a3 an-1 an 退出队列 进入队列 队首 队尾 …

置空队列SETNULL（Q） 进入队列ADDQUEUE（Q，x） 退出队列DELQUEUE（Q） 取队首元素FRONTQUE（Q） 队 列 队列的运算：设Q为一个队列 置空队列SETNULL（Q） 进入队列ADDQUEUE（Q，x） 退出队列DELQUEUE（Q） 取队首元素FRONTQUE（Q） 判断队列是否为空EMPTY（Q） 队列的存储结构：链式存储结构，一个链队列需要设置队首指针和队尾指针。

队列的应用：程序设计中经常用到，如操作系统中对作业的管理，运行结果的输出等。 队 列 数据 … 队首指针 队尾指针 链队列示意图 队列的应用：程序设计中经常用到，如操作系统中对作业的管理，运行结果的输出等。

例如下图(a)所示为井字棋的一 个格局，而格局之间的关系是由比赛规则决定的。 树型数据结构举例—— 计算机和人对奕问题 例如下图(a)所示为井字棋的一 个格局，而格局之间的关系是由比赛规则决定的。 图(a)所示的格局可以派生出五个格局，如下图所示，而从每一个新的格局又可派生出四个可能出现的格局。 (a) (a1) (a2) (a3) (a4) (a5)

图型数据结构举例——教学计划编排问题 在教学计划包含的许多课程之间，有些课程之间有先修和后续的关系，有些课程可以任意安排次序。 这种各个课程之间的次序关系可用一个称作图的数据结构来表示，如图1.3所示。 有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边<vi，vj>，则表示课程i必须先于课程j进行。

本 章 小 结 基本知识,包括:计算机的运算基础、逻辑代数基础、计算机的基本结构与工作原理、程序设计基础、算法与数据结构的基础知识。 应掌握数据在计算机内部的表示形式及数制间的转换方法，理解命题逻辑、逻辑代数、计算机的结构、程序设计语言、结构化程序设计方法以及算法与数据结构的基本知识，为进一步学习本书的以下各章和后继课程打好基础。 本章介绍了计算机的一些基本知识,包括:数制与码制、数的定点与浮点表示、信息的编码；逻辑代数与逻辑电路基础;计算机的基本结构与工作原理;程序设计语言、结构化程序设计、程序设计风格；以及算法与数据结构的基础知识。 通过本章的学习，应掌握数据在计算机内部的表示形式及数制间的转换方法，理解逻辑代数、逻辑电路、计算机的结构、程序设计语言、结构化程序设计方法以及算法与数据结构的基本知识，为进一步学习本书的以下各章和后继课程打好基础。

《计算机导论》第2章 课程到此结束！ Thank You !