数据结构中常见的基本结构

1、整理课件 数据结构中常见的基本结构 线性线性结构 树形树形结构 图状图状结构 集合集合结构 线性表线性表 栈栈 队列队列 串串 树和二叉树树和二叉树 图图 第第9 9章章 查找表查找表 整理课件 什么是查找？什么是查找？ 如何进行查找？如何进行查找？ 随机查阅有关的班级课程档案！随机查阅有关的班级课程档案！ 2006.12.032006.12.03是什么日子？是什么日子？评估专家进校评估专家进校 对班级课程档案进行的最为常见的对班级课程档案进行的最为常见的“操作操作”是什么？是什么？ 对同学而言： 查看、核实 现场试验 查找与现实生活的密切关系如何？查找与现实生活的密切关系如何？ 整理课件 请

2、查阅号18号同学的成绩 整理课件 整理课件 请查阅 “周丽”同学的成 绩 整理课件 整理课件 结论： 1.按照学号查找相对容易、省时 2.按照姓名查找相对费时 同样：日常生活中的查字典也是如此！ 数据存放的方式决定数据查找的方法 原因：一个有序、一个无序 整理课件 第第9章章 查找表查找表 9.1 基础知识简介基础知识简介 9.2 静态查找表静态查找表 9.3 动态查找表动态查找表 9.4 哈希表哈希表 整理课件 1.1.基本概念基本概念 若表中存在特定元素，称查找成功，应输出该记录若表中存在特定元素，称查找成功，应输出该记录 否则，称查找不成功（也应输出失败标志或失败位置）否则，称查找不成功

3、（也应输出失败标志或失败位置） 1)查找表 查找表 2)查找 查找 3)查找成功 查找成功 4)查找不成功 查找不成功 5)静态查找 静态查找 6)动态查找 动态查找 7)关键字 关键字 8)主关键字 主关键字 9)次关键字 次关键字 由同一类型的数据元素（或记录）构成的集合由同一类型的数据元素（或记录）构成的集合 查询查询(Searching)特定元素特定元素是否在表中是否在表中 只查找，不改变集合内的数据元素。只查找，不改变集合内的数据元素。 既查找，又改变（增减）集合内的数据元素既查找，又改变（增减）集合内的数据元素 记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识

4、别一个记录 ( 预先确定的记录的某种标志预先确定的记录的某种标志 ) 可以可以唯一唯一标识一个记录的关键字标识一个记录的关键字 例如例如“学号学号” 例如例如“女女” 是一种数据结构是一种数据结构 识别若干记录的关键字识别若干记录的关键字 9.1 基础知识基础知识 整理课件 2.2.对查找表经常进行的对查找表经常进行的操作操作 1）查询查询某个“特定的”数据元素是 否在查找表中； 2）检索检索某个“特定的”数据元素的 各种属性； 3）在查找表中插入插入一个数据元素； 4）从查找表中删去删去某个数据元素。 整理课件 仅作查询和检索操作的查找表。 静态查找表静态查找表 有时在查询之后，还需要将“查

5、询”结 果为“不在查找表中”的数据元素插入 到查找表中；或者从查找表中删除其 “查询”结果为“在查找表中”的数据 元素。 动态查找表动态查找表 3.3.查找表的分类查找表的分类 整理课件 9.2 静静 态态 查查 找找 表表 整理课件 数据对象数据对象D： 数据关系数据关系R： D是具有相同特性的数 据元素的集合。 数据元素同属一个集合。 ADT StaticSearchTable 1.抽象数据类型的定义抽象数据类型的定义 D是具有相同特性的数 据元素的集合。每个数每个数 据元素含有类型相同的据元素含有类型相同的 关键字关键字，可唯一标识数 据元素。 整理课件 Create( Destroy(

6、 Search(ST, key); Traverse(ST, Visit(); 基本操作基本操作 P： ADT StaticSearchTable 整理课件 typedef struct / 数据元素存储空间基址，建表时 / 按实际长度分配，0号单元留空 int length; / 表的长度 SSTable; 2.静态查找表静态查找表的顺序存储结构存储结构 ElemType *elem; elem 0 1 2 3 4 5 6 7 8 9 10 11 typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ; 整理课件 3.静态查找表的查找算法静态

7、查找表的查找算法 1)顺序查找顺序查找 即用逐一比较的办法顺序查找关键字，即用逐一比较的办法顺序查找关键字， 技巧：技巧： 把待查关键字把待查关键字key存入表头或表尾存入表头或表尾 （俗称（俗称“哨兵哨兵”），）， 即用即用逐一比较逐一比较的办法顺序查找关键字，的办法顺序查找关键字， 这显然是最直接的办法。这显然是最直接的办法。 技巧：技巧： 把待查关键字把待查关键字key存入表头或表尾存入表头或表尾 （俗称（俗称“哨兵哨兵”），这样可以加快执），这样可以加快执 行速度。行速度。 Flash动画演示 整理课件 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3

8、4 5 6 7 8 9 10 11 ST.Length ST.elem i 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length ST.elem i 60 i key=64 key=60 i 64 示例：已知静态查找表ST如下： 整理课件 int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 ST.elem0.key = key; / “哨兵” for (i=ST.le

9、ngth; ST.elemi.key!=key; -i); / 从后往前找 return i; / 找不到时，i为0 / Search_Seq 整理课件 int Search_Seq(SSTable ST, KeyType key) pd=0; / 判断标记 for (i=1;i=ST.length; i+) if (ST.elemi.key=key) pd=i; / 判断标记记录具体位置 break; return pd; / Search_Seq 实践：在上题的基础上写出从前往后找的算法 整理课件 上述顺序查找算法简单，但平均查找长 度较大，特别不适用于表长较大的查找表。 2)折半查找折半

10、查找 为此引入折半查找算法 先给数据排序（例如按升序排好），形 成有序表，然后再将key与中间元素相比，若 key小，则缩小至左半部内查找； 为此引入折半查找算法 先给数据排序（例如按升序排好），形 成有序表，然后再将key与中间元素相比，若 key小，则缩小至左半部内查找；若key大， 则缩小至右半部内查找； 为此引入折半查找算法 先给数据排序（例如按升序排好），形 成有序表，然后再将key与中间元素相比，若 key小，则缩小至左半部内查找；若key大， 则缩小至右半部内查找；再取其中值比较， 每次缩小1/2的范围，直到查找成功或失败为 止。 整理课件 05 13 19 21 37 56 6

11、4 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elem ST.length 例如例如: key=64 的查找过程如下： lowhigh mid low mid high mid low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2 整理课件 int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值 while (low = high) mid = (low + high) / 2; if （EQ (key , ST.

12、elemmid.key) ) / return mid; / 找到待查元素 else if ( LT (key , ST.elemmid.key) ) / data.key=key) return(T); else if (T-data.keykey) return(SearchBST (T-lchild, key) ); else return(SearchBST (T-rchild, key) ); / SearchBST 整理课件 根据动态查找表的定义，“插入插入” 操作在操作在查找不成功查找不成功时才进行时才进行； 4二叉排序树的插入算法二叉排序树的插入算法 若二叉排序树为空树空树，则

13、新插入的 结点为新的根结点新的根结点；否则，新插入 的结点必为一个新的叶子结点新的叶子结点，其 插入位置插入位置由查找过程得到。 这样算法需要改进！ 整理课件 二叉排序树查找算法的改进：二叉排序树查找算法的改进： Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree / SearchBST 否则表明否则表明查找不成功查找不成功，返回，返回 / 指针指针 p 指向查找路径上访问的最后一个结点，指向查找路径上访问的最后一个结点， / 并返回函数值为并返回函数值为FALSE, 指针指针 f 指向当前访问指向当前访问 / 的结点的双亲，其初

14、始调用值为的结点的双亲，其初始调用值为NULL 整理课件 if (!T) else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) ) else p = f; return FALSE; / 查找不成功 p = T; return TRUE; / 查找成功 SearchBST (T-lchild, key, T, p ); / 在左子树中继续查找 SearchBST (T-rchild, key, T, p ); / 在右子树中继续查找 整理课件 30 20 10 40 3525 23 f T 设 key = 48 f T f

15、T 22 p f T f T T T T f f f p 整理课件 Status Insert BST(BiTree 否则，不进行插入并返回否则，不进行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST 二叉排序树的插入算法：二叉排序树的插入算法： 整理课件 s = (BiTree) malloc (sizeof (BiTNode); / 为新结点分配空间 s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入 s 为新

16、的根结点 else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s 为 *p 的左孩子 else p-rchild = s; / 插入 *s 为 *p 的右孩子 return TRUE; / 插入成功 二叉树生成二叉树生成Flash 整理课件 （1）被删除的结点是叶子； 5二叉排序树的删除算法二叉排序树的删除算法 可分三种情况讨论： 和插入相反，删除在查找成功查找成功之后进行，并 且要求在删除二叉排序树上某个结点之后，仍仍 然保持二叉排序树的特性然保持二叉排序树的特性。 （1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有 右子

17、树； （1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有 右子树； （3）被删除的结点既有左子树，也有右 子树。 整理课件 50 3080 2090 85 40 35 8832 （1）被删除的结点是叶子结点叶子结点 例如例如: 被删关键字被删关键字 = 2088 其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空” 整理课件 50 3080 2090 85 40 35 8832 （2）被删除的结点只有左子树只有左子树 或者只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树指向被删除结点的左子树或右子

18、树”。 被删关键字被删关键字 = 4080 整理课件 50 3080 2090 85 40 35 8832 （3）被删除的结点既有左子树，也有右子树既有左子树，也有右子树 40 40 以其前驱替代之，然以其前驱替代之，然 后再删除该前驱结点后再删除该前驱结点 被删结点前驱结点 （中序遍历） 被删关键字被删关键字 = 50 整理课件 50 30 80 20 90 85 40 35 88 32 （3）被删除的结点既有左子树，也有右子树既有左子树，也有右子树 40 被删关键字被删关键字 = 50 直接观察看有没有其他方法？ 整理课件 50 30 80 20 90 85 40 35 88 32 （3）

19、被删除的结点既有左子树，也有右子树既有左子树，也有右子树 40 被删关键字被删关键字 = 50 整理课件 二、平衡二叉树二、平衡二叉树 树中每个结点的树中每个结点的左、右子树深度左、右子树深度 之差的绝对值不大于之差的绝对值不大于1 。 例如例如: 5 48 2 5 48 2 1 是平衡树是平衡树不是平衡树不是平衡树 平衡 因子 1 RL hh 又称又称AVL树，是具有如下性质的二叉树：树，是具有如下性质的二叉树： 整理课件 如何构建一棵平衡二叉树？平衡二叉树？ 平衡二叉树的构建过程类似于二平衡二叉树的构建过程类似于二 叉排序树的建立过程，即在二叉排序叉排序树的建立过程，即在二叉排序 树的建立

20、过程每当插入一个结点后，树的建立过程每当插入一个结点后， 立刻检查该树是否平衡，如果平衡：立刻检查该树是否平衡，如果平衡： 继续；继续； 平衡二叉树的构建过程类似于二平衡二叉树的构建过程类似于二 叉排序树的建立过程，即在二叉排序叉排序树的建立过程，即在二叉排序 树的建立过程每当插入一个结点后，树的建立过程每当插入一个结点后， 立刻检查该树是否平衡，如果平衡：立刻检查该树是否平衡，如果平衡： 继续；继续；否则：进行相应的调整！否则：进行相应的调整！ 整理课件 构造平衡二叉树的方法： 插入、判断、平衡旋转插入、判断、平衡旋转 若在若在A的的左子树的左子树上插入左子树的左子树上插入 结点，使结点，使

21、A的平衡因子从的平衡因子从1增加至增加至 2，需要进行一次，需要进行一次顺时针旋转顺时针旋转。 (以以B为旋转轴）为旋转轴） 若在若在A的的右子树的右子树上插入右子树的右子树上插入 结点，使结点，使A的平衡因子从的平衡因子从-1增加增加 至至-2，需要进行一次，需要进行一次逆时针旋转逆时针旋转。 (以以B为旋转轴）为旋转轴） 整理课件 构造平衡二叉树的方法： 插入、判断、平衡旋转插入、判断、平衡旋转 若在若在A的的右右子树的子树的左左子树上插入子树上插入结结 点，使点，使A的平衡因子从的平衡因子从-1增加至增加至-2， 需要需要先进行先进行顺顺时针旋转，再时针旋转，再逆逆时时 针旋转针旋转。

22、(以插入的结点以插入的结点C为旋转轴）为旋转轴） 若在若在A的的左左子树的子树的右右子树上插入子树上插入 结点，使结点，使A的平衡因子从的平衡因子从1增加至增加至 2，需要，需要先进行先进行逆逆时针旋转，再时针旋转，再 顺顺时针旋转。时针旋转。 (以插入的结点以插入的结点C为旋转轴）为旋转轴） 整理课件 构造平衡二叉树的方法： 插入、判断、平衡旋转插入、判断、平衡旋转 平衡旋转的具体操作可以演绎为左右手原则！平衡旋转的具体操作可以演绎为左右手原则！ A B C A B CC A BB C A A B CB C A LL型RR型RL型LR型 C B AA C B 整理课件 0 0 1313 0

23、0 3737 0 0 2424 例例1 1：请将下面序列构成一棵请将下面序列构成一棵平衡二叉排序树平衡二叉排序树： （ 13，24，37，90，53） 0 0 1313 0 0 3737 -1-1 1313 0 0 2424 -1-1 2424 1313 需要需要RR平衡旋转平衡旋转 (绕绕B逆转逆转,B为根）为根） 0 0 9090 -1-1 2424 -1-1 3737 0 0 5353 1 1 9090 3737 需要需要RL平衡旋转平衡旋转 (绕绕C先顺后逆）先顺后逆） 0 0 3737 0 0 9090 0 0 5353 0 0 3737 0 0 9090 0 0 5353 整理课件

24、 例2: 依次插入的关键字为5, 4, 2, 8, 6, 9 5 4 2 4 25 8 6 6 58 4 2 向右旋转 一次 先向右旋转 再向左旋转 整理课件 4 26 58 9 6 4 2 8 9 5 向左旋转一次 继续插入关键字 9 依次插入的关键字为5, 4, 2, 8, 6, 9 整理课件 一、一、哈希表是什么？哈希表是什么？ 二、哈希函数的构造方法哈希函数的构造方法 三、处理冲突的方法处理冲突的方法 四、哈希表的查找哈希表的查找 9.4 哈希表哈希表 整理课件 一、哈希表是什么？哈希表是什么？ 前面介绍的所有查找都是基于待查前面介绍的所有查找都是基于待查 关键字与表中元素进行比较而实

25、现的查关键字与表中元素进行比较而实现的查 找方法，查找的效率依赖于查找过程中找方法，查找的效率依赖于查找过程中 所进行的比较次数。理想的情况是希望所进行的比较次数。理想的情况是希望 不经过任何比较，一次便能得到所查记不经过任何比较，一次便能得到所查记 录。录。 哈希表哈希表 它既是一种查找方法，它既是一种查找方法， 又是一种存贮方法又是一种存贮方法 整理课件 哈希表：哈希表：即散列存储结构。即散列存储结构。 散列法存储的基本思想：散列法存储的基本思想：建立关键码字与其存储位置的建立关键码字与其存储位置的对应对应 关系，关系，或者说，由关键码的值决定数据的存储地址。或者说，由关键码的值决定数据的

26、存储地址。 优点：优点：查找速度极快（查找速度极快（O(1)O(1)）, ,查找效率与元素个数查找效率与元素个数n n无关！无关！ 例如：例如：有数据元素序列有数据元素序列(14(14，2323，3939，9 9，2525，11)11)，若规定每，若规定每 个元素个元素k k的存储地址的存储地址H H（k k）k k，请画出存储结构图。，请画出存储结构图。 （注：（注：H H（k k）k k称为散列函数）称为散列函数） 解：解：根据散列函数根据散列函数H H（k k）k k ，可知元素，可知元素1414应当存入地址为应当存入地址为 1414的单元，元素的单元，元素2323应当存入地址为应当存入

27、地址为2323的单元，的单元， 对应散列存储表（哈希表）如下：对应散列存储表（哈希表）如下： 地址地址 9 11 14 23 24 25 39 内容内容整理课件 选取某个函数，依该函数按关键字计算元素的存储位置，选取某个函数，依该函数按关键字计算元素的存储位置， 并按此存放；并按此存放；查找时，由同一个函数查找时，由同一个函数对给定值对给定值k k计算地址，计算地址， 将将k k与地址单元中元素关键码进行比较，确定查找是否成与地址单元中元素关键码进行比较，确定查找是否成 功。功。 通常关键码的集合比哈希地址集合大得多，因而经通常关键码的集合比哈希地址集合大得多，因而经

28、 过哈希函数变换后，过哈希函数变换后，可能将不同的关键码映射到同可能将不同的关键码映射到同 一个哈希地址上一个哈希地址上，这种现象称为，这种现象称为冲突冲突。 2.若干术语若干术语 哈希方法哈希方法 ( (杂凑法杂凑法) ) 哈希函数哈希函数 ( (杂凑函数杂凑函数) ) 哈希表哈希表 ( (杂凑表杂凑表) ) 冲冲 突突 哈希方法中使用的转换函数称为哈希方法中使用的转换函数称为哈希函数哈希函数( (杂杂 凑函数凑函数) ) 按上述思想构造的表称为按上述思想构造的表称为哈希表哈希表( (杂凑表杂凑表) ) 整理课件 有有6个元素的关键码分别为：（个元素的关键码分别为：（14，23，39，9，2

29、5，11）。）。 选取关键码与元素位置间的函数为选取关键码与元素位置间的函数为H(k)=k mod 7 通过哈希函数对通过哈希函数对6 6个元素建立哈希表：个元素建立哈希表： 25 3923 9 14 6个元素用个元素用7个个 地址应该足够地址应该足够! H(14)=14%7=011 H(25)=25%7=4 H(11)=11%7=4 0 1 2 3 4 5 6 整理课件 二、构造哈希函数的方法构造哈希函数的方法 对数字数字的关键字可有下列构造方法： 若是非数字关键字非数字关键字，则需先需先对其进行进行 数字化处理数字化处理。 1. 直接定址法直接定址法 3. 平方取中法平方取中法 5. 除留

30、余数法除留余数法 4. 折叠法折叠法 6. 随机数法随机数法 2. 数字分析法数字分析法 整理课件 哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b 1. 直接定址法直接定址法 此法仅适合于：此法仅适合于： 地址集合的大小地址集合的大小 = = 关键字集合的大小关键字集合的大小 整理课件 此方法仅适合于：此方法仅适合于： 能预先估计出预先估计出全体关键字的每一位上每一位上 各种数字出现的频度数字出现的频度。 2. 数字分析法数字分析法 假设关键字集合中的每个关键字都是 由 s 位数字组成 (u1, u2, , us)，分析关 键字集中的全体， 并

31、从中提取分布均匀 的若干位或它们的组合作为地址。 整理课件 以关键字的平方值的中间几位作为存 储地址。求“关键字的平方值” 的目的 是“扩大差别” ，同时平方值的中间各 位又能受到整个关键字中各位的影响。 3. 平方取中法平方取中法 此方法适合于此方法适合于: 关键字中的每一位都有某些数字重复 出现频度很高的现象。 整理课件 将关键字分割成若干部分，然后取它 们的叠加和为哈希地址。有两种叠加处 理的方法：移位叠加移位叠加和间界叠加间界叠加。 4. 折叠法折叠法 此方法适合于此方法适合于: 关键字的数字位数特别多。 整理课件 5. 除留余数法除留余数法 设定哈希函数为设定哈希函数为: H(key

32、) = key MOD p 其中其中， pm ( (表长表长) ) 并且并且 p 应为不大于应为不大于 m 的素数的素数 或是或是 不含不含 20 以下的质因子以下的质因子 整理课件 6.随机数法随机数法 设定哈希函数为设定哈希函数为: H(key) = Random(key) 其中，其中，Random 为伪随机函数为伪随机函数 通常，此方法用于对长度不等的关键 字构造哈希函数。 注意：实际造表时总的原则是使产生冲突总的原则是使产生冲突 的可能性降到尽可能地小的可能性降到尽可能地小。 整理课件 三、处理冲突的方法处理冲突的方法 “处理冲突处理冲突” 的实际含义是： 为产生冲突的地址寻找下一个寻

33、找下一个哈希地址。 1. 开放定址法开放定址法 2. 链地址法链地址法 整理课件 为产生冲突的地址为产生冲突的地址 H(key) H(key) 求得一个地址序列：求得一个地址序列： H H0 0, H, H1 1, H, H2 2, , H, , Hs s 1 sm-11 sm-1 其中：其中：H H0 0 = H(key) H = H(key) Hi i = ( H(key) + = ( H(key) + d di i ) MOD m ) MOD m i=1, 2, , s i=1, 2, , s 1. 开放定址法开放定址法 其中：对增量其中：对增量 d di i 有三种取法 有三种取法 1

34、) 1) 线性探测再散列线性探测再散列 d di i = c = c i i 最简单的情况最简单的情况 c=1c=1 2) 2) 二次探测再散列二次探测再散列 d di i = 1 = 12 2, -1, -12 2, 2, 22 2, -2, -22 2, , , 3) 3) 随机探测再散列随机探测再散列 d di i 是一组伪随机数列是一组伪随机数列 或者或者 d di i=i=iH H2 2(key) (key) ( (又称双散列函数探测又称双散列函数探测) ) 整理课件 例如例如: 关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 设定设定哈希函数 H(

35、key) = key MOD 11 ( 表长=11 ) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 190123 145568 190123 1468 2+4 若采用线性探测再散列线性探测再散列处理冲突 若采用二次探测再散列二次探测再散列处理冲突 11 8236 55 11 (0-1)mod 11 8236 1 1 2 1 3 6 2 5 1 Flash演示演示 整理课件 将所有哈希地址相同的记录 都链接在同一链表中。 2. 链地址法链地址法 0 1 2 3 4 5 6 14 0136 1982 23 11 68 55 ASL=(61+22+3)

36、/9=13/9 例如:同前例的关键 字，哈希函数为 H(key)=key MOD 7 Flash演示演示 整理课件 查找过程和造表过程一致。假设采用 开放定址处理冲突，则查找过程查找过程为： 四、哈希表的查找哈希表的查找 对于给定值 K， 计算哈希地址 i = H(K) 若若 ri = NULL 则查找不成功 若若 ri.key = K 则查找成功 否则否则 “求下一地址 Hi” ，直至 rHi = NULL (查找不成功) 或 rHi.key = K (查找成功) 为止。 整理课件 1. 顺序表顺序表和有序表有序表的查找方法。 3. 熟练掌握哈希表的构造方法。 2.熟练掌握二叉排序树、二叉排序树、平衡二叉树二叉树 的构造和查找方法