程序设计基础

1、第三部分程序设计基础3.1程序、程序设计、程序设计语言的定义程序：计算机程序，是指为了得到某种结果而可以由计算机等具有信息处理能力的装置执 行的代码化指令序列，或者町以被口动转换成代码化指令序列的符号化指令序列或者符号化 语句序列。程序设计:程序设计是给出解决特定问题程序的过程，是软件构造活动中的甫要组成部分。 程序设计往往以某种程序设计语言为工具，给出这种语言I、的程序。程序设计过程应当包括 分析、设计、编码、测试、排错等不同阶段。程序设计语肓：程序设计语言用于书写计算机程序的语育。语肓的基础足一组记兮和一组 规则。根据规则由记号构成的记号串的总体就是语言。在程序设计语言中，这些记号串就是

2、程序。程序设计语言有3个方面的因素，即语法、语义和语用。3.2高级语言和低级语言的概念及区别高级语言：高级语言（High-level programming language）是高度封装了的编程语言，与低 级语言相对。它是以人类的口常语言为基础的一种编程语言，使用一般人易于接受的文字来 表示（例如汉字、不规则英文或其他外语），从而使程序编写员编写更容易，亦有较高的町 读性，以方便对电脑认知较浅的人亦可以大概明白其内容。低级语言：低级语言分机器语言（二进制语言）和汇编语言（符号语言）,这两种语言都 是面向机器的语言，和具体机器的指令系统密切相关。机器语言用指令代码编写程序，而符 号语言用指令助记

3、符来编写程序。区别：高级语言：实现效率高，执行效率低，对硕件的可控性弱，目标代码大，町维护性好，可移 植性好低级语言：实现效率低，执行效率高，对硕件的町控性强，目标代码小，叮维护性差，町移 杭性差了解知识：CPU运行的是二进制指令，所有的语言编写的程序最终都要翻译成二进制代码。 越低级的语言，形式上越接近机器指令，汇编i） r吐与机器指令一一对应的。而越高级的 语言，一条语句对应的指令数越多，其中原因就屆冷级讥書对底层操作进行了抽象和封装, 使编写程序的过程更符合人类的思维习惯，并且极人了简化了人力劳动。也就是说用高级语 言写一句，会被转换成许多底层操作，大部分的工作交给了负责转换的机器（即编

4、译器）， 从而人力得到了解放。33编译程序的概念及作用编译程序（Compiler, compiling program）也称为编译器,是指把用高级程序设计语言书 写的源程序，翻译成等价的机器语言格式目标程序的翻译程序。（2）作用：它以高级程序设计语言书写的源程序作为输入,而以汇编语言或机器语言表示的目 标程序作为输出。3.4计算机求解问题的过程分析问题（确定计算机做什么）设计算法（寻找解决问题的途径利方法，即要计算机怎么 做）一编写程序（将算法翻译成计算机程序设计语言）一上机运行和测试3.5程序正确性的含义程序正确性证明就是采用严格的数学方法评价一个程序足否达到了预定的性能，即对于任何 一纽允

5、许的输入信息，程序执行后能得到一组和这组信息对应的正确的输出信息。3.6程序错误的几种类型程序错误，即英文的Bug,也称为缺陷，是指在软件运行中因为程序本身有错误而造成的功 能不正常、死机、数据丢失、非正常中断等现彖。语法错误逻辑错误3.7程序调试、程序测试的概念以及区别程序调试：是将编制的程序投入实际运行前，用于工或编译程序等方法进行测试，修正语 法错误和逻辑错误的过程。这是保证计算机信息系统正确性的必不可少的步骤。编完计算机 程序，必须送入计算机中测试。程序测试：(program testing)是指对一个完成了全部或部分功能、模块的计算机程序在正 式使用前的检测，以确保该程序能按预定的方

6、式正确地运行。了解知识：程序测试的方法灰盒测试，确实是介于白盒测试与黑盒测试之间的，町以这样理解，灰盒测试关注输出对 于输入的正确性，同时也关注内部表现，但这种关注不象白盒那样详细、完整，只是通过一 些表征性的现一象、事件、标志來判断内部的运行状态，仃时候输出是正确的，但内部其实已 经错误了，这种情况作常多，如果每次都通过白盒测试来操作，效率会很低，因此需要采取 这样的一种灰盒的方法。白盒测试，又称结构测试。他的前提是可以把程序看成在一个透明的白盒子里，测试者完全 知道程序的结构和处理算法。这种方法按照程序内部逻辑设计测试用例，检测程序中的主要 执行通路是否能按照预定要求正确工作。白盒测试根据

7、软件的内部逻辑设计设施用例，常用 的技术是逻辑覆盖，即考察用测试数据运行被测程序是对程序逻轲:的覆盖程度。主要的覆盖 标准有：语句覆盖、判定覆盖、条件覆捲、判定/条件覆盖、组介条件覆盖和路径覆盖。黑盒测试根据关键需求说明书所规定的功能來设计测试用例，它不考虎软件的内部结构和处 理算法。常用的黑盒测试技术包括等价类划分、边值分析、错误推测和因果图等。区别： 目的不同软件测试的目的是发现错误，至丁找出错误的原因和错误发生的地方不是软件测试的任务, 而是调试的任务.调试的目的是为了证明程序的正确，因此它必须不断地排除错误它们的出 发点不一样。前者是挑错，是一种挑剔过程，属于质盘保证活动。后者是排错，

8、是一种排除 过程，是编码活动的一部分。 指导原则和方法不同软件测试的输出是预知的，其软件测试用例必须包括预期的结果，而调试的输出大多是不町 预见的，需要调试者去解释、去发现产生的原因。 操作者不同因为心理状态是软件测试程序的障碍，所以执行软件测试的人一般不是开发人员，以使软件 测试更客观、更有效，而调试人员一般都是开发人员.3.8结构化程序设计概念及类型结构化程序设计(structured programming)是进行以模块功能和处理过程设计为主的详细设 计的基本原则。结构化程序设计的三种基本结构是:顺序结构、选择结构和循环结构。顺序结构表示程序中的各操作是按照它们出现的先后顾序执行的。选择

9、结构表示程序的处理步骤出现了分支，它需要根据某一特定的条件选择其中的一个分支 执行。选择结构有单选择、双选择和多选择三种形式。循坏结构表示程序反复执行某个或某些操作，宜到某条件为假(或为真)时才可终II循环。 在循坏结构中最主要的是：什么情况卜执行循坏？哪些操作需要循环执行？循坏结构的基本 形式有两种：当型循环和直到型循坏。当型循坏：表示先判断条件，当满足给定的*件时执行循环体，并II在循环终端处流程口动 返回到循环入门：如果条件不满足，则退出循环体立接到达流程出II处。因为是”当条件满 足时执行循坏“，即先判断后执行，所以称为当型循环。直到型循环:表示从结构入11处“接执行循环体，在循坏终端

10、处判断条件，如果条件不满足， 返回入11处继续执行循环体，直到条件为真时再退出循环到达流程出11处，是先执行后判断。 因为是“直到条件为真时为止“，所以称为直到型循环。3.9面向对象程序设计概念面向对象编程Object Oriented Programming. OOP,面向对象程序设计）是一种计算机编 程架构。OOP的一条基本原则是计算机程序是由单个能够起到子程序作用的单元或对象组 介而成。OOP达到了软件工程的三个主要目标：重月性、灵活性和扩展性。为了实现整体 运算，每个对象都能够接收信息、处理数据和向其它对彖发送信息。面向对象程序设计中的概念主要包括：对象、类、数据抽象、继承、动态绑定、

11、数据封装、 多态性、消息传递。通过这些概念面向对象的思想得到了具体的体现。3.10 ASCII字符集ASCII （American Standard Code for Information Interchange.美国标准信息交换代码）是基于 拉字母的一套电脑编码系统，主要用于显示现代英语和其他西欧语言。它是现今故通用的 单字节编码系统，并等同于国际标准ISO/IEC646o标准ASCII码也叫基础ASCII码,使用7位二进制数來表示所冇的大写和小写字母，数字0到 9、标点符号，以及在美式英语中使用的特殊控制字符。大小规则1）数字09比字母要小。如”7“F“；2）数字0比数字9要小，并按0到

12、9顺序递增。如3）字母A比字母Z要小，并按A到Z顺序递增。如4）同个字母的犬写字母比小写字母要小。如”A“v“a”记住几个常见字母的ASCII码大小：“换行LF”为10； “回车CR”为13；空格为32； 0为48：”A”为65： ”a“为97。3.11标识符、关键字的概念在编程语言中，标识符就是程序员自己规定的具有特定含义的词，比如类名称，属性名称, 变量名等。关犍字就是程序发明者规定的有特殊含义的单词，又叫保留字。3.12注释语句的作用注释语句在程序的开始或中间，不具有任何功能实现的作用，仅仅是对程序进行说明的语句。 注释语句在程序运行过程中不运行，却是程序编写时的重要内容，对于理解程序很

13、重要。3.13表达式的组成及类型表达式，是由数字、算符、数字分组符号（括号）、自由变最和约束变最等以能求得数值的 有意义排列方法所得的组合。类型：算术表达式：是最常用的表达式，又称为数值表达式.它是通过算术运算符来进行运算的数 学公式。加法、减法、乘法、除法、求余关系表达式：用关系运算符将两个表达式连接起来的式子，称关系表达式。关系表达式的值 是逻辑值“真”或“假”。=（等于）、 （小于）、=（小于等于）、 （大于）、=（大于等于）、 （不等于） 逻轲表达式:用逻辑运算符将关系表达式或逻辑最连接起来的有意义的式子称为逻辑我达式。 逻轲表达式的值是一个逻辑值，即“true”或“false”。NO

14、T （非）、AND （与）、OR （或）3.14子程序和函数的概念子程序:在计算机科学中,子程序（英语:Subroutine, procedure, function, routine, method, subprogram, callable unit）,是一个大型程序中的某部份代码,由一个或多个语句块组成。它 负责完成某项特定任务，而且相较于其他代码，具备相对的独立性。函数：在程序设计中，常将一些常用的功能模块编写成函数，放在函数库中供公共选用。要 善于利用函数，以减少重复编写程序段的工作量。许多程序设计语言中，町以将一段经常需 要使用的代码封装起來，在需要使用时可以直接调用，所以，函数也

15、町以说是许多代码的集 合，这就是程序中的函数。3.15数据、数据元素、数据对彖、数据项的概念数据：数据就是数值，也就是我们通过观察、实验或计算得出的结果。数据有很多种，垠简 单的就是数字。数据也町以是文字、图像、声音等。数据可以用于科学研究、设计、查证等。 数抓儿索：数据元素（data element）是计算机科学术语。它是数据的基本单位，数据元素也叫 做结点或记录。在计算机程序中通常作为一个整体进行考虑和处理。有时，一个数据元素町 由若干个数据项组成，例如，一本书的书目信息为一个数据元素，而书目信息的毎一项（如 书名、作者名等）为一个数据项。数据项是数据的不可分割的最小单位。数据对象：（Da

16、ta Object）是件质相同的数据元素的集介，是数据的一个子集，数据对象是 一种运行时的概念。可以是外部实体（例如，产生或使用信息的任何事物）、爭物（例如，报表）、 行为（例如，打电话）、爭件（例如，响警报）、角色（例如，教师、学生）、单位（例如，会计科）、 地点（例如，仓库）或结构（例如，文件）等。总之，町以由一组属性來定义的实体都可以被认 为是数据对象。数据项：数据项乂称数据元素（data element）,是数据的基本单位，一个数据可由若干个数 据项（data item）组成，数据项是数据的不可分割的故小单位。3.16数据的逻辑结构、存储结构数据的逻辑结构是对数据之间关系的描述，有时就

17、把逻辑结构简称为数据结构。逻辑结构形 式地定义为（K, R）（或（D, S）,其中，K是数据元素的有限集，R是K上的关系的月限 集。了解知识：逻辑结构仃四种基本类型：集合结构、线性结构、树状结构和网络结构:衷和树 是最常用的两种高效数据结构，许多高效的算法能够用这两种数据结构來设计实现。表是线 性结构的（全序关系），树（偏序或层次关系）和图（局部有序（weak/local order）是非线性结 构。数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。它包括数据元素的表示 和关系的表示。3.17数据运算 数据运算是对数据依某种模式而建立起來的关系进行处理的过程。最基本的数据运算有：算术

18、运算，如：力n、减、乘、除、乘方、开方、取模等：关系 运算，如：等于、不等于、大于、小于等：逻辑运算，如：与、或、非、恒等、蕴含等。3.18数据结构的两大逻辑结构和四种常用的存储表示方法数据的逻辑结构分两人类：线性结构和非线性结构了解知识：线性结构是一个冇序数据元素的集介。常用的线性结构有：线性表，栈，队列， 双队列，数组，串。常见的韭线性給构有：一 维数组，多维数组，广义表，树（.叉树等）， 图。数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法 了解知识：（1门顶序存储方法：该方法把逻辑上相邻的结点存储在物理位置上相邻的储单 元里，结点间的逻辑关系由存储单元的邻接

19、关系來体现。由此得到的存储衣示称为顺序存储 结构 （Sequential Storage Structure）,通常借助程序语言的数组描述。该方法主要应用于 线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。（2）链接存储方法：该方法不要求逻辑上相邻的结点在物理位豐上亦相邻，结点间的逻辑 关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure），通常借助于程序语言的指针类型描述。（3）索引存储方法：该方法通常在储存结点信息的同时，还建立附加的索引表。索引表由 若丁索引项组成。若每个结点在索W表中都有一个索引项，则该索引

20、表称Z为稠密索引（Dense lndex）o若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引（Spare Index）。索引项的一般形式是：（关键字、地址）关键字是能唯一标识个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储 位置：稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法：该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地 址。四种基本存储方法，既可单独使用，也町组合起来对数据结构进行存储映像。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相 应的逻辑结构，视其体要求而定，主要考虑运算方便及算法的时空要求。3.19算法和程序的关系算法是对特定问题求解步骤的描述，它是指令的有限序列。算法与程序的关系：算法和程序都是指令的有限序列，但是，程序是算法，而算法不一定 是程序。算法和程序的区别主要在于：（1）在语言描述上，程序必须是用规定的程序设计语言來写，而算法很随总：（2）在执行时间上，算法所描述的步骤一定是有限的，而程序可以无限地执行下去。 所以：程序=数据结构+算法3.20常用数据类型种类及特性不同的变成语言，数据类型的说法有差异。一般而言包含：数字型或者数值型,常有I