数据结构n学习.pptx

2.1 2.1 数据结构概述逻辑结构（逻辑结构（4 4种）种）集合结构集合结构、线性结构线性结构(1(1对对1)1)、树型结构、树型结构(1(1对多对多)、图、图/网结构网结构(多对多多对多)存储结构（4种）顺序(连续存储单元)、链接(用指针链接元素)、索引(包含索引表和子表)、散列存储(由散列函数得存储地址)运算 运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。每种逻辑结构都有一个运算集合。常用的运算有检索、插入、删除、更新、排序等。第1页/共112页2.2 2.2 线性表和数组一、线性表的定义线性表的逻辑结构是n个数据元素的有限序列:(a1,a2,a3,an)n为线性表的长度(n0)，n=0的表称为空表数据元素呈线性关系.必存在唯一的称为“第一个”的数据元素;必存在唯一的称为“最后一个”的数据元素；除第一个元素外，每个元素都有且只有一个前驱元素；除最后一个元素外，每个元素都有且只有一个后继元素。所有数据元素ai在同一个线性表中必须是相同的数据类型第2页/共112页2.2 2.2 线性表和数组线性表的基本运算主要有：求表长度检索插入删除修改归并线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表；用链式存储结构存储的线性表称为链表 数组是一种典型的顺序表第3页/共112页2.2 2.2 线性表和数组二、数组1 1、数组的特点均匀性：每个元素占据相同大小的存储空间。静态分配空间，必须预先定义大小。随机存取：下标与值一一对应，每个元素由下标确定位置。2 2、数组的顺序分配 n维数组A=l1u1,l2u2,lnun 元素个数：一维数组存储同构的线性表，要存储n维数组，需将n维下标映射为计算机存储的一维地址第4页/共112页2.2 2.2 线性表和数组n维数组的存储行主排列法：按下标由外至里变化的顺序依次存放于内存(外先变)列主排列法：按下标由里至外变化的顺序依次存放于内存例：二维数组A=1m，1n行主序：列主序：第5页/共112页2.2 2.2 线性表和数组地址计算公式（P44）一维数组二维数组三维数组n维数组三、顺序表(数组)的运算（1 1）插入）插入，在线性表(a1,a2，ai，ai+1，an)的第i个位置插入元素x，算法如下：第6页/共112页2.2 2.2 线性表和数组int sq_insert(list,npt,i,maxn,x)int*list,/线性表首结点指针 *npt,/记录线性表结点数的变量的指针 i,/插入位置 maxn,/线性表可以存储的最大数据元素个数 x;/插入结点值 int k;if(i*npt)return 1;/不合理的插入位置 if(*npt=maxn)return 2;/存储线性表的数组已满 for(k=*npk;ki;k-)listk=listk-1;/第n结点至第i结点后移1个位置 listi=x;/新结点插入 +*npt;/线性表结点数加1 return 0;/插入成功第7页/共112页2.2 2.2 线性表和数组（2 2）删除）删除：在表长为n的线性表(a1,a2,ai-1,a a a ai i i i,ai+1an)中删除第i个数据元素，通常还需将第i+1个至第n个元素向前推动一个位置，即(a1,a2,，ai-1,ai+1，an)，其算法描述如下:int sq_delete(list,npt,i)int*list,/线性表首结点指针 *npt,/记录线性表结点数的变量的指针 i,/删除位置 int k;if(i*npt)return 1;/不合理的删除位置 if(*npt=0)return 2;/线性表已空 for(k=i+1;km或top=maxn)return 1;/栈满，进栈失败返回1 *toppt+；stack*toppt=x;/完成进栈 return 0;/进栈成功返回0int pop(NODE stack,int*toppt,NODE*cp)/弹栈函数 if(*toppt=0)return 1;/栈空，弹栈失败返回1 *cp=stack*toppt;/完成弹栈 *toppt-；return 0;/弹栈成功返回0第12页/共112页2.3 2.3 栈和队列3 3、栈的应用子程序的调用及返回调用时，下一语句地址压栈；返回时，弹栈，获得返回后的执行语句的地址第13页/共112页2.3 2.3 栈和队列表达式计算参数传递递归过程的实现第14页/共112页2.3 2.3 栈和队列二、队列1 1、定义 是一种只许在队首删除元素，在队尾插入元素的先进先出(FIFO)的线性表。2 2、顺序存储队列（1）顺序队列队尾指示器rear指示队尾元素，队头指示器front指示队头元素的前一位置，即队头指针所指的位置是空的。第15页/共112页2.3 2.3 栈和队列入队时，rear+1，加入数据元素；出队时，取出数据元素，front+1；当front=rear时，队列空。存在问题：随着进队和出队操作，front和rear数组尾端，会出现前端空着，而队列空间已用完的情况。为此，引入循环队列。（2）循环队列（见下页图）将实现队列的数组的首元与末元连接起来。当rear=Maxsize时，如果q1有空，下一个元素将加入q1。p判断队空、队满的条件rear赶上front：队满front赶上rear：队空 第16页/共112页第17页/共112页2.3 2.3 栈和队列判断条件同为rear=frontrear=front，怎么办？区别方法：只剩一个空结点时就认为队满。（rear+1）MOD Maxsize=front，即少用一个单元区别两种情况。循环队列的运算判空（front=rear）入队 判断是否队满如未满调整队尾指示器rear把数据元素插入队尾出队 判断是否队空如未空调整队首指示器front取出数据元素。第18页/共112页2.3 2.3 栈和队列int en_queue(NODE q,int maxn,int*tpt,int*hpt,NODE x)/入队函数/设队列结点的数据类型为NODE，用能存储maxn个结点的数组实现 *tpt=(*tpt+1)%maxn;/*tpt队尾位置 if(*tpt=*hpt)/队满，*hpt队首位置 *tpt=(*tpt-1+maxn)%maxn;/恢复队尾位置*tpt return 1;/进队失败 q*tpt=x;return 0；int de_queue(NODE q,int maxn,int*tpt,int*hpt,NODE*cp)/出队函数 if(*hpt=*tpt)return 1；/队空 *hpt=(*hpt+1)%maxn;*cp=q*hpt；return 0;第19页/共112页2.3 2.3 栈和队列队列的应用队列的应用多道程序中的多道程序中的CPUCPU管理管理在只有一个CPU和内存的条件下，多用户同时使用计算机，需要在他们之间合理分配计算机资源。多用户队列在实现合理分配CPU中起重要作用。缓冲区的设计缓冲区的设计计算机向外设传送数据时，先把数据送到缓冲区，然后外设依次从缓冲区取数据进行具体操作。第20页/共112页2.4 2.4 链表链接存储的特点：动态分配存储空间；增删操作不需移动大量元素，不要求连续存储。p链表的分类：按链(指针)个数：单链表、双链表、多重链表按指针方向：双向链表、循环链表一、单链表 1 1、定义 链式存储的线性表。第21页/共112页2.4 2.4 链表结点除信息域外还含有一个指针域，用来指出其后继结点的位置最后一个结点没有后继结点，指针它的指针域为空(记为NIL 或)。另外还需要设置一个指针head，指向单链表的第一个结点第22页/共112页2.4 2.4 链表2 2、单链表的操作插插 入入 删删 除除第23页/共112页单链表的算法插入算法三种插入位置分析插入表头：空表，非空表统一修改头指针中间结点或尾结点前：修改中间结点链域尾结点后：修改尾结点链域后两种操作统一第24页/共112页单链表删除算法删除第i个结点，i为0n1三种删除位置分析删除表头结点：修改头指针删除中间结点或尾结点：修改中间结点链域时间复杂度O（n），用于沿链找删除结点第25页/共112页2.4 2.4 链表void insertList(nodetype*l,nodetype*np,char e)/在单链表的某给定字符节点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)/从头指针开始查找ep=p-lp;/向后查找np-lp=p-lp;/把np指针域指向p的下一节点p-lp=np;/把p的指针域指向np第26页/共112页2.4 2.4 链表（2）删除算法 void deleteList(nodetype*l,char e)/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;/将欲删除结点的链接字段赋给前一结点 delete p;/回收被删除结点的空间第27页/共112页2.4 2.4 链表删除算法需要2个检测指针，才能完成删除。一个用来判断比较(p)，一个用来指向当前结点的前驱结点(q)。3 3、存储池 是由若干可用结点组成的链表。需要的时候，从表的首部取走一个即可，返归的时候也只要将其链接在首部。第28页/共112页2.4 2.4 链表p它是OS存储管理的部分，OS采用某些方式将内存中空闲的部分管理起来。当应用程序申请动态分配存储空间时，存储管理从存储池中分配给用户，当用完后，应用程序释放动态存储空间，由存储管理将其归还存储池中。存储池图中，av是一个全局变量，它指向存储池的第一个可用节点。第29页/共112页2.4 2.4 链表4、循环链表 循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为“NIL”，而是指向头一个结点，成为一个由链指针链结的环。p可达性：从表中任一结点出发都可以找到其他结点，使查找更加灵活，单链表无此特性。第30页/共112页2.4 2.4 链表5、双向链表单链表只能查找后继结点，不能向前找前驱结点；即使循环链表也是通过先找后继结点才找到前驱结点，为克服这一缺点，引入双向链表。它设有一个指向后继结点的指针和一个指向前驱结点的指针，可方便的直接向前或向后查找。第31页/共112页2.5 2.5 字符串一、定义 字符的有限序列，记为s=s1s2sn。其中n为串长，当n=0时，s称为空串，记为NULL。二、串基本运算求长度len(s)联结concat(s,t)取子串substr(s,i,j)/从s中取从i到j的子串l均以子串和串为单位进行运算，不同于线性表以单个元素为操作对象。第32页/共112页2.5 2.5 字符串三、串存储方式1、顺序存储将串中字符依次存放在连续的存储空间。几种方式:(1)字节方式(字节编址)：按字节编址的计算机，8位机，一个字节存放一个字符，以特殊字符标志字符串结束，如。(2)紧缩格式(字编址)：以字为存取单位，一个字中放多个字符，节省空间，但寻址不便。(3)非紧缩格式(字编址)：一个字中放一个字符，存取方便但浪费空间。第33页/共112页2.5 2.5 字符串第34页/共112页2.5 2.5 字符串2 2、链接存储分为单字符结点、多字符结点；多字符结点每个结点的data域存放多个字符；最后一个结点的data域若未放满，应加上特殊字符。第35页/共112页2.5 2.5 字符串四、串的模式匹配 在主串s中查找子串p，若有则返回串p的起始位置序号，称为串的模式匹配。p简单模式匹配s:a a a a b c p:a a b 第一趟：s3 p3 a a b 第二趟：s4 p3 a a b 第三趟：s5=p3匹配成功 返回位置为3第36页/共112页2.5 2.5 字符串简单模式匹配的缺点 效率较低。设 len(s)=n,len(p)=m,如n m,显然寻找一个匹配所需要的扫描次数为O(n),而每次扫描进行比较的次数为O(m),所以总的时间花费为O(mn)。p为克服上述缺点，提出了KMP算法，其总的时间花费为O(m+n)。利用模式前后子串间的相等关系以及与s的一个字符发生失配的位置来确定在模式的何处继续查找匹配。第37页/共112页2.6 2.6 树一、树的定义 树是由一个或多个结点组成的有限集合T，满足以下两个条件：1、有一个特定的结点称为根节点；2、其余结点分成n(n0)个互不相交的集合T1、T2 Tn，且每个集合又都是一棵树，称为T的子树。结点的度：一个结点子树的数目。度为0的结点称为叶子；一棵树中结点度的最大值称为树的度。上图，根结点和树的度数都为3。结点的级：结点相对树根所处的层次。结点级的最大值称为树高或树深。(上图E为3级，树高3)第38页/共112页2.6 2.6 树二、二叉树1 1、定义 二叉树是一个有限的结点集合，该集合或者为空，或者由一个根节点及两棵互不相交的左右二叉子树所组成。二叉树第i级的结点数最多为2i-1深度为k的二叉树结点数最多为2k-1(等比数列)第39页/共112页2.6 2.6 树2 2、二叉树的表示方法 可使用具有2个指针域的链表，LC为左指针域，指向结点的左子树，RC为右指针域，指向结点的右子树。亦可用数组的下标来模拟指针，即开辟三个一维数组DATA，LC和RC分别存放结点的元素及其左、右指针。第40页/共112页2.6 2.6 树3 3、二叉树的遍历遍历：对每个结点访问一次且恰好一次。前序(DLR)、中序(LDR)、后序(LRD)看根节点的位置。前序遍历算法：前序遍历算法：若二叉树不空，则：访问根结点；前序遍历左子树；前序遍历右子树。右图前序ABEFCGDHIJABEFCGDHIJ第41页/共112页2.6 2.6 树 后序遍历算法：后序遍历算法：若二叉树不空，则：后序遍历左子树；后序遍历右子树；访问根结点。后序FEGJIHDCBAFEGJIHDCBA 中序遍历算法：中序遍历算法：若二叉树不空，则：中序遍历左子树；访问根结点；中序遍历右子树。中序EFBGCHIJDAEFBGCHIJDA第42页/共112页2.6 2.6 树4 4、二叉树遍历算法 以上三种遍历方法都是递归定义的，故可用递归算法实现。void preorder(TNODE*t)/前序遍历，t为根节点指针 if(t!=NULL)coutdatallink);preorder(t-rlink);第43页/共112页2.6 2.6 树void midorder(TNODE*t)/中序遍历 if(t!=NULL)midorder(t-llink);coutdatarlink);第44页/共112页2.6 2.6 树void posorder(TNODE*t)/后序遍历if(t!=NULL)posorder(t-llink);posorder(t-rlink);coutdata;第45页/共112页由遍历结果求二叉树结构第46页/共112页由遍历结果求二叉树结构第47页/共112页2.6 2.6 树三、线索二叉树 用标准形式存储二叉树时，树中有很多空指针，如何充分利用其提高算法效率？第48页/共112页第49页/共112页2.6 2.6 树四、树的二叉树表示o每一棵都能唯一地转换到它所对应的二叉树o转换方法：凡是兄弟就用线连接起来；对每个非终端结点，除其最左孩子外，删去该结点与其他孩子结点的连线；再以根结点为轴心，顺时针旋转450第50页/共112页第51页/共112页2.7 2.7 图一、图的概念 常用G=(V,E)代表一个图，V是结点的有穷集合(非空)，E是边的有穷集合(E可为空集)。若一条边的结点对无序，则称无向图。反之称为有向图。二、常用术语度 与结点v相联的边的数目。对有向图，以v为始端的边的数目称为v的出度，以v为末端的边的数目称为v的入度。p子图 对于一个图G，若存在图G，且满足v(G)v(G)，E(G)E(G)，则称G为G的子图。第52页/共112页2.7 2.7 图路径、简单路径在图中，沿E(G)中的边从一个顶点到达另一个顶点所经历的顶点的序列称为从到的一条路径。简单路径是一条路径，除了第一个顶点和最后一个顶点可以相同外，其余都是不同的。p连通图、连通分支、强连通图、强连通分支无向图中任何一对顶点相互可达，称为连通图。无向图的最大连通子图称为连通分支。有向图中任何一对顶点相互可达，称为强连通图。有向图的最大强连通子图称为强连通分支。第53页/共112页2.7 2.7 图加权图边上加权值：表示从一个顶点到达另一个顶点所花费的代价。三、图的存储(常用方法有两种：邻接矩阵和邻接表)1、邻接矩阵若G是一个具有n个结点的图，则G的相邻矩阵是:第54页/共112页2.7 2.7 图 对无向图：对无向图：l A为对称阵，只要存储一半元素；l A元素之和为图中边数乘2；l 顶点vi的度为A的第i行或第i列之和。第55页/共112页2.7 2.7 图 对有向图：对有向图：l A不具有对称阵，要存储全部元素；l A元素之和为图中边数；l 顶点vi的出度为A的第i行之和，入度为第i列之和。第56页/共112页2.7 2.7 图邻接矩阵的缺点时间花费：O(n2)，需对n2-n(对角线为0)个元素进行检查；空间花费：当边数mn时，A为稀疏矩阵，浪费空间。2、邻接表p顺序存储图中顶点+链接存储图中的边。表头元素：表元素：第57页/共112页2.7 2.7 图例：l 每个单链表相当于邻接矩阵中的一行，存放了邻接矩阵 中的非0元素；l 边少的情况下节省空间。第58页/共112页2.7 2.7 图四、图的遍历从图中任一顶点出发，访问图中所有顶点，且每个顶点仅被访问一次1、深度优先搜索基本过程是：首先选定一个出发顶点，并访问之，接着选择一个与相邻且未访问过的顶点访问之，再从开始进行深度优先搜索；每当到达一个所有相邻节点都已访问过的顶点时，就从最近所访问的顶点开始依次回退，并寻找另一个与它相邻且未访问过的顶点u，从u开始深度优先搜索。(方法描述是递归的)l注意：每个结点访问后要打上已访问标记，因为图中结点可能有多个前驱，可能被重复访问。l对于连通图/强连通图从一个顶点出发可以用dfs遍历整个图。第59页/共112页2.7 2.7 图2、广度优先搜索基本思想是：从某个结点V出发，访问此结点，再依次访问V邻接的未访问结点u1、u2、u3 um，并标记为已访问过，然后再访问所有ui(1im)相邻的但未访问过的结点。直至图中所有被访问过的结点的相邻结点都被访问到。(用队列(FIFO表)来实现)例：假设存在无向图G5第60页/共112页2.7 2.7 图第61页/共112页2.7 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。第62页/共112页2.7 2.7 图typedef struct nodeint vno;/顶点序号struct node*next;/后继邻接顶点 edgenode;int visitedN;/标记数组typedef edgenode*graphN;graph g;/指针数组第63页/共112页2.7 2.7 图void dfs(graph g,int i)/深度优先搜索，i为起始访问顶点edgenode*t;coutivno=0)dfs(g,t-vno);/从邻接顶点出发深度优先搜索t=t-next;/考察下一个邻接顶点第64页/共112页2.7 2.7 图void bfs(graph g,int s,int n)/广度优先搜索，s为起始访问顶点,n为顶点数int i,v,w,head,tail;edgenode*t;for(i=0;iN;i+)visitedi=0;/置全部顶点都未访问过head=tail=0;/队列置空couts;visiteds=1;queuetail+=s;/出发顶点进队while(headnext)/按邻接表顺序考察与顶点v 邻接的各顶点ww=t-vno;if(visitedw=0)/顶点w未被访问过coutw;/访问wvisitedw=1;/置w已被访问queuetail+=w;/顶点w进队第66页/共112页2.7 2.7 图五、图的应用1、最小代价生成树l生成树设G=(V，E)是一个连通的无向图，若G1是包含G中所有顶点的一个无回路的连通子图，则称G1为G的一棵生成树。l最小代价生成树对一个带权的图，在一棵生成树中，各边的权值之和称为这棵生成树的代价。代价最小的生成树称为最小代价生成树。最小代价生成树的结果不唯一，与出发点和遍历方式有关第67页/共112页2.7 2.7 图求最小代价生成树的Prim算法将图G的顶点集合V分成两部分，一部分是已生成部分的顶点集合u，另一部分是还未生成部分的顶点集合V-u；每一步寻找一条具有最低代价的边(w，r)，且使w u，r V-u；将顶点r并入集合u；当集合u中包含了图中所有顶点，结束。第68页/共112页第69页/共112页第70页/共112页2.7 2.7 图2、最短路径p问题的产生 实际应用中需要求某个结点到其他结点的最短路径，如网络通信中的路由选择。最小代价生成树：整体性选择，整体数之和为最小；最短路径：一对一的选择，顶点之间路径上数之和为最小（1）单源最短路径 给定带权有向图G和源点v，求从v到G中其余各顶点的最短路径。第71页/共112页2.7 2.7 图Dijkstra算法：按路径长度的递增次序逐一产生最短路径。即先求最短，次短，直到全部求出。集合S：存放已求得的最短路径的终点，初始=v1数组：Dj为从v1到vj(vjS)的只经过S中结点的最短路径长度。初始有边无边步骤：(1)初始v1S，cost1,jDj,j=2n;(2)第72页/共112页2.7 2.7 图(3)(4)若S=V,则算法终止，否则转(2)第73页/共112页2.7 2.7 图例：k SV-SD2D3D4D51 12,3,4,510301001,21,41,52 1,23,4,560301001,2,31,41,53 1,2,43,550901,4,31,4,54 1,2,3,45601,4,3,55 1,2,3,4,5第74页/共112页2.7 2.7 图k k S SV-SV-SD1D1D2D2D3D3D4D4 D5D51 1 001,2,3,1,2,3,4,54,55050101045450,10,10,20,2 0,0,442 2 0,0,221,3,4,1,3,4,555050252545450,10,10,2,0,2,330,0,443 3 0,0,2,32,3 1,4,1,4,554545454528280,2,0,2,3,13,10,0,440,2,0,2,3,53,54 4 0,0,2,3,2,3,551,41,4454545450,2,0,2,3,13,10,0,44第75页/共112页2.7 2.7 图int shortestPath(int mnn,int n,int v,int distn)/v为起始顶点,n为顶点数/m为图的邻接矩阵int sn,i,j,u,min;for(i=0;in;i+)disti=mvi;/为各顶点设置初始距离si=0;/s为标记数组,如某顶点已求得最短路径,则对应位置置1sv=1;第76页/共112页2.7 2.7 图for(i=0;in-1;i+)/重复n-1次，每次在V-S中选择一个顶点u，使/distu最短；接着将u加入集合S；最后对每个属于V-S的顶点w，调整v到w的距离。min=MAX_INT;u=-1;for(j=0;jn;j+)if(sj=0)/选择一个不属于s且具有最短距离的顶点u if(distj!=0&distjmin)min=distj;u=j;第77页/共112页2.7 2.7 图if(u=-1)return 0;/不连通的图su=1;/顶点u置入集合Sfor(j=0;jn;j+)/对不属于s的顶点的距离进行调整if(sj=0&mujdistu+muj)distj=distu+muj;return 1;第78页/共112页2.7 2.7 图（2）每对顶点间的最短路径 求图中每一对顶点间的最短路径。重复执行Dijkstra算法n次，或采用Floyd算法。第79页/共112页2.7 2.7 图3、拓扑排序 现实中，许多活动或工程都可以划分为若干子活动和子任务，而各任务间可能存在某种制约关系，这就需要确定所有子任务的执行顺序。一个工程的活动可以用AOV(Activity On Vertex)网表示。第80页/共112页2.7 2.7 图表示课程间优先关系的有向图p AOV网：有向图，图中各顶点代表活动/任务，各边代表任务间的先后次序关系。p 拓扑排序获得一个工程的AOV网后，借助计算机计算各自任务的执行顺序的过程。p 拓扑排序的内容 检查网络中是否有回路存在；给出各子任务执行的次序。第81页/共112页2.7 2.7 图拓扑排序的方法列出图中一个无前驱的顶点；从图中删除该顶点及其所有的出边。重复执行、，直至所有顶点都已列出(拓扑排序序列)，或出现有向回路(工程不可行)。v1、v2、v3、v4、v5算法看P71。第82页/共112页2.8 2.8 查找一、概念查找：是从给定的列表或文件中寻找一个具有指定特征(如具有指定关键字)的元素的过程。根据记录本身的排列情况采用不同的方法，如顺序查找、二分查找和斐波那契查找等。二、顺序查找顺序查找的方法是：用待查关键字值与线性表中各结点的关键字值逐个比较，直到找出相等的关键字值;或找遍所有结点都找不到,即查找失败顺序查找的优点是对线性表结点的逻辑次序无要求,对线性表的存储结构无要求,缺点是平均检索长度长,为n/2算法见书P73第83页/共112页2.8 2.8 查找三、二分法查找要求线性表结点按关键字码值排好，且以顺序方式存储。用要查找的码值X与中间位置结点的关键码值W相比较：(1)X=W，此时已经查找成功，查找结束。(2)XW,表明X在表的后半部分,取后半部分进行查找(3)XW,表明X在表的前半部分，取前半部分进行查找二分法查找的优点是平均检索长度小，为log2n第84页/共112页2.8 2.8 查找例：假定记录个数为15，要查找关键字为262的记录。39 41 45 69 81 123 142 157 261 262 275 280 291 292 29839 41 45 69 81 123 142 157 261 262 275 280 291 292 29839 41 45 69 81 123 142 157 261 262 275 280 291 292 298第85页/共112页2.8 2.8 查找int bin_search(int k,int n,int key)/二分查找/函数找到返回该节点的下标，找不到返回-1 int low=0,high=n-1,mid;while(lowkmid)/通过调整查找上、下限，调整查找范围 low=mid+1;else high=mid-1;return-1;第86页/共112页2.8 2.8 查找四、斐波那契查找p二分查找采用两均分法对文件进行分割。根据斐波那契序列的特点进行分割，称为斐波那契查找。p平均性能比二分查找好，但最坏情况下性能比二分查找差。p用得少，不讲。二分查找和斐波那契查找的基础是，文件记录是有序的，这就需要研究排序算法。第87页/共112页2.9 2.9 排序一、概念1、排序的定义设有n个记录(R1，R2，Rn)，其对应的关键字为(K1，K2，Kn)，排序就是求序号(1，2，n)的一个排列(P1，P2，Pn)使得K1K2 Kn，即得到按关键字有序的序列(RP1，RP2，RPn)。2、内排序/外排序l内排序：在内存中进行的排序；l外排序：数据量大，内存容纳不下，需对外存访问。下面仅讨论内排序第88页/共112页2.9 2.9 排序二、插入排序基本思想是：每步将一个待排序的记录，按关键码值的大小插入到前面已排序的适当位置上，直到全部插完止1.直接插入排序：在排好的序列中用顺序法查找插入位置，找到后将其后记录后移一个位置，插入新记录。排序n个记录的文件，关键码比较次数为n2量级，记录移动个数也为n2量级。2.二分法插入排序：在已排好序的序列中使用二分法查找插入位置，找到后移动其后记录插入新记录。关键字比较次数降为nlog2n量级，记录移动个数仍为n2量级。第89页/共112页2.9 2.9 排序三、交换排序基本思想是：两两比较待排序记录的关键码，并交换不满足顺序要求的偶对，直至全部满足为止。1、起泡排序 设存在一组记录K1，K2，Kn，l方法：第一趟：K1与K2比较，如K1K2，则两者交换位置；K2与K3比较，如K2K3，则两者交换位置；Kn-1与Kn比较，如Kn-1Kn，则两者交换位置；第一趟将最大关键字放在最后。第90页/共112页2.9 2.9 排序第二趟：对K1，Kn-1起泡排序；第i趟：对K1，Kn-i+1起泡排序，将最大关键字交换到第n-i+1的位置上；最多n-1趟(逆序的情况下)l判断起泡结束的条件：在一趟排序中没有进行过交换元素的操作(设置一个变量)。例：390 205 182 45 235 205 182 45 235 390（1）排序过程中关键字大的记录182 45 205 235 390（2）好像气泡一样逐渐浮起，所 45 182 205 235 390（3）以称为“起泡排序”45 182 205 235 390（4）第91页/共112页2.9 2.9 排序void sb_sort(int e,int n)/起泡排序/e-存储线性表的数组/n-节点个数/p-某趟最后进行节点交换的位置，p=0则结束，说明无交换。int j,p,h,t;for(h=n-1;h0;h=p)/最多n-1趟for(p=j=0;jej+1)/交换位置t=ej;ej=ej+1;ej+1=t;p=j;/记录交换位置第92页/共112页2.9 2.9 排序l效率最好：正序序列，只要一趟起泡排序，比较n-1次(n)，交换次；最坏：逆序序列，需n-1趟起泡排序，比较次数等于交换次数，为(n2)l因此起泡排序适用于基本有序序列。第93页/共112页2.9 2.9 排序、快速排序l思路：从序列中选一个分划元素，经过一趟快速排序分成三部分，分划元素前面的元素关键字值分划元素的关键字值，分划元素后面的元素关键字值分划元素的关键字值，再分别对两个子序列进行快速排序，直至子序列只剩一个元素或不含元素为止。l采用递归算法，分划元素一般取序列中第一个元素。第94页/共112页2.9 2.9 排序步骤：(1)选取表中一个元素rk(一般选第1个元素)，令x=rk称为控制关键字；(2)设置两个指示器i，j，分别表示线性表第1个和最后一个元素位置；(3)将j逐渐减小，逐次比较rj与x，直到出现一个rjx，然后将ri移到rj位置；直到i=j为止，最后将x移到rj位置，完成一趟排序。(4)再分别对两个子序列进行快速排序，直至子序列只剩一个元素或不含元素为止。第95页/共112页2.9 2.9 排序例：46 55 13 42 94 5 17 70 i j 17 55 13 42 94 5 17 70 i j17 55 13 42 94 5 55 70 i j17 5 13 42 94 5 55 70 i j17 5 13 42 94 94 55 70 i j17 5 13 42 46 94 55 70 i j第96页/共112页2.9 2.9 排序13 5 17 42 46 70 55 94 5 13 17 42 46 55 70 94第97页/共112页2.9 2.9 排序void r_quick(int e,int low,int high)/快速排序/对elow至ehigh以elow为基准作划分int i,j,t;/t-分划元素的关键字值if(lowhigh)/保证输入时lowhighi=low;j=high;t=elow;while(ij)while(it)j-;/从右侧寻找违反位置if(ij)ei+=ej;/将rj移到ri位置while(ij&ei=t)i+;/从左侧寻找违反位置if(ij)ej-=ei;/将ri移到rj位置 第98页/共112页2.9 2.9 排序 ei=t;r_quick(e,low,i-1);/递归，对左子序列做划分r_quick(e,i+1,high);/递归，对右子序列做划分第99页/共112页2.9 2.9 排序l效率平均计算时间为O(nlog2n)，在所有内排序方法中，就平均计算时间来说，是最佳的一种。第100页/共112页2.9 2.9 排序四、合并排序、基本运算：把两个或多个有序序列合并成一个有序序列，称为合并过程。、两路合并过程方法：比较两个有序序列中的最小元素，输出其中较小者；重复此过程，直到只剩下一个序列，并将其输出为止。第101页/共112页2.9 2.9 排序例：合并(5,25,55)和(10,20,30)第102页/共112页2.9 2.9 排序3、合并排序l方法：首先把输入序列分成长度为的n个子序列，合并相邻子序列，得到n/2个有序子序列(长度为)合并相邻子序列只剩一个长度为n的序列为止。(除最后一个序列，所有序列都有相同长度)l效率O(nlog2n)，较高，缺陷是需要较大的文件缓存区。第103页/共112页2.9 2.9 排序五、堆排序(一种选择排序)、堆的定义将一个具有n个记录R1,Rn的文件看作一株具有n个结点的近似完全二叉树，若每个结点关键字的值其子女关键字的值，该近似完全二叉树便是一个堆。显然，在一个堆中，根结点的关键字具有最大的值。第104页/共112页2.9 2.9 排序(R1,R2,Rn)(R1,R2,Rn)第一个记录为根结点；第i个记录的父结点是第i/2个记录；左子结点是第2i个记录；右子结点是第2i+1个记录；Ki/2Ki(1in)第105页/共112页2.9 2.9 排序 建堆方法：从最后一个非叶子结点开始，与其左右子结点值进行比较，若不满足堆的条件，则与其子结点中大者进行交换，直到所有子树都满足堆为止。例：p94第106页/共112页第107页/共112页2.9 2.9 排序、堆排序思路例：p95,最坏情况下，时间复杂度为O(nlog2n),但建堆时间较长。第108页/共112页2.9 2.9 排序void sift(int e,int n,int s)/渗透函数/e-存储节点序列/n-序列的节点个数/s-对es作渗透，其中es的左右子树是堆int t,k,j;t=es;k=s;j=2*k+1;/ek是ej和ej+1的父节点 while(jn)/未渗透到叶节点if(jn-1&ejej+1)/j=n-1时ej+1不存在 j+;/使ej中存放的是ek较大的子节点if(t=0;i-)sift(e,n,i);/建初始堆 for(k=n-1;k=1;k-)t=e0;/根节点与堆的末节点交换，t中间变量e0=ek;ek=t;sift(e,k,0);/重新建堆第111页/共112页感谢您的观看。第112页/共112页