(软考软件设计师)专题九：数据结构知识_1368

封面1/47作者： PanHongliang仅供个人学习专题九：数据结构知识数据结构是计算机软件的一门基础课程 , 计算机科学各个领域及有关的应用软件都要用到各种数据结构语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录2/47树等；数据库系统运用线性表、多链表及索引树等进行数据管理；而在人工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，如广义表、集合、搜索树及各种有向图等等 . 学习数据结构目的是要熟悉一些最常用的数据结构， 明确数据结构内在的逻辑关系，知道它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种操作时的动态性质及实际的执行算法，进一步提高软件计和编程水平 . 通过对不同存储结构和相应算法的对比，增强我们根据求解问题的性质选择合理的数据结构， 并将问题求解算法的空间、时间及复杂性控制在一定范围的能力 .软件设计师考试大纲对数据结构部分的要求是熟练掌握常用数据结构和常用算法，因此，本专题从数据结构的概述出发，对基本的概念引出常用的数据结构类型的介绍和讲解， 同时在讲解各种数据结构中间采用算法与数据结构相结合的方式， 在算法步骤中使用数据结构，对数据结构的重点、难点进行了分析，最后讲解了与数据结构紧密相关的排序和查找算法， 以及一些以往考试卷的分析 .1. 数据结构概述数据结构 研究了计算机需要处理的数据对象和对象之间的关系；刻画了应用中涉及到的数据的逻辑组织；也描述了数据在计算机中如何存储、传送、转换.学习数据结构注意的问题：系统掌握基本数据结构的特点及其不同实现.了解并掌握各种数据结构上主要操作的实现及其性能（时间、空间）的分析.掌握各种数据结构的使用特性，在算法设计中能够进行选择.掌握常用的递归、回溯、迭代、递推等方法的设计掌握自顶向下、逐步求精的程序设计方法.掌握自顶向下、逐步求精的程序设计方法.在学习数据结构的知识之前，我们要了解一下数据结构中的基本概念.数据：对客观事物的符号表示，在计算机中就是指所有能输入到计算机中并被计算机程序所处理的符号的总称 .数据项：是数据的不可分割的最小单位；数据元素： 是数据的基本单位，在计算机程序中通常作为一个整体进行处理；一个数据元素可由若干个数据项组成 .数据对象： 是性质相同的数据元素的集合，是数据的一个子集.数据结构上的基本操作：插入操作删除操作更新操作查找操作排序操作3/47数据结构是指数据对象及相互关系和构造方法，一个数据结构B 形式上可以用一个二元组表示为B=（ A，R）. 其中， A 是数据结构中的数据（称为结点）的非空有限集合，R是定义在 A 上的关系的非空有限集合.根据数据元素之间的关系的不同特性，通常有下列4 类基本结构 .集合结构中的数据元素除了“同属于一个集合”的关系外，别无其他关系 .线性结构结构中的数据元素之间存在一个对一个的关系.树形结构结构中的元素之间存在一个对多个的关系.图状结构或网状结构结构中的元素之间存在多个对多个的关系.数据结构中，结点与结点间的相互关系是数据的逻辑结构. 数据结构在计算机中的表示（又称为映象）称为数据的物理结构，也称存储结构.数据元素之间的关系在计算机中有两种不同的表示方式：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构.任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构 .数据的逻辑结构分为两类：线性结构：线性表、栈、队列和串非线性结构：树、图数据的存储方法有四类：顺序存储方法链接存储方法索引存储方法散列存储方法2. 常用数据结构2.1 线性表在数据结构中，线性结构常称为线性表，是最简单、最常用的一种数据结构，它是由 n 个相同数据类型的结点组成的有限序列.其特点是：在数据元素的非空有限集合中，存在唯一的一个被称做“第一个”的数据元素存在唯一的一个被称做“最后一个”的元素数据元素除第一个之外，集合中的每个数据元素均只有一个前驱除最后一个之外，集合中每个数据元素均只有一个后继4/47一个由 n 个结点 e0，e1 ， en-1 组成的线性表记为：（e0， e1 ， en-1 ） . 线性表的结点个数称为线性表的长度，长度为0 的线性表称为空的线性表，简称空表. 对于非空线性表， e0 是线性表的第一个结点，en-1 是线性表的最后一个结点. 线性表的结点构成了一个序列，对序列中两个相邻结点ei 和 ei-1 ，称前者是后者的前驱结点，后者是前者的后继结点 .线性表最重要的性质是线性表中结点和相对位置是确定的.线性表的结点也称为表元，或称为记录，要求线性表的结点一定是同一类型的数据 . 线性表的结点可由若干个成分组成，其中唯一标识表元的成分成为关键字，简称键 .线性表是一个相当灵活的数据结构，它的长度可以根据需要增长或缩短. 对线性表的基本运算如下：INITIATE （ L）初始化操作LENGTH（L）求长度函数GET（ L，i ）取元素函数PRIOR（ L， elm）求前驱函数NEXT（L， elm） 求后继函数LOCATE（L，x ） 定位函数INSERT（L，i ，b）插入操作DELETE（L，i ）删除操作有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链接存储.根据存储方式的不同，其上述的运算实现也不一样.顺序存储：是最简单的存储方式，其特点是逻辑关系上相邻的两个元素在物理位置上也相邻 . 通常使用一个足够大的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中.顺序存储方式优点：能直接访问线性表中的任意结点.线性表的第i 个元素 ai的存储位置可以使用以下公式求得：LOC（ ai ）=LOC（ a1）+（ i-1 ）*l式中 LOC（a1）是线性表的第一个数据元素a1 的存储位置， 通常称做线性表的起始位置或基地址 .顺序存储的缺点：1) 线性表的大小固定，浪费大量的存储空间，不利于节点的增加和减少；执行线性表的插入和删除操作要移动其他元素，不够方便；5/47链式存储线性表链接存储是用链表来存储线性表.单链表（线性链表）：从链表的第一个表元开始，将线性表的结点依次存储在链表的各表元中. 链表的每个表元除要存储线性表结点的信息以外，还要有一个成分来存储其后继结点的指针.线性链表的特点是： 每个链表都有一个头指针， 整个链表的存取必须从头指针开始，头指针指向第一个数据元素的位置，最后的节点指针为空 . 当链表为空时，头指针为空值；链表非空时，头指针指向第一个节点 .链式存储的缺点：1) 由于要存储地址指针，所以浪费空间；直接访问节点不方便；循环链表：循环链表是另一种形式的链式存储结构， 是单链表的变形 . 它的特点就是表中最后一个结点的指针域指向头结点，整个链表形成一个环 . 因此，从表中任意一个结点出发都可以找到表中的其他结点 .循环链表和单向链表基本一致，差别仅在于算法中循环的条件不是结点的指针是否为空，而是他们的指针是否等于头指针，循环链表最后一个结点的link指针不为 0 ( NULL)，而是指向了表的前端.为简化操作，在循环链表中往往加入表头结点.循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址.循环链表的示例：带表头结点的循环链表：双向链表：双向链表是另一种形式的链式结构，双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋 . 双向链表克服了单链表的单向性的缺点 .前驱方向后继方向6/47双向链表也可以有循环表， 链表中存在两个环. 一个结点的前趋的后继和该结点的后继的前趋都是指向该结点的.p =p lLink rLink = p rLink lLink2.2 栈栈（ Stack ）是限定仅在表尾进行插入或删除操作的线性表. 表尾端称栈顶（ top ），表头端称栈底（ bottom ） .若有栈 S=（ s ， s ， ， sn-1）则 s为栈底结点， sn-1为栈顶结点 . 通常称栈的结点010插入为进栈，栈的结点删除为出栈. 因为最后进栈的结点必定最先出栈，所以栈具有后进先出的特点 . 可以用一下一个图形来形象的表示：栈有两种存储结构：顺序栈和链栈顺序栈即栈的顺序存储结构是，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针 top 指示栈顶元素的当前位置 .栈也可以用链表实现， 链式存储结构的栈简称链栈 . 若同时需两个以上的栈， 则最好采用这种结构 . 对于栈上的操作，总结如下，大家可以仔细看一下这些程序，一个大的程序都是由一些对数据结构的小的操作组成的.顺序存储的栈的基本操作如下：判断栈满：int stackfull(seqstack *s)return (s-top= =stacksize-1)。进栈：7/47voidpush(seqstack *s,datatypex)if (stackfull(s)error(“ stack verflow” ) 。s-data+s-top=x。判断栈空：int stackempty(seqstack *s)return (s-top= = -1)出栈：datatype pop(seqstack *s)if (stackempty(s)error(“stack underflow”) 。x=s-datatop。s-top-。return (x)。链接存储栈：用链表实现的栈，链表第一个元素是栈顶元素，链表的末尾是栈底节点，链表的头指针就是栈顶指针，栈顶指针为空则是空栈 . 若同时需要两个以上的栈，最好采用链表作存储结构链接存储的栈的操作如下：进栈：Void push(linkstack *p,datatype x)stacknode *q q=(stacknode*)malloc(sizeof(stacknode)。q data=x 。8/47q next=p top 。p top=q 。出栈：Datatypepop(linkstack*p)datatypex 。stacknode*q=p top 。if(stackempty(p)error(“ stack underflow.”) 。x=q data 。p top=q next 。free(q)。return x。多栈处理栈浮动技术：n个栈共享一个数组空间V mn 设立栈顶指针数组t n+1和 栈底指针数组b n+1，t i 和 b i 分别指示第i个栈的栈顶与栈底，b n 作为控制量，指到数组最高下标各栈初始分配空间s = m/n指针初始值t 0 =b0 = -1b n = m-1t i = b i = b i -1 + s,i = 1, 2, n-12.3 队列队列是只允许在一端进行插入， 另一端进行删除运算的线性表 . 允许删除的那一端称为队首（ front ），允许插入运算的另一端称为队尾（ rear ）. 通常称队列的结点插入为进队，队列的结点删除为出队 . 若有队列Q=（q0，q1， ， qn-1 ）则 q0 为队首结点， qn-1 为队尾结点 . 因最先进入队列的结点将最先出队，所以队列具有先进先出的特性.9/47可以用顺序存储线性表来表示队列，也可以用链表实现， 用链表实现的队列称为链队列.队列操作：int push(PNODE *top， int e)是进栈函数，形参top 是栈顶指针的指针，形参e是入栈元素 .int pop(PNODE *top，int oe)是出栈函数，形参top 是栈顶指针的指针，形参e作为返回出栈元素使用.int enQueue(PNODE *tail，int e)是入队函数，形参tail是队尾指针的指针，形参 e 是入队元素 .int deQueue(PNODE *tail，int *e)是出队函数，形参tail是队尾指针的指针，形参 e 作为返回出队元素使用.定义结点的结构如下：typedef struct nodeint value。struct node *next。NODE， *PNODE。函数int push(PNODE *top， int e)PNODE p = (PNODE)malloc(sizeof(NODE)。if(!p)return 1。p-value = e。p-next = *top。 /指向栈顶指针*top = p。return 0。函数int pop(PNODE *top， int *e)10/47PNODE p = *top 。if(p = NULL) return 1。*e = p-value。*top = p-next。/ 栈顶指向取出的数的指针free(p)。return 0。函数int enQueue(PNODE *tail， int e)PNODE p，t ；t = *tail。p = (PNODE)malloc(sizeof(NODE)；if(!p) return l 。p value = e。p next = t next 。t-next = p。/将元素加在尾指针后*tail = p。return 0。函数int deQueue(PNODE *tail， int e)PNODE p，q；if(*tail)-next = *tail) return 1。 / 队列已经空p = (*tail)-next。/p获得尾指针q = p-next。e = q-value。p-next = q-next。if(*tail = q)*tail = p。/尾指针指向最后节点free(q)。return 0。11/47)循环队列 (Circular Queue):存储队列的数组被当作首尾相接的表处理.队头、队尾指针加1 时从 maxSize -1 直接进到 0，可用语言的取模( 余数 ) 运算实现 .队头指针进1:front= ( front+ 1) %maxSize。队尾指针进 1:rear= (rear+1)%。maxSize队列初始化： front =rear = 0 。队空条件： front =rear 。队满条件： ( rear + 1) %maxSize = front循环队列的进队和出队 :优先级队列：是不同于先进先出队列的另一种队列 . 每次从队列中取出的是具有最高优先权的元素2.4串字符串是非数值处理应用中重要的处理对象. 字符串是由某字符集上的字符所组成的任何有限字符序列.当一个字符串不包含任何字符时，称它为空字符串 . 一个字符串所包含的有效字符个数称为这个字符串的长度. 一个字符串中任一连续的子序列称为该字符串的子串. 包含子串的字符串相应称为主串. 通常称该字符在序列中的序号为该字符在串中的位置.字符串的串值必须用单引号括,c1c 2c3cn 起来，但单引号本身不属于串，它的作用是为了避免于变量名和数的常量混淆. 在 C 语言中，字符串常量是用一对双引号括住若干字符来表示，如“I am a student”字符串通常存于字符数组中，每个字符串最后一个有效字符后跟一个字符串结束符“0 ”. 系统提供的库函数形成的字符串会自动加结束符号，而用户的应用程序中形成的字符串必须由程序自行负责添加字符串结束符号.两个串相等当且仅当两个串的值相等，长度相等并且各个对应位置的字符都相等.常用的字符串的基本操作有7 种 .ASSING（s ，t ）和 CREAT（s ，ss ）赋值操作EQUAL（ s， t ）判等函数LENGTH（s ）求长度函数CONCAT（s ，t ）联接函数12/47SUBSTR（s ，start，len ）求子串函数INDEX（ s， t ）定位函数REPLACE（ s，t ，v）置换函数INSERT（s ，pos， t ）插入函数DELETE（s ，pos， t ）删除函数(1) 求字符串长 ,int strlen(char s)（2）串复制 (copy)char *strcpy(char to,char from)。该函数将串from 复制到串 to 中，并且返回一个指向串to 的开始处的指针 .(3) 联接 (concatenation)charstrcat(char to,char from)该函数将串from 复制到串 to 的末尾，并且返回一个指向串to 的开始处的指针 .(4) 串比较（ compare)int strcmp(chars1,char s2)。该函数比较串s1 和串 s2 的大小，当返回值小于0，等于 0 或大于 0 时分别表示s1s2例如： result=strcmp(“baker ”, ” Baker ”)result0result=strcmp(“12”, ”12”) 。result=0result=strcmp(“ Joe”, ”Joseph”) 。result1 时，元素 ai,j=0.14/47LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1) =LOC(0,0)+(2i+j)4. 稀疏矩阵简单说，设矩阵 A 中有并且分布没有一定规律列和值s 个非零元素，若s 远远小于矩阵元素的总数（即sm n），. 用顺序存储结构的三元组对稀疏矩阵进行存储，分别记录行、十字链表：由于非零元的位置和个数变化，所以用链表存储更恰当；在这种情况下采用十字链表来表示，每个非零元用一个节点表示，节点中有行、列还有向下的域和线右的域；此外还需要一个指向列链表的表头节点和指向行链表的表头节点 . 还可以设置一个指向整个十字链表的表头节点 . 还可以把列表头和行表头节点组成数组，便于操作；各种广义表示意图2.6树概述树型结构是一类重要的非线性数据结构. 其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构.树是由一个或多个结点组成的有限集T，它满足以下两个条件：I. 有一个特定的结点，成为根结点15/47II. 其余的结点分成 m（m=0）个互不相交的有限集 T0，T1， ， Tm-1. 其中每个集合又都是一棵树，称 T0， T1， ， Tm-1 为根结点的子树 .这里可以看出树的定义是递归的，即一棵树由子树构成，子树又由更小的子树构成. 一个结点的子树数目， 称为结点的度 . 树中各结点的度的最大值则称为树的度. 树中结点的最大层次称为树的深度.如果将树中结点的各子树看成从左到右是有次序的（即不能交换），则称该树为有序树，否则为无序树 . 森林是 m（m=0）棵互不相交的树的集合.存储结构树是非线性的结构，不能简单地用结点的线性表来表示 . 树有多种形式地存储结构，最常用的是标准存储形式和带逆存储形式 . 在树的标准存储结构中，树中的结点可分成两部分：结点的数据和指向子结点的指针 . 当程序需从结点返回到其父结点时，需要在树的结点中存储其父结点的位置信息，这种存储形式就是带逆存储结构.具体使用的链表结构有：双亲表示法： 利用每个节点只有一个双亲的特点；求节点的孩子时要遍历整个向量孩子表示法：把每个节点的孩子都排列起来，一单链表存储，则n 个节点有 n个孩子链表，而n 个头指针又组成了一个线性表.孩子兄弟表示法（又称二叉树表示法，或二叉链表表示法）：节点两个指针分别指向该节点的第一个孩子和下一个兄弟节点.树的遍历在应用树结构时，常要求按某种次序获得树中全部结点的信息，这可通过树的遍历操作来实现 . 常用的树的遍历方法有：树的前序遍历：首先访问根结点，然后从左到右遍历根结点的各棵子树.树的后序遍历： 首先从左到右按后序遍历根结点的各棵子树，然后访问根结点.树的层次遍历： 首先访问处于0 层上的根结点，然后从左到右依次访问处于1 层、 2 层 上的结点，即自上而下从左到右逐层访问树各层上的结点 .二叉树概述与一般的树的结构比较，二叉树在结构上更规范和更有确定性，应用也比树更为广泛.16/47二叉树的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2 的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒. 二叉树与树不同的地方在于，首先二叉树可以为空，空的二叉树没有结点；另外，在二叉树中，结点的子树是有序的，分左右两棵子二叉树.二叉树采用类似树的标准存储形式来存储.二叉树的性质 :二叉树具有下列重要特性.i 层至多有个结点（ i=1 ） .k 的二叉树至多有 -1 个结点（ k=1）.对任何一棵二叉树T，如果其终端结点数为n0，度为 2 的结点数为 n2，则 n0=n2+1.n 个结点的完全二叉树的深度为.二叉树的遍历树的所有遍历方法都适用于二叉树，常用的二叉树遍历方法有3 种.#include#include#define NULL 0Typedef struct nodechar data。struct node *lchild,*rchild。TREENODE。TREENODE *root。前序遍历 :访问根结点，按前序遍历根结点的左子树，按前序遍历根结点的右子树.中序遍历 :按中序遍历根结点的左子树，访问根结点，按中序遍历根结点的右子树.中序遍历算法 :17/47Void inorder(TREENODE *p)if(p!=NULL) inorder(p lchild)。printf(“ %c” ,p data)inorder(prchild)。后序遍历 :按后序遍历根结点的左子树，按后序遍历根结点的右子树，访问根结点 .以上 3 种遍历方法都是递归定义的.哈夫曼及其应用：又称为最优树，是一类带权路径长度最短的树路径长度： 从树中一个节点到另一个节点之间的分支构成的这两个节点之间的路径，路径上的分支树木就称为路径长度；树的路径长度：从树根到每一节点的路径长度之和；树的带权路径长度：树中所有叶子节点的带权路径长度之和；哈夫曼树就是一棵n 个叶子节点的二叉树，所有叶子节点的带权之和最小.算法描述：给定 n 个节点的集合，每个节点都带权值；选两个权值最小的节点构造一棵新的二叉树，新二叉树的根节点的权值就是两个子节点权值之和；从 n 个节点中删除刚才使用的两个节点，同时将新产生的二叉树根节点放在节点集合中.重复 2， 3 步，知道只有一棵树为止.例题：已知节点的前序序列和中序序列分别为：前序序列： ABCDEFG中序序列： CBEDAFG求出整个二叉树，以及构造过程2.7 图18/47基本概念 :图是一种较线性表和树更为复杂的数据结构. 在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关.一个图 G由非空有限的顶点集合 V 和有限的边的集合 E 组成，记为 G=（ V， E）. 图一般分为两种类型 .无向图的边是顶点的无序偶，用（i ， j ）来表示顶点i 和 j 之间的边 .有向图的边是顶点的有序偶，有向图的边也成为弧，用 来表示顶点i 和 j 之间的弧.其中，有条边的无向图称为完全图，而具有n(n-1) 条弧的有向图成为有向完全图.有时图的边或弧具有与它相关的树，这种与图的边或弧相关的数称作权. 带权图也简称为网 .如果同为无向图或同为有向图的两个图G1=（ V1，E1）和 G2=（V2 ，E2）满足V 2V1E2E1则称图 G2是图 G1的子图 .顶点的度就是指和顶点相关联的边的数目. 在有向图中，以顶点 v 为头的弧的数据成为v的入度；以v 为尾的弧成为v 的出度 . 这里有一个重要的公式反映了顶点和边的关系.其中， e 表示边的数目， n 表示顶点个数， TD(V ) 表示顶点 V 的度 .ii在图 G=（ V， E）中，如果存在顶点序列（ v0，v1， ， vk ），其中 v0 =p ，vk =q ，且（ v0， v ），（ v1， v） ，（ vk-1， v）都在 E 中，则称顶点 p 到顶点 q 有一条路12k径，并用（ v0，v ， ， v）表示这条路径，路径的长度就是路径上的边或弧的数目，1k这条路径的长度为k.如果第一个顶点和最后一个顶点相同的路径称为回路或环. 序列中顶点不重复出现的路径称为简单路径.对无向图而言，如果从任意两个不同顶点i 和 j 之间都有路径，则该无向图是连通的. 无向图中的极大连通子图为该图的连通分量.对有向图而言，如果任意两个不同顶点i到 j 有路径，同时 j 到 i 也有路径，则该有向图是强连通的 . 同样，无向图中的极大连通强子图为该图的强连通分量.存储结构 : 最常用的存储结构是有两种 .邻接矩阵 :这是反映顶点间邻接关系的矩阵. 定义如下：19/47设 G=（V， E）是具有 n（ n 1）个顶点的图， G的邻接矩阵M是一个 n 行 n 列的矩阵，若（ i ，j ）或 E，则 Mij=1；否则 Mij=0.邻接表 : 这是图的链式存储结构.图的每个顶点都建立了一个链表，且第i 个链表中的结点代表与顶点i 相关联的一条边或由顶点i 出发的一条弧 . 而这些链表的头指针则构成一个顺序线性表.另外，还有其他的一些存储结构，如十字链表和邻接多重表，分别用来存储有向图和无向图 .图的遍历 :图的遍历是指从图中的某个顶点出发，沿着图中的边或弧访问图中的每个顶点，并且每个顶点只被访问一次 . 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础 .通常有两种方法，它们对无向图和有向图都适用.深度优先搜索 :类似于树的先根遍历.广度优先搜索 :类似于树的层次遍历.这两种算法的时间复杂度相同，不同之处仅仅在于对顶点访问的顺序不同.图的有关算法涉及到图的有关算法比较多，这里只简单归纳介绍一下，具体算法希望大家参考有关资料 .求最小代价生成树设 G=（V ，E）是一个连通的无向图， 若 G1 是包含 G 中所有顶点的一个无回路的连通子图，则称 G1 为 G 的一棵生成树 . 其中代价最小（各条边的权值之和最小）的生成树就称为最小代价生成树（简称最小生成树） .这里提供两种算法来求解这一问题：普里姆（Prim）算法和克鲁斯卡尔（Kruskal ）算法 .分别适用于求边稠密的网的最小生成树和边稀疏的网的最小生成树，其时间复杂度分别是O(n2)和 O(eloge)（ e 为网中边的数目） .其中 prim 算法基本思想 ：任选一个顶点v 0 开始，连接与v0 最近的顶点v1，得子树T1，再连接与T1 最近的顶点v2，得子树 T2，如此进行下去，直到所有顶点都用到为止.L(v):v到子树 T0 的直接距离 .E是边集合 .输入加权连通图的带权邻接矩阵C=（C ）n*n.ij(1)T0- 空集， C（ T0） -0,V 1=v 020/47(2)对每一点 v 属于 V-V， L（ v） -C(v, v) 。 如果 (v, v0) 不属于 E，则 C(v, v )=100无穷大 (3) 若 V1=V,则输出 T0， C（ T0），停机 . 否则转到下一步；(4)在 V-V1 中找一点 u, 使 L（ u）=minL(v)|v属于 (V-V 1 ), 并记在 V1 中与 u 相邻的点为 w,e=(w,u)(5) T0 -T 0， C（ T0 ）- C （T0）+ C （ e）, V 1 -V 1(6)对所有的 v 属于 V-V1，若 C(v, u)L（v） , 则 L（v）- C(v, u),否则 L（ v）不变 .(7) 转 3克鲁斯卡尔（ Kruskal ）算法基本思想 ：最初把图的 n 个顶点看作n 个分离的部分树，每个树具有一个顶点，算法的每一步选择可连接两分离树的边中权最小的边连接两个部分树，合二为一，部分树逐步减少，直到只有一个部分树，便得到最小生成树.克鲁斯卡尔（ Kruskal ）算法步骤：T0 : 存放生成树的边的集合，初态为空；C(T0): 最小生成树的权，初值为0；VS：部分树的顶点集合，其初值为 v v v01n输入边的端点数组A（ e）, 边的权值 w(e) 。(1)T为空， C(T )-0 。 VS为空，将 E 中的边按从小到大的顺序排列成队列Q；00(2)对所有的 v 属于 V， VS -v 。(3)若 |VS|=1 ，输出 T，C(T ) ，停止，否则转下一步；00(4)从 Q中取出排头边（ u,v ），并从 Q中删除（ u,v ）。(5)如 u,v杂 VS 的同一个元素集 V中，则转4，否则分属于两个几个 V V2，11进行下一步；(6)T0- T 0 ， V-, C(T0)- C(T 0 )+ C(u,v),转 3求最短路径在图中求最短路径问题有两种提法，一是求从某个源点到其他顶点的最短路径， 二是求每一对顶点之间的最短路径 .对于前者，一般采用迪杰斯特拉（ Dijkstra）算法，按路径长度递增的次序产生最短路径 . 时间复杂度为 O(n2).迪杰斯特拉（ Dijkstra ）算法的基本思想：生长一棵以v0 为根的最短路树，在这棵树上每一顶点与根之间的路径都是最短路径. 由于网络不存在负权，最短路树的生长过程中21/47各顶点将按照距v 0 的远近及顶点的相邻关系，逐次长入树中，先近后远，直至所有顶点都已经在树中 .解决后面一种问题的方法是：每次以一个顶点为源点，重复执行迪杰斯特拉算法n 次.另外还可以使用一种弗洛伊德（Floyd ）算法，其时间复杂度也是O(n3).弗洛伊德（ Floyd）算法基本思想：直接在图的带权邻接矩阵中用插入顶点的方法依次（ ）（）（ ）（ ）构造出 n 个矩阵， D 1 D2.D n ,使最后得到的矩阵 .Dn 成为图的距离矩阵， 同时也求出插入点矩阵以便得到两点见的最短路径.拓扑排序拓扑排序的算法原理实际很简单.I. 在有向图中选一个没有前驱的顶点且输出之II. 从图中删除该顶点和所有以它为尾的弧重复执行以上两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止. 后一种情况则说明有向图中存在环.求关键路径在 AOE 网络中的某些活动可以并行的进行，因此完成工程的最少时间是从开始顶点到结束顶点的最长路径长度， 称从开始顶点到结束顶点的最长路径为关键路径，关键路径上的活动即为关键活动 .3. 数据结构相关算法3.1 排序算法基本概念排序 (Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列. 作为排序依据的数据项称为“排序码”，也即数据元素的关键码. 为了便于查找，通常希望计算机中的数据表是按关键码有序的 . 如有序表的折半查找， 查找效率较高 . 还有，二叉排序树、 B-树和 B+树的构造过程就是一个排序过程 . 若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可能不唯一，这是因为具有相同关键码的数据元素， 这些元素在排序结果中， 它们之间的的位置关系与排序前不能保持.若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的.排序分为两类：内排序和外排序.内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列.22/47外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序 .对于有n 个结点的线性表（e0， e1， ， en-1），将结点中某些数据项的值按递增或递减的次序，重新排列线性表结点的过程，称为排序 . 排序时参照的数据项称为排序码，通常选择结点的键值作为排序码 .若线性表中排序码相等的结点经某种排序方法进行排序后，仍能保持它们在排序之前的相对次序，称这种排序方法是稳定的；否则，称这种排序方法是不稳定的.在排序过程中， 线性表的全部结点都在内存， 并在内存中调整它们在线性表中的存储顺序，称为内排序 . 在排序过程中，线性表只有部分结点被调入内存，并借助内存调整结点在外存中的存放顺序的排序方法成为外排序.下面通过一个表格简单介绍几种常见的内排序方法，以及比较一下它们之间的性能特点.排序方法简介平均时最坏情辅助存是否稳间况储定反复从还未排好序的那部分线性表中选出键值最小的结点，并按从线性表中选出的顺序排列选择结点，重新组成线性表 . 直至未O()O()O(1)排序不稳定排序的那部分为空，则重新形成的线性表是一个有序的线性简表. (单选择排序)单假设线性表的前面 I 个结点序列排e0，e1， ，eI-1 是已排序的. 对序直接结点在这有序结点 ei 序列中找插入位置，并将 ei 插入，而使 i+1插入O()O()O(1)稳定个结点序列 e0，e1， ，ei 也变排序成排序的. 依次对 i=1，2， ，n-1分别执行这样的插入步骤，最终实现线性表的排序.23/47对当前还未排好序的范围内的全部结点，自上而下对相邻的两个结点依次进行比较和调整，让冒泡键值大的结点往下沉，键值小的O()O()O(1)稳定排序结点往上冒 . 即，每当两相邻比较后发现它们的排列顺序与排