各种排序的原函数

各种排序的原函数第一页，共一百一十八页，2022年，8月28日

为什么研究数据结构

对数据进行合理组织，使算法设计更容易、高效和可靠。

数据结构的定义

相互之间具有一种或多种特定关系的数据元素的集合。（关系可用操作描述，操作的描述称算法）数据结构的研究内容数据逻辑结构：数据元素之间的相互关系，面向问题；数据存储结构：逻辑结构在计算机中的实现，面向计算机；运算：在逻辑结构上定义一组相应的运算，在存储结构上建立算法实现这些运算。2.1数据结构概述第二页，共一百一十八页，2022年，8月28日2.1数据结构概述逻辑结构（4种）集合结构、线性结构(1对1)、树型结构(1对多)、图/网结构(多对多)存储结构（4种）顺序(连续存储单元)、链接(用指针链接元素)、索引(包含索引表和子表)、散列存储(由散列函数得存储地址)运算

运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。每种逻辑结构都有一个运算集合。常用的运算有检索、插入、删除、更新、排序等。第三页，共一百一十八页，2022年，8月28日2.1数据结构概述算法定义精确地描述解决问题所用方法的一系列确切有穷的步骤评价算法优劣的标准时间复杂度：算法运行时间随问题规模(如矩阵阶数、字符串长度、数据元素个数等)n增长的数量f(n)，一般用算法在最坏情况下语句重复执行的最大次数估算。虽不能精确确定算法执行时间，但可以评估算法的时间增长趋势。空间复杂度：指算法中所需的辅助空间单元。第四页，共一百一十八页，2022年，8月28日算法的时间量级第五页，共一百一十八页，2022年，8月28日第六页，共一百一十八页，2022年，8月28日2.2线性表和数组一、线性表的定义线性表的逻辑结构是n个数据元素的有限序列: (a1,a2,a3,…an)

n为线性表的长度(n≥0)，n=0的表称为空表数据元素呈线性关系.必存在唯一的称为“第一个”的数据元素;必存在唯一的称为“最后一个”的数据元素；除第一个元素外，每个元素都有且只有一个前驱元素；除最后一个元素外，每个元素都有且只有一个后继元素。所有数据元素ai在同一个线性表中必须是相同的数据类型第七页，共一百一十八页，2022年，8月28日2.2线性表和数组线性表的基本运算主要有：求表长度检索插入删除修改归并线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表；用链式存储结构存储的线性表称为链表

数组是一种典型的顺序表第八页，共一百一十八页，2022年，8月28日2.2线性表和数组二、数组1、数组的特点均匀性：每个元素占据相同大小的存储空间。静态分配空间，必须预先定义大小。随机存取：下标与值一一对应，每个元素由下标确定位置。2、数组的顺序分配

n维数组A=[l1…u1,l2…u2,…,

ln…un]

元素个数：一维数组存储同构的线性表，要存储n维数组，需将n维下标映射为计算机存储的一维地址第九页，共一百一十八页，2022年，8月28日2.2线性表和数组n维数组的存储行主排列法：按下标由外至里变化的顺序依次存放于内存(外先变)列主排列法：按下标由里至外变化的顺序依次存放于内存例：二维数组A=[1…m，1…n]行主序：列主序：第十页，共一百一十八页，2022年，8月28日2.2线性表和数组地址计算公式（P44）一维数组二维数组三维数组n维数组三、顺序表(数组)的运算（1）插入，设线性表结点的类型为整型，插入之前有n个结点，把值为x的新结点插在线性表的第i(0<=i<=n)个位置上，步骤如下：检查有关参数的合理性；把原来第n-1个结点至第i个结点依次后移一个位置；把新结点放在第i个位置上；修正结点个数。第十一页，共一百一十八页，2022年，8月28日2.2线性表和数组intsq_insert(int*list,int*npt,inti,intmaxn,intx)//*list,线性表首结点指针//*npt,记录线性表结点数的变量的指针//i,插入位置//maxn,线性表可以存储的最大数据元素个数//x;插入结点值{intk;if(i<0||i>*npt)return1;//不合理的插入位置

if(*npt==maxn)return2;//存储线性表的数组已满

for(k=*npk;k>i;k--)list[k]=list[k-1];//第n-1结点至第i结点后移1个位置

list[i]=x;//新结点插入

++*npt;//线性表结点数加1return0;//插入成功}第十二页，共一百一十八页，2022年，8月28日2.2线性表和数组（2）删除：在有n个结点的线性表中，删除第i(0<=i<=n-1)个结点。步骤如下：检查有关参数的合理性；把原来第i+1个结点至第n-1个结点依次前移一个位置；修正结点个数。第十三页，共一百一十八页，2022年，8月28日2.2线性表和数组intsq_delete(int*list,int*npt,inti)//*list,线性表首结点指针//*npt,记录线性表结点数的变量的指针//i,删除位置{intk;if(i<0||i>*npt)return1;//不合理的删除位置

if(*npt==0)return2;//线性表已空

for(k=i+1;k<*npt;k++)list[k-1]=list[k];//第i+1结点至第n-1结点前移1个位置

--*npt;//线性表结点数减1return0;//删除成功}第十四页，共一百一十八页，2022年，8月28日四、顺序表的特点和缺点特点:逻辑上相邻则物理位置相邻；随机存取；利用公式可计算其地址。缺点：静态分配存储空间，最大可能空间，浪费；静态分配存储空间，难以扩充表容量；插入和删除需移动大量元素。2.2线性表和数组第十五页，共一百一十八页，2022年，8月28日2.3栈和队列一、栈1、定义只能在表的一端存取元素的后进先出(LIFO)的线性表。

top—栈顶

m—栈的容量，m≥n栈空时，top=0增加元素，top+1；撤销元素，top-1；top>m或top<0栈溢出可用数组实现堆栈第十六页，共一百一十八页，2022年，8月28日2.3栈和队列2、栈的运算判空(isemp(s))：若栈为空栈，则返回True，否则返回False。弹栈(pop(s,i))：撤销s的栈顶元素，并赋给i，产生新栈。压栈(push(s,i)):把元素i堆进栈顶，产生新栈。注意：弹、压栈操作前需判断栈是否会溢出(是否空栈或满栈)。第十七页，共一百一十八页，2022年，8月28日2.3栈和队列intpush(NODEstack[],intmaxn,int*toppt,NODEx)//压栈函数//设栈点的数据类型为NODE，栈空间最多存储maxn个结点{if(*toppt>=maxn)return1;//栈满，进栈失败返回1*toppt++；

stack[*toppt]=x;//完成进栈

return0;//进栈成功返回0}intpop(NODEstack[],int*toppt,NODE*cp)//弹栈函数{if(*toppt==0)return1;//栈空，弹栈失败返回1*cp=stack[*toppt];//完成弹栈*toppt--；

return0;//弹栈成功返回0}第十八页，共一百一十八页，2022年，8月28日2.3栈和队列3、栈的应用子程序的调用及返回调用时，下一语句地址压栈；返回时，弹栈，获得返回后的执行语句的地址第十九页，共一百一十八页，2022年，8月28日2.3栈和队列表达式计算参数传递递归过程的实现第二十页，共一百一十八页，2022年，8月28日2.3栈和队列二、队列1、定义是一种只许在队首删除元素，在队尾插入元素的先进先出(FIFO)的线性表。2、顺序存储队列（1）顺序队列队尾指示器rear指示队尾元素，队头指示器front指示队头元素的前一位置，即队头指针所指的位置是空的。第二十一页，共一百一十八页，2022年，8月28日2.3栈和队列入队时，rear+1，加入数据元素；出队时，取出数据元素，front+1；当front=rear时，队列空。存在问题：随着进队和出队操作，front和rear→数组尾端，会出现前端空着，而队列空间已用完的情况,称为“假溢出”(P40,图2.21(c))。为此，引入循环队列。（2）循环队列（见下页图）将实现队列的数组的首元与末元连接起来。当rear=Maxsize时，如果q[1]有空，下一个元素将加入q[1]。判断队空、队满的条件rear赶上front：队满front赶上rear：队空

第二十二页，共一百一十八页，2022年，8月28日第二十三页，共一百一十八页，2022年，8月28日2.3栈和队列判断条件同为rear=front，怎么办？区别方法：只剩一个空结点时就认为队满。（rear+1）MODMaxsize=front，即少用一个单元区别两种情况。循环队列的运算判空（front=rear）入队判断是否队满→如未满→调整队尾指示器rear→把数据元素插入队尾出队判断是否队空→如未空→调整队首指示器front→取出数据元素。第二十四页，共一百一十八页，2022年，8月28日2.3栈和队列inten_queue(NODEq[],intmaxn,int*tpt,int*hpt,NODEx)//入队函数//设队列结点的数据类型为NODE，用能存储maxn个结点的数组实现{*tpt=(*tpt+1)%maxn;//*tpt队尾位置

if(*tpt==*hpt)//队满，*hpt队首位置

{*tpt=(*tpt-1+maxn)%maxn;//恢复队尾位置*tptreturn1;//进队失败

}q[*tpt]=x;return0；}intde_queue(NODEq[],intmaxn,int*tpt,int*hpt,NODE*cp)//出队函数{if(*hpt==*tpt)return1；//队空*hpt=(*hpt+1)%maxn;*cp=q[*hpt]；

return0;}第二十五页，共一百一十八页，2022年，8月28日2.3栈和队列队列的应用多道程序中的CPU管理在只有一个CPU和内存的条件下，多用户同时使用计算机，需要在他们之间合理分配计算机资源。多用户队列在实现合理分配CPU中起重要作用。缓冲区的设计计算机向外设传送数据时，先把数据送到缓冲区，然后外设依次从缓冲区取数据进行具体操作。第二十六页，共一百一十八页，2022年，8月28日2.4链表链接存储的特点：动态分配存储空间；增删操作不需移动大量元素，不要求连续存储。链表的分类：按链(指针)个数：单链表、双链表、多重链表按指针方向：双向链表、循环链表一、单链表

1、定义链式存储的线性表。第二十七页，共一百一十八页，2022年，8月28日2.4链表结点除信息域外还含有一个指针域，用来指出其后继结点的位置最后一个结点没有后继结点，指针它的指针域为空(记为NIL或∧)。另外还需要设置一个指针head，指向单链表的第一个结点第二十八页，共一百一十八页，2022年，8月28日2.4链表2、单链表的操作插入删除第二十九页，共一百一十八页，2022年，8月28日单链表的算法插入算法三种插入位置分析插入表头：空表，非空表统一修改头指针中间结点或尾结点前：修改中间结点链域尾结点后：修改尾结点链域后两种操作统一第三十页，共一百一十八页，2022年，8月28日单链表删除算法删除第i个结点，i为0～n－1三种删除位置分析删除表头结点：修改头指针删除中间结点或尾结点：修改中间结点链域时间复杂度O（n），用于沿链找删除结点第三十一页，共一百一十八页，2022年，8月28日2.4链表voidinsertList(nodetype**l,nodetype*np,chare)//在单链表的某给定字符节点e后插入新结点，如找不到则查在尾部；np是插入的新结点指针{nodetype*p;// if(*l==NULL)//如链表为空，则把插入结点作为头结点 {np->lp=*l;//把np的指针域设为NULL *l=np;//把np设为头指针 } else {p=*l;//取头指针 while(p->lp!=NULL&&p->elem!=e)//从头指针开始查找e p=p->lp;//向后查找 np->lp=p->lp;//把np指针域指向p的下一节点 p->lp=np;//把p的指针域指向np }}第三十二页，共一百一十八页，2022年，8月28日2.4链表（2）删除算法

voiddeleteList(nodetype**l,chare)//l为链表头指针的指针{if(*l==NULL)return;//空链表，返回

nodetype*p,*q; p=*l;//p用于判断比较

q=NULL;//q用于指向当前结点的前驱结点

while(p!=NULL&&p->elem!=e) {q=p;p=p->lp;}//向后查找并保存前一结点指针

if(p!=NULL)//如果找到e，进行删除操作；如未找到，无操作

if(p==*l)*l=p->lp;//如果删除的是首结点，需修改链表指针

else q->lp=p->lp;//将欲删除结点的链接字段赋给前一结点

deletep;//回收被删除结点的空间}第三十三页，共一百一十八页，2022年，8月28日2.4链表删除算法需要2个检测指针，才能完成删除。一个用来判断比较(p)，一个用来指向当前结点的前驱结点(q)。3、存储池

是由若干可用结点组成的链表。需要的时候，从表的首部取走一个即可，返归的时候也只要将其链接在首部。第三十四页，共一百一十八页，2022年，8月28日2.4链表它是OS存储管理的部分，OS采用某些方式将内存中空闲的部分管理起来。当应用程序申请动态分配存储空间时，存储管理从存储池中分配给用户，当用完后，应用程序释放动态存储空间，由存储管理将其归还存储池中。存储池图中，av是一个全局变量，它指向存储池的第一个可用节点。第三十五页，共一百一十八页，2022年，8月28日2.4链表4、循环链表

循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为“NIL”，而是指向头一个结点，成为一个由链指针链结的环。可达性：从表中任一结点出发都可以找到其他结点，使查找更加灵活，单链表无此特性。第三十六页，共一百一十八页，2022年，8月28日2.4链表5、双向链表单链表只能查找后继结点，不能向前找前驱结点；即使循环链表也是通过先找后继结点才找到前驱结点，为克服这一缺点，引入双向链表。它设有一个指向后继结点的指针和一个指向前驱结点的指针，可方便的直接向前或向后查找。第三十七页，共一百一十八页，2022年，8月28日2.5字符串一、定义字符的有限序列，记为s=‘s1s2…sn’。其中n为串长，当n=0时，s称为空串，记为NULL。二、串基本运算求长度len(s)联结concat(s,t)取子串substr(s,i,j)//从s中取从i到j的子串均以子串和串为单位进行运算，不同于线性表以单个元素为操作对象。第三十八页，共一百一十八页，2022年，8月28日2.5字符串三、串存储方式1、顺序存储将串中字符依次存放在连续的存储空间。几种方式:(1)字节方式(字节编址)：按字节编址的计算机，8位机，一个字节存放一个字符，以特殊字符标志字符串结束，如∧。(2)紧缩格式(字编址)：以字为存取单位，一个字中放多个字符，节省空间，但寻址不便。(3)非紧缩格式(字编址)：一个字中放一个字符，存取方便但浪费空间。第三十九页，共一百一十八页，2022年，8月28日2.5字符串第四十页，共一百一十八页，2022年，8月28日2.5字符串2、链接存储分为单字符结点、多字符结点；多字符结点每个结点的data域存放多个字符；最后一个结点的data域若未放满，应加上特殊字符。第四十一页，共一百一十八页，2022年，8月28日2.5字符串四、串的模式匹配

在主串s中查找子串p，若有则返回串p的起始位置序号，称为串的模式匹配。简单模式匹配s:aaaabc≠p:aab≠第一趟：s3≠p3aab第二趟：s4≠p3

aab第三趟：s5=

p3匹配成功返回位置为3第四十二页，共一百一十八页，2022年，8月28日2.5字符串简单模式匹配的缺点

效率较低。设len(s)=n,len(p)=m,如n»m,显然寻找一个匹配所需要的扫描次数为O(n),而每次扫描进行比较的次数为O(m),所以总的时间花费为O(mn)。为克服上述缺点，提出了KMP算法，其总的时间花费为O(m+n)。利用模式前后子串间的相等关系以及与s的一个字符发生失配的位置来确定在模式的何处继续查找匹配。第四十三页，共一百一十八页，2022年，8月28日2.6树一、树的定义

树是由一个或多个结点组成的有限集合T，满足以下两个条件：1、有一个特定的结点称为根节点；2、其余结点分成n(n≥0)个互不相交的集合T1、T2…

Tn，且每个集合又都是一棵树，称为T的子树。结点的度：一个结点子树的数目。度为0的结点称为叶子；一棵树中结点度的最大值称为树的度。上图，根结点和树的度数都为3。结点的级：结点相对树根所处的层次。结点级的最大值称为树高或树深。(上图E为3级，树高3)第四十四页，共一百一十八页，2022年，8月28日2.6树二、二叉树1、定义二叉树是一个有限的结点集合，该集合或者为空，或者由一个根节点及两棵互不相交的左右二叉子树所组成。二叉树第i级的结点数最多为2i-1深度为k的二叉树结点数最多为2k-1(等比数列)第四十五页，共一百一十八页，2022年，8月28日2.6树2、二叉树的表示方法可使用具有2个指针域的链表，LC为左指针域，指向结点的左子树，RC为右指针域，指向结点的右子树。亦可用数组的下标来模拟指针，即开辟三个一维数组DATA，LC和RC分别存放结点的元素及其左、右指针。第四十六页，共一百一十八页，2022年，8月28日2.6树3、二叉树的遍历遍历：对每个结点访问一次且恰好一次。前序(DLR)、中序(LDR)、后序(LRD)—看根节点的位置。前序遍历算法：若二叉树不空，则：访问根结点；前序遍历左子树；前序遍历右子树。右图前序ABEFCGDHIJ第四十七页，共一百一十八页，2022年，8月28日2.6树后序遍历算法：若二叉树不空，则：后序遍历左子树；后序遍历右子树；访问根结点。后序FEGJIHDCBA中序遍历算法：若二叉树不空，则：中序遍历左子树；访问根结点；中序遍历右子树。中序EFBGCHIJDA第四十八页，共一百一十八页，2022年，8月28日2.6树4、二叉树遍历算法以上三种遍历方法都是递归定义的，故可用递归算法实现。voidpreorder(TNODE*t)//前序遍历，t为根节点指针{if(t!=NULL){ cout<<t->data<<""; preorder(t->llink); preorder(t->rlink);}}第四十九页，共一百一十八页，2022年，8月28日2.6树voidmidorder(TNODE*t)//中序遍历{if(t!=NULL){ midorder(t->llink); cout<<t->data<<"";

midorder(t->rlink);}}第五十页，共一百一十八页，2022年，8月28日2.6树voidposorder(TNODE*t)//后序遍历{ if(t!=NULL) {

posorder(t->llink); posorder(t->rlink); cout<<t->data<<""; }}第五十一页，共一百一十八页，2022年，8月28日由遍历结果求二叉树结构第五十二页，共一百一十八页，2022年，8月28日由遍历结果求二叉树结构第五十三页，共一百一十八页，2022年，8月28日2.6树三、线索二叉树用标准形式存储二叉树时，树中有很多空指针，如何充分利用其提高算法效率？第五十四页，共一百一十八页，2022年，8月28日第五十五页，共一百一十八页，2022年，8月28日2.6树四、树的二叉树表示每一棵都能唯一地转换到它所对应的二叉树转换方法：①凡是兄弟就用线连接起来；②对每个非终端结点，除其最左孩子外，删去该结点与其他孩子结点的连线；③再以根结点为轴心，顺时针旋转450第五十六页，共一百一十八页，2022年，8月28日第五十七页，共一百一十八页，2022年，8月28日2.7图一、图的概念常用G=(V,E)代表一个图，V是结点的有穷集合(非空)，E是边的有穷集合(E可为空集)。若一条边的结点对无序，则称无向图。反之称为有向图。二、常用术语度与结点v相联的边的数目。对有向图，以v为始端的边的数目称为v的出度，以v为末端的边的数目称为v的入度。子图对于一个图G，若存在图G’，且满足v(G’)v(G)，E(G’)E(G)，则称G’为G的子图。第五十八页，共一百一十八页，2022年，8月28日2.7图路径、简单路径在图中，沿E(G)中的边从一个顶点到达另一个顶点所经历的顶点的序列称为从到的一条路径。简单路径是一条路径，除了第一个顶点和最后一个顶点可以相同外，其余都是不同的。连通图、连通分支、强连通图、强连通分支无向图中任何一对顶点相互可达，称为连通图。无向图的最大连通子图称为连通分支。有向图中任何一对顶点相互可达，称为强连通图。有向图的最大强连通子图称为强连通分支。第五十九页，共一百一十八页，2022年，8月28日2.7图加权图边上加权值：表示从一个顶点到达另一个顶点所花费的代价。三、图的存储(常用方法有两种：邻接矩阵和邻接表)1、邻接矩阵若G是一个具有n个结点的图，则G的相邻矩阵是:第六十页，共一百一十八页，2022年，8月28日2.7图

对无向图：

A为对称阵，只要存储一半元素；

A元素之和为图中边数乘2；顶点vi的度为A的第i行或第i列之和。第六十一页，共一百一十八页，2022年，8月28日2.7图

对有向图：

A不具有对称阵，要存储全部元素；

A元素之和为图中边数；顶点vi的出度为A的第i行之和，入度为第i列之和。第六十二页，共一百一十八页，2022年，8月28日2.7图邻接矩阵的缺点时间花费：O(n2)，需对n2-n(对角线为0)个元素进行检查；空间花费：当边数m«n时，A为稀疏矩阵，浪费空间。2、邻接表顺序存储图中顶点+链接存储图中的边。表头元素：表元素：第六十三页，共一百一十八页，2022年，8月28日2.7图例：

每个单链表相当于邻接矩阵中的一行，存放了邻接矩阵中的非0元素；

边少的情况下节省空间。第六十四页，共一百一十八页，2022年，8月28日2.7图四、图的遍历从图中任一顶点出发，访问图中所有顶点，且每个顶点仅被访问一次1、深度优先搜索基本过程是：首先选定一个出发顶点ｖ，并访问之，接着选择一个与ｖ相邻且未访问过的顶点ｗ访问之，再从ｗ开始进行深度优先搜索；每当到达一个所有相邻节点都已访问过的顶点时，就从最近所访问的顶点开始依次回退，并寻找另一个与它相邻且未访问过的顶点u，从u开始深度优先搜索。(方法描述是递归的)注意：每个结点访问后要打上已访问标记，因为图中结点可能有多个前驱，可能被重复访问。对于连通图/强连通图从一个顶点出发可以用dfs遍历整个图。第六十五页，共一百一十八页，2022年，8月28日2.7图2、广度优先搜索基本思想是：从某个结点V出发，访问此结点，再依次访问V邻接的未访问结点u1、u2、u3…um，并标记为已访问过，然后再访问所有ui(1≤i≤m)相邻的但未访问过的结点。直至图中所有被访问过的结点的相邻结点都被访问到。(用队列(FIFO表)来实现)例：假设存在无向图G5第六十六页，共一百一十八页，2022年，8月28日2.7图第六十七页，共一百一十八页，2022年，8月28日2.7图输入边的关系为(9条边)：（0，1），（0，2），（1，3），（1，4），（2，5），（2，6），（3，7），（4，7），（5，6）深度优先搜索遍历的结果序列是：0，2，6，5，1，4，7，3。广度优先遍历结果为：0，2，1，6，5，4，3，7。程序见P63。第六十八页，共一百一十八页，2022年，8月28日2.7图typedefstructnode{ intvno;//顶点序号

structnode*next;//后继邻接顶点}edgenode;intvisited[N];//标记数组typedefedgenode*graph[N];graphg;//指针数组第六十九页，共一百一十八页，2022年，8月28日2.7图voiddfs(graphg,inti)//深度优先搜索，i为起始访问顶点{ edgenode*t; cout<<i<<""; visited[i]=1; t=g[i];//从第i个顶点开始访问,g为存放顶点指针的指针数组

while(t!=NULL)//图非空

{ if(visited[t->vno]==0) dfs(g,t->vno);//从邻接顶点出发深度优先搜索

t=t->next;//考察下一个邻接顶点

}}第七十页，共一百一十八页，2022年，8月28日2.7图voidbfs(graphg,ints,intn)//广度优先搜索，s为起始访问顶点,n为顶点数{ inti,v,w,head,tail; edgenode*t; for(i=0;i<N;i++) visited[i]=0;//置全部顶点都未访问过

head=tail=0;//队列置空

cout<<s<<""; visited[s]=1; queue[tail++]=s;//出发顶点进队

while(head<tail)//队不空循环

{第七十一页，共一百一十八页，2022年，8月28日2.7图 v=queue[head++];//取队列首顶点于v for(t=g[v];t!=NULL;t=t->next)//按邻接表顺序考察与顶点v 邻接的各顶点w { w=t->vno; if(visited[w]==0)//顶点w未被访问过

{ cout<<w<<"";//访问w visited[w]=1;//置w已被访问

queue[tail++]=w;//顶点w进队

} } }}第七十二页，共一百一十八页，2022年，8月28日2.7图五、图的应用1、最小代价生成树生成树设G=(V，E)是一个连通的无向图，若G1是包含G中所有顶点的一个无回路的连通子图，则称G1为G的一棵生成树。最小代价生成树对一个带权的图，在一棵生成树中，各边的权值之和称为这棵生成树的代价。代价最小的生成树称为最小代价生成树。最小代价生成树的结果不唯一，与出发点和遍历方式有关第七十三页，共一百一十八页，2022年，8月28日2.7图求最小代价生成树的Prim算法将图G的顶点集合V分成两部分，一部分是已生成部分的顶点集合u，另一部分是还未生成部分的顶点集合V-u；每一步寻找一条具有最低代价的边(w，r)，且使wu，rV-u；将顶点r并入集合u；当集合u中包含了图中所有顶点，结束。第七十四页，共一百一十八页，2022年，8月28日第七十五页，共一百一十八页，2022年，8月28日第七十六页，共一百一十八页，2022年，8月28日2.7图2、最短路径问题的产生实际应用中需要求某个结点到其他结点的最短路径，如网络通信中的路由选择。最小代价生成树：整体性选择，整体数之和为最小；最短路径：一对一的选择，顶点之间路径上数之和为最小（1）单源最短路径给定带权有向图G和源点v，求从v到G中其余各顶点的最短路径。第七十七页，共一百一十八页，2022年，8月28日2.7图Dijkstra算法：按路径长度的递增次序逐一产生最短路径。即先求最短，次短，……直到全部求出。集合S：存放已求得的最短路径的终点，初始Ｓ={v1}数组Ｄ：D[j]为从v1到vj(vj

S)的只经过S中结点的最短路径长度。初始有边<v1,vj>无边步骤：(1)初始{v1}→S，cost[1,j]→D[j],j=2…n;(2)

第七十八页，共一百一十八页，2022年，8月28日2.7图(3)(4)若S=V,则算法终止，否则转(2)第七十九页，共一百一十八页，2022年，8月28日2.7图例：kSV-SD[2]D[3]D[4]D[5]1{1}{2,3,4,5}10∞30100{1,2}{1,4}{1,5}2{1,2}{3,4,5}6030100{1,2,3}{1,4}{1,5}3{1,2,4}{3,5}5090{1,4,3}{1,4,5}4{1,2,3,4}{5}60{1,4,3,5}5{1,2,3,4,5}{}第八十页，共一百一十八页，2022年，8月28日2.7图kSV-SD[1]D[2]D[3]D[4]D[5]1{0}{1,2,3,4,5}5010∞45∞{0,1}{0,2}{0,4}2{0,2}{1,3,4,5}502545∞{0,1}{0,2,3}{0,4}3{0,2,3}{1,4,5}454528{0,2,3,1}{0,4}{0,2,3,5}4{0,2,3,5}{1,4}4545{0,2,3,1}{0,4}第八十一页，共一百一十八页，2022年，8月28日2.7图intshortestPath(intm[n][n],intn,intv,intdist[n]){//v为起始顶点,n为顶点数//m为图的邻接矩阵

ints[n],i,j,u,min; for(i=0;i<n;i++) { dist[i]=m[v][i];//为各顶点设置初始距离

s[i]=0;//s为标记数组,如某顶点已求得最短路径,则对应位置置1 } s[v]=1;

第八十二页，共一百一十八页，2022年，8月28日2.7图for(i=0;i<n-1;i++)//重复n-1次，每次在V-S中选择一个顶点u，使//dist[u]最短；接着将u加入集合S；最后对每个属于V-S的顶点w，调整v到w的距离。

{ min=MAX_INT; u=-1; for(j=0;j<n;j++) { if(s[j]==0)//选择一个不属于s且具有最短距离的顶点u if(dist[j]!=0&&dist[j]<min) { min=dist[j]; u=j; } }第八十三页，共一百一十八页，2022年，8月28日2.7图 if(u==-1)return0;//不连通的图

s[u]=1;//顶点u置入集合S for(j=0;j<n;j++)//对不属于s的顶点的距离进行调整

{ if(s[j]==0&&m[u][j]<MAX_INT) if(dist[j]>dist[u]+m[u][j]) dist[j]=dist[u]+m[u][j]; } } return1;}第八十四页，共一百一十八页，2022年，8月28日2.7图（2）每对顶点间的最短路径求图中每一对顶点间的最短路径。重复执行Dijkstra算法n次，或采用Floyd算法。第八十五页，共一百一十八页，2022年，8月28日2.7图3、拓扑排序现实中，许多活动或工程都可以划分为若干子活动和子任务，而各任务间可能存在某种制约关系，这就需要确定所有子任务的执行顺序。一个工程的活动可以用AOV(ActivityOnVertex)网表示。第八十六页，共一百一十八页，2022年，8月28日2.7图表示课程间优先关系的有向图

AOV网：有向图，图中各顶点代表活动/任务，各边代表任务间的先后次序关系。拓扑排序获得一个工程的AOV网后，借助计算机计算各自任务的执行顺序的过程。拓扑排序的内容检查网络中是否有回路存在；给出各子任务执行的次序。第八十七页，共一百一十八页，2022年，8月28日2.7图拓扑排序的方法列出图中一个无前驱的顶点；从图中删除该顶点及其所有的出边。重复执行①、②，直至所有顶点都已列出(拓扑排序序列)，或出现有向回路(工程不可行)。v1、v2、v3、v4、v5算法看P71。第八十八页，共一百一十八页，2022年，8月28日2.8查找一、概念查找：是从给定的列表或文件中寻找一个具有指定特征(如具有指定关键字)的元素的过程。根据记录本身的排列情况采用不同的方法，如顺序查找、二分查找和斐波那契查找等。二、顺序查找顺序查找的方法是：用待查关键字值与线性表中各结点的关键字值逐个比较，直到找出相等的关键字值;或找遍所有结点都找不到,即查找失败顺序查找的优点是对线性表结点的逻辑次序无要求,对线性表的存储结构无要求,缺点是平均检索长度长,为n/2算法见书P73第八十九页，共一百一十八页，2022年，8月28日2.8查找三、二分法查找要求线性表结点按关键字码值排好，且以顺序方式存储。用要查找的码值X与中间位置结点的关键码值W相比较：

(1)X=W，此时已经查找成功，查找结束。

(2)X>W,表明X在表的后半部分,取后半部分进行查找

(3)X<W,表明X在表的前半部分，取前半部分进行查找二分法查找的优点是平均检索长度小，为log2n第九十页，共一百一十八页，2022年，8月28日2.8查找例：假定记录个数为15，要查找关键字为262的记录。[3941456981123142157261262275280291292298]3941456981123142157[261262275280291292298]3941456981123142157[261262275]280291292298第九十一页，共一百一十八页，2022年，8月28日2.8查找intbin_search(intk[],intn,intkey)//二分查找{//函数找到返回该节点的下标，找不到返回-1intlow=0,high=n-1,mid;while(low<=high){mid=(low+high)/2;//找中间位置

if(key==k[mid])returnmid;if(key>k[mid])//通过调整查找上、下限，调整查找范围

low=mid+1;elsehigh=mid-1;}return-1;}第九十二页，共一百一十八页，2022年，8月28日2.8查找四、斐波那契查找二分查找采用两均分法对文件进行分割。根据斐波那契序列的特点进行分割，称为斐波那契查找。平均性能比二分查找好，但最坏情况下性能比二分查找差。用得少，不讲。

二分查找和斐波那契查找的基础是，文件记录是有序的，这就需要研究排序算法。第九十三页，共一百一十八页，2022年，8月28日2.9排序一、概念1、排序的定义设有n个记录(R1，R2，…，Rn)，其对应的关键字为(K1，K2，…，Kn)，排序就是求序号(1，2，…，n)的一个排列(P1，P2，…，Pn)使得K1≤K2≤…≤Kn，即得到按关键字有序的序列(RP1，RP2，…，RPn)。2、内排序/外排序内排序：在内存中进行的排序；外排序：数据量大，内存容纳不下，需对外存访问。

下面仅讨论内排序第九十四页，共一百一十八页，2022年，8月28日2.9排序二、插入排序基本思想是：每步将一个待排序的记录，按关键码值的大小插入到前面已排序的适当位置上，直到全部插完止1.直接插入排序：在排好的序列中用顺序法查找插入位置，找到后将其后记录后移一个位置，插入新记录。排序n个记录的文件，关键码比较次数为n2量级，记录移动个数也为n2量级。2.二分法插入排序：在已排好序的序列中使用二分法查找插入位置，找到后移动其后记录插入新记录。关键字比较次数降为nlog2n量级，记录移动个数仍为n2量级。

第九十五页，共一百一十八页，2022年，8月28日2.9排序三、交换排序基本思想是：两两比较待排序记录的关键码，并交换不满足顺序要求的偶对，直至全部满足为止。1、起泡排序设存在一组记录K1，K2，…，Kn，方法：第一趟：K1与K2比较，如K1>K2，则两者交换位置；

K2与K3比较，如K2>K3，则两者交换位置；┇

Kn-1与Kn比较，如Kn-1>Kn，则两者交换位置；

第一趟将最大关键字放在最后。第九十六页，共一百一十八页，2022年，8月28日2.9排序第二趟：对K1，…，Kn-1起泡排序；第i趟：对K1，…，Kn-i+1起泡排序，将最大关键字交换到第n-i+1的位置上；最多n-1趟(逆序的情况下)判断起泡结束的条件：在一趟排序中没有进行过交换元素的操作(设置一个变量)。

例：3902051824523520518245235390（1）排序过程中关键字大的记录18245205235390

（2）好像气泡一样逐渐浮起，所

45182205235390

（3）以称为“起泡排序”

45182205235390

（4）第九十七页，共一百一十八页，2022年，8月28日2.9排序voidsb_sort(inte[],intn)//起泡排序//e[]----存储线性表的数组//n------节点个数//p-----某趟最后进行节点交换的位置，p=0则结束，说明无交换。{ intj,p,h,t; for(h=n-1;h>0;h=p){//最多n-1趟 for(p=j=0;j<h;j++)//每趟两两比较 if(e[j]>e[j+1])//交换位置 { t=e[j]; e[j]=e[j+1]; e[j+1]=t; p=j;//记录交换位置 } }}第九十八页，共一百一十八页，2022年，8月28日2.9排序效率最好：正序序列，只要一趟起泡排序，比较n-1次(Ｏ(n))，交换０次；最坏：逆序序列，需n-1趟起泡排序，比较次数等于交换次数，为Ｏ(n2)因此起泡排序适用于基本有序序列。第九十九页，共一百一十八页，2022年，8月28日2.9排序２、快速排序思路：从序列中选一个分划元素，经过一趟快速排序分成三部分，分划元素前面的元素关键字值≤分划元素的关键字值，分划元素后面的元素关键字值≥分划元素的关键字值，再分别对两个子序列进行快速排序，直至子序列只剩一个元素或不含元素为止。采用递归算法，分划元素一般取序列中第一个元素。第一百页，共一百一十八页，2022年，8月28日2.9排序步骤：(1)选取表中一个元素r[k](一般选第1个元素)，令x=r[k]称为控制关键字；(2)设置两个指示器i，j，分别表示线性表第1个和最后一个元素位置；(3)将j逐渐减小，逐次比较r[j]与x，直到出现一个r[j]<x，然后将r[j]移到r[i]位置；将i逐渐增大，逐次比较r[i]与x，直到出现一个r[i]>x，然后将r[i]移到r[j]位置；直到i=j为止，最后将x移到r[j]位置，完成一趟排序。(4)再分别对两个子序列进行快速排序，直至子序列只剩一个元素或不含元素为止。第一百零一页，共一百一十八页，2022年，8月28日2.9排序例：465513429451770ij

175513429451770ij175513429455570ij17513429455570ij175134294945570ij[1751342]46[945570]ij第一百零二页，共一百一十八页，2022年，8月28日2.9排序[135]17[42]46[7055]94513174246557094第一百零三页，共一百一十八页，2022年，8月28日2.9排序voidr_quick(inte[],intlow,inthigh)//快速排序{//对e[low]至e[high]以e[low]为基准作划分

inti,j,t;//t-----分划元素的关键字值

if(low<high) {//保证输入时low<high i=low;j=high;t=