数据结构与算法(第三部分-数据结构)

1、数据结构与算法（第三部分 数据结构）2009年10月1使用指针表示动态集合栈、队列、链表、有根树等2第三部分 数据结构第十章 基本数据结构 栈和队列（简要回顾）310.1 栈和队列栈的定义栈是只能在一端插入和删除元素的线性表。 术语：栈顶, 栈底, 入栈（压栈）, 出栈（弹栈） an an-1 a1入栈(PUSH) 出栈(POP) 栈顶(top)栈底(bottom)a1 a2 an 特性：后进先出 ( LIFO )-Last in First out a1a2anana2a1410.1栈和队列栈的运算1.栈的基本运算定义对栈的基本运算有如下几个：(1)初始化 ：设置栈为空。 (2)判断栈为空：

2、 若为空，则返回TRUE，否则返回FALSE. (3)判断栈为满： 若为满，则返回TRUE，否则返回FALSE. (4)取栈顶元素：取出栈顶元素。 条件：栈不空。 否则，应能明确给出标识，以便程序的处理。(5)入栈：将元素入栈，即放到栈顶。 如果栈满，怎样处理？ (6)出栈：删除当前栈顶的元素。510.1栈和队列队列的定义队列是只能在一端插入，另一端删除元素的线性表。 术语：队头, 队尾， 入队, 出队 a1 a2 an 特性：先进先出（FIFO：first in first out）a1a2anana2a1a1a2an队头队尾出队入队610.1栈和队列队列的运算1.队列的基本运算定义对队列的

3、基本运算有如下几个：(1)初始化 ：设置队列为空。 (2)判断队列为空： 若为空，则返回TRUE，否则返回FALSE. (3)判断队列为满： 若为满，则返回TRUE，否则返回FALSE. (4)取队头元素：取出队头元素。 条件：队列不空。 否则，应能明确给出标识，以便程序的处理。(5)入队：将元素入队，即放到队列的尾部。 如果队列满，怎样处理？ (6)出栈：删除当前队头的元素。 710.1栈和队列用两个栈来实现一个队列，并分析有关队列操作的运行时间。用两个队列来实现一个栈，并分析有关栈操作的运行时间。810.2 链表基本存储结构：插入操作分析： 三种位置：链表中间；链表尾；链表头 在链表中间某

4、位置插入时， s - next = p - next; p - next = s; /注意：两条语句顺序不能颠倒 a1an a3a2head头指针首元素结点尾结点 a1a2a3an X headPs910.2 链表引入“头结点”可以降低一些操作的常数因子在循环结构中，使得代码更加简洁在短链表中，会造成存储的浪费1010.2 链表引入“头结点”（附加结点）链表运算实现讨论和分析插入删除查找构造a1a2an 1110.2 链表其他形式的链表（1）单循环链表 运算讨论和分析查找插入删除a1a2an head1210.2 链表（2）双循环链表运算讨论和分析查找插入删除a1a2 an head1310.

5、3 二叉树 二叉树T：是n个结点组成的有限集合（n = 0）， n=0时为空二叉树， 否则：其中有一个根结点， 其余结点可以划分成两个互不相交的子集TL, TR， 且TL, TR也分别构成二叉树 左、右子树。1410.3 二叉树定义1：称高度为k且有2k-1个结点的二叉树为满二叉树。例如，高度为14的满二叉树如下。 ABCGFEDANOABCGFEHIDKJMLCBA(a) 高度为1的满二叉树(b) 高度为2的满二叉树(c) 高度为3的满二叉树(d) 高度为4的满二叉树1510.3 二叉树二叉树的二叉链表结构AGFEDCB G AB E C D F T16第11章 散列表实例：某班的成绩表如下

6、表为了能一次查找成功，在存储表的过程中，建立key与存储地址之间的一一对应关系17第11章 散列表更一般情况：对给定的关键字key，用一个函数H(key)计算出元素地址，由此而得散列表（Hash表，哈希表），其中函数H(key)称为散列函数此函数值称为散列地址。然而，在实际应用中，会出现这样的情况： k1k2，但H(k1)=H(k2) ， 称这种现象为冲突现象，k1,k2为同义词。针对冲突如何解决冲突呢？构造好的散列函数，以免冲突 由于冲突不可避免，因此，确切地说是减少冲突妥善处理冲突18第11章 散列表构造散列函数的基本方法除留余数法：H(k)= k % p 其中pm,m为数组规模的最大质数

7、。平方取中法： 例：325在平方后取105625中间两位，即56作为它的散列地址。折叠法：如 身份证号码：3461532先进行分组：340 104 198 805 061 532数值分析法直接定址法：H(k)= k 或者 H(k)= ak+b （a，b为任意正整数）19第11章 散列表处理冲突：开放地址法 Hi(k)=(H(k) + di ) % m，i=1,2,q qlchild;XT-data.keyT=T-rchild ;找到5040473020354549709065556780100T二叉查找树的查找 如何在二叉查找树中查找给定关键字的结点？ 以在下图所示树中分别查找45、55、66

8、为例来说明。 由此可得到查找的判定过程。 判定过程类似于二分查找的判定过程。失败！26第12章 二叉查找树查找算法的流程图XP-data.keyP=P-lchild;P=P-rchild;查找成功return PP!=NULLP=TYreturn NULL;N查找的非递归算法： bnode *bstsearch(bnode *T， elementtype x) p=T; while ( p != NULL ) if ( p - data = = x ) return p; if ( x data ) p = p - lchild; else p = p - rchild; return NUL

9、L; 27第12章 二叉查找树 查找的递归算法： bnode *bstsearch(bnode *T, elementtype x) if ( T = NULL ) return T; if (T - data = x ) return T; if (x data) return bstsearch(T-lchild,x); else return bstsearch(T-rchild,x); XP-data.keyP=P-lchild;P=P-rchild;查找成功return PP!=NULLP=TYreturn NULL;N28第12章 二叉查找树二叉查找树的构造：从空树出发，依次插入各

10、结点（作为叶子结点）。二叉查找树中插入结点：(1)若结点的值小于根结点的值， 则往左子树中插入 -通过递归调用插入算法来实现。(2)若结点的值大于等于根结点的值， 则往右子树中插入（递归调用）。按此方式递归调用若干次后， 可以搜索到一个空子树位置，即要插入的位置。29第12章 二叉查找树构造过程：依次将结点作为叶结点插入到二叉查找树中例：以下列数据序列作为输入构造一棵二叉查找树。100，65，88，93，145，118，138，112，188，173，42，78，20, 19710065422078938811811213817319718814530第12章 二叉查找树二叉查找树的插入算法逐

11、个插入元素来实现构造，插入的元素作为叶子结点。 void insert(bnode *& T, bnode *s) / 将s所指结点插入到以T为根指针的二叉查找树中 if ( T = = NULL ) / T 为空时 T = = s; / 新结点作为根结点 else if ( s-data data ) insert( T - lchild, s ); else insert( T - rchild, s ); 31第12章 二叉查找树二叉查找树的构造算法void creat(bnode *&T) / 接受读入数据，从空树开始构造二叉查找树 T= =NULL; cinx; while (x!=

12、结束符) s=new bnode; s - data=x; s - lchild=NULL; s - rchild=NULL; insert(T,s); cinx; 32第12章 二叉查找树二叉查找树构造分析： 以下列数据序列作为输入构造一棵二叉查找树。 100，65，88，93，145，118，138，112，188，173，42，78，20，197平均查找长度： （1223447）/14 = 45/1410065422078938811811213817319718814533第12章 二叉查找树二叉查找树构造分析： 再看以下列数据序列作为输入构造一棵二叉查找树。20，42，65，78，8

13、8，93，100，112，118，138，145，173，188,197平均查找长度： （1214）/14 = 105/1420426578.由此而提出平衡二叉树34第12章 二叉查找树二叉查找树删除结点：删除二叉查找树中的结点可分几种情况来实现 ：叶子结点 直接删除即可非叶子结点顶替法重新连接法100654220789388118112138173197188145删除叶子781006542209388118112138173197188145删除非叶子4220100654220789388118112138173197188145删除非叶子1451733512. 二叉查找树12.2 平衡二

14、叉树 定义：平衡二叉树是一棵二叉查找树，或者为空， 或者满足以下条件： 1)左右子树高度差的绝对值不大于1； 2)左右子树都是平衡二叉树。 平衡因子： 左子树的高度减去右子树的高度，显然，在平衡二叉树中， 每个结点的平衡因子的值为-1，0或1。 36第12章 二叉查找树如何构造平衡二叉树（树） 在平衡的二叉查找树中插入一个结点，当出现不平衡时，根据不平衡情况分四种调整方法 假设最低不平衡结点为A，根据新插入结点与A的位置关系来命名调整方法： LL型：新插入结点在A的左孩子(L)的左子树(L)中； LR型：新插入结点在A的左孩子(L)的右子树(R)中； RL型：新插入结点在A的右孩子(R)的左子

15、树(L)中； RR型：新插入结点在A的右孩子(R)的右子树(R)中。37第12章 二叉查找树LL型（图示）：ABCLL型BCAABBLBRARh+2hLL型ABBLBRAR38第12章 二叉查找树LR型（图示）：ABCLR型CBAABBLCLARh+2hLR型ACCRARCCRBBRCL39第12章 二叉查找树RL型（图示）：ABCRL型CABABALCLBRhh+2RL型BCCRBRCCRAARCL40第12章 二叉查找树RR型（图示）：ABCRR型BACABBLBRARh+2hRR型ABBLARBR41第12章 二叉查找树练习：依次输入下列数据构造一棵平衡二叉树： 100，90，80，60

16、，70，50，120，110，150，87。1009080LL型90801006070LR型9070100608050LL型907010060805012011042第12章 二叉查找树练习：依次输入下列数据构造一棵平衡二叉树： 100，90，80，60，70，50，120，110，150，87。9070100608050120110RL型9070110608050100120150RR型706050110908010012015043第12章 二叉查找树练习：依次输入下列数据构造一棵平衡二叉树： 100，90，80，60，70，50，120，110，150，87。70605011090801

17、0012015087RL型70605011090801001201508744第12章 二叉查找树思考：至少要用7个数作为输入序列，构造一棵平衡二叉树， 构造过程中同时包含4种调整方法。请给出这样的序列。在构造平衡二叉树的过程中， 若A的平衡因子变为-2，A的左孩子的平衡因子为0， 右孩子的平衡因子为1，则进行何种调整？ 求高度为n的平衡二叉树至少需要的结点个数。 一棵平衡二叉树中的叶子结点高度之差能不能超过2？45第13章 红黑树 由前面讨论可知：二叉查找树中查找元素的长度取决于树的高度极端情况下，接近于链表中查找红黑树（red-black-tree)是许多“平衡的”查找树中的一种，最坏情况

18、下，基本动态集合的操作时间为O(lgn)。46第13章 红黑树13.1 红黑树的性质红黑树是一种二叉查找树， 但在每个结点上增加一个存储位表示结点的颜色 -红或黑。通过对任意一条从根到叶子的路径上的各结点着色方式的限制， 确保没有一条路径会比其他路径长出两倍。 因而是接近平衡的。每个结点包含5个域:color, key, left, right, p如果某结点没有孩子结点或父结点，则其p值为nil.将这些nil视为指向二叉查找树的外结点（叶子结点）的指针，将带关键字的结点视为树的内结点。47第13章 红黑树定义：一棵二叉查找树如果满足以下性质，则为一棵红黑树:每个结点或者是红的，或者是黑的。根结点是黑的。每个叶子结点(nil)是黑的。如果一个结点是红的，则它的两个孩子结点都是黑的。对每个结点，从该结点到其后代结点的所有路径上包含相同数目的黑结点。48第13章 红黑树每个结点或者是红的，或者是黑的。根结点是黑的。每个叶子结点(nil)是黑的。如