大学信息技术导论第.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 基本概念,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,.运算符和表达式,关系运算符:,用来比较两个运算数据的大小。关系运算就是将两个数进行“比较”的运算。,包括：等于（,=,）、大于（,）、小于（,=,）、小于等于（,1时，除根结点以外的其余结点可分成m(m 0)个,互不相交的,有限集合T1，T2，Tm。其中每一个集合,本身又是一棵树，并称其为根的子树(subtree)。,5.3.4 基本数据结构,树,树的结点包括一个数据元素及若干指向其子树的分支。,结点拥有的子树个数称为,结点的度(degree),。,树中所有结点的度的最大值称为该,树的度,。,度为0的结点称为,叶子结点,(leaf)或终端结点。,结点的子树的根称为该结点的,孩子结点(child),，该结点是其孩子结点的,双亲结点(parent),。具有同一双亲结点的孩子结点之间互称为,兄弟(sibling),。某结点的,祖先,是指从根结点到该结点所经分支上的所有结点。以某结点为根的子树中的所有结点都称为该结点的,子孙,。结点的,层次(level),从根开始算起，根为第一层，根的孩子为第二层，某结点所在的层从根开始向下计算。在树的同一层上而双亲结点不同的结点互为,堂兄弟,。树中结点的最大层次称为,树的深度(depth)或高度,。,5.3.4 基本数据结构,树,如果将树中结点的各个子树看成从左至右是有序的(即不能互换)，则称该树为,有序树,，否则称为,无序树,。,森林,(forest)是m(m0)棵互不相交的树的集合，树和森林的概念很密切，删去一棵树的根，就得到一个森林。,5.3.4 基本数据结构,树,树的基本操作包括：,TREEEMPTY(T),判树空。若T为空树，返回TRUE，否则返回,FALSE。,ROOT(T),求根。返回树T的根结点地址。若T为空树，返,回一特殊值。,TREEDEPTH(T),求树的深度。返回树T的深度。,VALUE(T,a),求a结点。a是树T中的结点，函数返回a结点地址。,PARENT(T,a),求a结点的双亲。a是树T中的结点，当a是非根结,点时，返回其双亲结点地址。,CHILD(T,a,i),求a结点的孩子。a是树T中的结点，函数返回a结,点的第i个孩子结点的地址。,CREATE(T,T,1,T,k,),建树操作。当k1，建立一棵以T为根，,以T,1,T,2,T,k,为第1,2,k棵子树的树。,5.3.4 基本数据结构,二叉树(Binary Tree),二叉树是n(n 0)个结点的有限集合。,n=0时为空集，称为空二叉树；,n0时，二叉树由一个根结点及两棵互不相交、分别,称 为左子树和右子树的二叉树组成。,二叉树和树的不同：二叉树中每个结点的度小于等于2，,而且二叉树的子树有左右子树之分。,二叉树的五种基本形态：,空二叉树；仅有根结点的二叉树；右子树为空的二叉树；左子树为空的二叉树；左右子树均非空的二叉树。,5.3.4 基本数据结构,二叉树的五种基本形态：,5.3.4 基本数据结构,二叉树(Binary Tree)的性质,性质1：二叉树第i层上的结点数目至多为2,i-1,(i1)。,性质2：深度为M的二叉树至多有2,M,-1个结点(M1)。,性质3：在任何一棵二叉树中，如果其终端结点数为,n,0,，度为2的结点数为n,2,，则n,0,n,2,1,5.3.4 基本数据结构,二叉树,二叉树的存储结构有顺序和链式两种存储结构。,二叉树的顺序存储结构就是用一组地址连续的存储单元来存放一棵二叉树的结点。必须要按规定的次序来存放，这种次序应能反映结点之间的逻辑关系(父子关系)，否则二叉树上的基本操作在顺序存储结构上难以实现。,二叉树的链式存储结构主要是设计结点结构。由二叉树的定义得知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个指针构成。因此链式存储二叉树的结点结构包括三个域：数据域和左、右指针域。这种存储结构称为二叉链表。一个二叉链表由头指针惟一确定。,5.3.4 基本数据结构,完全二叉树：,5.3.4 基本数据结构,完全二叉树的存储结构,5.3.4 基本数据结构,二叉树的链式存储结构,链式存储结构,5.3.4 基本数据结构,二叉树的,遍历：,遍历二叉树是指按某种规律周游二叉树，对树中的每个结点,访问一次且仅访问一次,。对二叉树的遍历过程是将非线性结构的二叉树中的结点排列在一个线性序列上的过程。访问每一个结点时可对结点作各种操作。,假如以L、D、R分别表示二叉树的左子树、根结点和右子树，则二叉树可有DLR，LDR，LRD，DRL，RDL，RLD六种遍历的方法。再限定先左子树后右子树，则可以将前三种方案称之为,先序遍历、中序遍历和后序遍历,。遍历左、右子树的规律和遍历整个二叉树的规律相同，因而上述三种遍历都具有,递归性,。,对同一棵二叉树，用三种不同的遍历规律所得到的结果都是线性序列，有且仅有一个开始结点和一个终端结点。但三个线性序列并不相同，因此必须指明序列的遍历规则。,5.3.4 基本数据结构,二叉树的,遍历：,三种遍历所得到的三个线性序列如下：,先序遍历二叉树序列：ABCDEGF,中序遍历二叉树序列：CBEGDFA,后序遍历二叉树序列：CGEFDBA,先序遍历二叉树的操作步骤（递归算法）：,若二叉树非空，则依次进行如下操作：,访问根结点；,先序遍历左子树；,先序遍历右子树。,void preorder(BTCHINALR*bt),if(bt!=NULL),printf(%c,bt-data)；,preorder(bt-lchild)；preorder(bt-rchild)；,5.3.4 基本数据结构,图（Graph）,图,G由两个集合V和E组成，记为G(V,E)。V是顶点的有穷非空集合；E是边的集合，边是V中顶点的偶对。若E为空，则G中只有顶点没有边。,在图中，数据元素通常称为,顶点(vertex),。若顶点之间的偶对是有方向的，称此图为,有向图(digraph),，有方向的偶对用尖括号括起来，并称之为,弧(arc),。如v,wV，E，则是有向图中从顶点v到顶点w的一条弧，v是,弧尾(tail),(始点)，w是,弧头(head),(终点)。,若顶点之间的偶对是无方向的，称此图为,无向图,(undigraph),，无方向的偶对用圆括号括起来，通常称之为,边(edge),。如x,yU，(x,y)E，则(x,y)是无向图中顶点x和顶点y之间的一条边。,5.3.4 基本数据结构,图,用n表示图中顶点的数目，e表示图中边或弧的数目。,n个顶点有1/2(n(n1)条边的无向图称为,无向完全图,。,n个顶点有n(n1)条弧的有向图称为,有向完全图,。,有时图的边或弧附有相关的数值，这种数值称为,权,(weight),。,权可以表示一个顶点到另一个顶点的距离、时间耗费、开销等。,每条边或弧都带权的图又称为,网络,(network),。,5.3.4 基本数据结构,图,无向图中，若顶点x与y之间有边(x,y)，则x,y互为邻接点，边(x,y)与顶点x和y相,关联,。,无向图中顶点x的,度,(degree)是和x相关联的边的数目，记为TD(x)。,有向图中，若是一条弧，则称,顶点v邻接到顶点w,，,顶点w邻接自顶点v,。有向图中顶点v的,入度,(indegree)是以顶点v为终点的弧的数目，记为ID(v)，顶点v的,出度,(outdegree)是以顶点v为始点的弧的数目，记为OD(v)，顶点v的,度,记为TD(v)ID(v)OD(v)。,无论是无向图还是有向图，其,边数(或弧数)e都等于图中所有顶点Vi的度（TD(Vi)，i=1,n,n=图的顶点数）之和的二分之一,。,5.3.4 基本数据结构,图,设G(V,E)是一个图，G(V,E)也是一个图，如果V是V的子集，E是E的子集，且E中的边仅与V中顶点相关联，则称G为G的,子图(subgreph),。,5.3.4 基本数据结构,图,无向图G=(V,E)若存在一个顶点序列x=vi0,vi1,vi2,vin=y，其中，(vi0,vi1)E,(vi1,vi2)E,(vin-1,vin)E，则称顶点x到顶点y存在一条,路径(path),。若G是有向图，则路径也是有方向的，其中，,E。路径上的边或弧的数目定义为,路径长度,。路径序列中顶点不重复出现的路径称为,简单路径,。路径中第一个顶点和最后一个顶点相同的路径称为,回路或环(cycle),。简单路径中第一个顶点和最后一个顶点相同，该简单路径称为,简单回路,。,无向图中，如果顶点x到顶点y有路径，则称x和y是,连通,的。如果无向图中任意两个顶点Vi,VjV，Vi和Vj都是连通的，则称该无向图为,连通图,，否则称为,非连通图,，非连通图含有连通分量，非连通图中的极大连通子图定义为,连通分量,。连通图的连通分量就是其本身的图。,5.3.4 基本数据结构,图有两种常用的存储方法：邻接矩阵和邻接链表。,图的,邻接矩阵,适用于无向图和有向图，是表示图中顶点之间相邻关系的n阶方阵。设G(V,E)是一个图，含有n个顶点，则其邻接矩阵可表示为：,5.3.4 基本数据结构,邻接链表,是图的链式存储结构，适用于无向图和有向图。在邻接链表中，对图中的每个顶点建立一个单链表。单链表有一个表头结点。邻接链表将所有表头结点组成一个二维数组。,5.3.4 基本数据结构,图的遍历：,从图中某顶点出发对图中每个顶点访问一次，且仅访问一次，这一过程称为,图的遍历,(traversing graph)。有两种方法：,深度优先搜索,和,广度优先搜索。,5.4 结构化程序设计,结构是指系统内各组成要素之间的相互联系，相互作用的框架。,结构化方法(structured method)是强调开发方法的结构合理性以及所开发软件的结构合理性的软件开发方法。,5.4.1 程序基本控制结构,结构化程序设计限制三种基本控制结构：,顺序,结构 语句组中的语句按排列的顺序依次执行。,分支,结构 按照给定的条件进行判断，选择执行程序,中不同的语句组。,循环,结构 按照给定的条件重复执行语句组（也称为,循环体）。根据循环条件判断的先后。,基本控制结构所具有的特点：,只有一个入口；只有一个出口；对每一个框都有从入口到出口的路径通过；不包含死循环。,5.4.1 程序基本控制结构,任何复杂的问题，都可以用以下三种基本结构顺序地构成,5.4.2 结构化分析方法与设计方法,结构化分析,（Structual Analysis）,方法,结构化分析方法给出一组帮助系统分析人员产生功能规约的原理与技术。它一般利用图形表达用户需求，使用的手段主要有,数据,流图(DFD),、,数,据字典(DD),、,结构化语言,、,判定表,及,判定树,等。,特点：,分解和抽象；文档的规范化；面向用户；,系统的逻辑设计和物理设计分开进行,。,5.4.2 结构化分析方法与设计方法,数据流图,（Data Flow Diagram）,以图形的方式表达目标系统中信息的变换和传递过程。,四,个基本要素：,数据流、加工、文件、数据源和数据宿。,数据流,由一组固定成分的数据组成，它具有名字和流向；,加工,是对数据流的变换；,文件,是可访问的存储信息；,数据源和数据宿,是存在于计算机系统之外的实体，分别表明数据处理过程的数据来源及数据去向。,结构化分析方法采用,分层的数据流图,，,采用数据流图分解及抽象的手段，来控制需求分析工作的复杂性。,画数据流程图可采用自顶向下逐层分解、由外向里逐渐深化的方法。,5.4.2 结构化分析方法与设计方法,数据字典,（Data Dictionary）,对数据流图中出现的所有数据元素给出逻辑定义，对数据流图中的各要素给出确切的解释。,含四种类型的条目：,基本数据项条目,、,数据流条目,、,文件条目,和,加工条目,（即数据处理条目）,基本数据项条目包括：数据项名称、数据类型、数据长度、取值范围等内容。,数据流条目的各数据项可以分为三种：,必有项（,即数据流条目中必定包含的数据项,）；,必选项（,即在某几项中必定出现其中一项或几项,）；,任选项（,即可选可不选的数据项,）。,5.4.2 结构化分析方法与设计方法,结构化设计的步骤,评审和细化数据流图。,确定数据流图的类型。,把数据流图映射