大学信息技术导论第5章.ppt

大学信息技术导论 第5章,2004年10月,第5章 程序设计基础,程序设计语言是人们用来向计算机传递 信息与下达命令的通信工具。 软件发展的三个阶段: 1946年1956年 低级语言（机器语言或汇编语言），追求功效，顺序程序。 1956年1968年 高级语言（数学语言或接近于自然语言（英语）的语言），追求易读性和易维护性，并发程序和并行程序。 1968年 高级语言，结构良好性，使之易读、易维护，并发程序和 并行程序。 程序设计语言的发展趋势: 模块化 简明性 形式化 并行化 可视化,5.1 基本概念和程序设计语言的发展,基本概念: 程序、子程序、子例程、协同例程、模块， 程序的顺序性、并发性、并行性和分布性等。,5.1.1 基本概念,1. 程序 指令是计算机可以理解并执行的操作命令，有完整含义，在高级语言中表现为可执行的语句。 机器指令是CPU可以理解并执行的操作命令。用二进制数0和1组成的一串代码（1100110是8086的加法指令e.g.) 一条指令对应着一种基本操作，由两部分组成：操作码和操作数。 操作码是指明该指令要完成的操作，如加、减、传送、输入等。 操作数是指参加运算的数或者数所在的单元地址。 计算机所能执行的全部指令，就是计算机的指令系统(Instruction Set)，为特定体系结构独有。,5.1.1 基本概念,程序： 狭义地定义为计算机指令的集合； 广义地定义为说明一项任务或工作过程的符 号代码形式，这种符号代码人可以读懂，而 由计算机处理执行。 程序的实际工作过程称为程序的执行。 程序的静态特性：与执行过程无关的特性。 程序的动态特性：与执行过程有关的特性。,5.1.1 基本概念,程序必须具备的特征 程序必须具有解决某一问题的特定任务与功能，都需要回答“解决什么或做什么”的问题 程序要遵循一定的规则和步骤，而不是多条指令的胡乱堆砌。程序必须按照算法所规定的语法格式和步骤，回答“怎样做”和“如何执行”的问题 程序的执行者是计算机，由于计算机有其自身的逻辑和执行方式，所以程序必须符合计算机的逻辑及处理方式，才能被计算机识别和执行 程序是由人来编写的，是人对要处理和解决问题的方法和步骤要求计算机操作处理的说明 程序可以连续自动运行。计算机能够在无需人干预的情况下，连续、自动地执行程序，最终给出结果,5.1.1 基本概念,2.程序单位 构成程序基本成分:子程序、子例程、协同例程、递归例程和模块。 把计算机所进行的一项信息处理定义为一个计算任务,与子计算任务相应的处理对象和处理规则的描述被称为子程序。 可由其它程序或子程序调用的子程序被称为是子例程。 协同例程是指一组可以互相调用的程序单位，它们彼此处于平等地位，调用后毋须返回到开始位置，且自带工作区。 递归例程是可以作为其本身的子例程而被调用的例程。 模块是具有相对独立性的一组逻辑上有关的实体。 在现代高级语言中，有各种定义模块的方式，但其主要成分是一组说明和一组语句。,5.1.1 基本概念,3.源程序 为解决特定的问题用程序的宿主语言编写的正文，称为源程序(Source Program)或源代码(Source Code)。源代码由顺序执行的指令组成。 按语言是否可以直接被机器识别的程度可以分为机器语言、汇编语言和高级语言三类，前两者为低级语言。 低级语言中，源程序是一组机器指令和有关的数据。 高级语言中，源程序一般是一组说明和语句。,5.1.1 基本概念,机器语言 是表示成数码形式的机器基本指令集，或者是操作码经过符号化的基本指令集，也称为面向机器的语言。用二进制代码指令与计算机打交道，可以被计算机硬件直接识别，不需要翻译，因此执行速度快,执行效率高。 缺点是不直观，编程工作量大，易出错，程序难读、难记、难修改，也不具有通用性（在一种型号的机器上编写的程序一般不能在其他型号的机器上运行），对编程人员要求高。,5.1.1 基本概念,汇编语言 用一些简单的助记符（约定的某些为人们易记忆和理解的符号）来描述指令（如加法指令用“ADD”，数字用10进制或16进制来表示），因此又叫作“符号语言”。一般情况下，汇编语言的指令和机器语言的指令是一一对应的。 宏汇编指令 一条宏汇编指令可以代替若干条机器指令。同机器语言的指令相比，汇编语言指令的含义比较直观，也易于阅读和理解。 计算机并不能直接识别和执行汇编语言的指令，必须将它们翻译成机器语言指令，计算机才能执行；把汇编语言程序翻译成机器语言程序的程序为汇编程序（Assembler），而称翻译前的程序为汇编语言源程序，称翻译后的程序为目标程序。,5.1.1 基本概念,低级语言 更接近于计算机的逻辑，而不是人类思维的过程描述。 高级语言 是为普通用户使用而设计的程序语言，比较接近自然语言和数学语言，对机器依赖性低，在一定程度上与具体机器无关，即适用于各种机器的计算机语言。 易学、易用、易维护。 用变量名代替了存储单元的地址，不必由人们直接分配地址和管理存储空间。 程序具有可移植性。 不能被计算机硬件直接识别，需要翻译成机器可执行的目标代码后方可执行。,5.1.1 基本概念,编译程序把高级语言所写的程序作为一个整体进行处理，将高级语言指令一次翻译为机器语言组成的可执行代码文件，即编译程序生成独立可执行的目标代码。编译后与子程序库链接，形成一个完整的可执行程序。,解释程序对高级语言程序将源程序逐句分解为最低级的机器语言代码并执行，而不产生目标程序。 解释方式便于查找错误，但效率较低。,4. 编译程序和解释程序,5.1.1 基本概念,伪代码 当编写的程序并不完全生成可执行的目标代码，而由计算机内部产生中间代码(程序员无法看到)被称为伪代码。伪代码保留在内存中，等待用户或程序员的执行调用。可执行的目标代码最后被执行，但并不保留在内存中。所有程序，即使它们有EXE扩展名，也都必须使用解释程序或编译程序来运行（如VB）。,5.1.1 基本概念,5. 程序理论 研究程序的语义性质和程序设计及开发方法的理论。 主要包括程序语义理论、数据类型理论、程序逻辑理论、程序验证理论、并发程序设计理论和混合程序设计理论。 程序理论(theory of programs)和算法理论是计算机科学的两大支柱。 程序理论研究程序的规约、变换和验证，基本问题是如何建立一个相对完善的理论框架，为软件的设计和开发方法提供理论依据。这个框架应能提供有效地描述程序规约的语言；应能定义可操作的变换方法以便能规约构造可执行的程序；应能给出验证程序与其规约之间一致性的机制。,5.1.1 基本概念,6. 程序设计语言语义 用数学方法刻画程序语句的加工过程，并将其执行结果形式化。也叫形式语义。 分为四类: 操作语义，模拟程序执行中计算系统的操作过程。 指称语义，把程序作为论域间的泛函以便刻画程序的执行数学结果。 公理语义，用公理化方法刻画程序与被加工数据的逻辑关系。 代数语义，把程序执行的结果定义为满足某种公理体系的代数结构。 在高级语言中广泛使用的过程说明和过程调用的精确概念和实现机制，就是在语义理论的研究中逐步明确的。 ALGOL60是第一个明确区分语法和语义的程序设计语言。,5.1.1 基本概念,7. 并发程序 包含多个没有因果关系进程的程序。 进程间的通信、同步和它们的并行执行是并发程序区别于顺序程序的基本操作。 计算机科学中的并发概念是由 Petri 在1962年提出的。 20世纪70年代初期，为了保证在操作系统中多个并行执行进程的正确性，导致了并发程序理论的产生。 进入80年代以来，随着超大规模集成电路技术的日臻成熟，并行和分布计算机系统得到了迅速发展，成为程序理论的一个重要分支。 并发程序理论研究的内容包括：并行进程的描述（用代数方法），并行进程的相互模拟，各种通信及同步机制以及死锁及活性，可观察性和发散性等并发现象。,5.1.1 基本概念,8. 程序设计(programming) 设计、编制和调试程序的方法与过程，是目标明确的智力活动。 程序设计的分类: 按结构性质，有结构化（具有由基本结构构造复杂结构的层次性）与非结构化程序设计之分 按用户要求，有过程式与非过程式程序设计之分 按程序的成分性质，有顺序、并发、并行和分布式程序设计之分 按设计风格，有逻辑式、函数式和对象式程序设计之分，三者的设计基本构件分别为逻辑子句、函数和对象类。,5.1.1 基本概念,9. 程序设计语言 用于书写计算机程序的语言。 语言的基础是一组记号和一组规则。根据规则由记号构成的记号串的总体就是语言。 程序设计语言(programming language)包含三个方面，即语法、语义和语用。语法表示程序的结构或形式，亦即表示构成语言的各个记号之间的组合规则，但不涉及这些记号的特定含义，也不涉及使用者。语义表示程序的含义，亦即表示按照各种方法所表示各个记号的特定含义，但不涉及使用者。语用表示程序与使用者的关系。 程序设计语言的基本成分包括： 数据，用以描述程序中所涉及的数据； 运算，用以描述程序中所包含的运算； 控制，用以表达程序中的控制构造； 传输，用以表达程序中数据的传输。,5.1.1 基本概念,程序设计语言的分类 按照语言级别 低级语言与高级语言 按照用户要求 过程式语言（如FORTRAN、COBOL、 ALGOL60）和非过程式语言，非过程式语言用户无法明确 表示计算过程的一组可顺序执行的运算（如PROLOG） 按照应用范围 通用语言（非单一目标，如FORTRAN、 COBOL、ALGOL60）和专用语言 按照使用方式 交互式语言（具有反映人机交互作用的语 言成分，如BASIC）和非交互式语言（如Pascal、C） 按照成分性质 顺序语言、并发语言和分布语言。 传统的程序设计语言大都以冯诺伊曼式的计算机为设计背景，因而又称为冯诺伊曼式语言。J.Backus于1977年提出的函数式语言FP则以非冯诺伊曼式的计算机为设计背景，因而又称为非冯诺伊曼式语言。 20世纪80年代，在结构化程序设计方法的基础上，提出了面向对象的程序设计方法。相应产生了面向对象的语言。典型的面向对象的语言有C+，Delphi等。,5.1.1 基本概念,10. 程序设计方法学(programming methodology) 以程序设计方法为研究对象的学科。 程序设计方法可以分为两类。一类是全局性的，如结构化程序设计方法。它不仅要求编出的程序结构良好，而且要求程序设计过程是结构化、层次式、逐层降低抽象级别的；另一类则是局部性的，如子例程方法、协同例程方法等。,5.1.2 程序设计语言的发展,1. FORTRAN(FORmula TRANslation)语言 IBM公司1956年创立的世界上第一个高级程序设计语言，一种面向过程的非常适合于科学计算的语言。它已经具有相当完善的工程设计计算程序库和工程应用软件。 FORTRAN支持一些最常用的编码方式，如算术表达式、逻辑运算、过程调用、循环和条件等等，提高了程序员的编程效率。第一个FORTRAN语言标准称为FORTRAN66 70年代修订为FORTRAN77，分全集和子集。 1991年国际标准化组织又批准了新的FORTRAN标准，称为Fortran90(规定F后面的6个字母用小写),它是国际上第一个支持多字节字符集的标准，该标准采纳了我国FORTRAN工作组关于CHARACTER(KIND=，)的建议。 新一代高性能FORTRAN (HPF)正在设计中。HPF的目标是支持并行程序设计；能在SIMD或MIMD机上获得较高性能；易于在不同体系结构的计算机之间移植其目标代码；扩充数据分布特性和并行语句。,5.1.2 程序设计语言的发展,2. ALGOL(ALGOrithmic Language)语言 1958年在苏黎世举行的一次ACM和GAMM（欧洲小组）的联合会议上，关于算法表示法的建议被综合为ALGOL，又称ALGOL 58。 “关于算法语言ALGOL 60的报告” 是程序设计语言发展史上的一个里程碑，是程序设计语言由技艺转向科学的重要标志。ALGOL是一种用日常英语以及与常用数学表达式相近的形式表现算法的语言，没有输入输出语句，全部以过程的形式进行描述，以块结构为基础。 ALGOL的主要特点有：首次引进局部性概念，既扩充了语言的表达能力，又节省了内存空间；语言含有动态成分，从而明显提高了语言的表达能力，不过实现中的系统开销也明显增加；递归性的引进开拓了软件的研究领域，促进了软件的发展；语法和语义均有严格描述，语法的描述采用巴科斯形式体系(BNF)，结构清晰，理论严谨。 ALGOL60的国际标准于1984年公布(IS01538:1984)，全名为Programming Language ALGOL60。,5.1.2 程序设计语言的发展,3. COBOL(COmmon Business Oriented Language)语言 一种用于事务处理的通用程序设计语言。1959年Grace Murray Hopper开始，同年5月，成立CODASYL，要求面向用户，面向问题，与机器无关，用简单英语或类英语表示，并尽可能避免符号化。 1960年4月，COBOL 60。COBOL最早应用于事务数据处理，并使用文件、记录、组项、初等项的数据描述方法。 COBOL语言将其核心和功能模块均分成若干级，故可以灵活地构造功能上具有积木式的但又是标准的适用于不同层次的语言实现系统，从而适应不同行业的实际需求。 COBOL程序由4个部组成：标识部用于刻画程序的标识性特征；环境部用于刻画程序和计算机环境有关的成分；数据部用于刻画数据(包括文件、记录、组项和初等项等)定义的构成以及相关特征和属性；过程部用于刻画处理加工流程，采用节、段、语句的结构层次。 目前的COBOL国际标准版本是ISO COBOL 1989-1985。直到今天，仍然有许多用COBOL编制的程序在大型机上运行。,5.1.2 程序设计语言的发展,4. LISP(LISt Processing)语言 用于处理被称为“表”的特殊数据集的函数式程序设计语言，J.McCarthy于1960年创立。在人工智能领域内曾被广泛使用。 LISP的主要特点： 程序的通常形式是一串函数定义，其后跟着一串带有参数的函数调用，函数之间的关系只是在调用执行时才体现出来。LISP中没有语句概念，也没有分程序结构或其它语法结构。语言中的一切成份都是以函数的形式给出。 在标准LISP中只有很少几个原始函数，虽然现有的LISP系统已增加了大量的内部函数，但这些新增加的函数都可以用最初的原始函数来表示。 在LISP中，程序和数据在形式上是等价的。LISP的唯一数据结构是S表达式(表)，而程序本身也是用S表达式写的，因此可以把程序当作数据来处理，也可以把数据当作程序来执行。 递归是LISP的基础，是语言的主要控制结构，它不象大多数程序设计语言那样以迭代(循环)作为主要的控制结构。LISP的递归处理是基于递归定义的数据结构。,5.1.2 程序设计语言的发展,5. BASIC(Beginners All-purpose Symbolic Instruction Code) 最简单易学的交互式高级程序设计语言。 由美国Dartmouth学院数学系的Thomas E.Kurtz和John.G.Kemeny两位教授于19631964年间开始研制，1964年正式推出。 广泛应用于数值计算、数据处理、实时控制、绘图、游戏等多种领域。 1978年美国发布最小BASIC国家标准(ANSI X3.60-78)，1984年又被定为国际标准(IS0 6373-84)，1987年美国发布全BASIC国家标准(ANSI X3.113-87)。我国于1991年发布了BASIC子集国家标准(GB 12856-91)。 Microsoft于1991年推出VB（Visual Basic）语言，称为“可视化BASIC”，是重要的多媒体编程工具语言。它是以结构化BASIC语言为基础，以事件驱动作为运行机制的新一代可视化程序设计语言。VB既保留了BASIC语言简单易用的优点，又充分利用了Windows提供的图形环境。,5.1.2 程序设计语言的发展,6. PASCAL(Philips Automatic Sequence CALculator)语言 世界上第一个结构化程序设计语言, 简明、结构化。 PASCAL语言的主要特点是： 丰富的数据结构和构造数据结构的方法，除了整型、实型、布尔型和数组外，还提供了字符、枚举、子域、记录、集合、文件、指针等类型，由这些数据结构可以方便地描述各种事务元； 简明灵活的控制结构，其结构语句包括：复合语句、如果语句、情况语句、While语句、Repeat语句、For语句和处理记录变量分量的缩写形式With语句； 编译运行效率高； 有利于书写程序设计语言的编译程序。 BSI(英国标准化学会)于1982年正式出版了PASCAL语言的英国标准（BS 6192，即ISO 7185），Specification for Computer Programming Language PASCAL。我国于1987年正式生效的国家标准(GB 7591-87)，全名为程序设计语言PASCAL。1993年ISO又公布了有关修订标准（ISO/IEC 7185:1990）。 1983年，Borland公司创始人Philippe Kahn和Anders Hejlsberg，合作研制了Turbo Pascal。,5.1.2 程序设计语言的发展,7. PROLOG(PROgramming in LOGic)语言 一种处理逻辑问题的逻辑程序设计语言。曾广泛用于关系数据库、数理逻辑、抽象问题求解、自然语言理解等多种领域。 1972年前后，英国的Kowalski和法国的Colmeraur提出“逻辑可用作程序设计语言”这一基本思想，PROLOG这一语言也被提出来了。 20世纪80年代初，日本曾将PROLOG语言定为第五代计算机的核心语言。曾在PC上流行的Turbo PROLOG是美国Borland公司1986年推出的。无论是功能还是运行速度，此编译程序都很成熟，使用它可生成任一实际应用原型，实现动态关系数据库，建造专家系统和专家系统工具，完成语言翻译，形成同现有软件的自然语言交互，解方程，求微积分，设计智能软件，管理工业过程以及作情报检索等。 PROLOG语言的主要特点有：使用事实和规则；不作初始说明，而由一张逻辑语句表组成；可作演绎；程序的执行是自动控制的；程序具有回溯机制；有一内部模式匹配机制；允许交互式程序开发。,5.1.2 程序设计语言的发展,8. C语言 兼有低级语言和高级语言的功能，被人们称为中级语言。 C语言表达式简洁，运算符及控制结构和数据结构都很丰富，适合于各种应用场合。 由AT&T公司Bell实验室的Dennis Ritchie在DEC PDP-11的UNIX系统环境下完成的。 Turbo C是美国Borland公司在IBM PC机上实现的C编译程序。 C语言曾广泛用于研究、开发与教学，主要用于系统程序设计，是一个功能强大的编程语言，最初因被用于开发UNIX系统而闻名于世。 1983年美国国家标准学会(ANSI)开始进行C的标准化工作，以美国国家标准ANSI C为基础的国际标准化工作始于1985年(ISO/IEC JTCl/SC22 WG14)，于1990年正式公布（ISO/IEC 9899），是第一个支持多八位字符集的程序设计语言国际标准。我国国家标准等同采用了ISO/IEC 9899。,5.1.2 程序设计语言的发展,9. Ada语言 Ada是一种通用的模块化程序设计语言,主要特征是强类型化和模块化，便于实现分别编译，提供类属设施与异常处理，适于嵌入式应用。Ada有通用控制结构，有定义数据类型和子程序的能力，易于控制并行任务和处理异常情况。所以它可用于数值分析计算，系统程序设计，并满足实时和并行操作等要求。 在20世纪70年代初，应美国国防部为解决软件费用急剧增长的困境的要求产生 1980年7月 ，Ada语言手册出版，年末编译系统问世。1983年Ada语言被正式列入美国标准(ANSI/MIL 1815A-1983)，后来先后被批准为美国联邦标准和国际标准(ISO/IEC8652:1987-1992)。,5.1.2 程序设计语言的发展,10. C+语言 以C语言为基础、支持数据抽象和面向对象技术的通用程序设计语言，1983年推出。 1980年，在AT&T公司贝尔实验室计算机科学研究中心的Bjarne Stroustrup博士通过对C语言的扩充，开发出了被称作“带类的C语言”，1983年改名为C+。 C+保持了C语言紧凑、灵活、高效和易移植等优点，它对数据抽象的支持主要是类的概念和机制，对面向对象技术的支持主要通过虚拟函数来实现。,5.1.2 程序设计语言的发展,11. Java语言 简捷的、面向对象的、用于网络环境的、可在因特网上分布执行的程序设计语言。 由SUN MicroSystem公司于1995年5月正式对外发布。 “一次编译，到处运行”,适合于当前高速发展的网络环境的编程，也非常适合于交互式多媒体应用的编程。 Java语言具有的特点有： 简捷易学。 面向对象。 适用于网络分布环境。 解释执行和多线程。 安全可靠。,5.2 程序设计语言的基本成分与使用,数据及其运算 函数与过程的定义 程序设计语言的功能与使用 程序运行的控制与环境,5.2.1 数据及其运算,1. 常量 在程序运行其间保持不变的值。E.g.，圆周率3.14。 常量也有数据类型，因此可以有数值型常量、字符串常量、布尔型常量。 2. 变量 在程序执行过程中，变量的值是可以改变的。变量用来临时存储信息，包括输入数据或计算结果，代表一定的内存空间。 高级语言中，一般将一个有名称的内存单元称之为变量，即变量代表着计算机内存中指定的存储单元。 变量使用前要对其命名和进行变量说明。习惯上变量的命名称之为定义，变量类型的说明（即变量储存方式的说明）称之为说明。 变量的数据类型决定一个变量可以存储什么样的信息：数值型变量用来存储数值；字符串变量用来存储一串字符。 在实际编程中，不同类型数据既可以以常量的形式出现，也可以以变量的形式出现。,5.2.1 数据及其运算,3. 变量的命名 每个变量都有一个名字。变量命名遵照见名知义的原则，一般有以下的规则: (1) 变量名必须以字母开头； (2) 变量名所用的字符只能由字母、数字及 下划线组成，不能含有标点符号及空格 等字符； (3) 变量名的字符数目有限； (4) 每种程序设计语言都有自己的保留字或 关键字，不能用保留字做变量名。,5.2.1 数据及其运算,4. 运算符和表达式 运算即对数据进行加工的过程。 描述各种不同运算的符号称为运算符。 运算中由常量、变量、运算符、对象和圆括号按一 定的规则组成的运算式称为表达式。 每一个表达式产生一个运算结果，运算结果的数据 类型由数据和运算符共同决定。 运算符按功能可分为以下三种类型： 算术运算符 关系运算符 逻辑运算符 上述三类运算符的执行顺序是：算术运算符优先级 最高，关系运算符次之，逻辑运算符最低。,5.2.1 数据及其运算,4. 运算符和表达式 算术运算符: 用来进行算术运算，含加（+）、减（-）、乘（*）、除（/）等。 一般幂运算的优先级最高，其余运算的优先级顺序是：取负(-)、乘法或除法或整除、取模、加法或减法，其中，乘法和除法是同级运算符，加法和减法是同级运算符。 当一个表达式中含有多种算术运算符时，必须严格按上述顺序求值。同一表达式中若有两个优先级相同的运算符，则运算顺序由左向右。 如果表达式中含有括号，则先计算括号内表达式的值；有多层括号时，先算内层括号里表达式的值。,5.2.1 数据及其运算,4. 运算符和表达式 关系运算符: 用来比较两个运算数据的大小。关系运算就是将两个数进行“比较”的运算。 包括：等于（=）、大于（）、小于（=）、小于等于（=）、不等于（!=）。因此，关系运算符也称比较运算符，都是同级运算符。 关系运算的结果是一逻辑值：True(真)或False(假)。,5.2.1 数据及其运算,4. 运算符和表达式 逻辑运算符: 逻辑与又称为逻辑乘（& 或and）、逻辑或又称为逻辑加（| 或or）、逻辑非（! 或 not）等等，用来将操作数进行逻辑运算，结果是逻辑值True(真)或False(假)。 优先级顺序是：逻辑非优先级最高，逻辑加最低（可记为NOT-AND-OR）。 将关系表达式或逻辑量（常量、变量）用逻辑运算符连接起来的式子称为逻辑表达式或布尔表达式。 所有计算机的处理都是逻辑求值的结果，被称为二进制运算，因为它们的结果只有两个状态：True或False。,5.2.1 数据及其运算,5. 基本语句 每一种语言都规定了有限的词汇，并按规定的语法构成语句。语句构成计算机程序。 在程序设计语言中可以单独占据一行的指令称为短语(phrase)。 程序设计中的子句(或语句)是说明程序操作状态变化的指令，是告诉解释程序或编译程序如何运行程序的指令。 E.g. If R 0 Then Text2=2*3.14*R 单词If、Then是所有BASIC程序设计语言的基本关键字。 这条指令可以正确地作为BASIC语言的一个短语，由三个子句组成，它们都在一行内，因此这种短语也称为复合指令。 其中，关系表达式“R 0 ”是一条件子句；If-then和Text2的赋值被认为是子句，是因为它们说明了程序操作状态的变化。,5.2.2 函数与过程,函数与过程是完成特定功能的标准程序段。 在高级语言中函数与过程均为一个程序单位，二者亦可统称为子程序（对应低级语言中的子例程）。 一旦定义，便可在一定范围内多次调用，从而避免了相同或相似的程序段在程序中多次出现。 每一种语言都定义了许多函数，通常分类存放，构成函数库（Java语言称做包）。 函数的计算结果叫做返回值。返回值有三种类型：数值、字符串或布尔值。,5.2.2 函数与过程,用来定义计算过程的程序单位，称为子程序定义或子程序说明；用来使用该计算过程的调用语句，称为子程序调用。 函数与过程都是通过定义中的形式参数与调用中的实在参数传递与外部环境发生联系。 函数定义需指出通过函数名返回的函数值与类型，其值通过函数调用出现在表达式中。 过程调用往往以单独语句的形式出现，没有显式地立即回送计算值的功能。 子程序定义中的形式参数（简称形参）与子程序调用中的实在参数（简称实参）要在个数、顺序、类型上保持一致。,5.2.2 函数与过程,参数传递的5种方式 值参传递：形参等同于子程序的一个局部变量，其初值为调用时的实参值。对形参的赋值不影响调用程序。 变参传递：形参等同于子程序的局部变量。当调用返回时，此形参的内容赋给相应实参，这里的实参必须是变量。 值/变参传递：形参等同于子程序的局部变量，其初值为调用时的实参值。返回时，如果实参为变量，则把形参的内容赋给此实参。实参变量在调用前被定义，或在返回前被重定义。 引用（或地址传递）：子程序内形参的所有操作均通过对其实参的引用来执行。 名：计算引用实参的无参过程P被传递到子程序，对形参的操作变为先调用P，然后通过由P产生的引用进行操作。 在函数与过程的定义体部分若出现直接或间接地调用它自身时，则称此函数或过程是递归定义的。,5.2.3 语言的功能和使用,程序设计语言的功能 数据描述：对数据进行分类，如整型、浮点型、字符串型、指针型等，并规定每类数据的存储、使用及表示方式。 操作运算：直接或间接地提供某些种类的运算。如算术、关系、逻辑、字符串运算及函数。 程序控制：提供程序的顺序、选择、循环以及其他控制的实现机制。 数据传递：提供不同种类数据的传输方式。如赋值语句将运算结果从运算器送入存储器，读语句将内存数据区中的数据读到变量所代表的内存单元中，输入语句将从键盘输入的数据存入内存单元，输出语句将内存或运算器中的数据传送到显示器或打印机。,5.2.3 语言的功能和使用,程序设计语言的使用 编程 即把已经设计好的算法改写成用某一种程序设计语言所编写的源程序。 录入和编辑 编译 源程序一般是不能直接执行的，应先把源程序编译为目标程序。经编译得到的目标程序还可能要进行一些链接或装配工作（将不同的程序单位以及库程序连接起来，装配成一个可供执行的目标程序块）。链接和装配工作在有的系统中由编译程序自动进行，如PASCAL，有的系统则需单独进行，由连接程序连接，如FORTRAN。 执行 经编译及连接得到的可执行程序便可执行了。程序的运行除计算机外还需要两方面的支持：一是操作系统，二是程序所需的数据。 在程序运行过程中如果有错误，包括语法错误、逻辑错误、输入数据错误（称为“运行错误” ），程序人员根据编译和运行的情况不断地修改程序，直到最后得到正确结果为止，这个过程称为“调试程序（debugging）”。解释型语言是边解释边执行的，因此，上述过程中的“编译”和“执行”步骤是同时进行的。,5.2.4 程序运行的控制和环境,计算机可以同时运行多个程序。 计算机的控制程序（操作系统）为需要运行的程序提供系统资源和相关的服务。,5.3 算法和基本数据结构,韦氏新世界词典中，算法(Algorithm)被定义为“解某种问题的任何专门的方法” 。 一般教科书中，算法是指解题步骤的准确而完整的描述，“是一组严格定义了运算顺序的规则，每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止”。 计算机程序设计的艺术中“一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型问题的运算序列”,5.3 算法和基本数据结构,计算机解决实际问题的过程 明确问题要求 建立数学模型和确定计算方法 设法用数学方法来描述或模拟实际问题。对错综复杂的实际问题进行简化抽象，并用合理的数学公式来描述的过程，称为建立数学模型的过程。 算法设计 按所确定的数学模型及计算方法设计出解题步骤称为算法设计。设计过程中要用算法描述工具将算法描述出来。 编写程序 程序是用计算机语言描述的算法。 调试程序及结果分析,5.3.1 算法的概念,算法的形式化定义 算法是一个四元组，即( Q，I，F )。其中： Q 是一个包含子集I 和的集合，它表示计算的状态； I 表示计算的输入集合； 表示计算的输出集合； F 表示计算的规则，它是一个由Q 到它自身的函数， 且具有自反性，即对于任何一个元素qQ,有F(q)q。 一个算法是对于所有的输入元素x，都在有穷步骤内终止的一个计算方法。在算法的形式化定义中，对于任何一个元素xI，x均满足性质： x0x，xk+1F(xk)，( k0 ) 该性质表示任何一个输入元素x均为一个计算序列，即xo、x1、x2、xK。表示该序列在第k步结束。,5.3.1 算法的概念,算法的特性 有效性(Effectiveness) 确定性(Definiteness) 有穷性(Finiteness) 有零个或多个输入(Input) 有一个或多个输出(Output),5.3.1算法的概念,Example 1 有两个变量和,要求将它们的值互换。例如:=3,=5；互换后=5，=3。可以有两种算法实现两个变量的值互换。 算法1，引入一个辅助变量C作为过渡进行交换；算法2，不引入辅助变量，仍用三个步骤完成交换。算法表示如下： 其中，“”代表赋值操作；用S1，S2，S3表示步骤的次序(S是Step的首字母)，在写算法时常用这种形式的标记。两种算法都通过三个步骤实现了值的交换，但显然算法1的可读性要比算法2好，程序设计中经常使用。,算法1： S1：（将变量A的值赋给变量C）； S2：（将变量的值赋给变量A）； S3：（将变量C的值赋给变量B）。,算法： S1：； S2：； S3：。,5.3.1算法的概念,Example 2 求解斐波那契数( 0,1,1,2,3,5,8,13,21,34,)。数列中每个数都是它的前两个数之和。若用Fn表示这个数列的第n个数，则该数列可以形式化地定义为： 00，11，n+2n+1n，n 设变量、分别表示定义中前一个数的值（n）、当前数的值（n+1）和后一个数的值（n+2）。那么求解问题的算法可以描述如下： -,(1) 如果n0，则0，输出结果Y，转步骤执行； (2) 将0，输出X、Y； (3) I； (4) 如果I大于n-1,则转到步骤,否则继续执行； (5) ，； (6) 将Y输出； (7) ，转步骤继续执行； (8) 算法结束。,5.3.2 算法的表示方法,自然语言 人们比较容易接受。 但自然语言具有许多缺点。首先，自然语言有时具有歧义性，容易导致算法执行的不确定性；用自然语言描述的算法比较冗长，不简洁；自然语言的表示形式是顺序的，在描述分支和转移时不直观。另外，自然语言表示的算法不便翻译成计算机程序设计语言理解的语言。,5.3.2 算法的表示方法,流程图 流程图是算法描述的图形工具，采用ANSI规定的一组图形符号来表示算法，用一些几何图形表示各种类型的操作。 流程图可以很方便地表示顺序、选择和循环结构，而任何程序的逻辑结构都可以用顺序、选择和循环结构来表示，因此，流程图可以表示任何程序的逻辑结构。另外，用流程图表示的算法不依赖于任何具体的计算机和计算机程序设计语言，从而有利于不同环境的程序设计。,5.3.2 算法的表示方法,例: 存在一个长度为n的字符串，串中元素互不相同。编写一算法，确定字符e在字符串中的位置。分析：把字符串看成一个序列，结点类型为字符型。选用顺序存储方式表示，采用数组An存储这个字符串，用i表示e在数组的位置。,5.3.2 算法的表示方法,流程图 用流程图来描述算法比较方便、直观。 流程图的主要缺点： 本质上不是逐步求精的好工具，它会使人过早地考虑算法的控制流程，而不去考虑算法程序的全局结构； 不易表示算法的层次结构； 不易表示数据结构和模块调用关系等重要信息； 用箭头代表控制流，控制转移随意性很强，不符合结构化程序设计的思想。 流程图的结构随着问题规模和复杂程度的增加会变得很复杂，使人难以阅读、理解和修改，从而使算法的可靠性和可维护性难以保证。,5.3.2 算法的表示方法,N-S结构流程图 1973年美国学者纳斯（I.Nassi）和施内徳曼（B.Shneiderman）提出。 独立于任何计算机和计算机语言，但是又能很方便地转换成任一种计算机语言程序。 完全去掉了在算法描述中引起麻烦的流程线，全部算法写在一个大的矩形框内，用不同结构的框来表示结构化程序设计中的三种基本控制结构。 N-S图像一个多层的盒子，也称为盒图（box diagram）。,5.3.2 算法的表示方法,N-S结构流程图,顺序结构：A和B可以是基本操作（如加、减、乘、除运算，打印，赋值等），也可以是其他基本结构（例如选择结构、循环结构）。,选择结构：表示当P0条件成立时执行A操作，P0条件不成立时执行B操作。,5.3.2 算法的表示方法,N-S结构流程图,循环结构：分为当型循环与直到型循环。 当型循环见左图。其含意为：当P1条件成立时执行A操作，然后再返回判断P1条件是否成立，如成立再执行循环体A。如此重复下去，直到P1条件不成立时为止。 直到型循环见右图。其含意为：先执行循环体A，再判断P2条件是否成立，如不成立则返回再执行循环体A。如此重复下去，直到P2条件成立时为止。,5.3.2 算法的表示方法,N-S结构流程图 N-S结构流程图所具有的优点：能够保证流程图是由三种基本结构顺序组成的，则它必然是结构化的；画N-S图比画传统流程图容易而且节省篇幅；N-S图阅读起来直观、明确，容易理解。 N-S图的基本特点是：功能域比较明确，可以从框图中直接反映出来；不可能任意转移控制，符合结构化原则；很容易确定局部和全程数据的作用域；很容易表示嵌套关系，也可以表示模块的层次结构。,5.3.2 算法的表示方法,伪代码 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此，书写方便，格式紧凑，易于理解，便于向程序设计语言算法(程序)过渡。 求解斐波那契数的算法用伪代码描述如下： BEGIN(算法开始) If n = 0 0 Y Print Y Else 0 X 1 Y Print X, Y For ( i=1；i=n-1；i+ X + Y Z Y X Z Y Print Y END(算法结束),5.3.2 算法的表示方法,程序设计语言 程序设计语言是计算机能够接受、理解和执行的算法描述工具。 程序设计语言离人们掌握和习惯使用的语言最远，算法的基本逻辑流程难于遵循，程序要求描述计算步骤的细节，而忽视算法的本质。 程序设计语言也是基于串行的，不直观，对于较复杂的问题，很难直接写出程序。而且人们要花费大量的时间去熟悉和掌握某种特定的程序设计语言。 在算法设计阶段，一般采用先用专用工具来描述算法，之后再转换成程序的方法。作为例，右边给出用C语言求解斐波那契数的算法描述。,5.3.3 算法设计的基本方法,对于大型或复杂问题，可以采用“自顶向下，逐步细化”的方法。 高层设计中，首先要对问题进行分析，将问题严格分类，对不同的问题采用不同的方法。对大型问题，一般采用分割技术或分治策略，将一个问题划分为若干独立的子问题。如果可能，子问题仍可继续分解，直到每个子问题都比较容易处理为止，然后再着重设计解决每个子问题的详细算法。 低层设计中，可以采用递推或递归技术，或采用穷举等策略使算法具体化。,5.3.3 算法设计的基本方法,常见的算法设计方法 回溯法通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探，如八数码问题。 归纳法通过列举少量的特殊情况，经过分析，最后找出一般的关系。,5.3.3 算法设计的基本方法,常见的算法设计方法 递推法指从前面一些量可以依次推出后面一些量的算法，从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。递推常常表现为迭代，即由一个变量的原值推出它的新值，或者说，不断地用一个新值去代替变量的原值。原值与新值之间存在一定的关系，这种关系可用迭代公式来表示。 递归法将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题，这个过程可以一直做下去，逐步求精，直到最简单的问题为止。,5.3.3 算法设计的基本方法,列举法（穷举法） 常用于解决“是否存在”或“有多少种可能”等类型的问题。 根据提出的问题，列举所有可能的情况，并用问题中给定的条件进行检验和判断。 Example： 用C语言程序输出1000以内所有的“完数”（完数：即它的各因子之和等于该数本身的数称为完数）。要求程序运行后输出结果为： 6=1+2+3 28=1+2+4+7+14 496=1+2+4+8+16+31+62+124+248,5.3.3 算法设计的基本方法,5.3.3 算法设计的基本方法,减半递推法 减半，是指将问题的规模减半，而问题的性质不变。 递推，是指重复“减半”的过程。 Example： 二分法求方程实根的减半递推过程： （1） 取给定区间（a,b）的中点c(ab)/2； （2） 判断f(c)是否为0。若f(c)0,则说明c即为所求的根，求解过程结束； （3） 如果f(c)0,则根据以下原则将原区间减半： 若f(a)f(c)0，则取原区间的前半部分； 若f(b)f(c)0，则取原区间的后半部分。 （4） 最后判断减半后的区间长度是否已经很小： 若|ab|，则过程结束，取(ab)/2为根的近似值； 若|ab|，则重复上述的减半过程。,5.3.4 基本数据结构,数据结构(Data Structure)的概念 数据结构通过研究数据的逻辑结构和存储结构以及在各种数据结构之上所能进行的运算，来达到“提高数据处理效率”的目标 。 数据结构是指相互有关联的数据元素的集合，现实世界中客观存在的一切个体都可以是数据元素。 数据结构由数据的逻辑结构、存储结构(或称物理结构)及其运算三部分组成。,5.3.4 基本数据结构,数据结构的概念 数据的逻辑结构反映数据元素之间的逻辑关系，可形式化地定义为：DS=D,R D：数据元素的集合 R：在D上各数据元素之间关系的集合 Example: 一周七天的数据结构可表示为： Group=(D，S) D= 星期一，星期二，星期三，星期四，星期五，星期六，星期日 S=， ， ,5.3.4 基本数据结构,数据结构的概念 数据的存储结构是指在反映数据逻辑关系的原则下，数据在存储器中的存储方式，即数据的逻辑结构在存储空间中的存放形式。 数据的存储结构分为顺序存储结构和链式存储结构两种，其中前者借助数据元素在存储器中的相对位置来表示其逻辑关系，而后者借助指针来表示数据元素之间的逻辑关系，一般通过在数据元素上增加一个或多个指针类型的属性来实现这种链式存储结构的表示。,5.3.4 基本数据结构,数据结构的概念 如果用中间标有元素值的方框来表示数据集合D中的每一个数据元素（称为数据结点或结点），用一条有向线段连接前结点和后结点来表示两结点之间的关系，则数据结构就可以用图形（结点间的关系图）来表示。 按结点之间的连接关系，我们又将数据结构分为线性和非线性两种类型。线性数据结构有且只有一个根结点（启始结点），而且每个结点最多有一个前结点，也最多有一个后结点。线性结构又称线性表。如果一个数据结构不是线性结构，则称之为非线性数据结构。,5.3.4 基本数据结构,数据结构的概念 存储结构示例： A=(D，S) D=a，b，c，d，e S=， 设第一个结点的存储单元位置为1000，每一个结点所占的存储单元的个数为1。,顺序存储结构,链式存储结构,5.3.4 基本数据结构,线形表(Linear List)及其顺序存储结构 线性表是由n(n0)个数据元素a1，a2，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前结点，除了最后一个外，有且只有一个后结点。 线性表或是一个空表（n=0），或可以表示为(a1，a2，ai，an)，其中ai(i1，2，n)是属于数据集合D的数据元素，称其为线性表中的一个结点。n称为线性表的长度。 将可引用的最小的（不可再分的）命名数据单位称为数据项，在线性表中，由若干数据项组成的数据元素又称为记录(record)，由多个记录构成的线性表又称为文件(file)。,5.3.4 基本数据结构,线形表(Linear List)及其顺序存储结构 线性表的顺序存储结构的基本特点： 线性表中所有元