复旦大学软件工程考研(MSE)数据结构复习资料(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,数据结构,2016MSE,考研冲刺,1,课程安排,课程介绍,栈、队列和向量,树,查找,排序,图,2,课程目的,（以最小代价）通过考试！,不是成为专家,不是初学授课,3,试题结构,考试满分,60,分,考试题型：问答、分析、编程,4,样题问答和编程题,插入排序、选择排序、冒泡排序、快速排序中最快的排序方法是,_,试论述什么叫,Hash,冲突,及有那些处理方法,编程实现对二叉树所有节点的统计,5,课程安排,课程介绍,栈、队列和向量,树,查找,排序,图,6,链表、栈和队列,大纲描述：,单链表,双向链表,环形链表,带哨兵节点的链表,栈的基本概念和性质,栈,ADT,及其顺序,链接实现,;,栈的应用,;,栈与递归,;,队列的基本概念和性质,队列,ADT,及其顺序,链接实现,;,队列的应用,;,向量基本概念和性质,;,向量,ADT,及其数组、链接实现,;,7,线性表基本概念和性质,线性表,是,n,个数据元素的有限序列,常见线性表包括数组、链表、栈、队列等,线性表的两种实现方式,顺序,链式,对比：插入（有序、无序）、删除、查找、读取,8,环形链表,环形链表,又称循环列表，是另一种形式的链式存储结构。它的特点是表中最后一个元素的指针域指向头结点,9,栈的基本概念和性质,栈：,栈是限定仅在表尾进行插入和删除操作的线性表,后进先出特性（,LIFO,）,栈顶、栈底、出栈、入栈,10,例题,设有一个栈,S,，元素,S1,S2,S3,S4,S5,S6,依次进栈，如果,6,个元素的出栈顺序为,S2,S3,S4,S6,S5,S1,，则栈的容量至少应为多少？,答案：,3,11,栈的基本概念和性质,设计递归问题的非递归算法一般需要用到栈机制,三个数,a,、,b,、,c,进栈，不可能出现,c,、,a,、,b,顺序出栈,12,例题,若某栈的输入序列为,a,、,b,、,c,，则所有可能的出栈序列有,_,种，所有不可能的出栈序列有,_,种。,答案：,5,，,1,13,例题,若栈的输入序列为,1,2,3,4,，则,是不可能的栈输出序列之一。,答案：,4,，,3,，,1,，,2,14,习题,若某栈的输入序列为,a,、,b,、,c,、,d,，则所有可能的出栈序列有,_,种，所有不可能的出栈序列有,_,种。,请写出所有可能的序列和不可能的序列。,15,栈的应用,数制转换,十进制数字与,d,进制数字的转换,N=(N div d)d+N mod d,其中,div,为整除，,mod,为求余。,算法：,将算法,3.1,中,8,换成,d,16,例题,十进制数,1167,等于八进制数,？,答案：,2217,思路：,计算方法：除余倒排法,验证方法：指数相加法,17,习题,十进制数,1167,等于七进制数,？,18,栈的应用,表达式求值,：,中缀表达式转后缀表达式,后缀表达式求值,三种表达式：,前缀表达式,+a b,中缀表达式,a+b,后缀表达式,a b+,19,例题,中缀表达式,a+b c d,转为后缀表达式是,？,答案：,a b c,d,20,例题,中缀表达式（,a+b,）,c d,转为后缀表达式是,？,答案：,a b,cd,思路：,数字位序不变，运算符位置改变,后缀表达式无括号，运算顺序同中缀表达式,21,习题,中缀表达式,A-(B+C)*D/E,的后缀形式是,_,。,22,练习,中缀表达式,a*(b+c)/d,转为后缀表达式是,？,23,例题,计算后缀表达式,1 2+4*2/,的值为,？,答案：,6,思路：,顺序计算,或 转换为中缀表达式计算,24,习题,计算后缀表达式,3 2,4*2/3,的值为,？,25,递归,一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数,优点：结构清晰、程序易读、正确性容易得到证明,缺点：效率相对较低,26,队列的基本概念和性质,队列：,队列是限定仅在表的一头进行插入、另一头进行删除操作的线性表,先进先出特性（,FIFO,）,队尾、队头、入队、出队,27,例题,在初始为空的队列中插入元素,a,b,c,d,以后，紧接着作了两次删除操作，此时的队头元素是,，队尾元素是,。,答案：,c,，,d,28,双向队列,双向队列：,亦称双端队列（,Deque,）,是限定插入和删除操作在表的两端进行的线性表,可以用于包装产生栈和队列,29,课程安排,课程介绍,栈、队列和向量,树,查找,排序,图,30,树,大纲描述：,树的基本概念和术语；树的前序、中序、后序、层次序遍历；,二叉树及其性质；普通树与二叉树的转换；,树的存储结构,标准形式,;,完全树,(complete tree),的数组形式存储,;,树的应用，,Huffman,树。,31,树的基本概念和术语,树：,是,n,（,n,0,）个结点的有限集,在任意一棵非空树中：,有且仅有一个特定的称为根的结点,当,n1,时，其余结点可以分为,m,（,m0,）个互不相交的有限集，其中每个集合本身又是一棵树，并且称为根的子树,树属于层次结构数据结构,32,树的基本概念和术语,节点,标签,父节点、子节点、兄弟节点、祖先节点、子孙节点,路径、树枝,根、叶子,次数,内部节点、外部节点,树的次数、,K,次树,节点层次、树的高度和深度,子树,有序树、无序树,森林、果园,33,例题,34,例题,列出如上图所示树的所有叶子结点,答案：,K,L,F,G,M,I,J,列出如上图所示树的所有分支结点,答案：,A,B,C,D,E,H,树,A,为几次树？子树,B,呢？,答案：,3,，,2,前页图所示树的高度为多少？,答案：,4,35,树的基本概念和术语,如果将树中结点的各子树看作从左到右有序的,则该树为,有序树,(ordered tree),否则为无序树。,森林,(forest),是,m,棵互不相交的树的集合。,如果把一棵树的根砍去，剩下的部分就是森林。,如果原来的树是有序的,则砍去根后的森林也是有序的,此时称该森林为有序森林或果园。,36,二叉树及其性质,二叉树（,Binary Tree,）,另一种树形结构，特点是每个结点至多只有二棵子树，且子树有左右之分，其次序不能任意颠倒,二叉树可能的五种基本形态,37,二叉树及其性质,在二叉树的第,i,层上至多有,2,i,1,个结点（,i,1,）,38,例题,一棵二叉树第五层上至多有多少个结点？至少多少？,答案：,16,，,1,39,二叉树及其性质,深度为,k,的二叉树至多有,2,k,1,个结点（,k1,）,40,例题,深度为,n(n0),的二叉树最多有,_,个结点。,答案：,2,n,-1,41,例题,一棵深度为,5,的二叉树至多有多少个结点？至少多少？,答案：,31,，,5,42,例题,高度为,h(h0),的二叉树最少有,_,个结点？,答案：,h,43,二叉树及其性质,对于任何二叉树,如果叶子节点数为,n,0,度为,2,的节点数为,n,2,则,n,0,=n,2,+1,44,例题,在一棵二叉树中有,n,0,个叶结点，有,n,2,个度为,2,的结点，则,n,2,=_,。,答案：,n,0,1,45,例题,若一棵二叉树有,10,个叶结点，则该二叉树中度为,2,的结的点个数为,_,。,答案：,9,46,例题,若一二叉树有,2,度结点,100,个，则其叶结点有多少个？,答案：,101,47,例题,若二叉树中度为,2,的结点有,15,个，度为,1,的结点有,10,个，共有多少个结点？,答案：,41,48,例题,在一棵度为,3,的树中，度为,3,的结点有,2,个，度为,2,的结点有,1,个，度为,1,的结点有,2,个，那么，该树有,_,个叶结点。,答案：,6,构造法,49,二叉树及其性质,满二叉树：,一棵深度为,k,且有,2,k,1,个结点的二叉树,可以对满二叉树的结点进行连续编号，约定编号从根开始，自上而下，自左而右。,完全二叉树：,深度为,k,的，有,n,个结点的二叉树，当且仅当其每一个结点都与深度为,k,的满二叉树中编号从,1,到,n,的结点一一对应时，称为完全二叉树。,50,二叉树及其性质,完全二叉树特点：,叶子结点只可能出现在层次最大的两层上,对任一结点，若其右分支下子孙的最大层次为,l,，其左下分支的子孙的最大层次必为,l,或者,l,1,。,深度为,k,的完全二叉树第,k,层最少,1,个结点，最多,2,k-1,-1,个结点；整棵树最少,2,k-1,个结点，最多,2,k,-2,个结点,51,例题,若某完全二叉树的深度为,h,，则该完全二叉树中至少有,_,个结点。,答案：,2,h-1,52,例题,若深度为,6,的完全二叉树的第,6,层有,3,个叶结点，则该二叉树一共有,_,个结点。,答案：,2,5,-1+3,34,53,例题,一个具有,767,个结点的完全二叉树，其叶子结点个数为,_,。,答案：,384,分析：可以根据公式进行推导，假设,n,0,是度为,0,的结点总数（即叶子结点数），,n,1,是度为,1,的结点总数，,n,2,是度为,2,的结点总数，由二叉树的性质可知：,n,0,n,2,1,，则,n=n,0,n,1,n,2,（其中,n,为完全二叉树的结点总数），由上述公式把,n,2,消去得：,n=2n,0,+n,1,1,，由于完全二叉树中度为,1,的结点数只有两种可能,0,或,1,，由此得到,n,0,（,n,1,）,/2,或,n,0,n/2,，合并成一个公式：,n,0,（,n,1,）,/2,，就可根据完全二叉树的结点总数计算出叶子结点数。本题计算得：,384,。,54,二叉树及其性质,具有,n,个结点的完全二叉树的深度为,log,2,n+1,55,例题,具有,2000,个结点的二叉树，其深度至少为,_,。,答案：,11,56,二叉树及其性质,如果含有,n,1,个节点的,二叉树的高度为,log,2,n,1,将其所有结点按层次序编号,则对于任一节点,j(1,j,n),有,如果,j=1,则节点,j,是树的根,无双亲,;,如果,j1,则其父节点,parent(j),是节点,j/2,如果,2jn,则节点,j,无左子节点,;,否则其左子节点为,2j,如果,2j+1n,则节点,j,无右子节点,;,否则其右子节点为,2j+1,证明,57,完全树的数组形式存储,完全树的数组形式存储算法,将其编号为,i,的结点元素存储在一维数组下标为,i,1,的分量中,58,例题,已知数组,20,30,19,87,30,40,表示一棵完全二叉树，请画出该树。,59,练习答案,60,树的遍历,树的遍历,按某种搜索路径巡访树中每个结点，使每个结点均被访问一次仅且一次,二叉树的遍历可分为前序、中序、后序、层次序等,普通树的遍历可以分为先根、后根、层次序等,61,树的遍历,二叉树的遍历,前序、中序、后序定义,层次序：从上而下，从左至右,常见问题,已知树写遍历结果,已知遍历结果画树,依据：二叉树的前序和中序遍历可以唯一确定一棵二叉树,思路：前序定根，中序定左右,递归和非递归算法实现,62,例题,写出左图所示二叉树的前序、中序、后序、层次序遍历结果,63,例题答案,前序：,ABDCEFG,中序：,DBAECFG,后序：,DBEGFCA,层次序：,ABCDEFG,64,例题,假设一棵二叉树的前序遍历为,EBADCHGFIKJ,，中序遍历为,ABCDEFGHIJK,，请画出该树。,65,例题答案,66,树的遍历,普通树的遍历,前根：先遍历根结点，再依次前根遍历各棵子树,后根：先后根遍历各课子树，再遍历根结点,已知树写遍历结果,已知遍历结果画树,思路：先根定根，后根定子树,67,例题,写出如右图所示树的先根、后根、层次序遍历结果,68,例题答案,前序：,ABECFGHD,后序：,EBFHGCDA,层次序：,ABCDEFGH,69,练习,给出如图所示树的先根、后根和层次序遍历结果,70,练习答案,前根：,ABEFHIGCJKLDMNOQP,后根：,EHIFGBKLJCNQOPMDA,层次序：,ABCDEFGJMHIKLNOPQ,71,例题,画出和下列已知序列对应的树,T,：,树的先根次序访问序列为,GFKDAIEBCHJ,树的后根次序访问序列为,DIAEKFCJHBG,72,例题答案,73,普通树与二叉树的转换,对于任意,k,次树到相应二叉树的转换算法,对于具有子节点,n,1,n,2,n,k,的节点,n,将,n,1,作为其左子节点,且,k,j+1,作为,k,j,(1,j,k-1),的右子节点,思路：“,不同层在左，同层在右,”,74,普通树与二叉树的转换,对于任意森林到相应二叉树的转换算法为,设,T=(T,1,T,2,.T,m,),为,m(m,0,),棵树的序列,而,BT(T,1,T,2,.T,m,),为相应的二叉树,则,如果,m=0,则,BT,为空树,如果,m0,则,T,1,的根节点就是,BT,的根节点,而,BT,的左子树是,T,1,的子树,T,11,T,12,T,1K,转换成的,BT,l,(T,11,T,12,T,1K,),其右子树为,BT,r,(T,2,.T,m,),75,例题,将下页图所示森林转换为等价的二叉树,76,例题,77,例题答案,78,练习,将如图所示树转换为二叉树,79,练习答案,80,Huffman,树,Huffman,树：,又称最优树，是一类带权路径长度最短的树,基本概念：,树的路径长度：从根到每一结点的路径长度之和。,结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。,树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记做,WPL,。,81,Huffman,树,基本概念：,假设有,n,个权值,w,i,，试构造一棵有,n,个叶子结点的二叉树，每个叶子的结点带权为,w,i,，则其中,WPL,最小的二叉树称为最优二叉树或赫夫曼树,算法,见下页,82,Huffman,算法,(1),由给定的,n,个权值,w,0,w,1,w,2,w,n-1,，构造具有,n,棵二叉树的集合,F,=,T,0,T,1,T,2,T,n-1,，其中每一棵二叉树,T,i,只有一个带有权值,w,i,的根结点，其左、右子树均为空。,(2),在,F,中选取两棵根结点的权值最小的二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。,(3),在,F,中删去这两棵二叉树，加入新得的树。,(4),重复,(2)(3),，直到,F,只含一棵树为止。这棵树就是赫夫曼树,83,Z,K,F,C,U,D,L,E,2,7,24,32,37,42,42,120,2,Z,7,K,24,F,32,C,37,U,42,D,42,L,120,E,Step 1,2,Z,7,K,24,F,32,C,37,U,42,D,42,L,120,E,9,2,Z,7,K,24,F,32,C,37,U,42,D,42,L,120,E,9,33,Round 1,Round 2,例题,84,2,Z,7,K,24,F,32,C,37,U,42,D,42,L,120,E,9,33,65,Round 3,85,2,Z,7,K,24,F,32,C,37,U,42,D,42,L,120,E,9,33,65,79,Round 4,86,2,Z,7,K,24,F,32,C,37,U,42,D,42,L,120,E,9,33,65,79,107,Round 5,87,2,Z,7,K,24,F,32,C,37,U,42,D,42,L,120,E,9,33,65,79,107,186,Round 6,88,2,Z,7,K,24,F,32,C,37,U,42,D,42,L,120,E,9,33,65,79,107,186,306,Round 7,(final),89,Huffman,编码,编码：等长编码,/,不等长编码,前缀编码：若要设计长短不等的编码，则必须是任一个字符的编码抖不是另一个字符编码的前缀，这种编码叫做前缀编码,Huffman,编码：以,n,种字符出现的频率做权，设计一棵赫夫曼树，由此得到的前缀编码称为,Huffman,编码,90,例题,Letter,Freq,Code,Bits,C,32,1110,4,D,42,101,3,E,120,0,1,F,24,11111,5,K,7,111101,6,L,42,110,3,U,37,100,3,Z,2,111100,6,2,Z,7,K,24,F,32,C,37,U,42,D,42,L,120,E,9,33,65,79,107,186,306,0,0,0,0,0,1,1,1,1,1,1,0,0,1,91,习题,某通讯系统只使用,8,种字符,a,、,b,、,c,、,d,、,e,、,f,、,g,、,h,，其使用频率是,0.05,、,0.29,、,0.07,、,0.08,、,0.14,、,0.23,、,0.03,、,0.11,。构造以字符使用频率为权值的,Huffman,树，并给出相应的,Huffman,编码。,92,习题答案,93,习题答案,A,：,0110,B,：,10,C,：,1110,D,：,1111,E,：,110,F,：,00,G,：,0111,H,：,010,94,课程安排,课程介绍,栈、队列和向量,树,查找,排序,图,95,查找,大纲描述：,查找的基本概念；对线性关系结构的查找，顺序查找，二分查找；,Hash,查找法,常见的,Hash,函数,(,直接定址法,随机数法,),hash,冲突的概念,解决冲突的方法,(,开散列方法,/,拉链法,闭散列方法,/,开址定址法,),二次聚集现象,;,BST,树定义,性质,ADT,及其实现,BST,树查找,插入,删除算法,;,平衡树,(AVL),的定义,性质,ADT,及其实现,平衡树查找,插入算法,平衡因子的概念,;,优先队列与堆,堆的定义,堆的生成,调整算法,;,范围查询,;,96,查找的基本概念,查找表,(search table),：,具有同一类型数据元素,(,经常称为记录,),的集合,查找表的基本操作有：,查找某个“特定”记录是否在表中,查找到后取出某个“特定”记录的各个数据项,向表中插入记录,从表中删除记录,97,查找的基本概念,静态查找表,(static search table),：,仅用于查询的查找表。,动态查找表,(dynamic search table):,若在查找过程中需同时插入表中不存在的记录,;,或者需要删除记录,则称之为动态查找表。,关键字,/,键值,(key),：,记录某个数据项的值,用其可以标示该记录,当记录只有一个数据项时,其关键字即为该记录的值,如果一个,key,可以唯一标示一个就,则称之为主关键字,(primary key),否则称之为次关键字,(secondary key),98,查找的基本概念,查找,(search),：,在一个查找表中找出具有“特定”键值的那些记录,所谓查找成功是指在查找表中找到了满足条件的记录,此时一般会返回找到的记录,或者返回记录的位置信息,或者仅仅返回找到,(true),否则称为查找失败,此时一般返回空指针,或特殊值,或者仅仅返回没有找到,(false),有时也会就此插入这个元素,99,BST,树定义，性质，实现,二叉排序树,(Binary Sorted Tree),又称二叉搜索树或二叉查找树,或者是一棵空树；,或者是具有下列性质的二叉树：,如果左子树非空,则左子树中所有节点的键值均小于它的根结点的值；,如果右子树非空,则右子树中所有节点的键值均大于它的根结点的值；,它的左右子树也都是二叉排序树。,100,BST,树定义，性质，实现,二叉排序树性质,如果对二叉排序树进行中序遍历,则得到一个从小到大排好序的列表,所以可以得到一种简单的排序方法叫做“树排序”,(treesort),。,我们也可以根据这个性质定义二叉排序树为,:,如果一棵树按中序遍历为排好序的,则这棵树是二叉排序树。,101,BST,树查找，插入，删除算法,BST,树查找，插入，删除算法,画图,算法,102,例题,已知,BST,树如左，请画出插入,16,，再删除,36,之后的,BST,树,103,例题答案,104,例题,试求按关键字序列（,12,，,1,，,4,，,3,，,7,，,8,，,1O,，,2,）插入生成的二叉排序树,105,例题答案,106,练习,假设结点序列,F,（,60,，,30,，,90,，,50,，,120,，,70,，,40,，,80,），试用,BST,的插入算法，用,F,中的结点依次进行插入，画出由,F,中结点所构成的,BST,树,T,1,；再用删除算法，依次删除,40,，,70,，,60,，画出删除后的,BST,树,T,2,。,107,练习答案,108,平衡树,平衡因子（,balanced factor,）,二叉树上任一节点的左子树高度减去右子树高度的差,AVL Tree,，根据其三位发明者,(Adelson-Velskii and Landis),的名字命名,一棵,BST,树中每个节点平衡因子的绝对值不超过,1,109,平衡树,基本思想,:,在插入或删除节点后对新树进行判断,如果新树已经变得不平衡,则通过旋转,(rotation),的方法对树进行重组,/,改组,(re-arrange),使得重组后的树在保持查找树特性的同时保持平衡,所谓旋转,:,通过改变支撑点来维持平衡,顺时针旋转为右旋,;,逆时针旋转为左旋,可以进行连续的多次旋转,110,平衡树,111,算法代码及基本的时间复杂度分析,查找方法,平均时间,顺序查找,O(n),二分查找,O(logn),BST,查找,O(logn),AVL,查找,O(logn),112,Hash,查找法，常见的,Hash,函数,哈希（,Hash,）函数：,在记录的存储位置和它的关键字之间建立一个确定的对应关系,f,，使每个关键字和结构中一个唯一的存储位置相对应。这个对应关系,f,为,哈希函数,。按这个思想建立的表为,哈希表,。,哈希函数的设定可以很灵活，只要使得任何关键字的哈希函数值都落在表长允许范围之内即可。,113,Hash,查找法，常见的,Hash,函数,练习：,已知线性表关键字集合为：,S=and,begin,do,end,for,go,if,repeat,then,until,while,，求哈希函数。,答案：,H(key)=key0 a;,即为关键字,key,中的第一个字母在字母表,a,b,c,.,z,中的序号,114,Hash,查找法，常见的,Hash,函数,直接定址法,直接取,key,或者,key,的某个线性函数值,h(key)=a*key+b,a,b,为常数,如前面的例子,又如人口普查时使用年龄,出生年份等,115,Hash,查找法，常见的,Hash,函数,除留余数法,选择一个适当的正整数,P,，用,P,去除关键字，取所得得余数作为散列地址，即：,H(key)=key%P,方法的关键是选取适当的,P,。选择,P,最好不要是偶数，也不要是基数的幂。,一般地选,P,为小于或等于散列表长度,m,的某个最大素数比较好。,缺点,:,整数相除速度较慢,116,Hash,查找法，常见的,Hash,函数,如,:,m=8,，,16,，,32,，,64,，,128,，,256,，,512,，,1024,P =7,，,13,，,31,，,61,，,127,，,251,，,503,，,1019,117,解决冲突的方法,对不同的关键字可能得到同一哈希地址，这种现象称,冲突,。具有相同函数值的关键字对该哈希函数来说称作同义词。,在一般情况下，冲突只能尽可能的少，而不能完全避免。,118,解决冲突的方法,共同思想,:,将具有相同函数值的记录存作一个链,闭散列方法,/,开址定址法,冲突记录存储在表内,开散列方法,/,链地址法,冲突记录存储在表外,119,解决冲突的方法,基本思想,当冲突发生时，使用某种方法在散列表中形成一个探查序列,(,也称之为,链,),，按此序列逐个单元的查找，直到找到一个指定的关键字或碰到一个开放的地址（单元为空）为止。,H,j,=(H(key)+d,j,)MOD m,1,j m-1;m,为,hash,表长度,d,j,为增量数列,各种方法的不同就区别在取不同的增量数列上,120,解决冲突的方法,常用,的增量数列,:,线性探测法,二次探测法,伪随机法,再哈希法,/,二次哈希法,桶式散列法,121,解决冲突的方法,线性探测法,取,d,j,=1,2,m-1,将散列表看成是一个环形表。若地址为,d,（即,H(key)=d,）的单元发生冲突，则依次探查下述地址单元：,d+1,，,d+2,，,.,，,m-1,，,0,，,1,，,.,，,d-1,直到找到一个空单元或查找到关键字为,key,的结点为止。若沿着该探查序列查找一遍之后，又回到了地址,d,，则无论是做插入操作还是做查找操作，都意味着失败。,122,解决冲突的方法,线性探测法,缺点,:,特别容易产生聚集,链非常长,123,解决冲突的方法,拉链法,若选定的散列函数的值域为,0,到,m-1,，则可将散列表定义为一个由,m,个单链表的链表头指针组成的指针数组,HTP(m),，凡是散列地址为,i,的结点，均插入到以,HTP(i),为头指针的单链表中。,124,26,41,68,15,06,44,36,38,12,51,25,0,1,2,3,4,5,6,7,8,9,10,11,12,若一组关键字为（,26,，,36,，,41,，,38,，,44,，,15,，,68,，,12,，,06,，,51,，,25,），散列函数定义为：,H(key)=key%13,。用拉练法建立的散列表为：,125,解决冲突的方法,拉链法,优点,:,不会堆积,所以平均查找时间较短,动态申请空间,适用于造表前无法确定表长的情况,删除处理简单快速,链长易控制,一般较短,126,解决冲突的方法,负载系数的定义和作用,设,key,的数量为,N,散列表的大小为,M,则,N/M,称负载系数或装填因子,(loadfactor),它表现了平均情况下每个链的长度,我们一般预先规定好这个值,然后当不够的时候再增加,hash,表的长度,(re-hash),这样可以保证链的平均长度不超过负载系数,127,解决冲突的方法,增加时一般作两倍的增加，而且增加后需要将所有的表元素全部重新求值放置,(,因为,m,变了,),一般取值为,0.75,128,解决冲突的方法,聚集,(clustering),现象,又称,二次聚集,指处理冲突中发生的两个第一个,hash,地址不同的记录争夺同一个后继,hash,地址的情况,常发生在有大量,key,对应于同一,Hash,函数值的情况下,聚集现象仅出现于使用,闭散列方法,时,当使用,线性探测法,时特别容易发生聚集现象,很容易使散列查询退化为对于链表或者数组的顺序查询,129,解决冲突的方法,假设,Hash,函数为,H(key)=key MOD 11,表中已经有,key 17,60,29,此时分别占据,6,7,5;,然后再插入,38,此时可以发现,当表中,5,6,7,都被占据后,凡是函数值为,5,6,7,8,的,key,都将争夺,8,这个位置,!,130,例题,在初始为空的哈希表中依次插入关键字序列,(MON,，,TUE,，,WED,，,THU,，,FRI,，,SAT,，,SUN),哈希函数为,H(k)=i MOD 7,，其中，,i,为关键字,k,的第一个字母在英文字母表中的序号，地址值域为,0:6,，采用线性再散列法处理冲突。插入后的哈希表应该如,_,B,_,所示。,(),A.0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON,B.0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON,C.0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON,D.0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON,131,例题,若待散列的序列为,(18,25,63,50,42,32,9),，哈希函数为,H(key)=key MOD 9,，哈希表长度为,9,，与,18,发生冲突的元素有,_,个,答案：,2,132,例题,已知一组关键字为（,26,，,36,，,41,，,38,，,44,，,15,，,68,，,12,，,06,，,51,，,25,），用线性探查法解决冲突构造这组关键字的散列表，假设利用除余法构造散列函数。,133,例题答案,为了减少冲突，通常令装填因子,Apr-Aug,2-Dec,3-Feb,5-Jan-Jun-Jul,6-Mar-May,7-Oct-Nov,9-Sep,137,练习答案,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,Apr,Aug,Dec,Feb,Jan,Mar,May,Jun,Jul,Sep,Oct,Nov,138,范围查询,定义,:,在指定集合中有多少记录的关键字是落在指定范围中,一维的情况,:,记录可以看作直线上的点,问题可以看作有多少点落入指定线段区域中,139,课程安排,课程介绍,栈、队列和向量,树,查找,排序,图,140,排序,大纲描述：,排序基本概念；,插入排序，希尔排序，选择排序，快速排序，归并排序，基数排序等排序算法基本思想；,算法代码及基本的时间复杂度分析；,堆的定义，堆的生成。,141,排序基本概念,排序,(Sorting),：,重排一个记录序列,使之成为按关键字有序,常见排序可分为以下五类：,插入排序（简单插入排序、希尔排序）,交换排序（冒泡排序、快速排序）,选择排序（简单选择排序、堆排序）,归并排序,计数排序（多关键字排序）,142,插入排序,46 26 22 68 48 42 36 84 66 22*,26 46 22 68 48 42 36 84 66 22*,22 26 46 68 48 42 36 84 66 22*,22 26 46 68 48 42 36 84 66 22*,22 26 46 48 68 42 36 84 66 22*,22 26 42 46 48 68 36 84 66 22*,22 26 36 42 46 48 68 84 66 22*,22 26 36 42 46 48 68 84 66 22*,22 26 36 42 46 48 66 68 84 22*,22 22*26 36 42 46 48 66 68 84,143,希尔排序,定义,Shell Sort,又称“缩小增量排序”（,Diminishing Increment Sort,），也是一种属于插入排序类的算法，但时间效率较其他排序方法有较大改进,基本思想是：先将整个待排记录序列分割为若干子序列分别进行直接插入排序，待整个序列的记录“基本有序”时，再对全体记录进行一次直接插入排序,144,冒泡排序,交换排序的一种,依次比较相邻的两个待排序元素，若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”,每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置,直到全部元素有序为止,/,直到某次冒泡过程中没有发生交换为止,145,快速排序,就平均时间而言，快速排序是目前被认为最好的一种内部排序方法,由,C.A.R.Hoare,发明,分治法,(divide and conquer),思想的体现,Unix,系统函数库所提供的标准排序方法,C,标准函数库中的排序方法直接就命名为,qsort(),146,快速排序,基本思想,:,是对冒泡排序的一种改进,选取一个轴值,然后根据此轴值通过一趟排序对记录集进行一次分割,然后对分割后产生的两个记录子集分别进行快速排序,147,快速排序,基本概念,:,轴值,(pivot):,书上称枢轴,用于将记录集,分割,为两个部分的那个键值,分割,(partition):,将记录集分为两个部分,前面部分记录的键值都比轴值小,后面部分的键值都比轴值大,148,快速排序,149,快速排序,49,38,65,97,76,13,27,49,38,65,97,76,13,27,49,27,38,65,97,76,13,49,27,38,97,76,13,65,49,27,38,13,97,76,65,49,27,38,13,76,97,65,49,27,38,13,49,76,97,65,49,49,temp,150,例题,写出对于结点序列（,46,，,26,，,22,，,68,，,48,，,42,，,36,，,84,，,66,）进行第一次分割后序列的情况，注意列出步骤的每一步。,151,例题答案,【】26,，,22,，,68,，,48,，,42,，,36,，,84,，,66,36,，,26,，,22,，,68,，,48,，,42,，,【】,，,84,，,66,36,，,26,，,22,，,【】,，,48,，,42,，,68,，,84,，,66,36,，,26,，,22,，,42,，,48,，,【】,，,68,，,84,，,66,36,，,26,，,22,，,42,，,【】,，,48,，,68,，,84,，,66,36,，,26,，,22,，,42,，,46,，,48,，,68,，,84,，,66,152,练习,已知序列（,2,8,7,1,3,5,6,4,），如果选用,4,作为枢轴，那么进行一次分割后序列表现是怎样的？,答案：,2,，,3,，,1,，,4,，,7,，,5,，,6,，,8,153,练习,对序列,(49,38,65,97,76,27,13,50),采用快速排序法进行排序，以序列的第一个元素为基准元素得到的划分结果是,_,。,答案：,13,，,38,，,27,，,49,，,76,，,97,，,65,，,50,154,简单选择排序示例,49,38,65,97,76,13,27,49,13,38,65,97,76,49,27,49,13,27,65,97,76,49,38,49,13,27,38,97,76,49,65,49,13,27,38,49,76,97,65,49,13,27,38,49,49,97,65,76,13,27,38,49,49,65,97,76,13,27,38,49,49,65,76,97,155,例题,对数据元素序列,(49,，,72,，,68,，,13,，,38,，,50,，,97,，,27),进行排序，前三趟排序结束时的结果依次为：第一趟：,13,，,72,，,68,，,49,，,50,，,97,，,27,；第二趟：,13,，,27,，,68,，,49,，,38,，,50,，,97,，,72,；第三趟：,13,，,27,，,38,，,49,，,68,，,50,，,97,，,72,；该排序采用的方法是,答案：简单选择排序,156,练习,若对序列,(49,，,38,，,65,，,97,，,76,，,13,，,27,，,50),采用选择排序法排序，则第三趟结束后序列的状态是,_,。,157,练习答案,13,，,38,，,65,，,97,，,76,，,49,，,27,，,50,13,，,27,，,65,，,97,，,76,，,49,，,38,，,50,13,，,27,，,38,，,97,，,76,，,49,，,65,，,50,158,堆的定义，堆的生成,1964,年威洛姆斯,(J.willioms),提出堆排序,属于树型选择排序，仅需要一个记录大小的辅助空间，每个待排序记录仅占有一个存储空间。,159,堆的定义，堆的生成,定义,：,n,个元素的序列,k,1,k,2,k,n,当且仅当满足下列关系时，称之为堆：,k,i,k,2i,且,k,i,k,2i+1,或,k,i,k,2i,且,k,i,k,2i+1,等价的树的定义：,如果一棵完全二叉树,其中每个节点的键值不小于,(,或者不大于,),其子树的所有节点的键值,则称这棵二叉树为,(,最大值,/,最小值,),堆,(max/min heap),160,堆的定义，堆的生成,10,15,56,25,30,70,10,15,56,25,30,70,小根堆示例,161,堆的定义，堆的生成,70,56,30,25,1