数据结构(C描述)电子教案第8章

《数据结构(C描述)电子教案第8章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章查找数据结构（C++描述）目录8．4散列查找8．3树表查找8.1查找的基本概念8．2线性表的查找退出8.1查找的基本概念查找，也称为检索。在我们日常生活中，随处可见查找的实例。如查找某人的地址、电话号码；查某单位45岁以上职工等，都属于查找范畴。本书中，我们规定查找是按关键字进行的，所谓关键字(key)是数据元素(或记录)中某个数据项的值，用它可以标识(或识别)一个数据元素。例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。但有些关键字不能唯一标识一个数据元素，而有的关键字可以唯一标识一个

2、数据元素。如刚才的考生信息中，姓名不能唯一标识一个数据元素(因有同名同姓的人)，而考号可以唯一标识一个数据元素(每个考生考号是唯一的，不能相同)。我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。有了主关键字及关键字后，我们可以给查找下一个完整的定义。所谓查找，就是根据给定的值，在一个表中查找出其关键字等于给定值的数据元素，若表中有这样的元素，则称查找是成功的，此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置；若表中不存在这样的记录，则称查找是不成功的，或称查找失败，并可给出相应的提示。

3、因为查找是对已存入计算机中的数据所进行的操作，所以采用何种查找方法，首先取决于使用哪种数据结构来表示“表”，即表中结点是按何种方式组织的。为了提高查找速度，我们经常使用某些特殊的数据结构来组织表。因此在研究各种查找算法时，我们首先必须弄清这些算法所要求的数据结构，特别是存储结构。查找有内查找和外查找之分。若整个查找过程全部在内存进行，则称这样的查找为内查找；反之，若在查找过程中还需要访问外存，则称之为外查找。我们仅介绍内查找。要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡

4、量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL=，其中Ｐi为查找第i个元素的概率，且=1。一般情形下我们认为查找每个元素的概率相等，Ｃi为查找第i个元素所用到的比较次数。要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL=，其中Ｐi为查找第i个元素的概率，且=1。一般情形下我们认为查找每个元素的概率相等，Ｃi为查找第i个元素所用到的比较次数。8

5、．2线性表的查找8.2.1顺序查找1．顺序查找的基本思想顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值Ｋ相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于Ｋ的元素，则查找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。下面以顺序表的形式来描述算法。2．顺序查找算法实现constintn=maxn//n为表的最大长度structnode{…e

6、lemtypekey;//key为关键字，类型设定为elemtype};intseqsearch(nodeR[n+1],elemtypek)//在表Ｒ中查找关键字值为Ｋ的元素{R[0].key=k;inti=n;//从表尾开始向前扫描while(R[i].key!=k)i--;returni;}在函数seqsearch中，若返回的值为０表示查找不成功，否则查找成功。函数中查找的范围从Ｒ[n]到Ｒ[１]，Ｒ[０]为监视哨，起两个作用，其一，是为了省去判定while循环中下标越界的条件i≥1，从而节省比较时间，其二，保存要找值的副本，若查找时

7、，遇到它，表示查找不成功。若算法中不设立监视哨R[0]，程序花费的时间将会增加，这时的算法可写为下面形式。intseqsearch(nodeR[n+1]，elemtypek){inti=n;while(R[i].key!=k)&&(i>=1)i--;returni;}当然上面算法也可以改成从表头向后扫描，将监视哨设在右边，这种方法请读者自己完成。3.顺序查找性能分析假设在每个位置查找的概率相等，即有pi=1/n，由于查找是从后往前扫描，则有每个位置的查找比较次数Cn=1，Cn-1=2，…，C1=n，于是，查找成功的平均查找ASL====,

8、即它的时间复杂度为O(n)。这就是说，查找成功的平均比较次数约为表长的一半。若k值不在表中，则必须进行n+1次比较之后才能确定查找失败。另处，从ASL可知，当n较大时，ASL值较大，查找的效率