软件技术基础88

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

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

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

4、于机上运行的操作系统，它起源于SCP86-DOS（也是（也是 CP/M一类的操作系统），是一类的操作系统），是1980年基于年基于8086微处理器微处理器 而设计的单用户操作系统。而设计的单用户操作系统。 1.1 1.1 计算机软件的发展概况计算机软件的发展概况 二、操作系统的发展二、操作系统的发展 第一章第一章 计算机软件技术基础计算机软件技术基础 3 3WindowsWindows操作系统操作系统 WindowsWindows是是MicrosoftMicrosoft公司在公司在19851985年年1111月开始发月开始发 布的窗口式多任务系统，它使微机进入了图形布的窗口式多任务系统，它使微

5、机进入了图形 用户界面时代。用户界面时代。 其主要特点如下：其主要特点如下： 界面图形化，多用户、多任务，网络支持良好，界面图形化，多用户、多任务，网络支持良好， 出色的多媒体功能，硬件支持良好，众多的应出色的多媒体功能，硬件支持良好，众多的应 用程序用程序等于。等于。 1.1 1.1 计算机软件的发展概况计算机软件的发展概况 二、操作系统的发展二、操作系统的发展 第一章第一章 计算机软件技术基础计算机软件技术基础 4UNIX操作系统操作系统 UNIX操作系统并非指单一的操作系统软件，而是包括一操作系统并非指单一的操作系统软件，而是包括一 系列的系列的UNIX家族：家族：AIX、BSD、Dig

6、ital UNIX、Free BSD、HP-UX、IRIX、SunOS等。它是一个真正的多等。它是一个真正的多 用户分时系统。用户分时系统。 UNIX系统主要用于小型机、工作站和服务器系统主要用于小型机、工作站和服务器。 5 Linux操作系统操作系统 它是一个免费软件，您可以自由安装并任意修改软件的源它是一个免费软件，您可以自由安装并任意修改软件的源 代码。代码。 LinuxLinux操作系统与主流的操作系统与主流的UNIXUNIX系统兼容，这使得它一出现系统兼容，这使得它一出现 就有了一个很好的用户群。就有了一个很好的用户群。 支持几乎所有的硬件平台，包括支持几乎所有的硬件平台，包括Int

7、elIntel系列、系列、680 x0680 x0系列、系列、 AlphaAlpha系列、系列、MIPSMIPS系列等，并广泛支持各种周边设备。系列等，并广泛支持各种周边设备。 1.1 1.1 计算机软件的发展概况计算机软件的发展概况 二、操作系统的发展二、操作系统的发展 第一章第一章 计算机软件技术基础计算机软件技术基础 6. Mac OS操作系统操作系统 Mac OS是一套运行于苹果是一套运行于苹果Macintosh系列系列 电脑上的操作系统。电脑上的操作系统。1984年，苹果公司发年，苹果公司发 布了布了System 1，这是一个黑白界面的，也，这是一个黑白界面的，也 是世界上第一款成功

8、的图形化用户界面操是世界上第一款成功的图形化用户界面操 作系统。作系统。 1.1 1.1 计算机软件的发展概况计算机软件的发展概况 二、操作系统的发展二、操作系统的发展 第一章第一章 计算机软件技术基础计算机软件技术基础 1软件开发经历的三个时期软件开发经历的三个时期 项式程序时期（项式程序时期（1947-1960年初），程序作为机年初），程序作为机 器运行时必须进行的准备工作。程序设计全凭器运行时必须进行的准备工作。程序设计全凭 设计者个人经验和技艺独立进行，是一种典型设计者个人经验和技艺独立进行，是一种典型 的手工艺智力劳动。的手工艺智力劳动。 软件软件=程序程序+说明时期（说明时期（20

9、世纪世纪50年代末年代末-20世纪世纪 70年代初），程序规模较大，需要多人协作才年代初），程序规模较大，需要多人协作才 能完成；程序的设计与运行维护不能由一个人能完成；程序的设计与运行维护不能由一个人 来承担；程序不再是计算机硬件的附属部分，来承担；程序不再是计算机硬件的附属部分， 而是计算机系统中与硬件相互依存不可缺少的而是计算机系统中与硬件相互依存不可缺少的 部分。部分。 1.1 1.1 计算机软件的发展概况计算机软件的发展概况 三、软件开发与软件产业三、软件开发与软件产业 第一章第一章 计算机软件技术基础计算机软件技术基础 软件软件= =程序程序+ +文档时期（文档时期（2020世纪世

10、纪7070年代至今，即年代至今，即 软件工程时期），用软件工程时期），用“工程化工程化”的思想作指导的思想作指导 来解决软件研究和开发中面临的困难和混乱。来解决软件研究和开发中面临的困难和混乱。 q软件产业的不成熟体现在两个方面：软件产业的不成熟体现在两个方面： 第一，与软件研发相关技术和理论还没有成熟；第一，与软件研发相关技术和理论还没有成熟； 第二，软件工程化水平不成熟。第二，软件工程化水平不成熟。 1.1 1.1 计算机软件的发展概况计算机软件的发展概况 三、软件开发与软件产业三、软件开发与软件产业 第一章第一章 计算机软件技术基础计算机软件技术基础 1系统软件系统软件 系统软件是指管理

11、、监控和维护计算机系统正常系统软件是指管理、监控和维护计算机系统正常 工作的程序和有关资料。主要包括：工作的程序和有关资料。主要包括： 操作系统。操作系统。 各种语言解释程序和编译程序（如各种语言解释程序和编译程序（如BASIC解释解释 程序、程序、C编译程序等）。编译程序等）。 各种服务性程序（如机器的调试、故障检查与各种服务性程序（如机器的调试、故障检查与 诊断程序等）。诊断程序等）。 1.1 1.1 计算机软件的发展概况计算机软件的发展概况 四、系统软件和应用软件四、系统软件和应用软件 第一章第一章 计算机软件技术基础计算机软件技术基础 2应用软件应用软件 应用软件是指为解决某个实际问题

12、而编制的程应用软件是指为解决某个实际问题而编制的程 序和有关资料。序和有关资料。 应用软件又可分为：应用软件包和用户程序。应用软件又可分为：应用软件包和用户程序。 应用软件包是生产厂家或软件公司，为解决带应用软件包是生产厂家或软件公司，为解决带 有通用性问题而精心研制的程序供用户选择使有通用性问题而精心研制的程序供用户选择使 用，软件包种类繁多，如标准函数库、子程序用，软件包种类繁多，如标准函数库、子程序 库、文字处理等。库、文字处理等。 用户程序则是为特定用户解决特定问题而开发用户程序则是为特定用户解决特定问题而开发 的软件，通常由自己或委托别人研制，是面向的软件，通常由自己或委托别人研制，

13、是面向 特定用户的应用软件。特定用户的应用软件。 1.1 1.1 计算机软件的发展概况计算机软件的发展概况 四、系统软件和应用软件四、系统软件和应用软件 第一章第一章 计算机软件技术基础计算机软件技术基础 q数据结构（数据结构（Data Structure）指的是数据之间的）指的是数据之间的 相互关系，即数据的组织形式。相互关系，即数据的组织形式。 q数据结构一般包括以下三方面内容：数据结构一般包括以下三方面内容： 数据元素之间的逻辑关系，也称数据的逻辑数据元素之间的逻辑关系，也称数据的逻辑 结构（结构（Logical StructureLogical Structure）；）； 数据元素及其

14、关系在计算机存储器内的表示，数据元素及其关系在计算机存储器内的表示， 称为数据的存储结构（称为数据的存储结构（Storage StructureStorage Structure）；）； 数据的运算，即对数据施加的操作。数据的运算，即对数据施加的操作。 1.2 1.2 数据结构概论数据结构概论 一、什么是数据结构一、什么是数据结构 第一章第一章 计算机软件技术基础计算机软件技术基础 例例1.1 设有一学生成绩表。设有一学生成绩表。 1.2 1.2 数据结构概论数据结构概论 一、什么是数据结构一、什么是数据结构 学学 号号 姓姓 名名英语英语数学数学物理物理 平 均 成平 均 成 绩绩 2012

15、01 000000 1 1 张张 平平8888959566668383201201 000000 2 2 赵赵 军军92928484989891.391.3201201 000000 3 3 刘刘 冰冰79797373787876.776.7 （1）逻辑结构）逻辑结构 表中的每一行是一个数据元素（或记录、结点），它由学表中的每一行是一个数据元素（或记录、结点），它由学 号、姓名、各科成绩及平均成绩等数据项组成。号、姓名、各科成绩及平均成绩等数据项组成。 第一章第一章 计算机软件技术基础计算机软件技术基础 表中数据元素之间的逻辑关系是：对表中任一个结点，表中数据元素之间的逻辑关系是：对表中任一个

16、结点， 与它相邻且在它前面的结点（亦称为直接前趋）最多只与它相邻且在它前面的结点（亦称为直接前趋）最多只 有一个；与表中任一结点相邻且在其后的结点（亦称为有一个；与表中任一结点相邻且在其后的结点（亦称为 直接后继）也最多只有一个。表中只有第一个结点没有直接后继）也最多只有一个。表中只有第一个结点没有 直接前趋，故称为开始结点；也只有最后一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有 直接后继。故称之为终端结点。直接后继。故称之为终端结点。 （2 2）存储结构）存储结构 存储结构是指用计算机语言如何表示结点之间的这种关存储结构是指用计算机语言如何表示结点之间的这种关 系，即表中的结

17、点是顺序邻接地存储在一片连续的单元系，即表中的结点是顺序邻接地存储在一片连续的单元 之中，还是用指针将这些结点链接在一起。之中，还是用指针将这些结点链接在一起。 （3 3）数据的运算）数据的运算 1.2 1.2 数据结构概论数据结构概论 一、什么是数据结构一、什么是数据结构 第一章第一章 计算机软件技术基础计算机软件技术基础 q数据结构的图形表示中，对于数据集合数据结构的图形表示中，对于数据集合D D中的每中的每 一个数据元素用中间标有元素值的方框表示，一个数据元素用中间标有元素值的方框表示， 一般称之为数据结点，并简称为结点；为了进一般称之为数据结点，并简称为结点；为了进 一步表示各数据元素

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

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

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

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

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

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

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

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

26、程中 所需要的存储空间。所需要的存储空间。 算法的时间复杂度和空间复杂度合称为算法的算法的时间复杂度和空间复杂度合称为算法的 复杂度。复杂度。 1.3 1.3 算法及算法分析算法及算法分析 二、算法分析二、算法分析 第一章第一章 计算机软件技术基础计算机软件技术基础 1线性表的逻辑定义线性表的逻辑定义 线性表（线性表（Linear List）是由）是由n（n0）个数据元素（结点）个数据元素（结点） a1，a2，an组成的有限序列。组成的有限序列。 数据元素的个数数据元素的个数n定义为表的长度（定义为表的长度（n=0时称为空表）。时称为空表）。 将非空的线性表（将非空的线性表（n0）记作：（）记

27、作：（a1，a2，an） 数据元素数据元素ai（1 i n）只是个抽象符号，其具体含义在）只是个抽象符号，其具体含义在 不同情况下可以不同。不同情况下可以不同。 如学生成绩表中，每个学生及其成绩是一个数据元素，如学生成绩表中，每个学生及其成绩是一个数据元素， 其中数据元素由学号、姓名、各科成绩等数据项组成。其中数据元素由学号、姓名、各科成绩等数据项组成。 1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表 第一章第一章 计算机软件技术基础计算机软件技术基础 2线性表的逻辑结构特征线性表的逻辑结构特征 对于非空的线性表对于非空的线性表: 有且仅有一个开始结点有且仅有一个开始结

28、点a1，没有直接前趋，有，没有直接前趋，有 且仅有一个直接后继且仅有一个直接后继a2； 有且仅有一个终结结点有且仅有一个终结结点an，没有直接后继，有，没有直接后继，有 且仅有一个直接前趋且仅有一个直接前趋an-1； 其余的内部结点其余的内部结点ai（2in1）都有且仅有一）都有且仅有一 个直接前趋个直接前趋ai-1和一个直接后继和一个直接后继ai1。 1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表 第一章第一章 计算机软件技术基础计算机软件技术基础 3线性表的顺序存储结构线性表的顺序存储结构 有顺序存储和链式存储两种有顺序存储和链式存储两种 顺序存储方法即把线性表的结

29、点按逻辑次序依顺序存储方法即把线性表的结点按逻辑次序依 次存放在一组地址连续的存储单元里的方法。次存放在一组地址连续的存储单元里的方法。 用顺序存储方法存储的线性表简称为顺序表。用顺序存储方法存储的线性表简称为顺序表。 在顺序表中，每个结点在顺序表中，每个结点ai的存储地址是该结点的存储地址是该结点 在表中的位置在表中的位置i的线性函数。只要知道基地址和的线性函数。只要知道基地址和 每个结点的大小，就可在相同时间内求出任一每个结点的大小，就可在相同时间内求出任一 结点的存储地址。结点的存储地址。 1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表 第一章第一章 计算机软件技

30、术基础计算机软件技术基础 4常见的线性表的基本运算常见的线性表的基本运算 （1）InitList(L)：构造一个空的线性表：构造一个空的线性表L，即表的，即表的 初始化。初始化。 （2）ListLength(L)：求线性表：求线性表L中的结点个数，中的结点个数， 即求表长。即求表长。 （3）GetNode(L,i) ：取线性表：取线性表L中的第中的第i个结点，个结点， 这里要求这里要求1 i ListLength(L)。 （4）LocateNode(L,x)：在：在L中查找值为中查找值为x 的结点，的结点， 并返回该结点在并返回该结点在L中的位置。若中的位置。若L中有多个结点中有多个结点 的值

31、和的值和x 相同，则返回首次找到的结点位置；若相同，则返回首次找到的结点位置；若 L中没有结点的值为中没有结点的值为x，则返回一个特殊值表示，则返回一个特殊值表示 查找失败。查找失败。 1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表 第一章第一章 计算机软件技术基础计算机软件技术基础 （5）InsertList(L,x,i)：在线性表：在线性表L的第的第i个位置上个位置上 插入一个值为插入一个值为x 的新结点，使得原编号为的新结点，使得原编号为i，i 1，n的结点变为编号为的结点变为编号为i1，i2，n 1的结点。这里的结点。这里1 i n1，而，而n是原表是原表L的长

32、的长 度。插入后，表度。插入后，表L的长度加的长度加1。 （6）DeleteList(L,i)：删除线性表：删除线性表L的第的第i个结点，个结点， 使得原编号为使得原编号为i1，i2，n的结点变成编的结点变成编 号为号为i，i1，n1的结点。这里的结点。这里1 i n， 而而n是原表是原表L的长度。删除后表的长度。删除后表L的长度减的长度减1。 1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表 第一章第一章 计算机软件技术基础计算机软件技术基础 1栈的定义栈的定义 栈（栈（Stack）是限制仅在表的一端进行插入和）是限制仅在表的一端进行插入和 删除运算的线性表。栈的示意图

33、如图删除运算的线性表。栈的示意图如图1-4所示：所示： （1）通常称插入、删除的这一端为栈顶，另一端）通常称插入、删除的这一端为栈顶，另一端 称为栈底。称为栈底。 （2）当表中没有元素时称为空栈。）当表中没有元素时称为空栈。 （3）栈为后进先出（）栈为后进先出（Last In First Out）的线性表，）的线性表， 简称为简称为LIFO表。表。 栈的修改是按后进先出的原则进行。栈的修改是按后进先出的原则进行。 1.4 1.4 线性表、栈和队列线性表、栈和队列 二、栈二、栈 第一章第一章 计算机软件技术基础计算机软件技术基础 2栈的基本运算栈的基本运算 （1）InitStack(S)：构造一

34、个空栈：构造一个空栈S。 （2）StackEmpty(S)：判栈空。若：判栈空。若S为空栈，则返回为空栈，则返回TRUE， 否则返回否则返回FALSE。 （3）StackFull(S)：判栈满。若：判栈满。若S为满栈，则返回为满栈，则返回TRUE， 否则返回否则返回FALSE。注意：该运算只适用于栈的顺序存储。注意：该运算只适用于栈的顺序存储 结构。结构。 （4）Push(S,x)：进栈。若栈：进栈。若栈S不满，则将元素不满，则将元素x插入插入S的栈的栈 顶。顶。 （5）Pop(S)：退栈。若栈：退栈。若栈S非空，则将非空，则将S的栈顶元素删去，的栈顶元素删去， 并返回该元素。并返回该元素。

35、（6）StackTop(S)：取栈顶元素。若栈：取栈顶元素。若栈S非空，则返回栈顶非空，则返回栈顶 元素，但不改变栈的状态。元素，但不改变栈的状态。 1.4 1.4 线性表、栈和队列线性表、栈和队列 二、栈二、栈 第一章第一章 计算机软件技术基础计算机软件技术基础 1定义定义 只允许在一端进行插入，而在另一端进行删只允许在一端进行插入，而在另一端进行删 除的运算受限的线性表。除的运算受限的线性表。 （1）允许删除的一端称为队头（）允许删除的一端称为队头（Front）。）。 （2）允许插入的一端称为队尾（）允许插入的一端称为队尾（Rear）。）。 （3）当队列中没有元素时称为空队列。）当队列中没

36、有元素时称为空队列。 （4）队列亦称作先进先出（）队列亦称作先进先出（First In First Out） 的线性表，简称为的线性表，简称为FIFO表。表。 队列的修改是依先进先出的原则进行的。队列的修改是依先进先出的原则进行的。 1.4 1.4 线性表、栈和队列线性表、栈和队列 三、队列三、队列 第一章第一章 计算机软件技术基础计算机软件技术基础 2队列的基本逻辑运算队列的基本逻辑运算 （1）InitQueue(Q)：置空队。构造一个空队列：置空队。构造一个空队列Q。 （2）QueueEmpty(Q)：判队空。若队列：判队空。若队列Q为空，则返回为空，则返回 真值，否则返回假值。真值，否则

37、返回假值。 （3）QueueFull(Q)：判队满。若队列：判队满。若队列Q为满，则返回真值，为满，则返回真值， 否则返回假值。否则返回假值。 注意：注意：此操作只适用于队列的顺序存储结构。此操作只适用于队列的顺序存储结构。 （4）EnQueue(Q,x)：若队列：若队列Q非满，则将元素非满，则将元素x插入插入Q的的 队尾。此操作简称入队。队尾。此操作简称入队。 （5）DeQueue(Q)：若队列：若队列Q非空，则删去非空，则删去Q的队头元素，的队头元素， 并返回该元素。此操作简称出队。并返回该元素。此操作简称出队。 （6）QueueFront(Q)：若队列：若队列Q非空，则返回队头元素，非空

38、，则返回队头元素， 但不改变队列但不改变队列Q的状态。的状态。 1.4 1.4 线性表、栈和队列线性表、栈和队列 三、队列三、队列 第一章第一章 计算机软件技术基础计算机软件技术基础 以链接方式存储的线性表简称为链表。以链接方式存储的线性表简称为链表。 1链表的具体存储表示为：链表的具体存储表示为： 用一组任意的存储单元来存放线性表的结点用一组任意的存储单元来存放线性表的结点 （这组存储单元既可以是连续的，也可以是不（这组存储单元既可以是连续的，也可以是不 连续的）。连续的）。 链表中结点的逻辑次序和物理次序不一定相链表中结点的逻辑次序和物理次序不一定相 同。为了能正确表示结点间的逻辑关系，在

39、存同。为了能正确表示结点间的逻辑关系，在存 储每个结点值的同时，还必须存储指示其后继储每个结点值的同时，还必须存储指示其后继 结点的地址（或位置）信息（称为指针或链结点的地址（或位置）信息（称为指针或链)。 1.5 1.5 线性链表线性链表 一、线性链表的概念一、线性链表的概念 第一章第一章 计算机软件技术基础计算机软件技术基础 2链表的结点结构链表的结点结构 1.5 1.5 线性链表线性链表 一、线性链表的概念一、线性链表的概念 datanext data域域存放结点值的数据域。存放结点值的数据域。 next域域存放结点的直接后继的地址的指针域。存放结点的直接后继的地址的指针域。 其中：其中

40、： 链表通过每个结点的链域将线性表的链表通过每个结点的链域将线性表的n 个结点按其逻辑顺序链接在一起的。个结点按其逻辑顺序链接在一起的。 每个结点只有一个链域的链表称为单链表。每个结点只有一个链域的链表称为单链表。 每个结点有两个链域的链表，既指出该数据元每个结点有两个链域的链表，既指出该数据元 素的后继素的后继,指出前驱，则这种链表称为双链表。指出前驱，则这种链表称为双链表。 第一章第一章 计算机软件技术基础计算机软件技术基础 在单链表中增加一个表头结点，指针域指向线在单链表中增加一个表头结点，指针域指向线 形表的第一个元素的结点，令最后一个结点的形表的第一个元素的结点，令最后一个结点的 指

41、针域指向表头结点，即构成了循环链表，指针域指向表头结点，即构成了循环链表，在在 循环链表中，所有结点的指针构成了一个环状循环链表中，所有结点的指针构成了一个环状 链。链。 1.5 1.5 线性链表线性链表 一、线性链表的概念一、线性链表的概念 a1aiai+1an 第一章第一章 计算机软件技术基础计算机软件技术基础 n线性链表的基本运算主要有以下几个：线性链表的基本运算主要有以下几个： （1）在线性链表中包含指定元素的结点之前插入）在线性链表中包含指定元素的结点之前插入 一个新元素一个新元素 （2）在线性链表中删除包含指定元素的结点）在线性链表中删除包含指定元素的结点 （3）将两个线性链表按要

42、求合并成一个线性链表）将两个线性链表按要求合并成一个线性链表 （4）将一个线性链表按要求进行分解。）将一个线性链表按要求进行分解。 （5）逆转线性链表）逆转线性链表 （6）复制线性链表）复制线性链表 （7）线性链表的排序）线性链表的排序 （8）线性链表的查找）线性链表的查找 1.5 1.5 线性链表线性链表 二、二、线性链表的基本运算线性链表的基本运算 第一章第一章 计算机软件技术基础计算机软件技术基础 1.插入运算插入运算 思想方法思想方法:插入运算是将值为插入运算是将值为x的新结点插入的新结点插入 到表的第到表的第i个结点的位置上，即插入到个结点的位置上，即插入到ai与与ai1 之间。之间

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

44、中结点 ai的存储地址是在其直接前趋结点的存储地址是在其直接前趋结点ai-1的指针域的指针域 next中）；中）； （2）令）令pnext指向指向ai的直接后继结点（即把的直接后继结点（即把ai 从链上摘下）；从链上摘下）； （3）释放结点）释放结点ai的空间，将其归还给的空间，将其归还给“存储池存储池”。 1.5 1.5 线性链表线性链表 二、二、线性链表的基本运算线性链表的基本运算 第一章第一章 计算机软件技术基础计算机软件技术基础 n树形结构是一类重要的非线性结构。树形结构树形结构是一类重要的非线性结构。树形结构 是结点之间有分支，并具有层次关系的结构。是结点之间有分支，并具有层次关系的

45、结构。 如家谱、行政组织机构都可用树形象地表示。如家谱、行政组织机构都可用树形象地表示。 1.6 1.6 树树 一、什么是树一、什么是树 经济管理学经济管理学 院院 经济信息系经济信息系计划统计系计划统计系外贸系外贸系 信息处理信息处理 教研室教研室 经济数学经济数学 教研室教研室 计划学计划学 教研室教研室 统计学统计学 教研室教研室 外语外语 教研室教研室 国际贸易国际贸易 教研室教研室 第一章第一章 计算机软件技术基础计算机软件技术基础 2树结构的基本术语树结构的基本术语 在树结构中，每一个结点只有一个前件，称为在树结构中，每一个结点只有一个前件，称为 父结点。父结点。 没有前件的结点只

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

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

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

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

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

51、树。高度，它是具有最多结点数的二叉树。 满二叉树中不存在度数为满二叉树中不存在度数为1的结点，每个分支结的结点，每个分支结 点均有两棵高度相同的子树，且树叶都在最下点均有两棵高度相同的子树，且树叶都在最下 一层上。一层上。 1.6 1.6 树树 二、二、二叉树的基本性质二叉树的基本性质 第一章第一章 计算机软件技术基础计算机软件技术基础 （2）完全二叉树）完全二叉树(Complete BinaryTree) 若一棵二叉树至多只有最下面的两层上结点的度数可若一棵二叉树至多只有最下面的两层上结点的度数可 以小于以小于2，并且最下一层上的结点都集中在该层最左边，并且最下一层上的结点都集中在该层最左边

52、 的若干位置上，则此二叉树称为完全二叉树。的若干位置上，则此二叉树称为完全二叉树。 完全二叉树的特点：完全二叉树的特点： 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 在满二叉树的最下一层，从最右边开始连续删去若干结在满二叉树的最下一层，从最右边开始连续删去若干结 点后得到的二叉树仍然是一棵完全二叉树。点后得到的二叉树仍然是一棵完全二叉树。 在完全二叉树中，若某个结点没有左孩子，则它一定没在完全二叉树中，若某个结点没有左孩子，则它一定没 有右孩子，即该结点必是叶结点。有右孩子，即该结点必是叶结点。 1.6 1.6 树树 二、二、二叉树的基

53、本性质二叉树的基本性质 第一章第一章 计算机软件技术基础计算机软件技术基础 n链接的方法是它最自然的存储表示方法。链接的方法是它最自然的存储表示方法。 n每个结点有一个数据域，两个指针域。数据域每个结点有一个数据域，两个指针域。数据域 存储数据元素的值，两个指针分别指向该数据存储数据元素的值，两个指针分别指向该数据 元素的左子女和右子女。当某个子女不存在时，元素的左子女和右子女。当某个子女不存在时， 相应的指针为空指针。结点形式如下：相应的指针为空指针。结点形式如下： 1.6 1.6 树树 三、三、二叉树的存储结构二叉树的存储结构 llinkinforlink 一棵二叉树的所有这样形式的结点，

54、再加上一个一棵二叉树的所有这样形式的结点，再加上一个 指向根的指针，就构成此二叉树的存储表示。这指向根的指针，就构成此二叉树的存储表示。这 种存储表示法称为种存储表示法称为llink-rlink表示法或称为二叉链表示法或称为二叉链 表。表。 第一章第一章 计算机软件技术基础计算机软件技术基础 n遍历一棵二叉树实际上是对二叉树的结点进遍历一棵二叉树实际上是对二叉树的结点进 行一次扫描，是将二叉树的结点放入一个线性行一次扫描，是将二叉树的结点放入一个线性 序列的过程，或者说把二叉树进行线性化。遍序列的过程，或者说把二叉树进行线性化。遍 历运算是二叉树的一种最基本的运算。历运算是二叉树的一种最基本的

55、运算。 遍历二叉树有三种主要的方法：前序法、中遍历二叉树有三种主要的方法：前序法、中 序法和后序法。序法和后序法。 前序法，其操作如下：前序法，其操作如下： 访问根；访问根； 按前序遍历左子树；按前序遍历左子树； 按前序遍历右子树。按前序遍历右子树。 1.6 1.6 树树 四、四、二叉树的运算二叉树的运算 第一章第一章 计算机软件技术基础计算机软件技术基础 中序法，其操作如下：中序法，其操作如下： 按中序遍历左子树；按中序遍历左子树； 访问根；访问根； 按中序遍历右子树。按中序遍历右子树。 后序法，其操作如下：后序法，其操作如下： 按后序遍历左子树；按后序遍历左子树； 按后序遍历右子树；按后序

56、遍历右子树； 访问根。访问根。 1.6 1.6 树树 四、四、二叉树的运算二叉树的运算 第一章第一章 计算机软件技术基础计算机软件技术基础 + * 8 35 6 2 / 1.6 1.6 树树 四、四、二叉树的运算二叉树的运算 对于图中的二叉树，它的对于图中的二叉树，它的 三种方法遍历结果是：三种方法遍历结果是： 前序序列：前序序列： * 3 5 6 2 8 中序序列：中序序列： 3 * 5 6 2 8 后序序列：后序序列： 3 5 * 6 2 8 第一章第一章 计算机软件技术基础计算机软件技术基础 n顺序查找又称顺序搜索。顺序查找一般是指在线性表中顺序查找又称顺序搜索。顺序查找一般是指在线性表

57、中 查找指定的元素，其基本方法如下：查找指定的元素，其基本方法如下： n从线性表的第一个元素开始，依次将线性表中的元素与从线性表的第一个元素开始，依次将线性表中的元素与 被查元素进行比较，若相等则表示找到（即查找成功被查元素进行比较，若相等则表示找到（即查找成功)； 若线性表中所有的元素都与被查元素进行了比较但都不若线性表中所有的元素都与被查元素进行了比较但都不 相等，则表示线性表中没有要找的元素相等，则表示线性表中没有要找的元素(即查找失败即查找失败)。 n在下列两种情况下也只能采用顺序查找：在下列两种情况下也只能采用顺序查找： (1)如果线性表为无序表如果线性表为无序表(即表中元素的排列是

58、无序的即表中元素的排列是无序的)，则，则 不管是顺序存储结构还是链式存储结构，都只能用顺序不管是顺序存储结构还是链式存储结构，都只能用顺序 查找。查找。 (2)即使是有序线性表，如果采用链式存储结构，也只能用即使是有序线性表，如果采用链式存储结构，也只能用 顺序查找。顺序查找。 1.7 1.7 查找技术查找技术 一、顺序查找一、顺序查找 第一章第一章 计算机软件技术基础计算机软件技术基础 1.7 1.7 查找技术查找技术 二、二分法查找二、二分法查找 n二分法查找只适用于顺序存储的有序表。二分法查找只适用于顺序存储的有序表。 设有序线性表的长度为设有序线性表的长度为n，被查元素为，被查元素为x

59、，则对二，则对二 分查找的方法如下：分查找的方法如下： 将将x与线性表的中间项进行比较：与线性表的中间项进行比较： 若中间项的值等于若中间项的值等于x，则说明查到，查找结束；，则说明查到，查找结束； 若若x小于中间项的值，则在线性表的前半部分小于中间项的值，则在线性表的前半部分 (即中间项以前的部分即中间项以前的部分)以相同的方法进行查找；以相同的方法进行查找； 若若x大于中间项的值，则在线性表的后半部分大于中间项的值，则在线性表的后半部分 (即中间项以后的部分即中间项以后的部分)以相同的方法进行查找。以相同的方法进行查找。 第一章第一章 计算机软件技术基础计算机软件技术基础 n所谓排序是指将

60、一个无序序列整理成按值递减（或递增）所谓排序是指将一个无序序列整理成按值递减（或递增） 顺序排列的有序序列。顺序排列的有序序列。 n1冒泡排序冒泡排序 冒泡排序法的基本过程是：首先，从表头开始往后扫描冒泡排序法的基本过程是：首先，从表头开始往后扫描 线性表，在扫描过程中逐次比较相邻两个元素的大小。线性表，在扫描过程中逐次比较相邻两个元素的大小。 若相邻两个元素中，前面的元素大于后面的元素，则将若相邻两个元素中，前面的元素大于后面的元素，则将 它们互换，称之为消去了一个逆序：显然，在扫描过程它们互换，称之为消去了一个逆序：显然，在扫描过程 中，不断地将两相邻元素中的大者往后移动，最后就将中，不断