数据结构复习

第2章 线性表 1. 线性表概述 1. 线性表操作特点：可以在任意位置插入和删除数据元素操作、由n(n≥0)个相同类型数据元素a0, a1,…, an-1组成的线性结构。 2. 线性表抽象数据类型: 数据集合:｛ a0, a1, … , an-1 ｝, ai的数据类型为DataType 操作集合(见 P18):(1) ListInitiate(L) 初始化线性表(2) ListLength(L) 求当前数据元素个数(3) ListInsert(L,i,x) 插入数据元素(4) ListDelete(L,i,x) 删除数据元素(5) ListGet(L,i,x) 取数据元素 2. 顺序表的顺序表示和实现 1. 顺序存储结构的线性表称作顺序表 2. 实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元中，这样线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置上。 3. 顺序表的存储结构如图所示 其中a0 ,a1, a2等表示顺序表中存储的数据元素，list表示顺序表存储数据元素的数组，MaxSize表示存储顺序表的数组的最大存储单元个数，size表示顺序表当前存储的数据元素个数。 4. 顺序表的结构体定义 typedef struct { DataType list[MaxSize]; int size; } SeqList; 5. 顺序表操作的实现（p19-22） 6. 主要优点是算法简单，空间单元利用率高 主要缺点是需要预先确定数据元素的最大个数，插入和删除时需要移动较多的数据元素。 3. 单链表顺序表示和实现 1. 单链表 链式存储结构存储线性表数据元素的方法是： 指针是指向物理存储单元地址的变量，我们把一个由数据元素及一个或若干个指针域组成的结构体称为一个结点，其中数据域用来存放数据元素指针域用来构造数据之间的关联关系。 单链表中，构成链表的结点只有一个指向后继结点的指针域，其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。 单链表的结构 单链表的结构体 typedef struct { DataType data; //data域用来存放数据元素 struct Node*Next;//next域用来存放指向下一个结点的指针 } SLNode; 1) 带头结点链表和不带头结点链表 头指针、头结点和首元结点的区别 头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针； 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。 首元结点是指链表中存储线性表第一个数据元素a０的结点 6）带头结点单链表和不带头结点单链表的比较 （p27-29） （1）带头结点单链表无论在第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，操作方法不一样 （2）删除操作和插入操作类似 （3）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表的算法时，头指针参数必须设计成输出型参数 （4）因此，带头结点单链表的算法设计简单 7）单链表的操作实现（p29-34） 8）单链表与顺序表相比： 主要优点是不需要预先确定数据元素的最大个数，插入和删除操作不需要移动数据元素； 主要缺点是查找数据元素时需要顺序进行，不能像顺序表那样随机查找任意一个数据元素。另外，每个结点中要有一个指针域，因此空间单元利用率不高。而且单链表操作的算法也较复杂。 2. 循环单链表 循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域指向整个链表的第一个结点，从而使链表形成一个环。它的优点是从链尾到链头比较方便。循环单链表也有带头结点和不带头结点两种结构。 3. 循环双向链表 双向链表是每个结点除后继指针域外还有一个前驱指针域，它有带头结点和不带头结点，循环和非循环结构，双向链表是解决查找前驱结点问题的有效途径。 结点结构如图示 与普通单链表结点的差别是多了prior域是指向前驱结点的指针域 双向循环链表的操作实现（p37） 4. 静态链表 在数组中增加一个(或两个)指针域用来存放下一个(或上一个)数据元素在数组中的下标，从而构成用数组构造的单链表。因为数组内存空间的申请方式是静态的，所以称为静态链表，增加的指针称做仿真指针。 第3章 堆栈和队列 堆栈和队列都是特殊的线性表，这三者的数据元素和数据间的逻辑关系完全相同，差别是：线性表的插入和删除不受限制，二堆栈只能在栈顶插入和删除，队列只能在队尾插入，在队头删除。 1. 堆栈 (1)堆栈基本概念 定义:限定只能在固定一端进行插入和删除操作的线性表。特点：后进先出。 允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。当前栈顶位置是动态的，标识栈顶当前位置的变量称为栈顶指示器（或栈顶指针）。作用：可以完成从输入数据序列到某些输出数据序列的转换 堆栈抽象数据类型 1)数据集合: {a0,a1,…,an-1}ai的数据类型为DataType。 操作集合： 1 StackInitiate(S) ：初始化堆栈S 2 StackNotEmpty(S)：堆栈S非空否 3 StackPush(S, x) ：入栈 4 StackPop(S, d)：出栈 5 StackTop(S, d)：取栈顶数据元素 2)堆栈的顺序表示和实现 顺序堆栈：顺序存储结构的堆栈。 顺序栈的存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素. 存储结构 其中a0 ,a1, a2等表示顺序堆栈数组中存储的数据元素序列，stack表示顺序堆栈存放数据元素的数组，MaxSize表示顺序堆栈数组stack的最大存储单元个数，top表示顺序堆栈数组stack当前栈顶位置。 顺序堆栈的结构定义 typedef struct { DataType stack[MaxStackSize]; int top; } SeqStack; 顺序堆栈的操作实现（p50-53） (2)堆栈的链式表示和实现 1）链式堆栈：链式存储结构的堆栈。 2）链式栈的存储结构：它是以头指针为栈顶，在头指针处插入或删除，带头结点的链式堆栈结构。 链栈中每个结点由两个域构成：data域和next域 3）结点结构体定义如下： typedef struct snode { DataType data; struct snode *next; } LSNode; 4）链式堆栈的操作实现（p53-54） 1) 链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。 2)一般不会出现栈满情况；除非没有空间导致malloc分配失败。 3)采用链栈存储方式的优点是，当栈中元素个数变化较大，准确数字难以确定时，链栈较顺序堆栈方便 2. 队列 1.队列的基本概念 定义:只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。一个队列的示意图如下 队列中允许进行插入操作的一端称为队尾（由队尾指针或指示器指示），允许进行删除操作的一端称为队头（由队头指针或指示器指示）。 队列抽象数据类型 数据集合:{a0,a1,…,an-1}，ai的数据类型为DataType。 操作集合： （1）初始化QueueInitiate(Q) （2）非空否QueueNotEmpty(Q) （3）入队列QueueAppend(Q, x) （4）出队列QueueDelete(Q, d) （5）取队头数据元素QueueGet(Q, d) 2.顺序队列 (1)顺序队列： 顺序存储结构的队列。 (2)顺序队列动态示意图 front为队头指示器，rear为队尾指示器 (3)顺序队列的“假溢出”问题: 顺序队列因多次入队列和出队列操作后出现的虽有存储空间但不能进行入队列操作的情况。 可采取四种方法： 　1)采用顺序循环队列；（教材中的方法） 2)按最大可能的进队操作次数设置顺序队列的最大 元素个数；（最差的方法） 3)修改出队算法，使每次出队列后都把队列中剩余 数据元素向队头方向移动一个位置； 　４)修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向对头移动，然后方完成入队操作 1. 顺序循环队列 1) 顺序循环队列的基本原理:把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxQueueSize-1后，再前进一个位置就自动到０。 2)顺序循环队列的结构体定义如下： typedef struct { DataType queue[MaxQueueSize]; int rear; int front; int count; } SeqCQueue; 5)顺序循环队列的实现（p67-69） 4)顺序循环队列的队空和队满判断问题 新问题：在顺序循环队列中，队空特征是front=rear；队满时也会是 front=rear；判决条件将出现二义性！ 解决方案有三： ①使用一个计数器记录队列中元素个数（即队列长度）； （教材中的方法）　 判队满：count>0 && rear==front 判队空：count==0 ②设标志位，出队时置０,入队时置１,则可识别当前front=rear 属于何种情况 　　判队满：tag==1 && rear==front 判队空：tag==0 && rear==front ③ 少用一个存储单元 　　判队满： front=＝(rear+1)%MaxQueueSize 判队空： rear==front 2链式队列 1)链式队列：链式存储结构的队列。 2)链式队列的存储结构： 链式队列的队头指针指front向队列的当前队头结点;队尾指rear针指在队列的当前队尾结点. 一个不带头结点的链式队列的结构： 3）结点的结构体可定义如下： typedef struct qnode { DataType data; struct qnode *next; } LQNode; 队头指针front和队尾指针rear的结构体类型： typedef struct { LQNode *front; LQNode *rear; } LQueue; 4）链式队列操作的实现（p70） 3. 队列应用（p72-76） 第4章 串 1. 串概述 1.串的基本概念和C语言的串函数 串的基本概念：串(又称字符串)是由n(n≥0)个字符组成的有限序列。（它是数据元素为单个字符的特殊线性表。） 串长　 串中字符的个数（n≥0）。 空串 串中字符的个数为0 时称为空串 ( 。 空白串　由一个或多个空格符组成的串。 空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空白字符‘ ’(空格键)的字符串. 子串　串S中任意个连续的字符序列叫S的子串; S叫主串。 子串位置　子串的第一个字符在主串中的序号。 字符位置　字符在串中的序号。 串相等　 串长度相等，且对应位置上字符相等。（即两个串中的字符序列一一对应相等。） 注：串与字符的区别 　“a” 串，长度为１的串。（它不仅要存储字符‘a’，还要存储该串的长度数据１） 　‘a’　字符a。(只存储字符‘a’) 2.串的抽象数据类型 数据集合：串的数据集合可以表示为字符序列 s0,s1, ……,sn-1，每个数据元素的数据类型为字符类型。 操作集合： (1)初始化串　Initiate(S)(2)赋值　 Assign(S,T)(3)求串长度　Length(S) (4)比较　 Compare(S,T) :有相等和不相等两种比较结果，还有大于、等于和小于三种比较结果(5)插入　 Insert(S,pos,T)(6)删除　 Delete(S,pos,len) (7)取子串　 SubString(S,pos,len) (8)查找子串　Search(S,start,T) (9)替换子串　Replace(S,start,T,V) 注：用C语言处理字符串时，要调用标准库函数 #include见p88 2. 串的存储结构 1.串的顺序存储结构：就是用一个字符类型的数组存放串的所有字符，此时，表示串的长度的方法有两种： 一种方法是设置一个串的长度参数，此种方法的优点是便于在算法中用长度参数控制循环过程 另一种方法是在串值的末尾添加结束标记，此种方法的优点是便于系统自动实现。 而由于不同的内存分配方式定义的数组决定了串的顺序存储结构也有两种 (1)静态数组结构：用静态内存分配方法定义的数组。由于此时数组元素的个数是在编译是确定的，在运行时是不可改变的，所以也称为定长数组结构。 其类成员变量包括： typedef struct { char str[MaxSize]; int length; } String; (2)动态数组结构：用动态内存分配方法定义的数组。此时数组元素的个数是在用户申请动态数组空间时才确定的,因此，动态数组结构体定义中要增加一个指出动态数组个数的域。 其类成员变量包括： typedef struct { char *str; int maxLength; int length; } DString; 其中，str指向动态数组的首地址， maxLength表示动态数组的最大个数， length表示串的当前长度，必须满足length ≤ maxLength 2.串的链式存储结构 它分为单字符结点和块链两种见p91 3.实际应用中串存储结构的选择 串基本上采用动态数组存储结构p91 3． 串的基本操作的实现算法见p93 · 动态数组实现的顺序串 第5章 数组 1. 数组的基本概念 1.数组的定义 数组是n(n＞1)个相同数据类型的数据元素a0,a1,a2,...,an-1构成的占用一块地址连续的（而线性表没有此

要求

对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗

）内存单元的有限序列。 数组中任意一个元素可以用该元素在数组中的位置来表示，数组元素的位置通常称作数组的下标（对下标操作就可以实现元素的操作）。线性表的元素是逻辑意义上不可再分的元素，而数组的元素可以还是元素。 线性结构（包括线性表、堆栈、队列、串）的顺序存储结构实际就是使用数组来存储。数组是其他数据结构实现顺序存储结构的基础，是软件设计中最基础的数据结构。 2..数组的实现机制 (１)、一维数组（n个元素）中任一元素ai的内存单元地址 Loc(ai)=LOC(a０)+i*k (0≤i 0的树，有:(1)仅有一个特殊的结点称为根结点，根结点没有前驱结点；(2)当n>1时，除根结点外其余的结点分为m(m>0)个互不相交的有限集合T1,T2，…，Tm，其中每个集合Ti本身又是一棵结构和树类似的子树。 常用术语（p166） 2.树的表示方法（p167）(1)直观表示法 (2)形式化表示法 (3)凹入表示法 3.树的抽象数据类型 数据集合: 树的结点集合，每个结点由数据元素和构造数　　　　　 据元素之间关系的指针组成。 操作集合: （1）创建MakeTree(T) （2）撤消DestroyTree(T) （3）双亲结点Parent(T, curr) （4）左孩子结点LeftChild(T, curr) （5）右兄弟结点RightSibling(T, curr) （6）遍历树Traverse(T, Visit()) 4.树的存储结构（p169） 树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。 指针有常规指针和仿真指针 2． 二叉树 1.二叉树的定义 二叉树是n(n≥0)个结点的有限集合。n=0的树称为空二叉树；n>0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构： 一对二（1:2） 基本特征:① 每个结点最多只有两棵子树（不存在度大于2的结点）；② 左子树和右子树次序不能颠倒。所以下面是两棵不同的树 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。 完全二叉树：如果一棵深度为k，有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应的二叉树称为完全二叉树 2.二叉树抽象数据类型 数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。 操作集合： （1）创建MakeTree(T) （2）撤消DestroyTree(T)（3）左插入结点InsertLeftNode(curr, x) （4）右插入结点InsertRightNode(curr, x) （5）左删除子树DeleteLeftTree(curr) （6）右删除子树DeleteRightTree(curr) （7）遍历二叉树Traverse(T, Visit()) 3.二叉树的性质 性质1 在一棵非空二叉树的第i层上至多有2i个结点（i≥0）。 性质2 深度为k的二叉树至多有2k+1-1个结点。 说明：深度k=-1，表示没有一个结点；深度k=0，表示只有一个根结点。 性质3 对于一棵非空的二叉树，如果叶结点个数为n0，度为2的结点数为n2，则有 n0= n2+1。 性质4 具有n个结点的完全二叉树的深度k为大于或等于lb(n+1)-1的最小整数。 性质5 对于一棵有n个结点的完全二叉树，按照从上至下和从左至右的顺序对所有结点从0开始顺序编号,则对于序号为i的结点(0≤i < n),有： (1)如果i>0，则其双亲是结点(i-1)/2(“/”表示整除） ；如果i=0，则结点i是根结点，无双亲。 (2)如果2i+1＜n ，其左孩子是结点2i+1；如果2i+1≥n，则结点i无左孩子。 (3)如果2i＋2＜n，其右孩子是结点2i＋2；如果2i＋2≥n，则结点i无右孩子。 3． 二叉树设计和实现（p175） 1二叉树的存储结构 1） 二叉树的顺序存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。对于一般的非完全二叉树显然不能直接使用二叉树的顺序存储结构。可以首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用顺序存储结构存储 2）二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树最常用的的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个域，分别是数据域data、左孩子指针域leftChild和右孩子指针域rightChild。 二叉链存储结构的二叉树也有不带头结点和带头结点两种 3） 二叉树的仿真指针 二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。 2二叉树的操作实现（p177） 4） 二叉树遍历（p179） 三种遍历算法分别为前序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）。 此外，二叉树还有层序遍历。 当对一个二叉树用一种特定的遍历方法来遍历时，其遍历序列一定是线性的，且是惟一的。给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一确定一棵二叉树的结构。 5） 线索二叉树（p186） 对二叉链存储结构的二叉树分析可知，在有n个结点的二叉树中必定存在n+1个空链域。 规定：当某结点的左指针为空时，令该指针指向按某种方法遍历二叉树时得到的该结点的前驱结点；当某结点的右指针为空时，令该指针指向按某种方法遍历二叉树时得到的该结点的后继结点。仅仅这样做会使我们不能区分左指针指向的结点到底是左孩子结点还是前驱结点，右指针指向的结点到底是右孩子结点还是后继结点。因此我们再在结点中增加两个线索标志位来区分这两种情况。 线索标志位定义如下： 每个结点的结构就如下所示 结点中指向前驱结点和后继结点的指针称为线索。在二叉树的结点上加上线索的二叉树称作线索二叉树。对二叉树以某种方法（如前序、中序或后序方法）遍历使其变为线索二叉树的过程称作按该方法对二叉树进行的线索化。 6） 哈夫曼树 1.哈夫曼树的基本概念(p193) 从A结点到B结点所经过的分支序列叫做从A结点到B结点的路径；从A结点到B结点所经过的分支个数叫做从A结点到B结点的路径长度；从二叉树的根结点到二叉树中所有叶结点的路径长度之和称作该二叉树的路径长度。设二叉树有n个带权值的叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和称作该二叉树的带权路径长度（WPL），即： wi为第i个叶结点的权值，li为从根结点到第i个叶结点的路径长度。 定义：由给定的n个叶结点权值可以构造很多棵形态不同的二叉树，WPL值最小的二叉树称为哈夫曼树。 2.哈夫曼编码问题 (p194)：哈夫曼树可用于构造代码总长度最短的编码方案。 代码总长度最短的不等长编码称之为哈夫曼编码。 3.哈夫曼编码的设计和实现（p195） 设计哈夫曼树的结点存储结构为双亲孩子存储结构。采用仿真指针实现，每个结点的数据结构设计为（flag用来判断结点是否入哈夫曼树） 从哈夫曼树求叶结点的哈夫曼编码实际上是从叶结点到根结点路径分支的逐个遍历，每经过一个分支就得到一位哈夫曼编码值。存放哈夫曼编码的数据元素结构为（start表示起始位置）： 7)等价问题 8）树与二叉树的转换 9）树的遍历 第9章 图 1. 图的概述 1.图的基本概念 1）图是由顶点集合及顶点间的关系集合组成的一种数据结构。图G的定义是： G =（V，E） 其中，V = {x|x∈某个数据元素集合} E ={(x，y)|x，y∈V}或E = {＜x， y＞|x，y∈V并且Path(x， y)} 其中，（x，y）表示从 x到 y的一条双向通路，即（x，y）是无方向的；Path（x，y）表示从 x到 y的一条单向通路，即Path（x，y）是有方向的。 2)基本术语（p209） 1.图的抽象数据类型 2.数据集合：由一组顶点集合{vi}和一组边{ej}集合组成。当为带权图时每条边上权wj还构成权集合{wj}。 3.操作集合： （1）初始化Initiate(G, n) （2）插入顶点 InsertVertex(G, vertex) （3）插入边InsertEdgeG, v1, v2, weight)（4）删除边DeleteEdge(G, v1, v2) （5）删除顶点DeleteVertex(G, vertex) （6）第一个邻接顶点GetFirstVex(G, v) （7）下一个邻接顶点GetNextVex(G, int v1, v2) （8）遍历DepthFirstSearch(G 2. 图的存储结构（p213） 1.图的存储结构主要有邻接矩阵和邻接表两种 无向图的邻接矩阵一定是对称矩阵 有向图的邻接矩阵一般是非对称矩阵 带权图及其邻接矩阵 其中V表示了图的顶点集合，A表示了图的邻接矩阵。对于带权图，邻接矩阵第i行中所有0的权值wij。 3. 图的实现（p214） 4. 图的遍历（p225） · 图的深度和广度优先遍历算法 连通图的深度优先遍历递归算法为： （1）访问顶点v并标记顶点v为已访问； （2）查找顶点v的第一个邻接顶点w； （3）若顶点v的邻接顶点w存在，则继续执行，否则算法结束； （4）若顶点w尚未被访问则深度优先搜索递归访问顶点w； （5）查找顶点v的w邻接顶点的下一个邻接顶点w，转到步骤（3）。 对于所示的有向图，深度优先遍历访问顶点次序为： A B D C E 连通图的广度优先遍历算法为： （1）访问初始顶点v并标记顶点v为已访问； （2）顶点v入队列； （3）当队列非空时则继续执行，否则算法结束； （4）出队列取得队头顶点u； （5）查找顶点u的第一个邻接顶点w； （6）若顶点u的邻接顶点w不存在，则转到步骤（3），否则循环执行， （6.1）若顶点w尚未被访问则访问顶点w并标记顶点w为已访问； （6.2）顶点w入队列； （6.3）查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤（6）。 图的广度优先遍历算法是一个分层搜索的过程，需要一个队列以保持访问过的顶点的顺序，以便按访问过的顶点的顺序来访问这些顶点的邻接顶点。 对于所示的有向图，广度优先遍历访问顶点次序为： A B E D C 非连通图的遍历 对于非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。只能访问和初始顶点连通的所有顶点。 但是，每一个顶点都作为一次初始顶点进行深度优先遍历或广度优先遍历，并根据顶点的访问标记来判断是否需要访问该顶点，就一定可以访问非连通图中的所有顶点。 · 算法见（p225） 5. 最小生成树 1.基本概念 1）一个有n个顶点的连通图的生成树是原图的极小连通子图，它包含原图中的所有n个顶点，并且有保持图连通的最少的边 2）如果无向连通图是一个带权图，那么它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小代价生成树，简称最小生成树。 3） 构造有n个顶点的无向连通带权图的最小生成树必须满足以下三条： a) 构造的最小生成树必须包括n个顶点； b) 构造的最小生成树中有且只有n-1条边； c) 构造的最小生成树中不存在回路。 普里姆算法（p229）（算法思想、参数设计、函数设计、说明） 克鲁斯卡尔算法（p234） 克鲁斯卡尔算法是一种按照带权图中边的权值的递增顺序构造最小生成树的方法。设无向连通带权图G=(V,E)，其中V为顶点的集合，E为边的集合。 克鲁斯卡尔算法思想是：设带权图G的最小生成树T由顶点集合和边的集合构成，其初值为T=(V,{})，即初始时最小生成树T只由带权图G中的顶点集合组成，各顶点之间没有一条边。这样，最小生成树T中的各个顶点各自构成一个连通分量。然后，按照边的权值递增的顺序考察带权图G中的边集合E中的各条边，①若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边加入到最小生成树T，同时把两个连通分量连接为一个连通分量；②若被考察的边的两个顶点属于T的同一个连通分量，则将此边舍去。如此下去，当T中的连通分量个数为1时，T中的该连通分量即为带权图G的一棵最小生成树 6． 最短路径 基本概念 路径长度:一条路径上所经过的边的数目 带权路径长度:路径上所经过边的权值之和 最短路径:(带权)路径长度(值)最小的那条路径 拓扑排序 （p242） 1．偏序关系和全序关系 1）拓扑排序就是要由某个集合上的偏序关系得到该集合上的全序关系。 若集合X上的关系R是自反的、反对称的和传递的，则称关系R是集合X上的偏序关系（或称半序关系）。 2） 设关系R是集合X上的偏序关系，若对所有的x,y∈X，有(x,y)∈R或(y,x)∈R，则称关系R是集合X上的全序关系。 3） 偏序关系的实质是在集合X的元素之间建立层次结构。这种层次结构是依赖于偏序关系的可比性建立起来的。但是，偏序关系不能保证集合X中的任意两个元素之间都能比较。而全序关系可以保证集合中的任意两个元素之间都可以比较 2.有向图在实际问题中的应用 一个有向图可以表示一个施工

流程图

破产流程图 免费下载数据库流程图下载数据库流程图下载研究框架流程图下载流程图下载word

，或产品生产流程图，或数据流图等。设图中每一条有向边表示两个子

工程

路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理

之间的先后次序关系。若以有向图中的顶点来表示活动，以有向边来表示活动之间的先后次序关系，则这样的有向图称为顶点表示活动的网 (Activity On Vertex Network)，简称AOV网。 AOV网表示的有向图要解决的一个问题，就是如何得到一个完成整个工程项目的各子工程的序列。这就是有向图的拓扑排序问题。 3.拓扑排序在有向图中的应用 对一个有向图进行拓扑排序，就是将有向图中的所有顶点排成一个线性序列，使得对有向图中任意一对顶点u和v，若是有向图中的一条有向边，则顶点u在该线性序列中出现在顶点v之前。这样的线性序列称为满足拓扑次序的序列，简称为拓扑序列。对有向图建立拓扑序列的过程称为对有向图的拓扑排序。 对于AOV网的拓扑排序就是将AOV网中的所有顶点排成一个线性序列。拓扑排序实际上就是要由某个集合上的一个偏序关系得到该集合上的一个全序关系。 4.有向图的拓扑排序算法 有向图的拓扑排序算法： (1) 在有向图中选择一个没有前驱的顶点，并把它输出； (2) 从有向图中删去该顶点以及与它相关的有向边。 重复上述两个步骤，直到所有顶点都输出，或者剩余的顶点中找不到没有前驱的顶点。在前一种情况下，顶点的输出序列就是一个拓扑序列；后一种情况则说明有向图中存在回路，如果有向图中存在回路，则该有向图一定无法得到一个拓扑序列。 例：对于如下图所示的AOV网，写出利用拓扑排序算法得 到的一个拓扑序列。 解：根据拓扑排序算法，得到的一个拓扑序列为0,1,7,2,4,8,5,9,3,6。 6. 关键路径 （详细见p246） 基本概念：路径长度：AOE网的一条路径上所有活动的总和称为该路径的长度。 关键路径：在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。 关键活动：关键路径上的活动称为关键活动。显然，完成整个工程的最短时间就是AOE网中关键路径的长度，也就是AOE网中各关键活动所持续时间的总和 第10章 排序 1. 排序的基本概念 排序是对数据元素集合建立某种有序排列的过程。 关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。 主关键字:数据元素值不同时该关键字的值也一定不同，是能够惟一区分各个不同数据元素的关键字;不满足主关键字定义的关键字称为次关键字。 内部排序是把待排数据元素全部调入内存中进行的排序。 外部排序是因数量太大，把数据元素分批导入内存，排好序后再分批导出到磁盘和磁带外存介质上的排序方法。 比较排序算法优劣的标准: (1)时间复杂度:它主要是分析记录关键字的比较次数和记录的 移动次数 (2)空间复杂度:算法中使用的内存辅助空间的多少 (3)稳定性:若两个记录A和B的关键字值相等，但排序后A、B的 先后次序保持不变，则称这种排序算法是稳定的 2． 插入排序 插入排序的基本思想是：每步将一个待排序的数据元素，按其关键码大小，插入到前面已经排好序的一组数据元素的适当位置上，直到数据元素全部插入为止。(逐步扩大成果)常用的插入排序有直接插入排序和希尔排序两种。 1.直接插入排序 （p254） 其基本思想是：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。 算法分析 (1)时间效率： 因为在最坏情况下，所有元素的比较次数总和为（1＋…＋n-1)→O(n2)。其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n2) 最好的情况是数据接近有序 (2)空间效率：仅占用1个附加内存单元——O(1) (3)算法的稳定性：稳定 2.希尔(shell)排序(又称缩小增量排序)（p256） (1)基本思想：把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过程结束。 (2)技巧：小组的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个小组,让增量dk逐趟缩短（例如依次取5,3,1），直到dk＝1为止。 (3)优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。 算法分析 (1)时间效率： 时间复杂度为O(nlog2n) (2)空间效率：仅占用1个附加内存单元——O(1) (3)算法的稳定性：由于按增量分组，所以不稳定 三选择排序 基本思想是：每次从待排序的数据元素集合中选取关键字最小（或最大）的数据元素放到数据元素集合的最前（或最后），数据元素集合不断缩小，当数据元素集合为空时选择排序结束。常用的选择排序算法：（1）直接选择排序（2）堆排序 1.直接选择排序（p258） 基本思想是：从待排序的数据元素集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上数据元素的集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素为止。 优点：实现简单 缺点：每趟只能确定一个元素，表长为n时需要n-1趟 算法分析 时间效率： O(n2)——虽移动次数较少，但比较次数仍多。 空间效率：O(1)——没有附加单元（仅用到1个temp) 算法的稳定性：不稳定 2.堆排序 （p260） 1）基本思想:把待排序的数据元素集合构成一个完全二叉树结构，则每次选择出一个最大（或最小）的数据元素只需比较完全二叉树的高度次，即log2n次，则排序算法的时间复杂度就是O(nlog2n)。 2）堆的定义 堆分为最大堆和最小堆两种。定义如下： 设数组a中存放了n个数据元素，数组下标从0开始，如果当数组下标2i+1