第1章软件技术基础

《第1章软件技术基础》由会员分享，可在线阅读，更多相关《第1章软件技术基础（65页珍藏版）》请在金锄头文库上搜索。

1、第一章第一章软件技术基础软件技术基础q软件系统是计算机为某种特定目的而运行所需软件系统是计算机为某种特定目的而运行所需要的程序以及程序运行时所需要的数据和有关要的程序以及程序运行时所需要的数据和有关的技术资料，简称软件。的技术资料，简称软件。q计算机语言经过了机器语言、汇编语言、高级计算机语言经过了机器语言、汇编语言、高级语言三代。语言三代。q高级语言发展依据程序设计方法经历了三个时高级语言发展依据程序设计方法经历了三个时期：期：线线性程序性程序设计语设计语言言 结结构化程序构化程序设计语设计语言言 面向面向对对象程序象程序设计语设计语言言 1.1 1.1 计算机软件的发展概况计算机软件的发展

2、概况一、计算机语言的发展一、计算机语言的发展 第一章第一章 计算机软件技术基础计算机软件技术基础q计算机操作系统的发展经历了两个阶段。计算机操作系统的发展经历了两个阶段。q第一个阶段为单用户、单任务第一个阶段为单用户、单任务的操作系的操作系统，以统，以CP/M、MS-DOS等磁盘操作系统等磁盘操作系统为代表；为代表；q第二个阶段是多用户多任务和分时系统。第二个阶段是多用户多任务和分时系统。以以UNIX、Windows、Linux以及以及MacOS操作系统为代表。操作系统为代表。1.1 1.1 计算机软件的发展概况计算机软件的发展概况二、操作系统的发展二、操作系统的发展 第一章第一章 计算机软件

3、技术基础计算机软件技术基础1CP/M操作系统操作系统是是第第一一个个微微机机操操作作系系统统，这这个个系系统统允允许许用用户户通通过过控控制制台台的的键键盘盘对对系系统统进进行行控控制制和和管管理理，其其主主要要功功能能是是对对文文件件信信息息进行管理，以实现硬盘文件或其他设备文件的自动存取。进行管理，以实现硬盘文件或其他设备文件的自动存取。2DOS操作系统操作系统其其中中最最成成功功的的是是微微软软的的MS-DOS，它它是是在在IBM-PC及及其其兼兼容容机机上上运运行行的的操操作作系系统统，它它起起源源于于SCP86-DOS（也也是是CP/M一一类类的的操操作作系系统统），是是1980年年

4、基基于于8086微微处处理理器器而而设计的单用户操作系统。设计的单用户操作系统。1.1 1.1 计算机软件的发展概况计算机软件的发展概况二、操作系统的发展二、操作系统的发展 第一章第一章 计算机软件技术基础计算机软件技术基础3 3WindowsWindows操作系统操作系统 WindowsWindows是是MicrosoftMicrosoft公司在公司在19851985年年1111月开始发布月开始发布的窗口式多任务系统，它使微机进入了图形用户的窗口式多任务系统，它使微机进入了图形用户界面时代。界面时代。其主要特点如下：其主要特点如下： 界面界面图图形化，多用形化，多用户户、多任、多任务务，网，

5、网络络支持良好，支持良好，出色的多媒体功能，硬件支持良好，众多的出色的多媒体功能，硬件支持良好，众多的应应用用程序程序等于。等于。 1.1 1.1 计算机软件的发展概况计算机软件的发展概况二、操作系统的发展二、操作系统的发展 第一章第一章 计算机软件技术基础计算机软件技术基础4UNIX操作系操作系统统UNIX操操作作系系统统并并非非指指单单一一的的操操作作系系统统软软件件，而而是是包包括括一一系系列列的的UNIX家家族族：AIX、BSD、Digital UNIX、FreeBSD、HP-UX、IRIX、SunOS等等。它它是是一一个个真真正正的的多多用用户分时系统。户分时系统。UNIX系系统统主

6、要用于小型机、工作站和服主要用于小型机、工作站和服务务器器。5Linux操作系统操作系统它它是是一一个个免免费费软软件件，您您可可以以自自由由安安装装并并任任意意修修改改软软件件的的源源代码。代码。 LinuxLinux操操作作系系统统与与主主流流的的UNIXUNIX系系统统兼兼容容，这这使使得得它它一一出出现现就就有了一个很好的用户群。有了一个很好的用户群。 支支持持几几乎乎所所有有的的硬硬件件平平台台，包包括括IntelIntel系系列列、680x0680x0系系列列、AlphaAlpha系列、系列、MIPSMIPS系列等，并广泛支持各种周边设备。系列等，并广泛支持各种周边设备。 1.1

7、1.1 计算机软件的发展概况计算机软件的发展概况二、操作系统的发展二、操作系统的发展 第一章第一章 计算机软件技术基础计算机软件技术基础6.MacOS操作系统操作系统MacOS是一套运行于苹果是一套运行于苹果Macintosh系列系列电脑上的操作系统。电脑上的操作系统。1984年，苹果公司发年，苹果公司发布了布了System1，这是一个黑白界面的，也这是一个黑白界面的，也是世界上第一款成功的图形化用户界面操是世界上第一款成功的图形化用户界面操作系统。作系统。1.1 1.1 计算机软件的发展概况计算机软件的发展概况二、操作系统的发展二、操作系统的发展 第一章第一章 计算机软件技术基础计算机软件技

8、术基础1软件开发经历的三个时期软件开发经历的三个时期项项式式程程序序时时期期（1947-1960年年初初），程程序序作作为为机机器器运运行行时时必必须须进进行行的的准准备备工工作作。程程序序设设计计全全凭凭设设计计者者个个人人经经验验和和技技艺艺独独立立进进行行，是是一一种种典典型型的的手手工艺智力劳动。工艺智力劳动。软软件件=程程序序+说说明明时时期期（20世世纪纪50年年代代末末-20世世纪纪70年年代代初初），程程序序规规模模较较大大，需需要要多多人人协协作作才才能能完完成成；程程序序的的设设计计与与运运行行维维护护不不能能由由一一个个人人来来承承担担；程程序序不不再再是是计计算算机机硬

9、硬件件的的附附属属部部分分，而而是是计计算机系统中与硬件相互依存不可缺少的部分。算机系统中与硬件相互依存不可缺少的部分。1.1 1.1 计算机软件的发展概况计算机软件的发展概况三、软件开发与软件产业三、软件开发与软件产业 第一章第一章 计算机软件技术基础计算机软件技术基础软件软件= =程序程序+ +文档时期（文档时期（2020世纪世纪7070年代至今，即软年代至今，即软件工程时期），用件工程时期），用“工程化工程化”的思想作指导来解的思想作指导来解决软件研究和开发中面临的困难和混乱。决软件研究和开发中面临的困难和混乱。q软软件件产业产业的不成熟体的不成熟体现现在两个方面：在两个方面：第一，与第

10、一，与软软件研件研发发相关技相关技术术和理和理论还论还没有成熟；没有成熟；第二，第二，软软件工程化水平不成熟。件工程化水平不成熟。 1.1 1.1 计算机软件的发展概况计算机软件的发展概况三、软件开发与软件产业三、软件开发与软件产业 第一章第一章 计算机软件技术基础计算机软件技术基础1系统软件系统软件系系统统软软件件是是指指管管理理、监监控控和和维维护护计计算算机机系系统统正正常常工工作的程序和有关资料。主要包括：作的程序和有关资料。主要包括：操作系统。操作系统。各各种种语语言言解解释释程程序序和和编编译译程程序序（如如BASIC解解释释程程序、序、C编译程序等）。编译程序等）。各各种种服服务

11、务性性程程序序（如如机机器器的的调调试试、故故障障检检查查与与诊诊断程序等）。断程序等）。1.1 1.1 计算机软件的发展概况计算机软件的发展概况四、系统软件和应用软件四、系统软件和应用软件 第一章第一章 计算机软件技术基础计算机软件技术基础2应用软件应用软件应应用用软软件件是是指指为为解解决决某某个个实实际际问问题题而而编编制制的的程程序序和有关资料。和有关资料。应用软件又可分为：应用软件包和用户程序。应用软件又可分为：应用软件包和用户程序。应应用用软软件件包包是是生生产产厂厂家家或或软软件件公公司司，为为解解决决带带有有通通用用性性问问题题而而精精心心研研制制的的程程序序供供用用户户选选择

12、择使使用用，软软件件包包种种类类繁繁多多，如如标标准准函函数数库库、子子程程序序库库、文文字处理等。字处理等。用用户户程程序序则则是是为为特特定定用用户户解解决决特特定定问问题题而而开开发发的的软软件件，通通常常由由自自己己或或委委托托别别人人研研制制，是是面面向向特特定定用户的应用软件。用户的应用软件。1.1 1.1 计算机软件的发展概况计算机软件的发展概况四、系统软件和应用软件四、系统软件和应用软件 第一章第一章 计算机软件技术基础计算机软件技术基础q数数据据结结构构（DataStructure）指指的的是是数数据据之之间间的的相互关系，即数据的组织形式。相互关系，即数据的组织形式。q数据

13、结构一般包括以下三方面内容：数据结构一般包括以下三方面内容： 数据元素之间的逻辑关系，也称数据的逻辑数据元素之间的逻辑关系，也称数据的逻辑结构（结构（Logical StructureLogical Structure）；）； 数据元素及其关系在计算机存储器内的表示，数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（称为数据的存储结构（Storage StructureStorage Structure）；）； 数据的运算，即对数据施加的操作。数据的运算，即对数据施加的操作。1.2 1.2 数据结构概论数据结构概论 一、什么是数据结构一、什么是数据结构 第一章第一章 计算机软件技术基

14、础计算机软件技术基础例例1.1设有一学生成绩表。设有一学生成绩表。1.2 1.2 数据结构概论数据结构概论 一、什么是数据结构一、什么是数据结构 学学号号姓姓 名名英语英语数学数学物理物理平平 均均 成成绩绩2012010000001 1张张 平平88889595666683832012010000002 2赵赵 军军92928484989891.391.32012010000003 3刘刘 冰冰79797373787876.776.7（1）逻辑结构）逻辑结构表表中中的的每每一一行行是是一一个个数数据据元元素素（或或记记录录、结结点点），它它由由学学号、姓名、各科成绩及平均成绩等数据项组成。号

15、、姓名、各科成绩及平均成绩等数据项组成。第一章第一章 计算机软件技术基础计算机软件技术基础表中数据元素之间的逻辑关系是：对表中任一个结点，表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋与它相邻且在它前面的结点（亦称为直接前趋）最多只最多只有一个；与表中任一结点相邻且在其后的结点（亦称为有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继直接后继）也最多只有一个。表中只有第一个结点没有也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。直接后

16、继。故称之为终端结点。（2 2）存储结构）存储结构 存存储储结结构构是是指指用用计计算算机机语语言言如如何何表表示示结结点点之之间间的的这这种种关关系系，即即表表中中的的结结点点是是顺顺序序邻邻接接地地存存储储在在一一片片连连续续的的单单元元之中，还是用指针将这些结点链接在一起。之中，还是用指针将这些结点链接在一起。（3 3）数据的运算）数据的运算1.2 1.2 数据结构概论数据结构概论 一、什么是数据结构一、什么是数据结构 第一章第一章 计算机软件技术基础计算机软件技术基础q数数据据结结构构的的图图形形表表示示中中，对对于于数数据据集集合合D D中中的的每每一一个个数数据据元元素素用用中中间

17、间标标有有元元素素值值的的方方框框表表示示，一一般般称称之之为为数数据据结结点点，并并简简称称为为结结点点；为为了了进进一一步步表表示示各各数数据据元元素素之之间间的的前前后后件件关关系系，对对于于关关系系R R中中的的每每一一个个二二元元组组，用用一一条条有有向向线线段段从从前前件件结结点点指向后件结点。指向后件结点。1.2 1.2 数据结构概论数据结构概论 二、数据结构的图形表示二、数据结构的图形表示 如：一年四季的数据结构可以用图形来表示。如：一年四季的数据结构可以用图形来表示。第一章第一章 计算机软件技术基础计算机软件技术基础如如：反反映映家家庭庭成成员员间间辈辈分分关关系系的的数数据

18、据结结构构可可以以用用图图形来表示。形来表示。1.2 1.2 数据结构概论数据结构概论 二、数据结构的图形表示二、数据结构的图形表示 第一章第一章 计算机软件技术基础计算机软件技术基础数据的逻辑结构有两大类：数据的逻辑结构有两大类：（1）线性结构）线性结构线线性性结结构构的的逻逻辑辑特特征征：若若结结构构是是非非空空集集，则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，并并且且所所有有结点都最多只有一个直接前趋和一个直接后继。结点都最多只有一个直接前趋和一个直接后继。线线性性表表是是一一个个典典型型的的线线性性结结构构。栈栈、队队列列、串串等等都是线性结构。都是线性结

19、构。（2）非线性结构）非线性结构非非线线性性结结构构的的逻逻辑辑特特征征：一一个个结结点点可可能能有有多多个个直直接接前前趋趋和和直直接接后后继继。数数组组、广广义义表表、树树和和图图等等数数据结构都是非线性结构。据结构都是非线性结构。1.2 1.2 数据结构概论数据结构概论 三、线性结构与非线性结构三、线性结构与非线性结构第一章第一章 计算机软件技术基础计算机软件技术基础1算法算法所谓算法是指解题方案的准确而完整的描述。所谓算法是指解题方案的准确而完整的描述。2算法的基本特征算法的基本特征（1）可行性）可行性（2）确定性）确定性（3）有）有穷穷性性（4）拥拥有足有足够够的情的情报报1.3 1

20、.3 算法及算法分析算法及算法分析 一、算法一、算法 第一章第一章 计算机软件技术基础计算机软件技术基础3算法的基本要素算法的基本要素一一个个算算法法通通常常由由两两种种基基本本要要素素组组成成：一一是是对对数数据据对对象的运算和操作，二是算法的控制结构。象的运算和操作，二是算法的控制结构。（1）算法中对数据的运算和操作）算法中对数据的运算和操作基本的运算和操作有以下四类：基本的运算和操作有以下四类：算术运算：主要包括加、减、乘、除等运算。算术运算：主要包括加、减、乘、除等运算。逻逻辑辑运运算算：主主要要包包括括“与与”、“或或”、“非非”等等运算。运算。关关系系运运算算：主主要要包包括括“大

21、大于于”、“小小于于”、“等等于于”、“不等于不等于”等运算：等运算：数据传输：主要包括赋值、输入、输出等操作。数据传输：主要包括赋值、输入、输出等操作。1.3 1.3 算法及算法分析算法及算法分析 一、算法一、算法 第一章第一章 计算机软件技术基础计算机软件技术基础（2）算法的控制结构）算法的控制结构算算法法的的控控制制结结构构给给出出了了算算法法的的基基本本框框架架，它它不不仅仅决决定定了了算算法法中中各各操操作作的的执执行行顺顺序序，而而且且也也直直接接反反映映了了算算法法的的设设计计是是否否符符合合结结构构化化原原则则。描描述述算算法法的的工工具具通通常常有有传传统统流流程程图图、N-

22、S结结构构化化流流程程图图、算算法法描描述述语语言言等等。一一个个算算法法一一般般都都可可以以用用顺顺序序、选选择、循环三种基本控制结构组合而成。择、循环三种基本控制结构组合而成。1.3 1.3 算法及算法分析算法及算法分析 一、算法一、算法 第一章第一章 计算机软件技术基础计算机软件技术基础4算法设计基本方法算法设计基本方法（1 1）列举法）列举法根根据据提提出出的的问问题题，列列举举所所有有可可能能的的情情况况，并并用用问问题题中中给给定定的条件检验哪些是需要的，哪些是不需要的。的条件检验哪些是需要的，哪些是不需要的。（2 2）归纳法）归纳法通通过过列列举举少少量量的的特特殊殊情情况况，经

23、经过过分分析析，最最后后找找出出一一般般的的关关系。系。（3 3）递推）递推所所谓谓递递推推，是是指指从从已已知知的的初初始始条条件件出出发发，逐逐次次推推出出所所要要求求的的各各中中间间结结果果和和最最后后结结果果。其其中中初初始始条条件件或或是是问问题题本本身身已经给定，或是通过对问题的分析与化简而确定。已经给定，或是通过对问题的分析与化简而确定。（4 4）递归）递归（5 5）减半）减半递递推技推技术术 1.3 1.3 算法及算法分析算法及算法分析 一、算法一、算法 第一章第一章 计算机软件技术基础计算机软件技术基础q对算法的分析主要是对算法的时间复杂度和空间对算法的分析主要是对算法的时间

24、复杂度和空间复杂度的分析。复杂度的分析。q1时间复杂度时间复杂度一一个个算算法法的的时时间间复复杂杂度度是是该该算算法法的的时时间间耗耗费费，即即算法执行过程中所需要的基本运算次数。算法执行过程中所需要的基本运算次数。一一个个算算法法所所耗耗费费的的时时间间=算算法法中中每每条条语语句句的的执执行行时时间间之之和和。每每条条语语句句的的执执行行时时间间=语语句句的的执执行行次次数数语句执行一次所需时间。语句执行一次所需时间。q2空间复杂度空间复杂度一一个个算算法法的的空空间间复复杂杂度度为为该该算算法法在在执执行行过过程程中中所所需要的存储空间。需要的存储空间。算算法法的的时时间间复复杂杂度度

25、和和空空间间复复杂杂度度合合称称为为算算法法的的复复杂度。杂度。1.3 1.3 算法及算法分析算法及算法分析 二、算法分析二、算法分析 第一章第一章 计算机软件技术基础计算机软件技术基础1线性表的逻辑定义线性表的逻辑定义线线性性表表（LinearList）是是由由n（n0）个个数数据据元元素素（结结点点）a1，a2，an组成的有限序列。组成的有限序列。数据元素的个数数据元素的个数n定义为表的长度（定义为表的长度（n=0时称为空表）。时称为空表）。将非空的线性表（将非空的线性表（n0）记作：（记作：（a1，a2，an）数数据据元元素素ai（1in）只只是是个个抽抽象象符符号号，其其具具体体含含义

26、义在在不同情况下可以不同。不同情况下可以不同。如学生成绩表中，每个学生及其成绩是一个数据元素，如学生成绩表中，每个学生及其成绩是一个数据元素，其中数据元素由学号、姓名、各科成绩等数据项组成。其中数据元素由学号、姓名、各科成绩等数据项组成。1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表第一章第一章 计算机软件技术基础计算机软件技术基础2线性表的逻辑结构特征线性表的逻辑结构特征对于非空的线性表对于非空的线性表:有且仅有一个开始结点有且仅有一个开始结点a1，没有直接前趋，有，没有直接前趋，有且仅有一个直接后继且仅有一个直接后继a2；有且仅有一个终结结点有且仅有一个终结结点an

27、，没有直接后继，有，没有直接后继，有且仅有一个直接前趋且仅有一个直接前趋an-1；其余的内部结点其余的内部结点ai（2in1）都有且仅有一）都有且仅有一个直接前趋个直接前趋ai-1和一个直接后继和一个直接后继ai1。1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表第一章第一章 计算机软件技术基础计算机软件技术基础3线性表的顺序存储结构线性表的顺序存储结构有顺序存储和链式存储两种有顺序存储和链式存储两种顺序存储方法即把线性表的结点按逻辑次序依顺序存储方法即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。次存放在一组地址连续的存储单元里的方法。用顺序存储方法

28、存储的线性表简称为顺序表。用顺序存储方法存储的线性表简称为顺序表。在顺序表中，每个结点在顺序表中，每个结点ai的存储地址是该结点的存储地址是该结点在表中的位置在表中的位置i的线性函数。只要知道基地址和的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一每个结点的大小，就可在相同时间内求出任一结点的存储地址。结点的存储地址。 1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表第一章第一章 计算机软件技术基础计算机软件技术基础4常见的线性表的基本运算常见的线性表的基本运算（1）InitList(L)：构造一个空的线性表：构造一个空的线性表L，即表的，即表的初始化

29、。初始化。（2）ListLength(L)：求线性表：求线性表L中的结点个数，中的结点个数，即求表长。即求表长。（3）GetNode(L,i)：取线性表：取线性表L中的第中的第i个结点，个结点，这里要求这里要求1iListLength(L)。（4）LocateNode(L,x)：在：在L中查找值为中查找值为x的结点，的结点，并返回该结点在并返回该结点在L中的位置。若中的位置。若L中有多个结点中有多个结点的值和的值和x相同，则返回首次找到的结点位置；若相同，则返回首次找到的结点位置；若L中没有结点的值为中没有结点的值为x，则返回一个特殊值表示，则返回一个特殊值表示查找失败。查找失败。1.4 1.

30、4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表第一章第一章 计算机软件技术基础计算机软件技术基础（5）InsertList(L,x,i)：在线性表：在线性表L的第的第i个位置上个位置上插入一个值为插入一个值为x的新结点，使得原编号为的新结点，使得原编号为i，i1，n的结点变为编号为的结点变为编号为i1，i2，n1的结点。这里的结点。这里1in1，而，而n是原表是原表L的长度。的长度。插入后，表插入后，表L的长度加的长度加1。（6）DeleteList(L,i)：删除线性表：删除线性表L的第的第i个结点，个结点，使得原编号为使得原编号为i1，i2，n的结点变成编的结点变成编号为号为i

31、，i1，n1的结点。这里的结点。这里1in，而而n是原表是原表L的长度。删除后表的长度。删除后表L的长度减的长度减1。1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表第一章第一章 计算机软件技术基础计算机软件技术基础1栈的定义栈的定义栈（栈（Stack）是限制仅在表的一端进行插入和删）是限制仅在表的一端进行插入和删除运算的线性表。栈的示意图如图除运算的线性表。栈的示意图如图1-4所示：所示：（1）通常称插入、删除的这一端为栈顶，另一端）通常称插入、删除的这一端为栈顶，另一端称为栈底。称为栈底。（2）当表中没有元素时称为空栈。）当表中没有元素时称为空栈。（3）栈为后进先出（

32、）栈为后进先出（LastInFirstOut）的线性表，）的线性表，简称为简称为LIFO表。表。 栈的修改是按后进先出的原则进行。栈的修改是按后进先出的原则进行。 1.4 1.4 线性表、栈和队列线性表、栈和队列 二、栈二、栈第一章第一章 计算机软件技术基础计算机软件技术基础2栈的基本运算栈的基本运算（1）InitStack(S)：构造一个空栈：构造一个空栈S。（2）StackEmpty(S)：判栈空。若：判栈空。若S为空栈，则返回为空栈，则返回TRUE，否则返回，否则返回FALSE。（3）StackFull(S)：判栈满。若：判栈满。若S为满栈，则返回为满栈，则返回TRUE，否则返回否则返回

33、FALSE。注意：该运算只适用于栈的顺序存储。注意：该运算只适用于栈的顺序存储结构。结构。（4）Push(S,x)：进栈。若栈：进栈。若栈S不满，则将元素不满，则将元素x插入插入S的栈的栈顶。顶。（5）Pop(S)：退栈。若栈：退栈。若栈S非空，则将非空，则将S的栈顶元素删去，的栈顶元素删去，并返回该元素。并返回该元素。（6）StackTop(S)：取栈顶元素。若栈：取栈顶元素。若栈S非空，则返回栈顶非空，则返回栈顶元素，但不改变栈的状态。元素，但不改变栈的状态。1.4 1.4 线性表、栈和队列线性表、栈和队列 二、栈二、栈第一章第一章 计算机软件技术基础计算机软件技术基础1定义定义只允许在一

34、端进行插入，而在另一端进行删只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。除的运算受限的线性表。（1）允许删除的一端称为队头（）允许删除的一端称为队头（Front）。）。（2）允许插入的一端称为队尾（）允许插入的一端称为队尾（Rear）。）。（3）当队列中没有元素时称为空队列。）当队列中没有元素时称为空队列。（4）队列亦称作先进先出（）队列亦称作先进先出（FirstInFirstOut）的线性表，简称为的线性表，简称为FIFO表。表。队列的修改是依先进先出的原则进行的。队列的修改是依先进先出的原则进行的。 1.4 1.4 线性表、栈和队列线性表、栈和队列 三、队列三、队列第一章第

35、一章 计算机软件技术基础计算机软件技术基础2队列的基本逻辑运算队列的基本逻辑运算（1）InitQueue(Q)：置空队。构造一个空队列：置空队。构造一个空队列Q。（2）QueueEmpty(Q)：判队空。若队列：判队空。若队列Q为空，则返回为空，则返回真值，否则返回假值。真值，否则返回假值。（3）QueueFull(Q)：判队满。若队列：判队满。若队列Q为满，则返回真值，为满，则返回真值，否则返回假值。否则返回假值。注意：注意：此操作只适用于队列的顺序存储结构。此操作只适用于队列的顺序存储结构。（4）EnQueue(Q,x)：若队列：若队列Q非满，则将元素非满，则将元素x插入插入Q的的队尾。此

36、操作简称入队。队尾。此操作简称入队。（5）DeQueue(Q)：若队列：若队列Q非空，则删去非空，则删去Q的队头元素，的队头元素，并返回该元素。此操作简称出队。并返回该元素。此操作简称出队。（6）QueueFront(Q)：若队列：若队列Q非空，则返回队头元素，非空，则返回队头元素，但不改变队列但不改变队列Q的状态。的状态。1.4 1.4 线性表、栈和队列线性表、栈和队列 三、队列三、队列第一章第一章 计算机软件技术基础计算机软件技术基础以链接方式存储的线性表简称为链表。以链接方式存储的线性表简称为链表。1链表的具体存储表示为：链表的具体存储表示为：用一组任意的存储单元来存放线性表的结点用一组

37、任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不（这组存储单元既可以是连续的，也可以是不连续的）。连续的）。链表中结点的逻辑次序和物理次序不一定相同。链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针或链的地址（或位置）信息（称为指针或链)。1.5 1.5 线性链表线性链表 一、线性链表的概念一、线性链表的概念第一章第一章 计算机软件技术基础计算机软件技术基础2链表的结点结构链表的结点结构1

38、.5 1.5 线性链表线性链表 一、线性链表的概念一、线性链表的概念datanextdata域域存放结点值的数据域。存放结点值的数据域。next域域存放结点的直接后继的地址的指针域。存放结点的直接后继的地址的指针域。其其中中：链链表表通通过过每每个个结结点点的的链链域域将将线线性性表表的的n个结点按其逻辑顺序链接在一起的。个结点按其逻辑顺序链接在一起的。每个结点只有一个链域的链表称为单链表。每个结点只有一个链域的链表称为单链表。每每个个结结点点有有两两个个链链域域的的链链表表，既既指指出出该该数数据据元元素的后继素的后继,指出前驱，则这种链表称为双链表。指出前驱，则这种链表称为双链表。第一章第

39、一章 计算机软件技术基础计算机软件技术基础在单链表中增加一个表头结点，指针域指向线在单链表中增加一个表头结点，指针域指向线形表的第一个元素的结点，令最后一个结点的形表的第一个元素的结点，令最后一个结点的指针域指向表头结点，即构成了循环链表，指针域指向表头结点，即构成了循环链表，在在循环链表中，所有结点的指针构成了一个环状循环链表中，所有结点的指针构成了一个环状链。链。 1.5 1.5 线性链表线性链表 一、线性链表的概念一、线性链表的概念a1aiai+1an第一章第一章 计算机软件技术基础计算机软件技术基础n线性链表的基本运算主要有以下几个：线性链表的基本运算主要有以下几个：（1）在线性链表中

40、包含指定元素的结点之前插入）在线性链表中包含指定元素的结点之前插入一个新元素一个新元素（2）在线性链表中删除包含指定元素的结点）在线性链表中删除包含指定元素的结点（3）将两个线性链表按要求合并成一个线性链表）将两个线性链表按要求合并成一个线性链表（4）将一个线性链表按要求进行分解。）将一个线性链表按要求进行分解。（5）逆转线性链表）逆转线性链表（6）复制线性链表）复制线性链表（7）线性链表的排序）线性链表的排序（8）线性链表的查找）线性链表的查找1.5 1.5 线性链表线性链表 二、二、线性链表的基本运算线性链表的基本运算 第一章第一章 计算机软件技术基础计算机软件技术基础1.插入运算插入运算

41、思想方法思想方法:插入运算是将值为插入运算是将值为x的新结点插入的新结点插入到表的第到表的第i个结点的位置上，即插入到个结点的位置上，即插入到ai与与ai1之间。之间。具体步骤：具体步骤：（1）找到）找到ai存储位置存储位置p；（2）生成一个数据域为）生成一个数据域为x的新结点的新结点ax；（3）令结点）令结点*p的指针域指向新结点；的指针域指向新结点；（4）新结点的指针域指向结点）新结点的指针域指向结点ai1。1.5 1.5 线性链表线性链表 二、二、线性链表的基本运算线性链表的基本运算 第一章第一章 计算机软件技术基础计算机软件技术基础2.删除运算删除运算思想方法思想方法:删除运算是将表的

42、第删除运算是将表的第i个结点删去。个结点删去。具体步骤：具体步骤：（1）找到）找到ai-1的存储位置的存储位置p（因为在单链表中结点（因为在单链表中结点ai的存储地址是在其直接前趋结点的存储地址是在其直接前趋结点ai-1的指针域的指针域next中）；中）；（2）令）令pnext指向指向ai的直接后继结点（即把的直接后继结点（即把ai从链上摘下）；从链上摘下）；（3）释放结点）释放结点ai的空间，将其归还给的空间，将其归还给“存储池存储池”。1.5 1.5 线性链表线性链表 二、二、线性链表的基本运算线性链表的基本运算 第一章第一章 计算机软件技术基础计算机软件技术基础n树形结构是一类重要的非线

43、性结构。树形结构树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。是结点之间有分支，并具有层次关系的结构。 如家谱、行政组织机构都可用树形象地表示。如家谱、行政组织机构都可用树形象地表示。 1.6 1.6 树树 一、什么是树一、什么是树 经济管理学经济管理学院院经济信息系经济信息系计划统计系计划统计系外贸系外贸系信息处理信息处理教研室教研室经济数学经济数学教研室教研室计划学计划学教研室教研室统计学统计学教研室教研室外语外语教研室教研室国际贸易国际贸易教研室教研室第一章第一章 计算机软件技术基础计算机软件技术基础2树结构的基本术语树结构的基本术语在树结构中，每一个结

44、点只有一个前件，称为在树结构中，每一个结点只有一个前件，称为父结点。父结点。没有前件的结点只有一个，称为树的根结点。没有前件的结点只有一个，称为树的根结点。每一个结点可以有多个后件，都称为该结点的每一个结点可以有多个后件，都称为该结点的子结点。子结点。没有后件的结点称为叶子结点。没有后件的结点称为叶子结点。一个结点所拥有的后件个数称为该结点的度。一个结点所拥有的后件个数称为该结点的度。一棵树的度是指该树中结点的最大度数。一棵树的度是指该树中结点的最大度数。1.6 1.6 树树 一、什么是树一、什么是树 第一章第一章 计算机软件技术基础计算机软件技术基础结点的层数结点的层数(Level)：从根起

45、算，根的层数为：从根起算，根的层数为1，其余结点的层数等于其双亲结点的层数加，其余结点的层数等于其双亲结点的层数加1。树中结点的最大层数称为树的高度树中结点的最大层数称为树的高度(Height)或或深度深度(Depth)。ACBHDFIJGE1.6 1.6 树树 一、什么是树一、什么是树 图图中中，树树的的根根结结点点A度度为为2，结结点点B的的度度为为3，结结点点I的的度度为为0，树树的的度度为为3，结结点点A在在第第一一层层，结结点点B，C在在第第二二层层，结结点点D,E,F,G,H在在第第三三层层,结结点点I,J在第四层。在第四层。第一章第一章 计算机软件技术基础计算机软件技术基础n森林

46、森林(Forest)是是m(m0)棵互不相交的树棵互不相交的树的集合。的集合。n树和森林的概念相近。删去一棵树的根，树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。作树根，森林就变为一棵树。1.6 1.6 树树 一、什么是树一、什么是树 第一章第一章 计算机软件技术基础计算机软件技术基础1.二叉树的特点二叉树的特点（1）非空二叉树只有一个根结点。）非空二叉树只有一个根结点。（2）每一个结点最多有两棵子树，称为该结点的）每一个结点最多有两棵子树，称为该结点的左子树和右子树。左子树和右子树。如算术运算式如算术运算式3

47、 * 5 6 / 2 8就可用二叉树表就可用二叉树表示。示。1.6 1.6 树树 二、二、二叉树的基本性质二叉树的基本性质 +*83562/第一章第一章 计算机软件技术基础计算机软件技术基础2.二叉树具有以下重要性质：二叉树具有以下重要性质：性质性质1二叉树第二叉树第i层上的结点数目最多为层上的结点数目最多为2i1(i1)。性质性质2深度为深度为k的二叉树至多有的二叉树至多有2k1个结点个结点(k1)。性质性质3在任意一棵二叉树中，若终端结点的个数在任意一棵二叉树中，若终端结点的个数为为n0，度为，度为2的结点数为的结点数为n2，则，则no=n21。性质性质4具有具有n个结点的完全二叉树的深度

48、为：个结点的完全二叉树的深度为：（或（或）。）。1.6 1.6 树树 二、二、二叉树的基本性质二叉树的基本性质 第一章第一章 计算机软件技术基础计算机软件技术基础3.满二叉树和完全二叉树是二叉树满二叉树和完全二叉树是二叉树（1）满二叉树）满二叉树(FullBinaryTree)一棵深度为一棵深度为k且有且有2k1个结点的二叉树称为满二个结点的二叉树称为满二叉树。叉树。满二叉树的特点：满二叉树的特点：每一层上的结点数都达到最大值。即对给定的每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。高度，它是具有最多结点数的二叉树。满二叉树中不存在度数为满二叉树中不存在度数为1的结

49、点，每个分支结的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下点均有两棵高度相同的子树，且树叶都在最下一层上。一层上。1.6 1.6 树树 二、二、二叉树的基本性质二叉树的基本性质 第一章第一章 计算机软件技术基础计算机软件技术基础（2）完全二叉树）完全二叉树(CompleteBinaryTree)若一棵二叉树至多只有最下面的两层上结点的度数可若一棵二叉树至多只有最下面的两层上结点的度数可以小于以小于2，并且最下一层上的结点都集中在该层最左边，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。的若干位置上，则此二叉树称为完全二叉树。完全二叉树的特点：完全二

50、叉树的特点：满二叉树是完全二叉树，完全二叉树不一定是满二叉树。满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 在满二叉树的最下一层，从最右边开始连续删去若干结在满二叉树的最下一层，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。点后得到的二叉树仍然是一棵完全二叉树。 在完全二叉树中，若某个结点没有左孩子，则它一定没在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。有右孩子，即该结点必是叶结点。1.6 1.6 树树 二、二、二叉树的基本性质二叉树的基本性质 第一章第一章 计算机软件技术基础计算机软件技术基础n链接的方法是它最自然的存储表示方法。链接

51、的方法是它最自然的存储表示方法。n每个结点有一个数据域，两个指针域。数据域存每个结点有一个数据域，两个指针域。数据域存储数据元素的值，两个指针分别指向该数据元素储数据元素的值，两个指针分别指向该数据元素的左子女和右子女。当某个子女不存在时，相应的左子女和右子女。当某个子女不存在时，相应的指针为空指针。结点形式如下：的指针为空指针。结点形式如下：1.6 1.6 树树 三、三、二叉树的存储结构二叉树的存储结构 llinkinforlink一一棵棵二二叉叉树树的的所所有有这这样样形形式式的的结结点点，再再加加上上一一个个指指向向根根的的指指针针，就就构构成成此此二二叉叉树树的的存存储储表表示示。这这

52、种种存存储储表表示示法法称称为为llink-rlink表表示示法法或或称称为为二二叉叉链链表。表。第一章第一章 计算机软件技术基础计算机软件技术基础n遍历一棵二叉树实际上是对二叉树的结点进遍历一棵二叉树实际上是对二叉树的结点进行一次扫描，是将二叉树的结点放入一个线性行一次扫描，是将二叉树的结点放入一个线性序列的过程，或者说把二叉树进行线性化。遍序列的过程，或者说把二叉树进行线性化。遍历运算是二叉树的一种最基本的运算。历运算是二叉树的一种最基本的运算。遍历二叉树有三种主要的方法：前序法、中遍历二叉树有三种主要的方法：前序法、中序法和后序法。序法和后序法。 前序法，其操作如下：前序法，其操作如下：

53、访问根；访问根；按前序遍历左子树；按前序遍历左子树；按前序遍历右子树。按前序遍历右子树。1.6 1.6 树树 四、四、二叉树的运算二叉树的运算第一章第一章 计算机软件技术基础计算机软件技术基础中序法，其操作如下：中序法，其操作如下：按中序遍历左子树；按中序遍历左子树；访问根；访问根；按中序遍历右子树。按中序遍历右子树。后序法，其操作如下：后序法，其操作如下：按后序遍历左子树；按后序遍历左子树；按后序遍历右子树；按后序遍历右子树；访问根。访问根。1.6 1.6 树树 四、四、二叉树的运算二叉树的运算第一章第一章 计算机软件技术基础计算机软件技术基础+*83562/1.6 1.6 树树 四、四、二

54、叉树的运算二叉树的运算对于图中的二叉树，它的对于图中的二叉树，它的三种方法遍历结果是：三种方法遍历结果是：前序序列：前序序列：*35628中序序列：中序序列：3*5628后序序列：后序序列：35*628第一章第一章 计算机软件技术基础计算机软件技术基础n顺序查找又称顺序搜索。顺序查找一般是指在线性表中顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下：查找指定的元素，其基本方法如下：n从线性表的第一个元素开始，依次将线性表中的元素与从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功被查元素进行比较，若相等则表示找到（即查找

55、成功)；若线性表中所有的元素都与被查元素进行了比较但都；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素不相等，则表示线性表中没有要找的元素(即查找失败即查找失败)。n在下列两种情况下也只能采用顺序查找：在下列两种情况下也只能采用顺序查找：(1)如果线性表为无序表如果线性表为无序表(即表中元素的排列是无序的即表中元素的排列是无序的)，则，则不管是顺序存储结构还是链式存储结构，都只能用顺序不管是顺序存储结构还是链式存储结构，都只能用顺序查找。查找。(2)即使是有序线性表，如果采用链式存储结构，也只能用即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。顺序

56、查找。1.7 1.7 查找技术查找技术 一、顺序查找一、顺序查找第一章第一章 计算机软件技术基础计算机软件技术基础1.7 1.7 查找技术查找技术 二、二分法查找二、二分法查找n二分法查找只适用于顺序存储的有序表。二分法查找只适用于顺序存储的有序表。 设有序线性表的长度为设有序线性表的长度为n，被查元素为，被查元素为x，则对二，则对二分查找的方法如下：分查找的方法如下：将将x与线性表的中间项进行比较：与线性表的中间项进行比较：若中间项的值等于若中间项的值等于x，则说明查到，查找结束；，则说明查到，查找结束；若若x小于中间项的值，则在线性表的前半部分小于中间项的值，则在线性表的前半部分(即中间项

57、以前的部分即中间项以前的部分)以相同的方法进行查找；以相同的方法进行查找；若若x大于中间项的值，则在线性表的后半部分大于中间项的值，则在线性表的后半部分(即中间项以后的部分即中间项以后的部分)以相同的方法进行查找。以相同的方法进行查找。第一章第一章 计算机软件技术基础计算机软件技术基础n所谓排序是指将一个无序序列整理成按值递减（或递增）所谓排序是指将一个无序序列整理成按值递减（或递增）顺序排列的有序序列。顺序排列的有序序列。n1冒泡排序冒泡排序冒泡排序法的基本过程是：首先，从表头开始往后扫描冒泡排序法的基本过程是：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。线性表，

58、在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序：显然，在扫描过程它们互换，称之为消去了一个逆序：显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后，这也是最大元素应线性表中的最大者换到了表的最后，这也是最大元素应有的位置。有的位置。依次剩下的线性表元素重复上述过程，直到线性表中依次剩下的线性表元素重复上述过程，直到线性表中每一个元素都找到它应有的位置，此时的线性表变为有每一个元素都找到

59、它应有的位置，此时的线性表变为有序。序。1.7 1.7 查找技术查找技术 三、排序技术三、排序技术第一章第一章 计算机软件技术基础计算机软件技术基础2快速排序快速排序n快速排序法也是一种互换类的排序方法，但由于它比冒快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。泡排序法的速度快，因此称之为快速排序法。n快速排序法的基本思想如下：快速排序法的基本思想如下：从线性表中选取一个元素，设为从线性表中选取一个元素，设为T，将线性表后面小，将线性表后面小于于T的元素移到前面，而前面大于的元素移到前面，而前面大于T的元素移到后面。的元素移到后面。结果就将线性表分成了

60、两部分结果就将线性表分成了两部分(称为两个子表称为两个子表)，T插入插入到其分界线的位置处，这个过程称为线性表的分割。通到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以过对线性表的一次分割，就以T为分界线，将线性表分为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于，而后面子表中的所有元素均不小于T。如果对分割后的各子表再按上述原则进行分割，并且，如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，这种分割过程可以一直做下去

61、，直到所有子表为空为止，则此时的线性表就变成了有序表。则此时的线性表就变成了有序表。1.7 1.7 查找技术查找技术 三、排序技术三、排序技术第一章第一章 计算机软件技术基础计算机软件技术基础3.简单插入排序简单插入排序n所谓插入排序，是指将无序序列中的各元素依所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。次插入到已经有序的线性表中。n我们从线性表的第我们从线性表的第2个元素开始直到最后一个元个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面的有素，逐次将其中的每一个元素插入到前面的有序子表中。在简单插入排序法中，每一次比较序子表中。在简单插入排序法中，每一次比

62、较后最多移掉一个逆序，因此，这种排序方法的后最多移掉一个逆序，因此，这种排序方法的效率与冒泡法相同。在最坏情况下，排序需要效率与冒泡法相同。在最坏情况下，排序需要经过经过n（n1）/2次的比较。次的比较。1.7 1.7 查找技术查找技术 三、排序技术三、排序技术第一章第一章 计算机软件技术基础计算机软件技术基础4希尔排序希尔排序n希尔排序属于插入类排序，但它对简单插入排希尔排序属于插入类排序，但它对简单插入排序做了较大的改进。序做了较大的改进。n希尔排序的基本思想如下：希尔排序的基本思想如下：将整个无序序列分割成若干小的子序列分别将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割

63、方法是将相隔某进行插入排序。子序列的分割方法是将相隔某个增量个增量h的元素构成一个子序列。在排序过程中，的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当逐次减小这个增量，最后当h减到减到1时，进行一时，进行一次插入排序，排序就完成。增量序列一般取次插入排序，排序就完成。增量序列一般取ht=n/2K(K=1,2,log2n)，其中，其中n为待排序序列为待排序序列的长度。的长度。1.7 1.7 查找技术查找技术 三、排序技术三、排序技术第一章第一章 计算机软件技术基础计算机软件技术基础5简单选择排序简单选择排序n选择排序方法中最简单的一种就是直接选择排选择排序方法中最简单的一种就是直接

64、选择排序算法。序算法。n其操作过程是：首先，从表头开始往后扫描线其操作过程是：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的性表，在扫描过程中逐次比较相邻两个元素的大小。先选出最小的元素并将其与第一个元素大小。先选出最小的元素并将其与第一个元素交换。然后在剩下的交换。然后在剩下的n1个元素中再选出最小个元素中再选出最小的元素与第二个元素交换的元素与第二个元素交换最后在剩下的两最后在剩下的两个元素中。选出一个小的元素与第个元素中。选出一个小的元素与第n1个元素个元素交换。交换。 1.7 1.7 查找技术查找技术 三、排序技术三、排序技术第一章第一章 计算机软件技术基础计算机软

65、件技术基础6堆排序堆排序n堆排序属于选择类的排序方法。堆排序属于选择类的排序方法。n根据堆的定义，可以得到堆排序的方法如下：根据堆的定义，可以得到堆排序的方法如下：（1）首先将一个无序序列建成堆。）首先将一个无序序列建成堆。（2）然后将堆顶元素与堆中最后一个元素交换。）然后将堆顶元素与堆中最后一个元素交换。不考虑已经换到最后的那个元素，只考虑前不考虑已经换到最后的那个元素，只考虑前n1个元素构成的子序列，显然，该子序列已个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做第（列调整为堆。反复做第（2）步，直到剩下

66、的）步，直到剩下的子序列为空为止。子序列为空为止。 1.7 1.7 查找技术查找技术 三、排序技术三、排序技术第一章第一章 计算机软件技术基础计算机软件技术基础n1结构化程序设计的原则结构化程序设计的原则（1）自顶向下：程序设计时，应先考虑总体，后考虑细节；）自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。问题具体化。（2）逐步求精：对复杂问题，应设计一些子目标作过渡，）逐步求精：对复杂问题，

67、应设计一些子目标作过渡，逐步细化。逐步细化。（3）模块化：一个复杂问题，肯定是由若干稍简单的问题）模块化：一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个再进一步分解为具体的小目标，把每个小目标称为一个模块。模块。（4）限制使用）限制使用goto语句：限制使用语句：限制使用goto语句后，程序易理语句后，程序易理解、易排错、易维护，程序容易进行正确性证明。解、易排错、易维护，程序容易进行正确性证明。1.8 1.8 程序设计文法程序设计文法 一、结构化程序设计一、

68、结构化程序设计第一章第一章 计算机软件技术基础计算机软件技术基础2.结构化程序的基本结构与特点结构化程序的基本结构与特点（1）顺序结构：顺序结构是顺序执行结构）顺序结构：顺序结构是顺序执行结构。（2）选择结构：可以根据设定的条件，判断应该选择哪一）选择结构：可以根据设定的条件，判断应该选择哪一条分支来执行相应的语句序列。条分支来执行相应的语句序列。（3）循环结构：它根据给定的条件，判断是否需要重复执）循环结构：它根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段，利用重复结构可简化大行某一相同的或类似的程序段，利用重复结构可简化大量的程序行。量的程序行。3、按结构化程序设计方法设计出

69、的程序具有的优点：、按结构化程序设计方法设计出的程序具有的优点：其一，程序易于理解、使用和维护。其一，程序易于理解、使用和维护。其二，提高了编程工作的效率，降低了软件开发成本。其二，提高了编程工作的效率，降低了软件开发成本。1.8 1.8 程序设计文法程序设计文法 一、结构化程序设计一、结构化程序设计第一章第一章 计算机软件技术基础计算机软件技术基础3.结构化程序设计原则和方法的应用结构化程序设计原则和方法的应用（1）使用程序设计语言中的顺序、选择、循环等）使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；有限的控制结构表示程序的控制逻辑；（2）选用的控制结构只准许有一个

70、入口和一个出）选用的控制结构只准许有一个入口和一个出口；口；（3）程序语句组成容易识别的块，每块只有一个）程序语句组成容易识别的块，每块只有一个入口和一个出口；入口和一个出口；（4）复杂结构应该用嵌套的基本控制结构进行组）复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；合嵌套来实现；（5）语言中所没有的控制结构，应该采用前后一）语言中所没有的控制结构，应该采用前后一致的方法来模拟；致的方法来模拟；（6）严格控制）严格控制goto语句的使用。语句的使用。1.8 1.8 程序设计文法程序设计文法 一、结构化程序设计一、结构化程序设计第一章第一章 计算机软件技术基础计算机软件技术基础1对象（对象

71、（object）n对象是面向对象方法中最基本的概念。对象是对象是面向对象方法中最基本的概念。对象是系统中用来描述客观事物的一个实体，是构成系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。征的属性和它可执行的一组操作组成。n特点：特点：（1）标识唯一性。指对象是可区分的，并且由对）标识唯一性。指对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分。象的内在本质来区分，而不是通过描述来区分。（2）分类性。指可以将具有相同属性和操作的对）分类性。指可以将具有相同属性和操作的对象抽象成

72、类。象抽象成类。（3）多态性。指同一个操作可以是不同对象的行）多态性。指同一个操作可以是不同对象的行为。为。1.8 1.8 程序设计文法程序设计文法 二、面向对象的程序设计二、面向对象的程序设计第一章第一章 计算机软件技术基础计算机软件技术基础（4）封装性。从外面看只能看到对象的外部特性，）封装性。从外面看只能看到对象的外部特性，即只需知道数据的取值范围和可以对该数据施即只需知道数据的取值范围和可以对该数据施加的操作，根本无需知道数据的具体结构以及加的操作，根本无需知道数据的具体结构以及实现操作的算法。实现操作的算法。 （5）模块独立性好。）模块独立性好。 1.8 1.8 程序设计文法程序设计

73、文法 二、面向对象的程序设计二、面向对象的程序设计第一章第一章 计算机软件技术基础计算机软件技术基础2类（类（Class）和实例（）和实例（Instance）n类是具有共同属性、共同方法的对象的集合。类是具有共同属性、共同方法的对象的集合。类是对象的抽象，它描述了属于该对象类型的类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的所有对象的性质，而一个对象则是其对应类的一个实例。一个实例。n“实例实例” 是指一个具体的对象。是指一个具体的对象。如：如：Integer是一个整数类，它描述了所有整数是一个整数类，它描述了所有整数的性质。因此任何整数都是整数类的对象，而的

74、性质。因此任何整数都是整数类的对象，而一个具体的整数一个具体的整数“123”是类是类Integer的一个实的一个实例。例。1.8 1.8 程序设计文法程序设计文法 二、面向对象的程序设计二、面向对象的程序设计第一章第一章 计算机软件技术基础计算机软件技术基础3消息消息（Message）n对象间的这种相互合作需要一个机制协助进行，对象间的这种相互合作需要一个机制协助进行，这样的机制称为这样的机制称为“消息消息”。4继承（继承（Inheritance）n继承是面向对象的方法的一个主要特征。继承继承是面向对象的方法的一个主要特征。继承是使用已有的类定义作为基础建立新类的定义是使用已有的类定义作为基础

75、建立新类的定义技术。已有的类可当作基类来引用，则新类相技术。已有的类可当作基类来引用，则新类相应地可当作派生类来引用。应地可当作派生类来引用。1.8 1.8 程序设计文法程序设计文法 二、面向对象的程序设计二、面向对象的程序设计第一章第一章 计算机软件技术基础计算机软件技术基础5多态性（多态性（Polymorphism）n对象根据所接受的消息而做出动作，同样的消对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。该现象称为多态性。n在面向对象的软件技术中，多态性是指子类对在面向对象的软件技术中，多态性是指子类对象可以像父类对象那样使用，同样的消息既可象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象。以发送给父类对象也可以发送给子类对象。1.8 1.8 程序设计文法程序设计文法 二、面向对象的程序设计二、面向对象的程序设计第一章第一章 计算机软件技术基础计算机软件技术基础