查找

查找主要内容•静态查找表–顺序表的查找–有序表的查找–索引顺序表的查找概念•查找表–查找操作针对的数据集，由同一类型的数据元素组成•关键字(key)–数据元素中某个数据项的值，可唯一标识该数据元素•关键字和数据元素的类型说明，如typedeffloatKeyType;//实型typedefintKeyType;//整型typedefchar*KeyType;//字符串型/*出生日期类型定义*/typedefstruct{charyear[5]；/*年：用字符型表示，宽度为4个字符*/charmonth[3]；/*月：字符型，宽度为2*/chardate[3]；/*日：字符型，宽度为2*/}BirthDate；概念•查找–在查找表中根据关键字找出特定的数据元素的操作•查找成功–关键字找到，返回对应数据元素在查询表中的位置•查找失败–关键字没有找到，返回空记录或空指针•关键字比较的宏定义//对数值类型关键字#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)(b))#defineLQ(a,b)((a)=(b))…//对字符串类型关键字#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))0)#defineLQ(a,b)(strcmp((a),(b))=0)…概念•查找算法–取决于查找表的数据结构•静态查找表–查找表事先已确定–对查询表除了创建和销毁操作外，只有查找或遍历操作•动态查找表–查找表本身在查找过程中动态生成，即若没有找到，则插入该元素–对查询表除了创建、销毁、查找、遍历操作外，还能进行插入和删除操作静态表查找•顺序表的查找•有序表的查找•索引顺序表的查找顺序查找表•查找表的存储结构–顺序表或线性链表/*顺序存储结构*/typedefstruct{ElemType*elem；/*数组基址*/intlength；/*表长度*/}S_TBL；/*链式存储结构结点类型*/typedefstructNODE{ElemTypeelem；/*结点的值域*/structNODE*next；/*下一个结点指针域*/}NodeType；ints_search(S_TBLtbl，KeyTypekx){/*在表tbl中查找关键码为kx的数据元素，若找到返回该元素在数组中的下标，否则返回0*/tbl.elem[0].key=kx；/*存放监测，这样在从后向前查找失败时，不必判表是否检测完，从而达到算法统一*/for(i=tbl.length;tbl.elem[i].keykx；i--)；/*从标尾端向前找*/returni；}以顺序表存储结构为例，查找算法可以为：顺序表查找顺序表查找•性能分析–假设每个数据元素的查找概率相等，则平均查找长度为(n+1)/2–顺序查找算法简单，适应面广。但平均查找长度较大，特别当n很大时，查找效率较低•思考：–线性链表存储结构的查找算法有序表查找•又称折半查找•要求查找表中的数据元素已按关键字值排序•只适用于有序表且限于顺序存储结构(不能用于链表存储结构)•算法如下：intBinary_Search(S_TBLtbl，KEYkx){/*在表tbl中查找关键码为kx的数据元素，若找到返回该元素在表中的位置，否则，返回0*/intmid，flag=0；low=1；high=length；/*①设置初始区间*/while(low=high)/*②表空测试*/{/*非空，进行比较测试*/mid=(low+high)/2；/*③得到中点*/if(kxtbl.elem[mid].key)high=mid-1；/*调整到左半区*/elseif(kxtbl.elem[mid].key)low=mid+1；/*调整到右半区*/else{flag=mid；break；}/*查找成功，元素位置设置到flag中*/}returnflag;}如：已知查找表中各数据元素的关键字为{05,13,19,21,37,56,64,75,80,88,92}05,13,19,21,37,56,64,75,80,88,92low=1high=11mid=61high=5mid=32low=4mid=43查找成功•查找关键字为21的数据元素05,13,19,21,37,56,64,75,80,88,92low=1high=11mid=61low=7mid=92low=10mid=103查找结束•查找关键字为85的数据元素high=9有序表查找•性能分析–在查找不成功时和给定值进行比较的关键字个数最多不超过log2n+1–假设每个数据元素的查找概率相等，则平均查找长度为log2(n+1)-1–查找效率高，但需事先对查找表排序，且仅限于顺序存储结构索引顺序表查找•又称分块查找•是顺序查找的改进•除了查找表以外，还需一个索引表结构索引表2214878613块中最大key块第一个元素在查找表中的位置2212138920334244382444382448605874498653查找表(只描述了关键字部分)(块间有序，块内无序)(有序)索引顺序表查找•分块查找算法–首先，根据关键字值在索引表中查找(顺序或折半查找)以确定块的范围–然后，在块中根据关键字值做顺序查找•性能分析–若索引表查找采用顺序查找，则平均查找长度为(n/s+s)/2+1；若索引表查找采用折半查找，则平均查找长度为咯log2(n/s+1)+s/2；其中n为查找表表长，s为每一块中记录个数–查找效率高，但需建立索引表动态查找表•动态查找表的特点–表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录•动态查找表允许的操作–创建表、销毁表、关键字查找、记录插入、记录删除、记录遍历等动态查找表•二叉排序树(*)•平衡二叉树•B树、B+树•键树二叉排序树•二叉排序树，又称二叉查找树–或者是否一棵空树，或者是具有下列性质的二叉树：•1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值•2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值•3)它的左、右子树也分别为二叉排序树45125333710024619078CAOZHAODINGCHENWANGMADULIXIA二叉排序树示例二叉排序树•二叉排序树的存储结构–通常采用二叉链表结构datalchildrchild二叉排序树•二叉排序树的查找算法一(不考虑查找失败后插入记录)intSearchElem(NodeType*t,NodeType**p,NodeType**q,KeyTypekx){/*在二叉排序树t上查找关键码为kx的元素，若找到，返回1，且q指向该结点，p指向其父结点；*//*否则，返回0，且p指向查找失败的最后一个结点*/intflag=0;*q=t;while(*q)/*从根结点开始查找*/{if(kx(*q)-elem.key)/*kx大于当前结点*q的元素关键码*/{*p=*q;*q=(*q)-rc;}/*将当前结点*q的右子女置为新根*/else{if(kx(*q)-elem.key)/*kx小于当前结点*q的元素关键码*/{*p=*q;*q=(*q)-lc;}/*将当前结点*q的左子女置为新根*/else{flag=1;break;}/*查找成功，返回*/}}/*while*/returnflag;}•二叉排序树的插入(创建)算法intInsertNode(NodeType**t,KeyTypekx){/*在二叉排序树*t上插入关键码为kx的结点*/NodeType*p=*t,*q,*s;intflag=0;if(!SearchElem(*t,&p,&q,kx));/*在*t为根的子树上查找*/{s=(NodeType*)malloc(sizeof(NodeType));/*申请结点，并赋值*/s-elem.key=kx;s-lc=NULL;s-rc=NULL;flag=1;/*设置插入成功标志*/if(!p)t=s;/*向空树中插入时*/else{if(kxp-elem.key)p-rc=s;/*插入结点为p的右子女*/elsep-lc=s;/*插入结点为p的左子女*/}}returnflag;}•从空树开始，经过一系列查找插入操作后，可生成一棵二叉排序树例一：假设查找的关键序列为{45,24,53,45,12,24,90}，则生成二叉排序树的过程如下图所示：454524452453452453124524531290abcde例二：假设查找的关键序列为{27,32,16,27,14,16,27}，则生成二叉排序树的过程如下图所示：abcd27273227163227163214二叉排序树•二叉排序树的特点–中序遍历二叉排序树可得到一个关键字的有序序列（即：可以通过输入一个无序序列，而通过构造二叉排序树后进行遍历的方法实现排序）–二叉排序树的插入过程不需要移动其他记录–具有相同n个结点的二叉排序树会因为构造的时候关键字插入的顺序不同而不同(下页说明)–二叉排序树的查找算法具有折半查找的特性，同时又采用了链式存储结构，因此是动态查找表的适宜表示如：查找的关键序列分别为{27,32,16,14}、{16,14,27,32}和{14,16,27,32},生成二叉排序树分别如下：271632141614273214162732二叉排序树•二叉排序树的查找性能分析–与给定值比较的关键字个数不超过树的深度–平均查找长度与二叉排序树的形态有关哈希(Hash)表•Hash表又称散列表•Hash函数–建立关键字值集合到存储地址集合的映射关系即：记录的存储位置loc=h(key)•Hash表–所有记录按Hash思想组成而成的表–优点：根据key值，查找时不必经过多次key值比较就可以一次定位，直接找到所查找的记录–问题：hash函数的选择非常重要，如果不同的key值可能得到相同的loc，那末就存在存储位置冲突的问题Hash函数顺序表下标值等哈希(Hash)表如：hash函数h(key)=keymod10,记录集合为No.NameClass…5Zhangc112Liuc24Wangc110Lic3…则Hash表为10Lic312Liuc24Wangc15Zhangc301234567lockey哈希(Hash)表•冲突问题–不同key值对应的hash函数值(地址值)相同•冲突产生的原因–通常hash表的大小小于key值集合的大小–Hash函数构造不合理•建立hash表时需要重要考虑的是–设定好的hash函数，使hash值尽可能均匀分布–建立相应的冲突处理方法(冲突不可避免，力求尽量减少)哈希(Hash)表•Hash函数的构造–Hash函数的定义可以很灵活，只要使得所有key的hash值能落在hash表范围中，如：•直接定位法：h(key)=key或h(key)=a*key+bhash地址集合与key值集合大小相同•除留余数法：h(key)=keymodp(phash表长)•随机法：h(key)=random(key)•数字分析法：取key的若干数位组成hash地址•平方取中法：取key平方后的中间几位组成hash地址•折叠法：将key分割成若干部分，取这些部分的叠加和组成hash地址哈希(Hash)表•处理冲突的方法–开放定址法/再散列法•线性探测再散列法•二次探测再散列法•伪随机探测再散列法)2/(,...2,2,1,1mod))((22222mkkdmdkeyHHiii1,...,2,1)1(,...,2,1mod))((mdmkkimdkeyHHiiiHi=(H(key)+di)modmdi=伪随机数序列•m为hash表长•di为增量如，已知h(key)=keymod11,长度为11的hash表中已经填有key值分别为17,60,29的记录，hash表