《常用软件算法基础》课件-第8章 学生信息查找

第八章学生基本信息查找内容目标：查找的基本概念。顺序查找案例分析折半查找案例分析索引查找案例分析哈希查找案例分析重难点：各类查找的原理和实现1.功能描述学生基本信息表：1.功能描述学生基本查找界面设计如下：2.查找的基本概念查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素关键字——是数据元素中某个数据项的值，它可以标识一个数据元素查找方法评价查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的平均查找长度2.查找的基本概念查找表：在进行查找运算的数据元素通常是同一类型的数据元素或记录，由它们构成的集合称为查找表。静态查找表：仅对查找表进行查找操作，即查找关键字等于给定值的数据元素是否在查找表中，查找前后不能改变表。动态查找表：对查找表除进行查找操作外，可能还要向表中插入数据元素，或删除表中数据元素的表。3.1.1业务实现---顺序查找基本思想是：从查找表的一端开始逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。将整个学生成绩表，以关键字姓名来看是无序的查找表。依次从查找表中取出一条记录，将其中的姓名关键字与所要查找的关键字姓名K进行比较。如果找到与给定值K一致的关键字，返回查找成功，否则继续查找，若在查找表查找完毕仍未找到，返回查找失败。3.1.2业务实现---顺序查找流程图3.1.3业务实现---顺序查找学生基本信息顺序表查找类：publicclassSxb{ publicstringKey; publicStudentData; publicSxb(stringName,intNum,intcj) { Key=Name; Data=newStudent(Name,Num,cj); }}3.1.4业务实现---顺序查找构建顺序查找业务类：用以实现学生基本信息，按学生姓名进行顺序查找的业务类，具体的成员和方法实现如下：publicclassSx_Search{ publicStudent_info[]sx; //初始的学生信息表

publicSxb[]sxb; //用以查找的学生信息查找表

publicintMax; //记录学生信息的最大长度

publicintseach_times=0; //记录每次查找次数

publicStudentMangerBa=newStudentManger();//创建数据控制层对象

publicSx_Search() { Init(); }publicvoidInit(){}//初始化查找表

publicintshunxu_all()//实现所有学生查询统计

publicintshunxu(StringK，Student_infoElem){}//实现单个学生信息查询}

3.1.5业务实现---顺序查找学生信息表和查找表的初始化：进行学生基本信息数组和学生基本信息查找表类的初始化，具体的代码实现如下： publicvoidInit() { Max=Ba.Max; sx=newStudent_info[Max];//初始化学生信息数组

sxb=newSxb[Max];//初始化顺序查找表

for(inti=0;i<Max;i++)//逐个初始化学生信息数组元素

{ sx[i]=Ba.base_info[i]; sxb[i]=newSxb(sx[i]);//初始化顺序查找表中每个元素

} }

3.1.6业务实现---顺序查找单个学生信息查询实现该方法实现对输入学生的姓名信息关键字，在顺序查找表中进行查找，若查找到，返回所找到学生的全部信息以及在顺序查找表中的位置，并记录该姓名查找所进行循环的次数，具体实现代码如下：publicintshunxu(StringK,Student_infoElem){//进行顺序查找，输入参数是要查找的姓名和要返回的学生对象引用；返回所要查找的位置，若查找不成功返回-1 intn; seach_times=0; for(n=0;n<Max;n++)//循环逐个进行关键字比较

{ seach_times++;//记录查找过程所循环的次数

if(sxb[n].Key.equals(K))//查找成功，获取找到的学生对象并返回具体位置

{ Elem=sxb[n].Data; return-1; } } if(n>=Max)//当查找表照完，仍未找到，返回-1 n=-1; returnn;}

3.1.7业务实现---顺序查找所有学生信息查询所需次数统计：该方法实现顺序操作表中所有学生的信息查找的循环次数的累计（即记录有效查找的总次数）。代码实现如下： publicintshunxu_all() {//获取总的查找次数

inttimes=0; for(inti=0;i<Max;i++) { shunxu(sx[i].st_name,sx[i]); times=times+seach_times; } returntimes; }

3.1.8业务实现---顺序查找时间复杂度：3.2.1业务实现---折半查找二分查找又称为折半查找，它是一种效率较高的查找方法。其基本思想为：首先：设查找表的元素存储在一维数组r[1]…r[n]中，表中的元素已经按学生序号关键字递增（或递减）的方式排好序。然后：将待查值k与有序表r[1]到r[n]的中点位置上的关键字r[mid].key进行比较，比较结果有三种可能：若r[mid].key>k，说明若存在要查找的元素，该元素一定在数组的前半部分，从而查找范围缩小了一半，修改查找范围的上界n=mid-1，继续对数组的前半部分进行二分查找。若r[mid].key<k，说明若存在要查找的元素，该元素一定在数组的后半部分，从而查找范围缩小了一半，修改查找范围的下界为mid+1，继续对数组的后半部分进行二分查找。若r[mid].key=k，说明查找成功，mid所指元素即为要查找的数据。最后：这重复以上过程，查找范围每次缩小1/2，当查找范围变为空时，表示查找失败。3.2.2业务实现---折半查找流程图3.2.3业务实现---折半查找构建学生基本信息折半查找表类：折半查找类用以实现折半查找表信息的封装，主要的属性包括：查找关键字（学生的序号）、要查找的学生元素信息，具体实现如下：publicclassZbb{//折半查找结点类

publicintKey; //查找关键字，用以记录学生序号

publicStudent_infoData;//学生信息元素

publicZbb(Student_infoelem) { Key=elem.st_id; Data=elem; }}

3.2.4业务实现---折半查找构建折半查找业务类：用以实现学生基本信息查找，按学生序号进行折半查找的业务类，具体的成员和方法实现如下：publicclassZb_Search{publicStudent_info[]sx; //初始的学生信息表publicZbb[]zbb; //用以查找的学生信息查找表publicStudentMangerBa=newStudentManger();//创建数据控制层对象publicintMax; //记录学生信息的最大长度publicintseach_times=0; //记录每次查找次数publicZb_Search(){ Max=Ba.Max; sx=newStudent_info[Max]; //初始化学生信息数组

zbb=newZbb[Max]; for(inti=0;i<Max;i++) //逐个初始化学生信息数组元素

{sx[i]=Ba.base_info[i]; //初始化学生信息数组的每个元素

zbb[i]=newZbb(Ba.base_info[i]);//初始化学生信息查找表的每个元素

}}publicvoidInit(){}//初始化折半查找表publicintzb_all()//实现所有学生折半查找统计publicintzb_Search(intK,Student_infoElem){}//实现单个学生信息折半查找

}

3.2.5业务实现---折半查找单个学生信息折半查找实现该方法实现对输入学生的序号信息关键字，在折半查找表中进行查找，若查找到，返回所找到学生的全部信息以及在折半查找表中的位置，并记录该姓名查找所进行循环的次数，具体实现代码如下：publicintzb_Search(intK,Student_infoElem){//进行折半查找，输入参数是要查找的学号和要返回的学生对象引用；返回所要查找的位置，若查找不成功返回-1intLow=0;//赋初值inthigh=Max-1;intMid;seach_times=0;//记录查询循环次数while(Low<=high){seach_times++;//循环次数累加

Mid=(Low+high)/2; if(K==zbb[Mid].Key)//查找成功

{Elem=zbb[Mid].Data; returnMid+1; } elseif(K<zbb[Mid].Key)//在左半区进行查找

high=Mid-1; else //在右半区进行

Low=Mid+1; } return-1; //返回不失败}

3.2.6业务实现---折半查找所有学生信息查询所需次数统计：该方法利用折半查找思想，对学生信息表中所有学生信息查找一次的累计次数。代码实现如下：publicintzb_all(){//实现所有学生按序号查询时的总的查找次数

inttimes=0; for(inti=0;i<Max;i++) { zb_Search(sx[i].st_id,sx[i]); //调用单个学生的查询

times=times+seach_times; //累计求和每个学生的查询次数

} returntimes;}

3.2.7业务实现---折半查找为了分析二分查找，可以用二叉树来描述二分查找过程。例如如下的有序表{8，22，27，34，45，57，63，69，69，103}。3.2.8业务实现---折半查找3.3.1业务实现---索引查找分块查找又称为索引查找：首先将表分成若干块，每一块中的关键字不一定有序，但块之间是有序的，即后一块记录的关键字均大于前一个块中的最大关键字；此外还建立索引表，索引表按关键字有序。初看表中的学生语文成绩数据，好像没有什么规律可言，不能采用上节的折半查找来实现，只能利用顺序查找来实现，当数据量比较大时，查找效率不佳。仔细观察数据可以发现，前5个成绩小于60，中间8个在60到80之间，后面两个大于80。我们可以采用如下的策略来设计查找：首先将学生成绩表的数据分成三个区间<60;60~80,>80。其次，将所要查找的学生成绩先锁定在这三个区间当中的一个。最后，再利用顺序查找法，在所锁定的区间进行查找。3.3.2业务实现---索引查找分块查找又称为索引查找：首先将表分成若干块，每一块中的具体实现步骤如下：定义分块查找表类和索引表类。根据学生信息的特点，为查找表类和索引表类对象初始化。实现单个学生信息的索引查找：根据学生语文成绩，在索引表中使用顺序查找，锁定到相关的块。获取索引块所要查找表的上下界。利用顺序查找进行学生语文成绩的查找3.3.3业务实现---索引查找3.3.4业务实现---索引查找构建学生基本信息分块查找查找表类：publicclassblocknode{//查找表类

publicintKey;//块关键字：成绩

publicStudent_infoData;//数据元素：学生成绩信息

publicblocknode(Student_infoelem) { Key=elem.st_yw;//关键字赋值

Data=elem;//构造学生对象

}}

3.3.5业务实现---索引查找构建学生信息分块查找索引表类：publicclassindexnode{//索引表类

publicintindexKey;//索引关键字：成绩

publicintnum;//数组下标

publicindexnode(intNum,intcj) { indexKey=cj; num=Num; }}

3.3.6业务实现---索引查找构建分块查找业务类：用以实现学生基本信息，按学生的语文成绩进行分块查找的业务类，具体的成员和方法实现如下：publicclassSy_Search{publicStudent_info[]sx; //初始的学生信息表publicblocknode[]bn; //用以查找的学生信息查找表publicStudentMangerBa=newStudentManger();//创建数据控制层对象publicintMax; //记录学生信息的最大长度publicintseach_times=0; //记录每次查找次数publicindexnodeindex[]={newindexnode(0,59),newindexnode(5,79),newindexnode(13,100)};publicSy_Search() { Init(); } publicintInit(){}//初始化分块查找表publicintBlockSearch_all()//实现所有学生查询统计publicintBlockSearch(intK,intm，Student_infoElem){}//实现单个学生信息查询

}

3.3.7业务实现---索引查找学生信息表和查找表的初始化：进行学生基本信息数组和学生基本信息分块查找表类的初始化，具体的代码实现如下：publicvoidInit(){ Max=Ba.Max; sx=newStudent_info[Max]; //初始化学生信息数组

bn=newblocknode[Max]; for(inti=0;i<Max;i++) //逐个初始化学生信息数组元素

{ sx[i]=Ba.base_info[i]; //初始化学生信息数组的每个元素

bn[i]=newblocknode(Ba.base_info[i]); //初始化学生信息查找表的每个元素

}}

3.3.8业务实现---索引查找单个学生信息查询实现该方法实现对输入学生的语文成绩信息关键字，先在索引表中，找到对应的查找块，确定在查找表的上下界，利用顺序查找方法进行查找，若查找到，返回所找到学生的全部信息以及在查找表中的位置，并记录该查找所进行循环的次数，具体实现代码如下：publicintBlockSearch(intK,intm,Student_infoElem){//进行索引查找，输入参数是要查找的学生成绩、索引块大小和要返回的学生对象引用；返回所要查找的位置，若查找不成功返回-1 inti,flag;//局部变量：i用于循环，flag用于记录是否找到标志

intlow,hight;//局部变量：low查找块的下限，hight查找块的上限

i=0; flag=0; seach_times=0; while((i<m)&&(flag==0))//在索引表中查找

{ seach_times++; if(index[i].indexKey>=K) flag=1; //找到对应的索引块

else i++; }

3.3.8业务实现---索引查找单个学生信息查询实现if(flag==0)return-1;//所找数据不在相应索引块内

low=index[i].num; //为下限赋值

if(i<m-1) //为上限赋值

hight=index[i+1].num-1; //不是最后一个索引块

else hight=bn.length-1;//是最后一个索引块

flag=0; while((low<=hight)&&(flag==0))//在索引块内查找

{seach_times++; if(bn[low].Key==K) //查找成功

{ flag=1; } else low++; } if(flag!=1) return-1; //查找不成功

else { Elem=bn[low].Data; returnlow; } }

3.3.9业务实现---索引查找所有学生信息查询所需次数统计：应用索引查找的思想，对所有学生成绩信息查询一次的循环次数的累计。代码实现如下： publicintBlockSearch_all() { inttimes=0; for(inti=0;i<Max;i++) { BlockSearch(sx[i].st_sx,3,sx[i]); times=times+seach_times; } returntimes; }

3.3.10业务实现---索引查找算法分析：3.3.11查找算法比较

ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找3.4.1业务实现---哈希查找问题分析：我们从所给的查找表中的数据，以关键字联系电话，很难找到合理的规律。不能利用前面的二分查找和索引查找来解决问题。好像只能通过顺序查找来解决问题，但顺序查找很浪费时间，当数据量很大时，一个个进行比较，效率极低。我们注意观察10个学生的电话号码的末尾数各不相同，按电话号码的末尾数由小到大组成新的查找表（例如末尾数为0，对应新查找表下标为0，末尾数为1，对应新查找表下标为1，……，末尾数为9，对应下标为9）。当我们输入要查找的电话号码，取其末尾数与新查找表对应的元素进行比较（末尾数为0与下标为0的元素比较，……，末尾数为9与下标为9的元素比较）若相等则查找成功，否则查找失败（即所输入的电话号码与对应下标的电话号码不一致）。可见使用这样的查找方法只须作一次比较，就会等到结果，显然效率大大提高。3.4.2业务实现---哈希查找具体步骤如下：构建哈希查找表类。初始化学生信息数组。构建哈希函数，实现哈希表的初始化。哈希查找方法的实现。3.4.3业务实现---哈希查找构建哈希查找结点类：定义哈希查找结点类，其主要的属性如下：publicclassHaxi{ publicintKey;//块关键字：成绩

publicStudent_infoData;//数据元素：学生成绩信息

publicHaxi(Student_infoelem) { Key=elem.st_phone;//关键字赋值

Data=elem;//构造学生对象

}}

3.4.4业务实现---哈希查找哈希查找业务类：哈希查找业务类用以实现学生信息按电话号码进行查找的业务处理，代码如下：publicclassHx_Search{publicStudent_info[]sx; //初始的学生信息表publicHaxi[]hx; //学生信息顺序哈希查找表publicHaxi_Link[]hx_L; //学生信息链式哈希查找表publicStudentMangerBa=newStudentManger();//创建数据控制层对象publicintMax; //记录学生信息的最大长度publicintseach_times=0; //记录每次查找次数publicHx_Search(){ Init(); }publicvoidInit(){}//初始化学生信息表publicvoidHx_fun()//哈希函数，初始化哈希查找表publicintHx_all()//实现所有学生查询统计publicintHx_search(intK,Student_infoElem){}//实现单个学生信息哈希查询

}

3.4.5业务实现---哈希查找学生信息表的初始化：publicvoidInit(){ Max=Ba.Max; sx=newStudent_info[Max]; //初始化学生信息数组

for(inti=0;i<Max;i++) //逐个初始化学生信息数组元素

{ sx[i]=Ba.base_info[i]; //初始化学生信息数组的每个元素

}}

3.4.6业务实现---哈希查找哈希函数实现：用以实现构建哈希查找表，共哈希查找作准备。 publicvoidHx_fun() {//构建哈希函数

inti,j; hx=newHaxi[Max]; for(i=0;i<Max;i++)//逐个取出原始数据

{ j=sx[i].st_phone%10;//为每个原始数据进行哈希变换

hx[j]=newHaxi(sx[i]);//构建新的哈希表

} }

3.4.7业务实现---哈希查找哈希查找实现：给定学生的电话号码，进行哈希查找，并将查找后的结果进行返回。publicintHx_search(intK,Student_infoElem){//进行哈希查找inti;i=K%10;//对输入的关键字进行对应的哈希变换，找到对应的哈希表中的位置seach_times=0;if(hx[i].Key==K)//与哈希表对应位置的关键字进行比较

{ seach_times++; Elem=hx[i].Data; return1; //查找成功返回

} else return0; //查找失败返回}

4.1知识扩展—哈希查找定义：基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法定义哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素addr(ai)是ai的存储地址ki是ai的关键字关键字集合存储地址集合hash哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。例30个地区的各民族人口统计表编号地区别总人口汉族回族…...1北京2上海…...…...以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可冲突：key1key2，但H(key1)=H(key2)的现象叫冲突同义词：具有相同函数值的两个关键字，叫该哈希函数的同义词哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法哈希函数的构造方法直接定址法构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或H(key)=a·key+b特点直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少数字分析法构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8134653281372242813874228130136781322817813389678136853781419355…..…..

分析：只取8

只取1

只取3、4

只取2、7、5

数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址平方取中法构造：取关键字平方后中间几位作哈希地址适于不知道全部关键字情况折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况例关键字为：0442205864，哈希地址位数为4586442200410088H(key)=0088移位叠加5864022404

6092H(key)=6092间界叠加除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=keyMODp，pm特点简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产生同义词随机数法构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)适于关键字长度不等的情况选取哈希函数，考虑以下因素：计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率处理冲突的方法开放定址法方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MODm，i=1,2,……k(km-1)其中：H(key)——哈希函数

m——哈希表表长

di——增量序列分类线性探测再散列：di=1,2,3,……m-1二次探测再散列：di=1²,-1²,2²,-2²,3²,……±k²(km/2)伪随机探测再散列：di=伪随机数序列例表长为11的哈希表中已填有关键字为17，60，29的记录，

H(key)=keyMOD11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中012345678910601729(1)H(38)=38MOD11=5冲突

H1=(5+1)MOD11=6冲突

H2=(5+2)MOD11=7冲突

H3=(5+3)MOD11=8不冲突38(2)H(38)=38MOD11=5冲突

H1=(5+1²)MOD11=6冲突

H2=(5-1²)MOD11=4不冲突38(3)H(38)=38MOD11=5冲突设伪随机数序列为9，则：

H1=(5+9)MOD11=3不冲突38再哈希法方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key)i=1,2,……k其中：Rhi——不同的哈希函数特点：计算时间增加链地址法方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函数为：H(key)=keyMOD13,

用链地址法处理冲突012345678910111214^127796855198420231011^^^^^^^^^^^^哈希查找过程及分析哈希查找过程给定k值计算H(k)此地址为空关键字==k查找失败查找成功按处理冲突方法计算HiYNYN哈希查找分析哈希查找过程仍是一个给定值与关键字进行比较的过程评价哈希查找效率仍要用ASL哈希查找过程与给定值进行比较的关键字的个数取决于：哈希函数处理冲突的方法哈希表的填满因子

=表中填入的记录数/哈希表长度例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函数为：H(key)=keyMOD13,哈希表长为m=13，

设每个记录的查找概率相等(1)用线性探测再散列处理冲突，即Hi=(H(key)+di)MODmH(55)=3冲突，H1=(3+1)MOD16=4

冲突，H2=(3+2)MOD16=5H(79)=1冲突，H1=(1+1)MOD16=2

冲突，H2=(1+2)MOD16=3

冲突，H3=(1+3)MOD16=4

冲突，H4=(1+4)MOD16=5

冲突，H5=(1+5)MOD16=6

冲突，H6=(1+6)MOD16=7

冲突，H7=(1+7)MOD16=8

冲突，H8=(1+8)MOD16=90123456789101112131415ASL=(1*6+2+3*3+4+9)/12=2.514168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1冲突，H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6冲突，H1=(6+1)MOD1