数据结构教案78docx.docx
- 文档编号:13367146
- 上传时间:2023-06-13
- 格式:DOCX
- 页数:19
- 大小:156.22KB
数据结构教案78docx.docx
《数据结构教案78docx.docx》由会员分享,可在线阅读,更多相关《数据结构教案78docx.docx(19页珍藏版)》请在冰点文库上搜索。
数据结构教案78docx
第7章查找
1.
教学
目的
要求
理解查找的基本概念和术语
2.掌握线性表的顺序查找和二分法查找方法及算法实现。
3.掌握二叉排序树的生成和查找方法。
4.掌握散列表的构造方法、查找过程及解决冲突的方法。
教学重点基于线性表的查找方法;二叉排序树;散列表
教学难点平衡二叉树;哈希表处理冲突的方法
教学环境多媒体教室
教学内容备注
7.1基本概念与术语
以学生信息表为例,来讨论计算机中查找相关的概念。
关建字关疑码次关健码数据项(字段)
\///
姓哲
性别
专'业
年级
<000801
何文颖
女
计算机科学与技术
2000级
敏疝000802
愁胜利
舆
数学与应用数学
2000级
000803
男
信息与计蔑科学
2000级
010601
刘丽
女
计算机科学与技术
2001级
图7-1关键字、关键码
1.数据项(也称项或字段)
2.数据元素(记录)
3.关键字
4.查找
5.查找表
6.静态查找表:
仅对查找表进行查找操作,而不能改变的表;
7.动态查找表:
查找的同时对表修改(如插入和删除)。
平均查找长度ASL定义为:
n
AS£=p&+p2c2+•••+pncn=ZPQ
i=l
7.2线性表查找
顺序查找又称线性查找,是最基本的查找方法之一。
顺序查找的特点是:
从表的任一端开始逐个与给定值相比较,若相等,则查找成功。
intSeqSearch(NodeTypea[],intk)
{inti;
a[0]=k;
for(i=l;i〈n;i++)//数据元素从下标为1的数组单元开始存放,所以i的初值是1
if(a[i].key==k)
returni+1;/*因数组下标从0开始,位号要+1*/
return-1;
}
7.2.2折半查找
称二分查找(BinarySearch),折半查找对待查的线性表有两个要求:
(1)必须采取顺序存储结构;
(2)必须按关键字大小排序的有序表。
二分查找过程:
取表的中间记录关键字与查找key进行比较,三种情况:
相等:
查找成功;
小于:
要查找的记录只可能在表的后半部分;
大于:
要查找的记录只可能在表的前半部分。
经过一次比较就可将查找范围缩小一半。
如此反复进行,直到找到定关键字key记录,查找成功;当前查找范围为空,查找失败。
折半查找的过程可描述为:
(1)low—1;high=length
(2)若low>high,则查找失败
⑶.low+high
mid=
L2_
若key 若key>L.r[mid].key,贝ljlow—mid+1,转⑵ 若key—L.r[mid].key,则查找成功,返回mid 其中,low和high分别指示查找区间的起始位置和相终止位置,mid示中间元素的位置。 intBin_Search(NodeTypea[],intk) (intlow=l,high=n,mid;//n是顺序表的长度 while(low<=high) (mid=(low+high)/2; if(k==a[mid].key)returnmid; elseif(k elselow=mid+l; } return0; 7.2.3分块查找 分块查找又称索引顺序查找。 是对顺序查找的一种改进。 这种查找方中除了表本身以外尚需建立一个索引表。 查找过程分两步: 首先在索引表确定待查记录所在的块;然后,在块中按顺序查找。 由于索引表中的关键递增有序,且是顺序存储可以用折半查找,块中记录只能用顺序查找。 图7-4一棵二叉排序树 7.3二叉排序树 当表的插入删除操作频繁时,需要移动表中很多结点,可采用二叉排序树来进行查找和修改操作的方法。 7.3.1二叉排序树定义 二叉排序树又称为二叉查找树,它是一种特殊结构的二叉树,其定义为: 1、二叉排序树定义: 满足以下三个性质的二叉树。 1若它的左子树非空,则左子树上所有结点的值均小于根结点的值; 2若它鬲右子亦非空,则右子树上所有结点的值均大于根结点的值; 3左、右子树本身又各是一棵二叉排序树。 1.二叉排序树的插入和生成 二叉排序树中插入一个结点的过程: (1)二叉排序树T为空,则为待插入的关键字kx申请一个新结点,并令其为根; (2)若二叉排序树T非空,将key和根的关键字比较,若小于则将key插入根的左子树中,否则插入根的右子树中。 如: 记录的关键码序列为{63,92,70,50,60,43,98}构造一棵二叉排序树的过程如下: 7.3.3二叉排序树删除操作 从二叉排序树中删除1个结点之后,使其仍能保持二叉排序树的特性即可。 即删除1个结点相当于删去有序序列中的一个结点为。 分三种情况: 1)p结点是叶子,只将p的双亲parent中指向p的指针域置空即可。 2)若p结点只有1个孩子,只将child和p的双亲直接连接,删去p。 3)p结点有两个孩子,寻找p结点中序的后继结点q替代p结点。 7.3.4二叉排序树的查找 二叉排序树可看做是一有序表,其查找过程与二分查找类似,也是一个逐步缩小查找范围的过程。 首先将要查找的值与根结点比较,如果相等,算法可终止,如比根结点小则到左子树查,否则查右子树。 7.4哈希表查找 7.4.1哈希表与哈希方法 哈希法又称散列法、杂凑法以及关键字地址计算法等,相应的表称为哈希表。 哈希函数: 通过一个函数把记录的关键字转换成内存中可以使用的地址号,称这个函数为哈希函数。 哈希表: 按哈希函数把记录的关键字转换成内存中可以使用的地址号,按这个思想建立的表称为哈希表。 7.4.2哈希函数的构造方法 什么是“好”的哈希函数? 若对于关键字集合中的任一个关键字,经哈希函数映像到地址集合中任何一个地址的概率是相等的,则称此类哈希函数为均匀的哈希函数。 构造哈希函数的原则: 1函数本身便于计算; 2计算出来的地址分布均匀,即对任一关键字k,H(k)对应不同地址的概率相等,目的是尽可能减少冲突 常用的构造哈希函数的方法有: 1.直接定址法 取关键字或关键字的某个线性函数值为哈希地址。 艮" H(key)—key或H(key)—a•key十b 其中a和b为常数(这种哈希函数叫做自身函数)o 2.数字分析法 假设关键字是以r为基的数(如: 以10为基的十进制数),并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。 3.平方取中法 取关键字平方后的中间几位为哈希地址。 这是一种较常用的构造哈希函数的方法。 通常在选定哈希函数时不一定能知道关键字的全部情况, 取其中哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的。 取的位数由表长决定。 4.折叠法 将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法。 关键字位数很多,而且关键字中每一位上数字分布大致均匀时,可以采用折叠法得到哈希地址。 7.4.3处理冲突的方法 冲突: 是指不同的关键字经过同一个哈希函数,转换成内存中同一个地址号。 常用的解决冲突方法有以下四种: 1.开放定址法 这种方法实际上是利用下面的计算公式重新求地址: Hi=(H(key)+di)%mi-1,2---k(kWmT) 其中: H(key)为用哈希函数计算得到的地址号(但)已被其他记录占用;m为哈希表的长度;di为增量序列,可有下列三种取值方法: di=1,2,3…,mT,称线性探测再散列; di=r,-1%22,-22,32,…士k2(kWm/2)称二次探测再散列; di为伪随机序列,称伪随机探测再散列; 2.2)二次探测法 Hi=(H(key)±di)%m 在同义词产生地址冲突时计算另一个哈希函数地址,直到冲突不再发生。 这种方法不易产生“聚集”,但增加了计算的时间。 (2)拉链法 换一下思路,为什么有冲突就要换地方,能不能在原地解决。 拉链法就是在原地想办法解决冲突问题。 是将相同的关键字链接形成一个单链表,每个单链表第一个结点的地址对应存储在散列表相应的存储单元中。 (3)建立一个公共溢出区 (4)哈希表的查找分析 7.5应用举例 【例7-4】利用二分法查找实现学生信息查询模块设计。 第8排序 课题 第8排序章节 课时 教学 目的 要求 1.掌握排序的概念与分类 2.掌握各种排序算法的基本思想 3.掌握一般排序算法的设计与实现 4.掌握排序算法的效率分析 教学重点 插入排序;交换排序;选择排序 教学难点 快速排序;堆排序 教学环境 多媒体教室 教学内容 备注 8.1概述 排序又称分类,如淘宝按价格从高到低,经常用排序查找商品。 稳定排序与不稳定排序: 按关键字进行排序: 若相同关键字的元素间的位置关系,排序前与排序后保持一致,称此排序方法是稳定的;而不能保持排序前后一致的排序方法。 称此排序方法是不稳定的; 8.2插入排序 插入排序有: 直接插入排序、希尔排序。 8.2.1直接插入排序 直接插入排序是一种最基本的插入排序方法。 基本操作是将第i个记录插入到前面i-1个已排好序的记录中。 直接插入排序示例 排序记录存放在r[l..n]之中,为了提高效率r[0]为哨兵。 哨兵作用有两个: 一是备份待插入的记录;二是避免数组下标出界。 Insert_Sort(inta[],intn) (inti,j,temp; for(i=l;i (temp=a[i]; j=i-l;/*从右向左在有序区中找a[i]的插入位置*/ while(j>=0&&temp (a[j+l]=a|j];j-;)/*将关键字>a[i].key记录后移*/ a[j+l]=temp;/*在j+1处插入a[i]*/ }.. } 最好情况下: 即待排序列已按关键字排列有序,每趟操作只需1次比较不需要移动。 最坏情况下: 即第j趟操作,插入记录需要同前面的j个记录进行j 次关键字比较,移动记录的次数为j+2次。 8.2.2希尔排序排序 希尔排序也是一种插入排序方法,实际上是一种分组插入方法。 初始状态9876543210(连线部分为下一趟作准备) I~I~~~~~IIII d=5 4321098765(d=5执行结果) d=20 7— 6— 51 41 31 21 (d=2执行结果) d=l0123456789(d=l执行结果) 算法如下: voidShell_Sort(inta[],intn)/*希尔排序算法*/ (inti,j,d,temp; d=n/2;/*d取初值n/2*/ while(d>0) (for(i=d;i (j=i-d; while(j>=0&&a[j]>a[j+d]) (temp=a[j];a[j]=a[j+d];a[j+d]=temp;/*a[j]与a[j+d]交换*/j=j-d; } } d=d/2;/*递减增量d*/ } } 8.3交换排序 8.3.1冒泡排序 冒泡排序是一种简单的交换类排序方法,通过对待排序关键字的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮"直至“水面”O {49,38,65,97,13,27,49),分别存放在a[0]~a[7]中,其排 冒泡排序算法如下: voidBubble_Sort(inta[],intn)/*冒泡排序*/ {inti,j,temp; for(i=0;i (for(j=n-l;j>i;j-)/*比较找本趟最小关键字的记录*/ if(a。 ] (temp=a[j];a[j]=a[j-l];a[j-l]=temp;}/*a[j]与进行交换*/ ) } 算法的时间复杂度为0(蚤),空间复杂度为0 (1)。 另外,冒泡排序法是一种稳定的排序方法。 8.3.2快速排序 快速排序是由冒泡排序改进而得的。 无序的记录序列 快速排序的基本思想是: 从待排序记录序列中选取1个记录,将关键字小于枢轴的记录移到前面,大于的记录移到后面。 初始状态 一次交换 r[l]r[2]r[3]r[4]r[5]r[6]r[7] 4914387496 存储单元 658记录中关键码 A 1 i Oj 二次交换 8 14 A 38 74 96 65 49A 1i-> 1 j 8 14 38 74 96 65 49 三次交换8143849966574 tt 1〈一j 8143849966574 tt iv-j 8143849966574 tt i<-j 图8-5快速排序排序过程 intPass(inta[],intx,inty)/*快速排序法*/ (inttemp=a[x],i=x+l,j=y,stemp; while(l) (while(a[j]>temp)j—; while(a[i] if(i>』)break; stemp=a[i];a[i]=a[j];a[j]=stemp; } a[x]=a[j];a[j]=temp; returnj; } 整个快速排序算法如下: voidQSort(inta[],intlow,inthigh)/*递归形式的快排序*/ (inti;」 if(low (i=Pass(a,low,high);/*将表一分为二*/ QSort(a,low,i-1);/*对低子表递归排序*/ QSort(a,i+1,high);/*对高子表递归排序*/ } 8.4选择排序 选择排序主要是每一趟从待排序列中选取一个关键字最小的记录,也即第一趟从n个记录中选取关键字最小的记录,第二趟从剩下的n-1个记录中选取关键字最小的记录,直到整个序列的记录选完。 8.4.1简单选择排序 基本思想: 第i趟简单选择排序是指通过n-i次关键字的比较,从n-i+l个记录中选出关键字最小的记录,并与第i个记录进行交换。 共需进行i-1趟比较,直到所有记录排序完成为止。 例如: 进行第i趟选择时,从当前候选记录中选出关键字最小的k号记录,并与第i个记录进行交换。 voidSelect_Sort(inta[],intn)/*直接选择排序*/ (inti,j,k,x;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 教案 78 docx