《数据结构与算法(第三部分-数据结构)》由会员分享，可在线阅读，更多相关《数据结构与算法(第三部分-数据结构)（50页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法,（第三部分 数据结构） 胡学钢 计算机与信息学院 2009年10月,使用指针表示动态集合 栈、队列、链表、有根树等,第三部分 数据结构,第十章 基本数据结构栈和队列（简要回顾）,10.1 栈和队列,栈的定义 栈是只能在一端插入和删除元素的线性表。术语：栈顶, 栈底, 入栈（压栈）, 出栈（弹栈）,入栈 (PUSH),出栈 (POP),栈顶 (top),栈底 (bottom),a1 a2 an,特性：后进先出 ( LIFO ) -Last in First out,a1,a2,an,an,a2,a1,10.1栈和队列,栈的运算 1.栈的基本运算定义 对栈的基本运算有如下几个： (
2、1)初始化 ：设置栈为空。 (2)判断栈为空：若为空，则返回TRUE，否则返回FALSE. (3)判断栈为满：若为满，则返回TRUE，否则返回FALSE. (4)取栈顶元素：取出栈顶元素。条件：栈不空。 否则，应能明确给出标识，以便程序的处理。 (5)入栈：将元素入栈，即放到栈顶。如果栈满，怎样处理？ (6)出栈：删除当前栈顶的元素。,10.1栈和队列,队列的定义 队列是只能在一端插入，另一端删除元素的线性表。术语：队头, 队尾， 入队, 出队,a1 a2 an,特性：先进先出 （FIFO：first in first out）,a1,a2,an,an,a2,a1,a1,a2,an,队头,队尾
3、,出队,入队,10.1栈和队列,队列的运算 1.队列的基本运算定义 对队列的基本运算有如下几个： (1)初始化 ：设置队列为空。 (2)判断队列为空：若为空，则返回TRUE，否则返回FALSE. (3)判断队列为满：若为满，则返回TRUE，否则返回FALSE. (4)取队头元素：取出队头元素。条件：队列不空。 否则，应能明确给出标识，以便程序的处理。 (5)入队：将元素入队，即放到队列的尾部。如果队列满，怎样处理？ (6)出栈：删除当前队头的元素。,10.1栈和队列,用两个栈来实现一个队列，并分析有关队列操作的运行时间。 用两个队列来实现一个栈，并分析有关栈操作的运行时间。,10.2 链表,基
4、本存储结构：插入操作分析：三种位置：链表中间；链表尾；链表头在链表中间某位置插入时，s - next = p - next;p - next = s; /注意：两条语句顺序不能颠倒,X,head,P,s,10.2 链表,引入“头结点” 可以降低一些操作的常数因子 在循环结构中，使得代码更加简洁 在短链表中，会造成存储的浪费,10.2 链表,引入“头结点”（附加结点）链表运算实现讨论和分析 插入 删除 查找 构造,10.2 链表,其他形式的链表 （1）单循环链表运算讨论和分析 查找 插入 删除,10.2 链表,（2）双循环链表运算讨论和分析 查找 插入 删除,head,10.3 二叉树,二叉树T
5、：是n个结点组成的有限集合（n = 0），n=0时为空二叉树，否则：其中有一个根结点，其余结点可以划分成两个互不相交的子集TL, TR，且TL, TR也分别构成二叉树 左、右子树。,10.3 二叉树,定义1：称高度为k且有2k-1个结点的二叉树为满二叉树。 例如，高度为14的满二叉树如下。,A,(a) 高度为1的满二叉树,(b) 高度为2的满二叉树,(c) 高度为3的满二叉树,(d) 高度为4的满二叉树,10.3 二叉树,二叉树的二叉链表结构,第11章 散列表,实例：某班的成绩表如下表,为了能一次查找成功，在存储表的过程中， 建立key与存储地址之间的一一对应关系,第11章 散列表,更一般情况
6、： 对给定的关键字key， 用一个函数H(key)计算出元素地址， 由此而得散列表（Hash表，哈希表）， 其中函数H(key)称为散列函数 此函数值称为散列地址。 然而，在实际应用中，会出现这样的情况：k1k2，但H(k1)=H(k2) ，称这种现象为冲突现象，k1,k2为同义词。 针对冲突如何解决冲突呢？ 构造好的散列函数，以免冲突由于冲突不可避免，因此，确切地说是减少冲突 妥善处理冲突,第11章 散列表,构造散列函数的基本方法,除留余数法：H(k)= k % p 其中pm,m为数组规模的最大质数。,平方取中法：例：325在平方后取105625中间两位，即56作为它的散列地址。,折叠法：
7、如 身份证号码：340104198805061532 先进行分组：340 104 198 805 061 532,数值分析法,直接定址法：H(k)= k 或者 H(k)= ak+b （a，b为任意正整数）,第11章 散列表,处理冲突： 开放地址法 Hi(k)=(H(k) + di ) % m，i=1,2,q qlchild;,T=T-rchild ;,找到,二叉查找树的查找如何在二叉查找树中查找给定关键字的结点？以在下图所示树中分别查找45、55、66为例来说明。由此可得到查找的判定过程。判定过程类似于二分查找的判定过程。,失败！,第12章 二叉查找树,查找算法的流程图,XP-data.key
8、,P=P-lchild;,P=P-rchild;,查找成功 return P,P!=NULL,P=T,Y,return 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 NULL; ,第12章 二叉查找树,查找的递归算法：bnode *bstsearch(bnode *T,elementtype x)
9、 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.key,P=P-lchild;,P=P-rchild;,查找成功 return P,P!=NULL,P=T,Y,return NULL;,N,第12章 二叉查找树,二叉查找树的构造： 从空树出发，依次插入各结点（作为叶子结点）。 二叉查找树中插入结点： (1)若结点的值小于根结点的值，则往左子树中插入-通过递归调用
10、插入算法来实现。 (2)若结点的值大于等于根结点的值，则往右子树中插入（递归调用）。 按此方式递归调用若干次后，可以搜索到一个空子树位置，即要插入的位置。,第12章 二叉查找树,构造过程： 依次将结点作为叶结点插入到二叉查找树中 例：以下列数据序列作为输入构造一棵二叉查找树。 100，65，88，93，145，118，138，112，188，173，42，78，20, 197,100,第12章 二叉查找树,二叉查找树的插入算法 逐个插入元素来实现构造，插入的元素作为叶子结点。void insert(bnode *,第12章 二叉查找树,二叉查找树的构造算法 void creat(bnode *
11、,第12章 二叉查找树,二叉查找树构造分析：以下列数据序列作为输入构造一棵二叉查找树。100，65，88，93，145，118，138，112，188，173，42，78，20，197平均查找长度： （1223447）/14 = 45/14,第12章 二叉查找树,二叉查找树构造分析：再看以下列数据序列作为输入构造一棵二叉查找树。 20，42，65，78，88，93，100，112，118，138，145，173，188,197 平均查找长度：（1214）/14 = 105/14,20,由此而提出平衡二叉树,第12章 二叉查找树,二叉查找树删除结点：删除二叉查找树中的结点 可分几种情况来实现 ： 叶子结点 直接删除即可 非叶子结点 顶替法 重新连接法,100,删除叶子78,100,删除非叶子42,100,删除非叶子145,12. 二叉查找树,12.2 平衡二叉树 定义：平衡二叉树是一棵二叉查找树，或者为空，或者满足以下条件：1)左右子树高度差的绝对值不大于1；2)左右子树都是平衡二叉树。平衡因子：左子树的高度减去右子树的高度， 显然，在平衡二叉树中，每个结点的平衡因子的值为-1，0或1。,
