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

1、数据结构2016MSE考研冲刺,课程安排,课程介绍栈、队列和向量 树查找排序图,课程目的,（以最小代价）通过考试！不是成为专家不是初学授课,试题结构,考试满分60分考试题型：问答、分析、编程,样题问答和编程题,插入排序、选择排序、冒泡排序、快速排序中最快的排序方法是_试论述什么叫Hash冲突及有那些处理方法编程实现对二叉树所有节点的统计,课程安排,课程介绍栈、队列和向量 树查找排序图,链表、栈和队列,大纲描述：单链表,双向链表,环形链表,带哨兵节点的链表栈的基本概念和性质,栈ADT及其顺序,链接实现;栈的应用;栈与递归;队列的基本概念和性质,队列ADT及其顺序,链接实现;队列的应用;向量基本概

2、念和性质;向量ADT及其数组、链接实现;,线性表基本概念和性质,线性表是n个数据元素的有限序列常见线性表包括数组、链表、栈、队列等线性表的两种实现方式顺序链式对比：插入（有序、无序）、删除、查找、读取,环形链表,环形链表又称循环列表，是另一种形式的链式存储结构。它的特点是表中最后一个元素的指针域指向头结点,栈的基本概念和性质,栈：栈是限定仅在表尾进行插入和删除操作的线性表后进先出特性（LIFO）栈顶、栈底、出栈、入栈,例题,设有一个栈S，元素S1,S2,S3,S4,S5,S6依次进栈，如果6个元素的出栈顺序为S2,S3,S4,S6,S5,S1，则栈的容量至少应为多少？答案：3,栈的基本概念和性

3、质,设计递归问题的非递归算法一般需要用到栈机制三个数a、b、c进栈，不可能出现c、a、b顺序出栈,例题,若某栈的输入序列为a、b、c，则所有可能的出栈序列有_种，所有不可能的出栈序列有_种。答案：5，1,例题,若栈的输入序列为1,2,3,4，则是不可能的栈输出序列之一。答案：4，3，1，2,习题,若某栈的输入序列为a、b、c、d，则所有可能的出栈序列有_种，所有不可能的出栈序列有_种。请写出所有可能的序列和不可能的序列。,栈的应用,数制转换十进制数字与d进制数字的转换N=(N div d)d+N mod d其中div为整除，mod为求余。算法：将算法3.1中8换成d,例题,十进制数1167等于

4、八进制数？答案：2217思路：计算方法：除余倒排法验证方法：指数相加法,习题,十进制数1167等于七进制数？,栈的应用,表达式求值：中缀表达式转后缀表达式后缀表达式求值三种表达式：前缀表达式+a b中缀表达式 a+b后缀表达式 a b+,例题,中缀表达式a+b c d转为后缀表达式是？答案：a b cd,例题,中缀表达式（a+b）c d转为后缀表达式是？答案：a b cd思路：数字位序不变，运算符位置改变后缀表达式无括号，运算顺序同中缀表达式,习题,中缀表达式A-(B+C)*D/E的后缀形式是_。,练习,中缀表达式a*(b+c)/d转为后缀表达式是？,例题,计算后缀表达式1 2+4*2/的值为

5、？答案：6思路：顺序计算或 转换为中缀表达式计算,习题,计算后缀表达式3 2 4*2/3的值为？,递归,一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数优点：结构清晰、程序易读、正确性容易得到证明缺点：效率相对较低,队列的基本概念和性质,队列：队列是限定仅在表的一头进行插入、另一头进行删除操作的线性表先进先出特性（FIFO）队尾、队头、入队、出队,例题,在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队头元素是，队尾元素是。答案：c，d,双向队列,双向队列：亦称双端队列（Deque）是限定插入和删除操作在表的两端进行的线性表可以用于包装产生栈

6、和队列,课程安排,课程介绍栈、队列和向量 树查找排序图,树,大纲描述：树的基本概念和术语；树的前序、中序、后序、层次序遍历；二叉树及其性质；普通树与二叉树的转换；树的存储结构,标准形式;完全树(complete tree)的数组形式存储;树的应用，Huffman树。,树的基本概念和术语,树：是n（n0）个结点的有限集在任意一棵非空树中：有且仅有一个特定的称为根的结点当n1时，其余结点可以分为m（m0）个互不相交的有限集，其中每个集合本身又是一棵树，并且称为根的子树树属于层次结构数据结构,树的基本概念和术语,节点标签父节点、子节点、兄弟节点、祖先节点、子孙节点路径、树枝,根、叶子次数内部节点、外

7、部节点树的次数、K次树节点层次、树的高度和深度子树有序树、无序树森林、果园,例题,例题,列出如上图所示树的所有叶子结点答案：K,L,F,G,M,I,J列出如上图所示树的所有分支结点答案：A,B,C,D,E,H树A为几次树？子树B呢？答案：3，2前页图所示树的高度为多少？答案：4,树的基本概念和术语,如果将树中结点的各子树看作从左到右有序的,则该树为有序树(ordered tree),否则为无序树。森林(forest)是m棵互不相交的树的集合。如果把一棵树的根砍去，剩下的部分就是森林。如果原来的树是有序的,则砍去根后的森林也是有序的,此时称该森林为有序森林或果园。,二叉树及其性质,二叉树（Bin

8、ary Tree）另一种树形结构，特点是每个结点至多只有二棵子树，且子树有左右之分，其次序不能任意颠倒二叉树可能的五种基本形态,二叉树及其性质,在二叉树的第i层上至多有2i1个结点（i1）,例题,一棵二叉树第五层上至多有多少个结点？至少多少？答案：16，1,二叉树及其性质,深度为k的二叉树至多有2k1个结点（k1）,例题,深度为n(n0)的二叉树最多有_个结点。答案：2n-1,例题,一棵深度为5的二叉树至多有多少个结点？至少多少？答案：31，5,例题,高度为h(h0)的二叉树最少有_个结点？答案：h,二叉树及其性质,对于任何二叉树,如果叶子节点数为n0,度为2的节点数为n2,则n0=n2+1,

9、例题,在一棵二叉树中有n0个叶结点，有n2个度为2的结点，则n2=_。答案：n0 1,例题,若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为_。答案：9,例题,若一二叉树有2度结点100个，则其叶结点有多少个？答案：101,例题,若二叉树中度为2的结点有15个，度为1的结点有10个，共有多少个结点？答案：41,例题,在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，那么，该树有_个叶结点。答案：6构造法,二叉树及其性质,满二叉树：一棵深度为k且有2k1个结点的二叉树可以对满二叉树的结点进行连续编号，约定编号从根开始，自上而下，自左而右。完全二叉树：深度

10、为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。,二叉树及其性质,完全二叉树特点：叶子结点只可能出现在层次最大的两层上对任一结点，若其右分支下子孙的最大层次为l，其左下分支的子孙的最大层次必为l或者l1。深度为k的完全二叉树第k层最少1个结点，最多2k-1-1个结点；整棵树最少2k-1个结点，最多2k-2个结点,例题,若某完全二叉树的深度为h，则该完全二叉树中至少有_个结点。答案：2h-1,例题,若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有_个结点。答案：25-1+334,例题,一个具有767个结点的完全二叉

11、树，其叶子结点个数为_。答案：384分析：可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0n21，则n=n0n1n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n=2n0+n11，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0（n1）/2或n0n/2，合并成一个公式：n0（n1）/2，就可根据完全二叉树的结点总数计算出叶子结点数。本题计算得：384。,二叉树及其性质,具有n个结点的完全二叉树的深度为log2n+1,例题,具有2000个结点的二叉树，其深度至少为_。答案：11,

12、二叉树及其性质,如果含有n 1个节点的二叉树的高度为log2n1,将其所有结点按层次序编号,则对于任一节点j(1j n),有如果j=1,则节点j是树的根,无双亲;如果j1,则其父节点parent(j)是节点j/2如果2jn,则节点j无左子节点;否则其左子节点为2j如果2j+1n,则节点j无右子节点;否则其右子节点为2j+1证明,完全树的数组形式存储,完全树的数组形式存储算法将其编号为i的结点元素存储在一维数组下标为i1的分量中,例题,已知数组20,30,19,87,30,40表示一棵完全二叉树，请画出该树。,练习答案,树的遍历,树的遍历 按某种搜索路径巡访树中每个结点，使每个结点均被访问一次仅

13、且一次二叉树的遍历可分为前序、中序、后序、层次序等普通树的遍历可以分为先根、后根、层次序等,树的遍历,二叉树的遍历前序、中序、后序定义层次序：从上而下，从左至右常见问题已知树写遍历结果已知遍历结果画树依据：二叉树的前序和中序遍历可以唯一确定一棵二叉树思路：前序定根，中序定左右递归和非递归算法实现,例题,写出左图所示二叉树的前序、中序、后序、层次序遍历结果,例题答案,前序：ABDCEFG中序：DBAECFG后序：DBEGFCA层次序：ABCDEFG,例题,假设一棵二叉树的前序遍历为EBADCHGFIKJ，中序遍历为ABCDEFGHIJK，请画出该树。,例题答案,树的遍历,普通树的遍历前根：先遍历

14、根结点，再依次前根遍历各棵子树后根：先后根遍历各课子树，再遍历根结点已知树写遍历结果已知遍历结果画树思路：先根定根，后根定子树,例题,写出如右图所示树的先根、后根、层次序遍历结果,例题答案,前序：ABECFGHD后序：EBFHGCDA层次序：ABCDEFGH,练习,给出如图所示树的先根、后根和层次序遍历结果,练习答案,前根：ABEFHIGCJKLDMNOQP后根：EHIFGBKLJCNQOPMDA层次序：ABCDEFGJMHIKLNOPQ,例题,画出和下列已知序列对应的树T：树的先根次序访问序列为GFKDAIEBCHJ树的后根次序访问序列为DIAEKFCJHBG,例题答案,普通树与二叉树的转换

15、,对于任意k次树到相应二叉树的转换算法对于具有子节点n1,n2nk的节点n,将n1作为其左子节点,且kj+1作为kj(1 j k-1)的右子节点思路：“不同层在左，同层在右”,普通树与二叉树的转换,对于任意森林到相应二叉树的转换算法为 设T=(T1,T2.Tm)为m(m0)棵树的序列,而BT(T1,T2.Tm)为相应的二叉树,则如果m=0,则BT为空树如果m0,则T1的根节点就是BT的根节点,而BT的左子树是T1的子树T11,T12T1K转换成的BTl(T11,T12T1K),其右子树为BTr(T2.Tm),例题,将下页图所示森林转换为等价的二叉树,例题,例题答案,练习,将如图所示树转换为二叉

16、树,练习答案,Huffman树,Huffman树：又称最优树，是一类带权路径长度最短的树基本概念：树的路径长度：从根到每一结点的路径长度之和。结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记做WPL。,Huffman树,基本概念：假设有n个权值wi，试构造一棵有n个叶子结点的二叉树，每个叶子的结点带权为wi，则其中WPL最小的二叉树称为最优二叉树或赫夫曼树算法见下页,Huffman算法,(1)由给定的n个权值w0,w1,w2,wn-1，构造具有n棵二叉树的集合F=T0,T1,T2,Tn-1，其中每一棵二叉树Ti只有一

17、个带有权值wi的根结点，其左、右子树均为空。(2)在F中选取两棵根结点的权值最小的二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。(3)在F中删去这两棵二叉树，加入新得的树。(4)重复(2)(3)，直到F只含一棵树为止。这棵树就是赫夫曼树,Step 1,2Z,7K,24F,32C,37U,42D,42L,120E,9,33,Round 1,Round 2,例题,2Z,7K,24F,32C,37U,42D,42L,120E,9,33,65,Round 3,2Z,7K,24F,32C,37U,42D,42L,120E,9,33,65,79,Ro

18、und 4,2Z,7K,24F,32C,37U,42D,42L,120E,9,33,65,79,107,Round 5,2Z,7K,24F,32C,37U,42D,42L,120E,9,33,65,79,107,186,Round 6,2Z,7K,24F,32C,37U,42D,42L,120E,9,33,65,79,107,186,306,Round 7(final),Huffman编码,编码：等长编码/不等长编码前缀编码：若要设计长短不等的编码，则必须是任一个字符的编码抖不是另一个字符编码的前缀，这种编码叫做前缀编码Huffman编码：以n种字符出现的频率做权，设计一棵赫夫曼树，由此得到的

19、前缀编码称为Huffman编码,例题,2Z,7K,24F,32C,37U,42D,42L,120E,9,33,65,79,107,186,306,0,0,0,0,0,1,1,1,1,1,1,0,0,1,习题,某通讯系统只使用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编码。,习题答案,习题答案,A：0110B：10C：1110D：1111,E：110F：00G：0111H：010,课程安排,课程介绍栈、队列和向量 树查找排序图,查找,大纲

20、描述：查找的基本概念；对线性关系结构的查找，顺序查找，二分查找；Hash查找法,常见的Hash函数(直接定址法,随机数法),hash冲突的概念,解决冲突的方法(开散列方法/拉链法,闭散列方法/开址定址法),二次聚集现象;BST树定义,性质,ADT及其实现,BST树查找,插入,删除算法;平衡树(AVL)的定义,性质,ADT及其实现,平衡树查找,插入算法,平衡因子的概念;优先队列与堆,堆的定义,堆的生成,调整算法;范围查询;,查找的基本概念,查找表(search table)：具有同一类型数据元素(经常称为记录)的集合查找表的基本操作有：查找某个“特定”记录是否在表中查找到后取出某个“特定”记录的

21、各个数据项向表中插入记录从表中删除记录,查找的基本概念,静态查找表(static search table)：仅用于查询的查找表。动态查找表(dynamic search table):若在查找过程中需同时插入表中不存在的记录;或者需要删除记录,则称之为动态查找表。关键字/键值(key)：记录某个数据项的值,用其可以标示该记录当记录只有一个数据项时,其关键字即为该记录的值如果一个key可以唯一标示一个就,则称之为主关键字(primary key),否则称之为次关键字(secondary key),查找的基本概念,查找(search)：在一个查找表中找出具有“特定”键值的那些记录所谓查找成功是指

22、在查找表中找到了满足条件的记录,此时一般会返回找到的记录,或者返回记录的位置信息,或者仅仅返回找到(true)否则称为查找失败,此时一般返回空指针,或特殊值,或者仅仅返回没有找到(false),有时也会就此插入这个元素,BST树定义，性质，实现,二叉排序树(Binary Sorted Tree)又称二叉搜索树或二叉查找树或者是一棵空树；或者是具有下列性质的二叉树：如果左子树非空,则左子树中所有节点的键值均小于它的根结点的值；如果右子树非空,则右子树中所有节点的键值均大于它的根结点的值；它的左右子树也都是二叉排序树。,BST树定义，性质，实现,二叉排序树性质 如果对二叉排序树进行中序遍历,则得到

23、一个从小到大排好序的列表,所以可以得到一种简单的排序方法叫做“树排序”(treesort)。我们也可以根据这个性质定义二叉排序树为:如果一棵树按中序遍历为排好序的,则这棵树是二叉排序树。,BST树查找，插入，删除算法,BST树查找，插入，删除算法画图算法,例题,已知BST树如左，请画出插入16，再删除36之后的BST树,例题答案,例题,试求按关键字序列（12，1，4，3，7，8，1O，2）插入生成的二叉排序树,例题答案,练习,假设结点序列F（60，30，90，50，120，70，40，80），试用BST的插入算法，用F中的结点依次进行插入，画出由F中结点所构成的BST树T1；再用删除算法，依次

24、删除40，70，60，画出删除后的BST树T2。,练习答案,平衡树,平衡因子（balanced factor）二叉树上任一节点的左子树高度减去右子树高度的差AVL Tree，根据其三位发明者(Adelson-Velskii and Landis)的名字命名一棵BST树中每个节点平衡因子的绝对值不超过1,平衡树,基本思想:在插入或删除节点后对新树进行判断,如果新树已经变得不平衡,则通过旋转(rotation)的方法对树进行重组/改组(re-arrange),使得重组后的树在保持查找树特性的同时保持平衡所谓旋转:通过改变支撑点来维持平衡顺时针旋转为右旋;逆时针旋转为左旋可以进行连续的多次旋转,平衡

25、树,算法代码及基本的时间复杂度分析,Hash查找法，常见的Hash函数,哈希（Hash）函数：在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。这个对应关系f为哈希函数。按这个思想建立的表为哈希表。哈希函数的设定可以很灵活，只要使得任何关键字的哈希函数值都落在表长允许范围之内即可。,Hash查找法，常见的Hash函数,练习：已知线性表关键字集合为：S=and,begin,do,end,for,go,if,repeat,then,until,while，求哈希函数。答案：H(key)=key0 a;即为关键字key中的第一个字母在字母表a,b

26、,c,.,z中的序号,Hash查找法，常见的Hash函数,直接定址法直接取key或者key的某个线性函数值 h(key)=a*key+b,a,b为常数如前面的例子,又如人口普查时使用年龄,出生年份等,Hash查找法，常见的Hash函数,除留余数法选择一个适当的正整数P，用P去除关键字，取所得得余数作为散列地址，即：H(key)=key%P方法的关键是选取适当的P。选择P最好不要是偶数，也不要是基数的幂。一般地选P为小于或等于散列表长度m的某个最大素数比较好。缺点:整数相除速度较慢,Hash查找法，常见的Hash函数,如:m=8，16，32，64，128，256，512，1024P=7，13，3

27、1，61，127，251，503，1019,解决冲突的方法,对不同的关键字可能得到同一哈希地址，这种现象称冲突。具有相同函数值的关键字对该哈希函数来说称作同义词。在一般情况下，冲突只能尽可能的少，而不能完全避免。,解决冲突的方法,共同思想:将具有相同函数值的记录存作一个链闭散列方法/开址定址法冲突记录存储在表内开散列方法/链地址法冲突记录存储在表外,解决冲突的方法,基本思想当冲突发生时，使用某种方法在散列表中形成一个探查序列(也称之为链)，按此序列逐个单元的查找，直到找到一个指定的关键字或碰到一个开放的地址（单元为空）为止。Hj=(H(key)+dj)MOD m 1 j m-1;m为hash表

28、长度dj为增量数列,各种方法的不同就区别在取不同的增量数列上,解决冲突的方法,常用的增量数列:线性探测法二次探测法伪随机法再哈希法/二次哈希法桶式散列法,解决冲突的方法,线性探测法取dj=1,2,m-1将散列表看成是一个环形表。若地址为d（即H(key)=d）的单元发生冲突，则依次探查下述地址单元：d+1，d+2，.，m-1，0，1，.，d-1,直到找到一个空单元或查找到关键字为key的结点为止。若沿着该探查序列查找一遍之后，又回到了地址d，则无论是做插入操作还是做查找操作，都意味着失败。,解决冲突的方法,线性探测法缺点:特别容易产生聚集链非常长,解决冲突的方法,拉链法若选定的散列函数的值域为

29、0到m-1，则可将散列表定义为一个由m个单链表的链表头指针组成的指针数组HTP(m)，凡是散列地址为i的结点，均插入到以HTP(i)为头指针的单链表中。,0123456789101112,若一组关键字为（26，36，41，38，44，15，68，12，06，51，25），散列函数定义为：H(key)=key%13。用拉练法建立的散列表为：,解决冲突的方法,拉链法优点:不会堆积,所以平均查找时间较短动态申请空间,适用于造表前无法确定表长的情况删除处理简单快速链长易控制,一般较短,解决冲突的方法,负载系数的定义和作用设key的数量为N,散列表的大小为M,则N/M称负载系数或装填因子(loadfac

30、tor),它表现了平均情况下每个链的长度我们一般预先规定好这个值,然后当不够的时候再增加hash表的长度(re-hash),这样可以保证链的平均长度不超过负载系数,解决冲突的方法,增加时一般作两倍的增加，而且增加后需要将所有的表元素全部重新求值放置(因为m变了)一般取值为0.75,解决冲突的方法,聚集(clustering)现象又称二次聚集,指处理冲突中发生的两个第一个hash地址不同的记录争夺同一个后继hash地址的情况,常发生在有大量key对应于同一Hash函数值的情况下聚集现象仅出现于使用闭散列方法时当使用线性探测法时特别容易发生聚集现象,很容易使散列查询退化为对于链表或者数组的顺序查询

31、,解决冲突的方法,假设Hash函数为H(key)=key MOD 11,表中已经有key 17,60,29,此时分别占据6,7,5;然后再插入38此时可以发现,当表中5,6,7都被占据后,凡是函数值为5,6,7,8的key都将争夺8这个位置!,例题,在初始为空的哈希表中依次插入关键字序列(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 MO

32、N 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,例题,若待散列的序列为(18,25,63,50,42,32,9)，哈希函数为H(key)=key MOD 9，哈希表长度为9，与18发生冲突的元素有_个答案：2,例题,已知一组关键字为（26，36，41，38，44，15，68，12，06，51，25），用线性探查法解决冲突构造这组关键字的散列表，假设利用除余法构造散列函数。,例题

33、答案,为了减少冲突，通常令装填因子1，在此我们取=0.75。因为n=11，所以散列表长度m=high(n/)=15；对于除余法，选P=13（小于15的最大素数），即散列函数为：H(key)=key%13。按顺序插入各个结点：26:H(26)=26/13=0 36:.=10，41:.=2，38:.=12，44:.=5插入15时，其散列地址为2，由于2已被关键字为41的元素占用，故需进行探查。按顺序探查法，显然3为开放地址，故可将其放在3单元。类似的，68和12可分别放在4和13单元中,练习,在地址空间为0-16的散列区中,对以下关键字构造两个hash表:(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)使用开散列方法(此时请注明装载因子为多少)使用闭散列方法(此时使用线性探测法)此处设hash函数为H(x)=i/2,其中i为关键字中第一个字