赞
踩
定义:根据给定的某一个值,在查找表中确定一个关键字等于给定的值的数据元素
查找算法的分类:动态查找和静态查找;无序查找和有序查找;无序查找和有序查找
平均查找的长度:ASL:需要和指定的key进行比较的关键字的个数的期望值。对于n个数据元素的查找表,查找成功的平均查找长度位:ASL = PI*CI 。PI时查找到第i个数据元素的概率。CI:找到第i个元素时已经比较过得出次数
从线性表的一端开始,顺序查找,直到找到指定的代码为止
for(int i = 0 ; i < listlength ;i++ ){
if(list[i] == key)return i;
}
进行优化
//在头部插入哨兵,依次从后往前进行比较,可以免去每一步都要检查是不是越界
list[0].key = key; //设置哨兵
for(int i = listlength ; list[i].key != key ; i--)
return i;
平均查找长度 ASL = (N+1)/2;
查找不成功时需要n+1次比较所以,时间复杂度时O(n)
分块查找(Blocking Search)又称索引顺序查找,这是一种性能介于顺序查找和折半查找之间的一种查找方法。
分块查找中,需要建立一个“索引表”来划分块区域,通过定位某一块区域来查找相应信息;
索引表包括两项内容:最大关键项、最大关键项块区域的指针项;
对索引表来说是有序的顺序表,可用顺序查找和折半查找两种方法查找索引表;
而对索引表所标识的块区域中的数据是无序的,所以只能使用顺序查找。
int low = L; int high = R; int mid = (low+high)/2; while(low < high) //先折半查找索引表 { if(key == I[mid].maxkey) break; else { if(key < I[mid].maxkey) //缩小查找范围到左子序列 high = mid; else //缩小查找范围到右子序列 low = mid +1; } mid = (low+high)/2; } int i, end, start = I[mid].address; //找key值所在的区间首地址 if(mid == R) //确定查找的结束地址 end = len + 1; else end = I[mid+1].address; for(i = start; i < end; i++)//再顺序查找该区间 if(key == K[i].key) return i; //返回位置 return 0; }
O(log2n)~O(n)之间
首先元素时有序的,如果你要时没有顺序,那么对不起,先进行排序
二分查找又叫折半查找,就是把给定的值key和中间的节点进行比较,然后把线性表分成了两个子表,然后不断的进行继续分。
//递归版本的代码 int search1(int a[],int key,int left,int right) { int mid = (left + right)/2; if(left > right)return -1; if(a[mid] == key)return mid; if(a[mid] < key)return search1(a[],key,mid+1,right); if(a[mid] > key)return search1(a[],key,left,mid-1); } //非递归版本的代码 int search2(int a[],int key,int length) { int left,right,mid; left = 0;right = length - 1; while(left <= right) { mid = (left + right) / 2; if(a[mid] == key)return mid; if(a[mid] > key)right = mid -1; if(a[mid] < key)left = mid + 1; } }
折半查找的运行过程可以使用二叉树来进行表示,这一棵树通常被称为“判定树”
对于具有n个节点的判定树,他的层次至多为 l o g 2 n log_2n log2n + 1 结果如果不是整数向下取整
ASL= l o g 2 ( n + 1 ) log_2(n+1) log2(n+1) - 1
最坏的情况下关键此比较的次数是 l o g 2 ( n + 1 ) log_2(n+1) log2(n+1) 所以时间复杂度树O( l o g 2 n log_2n log2n)
基于二分查找算法,将查找点的选择改为自适应选择,可以提高查找效率,由于是二分查找的变异,所以插值查找属于有序查找
你仔细想一想,有必要一定选择二分查找吗?不一定把,你可以选择四分之一处吧,也可以选着三分之一处吧。所以说,折半查找不具有自适应性,这也就意味着有可能会有比他效率更搞的折半。
二分查找的计算
mid = (left + right) / 2 ,也就是 mid = low + 1/2 * (left - right)
我们改进一下
mid = left + (key - a[left]) /(a[right] - a[left]) * (right - left)
我们仅仅进行了系数1/2的改变,我们把1/2改进成了自适应的参数,这样跟关键字在有序表中的位置,让mid的值的变化更加接近关键字,这样也就简介减少了比较的次数
有一说一:当你表长大,而且关键字分布比较均匀的查找表来说,确实很好用,到那时如果分布很少不均匀,使用插值并不是一个好选择
int left = 0 ,mid ,right = listlength -1; while(left <= right) { mid = left + (key - list[left])/(list[right] - list[left]); if(key < list[mid]) { right = mid - 1; } else if(key > list[mid]) { left = mid + 1; } else { return mid; } }
查找成功或者失败的时间复杂度O( l o g 2 ( l o g 2 n ) log_2(log_2n) log2(log2n))
还是二分查找的一种提升算法,通过利用黄金比例在数列中选择查找点进行查找,来提高查找效率。那么这也是一种有序查找算法
要求开始表中记录的个数为某个斐波那契数小1,及n = F(k) - 1;
开始将key值和第F(k-1)位置的记录进行比较(也就是:mid = left + F(k-1)- 1)比较结果也分为三种
1:相等,那么return mid
2; key > mid , left = mid + 1,k-=2;
解释:low = mid + 1 上面查找的元素在【mid + 1 ,right 】范围内,k-=2说明分为在[mid+1 , right]内的个数为n - (F(k-1)) =
F(k) - 1 - F(k-1) = F(k) - F(k-1)-1 = F(k-2) -1 个,所以可以使用递归应用斐波那契查找
3 key < mid , right = mid - 1 , k-=1;
解释: low = mid + 1 说明待查找的元素在[left, mid -1]内, k-= 1 说明非为[left , mid-1]内的元素个数为F(k-1) - 1个,所以可以递归的应用斐波那契数列
void fib(int *f) { f[0],f[1] = 1; for(int i = 2; i < 20; i++)//20仅仅是一个暂定的数字可以修改 { f[i] f[i-2] + f[i - 1]; } } int fibsearch(int *a, int key, int length) { int i,left = 0,right = length - 1; int mid = 0; int k = 0; int F[20];//20仅仅是一个暂定的数字可以修改 fib(F); while(n > F[k] - 1)//计算处n在斐波那契中的数列 k++; for(i = length ; i < F[k - 1] ;i++) a[i] = a[right];//补全数组 while(left <= right) { mid = left + F[k - 1] - 1 ;//根据斐波那契数列进行黄金分割 if(a[mid] > key){ right = mid - 1; k = k -1; } else if(a[mid] < key ) { left = mid = 1; k-= 2; } else { if(mid <= right)return mid; else return -1; } } return 0; }
最坏的情况下,时间复杂度O( l o g 2 n log_2n log2n),所以复杂度也是O( l o g 2 n log_2n log2n)。
我家门前有两棵树,一棵是二叉树,另一棵也是二叉树
首先先生成一棵二叉排序树,然后根据左分支一定大于右分支的原则不断的进行查找
while(root != nullptr)
{
if(root->data == key)return root;
else if(root->data > key)root = root->lchild;
else root = root->rchild;
}
在正常的情况下,应该是O( l o g 2 n log_2n log2n),但是要是极端一点O(n)也是有可能的。所以需要优化,下面给出优化算法
2-3查找树定义:
2-节点:含有一个键和两条链接,左链接指向的2-3树中的键都小于该节点,右链接指向的2-3树中的键都大于该节点。
3-节点:含有两个键和三条链接,左链接指向的2-3树中的键都小于该节点,链接指向的2-3树中的键都位于该节点的两个键之间,右链接指向的2-3树中的键都大于该节点。
这样多了一个3节点之后,树就多了分配节点的能力
public class Tree234 { private Node root = new Node() ; /*public Tree234(){ root = new Node(); }*/ //查找关键字值 public int find(long key){ Node curNode = root; int childNumber ; while(true){ if((childNumber = curNode.findItem(key))!=-1){ return childNumber; }else if(curNode.isLeaf()){//节点是叶节点 return -1; }else{ curNode = getNextChild(curNode,key); } } } public Node getNextChild(Node theNode,long theValue){ int j; int numItems = theNode.getNumItems(); for(j = 0 ; j < numItems ; j++){ if(theValue < theNode.getItem(j).dData){ return theNode.getChild(j); } } return theNode.getChild(j); } //插入数据项 public void insert(long dValue){ Node curNode = root; DataItem tempItem = new DataItem(dValue); while(true){ if(curNode.isFull()){//如果节点满数据项了,则分裂节点 split(curNode); curNode = curNode.getParent(); curNode = getNextChild(curNode, dValue); }else if(curNode.isLeaf()){//当前节点是叶节点 break; }else{ curNode = getNextChild(curNode, dValue); } }//end while curNode.insertItem(tempItem); } public void split(Node thisNode){ DataItem itemB,itemC; Node parent,child2,child3; int itemIndex; itemC = thisNode.removeItem(); itemB = thisNode.removeItem(); child2 = thisNode.disconnectChild(2); child3 = thisNode.disconnectChild(3); Node newRight = new Node(); if(thisNode == root){//如果当前节点是根节点,执行根分裂 root = new Node(); parent = root; root.connectChild(0, thisNode); }else{ parent = thisNode.getParent(); } //处理父节点 itemIndex = parent.insertItem(itemB); int n = parent.getNumItems(); for(int j = n-1; j > itemIndex ; j--){ Node temp = parent.disconnectChild(j); parent.connectChild(j+1, temp); } parent.connectChild(itemIndex+1, newRight); //处理新建的右节点 newRight.insertItem(itemC); newRight.connectChild(0, child2); newRight.connectChild(1, child3); } //打印树节点 public void displayTree(){ recDisplayTree(root,0,0); } private void recDisplayTree(Node thisNode,int level,int childNumber){ System.out.println("levle="+level+" child="+childNumber+" "); thisNode.displayNode(); int numItems = thisNode.getNumItems(); for(int j = 0; j < numItems+1 ; j++){ Node nextNode = thisNode.getChild(j); if(nextNode != null){ recDisplayTree(nextNode, level+1, j); }else{ return; } } } //数据项 class DataItem{ public long dData; public DataItem(long dData){ this.dData = dData; } public void displayItem(){ System.out.println("/"+dData); } } //节点 class Node{ private static final int ORDER = 4; private int numItems;//表示该节点有多少个数据项 private Node parent;//父节点 private Node childArray[] = new Node[ORDER];//存储子节点的数组,最多有4个子节点 private DataItem itemArray[] = new DataItem[ORDER-1];//存放数据项的数组,一个节点最多有三个数据项 //连接子节点 public void connectChild(int childNum,Node child){ childArray[childNum] = child; if(child != null){ child.parent = this; } } //断开与子节点的连接,并返回该子节点 public Node disconnectChild(int childNum){ Node tempNode = childArray[childNum]; childArray[childNum] = null; return tempNode; } //得到节点的某个子节点 public Node getChild(int childNum){ return childArray[childNum]; } //得到父节点 public Node getParent(){ return parent; } //判断是否是叶节点 public boolean isLeaf(){ return (childArray[0] == null)?true:false; } //得到节点数据项的个数 public int getNumItems(){ return numItems; } //得到节点的某个数据项 public DataItem getItem(int index){ return itemArray[index]; } //判断节点的数据项是否满了(最多3个) public boolean isFull(){ return (numItems == ORDER-1) ? true:false; } //找到数据项在节点中的位置 public int findItem(long key){ for(int j = 0 ; j < ORDER-1 ; j++){ if(itemArray[j]==null){ break; }else if(itemArray[j].dData == key){ return j; } } return -1; } //将数据项插入到节点 public int insertItem(DataItem newItem){ numItems++; long newKey = newItem.dData; for(int j = ORDER-2 ; j >= 0 ; j--){ if(itemArray[j] == null){//如果为空,继续向前循环 continue; }else{ long itsKey = itemArray[j].dData;//保存节点某个位置的数据项 if(newKey < itsKey){//如果比新插入的数据项大 itemArray[j+1] = itemArray[j];//将大数据项向后移动一位 }else{ itemArray[j+1] = newItem;//如果比新插入的数据项小,则直接插入 return j+1; } } } //如果都为空,或者都比待插入的数据项大,则将待插入的数据项放在节点第一个位置 itemArray[0] = newItem; return 0; } //移除节点的数据项 public DataItem removeItem(){ DataItem temp = itemArray[numItems-1]; itemArray[numItems-1] = null; numItems--; return temp; } //打印节点的所有数据项 public void displayNode(){ for(int j = 0 ; j < numItems ; j++){ itemArray[j].displayItem(); } System.out.println("/"); } } }
最坏的情况下,所有的节点都是2节点效率是O( l o g 2 n log_2n log2n)
最好的情况下,所有的节点都是3节点,效率是O( l o g 3 n log_3n log3n)
//过于复杂,建议自行百度
时间复杂度:最坏也是对数级
对2-3树的一种扩展,根节点至少有两个节点,每个节点有M-1个key,并且可以升序排列;位于M-1和Mkey的子节点的值位于M-1和Mkey对应的value之间;其他节点至少有M/2个节点
// C++ program for B-Tree insertion #include<iostream> using namespace std; // A BTree node class BTreeNode { int *keys; // An array of keys int t; // Minimum degree (defines the range for number of keys) BTreeNode **C; // An array of child pointers int n; // Current number of keys bool leaf; // Is true when node is leaf. Otherwise false public: BTreeNode(int _t, bool _leaf); // Constructor // A utility function to insert a new key in the subtree rooted with // this node. The assumption is, the node must be non-full when this // function is called void insertNonFull(int k); // A utility function to split the child y of this node. i is index of y in // child array C[]. The Child y must be full when this function is called void splitChild(int i, BTreeNode *y); // A function to traverse all nodes in a subtree rooted with this node void traverse(); // A function to search a key in subtree rooted with this node. BTreeNode *search(int k); // returns NULL if k is not present. // Make BTree friend of this so that we can access private members of this // class in BTree functions friend class BTree; }; // A BTree class BTree { BTreeNode *root; // Pointer to root node int t; // Minimum degree public: // Constructor (Initializes tree as empty) BTree(int _t) { root = NULL; t = _t; } // function to traverse the tree void traverse() { if (root != NULL) root->traverse(); } // function to search a key in this tree BTreeNode* search(int k) { return (root == NULL)? NULL : root->search(k); } // The main function that inserts a new key in this B-Tree void insert(int k); }; // Constructor for BTreeNode class BTreeNode::BTreeNode(int t1, bool leaf1) { // Copy the given minimum degree and leaf property t = t1; leaf = leaf1; // Allocate memory for maximum number of possible keys // and child pointers keys = new int[2*t-1]; C = new BTreeNode *[2*t]; // Initialize the number of keys as 0 n = 0; } // Function to traverse all nodes in a subtree rooted with this node void BTreeNode::traverse() { // There are n keys and n+1 children, travers through n keys // and first n children int i; for (i = 0; i < n; i++) { // If this is not leaf, then before printing key[i], // traverse the subtree rooted with child C[i]. if (leaf == false) C[i]->traverse(); cout << " " << keys[i]; } // Print the subtree rooted with last child if (leaf == false) C[i]->traverse(); } // Function to search key k in subtree rooted with this node BTreeNode *BTreeNode::search(int k) { // Find the first key greater than or equal to k int i = 0; while (i < n && k > keys[i]) i++; // If the found key is equal to k, return this node if (keys[i] == k) return this; // If key is not found here and this is a leaf node if (leaf == true) return NULL; // Go to the appropriate child return C[i]->search(k); } // The main function that inserts a new key in this B-Tree void BTree::insert(int k) { // If tree is empty if (root == NULL) { // Allocate memory for root root = new BTreeNode(t, true); root->keys[0] = k; // Insert key root->n = 1; // Update number of keys in root } else // If tree is not empty { // If root is full, then tree grows in height if (root->n == 2*t-1) { // Allocate memory for new root BTreeNode *s = new BTreeNode(t, false); // Make old root as child of new root s->C[0] = root; // Split the old root and move 1 key to the new root s->splitChild(0, root); // New root has two children now. Decide which of the // two children is going to have new key int i = 0; if (s->keys[0] < k) i++; s->C[i]->insertNonFull(k); // Change root root = s; } else // If root is not full, call insertNonFull for root root->insertNonFull(k); } } // A utility function to insert a new key in this node // The assumption is, the node must be non-full when this // function is called void BTreeNode::insertNonFull(int k) { // Initialize index as index of rightmost element int i = n-1; // If this is a leaf node if (leaf == true) { // The following loop does two things // a) Finds the location of new key to be inserted // b) Moves all greater keys to one place ahead while (i >= 0 && keys[i] > k) { keys[i+1] = keys[i]; i--; } // Insert the new key at found location keys[i+1] = k; n = n+1; } else // If this node is not leaf { // Find the child which is going to have the new key while (i >= 0 && keys[i] > k) i--; // See if the found child is full if (C[i+1]->n == 2*t-1) { // If the child is full, then split it splitChild(i+1, C[i+1]); // After split, the middle key of C[i] goes up and // C[i] is splitted into two. See which of the two // is going to have the new key if (keys[i+1] < k) i++; } C[i+1]->insertNonFull(k); } } // A utility function to split the child y of this node // Note that y must be full when this function is called void BTreeNode::splitChild(int i, BTreeNode *y) { // Create a new node which is going to store (t-1) keys // of y BTreeNode *z = new BTreeNode(y->t, y->leaf); z->n = t - 1; // Copy the last (t-1) keys of y to z for (int j = 0; j < t-1; j++) z->keys[j] = y->keys[j+t]; // Copy the last t children of y to z if (y->leaf == false) { for (int j = 0; j < t; j++) z->C[j] = y->C[j+t]; } // Reduce the number of keys in y y->n = t - 1; // Since this node is going to have a new child, // create space of new child for (int j = n; j >= i+1; j--) C[j+1] = C[j]; // Link the new child to this node C[i+1] = z; // A key of y will move to this node. Find location of // new key and move all greater keys one space ahead for (int j = n-1; j >= i; j--) keys[j+1] = keys[j]; // Copy the middle key of y to this node keys[i] = y->keys[t-1]; // Increment count of keys in this node n = n + 1; } // Driver program to test above functions int main() { BTree t(3); // A B-Tree with minium degree 3 t.insert(10); t.insert(20); t.insert(5); t.insert(6); t.insert(12); t.insert(30); t.insert(7); t.insert(17); cout << "Traversal of the constucted tree is "; t.traverse(); int k = 6; (t.search(k) != NULL)? cout << "\nPresent" : cout << "\nNot Present"; k = 15; (t.search(k) != NULL)? cout << "\nPresent" : cout << "\nNot Present"; return 0; }
B+树代码太长,就不放这里了。
B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。
B+ 树的优点在于:
由于B+树在内部节点上不好含数据信息,因此在内存页中能够存放更多的key。数据存放的更加紧密,具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的,因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。
但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。
哈希查找也叫散列查找,整个散列查找过程大概分两步:在存储时通过散列函数计算记录的散列地址,并按此散列地址存储该记录。当查找时,一样通过散列函数计算记录的散列地址,然后访问散列地址的记录。
(1)直接定址法: 取关键字的某个线性函数值为散列地址,需要事先知道关键字的分布情况,适合查找表较小且连续的情况。
(2)数字分析法:使用关键字的一部分来计算散列存储的位置。适合处理关键字位数较大的情况。
(3)平方取中法:假设关键字是1234,那它的平方就是1522756,再抽取中间的3位就是277,适合不知道关键字的分布,而位数又不是很大的情况。
(4)折叠法: 将关键字从左到右分割成位数相等的几个部分,然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。比如关键字是9876543210,散列表表长为三位,我们将它分成四组,987|654|321|0,然后将他们叠加求和等于1962,再求后三位得到散列地址962。 适合事先不知道关键字的分布,关键字位数叫多的情况。
5)除留余数法:此方法为最常用的构造散列函数的方法
处理冲突散列的方法:
1:开放定址法就是一旦出现了冲突,就去寻找下一个空的散列地址,只要散列地址够大,空的散列地址总会被找到
2再散列函数法:事先准备多几个散列函数
3:链地址法:将所有同关键字的记录存储在一个单链表中,称这种表为同义词子表,在散列表中只存储所有同义词子表的头指针。
//哈希查找 #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct hash { int nValue; int nIndex; struct hash *pNext; }HashTable; //造哈希表 HashTable **CreateHashTable(int arr[],int nLength) { if(arr == NULL || nLength <= 0) return NULL; //申请表头 HashTable **pHash = NULL; pHash = (HashTable **)malloc(sizeof(HashTable*)*nLength); memset(pHash,0,sizeof(HashTable*)*nLength); //元素入表 int nIndex; int i; HashTable *pTemp = NULL; for(i = 0;i < nLength;i++) { nIndex = arr[i]%nLength; pTemp = (HashTable*)malloc(sizeof(HashTable)); pTemp->nValue = arr[i]; pTemp->nIndex = i; pTemp->pNext = pHash[nIndex]; pHash[nIndex] = pTemp; } return pHash; } int HashSearch(HashTable **pHash,int nLength,int nNum) { if(pHash == NULL || nLength <=0) return -1; int nIndex; HashTable *pTemp = NULL; //找到对应的链表 nIndex = nNum%nLength; pTemp = pHash[nIndex]; while(pTemp) { if(pTemp->nValue == nNum) { return pTemp->nIndex; } else { pTemp =pTemp->pNext; } } return -1; } int main() { int arr[] = {101,12,15,12,11,45,78,1}; HashTable **pHash = CreateHashTable(arr,sizeof(arr)/sizeof(arr[0])); int nIndex = HashSearch(pHash,sizeof(arr)/sizeof(arr[0]),1); printf("%d\n",nIndex); return 0; }
O(1)
1、顺序查找:
(1)最好情况:要查找的第一个就是。时间复杂度为:O(1)
(2)最坏情况:最后一个是要查找的元素。时间复杂度未:O(n)
(3)平均情况下就是:(n+1)/2。
所以总的来说时间复杂度为:O(n)
2、二分查找:O(log2n)->log以2为底n的对数
解释:2^t = n; t = log(2)n;
3、插值查找:O(log(2)(log(2)n))->log以2为底的(log以2为底的n的对数)的对数
4、斐波那契查找:O(log2n)->log以2为底n的对数
5、树表查找:
(1)二叉树:O(log2n)~O(n)之间
(2)红黑树:O(lgn)
(3)B和B+树:O(log2n)
6、分块查找:O(log2n)~O(n)之间
7、哈希查找:O(1)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。