欢迎来到天天文库
浏览记录
ID:49312860
大小:432.50 KB
页数:52页
时间:2020-02-03
《计算机软件技术基础3-4 数据结构及算法(查找与排序).ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、常用数据结构及其运算第三章1§3.1概述§3.2线性表§3.3栈与队§3.4树与二叉树§3.5图§3.6查找与排序目录23.6.1查找的基本概念3.6.2静态查找技术3.6.3动态查找技术3.4.4排序基本概念3.4.5简单选择排序3.4.6插入排序3.4.7交换排序3.6查找与排序32.查找表由同一类数据构成的用于查找的集合被称作查找表。查找表是具有一定存储结构的数据集合,比如顺序表结构、链式结构、树形结构等。3.关键字查找往往根据数据元素的某个属性进行。例如根据学号查找某个学生记录。这种被用于查找的元素属性一般称为关键字,它往往可以唯一标识一个元素。3.6.1查找的基本概念1.什么是
2、查找确定给定值k在含有n个记录的文件中的位置的过程称为查找。44.静态查找表查找表一旦建立,在以后的查找过程中就不会改变。它所对应的查找算法属于静态查找技术。5.动态查找表:查找表建立后,在后来的查找过程中仍会改变查找表的内容。它所对应的查找算法属于动态查找技术。动态查找的例子——词汇统计问题。就是统计一篇文章中使用了多少词汇以及每个词汇的使用次数。解决方法是先建立一个空的查找表,以后每读到一个词就在查找表中查询一下,如果该词汇存在则将其使用次数加一,否则将新词插入到查找表中并设使用次数为一次。显然,这个查找表是不断扩张的。3.6.1查找的基本概念56.平均查找长度:为了确定数据元素在
3、查找表中的位置,需要将给定值和表中的数据元素的关键字进行比较的次数的期望值。平均查找长度ASL的计算方法为:n为表长;Pi为查找第i个元素的概率。Ci为找到该记录时,曾和给定值比较过的数据元素的个数。在等概率条件下(Pi=1/n)这时平均查找长度为:其中:3.6.1查找的基本概念6假设静态顺序查找表的存储结构为:structSSTable{ElemType*data;//存储空间地址intlength;//表的长度};顺序查找表的元素存放在data[0]至data[length-1]中。3.6.2静态查找技术71.顺序查找顺序查找的方法是从表的一端开始,逐一比较给定的数据key和表中数据
4、元素的关键字x的值,若两个数据一致则查找成功,同时给出该数据元素在表中的位置,否则查找失败。3.6.2静态查找技术8顺序查找算法C++语言描述如下:intSqSearch(SSTable&L,KeyTypekey){intk=0;while(k5、法的执行时间几乎增加一倍。为提高效率,对查找表的结构改动如下:适当设置数组长度,将元素存于data[1]至data[length-1]中,在0号单元预存待查找数据key作为监视哨。改写查找过程为从后往前查找。因为循环查找过程至少会在0号单元停止,这样就不必在每一次循环中都判别是否数组出界。3.6.2静态查找技术10改进的顺序查找算法C++语言描述如下:intSqSearch(SSTable&L,KeyTypekey){L.data[0].x=key;//监视哨intk=L.length;while(L.data[k].x!=key)k=k-1;//从后往前找returnk;//找不到时,6、k为0}该算法若查找成功,则函数返回值为目标元素在表中的位置,否则返回0。3.6.2静态查找技术11下面分析一下改进的顺序查找算法的时间性能。对于改进的顺序查找而言,找到第i个元素的比较次数Ci=n-i+1,所以在等概率查找的情况下,顺序表查找的平均查找长度为:3.6.2静态查找技术122.折半查找(也称二分查找)顺序查找表的查找算法简单,但平均查找长度较大。如果顺序查找表的元素按照关键字的值有序存放,那么可利用高效的折半查找来完成查询。假定元素按关键字的值升序排列,折半查找的思路是将给定的数据与有序表中间位置的元素做比较,若两者相等则查找成功;若前者小于后者则在中间位置左边的元素中继续7、查找;若前者大于后者则在中间位置右边的元素中继续查找。不断重复这一过程直到查找成功,或者直到查找区间缩小为一个元素时却仍未找到目标,则查找失败。3.6.2静态查找技术13折半查找算法的步骤描述如下:①设置查找区间初值,设下界low=0,设上界high=length-1。②若low≤high则计算中间位置mid=(low+high)/2。③若keydata[mi
5、法的执行时间几乎增加一倍。为提高效率,对查找表的结构改动如下:适当设置数组长度,将元素存于data[1]至data[length-1]中,在0号单元预存待查找数据key作为监视哨。改写查找过程为从后往前查找。因为循环查找过程至少会在0号单元停止,这样就不必在每一次循环中都判别是否数组出界。3.6.2静态查找技术10改进的顺序查找算法C++语言描述如下:intSqSearch(SSTable&L,KeyTypekey){L.data[0].x=key;//监视哨intk=L.length;while(L.data[k].x!=key)k=k-1;//从后往前找returnk;//找不到时,
6、k为0}该算法若查找成功,则函数返回值为目标元素在表中的位置,否则返回0。3.6.2静态查找技术11下面分析一下改进的顺序查找算法的时间性能。对于改进的顺序查找而言,找到第i个元素的比较次数Ci=n-i+1,所以在等概率查找的情况下,顺序表查找的平均查找长度为:3.6.2静态查找技术122.折半查找(也称二分查找)顺序查找表的查找算法简单,但平均查找长度较大。如果顺序查找表的元素按照关键字的值有序存放,那么可利用高效的折半查找来完成查询。假定元素按关键字的值升序排列,折半查找的思路是将给定的数据与有序表中间位置的元素做比较,若两者相等则查找成功;若前者小于后者则在中间位置左边的元素中继续
7、查找;若前者大于后者则在中间位置右边的元素中继续查找。不断重复这一过程直到查找成功,或者直到查找区间缩小为一个元素时却仍未找到目标,则查找失败。3.6.2静态查找技术13折半查找算法的步骤描述如下:①设置查找区间初值,设下界low=0,设上界high=length-1。②若low≤high则计算中间位置mid=(low+high)/2。③若keydata[mi
此文档下载收益归作者所有