数据查找顺序、二分、索引、哈希查找.doc

选题八数据查找一、基本概念查找表：是由同一类型的数据元素(或记录)构成的集合。 查找：也称检索，即根据给定的某个值，在查找表中确定一个其关键字等于给定值的第一条记录(元素)或全部记录。若表中存在这样的记录，则查找成功，通常要求返回该记录存储位置；若不存在这样的记录，表明查找失败，返回特定值。例：在下表中查找 学号为“98182”的学生信息学 号姓 名性别籍 贯出生年月198131刘激扬男北 京1979.12298164衣春生男青 岛1979.07398165卢声凯男天 津1981.02498182袁秋慧女广 州1980.10598203林德康男上 海1980.05平均查找长度：在查找成功情况下平均比较次数，可用作判定一个查找算法的时间复杂度：其中：n：查找表长；Pi：查找第i个元素；Ci：查找第i个元素比较次数。二、顺序查找1查找思路顺序表：指线性表的顺序存储结构。本章讨论中，设顺序表采用一维数组A表示，其元素类型为ElemType，它含有关键字域key和其它一些数据域，并设定A的大小为整型常量MaxSize，数组的元素个数为n，n应小于等于MaxSize。typedef struct KeyType key;ElemType;顺序查找：又称线性查找，它是一种最简单最基本查找方法。查找思路：从顺序表的一端开始，依次将每个元素关键字同给定值K进行比较，若某个元素关键字等于K，则查找成功，返回该元素所在下标，若直到所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败，反回特定值(常用-1表示)。基本算法int Seqsch(ElemType A ,int n,KeyType K) /从顺序表A的n个元素中顺序查找关键字为K的元素，若成功返回其下标，否则返回-1for(int i=0;in;i+)if(Ai.key=K)break; if(in)/查找成功返回下标，否则返回-1 return i;else return -1;如下图：0123452345643278在顺序表中查找56，比较3次。改进算法对该算法作一改进：在表的尾端An设一岗哨，在查找前先将K赋给An,这样每循环一次不需比较下标是否越界，当比较到第n位置时，由于An.key=K成立，必退出循环。 int Seqsch(ElemType A ,int n,KeyType K) /从顺序表A的n个元素中顺序查找关键字为K的元素，若成功返回其下标，否则返回-1An.key=k; /设置岗哨for(int i=0; ;i+)if(Ai.key=K)break;if(in)return i;elsereturn -1;在顺序表中查找56，设A6=56为岗哨：0123456234564327856性能描述平均查找长度为：顺序查找时间复杂度为O(n)。缺点：速度较慢，查找成功最多需比较n次，平均查找长度约为表长一半。优点：算法简单，适应面广，对表结构无任何要求。三、二分查找二分查找又称折半查找。作为二分查找对象的表必须是顺序存储的有序表。查找过程：首先取整个有序表A0An-1的中点元素Amid(mid=(n-1)/2的关键字与K比较。如下图所示：例如：查找23：查找96：查找58：1二分查找的递归算法int Binsch(ElemType A ,int low,int high,KeyType K)/在AlowAhigh内查找K,low初值为0,high初值n-1if(low=high) int mid=(low+high)/2; /求中间点下标if(K=Amid.key)return mid; /查找成功返回else if(KAmid.key)return Binsch(A,low,mid-1,K); /左子表上查找elsereturn Binsch(A,mid+1,hign,K);/右子表上查找else return -1; /查找失败反回-12二分查找的非递归算法在下面的递增有序序列中查找关键字6。四、索引查找1概念索引查找：又称分级查找，计算机中为索引查找建立一张主表和各级索引表。索引存储的基本思想是：首先把一个线性表(主表)按一定的函数关系划分成若干逻辑上的子表，为每个子表分别建立一个索引项，由所有这些索引项构成主表的一个索引表，然后可采用顺序或链接方式存储索引表和子表。职工号姓名单位职称工资JS001王大明计算机教授680JS002吴进计算机讲师440JS003邢怀学计算机讲师460DZ001赵利电子助教380DZ002刘平电子讲师480DZ003张卫电子副教授600JJ001安晓军机械讲师450JJ002赵京华机械讲师440HG001孙亮化工教授720HG002陆新化工副教授580HG003王方化工助教400索引表中每个索引项通常包含三个域：一是索引值域(index)；二是子表开始位置域(start)；三是子表长度域(length)。一个学校的教师登记表如下表，其中职工号作为关键字：以每个记录的“职工号”作关键字，则线性表可简记：LA=(JS001,JS002,JS003,JS004,DZ001,DZ002,DZ003,JJ001,JJ002,HG001,HG002,HG003)若按“单位”数据项值对LA划分，则得四个子表：JS=(JS001,JS002,JS003)DZ=(DZ001,DZ002,DZ003)JJ=(JJ001,JJ002)HG=(HG001,HG002,HG003)可得索引表b1，如图所示：indexstartlength0JS031DZ332JJ623HG832索引表类型定义索引项的类型和顺序存储的索引表类型如下定义：struct IndexItemIndexKeyType index; /IndexKeyType为事先定义/的索引值类型int start; /子表中第一个元素所在下标位置int length; /子表的长度;typedef IndexItem indexlistILMSize ; /ILMSize为事先定义整型常量，它大于等于索引项m。若所有子表(合称为主表)被顺序存储在同一数组中，类型定义如下：typedef ElemType mainlistMaxSize; /MaxSize为事先定义的整型常量，它大于等于n。indexstartlength0JS031DZ332JJ623HG833索引查找算法算法思路：索引查找是有索引表和主表上进行的查找，其过程是：先根据给定的索引值K1，在索引表上查找出索引值等于K1的索引项，以确定对应子表在主表中开始位置和长度，再根据给定关键字K2，在对应子表中查找出关键字等于K2的结点。一个学校的教师登记表如下，职工号作为关键字： 职工号姓名单位职称工资JS001王大明计算机教授680JS002 吴进计算机讲师440JS003邢怀学计算机讲师460DZ001 赵利电子助教380DZ002刘平电子讲师480DZ003 张卫电子副教授600JJ001安晓军机械讲师450JJ002赵京华机械讲师440HG001孙亮化工教授720HG002陆新化工副教授580HG003王方化工助教400按“单位”数据项值对线性表划分，则得四个子表：JS=(JS001,JS002,JS003)DZ=(DZ001,DZ002,DZ003)JJ=(JJ001,JJ002)HG=(HG001,HG002,HG003)可得索引表b1，如图所示：indexstartlength0JS031DZ332JJ623HG83nt Indsch(mainlist A,indexlist B,int m,IndexKeyType K1,KeyType K2)/利用主表A和大小为m的索引表B索引查找索引值为K1,关键字为K2的记录，返回该记录在主表中的下标位置，若查找失败返回-1int i,j;/在索引表中顺序查找索引值为K1的索引项for(i=0;im;i+)if(K1=Bi.index) break;if(i=m) return -1；/在已查找到的第i个子表中顺序查找关键字为K2的记录j=Bi.start;while(jBi.start+Bi.length)if(K2=Aj.key) break;else j+;if(jBi.start+Bi.length) return j;else return -1;设索引表长度为m,相应子表长度为s,索引查找的平均查找长度为：(m+1)/2+(s+1)/24分块查找分块查找：属于索引查找，它要求主表中每个子表之间递增(递减)有序，并且索引表中每个索引项的索引值域用来存储对应块中最大关键字。分块查找算法：int Blocksch(mainlist A,indexlist B,int m,KeyType K)/利用主表A和大小为m的索引表B分块查找关键字为K的记录int i,j;/在索引表中顺序查找关键字为K所对应的索引项for(i=0;im;i+)if(K=Bi.index) break;if(i=m) return -1;/在已经查找到的第i个子表中顺序查找关键字Kj=Bi.start;while(jBi.start+Bi.length)if(K=Aj.key) break;else j+;/若查找成功则返回元素的下标位置，否则返回-1if(jBi.start+Bi.length) return j;else return -1;五、散列查找1基本概念散列函数：在进行查找时，在记录的存储位置与它的关键字之间建立一个确定的对应关系h,以线性表中每个元素的关键字K为自变量，通过函数h(K)计算出该元素的存储位置，我们将h函数称为散列函数或哈希函数。h(K)的值称为散列地址或哈希地址。例：假定一个线性表为 A=(18,75,60,43,54,90,46)，选取散列函数为：h(K)=K%m 取m=13则得每个元素散列地址：h(18)=18 % 13=5 h(75)=75 % 13=10 h(60)=60 % 13=8 h(43)=43 % 13=4h(54)=54 % 13=2 h(90)=90 % 13=12 h(46)=46 % 13=7根据散列地址，实现元素的存储映象Hm：0123456789101112H54431846607590冲突：在实际应用中，通常可能出现一个待插入元素的散列地址单元已被占用情况，使得该元素无法直接存入此单元，这种情况称为冲突。同义词：具有不同关键字而具有相同散列地址的元素称为同义词，即key1key2，但h(key1)=h(key2)。由同义词引起的冲突称作同义词冲突。例：如向下表中再插入元素70时，70%13=5，则出现了冲突 0123456789101112H54431846607590装填因子()：指散列表中已存入的元素数n与散列表空间大小m的比值,即：=n/m。当越小时，冲突可能性就越小，但同时，存储空间利用率就越低。散列表：根据设定的哈希函数及处理冲突的方法将一组关键字映象到一个有限的连续的地址集上，即把记录存放在表中映象的位置上，这种表便称为散列表(哈希表)。一个散列表的好坏与三个因素有关：l 装填因子l 所采用的散列函数l 解决冲突的方法 2散列函数构造散列函数的目标是使散列地址尽可能均匀分布在散列空间上，同时使计算尽可能简单，以节省计算时间。直接定址法以关键字K本身或关键字加上某个数值常量C作为散列地址的方法，对应的散列函数：h(K)=K+C (C为常数)例：有一个解放后出生的人口调查表，关键字是年份，h(K)=K+(-1948)，如表所示：地址 01 02 03 22 年份1949 1950 1951 1970 人数 15000 .除留余数法以关键字K除以散列长度m所得余数作为散列地址的方法，对应的散列函数：h(K)=K%m m为散列表长，取m=13,得散列表：0123456789101112H54431846607590l 取m为奇数比取m为偶数好l 确保m的值大于等于待散列的线性表的长度nl 当关键字K为字符串时，需转换为整数(先求K长，接着把每个字符的ASCII码累加到无符号整型量h上，并且每次累加前，h值左移3位，扩大8倍)int Hash(char * K, int m)/把字符串K转换为0m-1之间的一个值作为对应记录的散列地址int len=strlen(K); /求字符串K的长度unsigned int h=0;for(int i=0;ilen;i+)/采用一种方法计算K所对应的整数h=3; /h的值左移3位h+=Ki; return h%m;数字分析法取关键字中某些数值较分散的数字位作为散列地址的方法，适用于所有关键字已知，并对关键字中每一位的取值分布情况作了分析。例：有一组关键字如下：92326875927396289234363492706816927746389238126292394220通过分析：每个关键字从左到右第1、2、3位和第6位取值较集中，不宜作散列地址，其余的第4、5、7、8位取值分散，可以选择，若取最后两位作散列地址，得：(2,75,28,34,16,38,62,20)平方取中法取关键字平方的中间几位作为散列地址的方法，由平方取中法得到的散列地址同关键字的每一位都有关，使得散列地址有较好分散性。它适用于关键字中每一位取值都不够分散或者较分散的位数小于散列地址所需要的位数的情况。折叠法：首先将关键字分割成位数相同的几段(最后一段位数可少一些)，然后将它们的叠加和(舍去最高位进位)作为散列地址的方法。例：有一关键字：K=68242324，散列地址3位，将此关键字从左到右每三位一段划分后相叠加得： 3处理冲突的方法1) 开放定址法思路：从发生冲突的那个单元开始，按照一定次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元的一类处理冲突的方法。在使用该方法处理冲突的散列表中，查找一个元素的过程是：先根据给定关键字K，利用与插入时使用的同一散列函数h(K)计算出散列地址(设下标为d),然后用K同d单元的关键字比较，若相等则查找成功，否则按插入时处理冲突的相同次序，依次用K同所查单元的关键字比较，直到查找成功或查找到一空单元(表明查找失败)为止。三种方法： 线性探查法是用开放定址法处理冲突的一种最简单的探查方法。从发生冲突的d单元起,依次探查下一个单元,直到碰到一个空闲单元或探查完所有单元为止探查时,当达到下标为m-1的表尾单元时,下一个探查的单元是下标为0的表首单元。探查序列为d,d+1,d+2，表示为(d+i)%m (0im-1)。例如：构取m=13,线性表为 A=(18,75,60,43,54,90,46)，构造的散列表如下：0123456789101112H54431846607590现向表中再插入关键字为31和58的两个元素,用线性探查法解决冲突。先插入31，h(31)=31%13=5,因H5被占用，探查下一个即下标为6的单元，空闲，插入31。0123456789101112H5443183146607590再插入58，h(58)=58%13=6,因H6被占用，探查下一个即下标为7的单元，因H7仍不空闲，再接着向下探查，当探查到下标为9的单元时，空闲，插入58。0123456789101112H544318314660587590利用线性探查法处理冲突易造成元素的“堆积”(聚集) 0123456789101112H54431846607590向散列表中插入一个元素：int Insert (hashlist1 HT,int m,ElemType item)/向长度为m的散列表HT中插入一个元素int d=H(item.key,m); /可选一种合适的构造散列函数的方法，计算散列地址int temp=d;while(HTd.key != NullTag)/当d单元不空时继续向后查找空位置d=(d+1)%m;if(d=temp) return 0;HTd=item; /将新元素插入到下标为d的位置return 1; 从散列表中查找一个元素：int Search (hashlist1 HT,int m, ElemType item)/从长度为m的散列表HT中查找int d=H(item.key, m);int temp=d;while(HTd.key!=NullTag)/当散列地址中的关键字域不为空则循环if(HTd.key=item.key) return d;else d=(d+1)%m;if(d=temp) return -1;return -1; 平方探查法探查序列为d,d+12,d+22,表示为(d+i2)%m(0im-1)。递推公式为：优点：它是一种较好的处理冲突的方法，可以较好避免堆积现象缺点：不能探查到散列表上所有单元。例：当d0=5,m=17时，只能探查到下标依次为5、6、9、14、4、13、7、3、1的单元。d0=5;d1=(5 +2*1-1)%17=6; d2=(6 +2*2-1)%17=9;d3=(9 +2*3-1)%17=14; d4=(14 +2*4-1)%17=4;d5=(4 +2*5-1)%17=13; d6=(13 +2*6-1)%17=7;d7=(7 +2*7-1)%17=3; d8=(3 +2*8-1)%17=1; d9=(1 +2*9-1)%17=1; 双散列函数探查法思路：该方法使用两个散列函数h1和h2，其中h1和前面的h(K)一样，以关键字为自变量，产生一个0m-1之间的数作散列地址;h2也以关键字为自变量，产生一个1m-1之间的、并和m互素的数作散列地址。它的探查序列为：利用双散列法，按一定的距离，跳跃式地寻找“下一个”桶，减少了“堆积”的机会，最多经过m-1次探查，它会遍历表中所有位置，回到H0 位置。例：给出一组表项关键码22,41,53,46,30,13,01,67。散列表为 HT0.10，m = 11。散列函数为：Hash(x)(3x) % 11再散列函数为：ReHash(x) = (7x) % 10 +1Hi = ( Hi-1 + (7x) % 10 +1 ) % 11, i = 1, 2, H0(22) = 0 H0(41) = 2 H0(53) = 5 H0(46) = 6H0(30) = 2 冲突 H1 = (2+1) = 3 ,H0(13) = 6 冲突 H1 = (6+2) = 8H0(01) = 3 冲突 H1 = (3+8) = 0 ,H2 = (0+8) = 8 H3 = (8+8) = 5H4 =(5+8)=2 H5 =(2+8)=10,H0(67)=3 冲突, H1 = (3+10) = 2 H2 = (2+10) = 1搜索成功的平均搜索长度：2) 链接法思路：就是把发生冲突的同义词元素(结点)用单链表链接起来的方法。例：假定一个线性表B为：B=(18,75,60,43,54,90,46,31,58,73,15,34)。设采用的散列函数为h(K)=K%13,采用链接法处理：在该例中，查找成功时平均查找长度为：ASL=(8132+13)/121.42若线性探查法处理冲突进行散列存储，得到：查找成功时平均查找长度为：ASL=(7112+14+14+12+16)/122.13) 多种方法分析在散列表的插入和查找算法中，平均查找长度与表的大小m无关，只与选取的散列函数、值和处理冲突的方法有关,若假定所选取的散列函数能够使任一关键字等概率地映射到散列空间的任一地址上，理论上证明：当采用线性探查法处理冲突时， ASL=当采用链地址法处理冲突时，ASL=当采用平方探查法、双散列函数法处理冲突时，ASL=散列存储优缺点 插入与查找的速度相当快 根据关键字计算散列地址需要开销一定计算时间 占用存储空间较多 在散列表中只能按关键字查找元素 线性表中元素的逻辑关系无法在散列表中体现4散列表的运算设用HashMaxSize常量表示待定义的散列表类型的长度。假定采用开放定址法,其散列表类型用hashlist1表示,类型定义为：typedef ElemType hashlist1HashMaxSize;若采用链接表，其散列表类型用hashlist2表示，类型定义为：typedef LNode * hashlist2HashMaxSize;Lnode 定义如下：struct Lnode ElemType data;Lnode *next; 在类型为hashlist1的散列表上进行的运算类型定义：typedef ElemType hashlist1HashMaxSize;l 初始化散列表void InitHashList (hashlist1 HT)/把散列表HT中每一单元的关键字key域都置空for(int i=0;iHashMaxSize;i+)HTi.key=NullTag; /NullTag常量表示空标志，l 清空一个散列表void ClearHashList (hashlist1 HT)/把散列表HT中每一单元的关键字key域都置空for(int i=0;iHashMaxSize;i+)HTi.key=NullTag;l 向散列表中插入一个元素int Insert (hashlist1 HT,int m,ElemType item)/向长度为m的散列表HT中插入一个元素itemint d=H(item.key,m);int temp=d;while(HTd.key != NullTag)/当d单元不空时继续向后查找空位置d=(d+1)%m;if(d=temp) return 0;HTd=item; /将新元素插入到下标为d的位置return 1; /返回1表示插入成功l 从散列表中查找一个元素int Search (hashlist1 HT,int m, ElemType item)/从长度为m的散列表HT中查找关键字为item.key的一个元素int d=H(item.key, m);int temp=d;while(HTd.key!=NullTag)/当散列地址中的关键字域不为空则循环if(HTd.key=item.key) return d; /查找成功则反回下标delse d=(d+1)%m;if(d=temp) return -1; /查找失败反回-1return -1; l 从散列表中删除一个元素int Delete (hashlist1 HT,int m, ElemType item)/从长度为m的散列表HT中删除关键字为item.key的一个元素int d=H(item.key, m);int temp=d;while(HTd.key!=NullTag)if(HTd.key=item.key) HTd.key=DeleteTag;/DeleteTag常量为一删除标记return 1;else d=(d+1)%m; /继续向后探查if(d=temp) return 0;return 0; /删除失败返回0 在类型为hashlist2的散列表上进行的运算类型定义：struct Lnode ElemType data;Lnode *nex