第一章 软件技术基础第一章 计算机软件技术基础
软件系统是计算机为某种特定目的而运行所需要的程序以及程序运行时所需要的数据和有关的技术资料，简称软件。
计算机语言经过了机器语言、汇编语言、高级语言三代。
高级语言发展依据程序设计方法经历了三个时期：
线性程序设计语言
结构化程序设计语言
面向对象程序设计语言
1.1 计算机软件的发展概况一、计算机语言的发展第一章 计算机软件技术基础
计算机操作系统的发展经历了两个阶段。
第一个阶段为单用户、单任务的操作系统，以 CP/M,MS-DOS等磁盘操作系统为代表；
第二个阶段是多用户多任务和分时系统。
以 UNIX,Windows,Linux以及 Mac OS
操作系统为代表。
1.1 计算机软件的发展概况二、操作系统的发展第一章 计算机软件技术基础
1,CP/M操作系统是第一个微机操作系统,这个系统允许用户通过控制台的键盘对系统进行控制和管理,其主要功能是对文件信息进行管理,以实现硬盘文件或其他设备文件的自动存取 。
2,DOS操作系统其中最成功的是微软的 MS-DOS,它是在 IBM-PC及其兼容机上运行的操作系统,它起源于 SCP86-DOS（ 也是
CP/M一类的操作系统 ）,是 1980年基于 8086微处理器而设计的单用户操作系统 。
1.1 计算机软件的发展概况二、操作系统的发展第一章 计算机软件技术基础
3,Windows操作系统
Windows是 Microsoft公司在 1985年 11月开始发布的窗口式多任务系统，它使微机进入了图形用户界面时代。
其主要特点如下：
界面图形化，多用户、多任务，网络支持良好，
出色的多媒体功能，硬件支持良好，众多的应用程序 等于。
1.1 计算机软件的发展概况二、操作系统的发展第一章 计算机软件技术基础
4,UNIX操作系统
UNIX操作系统并非指单一的操作系统软件,而是包括一系列的 UNIX家族,AIX,BSD,Digital UNIX,Free
BSD,HP-UX,IRIX,SunOS等 。 它是一个真正的多用户分时系统 。
UNIX系统主要用于小型机,工作站和服务器 。
5,Linux操作系统它是一个免费软件,您可以自由安装并任意修改软件的源代码 。
Linux操作系统与主流的 UNIX系统兼容,这使得它一出现就有了一个很好的用户群 。
支持几乎所有的硬件平台,包括 Intel系列,680x0系列,
Alpha系列,MIPS系列等,并广泛支持各种周边设备 。
1.1 计算机软件的发展概况二、操作系统的发展第一章 计算机软件技术基础
6,Mac OS操作系统
Mac OS是一套运行于苹果 Macintosh系列电脑上的操作系统。 1984年，苹果公司发布了 System 1，这是一个黑白界面的，也是世界上第一款成功的图形化用户界面操作系统。
1.1 计算机软件的发展概况二、操作系统的发展第一章 计算机软件技术基础
1,软件开发经历的三个时期
项式程序时期 （ 1947-1960年初 ）,程序作为机器运行时必须进行的准备工作 。 程序设计全凭设计者个人经验和技艺独立进行,是一种典型的手工艺智力劳动 。
软件 =程序 +说明时期 （ 20世纪 50年代末 -20世纪
70年代初 ）,程序规模较大,需要多人协作才能完成；程序的设计与运行维护不能由一个人来承担；程序不再是计算机硬件的附属部分,而是计算机系统中与硬件相互依存不可缺少的部分 。
1.1 计算机软件的发展概况三、软件开发与软件产业第一章 计算机软件技术基础
软件 =程序 +文档时期（ 20世纪 70年代至今，即软件工程时期），用,工程化,的思想作指导来解决软件研究和开发中面临的困难和混乱。
软件产业的不成熟体现在两个方面：
第一，与软件研发相关技术和理论还没有成熟；
第二，软件工程化水平不成熟。
1.1 计算机软件的发展概况三、软件开发与软件产业第一章 计算机软件技术基础
1,系统软件系统软件是指管理,监控和维护计算机系统正常工作的程序和有关资料 。 主要包括：
操作系统 。
各种语言解释程序和编译程序 （ 如 BASIC解释程序,C编译程序等 ） 。
各种服务性程序 （ 如机器的调试,故障检查与诊断程序等 ） 。
1.1 计算机软件的发展概况四、系统软件和应用软件第一章 计算机软件技术基础
2,应用软件
应用软件是指为解决某个实际问题而编制的程序和有关资料 。
应用软件又可分为：应用软件包和用户程序 。
应用软件包是生产厂家或软件公司,为解决带有通用性问题而精心研制的程序供用户选择使用,
软件包种类繁多,如标准函数库,子程序库,文字处理等 。
用户程序则是为特定用户解决特定问题而开发的软件,通常由自己或委托别人研制,是面向特定用户的应用软件 。
1.1 计算机软件的发展概况四、系统软件和应用软件第一章 计算机软件技术基础
数据结构 （ Data Structure） 指的是数据之间的相互关系,即数据的组织形式 。
数据结构一般包括以下三方面内容：
① 数据元素之间的逻辑关系，也称数据的逻辑结构（ Logical Structure）；
② 数据元素及其关系在计算机存储器内的表示，
称为数据的存储结构（ Storage Structure）；
③ 数据的运算，即对数据施加的操作。
1.2 数据结构概论一、什么是数据结构第一章 计算机软件技术基础
[例 1.1] 设有一学生成绩表。
1.2 数据结构概论一、什么是数据结构学号 姓 名 英语 数学 物理平均成绩201000
1
张 平 88 95 66 832 1
000
2
赵 军 92 84 98 91.32 1
000
3
刘 冰 79 73 78 76.7…
… …… …… …… …… ……
（ 1）逻辑结构表中的每一行是一个数据元素 （ 或记录,结点 ）,它由学号,姓名,各科成绩及平均成绩等数据项组成 。
第一章 计算机软件技术基础表中数据元素之间的逻辑关系是：对表中任一个结点，
与它相邻且在它前面的结点（亦称为直接前趋）最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继）也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。
（ 2） 存储结构存储结构是指用计算机语言如何表示结点之间的这种关系,即表中的结点是顺序邻接地存储在一片连续的单元之中,还是用指针将这些结点链接在一起 。
（ 3） 数据的运算
1.2 数据结构概论一、什么是数据结构第一章 计算机软件技术基础
数据结构的图形表示中,对于数据集合 D中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据结点,并简称为结点；为了进一步表示各数据元素之间的前后件关系,对于关系 R
中的每一个二元组,用一条有向线段从前件结点指向后件结点 。
1.2 数据结构概论二、数据结构的图形表示如：一年四季的数据结构可以用图形来表示。
第一章 计算机软件技术基础如：反映家庭成员间辈分关系的数据结构可以用图形来表示 。
1.2 数据结构概论二、数据结构的图形表示第一章 计算机软件技术基础数据的逻辑结构有两大类：
（ 1） 线性结构线性结构的逻辑特征：若结构是非空集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继 。
线性表是一个典型的线性结构 。 栈,队列,串等都是线性结构 。
（ 2） 非线性结构非线性结构的逻辑特征：一个结点可能有多个直接前趋和直接后继 。 数组,广义表,树和图等数据结构都是非线性结构 。
1.2 数据结构概论三、线性结构与非线性结构第一章 计算机软件技术基础
1,算法所谓算法是指解题方案的准确而完整的描述。
2,算法的基本特征
（ 1）可行性
（ 2）确定性
（ 3）有穷性
（ 4）拥有足够的情报
1.3 算法及算法分析一、算法第一章 计算机软件技术基础
3,算法的基本要素一个算法通常由两种基本要素组成：一是对数据对象的运算和操作,二是算法的控制结构 。
（ 1） 算法中对数据的运算和操作基本的运算和操作有以下四类：
① 算术运算：主要包括加,减,乘,除等运算 。
② 逻辑运算：主要包括,与,,,或,,,非,
等运算 。
③ 关系运算：主要包括,大于,,,小于,,
,等于,,,不等于,等运算：
④ 数据传输：主要包括赋值,输入,输出等操作 。
1.3 算法及算法分析一、算法第一章 计算机软件技术基础
（ 2）算法的控制结构算法的控制结构给出了算法的基本框架,它不仅决定了算法中各操作的执行顺序,而且也直接反映了算法的设计是否符合结构化原则 。 描述算法的工具通常有传统流程图,N-S结构化流程图,
算法描述语言等 。 一个算法一般都可以用顺序,
选择,循环三种基本控制结构组合而成 。
1.3 算法及算法分析一、算法第一章 计算机软件技术基础
4,算法设计基本方法
（ 1） 列举法根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的 。
（ 2） 归纳法通过列举少量的特殊情况,经过分析,最后找出一般的关系 。
（ 3） 递推所谓递推,是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果 。 其中初始条件或是问题本身已经给定,或是通过对问题的分析与化简而确定 。
（ 4） 递归
（ 5） 减半递推技术
1.3 算法及算法分析一、算法第一章 计算机软件技术基础
对算法的分析主要是对算法的时间复杂度和空间复杂度的分析。
1．时间复杂度
一个算法的时间复杂度是该算法的时间耗费,即算法执行过程中所需要的基本运算次数 。
一个算法所耗费的时间 =算法中每条语句的执行时间之和 。 每条语句的执行时间 =语句的执行次数 × 语句执行一次所需时间 。
2．空间复杂度
一个算法的空间复杂度为该算法在执行过程中所需要的存储空间 。
算法的时间复杂度和空间复杂度合称为算法的复杂度 。
1.3 算法及算法分析二、算法分析第一章 计算机软件技术基础
1,线性表的逻辑定义线性表 （ Linear List） 是由 n（ n≥0） 个数据元素 （ 结点 ）
a1,a2,…,an组成的有限序列 。
① 数据元素的个数 n定义为表的长度 （ n=0时称为空表 ） 。
② 将非空的线性表 （ n＞ 0） 记作,（ a1,a2,…,an）
③ 数据元素 ai（ 1≤ i ≤ n） 只是个抽象符号,其具体含义在不同情况下可以不同 。
如学生成绩表中，每个学生及其成绩是一个数据元素，
其中数据元素由学号、姓名、各科成绩等数据项组成。
1.4 线性表、栈和队列一、线性表第一章 计算机软件技术基础
2．线性表的逻辑结构特征对于非空的线性表,
① 有且仅有一个开始结点 a1，没有直接前趋，有且仅有一个直接后继 a2；
② 有且仅有一个终结结点 an，没有直接后继，有且仅有一个直接前趋 an-1；
③ 其余的内部结点 ai（ 2≤i≤n－ 1）都有且仅有一个直接前趋 ai-1和一个直接后继 ai＋ 1。
1.4 线性表、栈和队列一、线性表第一章 计算机软件技术基础
3．线性表的顺序存储结构有顺序存储和链式存储两种顺序存储方法即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。
用顺序存储方法存储的线性表简称为顺序表。
在顺序表中，每个结点 ai的存储地址是该结点在表中的位置 i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。
1.4 线性表、栈和队列一、线性表第一章 计算机软件技术基础
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中有多个结点的值和 x 相同，则返回首次找到的结点位置；若
L中没有结点的值为 x，则返回一个特殊值表示查找失败。
1.4 线性表、栈和队列一、线性表第一章 计算机软件技术基础
（ 5） InsertList(L,x,i)：在线性表 L的第 i个位置上插入一个值为 x 的新结点，使得原编号为 i,i＋
1,…,n的结点变为编号为 i＋ 1,i＋ 2,…,n
＋ 1的结点。这里 1 ≤ i ≤ n＋ 1，而 n是原表 L的长度。插入后，表 L的长度加 1。
（ 6） DeleteList(L,i)：删除线性表 L的第 i个结点，
使得原编号为 i＋ 1,i＋ 2,…,n的结点变成编号为 i,i＋ 1,…,n－ 1的结点。这里 1 ≤ i ≤ n，
而 n是原表 L的长度。删除后表 L的长度减 1。
1.4 线性表、栈和队列一、线性表第一章 计算机软件技术基础
1．栈的定义栈（ Stack）是限制仅在表的一端进行插入和删除运算的线性表。栈的示意图如图 1-4所示：
（ 1）通常称插入、删除的这一端为栈顶，另一端称为栈底。
（ 2）当表中没有元素时称为空栈。
（ 3）栈为后进先出（ Last In First Out）的线性表，
简称为 LIFO表。
栈的修改是按后进先出的原则进行。
1.4 线性表、栈和队列二、栈第一章 计算机软件技术基础
2．栈的基本运算
（ 1） InitStack(S)：构造一个空栈 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的栈顶元素删去，
并返回该元素。
（ 6） StackTop(S)：取栈顶元素。若栈 S非空，则返回栈顶元素，但不改变栈的状态。
1.4 线性表、栈和队列二、栈第一章 计算机软件技术基础
1．定义只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
（ 1）允许删除的一端称为队头（ Front）。
（ 2）允许插入的一端称为队尾（ Rear）。
（ 3）当队列中没有元素时称为空队列。
（ 4）队列亦称作先进先出（ First In First Out）
的线性表，简称为 FIFO表。
队列的修改是依先进先出的原则进行的。
1.4 线性表、栈和队列三、队列第一章 计算机软件技术基础
2．队列的基本逻辑运算
（ 1） InitQueue(Q)：置空队。构造一个空队列 Q。
（ 2） QueueEmpty(Q)：判队空。若队列 Q为空，则返回真值，否则返回假值。
（ 3） QueueFull(Q)：判队满。若队列 Q为满，则返回真值，
否则返回假值。
注意,此操作只适用于队列的顺序存储结构。
（ 4） EnQueue(Q,x)：若队列 Q非满，则将元素 x插入 Q的队尾。此操作简称入队。
（ 5） DeQueue(Q)：若队列 Q非空，则删去 Q的队头元素，
并返回该元素。此操作简称出队。
（ 6） QueueFront(Q)：若队列 Q非空，则返回队头元素，
但不改变队列 Q的状态。
1.4 线性表、栈和队列三、队列第一章 计算机软件技术基础以链接方式存储的线性表简称为链表。
1．链表的具体存储表示为：
① 用一组任意的存储单元来存放线性表的结点
（这组存储单元既可以是连续的，也可以是不连续的）。
② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针或链 )。
1.5 线性链表一、线性链表的概念第一章 计算机软件技术基础
2．链表的结点结构
1.5 线性链表一、线性链表的概念
data next
data域 —存放结点值的数据域 。
next域 —存放结点的直接后继的地址的指针域 。
其中,① 链表通过每个结点的链域将线性表的 n
个结点按其逻辑顺序链接在一起的 。
② 每个结点只有一个链域的链表称为单链表 。
③ 每个结点有两个链域的链表,既指出该数据元素的后继,指出前驱,则这种链表称为双链表 。
第一章 计算机软件技术基础
④ 在单链表中增加一个表头结点，指针域指向线形表的第一个元素的结点，令最后一个结点的指针域指向表头结点，即构成了循环链表,在循环链表中，所有结点的指针构成了一个环状链。
1.5 线性链表一、线性链表的概念
a1 ai ai+1 an ∧…
第一章 计算机软件技术基础
线性链表的基本运算主要有以下几个：
（ 1）在线性链表中包含指定元素的结点之前插入一个新元素
（ 2）在线性链表中删除包含指定元素的结点
（ 3）将两个线性链表按要求合并成一个线性链表
（ 4）将一个线性链表按要求进行分解。
（ 5）逆转线性链表
（ 6）复制线性链表
（ 7）线性链表的排序
（ 8）线性链表的查找
1.5 线性链表二,线性链表的基本运算第一章 计算机软件技术基础
1.插入运算思想方法,插入运算是将值为 x的新结点插入到表的第 i个结点的位置上，即插入到 ai与 ai＋ 1
之间。
具体步骤：
（ 1）找到 ai存储位置 p；
（ 2）生成一个数据域为 x的新结点 ax；
（ 3）令结点 *p的指针域指向新结点；
（ 4）新结点的指针域指向结点 ai＋ 1。
1.5 线性链表二,线性链表的基本运算第一章 计算机软件技术基础
2.删除运算思想方法,删除运算是将表的第 i个结点删去。
具体步骤：
（ 1）找到 ai-1的存储位置 p（因为在单链表中结点
ai的存储地址是在其直接前趋结点 ai-1的指针域
next中）；
（ 2）令 p－＞ next指向 ai的直接后继结点（即把 ai
从链上摘下）；
（ 3）释放结点 ai的空间，将其归还给“存储池”。
1.5 线性链表二,线性链表的基本运算第一章 计算机软件技术基础
树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。
如家谱、行政组织机构都可用树形象地表示。
1.6 树一、什么是树经济管理学院经济信息系 计划统计系 外贸系信息处理教研室经济数学教研室计划学教研室统计学教研室外语教研室国际贸易教研室第一章 计算机软件技术基础
2．树结构的基本术语
在树结构中，每一个结点只有一个前件，称为父结点。
没有前件的结点只有一个，称为树的根结点。
每一个结点可以有多个后件，都称为该结点的子结点。
没有后件的结点称为叶子结点。
一个结点所拥有的后件个数称为该结点的度。
一棵树的度是指该树中结点的最大度数。
1.6 树一、什么是树第一章 计算机软件技术基础
结点的层数 (Level)：从根起算，根的层数为 1，
其余结点的层数等于其双亲结点的层数加 1。
树中结点的最大层数称为树的高度 (Height)或深度 (Depth)。
A
CB
HD F
I J
GE
1.6 树一、什么是树图中,树的根结点 A度为 2，
结点 B的度为 3,结点 I的度为
0,树的度为 3,结点 A在第一层,结点 B,C在第二层,结点 D,E,F,G,H在第三层,结点 I,J
在第四层 。
第一章 计算机软件技术基础
森林 (Forest)是 m(m≥0)棵互不相交的树的集合。
树和森林的概念相近。删去一棵树的根，
就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。
1.6 树一、什么是树第一章 计算机软件技术基础
1.二叉树的特点
（ 1）非空二叉树只有一个根结点。
（ 2）每一个结点最多有两棵子树，称为该结点的左子树和右子树。
如算术运算式 3 * 5 ＋ 6 / 2 – 8就可用二叉树表示。
1.6 树二,二叉树的基本性质
+
－*
83 5
6 2
/
第一章 计算机软件技术基础
2.二叉树具有以下重要性质：
性质 1 二叉树第 i层上的结点数目最多为 2i－ 1(i≥1)。
性质 2 深度为 k的二叉树至多有 2k－ 1个结点 (k≥1)。
性质 3 在任意一棵二叉树中，若终端结点的个数为 n0，度为 2的结点数为 n2，则 no=n2＋ 1。
性质 4 具有 n个结点的完全二叉树的深度为：
（或 ）。
1l?gn
1.6 树二,二叉树的基本性质
1lg?n
)1lg( n?
第一章 计算机软件技术基础
3.满二叉树和完全二叉树是二叉树
（ 1）满二叉树 (FullBinaryTree)
一棵深度为 k且有 2k－ 1个结点的二叉树称为满二叉树。
满二叉树的特点：
① 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
② 满二叉树中不存在度数为 1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
1.6 树二,二叉树的基本性质第一章 计算机软件技术基础
（ 2）完全二叉树 (Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于 2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
完全二叉树的特点：
① 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
② 在满二叉树的最下一层，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
③ 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
1.6 树二,二叉树的基本性质第一章 计算机软件技术基础
链接的方法是它最自然的存储表示方法。
每个结点有一个数据域，两个指针域。数据域存储数据元素的值，两个指针分别指向该数据元素的左子女和右子女。当某个子女不存在时，
相应的指针为空指针。结点形式如下：
1.6 树三,二叉树的存储结构
llink info rlink
一棵二叉树的所有这样形式的结点,再加上一个指向根的指针,就构成此二叉树的存储表示 。 这种存储表示法称为 llink-rlink表示法或称为二叉链表 。
第一章 计算机软件技术基础
遍历一棵二叉树实际上是对二叉树的结点进行一次扫描，是将二叉树的结点放入一个线性序列的过程，或者说把二叉树进行线性化。遍历运算是二叉树的一种最基本的运算。
遍历二叉树有三种主要的方法：前序法、中序法和后序法。
① 前序法，其操作如下：
访问根；
按前序遍历左子树；
按前序遍历右子树。
1.6 树四,二叉树的运算第一章 计算机软件技术基础
② 中序法，其操作如下：
按中序遍历左子树；
访问根；
按中序遍历右子树。
③ 后序法，其操作如下：
按后序遍历左子树；
按后序遍历右子树；
访问根。
1.6 树四,二叉树的运算第一章 计算机软件技术基础
+
－*
83 5
6 2
/
1.6 树四,二叉树的运算对于图中的二叉树，它的三种方法遍历结果是：
前序序列：
＋ * 3 5 － ／ 6 2 8
中序序列：
3 * 5 ＋ 6 ／ 2 － 8
后序序列：
3 5 * 6 2 ／ 8 － ＋
第一章 计算机软件技术基础
顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下：
从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功 )；
若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素 (即查找失败 )。
在下列两种情况下也只能采用顺序查找：
(1)如果线性表为无序表 (即表中元素的排列是无序的 )，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
(2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
1.7 查找技术一、顺序查找第一章 计算机软件技术基础
1.7 查找技术二、二分法查找
二分法查找只适用于顺序存储的有序表。
设有序线性表的长度为 n，被查元素为 x，则对二分查找的方法如下：
将 x与线性表的中间项进行比较：
若中间项的值等于 x，则说明查到，查找结束；
若 x小于中间项的值，则在线性表的前半部分
(即中间项以前的部分 )以相同的方法进行查找；
若 x大于中间项的值，则在线性表的后半部分
(即中间项以后的部分 )以相同的方法进行查找。
第一章 计算机软件技术基础
所谓排序是指将一个无序序列整理成按值递减（或递增）
顺序排列的有序序列。
1．冒泡排序冒泡排序法的基本过程是：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。
若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序：显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后，这也是最大元素应有的位置。
依次剩下的线性表元素重复上述过程，直到线性表中每一个元素都找到它应有的位置，此时的线性表变为有序。
1.7 查找技术三、排序技术第一章 计算机软件技术基础
2．快速排序
快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。
快速排序法的基本思想如下：
从线性表中选取一个元素，设为 T，将线性表后面小于 T的元素移到前面，而前面大于 T的元素移到后面。
结果就将线性表分成了两部分 (称为两个子表 ),T插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以 T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于
T，而后面子表中的所有元素均不小于 T。
如果对分割后的各子表再按上述原则进行分割，并且，
这种分割过程可以一直做下去，直到所有子表为空为止，
则此时的线性表就变成了有序表。
1.7 查找技术三、排序技术第一章 计算机软件技术基础
3.简单插入排序
所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。
我们从线性表的第 2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面的有序子表中。在简单插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡法相同。在最坏情况下，排序需要经过 n（ n－ 1） /2次的比较。
1.7 查找技术三、排序技术第一章 计算机软件技术基础
4．希尔排序
希尔排序属于插入类排序，但它对简单插入排序做了较大的改进。
希尔排序的基本思想如下：
将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法是将相隔某个增量 h的元素构成一个子序列。在排序过程中，
逐次减小这个增量，最后当 h减到 1时，进行一次插入排序，排序就完成。增量序列一般取
ht=n/2K(K=1,2,…,[log2n),其中 n为待排序序列的长度。
1.7 查找技术三、排序技术第一章 计算机软件技术基础
5．简单选择排序
选择排序方法中最简单的一种就是直接选择排序算法。
其操作过程是：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。先选出最小的元素并将其与第一个元素交换。然后在剩下的 n－ 1个元素中再选出最小的元素与第二个元素交换 …… 最后在剩下的两个元素中。选出一个小的元素与第 n－ 1个元素交换。
1.7 查找技术三、排序技术第一章 计算机软件技术基础
6．堆排序
堆排序属于选择类的排序方法。
根据堆的定义，可以得到堆排序的方法如下：
（ 1）首先将一个无序序列建成堆。
（ 2）然后将堆顶元素与堆中最后一个元素交换。
不考虑已经换到最后的那个元素，只考虑前 n
－ 1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做第（ 2）步，直到剩下的子序列为空为止。
1.7 查找技术三、排序技术第一章 计算机软件技术基础
1．结构化程序设计的原则
（ 1）自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。
（ 2）逐步求精：对复杂问题，应设计一些子目标作过渡，
逐步细化。
（ 3）模块化：一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，
再进一步分解为具体的小目标，把每个小目标称为一个模块。
（ 4）限制使用 goto语句：限制使用 goto语句后，程序易理解、易排错、易维护，程序容易进行正确性证明。
1.8 程序设计文法一、结构化程序设计第一章 计算机软件技术基础
2.结构化程序的基本结构与特点
（ 1）顺序结构：顺序结构是顺序执行结构 。
（ 2）选择结构：可以根据设定的条件，判断应该选择哪一条分支来执行相应的语句序列。
（ 3）循环结构：它根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段，利用重复结构可简化大量的程序行。
3、按结构化程序设计方法设计出的程序具有的优点：
其一，程序易于理解、使用和维护。
其二，提高了编程工作的效率，降低了软件开发成本。
1.8 程序设计文法一、结构化程序设计第一章 计算机软件技术基础
3.结构化程序设计原则和方法的应用
（ 1）使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；
（ 2）选用的控制结构只准许有一个入口和一个出口；
（ 3）程序语句组成容易识别的块，每块只有一个入口和一个出口；
（ 4）复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；
（ 5）语言中所没有的控制结构，应该采用前后一致的方法来模拟；
（ 6）严格控制 goto语句的使用。
1.8 程序设计文法一、结构化程序设计第一章 计算机软件技术基础
1．对象（ object）
对象是面向对象方法中最基本的概念。对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。
特点：
（ 1）标识唯一性。指对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分。
（ 2）分类性。指可以将具有相同属性和操作的对象抽象成类。
（ 3）多态性。指同一个操作可以是不同对象的行为。
1.8 程序设计文法二、面向对象的程序设计第一章 计算机软件技术基础
（ 4）封装性。从外面看只能看到对象的外部特性，
即只需知道数据的取值范围和可以对该数据施加的操作，根本无需知道数据的具体结构以及实现操作的算法。
（ 5）模块独立性好。
1.8 程序设计文法二、面向对象的程序设计第一章 计算机软件技术基础
2．类（ Class）和实例（ Instance）
类是具有共同属性、共同方法的对象的集合。
类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。
,实例,是指一个具体的对象。
如,Integer是一个整数类，它描述了所有整数的性质。因此任何整数都是整数类的对象，
而一个具体的整数,123”是类 Integer的一个实例。
1.8 程序设计文法二、面向对象的程序设计第一章 计算机软件技术基础
3,消息 （ Message）
对象间的这种相互合作需要一个机制协助进行，
这样的机制称为“消息”。
4．继承（ Inheritance）
继承是面向对象的方法的一个主要特征。继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可当作基类来引用，则新类相应地可当作派生类来引用。
1.8 程序设计文法二、面向对象的程序设计第一章 计算机软件技术基础
5．多态性（ Polymorphism）
对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，
该现象称为多态性。
在面向对象的软件技术中，多态性是指子类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象。
1.8 程序设计文法二、面向对象的程序设计
软件系统是计算机为某种特定目的而运行所需要的程序以及程序运行时所需要的数据和有关的技术资料，简称软件。
计算机语言经过了机器语言、汇编语言、高级语言三代。
高级语言发展依据程序设计方法经历了三个时期：
线性程序设计语言
结构化程序设计语言
面向对象程序设计语言
1.1 计算机软件的发展概况一、计算机语言的发展第一章 计算机软件技术基础
计算机操作系统的发展经历了两个阶段。
第一个阶段为单用户、单任务的操作系统，以 CP/M,MS-DOS等磁盘操作系统为代表；
第二个阶段是多用户多任务和分时系统。
以 UNIX,Windows,Linux以及 Mac OS
操作系统为代表。
1.1 计算机软件的发展概况二、操作系统的发展第一章 计算机软件技术基础
1,CP/M操作系统是第一个微机操作系统,这个系统允许用户通过控制台的键盘对系统进行控制和管理,其主要功能是对文件信息进行管理,以实现硬盘文件或其他设备文件的自动存取 。
2,DOS操作系统其中最成功的是微软的 MS-DOS,它是在 IBM-PC及其兼容机上运行的操作系统,它起源于 SCP86-DOS（ 也是
CP/M一类的操作系统 ）,是 1980年基于 8086微处理器而设计的单用户操作系统 。
1.1 计算机软件的发展概况二、操作系统的发展第一章 计算机软件技术基础
3,Windows操作系统
Windows是 Microsoft公司在 1985年 11月开始发布的窗口式多任务系统，它使微机进入了图形用户界面时代。
其主要特点如下：
界面图形化，多用户、多任务，网络支持良好，
出色的多媒体功能，硬件支持良好，众多的应用程序 等于。
1.1 计算机软件的发展概况二、操作系统的发展第一章 计算机软件技术基础
4,UNIX操作系统
UNIX操作系统并非指单一的操作系统软件,而是包括一系列的 UNIX家族,AIX,BSD,Digital UNIX,Free
BSD,HP-UX,IRIX,SunOS等 。 它是一个真正的多用户分时系统 。
UNIX系统主要用于小型机,工作站和服务器 。
5,Linux操作系统它是一个免费软件,您可以自由安装并任意修改软件的源代码 。
Linux操作系统与主流的 UNIX系统兼容,这使得它一出现就有了一个很好的用户群 。
支持几乎所有的硬件平台,包括 Intel系列,680x0系列,
Alpha系列,MIPS系列等,并广泛支持各种周边设备 。
1.1 计算机软件的发展概况二、操作系统的发展第一章 计算机软件技术基础
6,Mac OS操作系统
Mac OS是一套运行于苹果 Macintosh系列电脑上的操作系统。 1984年，苹果公司发布了 System 1，这是一个黑白界面的，也是世界上第一款成功的图形化用户界面操作系统。
1.1 计算机软件的发展概况二、操作系统的发展第一章 计算机软件技术基础
1,软件开发经历的三个时期
项式程序时期 （ 1947-1960年初 ）,程序作为机器运行时必须进行的准备工作 。 程序设计全凭设计者个人经验和技艺独立进行,是一种典型的手工艺智力劳动 。
软件 =程序 +说明时期 （ 20世纪 50年代末 -20世纪
70年代初 ）,程序规模较大,需要多人协作才能完成；程序的设计与运行维护不能由一个人来承担；程序不再是计算机硬件的附属部分,而是计算机系统中与硬件相互依存不可缺少的部分 。
1.1 计算机软件的发展概况三、软件开发与软件产业第一章 计算机软件技术基础
软件 =程序 +文档时期（ 20世纪 70年代至今，即软件工程时期），用,工程化,的思想作指导来解决软件研究和开发中面临的困难和混乱。
软件产业的不成熟体现在两个方面：
第一，与软件研发相关技术和理论还没有成熟；
第二，软件工程化水平不成熟。
1.1 计算机软件的发展概况三、软件开发与软件产业第一章 计算机软件技术基础
1,系统软件系统软件是指管理,监控和维护计算机系统正常工作的程序和有关资料 。 主要包括：
操作系统 。
各种语言解释程序和编译程序 （ 如 BASIC解释程序,C编译程序等 ） 。
各种服务性程序 （ 如机器的调试,故障检查与诊断程序等 ） 。
1.1 计算机软件的发展概况四、系统软件和应用软件第一章 计算机软件技术基础
2,应用软件
应用软件是指为解决某个实际问题而编制的程序和有关资料 。
应用软件又可分为：应用软件包和用户程序 。
应用软件包是生产厂家或软件公司,为解决带有通用性问题而精心研制的程序供用户选择使用,
软件包种类繁多,如标准函数库,子程序库,文字处理等 。
用户程序则是为特定用户解决特定问题而开发的软件,通常由自己或委托别人研制,是面向特定用户的应用软件 。
1.1 计算机软件的发展概况四、系统软件和应用软件第一章 计算机软件技术基础
数据结构 （ Data Structure） 指的是数据之间的相互关系,即数据的组织形式 。
数据结构一般包括以下三方面内容：
① 数据元素之间的逻辑关系，也称数据的逻辑结构（ Logical Structure）；
② 数据元素及其关系在计算机存储器内的表示，
称为数据的存储结构（ Storage Structure）；
③ 数据的运算，即对数据施加的操作。
1.2 数据结构概论一、什么是数据结构第一章 计算机软件技术基础
[例 1.1] 设有一学生成绩表。
1.2 数据结构概论一、什么是数据结构学号 姓 名 英语 数学 物理平均成绩201000
1
张 平 88 95 66 832 1
000
2
赵 军 92 84 98 91.32 1
000
3
刘 冰 79 73 78 76.7…
… …… …… …… …… ……
（ 1）逻辑结构表中的每一行是一个数据元素 （ 或记录,结点 ）,它由学号,姓名,各科成绩及平均成绩等数据项组成 。
第一章 计算机软件技术基础表中数据元素之间的逻辑关系是：对表中任一个结点，
与它相邻且在它前面的结点（亦称为直接前趋）最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继）也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。
（ 2） 存储结构存储结构是指用计算机语言如何表示结点之间的这种关系,即表中的结点是顺序邻接地存储在一片连续的单元之中,还是用指针将这些结点链接在一起 。
（ 3） 数据的运算
1.2 数据结构概论一、什么是数据结构第一章 计算机软件技术基础
数据结构的图形表示中,对于数据集合 D中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据结点,并简称为结点；为了进一步表示各数据元素之间的前后件关系,对于关系 R
中的每一个二元组,用一条有向线段从前件结点指向后件结点 。
1.2 数据结构概论二、数据结构的图形表示如：一年四季的数据结构可以用图形来表示。
第一章 计算机软件技术基础如：反映家庭成员间辈分关系的数据结构可以用图形来表示 。
1.2 数据结构概论二、数据结构的图形表示第一章 计算机软件技术基础数据的逻辑结构有两大类：
（ 1） 线性结构线性结构的逻辑特征：若结构是非空集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继 。
线性表是一个典型的线性结构 。 栈,队列,串等都是线性结构 。
（ 2） 非线性结构非线性结构的逻辑特征：一个结点可能有多个直接前趋和直接后继 。 数组,广义表,树和图等数据结构都是非线性结构 。
1.2 数据结构概论三、线性结构与非线性结构第一章 计算机软件技术基础
1,算法所谓算法是指解题方案的准确而完整的描述。
2,算法的基本特征
（ 1）可行性
（ 2）确定性
（ 3）有穷性
（ 4）拥有足够的情报
1.3 算法及算法分析一、算法第一章 计算机软件技术基础
3,算法的基本要素一个算法通常由两种基本要素组成：一是对数据对象的运算和操作,二是算法的控制结构 。
（ 1） 算法中对数据的运算和操作基本的运算和操作有以下四类：
① 算术运算：主要包括加,减,乘,除等运算 。
② 逻辑运算：主要包括,与,,,或,,,非,
等运算 。
③ 关系运算：主要包括,大于,,,小于,,
,等于,,,不等于,等运算：
④ 数据传输：主要包括赋值,输入,输出等操作 。
1.3 算法及算法分析一、算法第一章 计算机软件技术基础
（ 2）算法的控制结构算法的控制结构给出了算法的基本框架,它不仅决定了算法中各操作的执行顺序,而且也直接反映了算法的设计是否符合结构化原则 。 描述算法的工具通常有传统流程图,N-S结构化流程图,
算法描述语言等 。 一个算法一般都可以用顺序,
选择,循环三种基本控制结构组合而成 。
1.3 算法及算法分析一、算法第一章 计算机软件技术基础
4,算法设计基本方法
（ 1） 列举法根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的 。
（ 2） 归纳法通过列举少量的特殊情况,经过分析,最后找出一般的关系 。
（ 3） 递推所谓递推,是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果 。 其中初始条件或是问题本身已经给定,或是通过对问题的分析与化简而确定 。
（ 4） 递归
（ 5） 减半递推技术
1.3 算法及算法分析一、算法第一章 计算机软件技术基础
对算法的分析主要是对算法的时间复杂度和空间复杂度的分析。
1．时间复杂度
一个算法的时间复杂度是该算法的时间耗费,即算法执行过程中所需要的基本运算次数 。
一个算法所耗费的时间 =算法中每条语句的执行时间之和 。 每条语句的执行时间 =语句的执行次数 × 语句执行一次所需时间 。
2．空间复杂度
一个算法的空间复杂度为该算法在执行过程中所需要的存储空间 。
算法的时间复杂度和空间复杂度合称为算法的复杂度 。
1.3 算法及算法分析二、算法分析第一章 计算机软件技术基础
1,线性表的逻辑定义线性表 （ Linear List） 是由 n（ n≥0） 个数据元素 （ 结点 ）
a1,a2,…,an组成的有限序列 。
① 数据元素的个数 n定义为表的长度 （ n=0时称为空表 ） 。
② 将非空的线性表 （ n＞ 0） 记作,（ a1,a2,…,an）
③ 数据元素 ai（ 1≤ i ≤ n） 只是个抽象符号,其具体含义在不同情况下可以不同 。
如学生成绩表中，每个学生及其成绩是一个数据元素，
其中数据元素由学号、姓名、各科成绩等数据项组成。
1.4 线性表、栈和队列一、线性表第一章 计算机软件技术基础
2．线性表的逻辑结构特征对于非空的线性表,
① 有且仅有一个开始结点 a1，没有直接前趋，有且仅有一个直接后继 a2；
② 有且仅有一个终结结点 an，没有直接后继，有且仅有一个直接前趋 an-1；
③ 其余的内部结点 ai（ 2≤i≤n－ 1）都有且仅有一个直接前趋 ai-1和一个直接后继 ai＋ 1。
1.4 线性表、栈和队列一、线性表第一章 计算机软件技术基础
3．线性表的顺序存储结构有顺序存储和链式存储两种顺序存储方法即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。
用顺序存储方法存储的线性表简称为顺序表。
在顺序表中，每个结点 ai的存储地址是该结点在表中的位置 i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。
1.4 线性表、栈和队列一、线性表第一章 计算机软件技术基础
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中有多个结点的值和 x 相同，则返回首次找到的结点位置；若
L中没有结点的值为 x，则返回一个特殊值表示查找失败。
1.4 线性表、栈和队列一、线性表第一章 计算机软件技术基础
（ 5） InsertList(L,x,i)：在线性表 L的第 i个位置上插入一个值为 x 的新结点，使得原编号为 i,i＋
1,…,n的结点变为编号为 i＋ 1,i＋ 2,…,n
＋ 1的结点。这里 1 ≤ i ≤ n＋ 1，而 n是原表 L的长度。插入后，表 L的长度加 1。
（ 6） DeleteList(L,i)：删除线性表 L的第 i个结点，
使得原编号为 i＋ 1,i＋ 2,…,n的结点变成编号为 i,i＋ 1,…,n－ 1的结点。这里 1 ≤ i ≤ n，
而 n是原表 L的长度。删除后表 L的长度减 1。
1.4 线性表、栈和队列一、线性表第一章 计算机软件技术基础
1．栈的定义栈（ Stack）是限制仅在表的一端进行插入和删除运算的线性表。栈的示意图如图 1-4所示：
（ 1）通常称插入、删除的这一端为栈顶，另一端称为栈底。
（ 2）当表中没有元素时称为空栈。
（ 3）栈为后进先出（ Last In First Out）的线性表，
简称为 LIFO表。
栈的修改是按后进先出的原则进行。
1.4 线性表、栈和队列二、栈第一章 计算机软件技术基础
2．栈的基本运算
（ 1） InitStack(S)：构造一个空栈 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的栈顶元素删去，
并返回该元素。
（ 6） StackTop(S)：取栈顶元素。若栈 S非空，则返回栈顶元素，但不改变栈的状态。
1.4 线性表、栈和队列二、栈第一章 计算机软件技术基础
1．定义只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
（ 1）允许删除的一端称为队头（ Front）。
（ 2）允许插入的一端称为队尾（ Rear）。
（ 3）当队列中没有元素时称为空队列。
（ 4）队列亦称作先进先出（ First In First Out）
的线性表，简称为 FIFO表。
队列的修改是依先进先出的原则进行的。
1.4 线性表、栈和队列三、队列第一章 计算机软件技术基础
2．队列的基本逻辑运算
（ 1） InitQueue(Q)：置空队。构造一个空队列 Q。
（ 2） QueueEmpty(Q)：判队空。若队列 Q为空，则返回真值，否则返回假值。
（ 3） QueueFull(Q)：判队满。若队列 Q为满，则返回真值，
否则返回假值。
注意,此操作只适用于队列的顺序存储结构。
（ 4） EnQueue(Q,x)：若队列 Q非满，则将元素 x插入 Q的队尾。此操作简称入队。
（ 5） DeQueue(Q)：若队列 Q非空，则删去 Q的队头元素，
并返回该元素。此操作简称出队。
（ 6） QueueFront(Q)：若队列 Q非空，则返回队头元素，
但不改变队列 Q的状态。
1.4 线性表、栈和队列三、队列第一章 计算机软件技术基础以链接方式存储的线性表简称为链表。
1．链表的具体存储表示为：
① 用一组任意的存储单元来存放线性表的结点
（这组存储单元既可以是连续的，也可以是不连续的）。
② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针或链 )。
1.5 线性链表一、线性链表的概念第一章 计算机软件技术基础
2．链表的结点结构
1.5 线性链表一、线性链表的概念
data next
data域 —存放结点值的数据域 。
next域 —存放结点的直接后继的地址的指针域 。
其中,① 链表通过每个结点的链域将线性表的 n
个结点按其逻辑顺序链接在一起的 。
② 每个结点只有一个链域的链表称为单链表 。
③ 每个结点有两个链域的链表,既指出该数据元素的后继,指出前驱,则这种链表称为双链表 。
第一章 计算机软件技术基础
④ 在单链表中增加一个表头结点，指针域指向线形表的第一个元素的结点，令最后一个结点的指针域指向表头结点，即构成了循环链表,在循环链表中，所有结点的指针构成了一个环状链。
1.5 线性链表一、线性链表的概念
a1 ai ai+1 an ∧…
第一章 计算机软件技术基础
线性链表的基本运算主要有以下几个：
（ 1）在线性链表中包含指定元素的结点之前插入一个新元素
（ 2）在线性链表中删除包含指定元素的结点
（ 3）将两个线性链表按要求合并成一个线性链表
（ 4）将一个线性链表按要求进行分解。
（ 5）逆转线性链表
（ 6）复制线性链表
（ 7）线性链表的排序
（ 8）线性链表的查找
1.5 线性链表二,线性链表的基本运算第一章 计算机软件技术基础
1.插入运算思想方法,插入运算是将值为 x的新结点插入到表的第 i个结点的位置上，即插入到 ai与 ai＋ 1
之间。
具体步骤：
（ 1）找到 ai存储位置 p；
（ 2）生成一个数据域为 x的新结点 ax；
（ 3）令结点 *p的指针域指向新结点；
（ 4）新结点的指针域指向结点 ai＋ 1。
1.5 线性链表二,线性链表的基本运算第一章 计算机软件技术基础
2.删除运算思想方法,删除运算是将表的第 i个结点删去。
具体步骤：
（ 1）找到 ai-1的存储位置 p（因为在单链表中结点
ai的存储地址是在其直接前趋结点 ai-1的指针域
next中）；
（ 2）令 p－＞ next指向 ai的直接后继结点（即把 ai
从链上摘下）；
（ 3）释放结点 ai的空间，将其归还给“存储池”。
1.5 线性链表二,线性链表的基本运算第一章 计算机软件技术基础
树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。
如家谱、行政组织机构都可用树形象地表示。
1.6 树一、什么是树经济管理学院经济信息系 计划统计系 外贸系信息处理教研室经济数学教研室计划学教研室统计学教研室外语教研室国际贸易教研室第一章 计算机软件技术基础
2．树结构的基本术语
在树结构中，每一个结点只有一个前件，称为父结点。
没有前件的结点只有一个，称为树的根结点。
每一个结点可以有多个后件，都称为该结点的子结点。
没有后件的结点称为叶子结点。
一个结点所拥有的后件个数称为该结点的度。
一棵树的度是指该树中结点的最大度数。
1.6 树一、什么是树第一章 计算机软件技术基础
结点的层数 (Level)：从根起算，根的层数为 1，
其余结点的层数等于其双亲结点的层数加 1。
树中结点的最大层数称为树的高度 (Height)或深度 (Depth)。
A
CB
HD F
I J
GE
1.6 树一、什么是树图中,树的根结点 A度为 2，
结点 B的度为 3,结点 I的度为
0,树的度为 3,结点 A在第一层,结点 B,C在第二层,结点 D,E,F,G,H在第三层,结点 I,J
在第四层 。
第一章 计算机软件技术基础
森林 (Forest)是 m(m≥0)棵互不相交的树的集合。
树和森林的概念相近。删去一棵树的根，
就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。
1.6 树一、什么是树第一章 计算机软件技术基础
1.二叉树的特点
（ 1）非空二叉树只有一个根结点。
（ 2）每一个结点最多有两棵子树，称为该结点的左子树和右子树。
如算术运算式 3 * 5 ＋ 6 / 2 – 8就可用二叉树表示。
1.6 树二,二叉树的基本性质
+
－*
83 5
6 2
/
第一章 计算机软件技术基础
2.二叉树具有以下重要性质：
性质 1 二叉树第 i层上的结点数目最多为 2i－ 1(i≥1)。
性质 2 深度为 k的二叉树至多有 2k－ 1个结点 (k≥1)。
性质 3 在任意一棵二叉树中，若终端结点的个数为 n0，度为 2的结点数为 n2，则 no=n2＋ 1。
性质 4 具有 n个结点的完全二叉树的深度为：
（或 ）。
1l?gn
1.6 树二,二叉树的基本性质
1lg?n
)1lg( n?
第一章 计算机软件技术基础
3.满二叉树和完全二叉树是二叉树
（ 1）满二叉树 (FullBinaryTree)
一棵深度为 k且有 2k－ 1个结点的二叉树称为满二叉树。
满二叉树的特点：
① 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
② 满二叉树中不存在度数为 1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
1.6 树二,二叉树的基本性质第一章 计算机软件技术基础
（ 2）完全二叉树 (Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于 2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
完全二叉树的特点：
① 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
② 在满二叉树的最下一层，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
③ 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
1.6 树二,二叉树的基本性质第一章 计算机软件技术基础
链接的方法是它最自然的存储表示方法。
每个结点有一个数据域，两个指针域。数据域存储数据元素的值，两个指针分别指向该数据元素的左子女和右子女。当某个子女不存在时，
相应的指针为空指针。结点形式如下：
1.6 树三,二叉树的存储结构
llink info rlink
一棵二叉树的所有这样形式的结点,再加上一个指向根的指针,就构成此二叉树的存储表示 。 这种存储表示法称为 llink-rlink表示法或称为二叉链表 。
第一章 计算机软件技术基础
遍历一棵二叉树实际上是对二叉树的结点进行一次扫描，是将二叉树的结点放入一个线性序列的过程，或者说把二叉树进行线性化。遍历运算是二叉树的一种最基本的运算。
遍历二叉树有三种主要的方法：前序法、中序法和后序法。
① 前序法，其操作如下：
访问根；
按前序遍历左子树；
按前序遍历右子树。
1.6 树四,二叉树的运算第一章 计算机软件技术基础
② 中序法，其操作如下：
按中序遍历左子树；
访问根；
按中序遍历右子树。
③ 后序法，其操作如下：
按后序遍历左子树；
按后序遍历右子树；
访问根。
1.6 树四,二叉树的运算第一章 计算机软件技术基础
+
－*
83 5
6 2
/
1.6 树四,二叉树的运算对于图中的二叉树，它的三种方法遍历结果是：
前序序列：
＋ * 3 5 － ／ 6 2 8
中序序列：
3 * 5 ＋ 6 ／ 2 － 8
后序序列：
3 5 * 6 2 ／ 8 － ＋
第一章 计算机软件技术基础
顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下：
从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功 )；
若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素 (即查找失败 )。
在下列两种情况下也只能采用顺序查找：
(1)如果线性表为无序表 (即表中元素的排列是无序的 )，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
(2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
1.7 查找技术一、顺序查找第一章 计算机软件技术基础
1.7 查找技术二、二分法查找
二分法查找只适用于顺序存储的有序表。
设有序线性表的长度为 n，被查元素为 x，则对二分查找的方法如下：
将 x与线性表的中间项进行比较：
若中间项的值等于 x，则说明查到，查找结束；
若 x小于中间项的值，则在线性表的前半部分
(即中间项以前的部分 )以相同的方法进行查找；
若 x大于中间项的值，则在线性表的后半部分
(即中间项以后的部分 )以相同的方法进行查找。
第一章 计算机软件技术基础
所谓排序是指将一个无序序列整理成按值递减（或递增）
顺序排列的有序序列。
1．冒泡排序冒泡排序法的基本过程是：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。
若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序：显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后，这也是最大元素应有的位置。
依次剩下的线性表元素重复上述过程，直到线性表中每一个元素都找到它应有的位置，此时的线性表变为有序。
1.7 查找技术三、排序技术第一章 计算机软件技术基础
2．快速排序
快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。
快速排序法的基本思想如下：
从线性表中选取一个元素，设为 T，将线性表后面小于 T的元素移到前面，而前面大于 T的元素移到后面。
结果就将线性表分成了两部分 (称为两个子表 ),T插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以 T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于
T，而后面子表中的所有元素均不小于 T。
如果对分割后的各子表再按上述原则进行分割，并且，
这种分割过程可以一直做下去，直到所有子表为空为止，
则此时的线性表就变成了有序表。
1.7 查找技术三、排序技术第一章 计算机软件技术基础
3.简单插入排序
所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。
我们从线性表的第 2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面的有序子表中。在简单插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡法相同。在最坏情况下，排序需要经过 n（ n－ 1） /2次的比较。
1.7 查找技术三、排序技术第一章 计算机软件技术基础
4．希尔排序
希尔排序属于插入类排序，但它对简单插入排序做了较大的改进。
希尔排序的基本思想如下：
将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法是将相隔某个增量 h的元素构成一个子序列。在排序过程中，
逐次减小这个增量，最后当 h减到 1时，进行一次插入排序，排序就完成。增量序列一般取
ht=n/2K(K=1,2,…,[log2n),其中 n为待排序序列的长度。
1.7 查找技术三、排序技术第一章 计算机软件技术基础
5．简单选择排序
选择排序方法中最简单的一种就是直接选择排序算法。
其操作过程是：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。先选出最小的元素并将其与第一个元素交换。然后在剩下的 n－ 1个元素中再选出最小的元素与第二个元素交换 …… 最后在剩下的两个元素中。选出一个小的元素与第 n－ 1个元素交换。
1.7 查找技术三、排序技术第一章 计算机软件技术基础
6．堆排序
堆排序属于选择类的排序方法。
根据堆的定义，可以得到堆排序的方法如下：
（ 1）首先将一个无序序列建成堆。
（ 2）然后将堆顶元素与堆中最后一个元素交换。
不考虑已经换到最后的那个元素，只考虑前 n
－ 1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做第（ 2）步，直到剩下的子序列为空为止。
1.7 查找技术三、排序技术第一章 计算机软件技术基础
1．结构化程序设计的原则
（ 1）自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。
（ 2）逐步求精：对复杂问题，应设计一些子目标作过渡，
逐步细化。
（ 3）模块化：一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，
再进一步分解为具体的小目标，把每个小目标称为一个模块。
（ 4）限制使用 goto语句：限制使用 goto语句后，程序易理解、易排错、易维护，程序容易进行正确性证明。
1.8 程序设计文法一、结构化程序设计第一章 计算机软件技术基础
2.结构化程序的基本结构与特点
（ 1）顺序结构：顺序结构是顺序执行结构 。
（ 2）选择结构：可以根据设定的条件，判断应该选择哪一条分支来执行相应的语句序列。
（ 3）循环结构：它根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段，利用重复结构可简化大量的程序行。
3、按结构化程序设计方法设计出的程序具有的优点：
其一，程序易于理解、使用和维护。
其二，提高了编程工作的效率，降低了软件开发成本。
1.8 程序设计文法一、结构化程序设计第一章 计算机软件技术基础
3.结构化程序设计原则和方法的应用
（ 1）使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；
（ 2）选用的控制结构只准许有一个入口和一个出口；
（ 3）程序语句组成容易识别的块，每块只有一个入口和一个出口；
（ 4）复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；
（ 5）语言中所没有的控制结构，应该采用前后一致的方法来模拟；
（ 6）严格控制 goto语句的使用。
1.8 程序设计文法一、结构化程序设计第一章 计算机软件技术基础
1．对象（ object）
对象是面向对象方法中最基本的概念。对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。
特点：
（ 1）标识唯一性。指对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分。
（ 2）分类性。指可以将具有相同属性和操作的对象抽象成类。
（ 3）多态性。指同一个操作可以是不同对象的行为。
1.8 程序设计文法二、面向对象的程序设计第一章 计算机软件技术基础
（ 4）封装性。从外面看只能看到对象的外部特性，
即只需知道数据的取值范围和可以对该数据施加的操作，根本无需知道数据的具体结构以及实现操作的算法。
（ 5）模块独立性好。
1.8 程序设计文法二、面向对象的程序设计第一章 计算机软件技术基础
2．类（ Class）和实例（ Instance）
类是具有共同属性、共同方法的对象的集合。
类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。
,实例,是指一个具体的对象。
如,Integer是一个整数类，它描述了所有整数的性质。因此任何整数都是整数类的对象，
而一个具体的整数,123”是类 Integer的一个实例。
1.8 程序设计文法二、面向对象的程序设计第一章 计算机软件技术基础
3,消息 （ Message）
对象间的这种相互合作需要一个机制协助进行，
这样的机制称为“消息”。
4．继承（ Inheritance）
继承是面向对象的方法的一个主要特征。继承是使用已有的类定义作为基础建立新类的定义技术。已有的类可当作基类来引用，则新类相应地可当作派生类来引用。
1.8 程序设计文法二、面向对象的程序设计第一章 计算机软件技术基础
5．多态性（ Polymorphism）
对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，
该现象称为多态性。
在面向对象的软件技术中，多态性是指子类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象。
1.8 程序设计文法二、面向对象的程序设计
