程序设计基础

1、程序与程序设计语言的基本知识

1）程序：为解决某一问题而采用程序设计语言编写的一个指令集合。

      程序=算法（对操作的描述）+数据结构（对数据的描述）+程序设计语言+语言工具和环境。

2）程序的特点：目的性、有序性、分步性、有限性、操作性。

3）程序设计语言---按发展过程分类

（1）机器语言

          由一连串的0和1二进制代码组成，能被计算机直接理解和执行的指令集合。

          指令格式：

操作码

操作数

（2）汇编语言

          使用“助词符”来表示指令的操作码，使用存储单元或寄存器的名字表示地址码。

          可读性好，易查错，方便修改，占存储空间少，执行速度快。

（3）高级语言

          与机器指令系统无关，独立于机器的程序设计语言，所使用的符号接近人类的自然语言，表达形式接近于被描述的问题。

          高级程序设计语言分类：

                  面向过程的语言：程序不仅要说明做什么，还要详细说明如何做，程序需要详细描述解题的过程和细节；目的在于高效的实现各种算法。

                  面向问题的语言：又称为非过程化语言或第四代语言，只需指出要计算机做什么、数据的输入和输出形式，就能得到所需结果；目的在于高效、直接地实现各种应用系统。

                  面向对象的语言：将客观事物看作具有属性和行为的对象，通过抽象找出同一类对象的共同属性和行为，形成类，通过继承和多态重用。

4）翻译程序（编译器）

（1）定义：其他编程语言必须经过一个翻译过程才能转换成机器语言，实现编译过程的工具是语言处理程序。

（2）汇编程序

                 定义：将汇编语言编制的程序（称源程序）翻译成机器语言程序（称目标程序）的工具。

                 翻译工作的步骤：

                         用机器操作码代替符号化的操作符。

                         用数值地址代替符号名称。

                         将常数翻译为机器的内部表示。

                         分配指令和数据的存储单元。

                作用：

                     

 

 

 （3）翻译程序

                  定义：将高级语言编写的源程序翻译成目标程序的工具。

                  工作方式：

                          解释方式：解释程序

                                  解释程序对源程序逐条地解释执行，不产生目标代码，程序执行时，解释程序和源程序一起参加运行。

                                         

 

 

                                  解释方式执行速度较慢的原因：

                                          每次运行需重新解释。

                                          若程序较大，且错误发生在程序后面，则前面的运行是无效的。

                                          解释程序只看到一句语句，无法对整个程序优化。

                          编译方式：编译程序

                                  对整个源程序经过编译处理后，产生一个与源程序等价的目标程序。

                                          

 

 

                                  编译过程的六个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。

5）程序设计语言的支持环境

             操作系统是各种软件的核心和基础，是整个系统的控制管理中心，为其他软件提供运行环境。

                     

 

 

 6）程序设计语言的基本成分和语法

（1）程序的基本语法单位

                 定义：程序是由语句构成的，而语句又是由数据、表达式、函数等基本语法单位组成的，构成表达式、函数等的最小单位是字符。

                 字符集：

                         定义：字符是构成程序设计语言的最小语法单位，每一种程序设计语言都有自己的合法字符集。

                         基本字符集：数字：0-9

                                               字符：a-z，A-Z

                                               分隔符：，；

                                               运算符：+，-，*，/

                数据类型：

                        定义：数据就是描述客观事物的数字、字符、图片等，即所有能输入到计算机中并能被计算机处理的符号的集合。

                        分类：基本数据类型：程序设计语言系统内置的。

                                          特点：其值不可再分解。整数类型、实数类型、字符类型、逻辑类型等。

                                   构造数据类型：由基本数据类型按某种方式组合而成的。

                                           数组类型、记录类型、枚举类型、集合类型、字符类型、文件等。

                       使用数据类型的目的：

                               决定该类型数据的取值形式、范围和在计算机中的存储和表示方式。

                               决定了该类型的数据所能执行的操作种类，即能够施加到不同类型数据上的运算是不同的。

                表达式：

                        定义：表达式由变量、常量、函数调用和运算符组成。

                        常量和变量：数据存入内存→存放数据的内存单元命名→内存单元名来访问其中的数据

                                 常量：在程序运行中数据不变的量。

                                 变量：在程序运行中数据变化的量。

                                 变量在使用前必须声明其类型和名称，编译程序根据其数据类型，在内存中分配相应的存储空间，以存储该变量的值。

                        运算符：

                                算术运算：加减乘除和乘方。

                                字符运算：连接、取子串

                                关系运算：大于、大于等于、小于、小于等于、等于、不等于

                                逻辑运算：与、或、非

                        内部函数：按功能分为数学函数、字符串函数、日期函数、转换函数。

                赋值语句：表达式和赋值号构成了程序设计的一条赋值语句。 

（2）数据的输入和输出

                 一类：程序之间以文件形式传送数据。

                 二类：人机交互，将人们可以识别的形式按一定格式输入到程序的变量中，输出则相反，按用户的要求格式将变量或常量的值显示或打印。

（3）基本控制结构

                 顺序结构：指程序的执行按照语句出现的先后顺序一次执行。

                 选择结构：根据条件判断，决定程序的执行顺序。

                 循环结构：指重复执行某个操作。

（4）过程：指重复处理的程序段或者分解的子功能编写成一个逻辑上独立的过程，当程序需要该过程时进行调用。

2、算法的基本知识

1）算法的描述：程序---计算机语言表述的算法。

                           流程图---图形化的算法。

2）计算机的算法

（1）数值计算算法

                 目的：求数值解。

                 特点：少量输入、输出，复杂的运算。

（2）非数值计算算法

                 目的：对数据的处理。

                 特点：大量输入、输出，简单的运算。

3）算法的定义：是解决问题方法的精确描述，但算法并不给出问题的精确解，只是说明怎样才能得到解。

4）算法的性质：有穷性、确定性、有效性、零个或多个输入、一个或多个输出

5）算法=数据对象的运算和操作（算数运算、逻辑运算、关系运算、数据运算）+控制结构（顺序结构、选择结构、循环结构）。

6）描述算法的方法

（1）自然语言

                 优点：通俗易懂

                 缺点：易产生歧义，往往根据上下文才能判断其含义，不严格；语句繁琐、冗长，很难清楚地表达算法的逻辑流程。

（2）流程图法

                 定义：用图框、线条、文字说明，形象直观的描述算法。

                 流程图符号：

                       ---起止框：表示流程的开始或结束。

 

 

                       ---输入输出框：表示输入数据或输出结果。

 

 

                         ---判断框：根据条件判断，决定算法的继续执行的走向。

 

 

                         ---处理框：表示基本功能的处理的描述。

 

 

                         ---流程线：表示流程的路径和方向。

 

 

                            ---连接点：表示流程中“向”和“来自”其他地点的输出或输入。

 

 

（3）N-S流程图法：全部算法以一个大的矩形框表示，内包含一些从属于它的小矩形框。

                  顺序语句：

 

 

                  选择语句：

                  循环语句：

 

 

 （4）伪代码法：简称伪码，伪代码是介于自然语言和计算机语言之间的文字和符号来描述算法。

7）算法评价

（1）正确性：设计和评价算法的首要条件。

（2）算法的时间特性：指依据算法编制成程序后在计算机中运作所耗费时间的长短。

         算法的时间复杂度：把程序中语句重复执行次数之和作为程序运行时的时间特性。

（3）算法的空间特性：指依据算法编制成程序后在计算机中运行所占用空间的大小。

         算法的空间复杂度：在计算机上运行所占用的空间同样也是问题规模n的一个函数。

（4）算法的易理解性。

3、程序设计的过程。

1）程序设计步骤

             

 

 

2）测试的前提：程序通过编译，没有语法和连接上的错误。

3）测试用例：为了发现程序中的错误而设计的测试数据。

4）黑盒测试：又称功能测试或数据驱动测试，不考虑程序的内部结构和处理过程，只对程序的接口进行测试，检查程序是否能适当地接受输入数据并产生正确的输出信息。

             黑盒测试技术有事务处理流程测试、等价类划分、边界值分析。

5）白盒测试：又称结构测试或逻辑驱动测试，检验程序内部的逻辑来测试，检查程序中每条通路是否正确工作。

             百合测试有路径测试、语句测试、分支测试、条件组合测试。

4、程序设计思路

1）三种基本程序结构

（1）顺序结构：

                 特点：只有一个入口点和一个出口点。

                 组成：说明语句、赋值语句、输入输出语句、子函数调用语句、返回语句。

（2）选择结构：

                 特点：程序的处理步骤出现分支，根据某一特定的条件选择其中的一个分支执行。

                 形式：单选泽、双选择、多选择。

（3）循环结构

                 当型循环：先判断后执行。

                 直到型循环：先执行后判断。

2）结构化程序设计的基本思想

             采用“自顶向下，逐步求精”（基本原则）的程序设计方法，结构化设计以模块化设计为中心，每个模块各个击破，最后再统一组装。

3）结构化程序设计的特征

（1）以三种基本结构的组合来描述程序

（2）整个程序采用模块化结构。

（3）以控制结构为单位，每个结构只有一个入口一个出口，各单位之间接口简单，逻辑清晰。

（4）采用结构化程序设计语言书写程序，并采用一定的书写格式使程序结构清晰，易于阅读。

（5）注意程序设计风格。

（6）有限制地使用转移语句，在非用不可的情况下，只限于在一个结构内部跳转，不允许从一个结构跳到另一个结构。

4）良好的设计风格

            语句形式化、程序一致性、结构规范化、适当使用注释、标识符贴近实际。

5）面对对象的基本概念

（1）对象（object）---最简单的实体

                对现实世界中对象的模式化，是数据和代码的组合，具有自己的特征和行为。

                对象的特征用数据来表示，称属性。

                对象的行为用对象中的代码来实现，称为对象的方法。

                任何对象都由属性和方法组成的。

                将反映对象的属性和行为封装在一起，是面向对象编程的基本元素，是面向对象设计的核心。

（2）类（class）

                类是创建对象实例的模板，是同种对象的集合与抽象，它包含所创建对象的属性描述和行为特征的定义，对象是类的实例。

（3）属性（property）

                属性用来表示对象的特征，不同的对象有不同的属性。

（4）方法（method）

                方法是对对象的属性的各种操作。

（5）事件、事件过程和事件驱动

                事件是面向对象程序设计中对应于“消息”的术语。

                对象的事件是指系统事先设定的，能被对象识别和响应的动作。

                事件过程：应用程序处理事件的步骤。

                事件驱动的编程机制是程序执行后系统等待某个事件的发生，然后去执行处理此事件过程，待事件过程执行完后，系统又处于等待某事件发生的状态。

（6）封装

               封装机制将数据和代码捆绑在一起，避免了外界的干扰和不确定性。一个对象就是一个封装了数据和操作这些数据的代码的逻辑实体，封装的目的在于将对象的使用者和对象的设计者分开。

               封装一方面通过数据抽象把相关的信息结合在一起，另一方面简化了接口。

               封装性可降低开发过程的复杂性，提高效率和质量，同时也保证了程序中数据的完整性和安全性。

（7）继承

               继承是可以让某个类型的对象获得另一个类型的对象的属性的方法。

（8）多态性

               多态机制使具有不同内部结构的对象可以共享相同的外部接口，虽然针对不同对象的具体操作不同，但通过一个公共类，他们可以通过相同的方式调用。

               优点：大大提高程序的抽象程度和简洁性，降低类和模块之间的耦合性，有利于程序的开发和维护。

（9）消息传递

6）OOP的基本过程

（1）分析现实问题。

（2）建立模型（类属性/方法的确定及类之间关系的确定）。

（3）编程建立数据模型（属性、方法）。

（4）用类声明对象，通过对象间传递信息（方法调用）完成预订功能。

7）OOP的优点

（1）通过继承，减少多余的代码并扩展现有代码。

（2）在标准的模块上构建自己的程序，减少软件开发时间并提高生产效率。

（3）数据隐藏---保护程序免受外部代码的侵袭。

（4）允许一个对象的多个实例同时存在，彼此之间相互不干扰。

（5）允许将问题空间中的对象直接映射到程序中。

（6）基于对象的工程可以很容易地分割为独立部分。

（7）以数据为中心的设计方法允许我们抓住可实现模型的更多细节。

（8）面向对象的系统很容易从小到大逐步升级。

（9）对象间通信所使用的消息传递技术与外部系统接口部分描述更简单。

（10）便于控制软件复杂度。