查找方法总结---待完善
myFind.h
#ifndefMYFIND_H_INCLUDED#defineMYFIND_H_INCLUDED/*线性查找:顺序查找\折半查找两种形式:破坏性查找\非破坏性查找*///顺序查找:如果查找的到就返回key在数组中第一个位置的下标,否则返回-1intsequenceSearc(intarr[],intarrLen,intkey);//折半查找:数组必须有序、只限于线性查找intbinarySearch(intarr[],intarrLen,intkey);/*哈希查找:key-valus通过哈希函数建立一种关系,能够做到O(1)。key要尽可能的分散,最好能保证每个key都有一个相应的value,同时哈希函数也要尽可能简单快速哈希函数:直接定址法、除法取余法、数字分析法、平方取中法、折叠法解决冲突的方法:开放地址法、链接法*//*索引查找:索引:就是把一个关键字与它对应的i记录相关联的过程,一个索引由若干个索引项构成,每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引按照结构可以分为:线性索引、树形索引和多级索引。线性索引是将索引项集合组织为线性结构,也称为索引表。包括稠密索引、分块索引、倒排索引。*//*二叉排序树:根节点的左孩子小于根节点,根节点的右孩子大于根节点(相同数字??)*/#endif//MYFIND_H_INCLUDED
myFind.c
#include"myFind.h"#include"mysort.h"//线性查找:O(n)intsequenceSearc(intarr[],intarrLen,intkey){inti;for(i=0;i<arrLen;i++){if(key==arr[i]){returni;}}return-1;}//折半无序(使用最快的排序方法):O(NlogN)+O(logN);折半有序的时间复杂度:O(logN);intbinarySearch(intarr[],intarrLen,intkey){intleft;intright;intmiddle;//先排序quickSort(arr,0,arrLen-1);left=0;right=arrLen-1;while(left<=right){middle=(left+right)/2;if(key==arr[middle])//如果key恰好等于中间数字就返回{returnmiddle;}elseif(key<arr[middle])//key小于中间值,则向左查找{right=middle-1;}else{left=middle+1;}}return-1;}
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。