C语言软件基础部分知识点

1、数据结构的基础知识内容1数据结构的基本概念数据结构是讨论计算机系统中数据的组织形式及其相互关系的学科研究数据结构就是要研究以下三方面的内容：1）数据元素之间的逻辑关系是什么?2）适宜选用什么样的存储结构？3）采用什么样的操作实现算法效率更高?2. 反映数据元素之间关系的数据逻辑结构可分为两大类.1）线性结构:线性结构的逻辑特征是:有且仅有一个开始数据元素和一个终点数据元素并且所有数据元素都最多只有 一个直接前趋和一个直接后继线性表就是一个典型的线性 结构.2）非线性结构:非线性结构的逻辑特征是：该结构中一个数据元素可能有多个直接前趋和直接后继.非线性结构中取 般结构是图结构，在图结构中，任何数

2、据元素的直接前趋和 直接后继的人数都不作限制，在非线性结构中有一类较特殊 的结构，我们称为树结构，它的逻辑特征是:所有数据元素 （除根元素）都存在一条从根元素到该元素的路径.3. 反映数据元素在计算机中的存储方法就是数据的存储结构，数据的存储结构图:有时它称为数据的物理结构,它是数 据的逻辑结构在存储器里的实现数据的存储方法可分为如 下四类:1) 顺序存储方法:该方法是把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里，元素间的逻辑关系由存储 单元的邻接关系体现.由此得到的存储表称为顺序存储结构. 顺序存储方法主要应用于线性的数据结构，如线性表，数组 等非线性的数据结构也可以通过某种线性化

3、的方法来实现 顺序存储.2) 链接存储方法:该方法不要求逻辑上相邻的元素其物理位置上亦相邻，元素间的逻辑关系是由附加的指针字段表示 的，由此得到的存储表称为链式存储结构，链式存储结构要 借助于程序结构的指针类型来描述元素的存储地址，即在此 存储方法中，每个数据元素所占存储单元分成两部分:一部 分为元素本身数据项；而另一部分为指针项，指出其后继前 趋元素的存储地址，从而形成一个链.3) 索引存储方法:该方法通常是在存储元素信息的同时，还 建立附加的索引表，索引表中的每一项称为索引项,索引项 的一般形式是:关键字,地址。关键字是能唯一标识一个元素 的数据项若每个元素在索引表中都有一个索引项，则该索

4、 引位置称为稠密索引(dense. index)；若一级元素在索引表中只对应一个索引项，则该索引位置称稀疏索引(sdarse. index),稠密索引中索引项的地址指示元素所在存储位置，而稀疏索引中索引项的地址则指示一级元素的起始 存储位置.4) 散列存储方法:该方法的基本思想是根据元素的关键字直接计算出该元素的存储地址即在数据元素的字段中有一 个或几个字段的值，通过某一散列函数唯一地确定该元素的 存储地址有时又称散列存储方法为关键字地址转移 法.4. 把数据以一定的有效逻辑结构组织起来，并以适当的方法存储在计算机系统的存储器里,其最终目的是有效处理数据, 提高数据处理的运算速度.在数据结构中

5、，要讨论的常用数据处理与运算有下列几种:1)遍历：在数据结构的各个元素移动，或查看所有数据元素.2)插入:往数据结构中加新的元素.3) 更新:修改或替代数据结构中指定元素的一个或多个数 据项(字段值).4) 删除:把指定的数据元素从数据结构中去掉.5) 查找:在数据结构中查找满足一定条件的数据元素.6) 排序:在数据结构中数据元素个数不变的前提下，把元素按指定的顺序重新排列排序一般是建立在线性逻辑结构的 基础上.线性结构1.结构特点：线性结构是数据结构中最简单且最常用的一种数据结构线 性结构基本特点是数据元素有序并有限正如上一节所述: 线性结构的逻辑特征是在其结构中，有且仅有一个无直接前 趋而

6、仅有一个直接后继的数据元素为起始元素：有且仅有一 个无直接后继而仅有一个直接前趋的数据元素为终点元素： 其余均为内部元素，它们各有一个直接前趋和直接后继因 此,线性结构的数据元素可排成一个线性的序列:al, a2,an其中，al为起始元素,an为终点元素,ai为索引号为i的数据 元素.2.常见的线性结构:线性结构有各种类型，如线性表，堆栈，队列，数组，串等.(一) 线性表：线性表是n(nno)个相同类型的元素al, a2,an所构成的有限线性序列，通常表示为(al, a2,an),其中n为线性表的长度.ai (l<i<n)是线性表中第i个位置的数据元素ai是抽象表示符号，在不同的

7、情况下含义不同.例如：一个整数序 列:(1, 12, 123, 1234, 321, 21, 22)是一个线性表，表中元素ai是一个整数,表长为7.线性表有两种存储方式,对应地把线性表分成了两类:顺序 存储结构的顺序表和链式存储结构的链表.(1) .顺序表:顺序表:在顺序表的存储结构中，数据元素按其逻辑次序集中存放在地址连续的存储单元里，由于逻辑上的相邻的元素 存放在内存的相邻单元中，所以顺序表的逻辑关系蕴含在存 储单元的邻接关系中通常顺序表是用一个一维数组和一个 指示当前表长的整数来表征.基于顺序表的各种操作(如建表、插入、删除、求表长等)都 是很简单的在程序设计课程中一般都应有所介绍，这里

8、仅强 调下操作特点，以顺序表插入数据的算法为例:假设顺序表 中已有num(lsmms (maxnum-1)个数据元素，在第i个位置 ±(0<i<num)插入一个新的数据元素，构成一个num+1长的 顺序表其实现方法是:将原来表中第i个元素到第n个元素 后移一个位置，将要插入的元素x插入在第i个位置上，再将 表长num加1.(2) 线性链表线性链表是采用链式存储方式进行存储的线性表即有一级 任意的存储单元来存放线性表有限个数据元素，这组存储单 元既可是连续的，也可以是不连续，从而可以大大提高存储 器的使用效率线性链表有单向链表,双向链表和循环链表 等多种形式.(a).单向链

9、表:单向链表是链式存储结构中最简单和最基本 的结构因为在链表中元素的逻辑次序与物理存储次序不一 定相同，为了能正确表示数据元素间的逻辑关系，在存储每个元素的同时，还必须存储其直接后续(或直接前趋)的存储位置，这一部分称为链因此，单向链表的每个数据元素都是 由二部分组成:存储元素的数据域(data)和存储直接后续元 素存储地址的指针域(next)其结构如下：datanext一个线性表al, a2, , an,对应的单向链表可以用逻辑示 意图1表示其中,h为链表的头指针,用以确定线性表中第 一个元素对应的存储位置单向链表可以用头指针的名字来 命名.链表的终点元素无直接后续，故其指针域为空nil,在

10、 图中用八表示下图为单向链表示意图：aiaa2an图1设有线性表al, a2,-an用带头结点的单链表存储,现要求0在数据元素ai的结点之前插入一个数据元素为x的结点首先应找到数据元素ai,的结点，以便打开ai-1与,x, x与ai两数据元素之间的链，构成新的链表，算法示意图如图2所图2结点插入显然，与基于唯一数组的顺序表的插入操作比较，线性链表 不需要大量的数据元素的移动，使得操作效率明显提高.b）双向链表:在单向链表中，每个结点的指针域只放一个指针，该指针指向该结点元素的直接后继元素的结点，每查找 一个数据元素都必须从头结点开始，从前向后单方向搜寻. 若在每个元素的结点中，增加指向直接前趋

11、的指针，就可以 实现线性链表从后向前的搜寻，即可双向配搭，这种指针域 包括指向该结点的直接前趋附于和直接后继的两个指针的 存储结构,称为双向链表，简称双链表，双链表的结点结构如图3所不.priordatanextv指向前结点的指针域数据区指向示继结点的指针域图3一个带头结点的双链表，其逻辑示意图如图4所示.显然，在双链表中，并不需要用头指针h来命名这个链表，因为，知道任一结点的指针，就可以访问整个链表的所有结点，包括结 点.a1（3）循环链表:循环链表是一种首尾相接的链表在单链表中 最后一个结点的指针域指向空（nil）,如果它指向头结点（带 头结点的链表）或第一个元素结点（不带头结点的链表），

12、使 整个链表形成一个环，这就构成了单向循环链表.同样，在双 链表中，将双链表最后一个结点与头结点（带头结点的双链 表）或第一个元素结点（不带头结点的双链表）链接起来，就可构成双向循环链表.ala2anala2（二）栈:栈是限制仅在表的一端进行插入和删除运算的线性 表通常称插入，删除的这一端为栈顶，另一端称为栈底当 表中没有元素是称为空栈.由于栈中元素的插入和删除只能 在栈顶进行，所以总是后进栈的元素先出来.即后进先出(lifo) 栈根据存储方式分为采用顺序存储结构的顺序栈和 采用链式结构的链栈栈的结构示意图6所示a2ai(a)顺序栈(b)谜栈图6:栈结构示意图栈的基本操作包括:判栈空，进栈，出

13、栈等.(三) 队列:队列是另一种操作受限的线性表,它只允许在线 性表的一端进行数据元素插入操作而在另一端才能进行数 据元素删除操作其中允许插入的一端称为队尾，允许删除 的另一端称为队头根据队列的特点，队列需要两个队列指 针来说明;一个是队头指针front,它总是指向队头元素的前一个位置;另一个是队尾指针rear,它总是指向队尾元素所 在的存储位置队列的结构示意图如图7所示.出队由于队列是元素的插入和删除分别在队尾和队头进行所以 总是先入队列的元素先出队列即队列具有先进先出的特性, 故队列又称为先进先出表(fifo) 同栈的操作类似，队列的基本操作包括:判队列空，进队列, 出队列等等.(四) 数

14、组:数组应是读者十分熟悉的类型，几乎所有的高级 程序设计语言都支持数组这种数据类型在前面讨论的各种 线性表结构的顺序存储结构时都是借用一维数组来描述的.数组本身也是一种数据结构，一维数组是一种顺序表结构, 多维数组是一种特殊的线性结构，是线性表的推广基于二 维数组应用最为广泛，像数学中的矩阵，生活中的常见报表 都是二维数组因此，二维数组是学习的重点.对于二维数组有两种最基本的操作:(1) 给定一组下标，找到与之相应的数据元素.(2) 给定一组下标，存取或修改与其相应的数据元素中某个数据项的值.这两种运算，可以归结为给定一组目标，确定与之相应的数 据元素的存储地址.而这个问题是与数组的存储结构有

15、关 的.最简单的存储结构是顺序结构,在计算机内是用一组连续的 内存单元来存储数组的它又分为两种：一种是行优先顺序 存储:数组元素按行向量排列，即i+1行向量紧接在第i个行 向量之后;另一种数组顺序存储的方法是按列优先顺序存储: 数组元素按列向量排列，即j+1个列向量紧接在第j个列向量之后 设每个数元素占s个存储单元,则在行优先存储中二维数组a (m, n)的每个元素的存储地址可用下列计算公式算出:loc(aij)二loc(all) + (i-1)*n+ (j-1) *s.设每个数元素占s个存储单元,则在列优先存储中二维数组a (m, n)的每个元素的存储地址可用下列计算公式算出:loc(aij

16、)二loc(all) + (i-1)*m+ (j-1) *s.另一种二维数组的存储结构是压缩存储结构,用于特殊矩阵 和稀疏矩阵的存储.特殊矩阵是指值相同的元素或者零元素的分布有一定规律 的矩阵，如对称矩阵，三角矩阵，对角矩阵等，利用其规律可 以实现存储压缩.稀疏矩阵是指在一个矩阵中绝大多数元素为零，非零元素很 少且无一定规律在实际应用中，经常会遇到处理大量的稀 疏矩阵情况按照压缩存储的概念，稀疏矩阵只需存储矩阵 中的非零元素这可以通过使用三元组存储法实现.这里三 元组指非零元素所处的行值和列值，以及非零元素本身的（五）串：串是字符串的简称，它是由零到多个字符组成的连 续有限序列，一般记为:al

17、a2a3-.an,，其中,s串名，引 号中为串值（单引号本身不是串值）ai是串元素，它由字母 或其他符号组成.n（no）是串的长度.对比串的定义和线性表的定义可知，串是一种其数据元素固 定为字符的线性表因此，仅就数据结构而言，串归属于线性 表这种数据结构但是，串的基本操作和线性表上的基本操 作相比却有很大的不同线性表上的操作主要针对线性表中 的某个数据元素进行，而串上的操作主要是针对串的整体或 串的某一部分子串进行串的基本操作包括:判串等，求串长, 连接串，替换串.第三节非线性结构对于非线结构，重点是让学生建立基本概念.非线性结构的逻辑特征是一个结点元素可能有多个直接前 趋或多个直接后继最主要

18、的非线性结构是树结构，二叉树 和图结构.(一)树结构的基本概念树结构是结点之间有分支,层次关系结构，类似于自然界中 的树,也有根，树叶及联系它们的支干,不过是一种倒生树. 树一般用递归方式定义.树是一个或多个结点元素组成的有限集合t,且满足如下条 件：(1) 有一个特定的结点元素，称为根结点(root).(2) 其余结点元素分成m个(mo)互不相交的有限集tl, t2,.tm,其中每个集又都是一棵树，这些树称为root 的子树x.在树中，一个结点元素常简称结点.下面介绍一些有关树结 构的重要术语与概念.(1) 叶子:没有后继的结点称为叶子(或终端结点).(2) 分支结点:非叶子结点称为分支结点

19、(或非终端结点)(3) 结点的度:一个结点的子树数目就称为该结点的度.(4) 树的度:树中各结点的度的最大值称为该树的度.(5) 子结点:某结点子树的根称为该结点的子结点.(6) 父结点:相对于某结点子树的根,称该结点为子树根的 父结点.(7) 兄弟:具有同一父结点的子结点称兄弟.(8) 结点的层次:根结点的层次为1,其他任何的层数等于它的父结点的层数和加1.(9) 树的深度：一棵树中，结点的最大层次值就是树的深度.(10) 有序树和无序树:如果一棵树中结点的各子树从左到 右是有序的，即若交换了某结点各子树的相对位置，则构 成了不同的树，称这棵树为有序树反之，则为无序树.(11) 森林:森林是

20、n棵树的集合任何一棵树，删去根结点,树就变成了森林对树中的每个结点来说,其子树的集合就是一个森林.(-)二叉结构二叉树结构同一般树结构一样,也是非线性结构中重要的一 类，但又不同于一般的树结构二叉树的定义如下:二叉树是 n个结点的有限集合;这个集合可以是空(即n=0),此时称为 空二叉树;或者由一个根点和两棵互不相交的被称为根的左 子树和右子树组成左子树和右子树分别又是一棵二叉树. 这也是一种递归定义二叉树可以是空集，同样，根可以有空 的左子树或右子树,或者左，右子树皆为空.由此，二叉树可 以有五种基本形态,必须注意一般树与二叉树概念上的不同. 树至少就应有一个结点,而二叉树可以是空;其次，二

21、叉树的 结点的子树要区分为左子树和右子树,而树中则无此区分.1. 了解几个特殊二叉树的概念：(1) 满二叉树:在一棵二叉树中，如果所有分支结点都存在 左子树和右子树，并且所有叶结点都在同一层上,这样的 一棵二叉树的图示说明，图中结点内的字符代表该结点的 顺序编号.（2）完全二叉树:若一棵二叉树至多只有最下面的两层上 结点的度数可以小于2,并且在最左边的若干位置上，则此 二叉树称为完全二叉树.一个n个结点的二叉树,其所有 结点的编号和一个满二叉树的1至n个结点编号完全一致, 则它肯定是完全二叉树.（3）二叉排序树:二叉排序树可以通过递归方式来定义，它 或者是空叉或者是具有如下性质的二叉:左子树上

22、所有结点的关键字均小于结点的关键字左子树和右子树本身又各是一棵二叉排序树.2. 二叉树的遍历:遍历是树结构的基本操作树遍历的含义是指用一定的规律 走遍树的每一个结点，使每个结点被访问一次而且只被访问 一次访问该结点时,可对该结点进行操作任一棵二叉树都 由三部分组成：即根结点（记作d）,左子树（记作l）,右子树 （记作r）.这样，遍历一棵二叉树的次序有六 种:dlr, ldr, drl, rdl, lrd, rld.若限定对左右子树的访问是 先左后右，则只有三种dlr（称为先序遍历）,ldr（称为中序遍 历）和lrd （称为后序遍历）.（三）图 图是另一种重要的，比树更复杂的非线性数据结构在树中

23、, 每个结点只与上层的父结点有联系，并可以与其下层的多个 结点有联系，而同一层的结点之间没有任何横向联系但在 图中，结点之间的联系是任意的，每个结点都可以与其他的 结点相联系.定义一个图g由两个集合v和e来组成，记为 g二(v, e),其中v是顶点的有穷非空集合,e是v中顶点偶对(称为边)的有空集通常也将图g的顶点集各边集分别记为v(g)和e (g)e(g)可以是空集，若e(g)为空信，则图g只有顶点而没有边.若图g中的每条边都是有方向的，则称g为有向图在有向图 中，一条有向边是由两个顶点组成的有序对,通常用尖括号 表示例如vi, vj表示一条有向边,vi是边的始点，vj是 边的终点若图g的每

24、条边都必须是没有方向的，则称g为无 向图无向图中的边均是顶点的无序对，用圆括号表示(vi,vj)下面介绍一些有关图结构的重要术语和概念.(1) 邻接点:对于无向图，如果边(v, u) eg(e),则v和u是 互为邻结点,v也是u的邻接点.对于有向图，如果弧匕u wg(e),则u是v的邻接点. 顶点度:常用d(v)表示，在无向图中，顶点的度就是以 该顶点为一个端点的边的条数.在有向图中，以某顶点为 弧头的弧的数目，称为此顶点的入度，常用id(v)表示；以 某顶点为弧尾的弧的数目，称为此顶点的出度，常用od(v) 表示有向图顶点的度是此顶点的入度与出度之和，即 d (v)二 id (v) +0d

25、(v)(3) 路径:在图g中,从顶点v至顶点u的一条路径是顶点 的序列，路径上边或弧的数目称为该路径的长度.(4) 在无向图中,若每一对顶点之间都有路径，则称此图为 连通图在有向图中，若每一对顶点u和v之间都存在从v到u及从u到v的路径，则称此图为强连通图.(5) 网络:如果图g(v, e)中每条边都赋有反映这条边的某种特性的数据，则称此图是一个网络，其中与边相关的数据称为该边的权.第四节查找与排序查找算法 查找的功能是根据给定的关键字值，在一组数据元素中确定 一个其关键字值等于给定值的数据元素若存在这样数据元 素，则称查找是有是成功的，否则称查找失败一组待查数据 元素的集合又称为查找表.查找

26、运算依赖于查找表中各数据元素在计算机存储系统的 组织与存储结构按照数据元素的组织与存储方式商定了采 用什么样的查找方法;反过来，为了提高查找方法的效率，又 要求数据元素采用某些特殊的存储方式.根据大纲要求，这 里就简单介绍一下基于线性表的几种常用的查找方法.(1)顺序查找顺序查找是最普通也是最简单的查找技术其基本思路为是: 从第一个数据元素开始,逐个把数据元素的关键字值和给定 值比较，若某个元素的关键字值和给定值相等,则查找成功;否则，若直至第n个数据元素都不相等，说明不存在满足条件 的数据元素，查找失败.顺序查找方法既适用于以顺序存储结构组织的查找表的查 找，也适用于以链式存储组织的查找表的

27、查找.(2) 二分查找如果按顺序存储结构组织的查找表中的所有数据元素按关键字有序,则可以采用一种高效率的查找方法二分查找其基本思路为：由于查找表中的数据元素按关键字有序 (假设递增有序)，则在查找时可不必逐个顺序比较，而采用跳跃的方式先与”中间位置”的数据元素的关键字 比较;若相等，则查找成功;否则在前半部分进行二分查找. 二分查找的过程是:先确定待查元素所在区域，然后逐步缩=1小区域，直到查找成功或失败为止设待查元素所在区域的 下界为low,上界为hig,中间位置mid二(low-hig)/21. 若此元素关键字值等于给定值,则查找成功；2. 若此元素关键值大于给定值，则在区域mid+1-h

28、ig内进行二分查找;3. 若此元素关键值小于给值，则在区域low-mid-l内进行二分查找.由于二分查找要求数据元素的组织方式应具有随机存取的 特性，所以二分查找只适用于顺序存储结构组织的有序查找 表.(3) 分块查找分块查找又称索引顺序查找，是介于顺序查找和二分查找之 间的一种查找查找方法它的基本思想:(1) 将所有数据元素分成若干块，块内元素按关键字是无 序的，但块间按关键字是有序的.即第一块中所有元素均 大于(或小于)第二块中所有元素，第二块中所有元素均大 于(或小于)第三块中所有元素;依次类推.(2) 建立一个块的最大(或最小)索引关键字表，该表是有 序的.(3) 查找是分两步进行:第

29、一步:先用待查的关键字对索引关键字对索引关键字表进 行二分查找或顺序查找,确定待查数据元素可能在哪一块. 第二步:在已确定的那一块中进行顺序查找.下面比较一下三种查找算法的效率:对于顺序查找,其平均 查找长度asl二(n+l)/2高有1000个数据元素组成的查找表, 采用二分查找，平均查找长度为9,显然其效率要高得多;分 块查找的效率介于顺序查找和二分查找之间.二.排序算法排序是将一组数据元素(有时又称为记录)按其排序码进行 递增或递减排列的运算操作，含有n个数据元素的序列为rl(p), r2(p),rn(p),其相应的排序码为：k1,k2kn按其排序码的某种次序排列得到一种排列，p使ki+1

30、 (p)或ki+(p) wki(p),由此得到的一个按其排序码线性有序的序列rl(p),r2(p),rn(p),就是排序。下面介 绍几个有关排序的基本概念；(1)排序码:排序的依据是排序字，也可以不是关键字.(2)排序算法的稳定性:如果待排序 的序列中，存在多个具有相同排序码数据元素，若经过排序 这些数据元素的相对次序保持不变，则称这种排序算法是稳 定的若经过排序，这些数据元素的相对次序发生了改变，则 称这种排序算法是不稳定的.(3)内部排序和外部排序：内部 排序指对数据元素序列的整个排序过程都是在计算机内存 中进行的排序;外部排序是指待排序的数据元素太多，不能 同时存放在内存中，所以排序操作

31、不仅要使用内存,而且还 要使用外部存储器存储数据的排序.下面介绍几种最常用的排序方法:1.简单插入排序:简单插入排序的基本思想是把n个数据元素的序列分为两部分，r1,ri为已排好序的有序部分，ri, ri+1,.rn为未排序部分这时，把未排序部分的第一个元素ri依次与r1,ri-1比较,并插入到有序部分的合适位置上便得r1,ri变成新的有序部分.2.简单选择排序:简单选择排序的基本思想是：第一趟排序是在无序, r1r2, r3,.rn中选出最小的元素与r1交换；第二趟排序是在无序r2, r3, r4,.rn中选出最小 的元素与r2交换;而第i趟排序时rl, r2,.ri已排好 序,在当前无序的

32、r1,rn中再选项出最小的元素，将它与ri元素交换，使r1,r2ri成为有序因为每趟排序都使有序区中增加了一个数据元素，且有序区中的数据元素的排序码均不大于无序区中元素的排序码，所以经过n-1趟排序后，整个数据元素序列就递增有序.3. 冒泡排序：冒泡排序是一最常用的方法，它的基本思想是:从r1开始两两比较ri和ri+1 (i二1, 2,.n-1)的排序码的大小，若ki>ki+l则交换ri和ri+1的位置。第一趟全部比较完毕后rn是序列最大的数据元素再从r1开始两两比较ri和ri+l(i=l,2,-.n-2)的排序码的大小，若ki>ki+l则交换ri和ri+1的位置，第二趟全部比较完

33、毕后rn-1是序列中次大的元素如此反复，进行n-l趟冒泡 排序后，所有待排序的n个元素序列按排序码有序.4. 快速排序:快速排序又叫作分区交换排序，是目前已知的 平均速度较快的一种排序方法，它是对冒泡排序方法的一 种改进，快速排序方法的基本思想是:从待排序的n个数据元素中任意选取一个元素ri (通常选取无序序列中的第一个元素）作标准，调整序中各个元素的位置，使排列在ri前面的元素排序码都小于rikey,排在ri后面的元素的排序码都大于ri-key.通常把这样的一个过程称作一次快速排序在第一次快速排序中，确定了元素ri最终在序列中的排列位置，同时也把剩余的数据元素分成了两个子序列，对两个子序列再

34、分别进行快速排序,又确定了两个元素在序列中应处的位置，并将剩余元素分成了四个子序列,如此重复下去，当各个子序列的长度为1时，全部元素排序完毕.可见，快速排序中的基本操作是子序列的划分操作设当前处理的元素序列的下界是low,上界是high,划分操作的步骤如下:（1）让两个指针1, j分别指向序列的第一个元素各最后一 个元素（即i=low; j=high）并将第一个元素的排序码保存 在k中. 用k与j指向的元素与排序码key比较，若kwrjkey,则再比较j的前一个元素的排序码（j二j-1）;否则将元素rj和ri互换位置此过程又称从左向右扫描过程. 用k与i指向的元素的排序码key比较,k$rik

35、ey,则再与i的后一个元素的排序码比较（i二i+1）；否则将元素ri和rj互换位置此过程又称从左向右扫描过程.（4）比较i和j, i<j则重复上面,（3）操作，直到i二j时,划分操作结束.5. 归并排序:归并排序又称作表排序，归并的含义是把两个(或两个以上)有序的序列合并为一个有序的序列，若是对 两个有序序列进行归并又称为2路归并.归并排序的基本思想是:将有n个元素的原始序列看作n个 有序子序列，每个序列的长度为1,然后从第一个子序列开始, 把相邻的子序列两两合并，得到n/2个长度为2或1的子序 列,这一过程称为一次归并排序，对第一次归并排序后的n/2 个子序列釆用上述方法继续顺序成对归

36、并，如此重复当最后 通牒得到长度为n的一个子序列时，该子序列便是原始序列 归并排序后的有序序列.由归并排序的基本思想可以看出：在归并排序过程中，最基 本的问题是如何把两个位置相邻的有序子序列合并为一个 有序子序列.设两个有序序列存储在一维数组r中，有序序列1是 (rl,r2,-rmj),有序子序列 2 是(rm+1,.rr). 归并后产生的有序序列存入到另一个一维组x中，该有序序 歹!j是(xl, x,xr)归并方法如下: (1)设置三个变量il, i2, j其中il, 12分别表示序列1和2中当前要比较的元素的位置号(下标)，初始值为1.反复比较r订和ri2排序码的值，若rilkey二ri2

37、key则 ril存储到 xj中，然 后，ilhl+1, j=j+l;若 rilkey>ri2key,则 ri2 存储到 xj中，然后，i2=i2+l, j=j+l.当序列1或2中的全部元素已归并到数组x中，即il=m或i2=r时，比较结束,然后将另一序列中剩余的所有元素 领奖放到数组x中，这样就完成了有序序列1和2的合并.第二部分软件工程第一节软件工程的基本概念一, 软件工程的形成和发展软件工程学是在克服60年代末所出现的”软件危机”的过 程中逐渐形成和发展的.软件危机(software crisis)的出现是由于软件的的规模越来越大，复杂度不断增加，软件 需求量增加，而软件开发过程是一

38、种高密度的脑力活动，软 件开发的模式及技术不能适应软件发展的需要.“软件危机”主要表现在两方面:(1) 软件产品质量低劣，甚至开发过程就夭折.(2) 软件生产效率低不能满足需求.二, 软件工程学研究的内容(1)软件开发技术(软件结构，开发方法，工具与软件工程环境,软件工程标准化)(2)软件工程管理(质量管理，软件工场经济学:成本估算，计 划安排)软件工程研究的目标是”以较少的投资获取高质量 的软件产品”三, 软件与软件生命周期(1)软件必须纠正那些认为软件就是程序，开发软件就是写程序的错 误观念.软件应是”程序以及开发使用维护程序所需的所有 文档” 具体有应用程序，系统程序，面向用户的文档，及

39、面 向开发者的文档四部分组成.(3) 软件生命周期(sdld)软件生命周期是指从软件开始开发到报废的全过程,也称软 件生存期.一般用经典的瀑布模式来描述.通常软件生命周期分为三个阶段，计划阶段，开发阶段，运行 维护阶段.在开发阶段由于开发方法不同，开发步骤和技术 也有所不同.第二节软件开发方法与工作模型一 结构化开发方法(strcrured developing method) 结构化开发方法是现有的软件开发方法中最成熟，应用最广 泛的方法，主要特点是迅速，自然和方便.(1)结构化开发方法的组成 70年代初，结构化程序设计方法sp法(strucrured program)70年代中，结构化设计

40、方法sd法(structured design)70年代末，结构化分析法sa(structured analysis)sa, sd, sp法相互衔接,形成了一整套开发方法若将sa, sd法 结合起来，又称为结构化分析与设计技术(sadt技术).(2) 结构化方法的工作模型瀑布模型(waterfall model)是结构化方法的工作模型.但从80年代开始，逐渐发现其不足，软件开发过程是一个充 满回朔的过程而瀑布模型将其分割为独立的几个阶段，不 能从本质上反映软件开发过程本身的规律此处，过分强调 复审，并不能完全避免较为频繁的变动尽管如此，瀑布模型 仍然是开发软件产品的一个行之有效的工程模型.二.

41、原型化方法(prototyping method)原型是软件开发过程中，软件的一个早期可运行的版本，它 反映了最终系统的部分重要特性原型化方法的基本思想是 花费少量代价建立一个可运行的系统,使用户及早获得学习 的机会原型化方法又称速成型法(rapidprototyping).强 调的是软件开发人员与用户的不断交互，通过原型的演进不 断适应用户任务改变的需求，将维护和修改阶段的工作尽早 进行，使用户验收提前,从而使软件产品更加适用.(1)快速建立需求规格原型(rep法)rep (rapid cyclic prototyping)法所建立的原型反映了系 统的某些特征，让用户学习，有利于获得更加精确

42、的需求说 明，待需求说明书一旦确定原型被废弃，后阶段的工作仍按 照瀑布模型开发.(2) 快速建立渐进原型(rsp法)(图1) rep (rapid cyclicprototyping)法采用循环渐进的方式，对系统模型作连续 精化，将系统需要具备的性质逐步添加上去，直至所有性 质全部满足，此时的原型也就是最终的产品.速成原型法适合于开发”探索型”，”实验型”与”进化 型”一类的软件系统速成原型的工作模型（图1）是一个循 环的模型.以下步骤循环执行:1 快速分析快速确定软件系统的基本要求，确定原型所要体现的特性（界面，总体结构，功能，性能）.2.构造原型在快速分析的基础上，根据基本规格说明，忽略细

43、节，只考虑主要特性，快速构造一个可运行的系统.3.运行和平价原型,用户试用原型并与开发者之间频繁交流,发现问题，目的是验证原型的正确性.4修正与改进对原型进行修改,增删.三.面向对象的开发方法 却 oosd（objec t-orie nted soft ware developme nt）法，这是80年代推出的一种全新的软件开发方法,非常实用而强有力.被兴誉为90年代软件的核心技术之一.其基本思想是:对问题领域进行自然的分割，以更按近人类 通常思想的方式建立问题领域的模型，以便对客观的信息实 体进行结构和行为的模拟，从而使设计的软件更直接地表现 问题的求解进程面向对象的开发方法以对象作为最基本

44、的 元素，分析和解决问题的核心.(1) 面向对象的开发方法的组成oods由面向对象的分析(ooa)面向对象的设计(ood)和面向 对象的程序设计(oop)组成.n效果满息否3e理原型提供文档图1快速分析，确定初步规格说明图2细化的快速霊豐n原型完成否要细部说明否y i严格说明细部1) ooa法提供了三种模型：信息模型(定义构成系统的类和对象，以及它们的属性与操 作)状态模型(描述任何时刻对象的联系及其联系的改变，即时序,常用状态图.事件追踪图描述)处理模型(系统内部数据的传送处理)2) ood法分为概要设计和详细设计概要设计(细化对象行为, 添加新对象,认定类，组类库,确定外部接口及主要数据结

45、构）3）oop （使用面向对象和程序设计语言，如c+进行程序设计） coad和yourdon给出一个面向对象的定义：面向对象二对象+类+继承+消息 如果一个软件系统是按照这样四个概念设计和实现的，则可 以认为这个软件系统是面向对象的.（2）面向对象的基本概念 1）对象（object）对客观存在的事物的描述，可以是事，物,或概念是将一组 数据和使用该数据的一组基本操作或过程封装在一起的实 体.2) 类(class)组具有相同数据结构和相同操作的对象的集合在一个类中, 每个对象都是类的实例.它们都可以使用类中提供的函数.3）继承（inheritance）继承是使用现存的定义作为基础,建立新定义的技

46、术.继承性分：单重继承:一个子类只有一个父类.现存类定乂二a z 、父类（基础）子类（派生类）国3多重继承:一个子类可有多个父类.4）消息（information）对象之间的联系可表示为对象间的消息传递,即对象间的通 迅机制.5）关于软件重用及”软件ic”的概念.第三节结构化开发方法概述 结构化分析（sa）方法sa法的基本思想结构化分析方法的基本思想是”分解”和”抽象”（2） sa法的步骤（3）sa法的描述方法 1）分层的数据流图通常用dfd（data flow diagram）图来描述画dfd图的方 法:”由外向内，自顶而下逐层分解”.画分层dfd图的基本原则：数据守恒与数据封闭原则加工分解

47、的原则（自然性,均匀性，分解度）子图与父图的”平衡”.合理使用文件注意:dfd图不是流程图2）数据词典（dd）3）加工说明，结构化语言（简单，易学，少二义性）；判定树（描 述一般组合条件清晰）；判定表（用于较复杂的组合条件）.二.结构化设计（sd）方法直接影响软件质量分为软件设计是软件开发的关键步两个阶段:总体设计和详细设计1 总体设计 解决系统的模块结构，分解模块,确定系统的模块层次关系.（1）具体任务1）划分模块；2）确定模块功能;3）确定模块的调用关系;4）确 定模块间的界面.（2）设计步骤1）分析系统的dfd图的类型，将其转换为初始的模块结构图, 中心变换型的dfd图（图5（a）采用”

48、变换分析” （transaction analysis）技术（图5）.事务处理型的dfd 图（b）采用”事务分析” （transaction analysis）技 术（图6）.2）按照”降低块间联系，提高块内联系”的设计总则修改. 完善系统的模块图写出模块的功能说明.具体应从以下方面改进: 尽可能建立功能模块.消除重复功能.模块的作用范围应是控制范围的子集.作用范围是指结构方面的特点，包括模块本身及其所有下属模块.控制范围是指判断所涉及到的模块，是从功能特点考虑的.模块的大小适当.模块的扇入扇出数不宜太多（除服务性模块外）.2. 详细设计对系统中每个模块的内部进程进行设计和描述常用的描述 方法

49、有：1）流程图2）ns图（结构化流程图）3）pad 图4）pdl语言三，软件编码b根据软件系统的应用范围，语言的内在特点待选择程序 设计语言。2,良好的程序设计风格（包括代码文件，数据说明方法， 语句构造方法，输入/输岀技术）。3, 重视用户界面设计。1, 软件测试的目的和重要性因为开发工作的前期不可避免地会引入错误，测试的目的是 为了检查发现和改正错误，这对于某些涉及人的生命安全的 项目显得尤其2, 软件测试方法1）静态分析方法指以人工的、非形式的方法对程序进行分析和测试。常用的 方法有1）桌前检查2）代码会审3）步行检查。2）动态测试分析方法通过选择适当的测试用例，执行程序。测试用例应由两

50、部分 组成：输入数据及预期的输出结果。将运行结果与预期结果 比较，查出错误。常用的方法有:1）白盒法分析程序的内部逻辑结构，注意选择适当的覆盖标准设计测 试用例，对主要路径进行尽可能多的测试.2）黑盒法不考虑程序的内部结构与特性,只根据程序功能设计测试用 例.常用的方法有：等价分类法:选择具有代表性的测试用例关键是划分”等价类”，应按照输入条件(如输入值的范围，值的个数，值的 集合,输入条件必须如何)分有效等价类和无效等价类.一个 测试用例可覆盖多个有效等价类，但一个测试用例只能覆盖 一个无效等价类.边值分析法:选择等价类的边缘值作为测试用例，选择测试 用既考虑输入亦考虑输出 因果图法:采用逻辑图的形式来表达功能说明书中输入条件 的各种组合与输出的关系根据这种关系可选择