《大学计算机基础》课程介绍软件开发与程序设计基础.ppt

第5章 软件开发与程序设计基础,主讲教师郭松涛,本章教学计划理论教学（课堂教学）：4学时实验教学（上机实习）：2学时本章教学重点1.程序的基本概念及程序设计语言2.程序设计基本方法和过程3.数据结构、算法描述及分析 4.软件开发方法及工具,第5章 软件开发与程序设计基础,5.1 程序设计的基本概念5.2 程序设计的基本过程 5.3 数据结构与算法的基本概念 5.4 软件开发方法,第5章 软件开发与程序设计基础,5.1 程序设计的基本概念,程序的基本概念程序是程序设计中最基本的概念。程序是计算机软件的本体，又是软件的研究对象。实际上,一个程序是有限指令的序列。程序除了有作者之外，还应该有执行者来实现这些指令。实现指令称为执行或运行程序。一个运行中的程序称为进程。计算机程序分为可执行程序、目标程序和源程序三类。可执行程序是由机器指令组成的程序，可以直接在CPU中执行并得到运行结果。目标程序是一种中间代码的程序，是源程序经过编译后产生的结果。源程序泛指由计算机语言书写的程序，源程序需要经过编译器或者解释器等软件工具翻译为可执行程序。,5.1 程序设计的基本概念,程序的基本概念程序可能有几种状态。静态程序指在外存储器中存放的源程序、目标程序和可执行程序，他们一般以文件形式存在。静态的可执行程序文件需要通过“装入”内存储器才能由CPU执行，这个过程称为“运行程序”。运行中的程序称为动态程序。动态程序一般分为若干“进程”，由CPU分别执行进程的指令序列，完成相应的计算任务。进程（又称计算机作业）是为CPU运行程序组织的内存区域，由被执行程序的机器指令、用户数据区和系统数据区组成。它是程序运行的基本单位。,5.1 程序设计的基本概念,程序的基本概念计算机程序设计经过了以下四个发展过程：(1)机器语言程序阶段(1946一1956年)(2)高级语言程序阶段(1956一1958年)(3)结构化程序阶段(1958一1975年)(4)面向对象和自动化程序阶段（1975至今）,5.1 程序设计的基本概念,5.1.2 程序设计语言概述 程序设计语言是用来定义计算机程序的一组记号和一组语法规则。它是一种被标准化的交流技巧，用来向计算机发出指令。一种计算机语言让程序员能够准确地定义计算机所需要使用的数据，并精确地定义在不同情况下的操作。程序设计语言有三个方面的因素，即语法、语义和语用。语法表示程序的结构或形式，亦即表示构成语言的各个记号之间的组合规律，但不涉及这些记号的特定含义，也不涉及使用者。语义表示程序的含义，亦即表示按照各种方法所表示的各个记号的特定含义。语用表示程序与使用者的关系。,5.1 程序设计的基本概念,5.1.2 程序设计语言概述一段程序的含义就是该语言的语义，如：if(x0)y=1;else y=-1;其语义是：如果x0 则y=1,否则y=-1。语用就是该程序属于谁。它有2层含义，一方面指出程序属于哪个模块，另一方面指出程序起作用的范围。一般说来，程序设计语言有以下基本成分：(1)数据成分：用以描述程序中所涉及的数据；(2)运算成分：用以描述程序中所包含的运算；(3)控制成分：用以表达程序中的控制构造，或者是程序流程控制；(4)传输成分：用以表达程序中数据的传输。,5.1 程序设计的基本概念,5.1.2 程序设计语言概述1)程序设计语言的分类按语言级别，有低级语言和高级语言之分。低级语言主要是机器语言和汇编语言。高级语言的表示方法要比低级语言更接近于待解问题的表示方法，大量引入数学表示形式，其特点是与具体机器无关，易学、易用、易维护。一般说来，一个高级语言程序单位要对应多条机器指令，相应的编译程序所产生的目标程序往往功效较低。按照程序实现的机制，有过程式语言和非过程式语言之分。过程式语言的主要特征是明确问题解决的详细步骤，设计者需要指明可以顺序执行的一系列操作运算，以表示相应的计算过程。例如，FORTRAN、ALGOL60等都是过程式语言。非过程式语言的含义是相对的，凡是无法指明可顺序执行的程序运算的语言，都是非过程式语言。,5.1 程序设计的基本概念,按照应用范围，有通用语言和专用语言之分。目标非单一的语言，称为通用语言，例如 FORTRAN、C等都是通用语言。目标单一的语言称为专用语言，如APT（数控机床专用语言）、PHP（动态网页设计语言）等。按照程序语言的使用方式，有交互式语言和非交互式语言之分。具有反映人一机交互作用的语言称为交互式语言，如BASIC语言就是交互式语言。反之称非交互式语言，如FORTRAN、PASCAL等都是非交互式语言。传统的程序设计语言大都以冯诺伊曼（Von Neuman）式计算机为设计背景，因而又称为诺伊曼式语言。这类语言的特点是“存储程序”和“过程式”，程序设计需要详细规定程序运行过程的步骤。程序和程序所需的数据必须被存储在计算机的主内存中，当执行程序时，就从主内存中读取程序中的指令和数据并把计算结果存入主内存。,5.1 程序设计的基本概念,5.1.2 程序设计语言概述2)程序设计语言的发展史（1）第一代语言（大约从1946年开始）（2）第二代语言（大约从1950年早期开始）（3）第三代语言（大概从1950年中期开始）（4）第四代语言（4GL，超高级语言。大致从二十世纪八十年代开始）,5.1 程序设计的基本概念,5.1.2 程序设计语言概述3)常用高级程序设计语言简介FORTRAN(FORmula TRANslation)公式翻译程序设计语言。是在IBM公司的704系列计算机上开发的。多年来，FORTRAN一直被选作为科学和工程的计算语言，它广泛支持浮点运算甚至支持复数运算。COBOL(COmmon Business Oriented Language)面向商业的通用语言。1960诞生。是第一个面向文件的数据处理语言。它采用300多个英语单词作为保留字，以一种接近于英语书面语言的形式来描述数据特性和数据处理过程。在银行业、证券交易、公司财务管理、情报检索、企业管理中使用最广泛的高级语言。,5.1 程序设计的基本概念,5.1.2 程序设计语言概述3)常用高级程序设计语言简介ALGOL60(ALGOrithmic Language60)算法语言60。程序设计语言由技艺转向科学的重要标志，其特点是局部性、动态性、递归性和严谨性。它由欧洲的研究人员设计，以严格的语法规则定义语言，使用BNF(巴克斯范式)来描述文法，引入了分程序结构。从某种意义上来说ALGOL60正如一粒种子，成为许多流行的通用语言的直接祖先。甚至在今天，人们也用到“类ALGOL”的程序设计语言。PASCAL(Philips Automatic Sequence CALculator)菲利浦自动顺序计算语言。在ALGOL60的基础上发展起来的重要语言，其最大特点是简明性与结构化。Pascal程序设计语言继承了ALGOL的许多结构，但也包括了COBOL的记录处理。该语言由瑞士计算机科学教授沃思（Niklaus Wirth）于1971年设计而成。,5.1 程序设计的基本概念,5.1.2 程序设计语言概述3)常用高级程序设计语言简介BASIC（Beginners All-purpose Symbolic Instruction Code）初学者通用指令码。是Dartmouth数学系的John Kemeny和Thomas Kurtz在1964年为Dartmouth的分时系统开发的。BASIC语言适合初学者学习程序设计,特别是非理工科的学生。BASIC程序员只需坐在终端前，在数字之后敲入BASIC语句，即可建立BASIC程序。数字表明程序中语句的顺序。最简单的BASIC程序为：10 LET X=(7+8)/320 PRINT X30 END输入以上程序代码后，敲入运行命令RUN。该程序在终端上显示（7+8）/3的计算结果。BASIC语言不需要程序员指定一个变量是按整数存储还是浮点数存储。大多数的BASIC版本是解释程序，非常方便对程序代码的修改。,5.1 程序设计的基本概念,5.1.2 程序设计语言概述3)常用高级程序设计语言简介C语言于1969年1973年产生。它是BCPL(Basic Combined Programming Language)和B语言的后继，故取名C语言。C语言是第一个成功实现系统软件开发的高级语言，是一种受到专业程序员欢迎的程序语言。它由贝尔电话实验室的Dennis M.Ritchie 在PDP-11计算机上首先实现，并用它重写了UNIX操作系统。从那时起，操作系统和C语言的关系就紧密起来了。C 是很简洁的语言，例如，Pascal中用begin和end 来定义语句块，在C语言中用来代替。C语言支持移位操作和按位逻辑操作等CPU的基本指令。另外，C语言还支持指针，指针实质上是符号化的内存地址。C语言支持多种数据结构，具有很高的可移植性。LISP(LISt Processing)表处理语言。是由John McCarthy 于1960年设计而成的，是一个著名的非冯诺依曼的语言。LISP 引进函数式程序设计概念和表处理设施，在人工智能的领域内广泛使用。LISP程序处理的对象是符号列表，它的数据和程序的表示是一致的，都使用S-表达式，操作符采用前缀形式，程序控制结构采用递归形式。,5.1 程序设计的基本概念,5.1.2 程序设计语言概述3)常用高级程序设计语言简介 PROLOG(PROgramming in LOGic)逻辑程序设计语言。它已广泛用于关系数据库、数理逻辑、抽象问题求解、自然语言理解等多种领域，l972年由法国科学家研制。ADA一种现代模块化语言，属于ALGOLPASCAL语言族，但有较大变动。其主要特征是强类型化和模块化，便于实现个别编译，提供类属设施，提供异常处理，适于嵌入式应用。Ada是1979开发的，为美国国防部使用的一种语言，是以Augusta Ada Byron命名的，他是英国数学家查尔斯巴贝奇（Charles Babbage）的差分机的见证人。,5.1 程序设计的基本概念,5.1.3 程序设计语言处理程序 常见的语言处理程序有汇编程序、解释程序和编译程序。1)汇编程序 汇编程序又称汇编系统。它的功能是将汇编语言程序翻译成机器语言程序。由于汇编语言的指令与机器语言的指令基本保持了一一对应关系，所以汇编的过程比较简单，效率非常高。汇编的基本步骤是：将指令助记符转换为机器操作码。将符号操作数转换为地址码。将操作码和操作数构成机器指令。汇编程序是为特定的CPU指令系统设计的，因此没有互换性。不同的CPU指令集有不同的汇编程序。可以将机器语言程序转换为相应的汇编语言程序，这个过程称为反汇编，这样的系统程序称为反汇编程序。,5.1 程序设计的基本概念,5.1.3 程序设计语言处理程序2)编译程序编译程序又称为编译系统。它的主要功能是将高级语言编写的程序翻译成等效的机器语言程序，以便直接运行程序。其翻译过程如图所示。编译程序主要执行下列步骤：编译连接加载,5.1 程序设计的基本概念,5.1.3 程序设计语言处理程序3)解释程序解释程序又称解释系统。所谓解释实际上是对源程序的每一可能的行为，都以机器语言编写一个子程序，用来模拟这一行为。因此对高级语言程序的解释，实际上调用一系列的子程序来完成。解释过程如图所示。一个解释程序是一个重复执行下列步骤的程序：取下一个语句；确定被执行的活动；执行这一活动。,5.1 程序设计的基本概念5.2 程序设计的基本过程 5.3 数据结构与算法的基本概念 5.4 软件开发方法,第5章 软件开发与程序设计基础,5.2 程序设计的基本过程,一个程序应该包含两个方面的内容：一是程序要处理的对象，人们用数据和数据之间的关系来表示，即数据结构（data structure）；二是对这些对象的处理方法，即操作步骤，人们用算法（algorithm）来描述。著名计算机科学家沃思（Niklaus Wirth）提出了一个公式：“程序=数据结构+算法”，诠释了程序设计的本质。实际上，一个程序除以上两个因素外，还应考虑程序设计的语言和程序设计方法，因此，可以有如下的表示：“程序=数据结构+算法+程序设计方法+语言工具和环境”也就是说，以上四个方面是一个程序设计人员应具备的知识。,5.2 程序设计的基本过程,程序设计的基本方法1)结构化程序设计技术(1)结构化程序设计方法的产生结构化程序设计的概念不是孤立发展而形成的。实际上，二十世纪六十年代，随着高级语言的不断产生和广泛的应用，越来越多的、大而复杂的应用问题需要通过计算机来解决。随之而来出现了一系列严重的问题，如：程序的质量无法保证、程序的修改难以进行、程序的开发周期和成本估计不准等，造成了许多项目的失败，这就是所谓的软件危机。因此，许多科学家为了解决这些问题，首先在程序设计方面进行了广泛、深入的研究和讨论，从而建立了结构化程序设计的基本概念、理论和方法。,5.2 程序设计的基本过程,程序设计的基本方法结构定理1966年，Bohra 和Jacopini证明了仅用三种基本结构就能实现任何算法。这是：顺序、选择和循环，如图所示。其中,S1、S2又可能或是三种基本结构之一。通过把它们合理地组合可以形成任何算法。goto之争单入口和单出口自顶向下，逐步求精其基本思想是：从欲求解的原问题出发，运用科学抽象的方法，把它分解成若干相对独立的小问题，依次细化，直至各个小问题获得解决为止。,5.2 程序设计的基本过程,5.2 程序设计的基本过程,程序设计的基本方法（2）结构化程序设计方法的基本思想结构化程序设计方法的基本思想之一就是抽象与分解。抽象实际上是人类认识世界的基本法则之一。人们在实践中认识到，在现实世界中一定事物、状态、或过程之间总是存在着某些相似的方面，把这些相似的方面集中和概括起来，暂时忽略它们之间的差异,或者说抽出事物的本质特性而暂时不考虑它们的细节，这就是抽象。显然，这种抽象包含了系统的观点和分层的观点，即可以把程序设计所面临的问题看成是一个系统，这个系统可用高级的抽象概念来理解和构造,这些高级的抽象概念又可用较低级的抽象概念来理解和构造，如此进行下去，直到最低层次的模块可以表示成某种程序设计语言的语句为止。,5.2 程序设计的基本过程,程序设计的基本方法2)面向对象程序设计技术面向对象技术是程序设计技术的一次革命，在软件开发史上具有里程碑的意义。（1）面向对象的基本概念：对象和类所谓对象是现实世界中的实体，是某个抽象数据类型的值。利用对象和类可以达到信息隐蔽和数据抽象的目的。对象包含有下面几个含义：每个对象有可以唯一地标识它的名字；每个对象都占有自己的空间，每个对象都与一组施加在这些数据结构上的操作相联系一个对象的状态只能由该对象的操作来改变。,5.2 程序设计的基本过程,程序设计的基本方法所谓类是定义抽象数据类型的一种机制。类是对一组具有相同数据结构和方法的对象的特征抽象，是一个“对象工厂”，是一个创建对象的模板，每一个由类而生成的新对象都有同样的数据结构和方法。在这种意义下，每个对象都是某一个类的实例。例如，“小轿车”是一个类，某一辆“小轿车”是这个类的一个实例，谁也没有见过抽象的“小轿车”，只见过具体的某一种品牌型号的“小轿车”。另一方面，类也可以是一个“对象仓库”，是存在于系统中的所有同一类对象的整体表示，在这种意义上讲，类也是一个对象。,5.2 程序设计的基本过程,程序设计的基本方法方法和消息对象一旦被定义，就与一组方法联系起来。方法是在类中定义的，同一类的所有对象都具有同样的方法，方法是作用在对象上的，一个对象的方法是通过消息来激活的。消息可以激活对象上的方法，对对象的实例变量进行计算、存取，也可以向另外的对象发送消息。继承性继承性是从已定义的类定义新类的一种手段。通过继承性，可以对一个已经定义的类进行细化，加入新的属性和方法，而不用重复说明已定义的属性和方法，甚至不必了解已定义类的表示和实现细节。,5.2 程序设计的基本过程,程序设计的基本方法（2）面向对象的程序设计方法的思想：所谓“程序设计”即是用计算机模拟现实世界的活动。从传统的角度看，程序是“活动”的集合；程序=过程+调用称这种程序设计方法为面向过程的程序设计。现实世界是由许许多多的实体或对象构成的。这些对象彼此相关并能相互通讯，对象的活动构成了现实世界的活动。从面向对象的角度看，程序是对象的集合；对象之间的相互作用构成了一个软件系统。对象参与的交互动作称为事件，在事件中消息在对象之间发送，接收消息的对象调用相应的方法进行响应。如图所示。,5.2 程序设计的基本过程,程序设计的基本方法（2）面向对象的程序设计方法的思想：面向对象的程序设计最突出的特点是建立在对象和类的基础上，把问题所对应的现实世界中的事物抽象成对象或类，并建立对象之间的关系。每个对象或类不仅包含描述其特征的属性或数据结构，而且还包含对这些数据结构的操作（也称为方法或服务），如图所示。,5.2 程序设计的基本过程,程序设计的基本方法（2）面向对象的程序设计方法的思想：当我们对对象中的每一个操作进行描述时，可以把一个操作理解为一个“过程”，这个“过程”需要完成一定的任务，这里的“过程”与结构化程序设计中的过程本质上是两个不同的概念。因为结构化程序设计中的过程在对数据的操作中，数据是被动的；而这里的对象是主动的不是被动的，对象是中心，是被封装了的抽象体，对象中的“过程”即操作只能通过接收消息时进行启动和执行并对对象中的属性进行改变。面向对象的程序设计方法可以简单地表示为：面向对象=对象+类+继承+消息通信,5.2 程序设计的基本过程,程序设计的基本方法3)组件（COM）程序设计组件化程序设计方法继承并发展了面向对象的程序设计方法。它把对象技术应用于系统设计，对面向对象的程序设计的实现过程作了进一步的抽象。我们可以把组件化程序设计方法用作构造系统的体系结构层次的方法，并且可以使用面向对象的方法很方便地实现组件。前面的设计思想只能在源程序级别重用，不能在二进制级别（可执行代码级）重用，而组件程序设计正是从这个层面解决问题的。,5.2 程序设计的基本过程,程序设计的基本过程1)程序设计的基本过程 在编制程序的过程中，将受三项因素的制约：计算机解决什么问题，要研究问题的可计算性和计算的复杂性；将要运行这一程序的计算机所具有的运行环境，包括计算机的系统结构及其可利用的资源；用什么语言来编写程序。,5.2 程序设计的基本过程,程序设计的基本过程这种采用程序设计方法来解决实际问题的过程,一般分为下列几个步骤：（1）分析问题（2）建立数学模型（3）确定数据结构（4）设计算法（5）编制程序,一个高质量的程序，应具备以下条件:建立正确的数学模型和确立有效的计算方法；运行结果必须是正确的，且在精度和其他各方面均满足要求；程序本身具有良好的结构，逻辑清楚，易读易懂；程序运行时间尽可能短，同时尽可能合理地使用内存；便于检查、修正、移植和维护。,5.2 程序设计的基本过程,程序设计的基本过程（6）调试程序程序调试的首要任务是查错；通过调试程序发现程序中的语法和逻辑错误并将其消除。程序的错误一般可以分为编译错误、执行错误和逻辑错误。调试是一项复杂而富有挑战性的工作,有时为了改正一个小错误，可能要花费很长的时间。测试程序的方法包括：书写检查，通过仔细阅读源程序代码修正错误；手工调试，使用采样数据手工调试程序；编译调试，使用编译软件测试程序；采样数据测试，使用采样数据在计算机上执行程序以发现错误用户测试，通过程序用户的使用来测试程序。,5.2 程序设计的基本过程,程序设计的基本过程（7）编制文档经过调试正常后的程序，应该为它编制以下文件：a)程序内容摘要、简述程序的功能；b)程序的逻辑结构即程序规格的详细叙述；c)数据规格描述，包括输入记录及形式、输出报告及形式；d)查错时使用的测试数据表及相应的输出示例；e)包括注释行在内的程序清单；f)可能包括的算法描述等。,5.2 程序设计的基本过程,程序设计的基本过程2)程序设计举例,5.2 程序设计的基本过程,5.2 程序设计的基本过程,5.2 程序设计的基本过程,5.2 程序设计的基本过程,程序设计的基本过程 程序的调试、运行。通过上机，进行编辑、编译、连接、执行等工作，对程序做检查，验证程序的正确性。编制程序文档。这个例子的文档很简单，只要依次把问题描述、数学模型、算法和C语言程序汇集在一起即可形成程序文档资料。,5.1 程序设计的基本概念5.2 程序设计的基本过程 5.3 数据结构与算法的基本概念 5.4 软件开发方法,第5章 软件开发与程序设计基础,5.3 数据结构与算法的基本概念,数据结构的基本概念计算机能够为人服务的前提是要编写程序告知计算机所要做的工作。编写程序时，程序员必须首先找到完成这个任务的步骤，即计算机科学中的所谓“算法”；任何算法所处理的对象是数据，数据的不同表示（逻辑的和结构的）将影响算法的设计及执行的效率（时间与空间）。因此如何表示数据是程序设计的关键技术之一。这一问题是计算机科学中数据结构的任务。作为一门课程主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，数据结构主要有三方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作(或算法)。,5.3 数据结构与算法的基本概念,数据结构的基本概念1)数据结构的定义数据是描述客观事物的数字、字母和符号，是计算机程序使用和加工的“原料”。数据的基本单位是数据元素，性质相同的数据元素的集合叫做数据对象。数据对象中的元素彼此之间的相互关系叫做结构。（1）数据及数据元素数据(Data)是指能被计算机识别、存储和处理的对象的集合。数据不仅包括数值、还包括字符、语音、图像等非数值数据。数据是计算机程序使用和加工的“原料”。其特点是它们都能被计算机识别、存储和处理。数据元素(Data Element)是组成数据的基本单位，性质相同的数据元素的集合叫做数据对象。在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项(Data Item)组成。数据项也称为字段或域。例如，通信簿表中的一行（包括：姓名、单位、出生日期、电话号码、地址、邮政编码等相关信息）是数据元素。数据项是具有独立含义的数据最小单位；,5.3 数据结构与算法的基本概念,1)数据结构的定义如通信簿表中的“单位”、“电话号码”等。如下表所示：,5.3 数据结构与算法的基本概念,1)数据结构的定义（2）数据结构的定义数据对象中元素彼此之间的相互关系叫做结构。为了进一步理解什么是数据结构，我们来看一个具体的例子。图书馆是大家所熟悉的，一本图书由书名、作者、出版社等数据来描述；根据需要，我们选择其中的若干项组成一个数据元素来对应一本书。图书馆的编目表反映了书与书之间的关系，是数据元素之间的结构。当然我们还应注意到，书是具体地放在某个书架上的，它是编目表的物理实现。图书馆从两方面管理图书：物理的藏书和逻辑的编目表。和图书馆一样，计算机管理数据也有两个方面：即物理的存储和逻辑的关系。从这两个方面，我们来回答什么是数据结构。,5.3 数据结构与算法的基本概念,1)数据结构的定义（2）数据结构的定义数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。数据结构指的是信息的组织形式；即一个数据由哪些数据元素构成、以什么方式构成、呈现什么结构。数据结构指的是数据之间的结构关系。具体地说，它包括数据的逻辑结构和数据的物理结构。数据的逻辑结构：仅考虑数据元素之间的逻辑关系。它包括线性结构（如线性表、栈、队）和非线性结构（如树、二叉树和图）。数据的物理结构：指数据元素在存储器中的表示，即存储结构。比如向量、链表。,5.3 数据结构与算法的基本概念,2)数据的逻辑结构一般情况下，数据元素之间不是相互孤立的，常常存在某些逻辑上的联系，这些联系与它们在计算机中的存储位置无关，是独立于计算机的；我们把客观事物本身的数据元素之间抽象化的相互关系（即：对数据元素之间的逻辑关系的描述）称为数据的逻辑结构。从结合的观点，一个数据结构（Data Structure）可以表示为一个二元组：Data_Structure=(D，R)其中：D是数据元素的集合（或者是“结点”，可能还含有“数据项”或“数据域”），R是定义在D（或其他集合）上关系的集合。按集合的观点，数据的逻辑结构有两个要素：一是数据元素；二是关系。,5.3 数据结构与算法的基本概念,2)数据的逻辑结构,5.3 数据结构与算法的基本概念,3)数据结构的分类数据的逻辑结构按数据元素之间的相互关系，可以把数据结构分为四种基本结构。图中每一个圆圈表示一个结点（或数据元素），两结点之间的连线表示两结点有相邻关系。（1）集合结构（2）线性结构（3）树结构（4）图结构,5.3 数据结构与算法的基本概念,5.3 数据结构与算法的基本概念,4)数据结构的存储结构数据要能被计算机处理，就必须存储在计算机内，我们把这种数据元素及其关系（数据结构）在计算机内的存储表示称为数据的存储结构，也称物理结构；它是数据的逻辑结构在计算机存储器里的映象。映象就是对给定的逻辑结构，找出恰当的与其对应的存储结构，以便在计算机中存储。数据的物理结构，即存储结构，按关系的映象分为顺序存储结构和非顺序存储结构。计算机的存储器（内存）是由很多存储单元（word 或byte）组成的，每个存储单元都有惟一的地址。各存储单元的地址编码是线性连续的，即每一个存储单元有惟一的前驱单元和惟一的后继单元。我们把两个互为前驱后继的存储单元称为相邻存储单元，把一片相邻的存储单元称为存储区域。一般情况下，一个结点所占用的空间并不止一个存储单元，不同类型的结点所占用的存储单元数量也各不相同。数据结构包括结点的值及结点之间的关系，其存储结构除了必须存储结点的值外，还得能以直接或隐含的方式体现出结点之间的关系。一种逻辑结构通过映象便得到它相应的存储结构。同一种逻辑结构可以映象成不同的内部存储结构。反过来，数据的存储结构一定要反映数据之间的逻辑关系。,5.3 数据结构与算法的基本概念,4)数据结构的存储结构一般情况下，一个结点所占用的空间并不止一个存储单元，不同类型的结点所占用的存储单元数量也各不相同。数据结构包括结点的值及结点之间的关系，其存储结构除了必须存储结点的值外，还得能以直接或隐含的方式体现出结点之间的关系。一种逻辑结构通过映象便得到它相应的存储结构。同一种逻辑结构可以映象成不同的内部存储结构。反过来，数据的存储结构一定要反映数据之间的逻辑关系。存储结构中应有两方面的内容：数据元素自身值的表示（数据域）；该结点与其它结点关系的域（链域）。,5.3 数据结构与算法的基本概念,4)数据结构的存储结构(1)数据元素的映象方法：用二进制位(bit)的位串表示数据元素：(321)10(501)8(101000001)2A(101)8(001000001)2(2)关系的映象方法：数据元素(Data Element)之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象；并由此得到两种不同的存储结构：顺序存储结构和链接存储结构。顺序存储结构是逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里，元素的关系由存储单元的邻接关系来体现。非顺序存储结构是数据元素可以在计算机内任意位置上存储（它不要求逻辑上相邻的元素在物理位置上也相邻)，它们的逻辑关系用指针来链接。所以非顺序存储结构又叫链式存储结构。链式存储结构将数据元素存放的存储单元分为两个部分，分别存放数据和指针，称为数据域和指针域。,5.3 数据结构与算法的基本概念,4)数据结构的存储结构,5.3 数据结构与算法的基本概念,4)数据结构的存储结构,5.3 数据结构与算法的基本概念,4)数据结构的存储结构顺序存储结构包括向量(典型的顺序存储结构，一组相互毗邻的连续单元)、数组。链式存储结构是链表，按指针域的个数分为单链表，双向链表和多重链表。在链式存储结构中，我们提到一个概念指针，指针即地址。程序中的变量名、下标地址都是指针。指针是数据结构中十分关键的概念，对它的理解及其应用都非常重要。首先指针是许多数据结构得以实现的基础，链式存储结构就是用指针来实现逻辑结构与存储结构的映象；其次指针的应用，将导致许多优雅的算法，例如，应用指针数组(索引)，作为中间媒介，可不移动真实的数据，从而利用好计算机程序的时间和空间两大资源。,5.3 数据结构与算法的基本概念,4)数据结构的存储结构(3)顺序存储结构与链接存储结构的比较：顺序存储结构中，只需元素信息本身的域，无需指针域，因此占用存储空间少；而链接存储结构中，除了元素信息本身的数据域外，还需指针域，因此存储空间利用率低。顺序存储结构中，逻辑上相邻的结点物理上也相邻；而链接存储结构中，逻辑上相邻的结点物理上却不必相邻。顺序存储结构易于存、取和访问运算，不便于插入和删除运算；而链接存储结构的插入和删除运算方便灵活。实际应用中，多数数据结构采用上述两种存储结构之一，或两种结构的结合。除此之外，还有散列存储结构和索引存储结构。,5.3 数据结构与算法的基本概念,4)数据结构的存储结构值得指出的是，选择某个结构和选择某个结构的表示是不同的。前者是为解决某个问题，在对问题理解的基础上，选择一个合适的逻辑结构表示出数据的逻辑关系；后者是对这个逻辑结构为适应求解，即运算的需要，选择一个恰当的存储表示。前面的选择是面向问题，后面的选择是面向机器。这中间有一个“面向问题”的数据的逻辑结构向“面向机器”的数据的存储结构转换的问题，这正是数据结构所要研究的。学习、研究数据结构的目的在于对大量的数据进行有效处理，合理地应用好计算机的两大资源时间和空间。,5.3 数据结构与算法的基本概念,算法描述与算法分析1)算法的基本概念算法(Algorithms)指的是为了解决某类实际问题而规定的、一个有限长度的、步骤可执行的操作序列的集合。实际上，算法是能被机械地执行的动作或指令的有穷集合。一个动作的一次执行称为一步，而能够用算法来解的问题称为可计算问题。,5.3 数据结构与算法的基本概念,算法描述与算法分析2)算法的基本特征一个算法必须同时满足以下五个重要特性：有穷性。例如求正弦函数值的公式：没有表示出计算到何时为止，所以这样的描述只是计算方法而不是算法。当以某种方式表述了计算到多少项为止的时候（例如，某一项的绝对值小于10-5时停止计算）才能称之为算法。确定性。可执行性。一个算法有零个或多个输入数据。一个算法有一个或多个输出数据。,5.3 数据结构与算法的基本概念,算法描述与算法分析3)算法的基本结构 一般地说，由于需要解决的问题是各种各样的，所以算法的构造是千变万化的，其形式也是千姿百态的。但算法的最基本的组成形式和构造成分只有三种基本结构，任何复杂的算法都是这三种基本结构按某种方式的堆砌，这三种基本结构是：顺序结构、选择（分支）结构和循环结构。顺序结构选择（分支）结构循环结构,5.3 数据结构与算法的基本概念,算法描述与算法分析4)算法的描述方法一个算法可以有多种描述方式。除自然语言外，常用于描述算法的工具有三种，它们是：程序流程图（Flow Chart）、盒图（N-S图）和伪代码（Pseudo Code）。（1）程序流程图程序流程图又称为程序框图，使用一些图形符号来表示算法中的各个执行或判断过程，使用流程线（有向线段）来表示算法执行中每一个步骤在执行上的时间顺序。流程图可以非常清楚地描述整个算法执行的过程，但由于流程线画法十分灵活自由，使用不当会造成算法清晰性差以及理解上的困惑。,5.3 数据结构与算法的基本概念,算法描述与算法分析4)算法的描述方法（2）N-S图N-S图是由Nassi和Shneiderman两人提出的一种结构化程序设计图，与程序流程图的主要区别在于去掉了程序流程图中的流程线，从而解决了使用程序流程图容易设计出非结构化算法的问题，强制算法设计者使用结构化程序设计思想。常见算法基本结构的N-S图画法如下图所示。,5.3 数据结构与算法的基本概念,算法描述与算法分析4)算法的描述方法（3）伪代码用程序流程图或N-S图来描述算法虽然简单直观，但在算法设计过程中使用起来并不十分方便，特别是当算法稍微复杂一点，需要反复修改时更是如此。在实际的算法设计中，为了清晰方便地描述算法，常常使用自然语言或计算机语言或类计算机语言来描述。这里的类计算机语言是一种非计算机语言，借用了一些高级语言的某些成分,没有加入严格的规则，而且不能够被计算机所接受；称其为“伪代码”或“伪语言”；用伪语言来描述算法时并无一定的严格规则，原则上只要能够将算法的意思表现清楚、描述方式清晰、易读、易懂即可。用伪语言描述的算法的三种基本结构如下所示：,5.3 数据结构与算法的基本概念,算法描述与算法分析4)算法的描述方法（3）伪代码用程序流程图或N-S图来描述算法虽然简单直观，但在算法设计过程中使用起来并不十分方便，特别是当算法稍微复杂一点，需要反复修改时更是如此。在实际的算法设计中，为了清晰方便地描述算法，常常使用自然语言或计算机语言或类计算机语言来描述。这里的类计算机语言是一种非计算机语言，借用了一些高级语言的某些成分,没有加入严格的规则，而且不能够被计算机所接受；称其为“伪代码”或“伪语言”；用伪语言来描述算法时并无一定的严格规则，原则上只要能够将算法的意思表现清楚、描述方式清晰、易读、易懂即可。用伪语言描述的算法的三种基本结构如下所示：,5.3 数据结构与算法的基本概念,算法描述与算法分析4)算法的描述方法（3）伪代码,5.3 数据结构与算法的基本概念,算法描述与算法分析4)算法的描述方法（3）伪代码,5.3 数据结构与算法的基本概念,算法描述与算法分析5)算法设计的原则 设计算法时，通常应考虑达到以下目标：正确性(Correctness)首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果；c程序对于精心选择的、典型的、苛刻而带有刁难性的几组输入数据能够得出满足要求的结果；d程序对于一切合法的输入数据都能得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。可读性(Readability)健壮性(Robustness)高效率与低存储量需求,5.3 数据结构与算法的基本概念,算法描述与算法分析6)算法分析初步一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需资源越多，我们就说该算法的复杂性越高；反之，所需资源越少，我们就说该算法的复杂性越低。最重要的计算机资源是时间和空间(即存储器)资源。因此，算法的复杂性有时间复杂性和空间复杂性之分。选择其中复杂性最低者，是我们在选用算法时遵循的一个重要准则。算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该集中反映算法的效率，并从运行该算法的实际计算机中抽象出来。空间单位一般规定为一个简单变量(如整型、实型等)所占存储空间的大小；时间单位则一般规定为执行一个简单语句(如赋值语句、判断语句等)所用时间。,5.3 数据结构与算法的基本概念,算法描述与算法分析6)算法分析初步(1)算法的时间复杂性算法的时间代价(或称时间复杂性)：当问题规模以某种单位由1增至n时，对应算法所耗费的时间也以某种单位由f(1)增至f(n)，这时我们称该算法的时间代价是f(n)。在描述算法分析的结果时，人们通常采用“”表示法。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=(f(n)称T(n)为算法的(渐近)时间复杂度。算法=控制结构+原操作（固有数据类型的操作）；算法的执行时间=原操作(i)的执行次数原操作(i)的执行时间；算法的执行时间 与 原操作执行次数之和成正比。从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。,5.3 数据结构与算法的基本概念,算法描述与算法分析6)算法分析初步(1)算法的时间复