查找算法汇总—手撕代码
2021/7/8 22:36:03
本文主要是介绍查找算法汇总—手撕代码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1、顺序查找
int SequenceSearch(int a[], int value, int n) { int i; for(i = 0; i < n; i++) if(a[i] == value) return i; return -1; }
2、二分查找
折半查找
int BinarySearch(int a[], int value, int n) { int low, high, mid; low = 0; high = n - 1; while(low <= high) { mid = (low + high) / 2; if(a[mid] == value) return mid; if(a[mid] > value) high = mid - 1; if(a[mid] < value) low = mid + 1; } return -1; }
递归查找
int BinarySearch(int a[], int value, int low, int hight) { int mid = low + (high - low) / 2; if(a[mid] == value) return mid; if(a[mid] > value) return BinarySearch(a, value, low, mid - 1); if(a[mid] < value) return BinarySearch(a, value, mid + 1, high); }
3、插值查找
int InsertionSearch(int a[], int value, int low, int high) { int mid = low + (value - a[low]) / (a[high] - a[low]) * (high - low); if(a[mid] == value) return mid; if(a[mid] > value) return InsertionSearch(a, value, low, mid - 1); if(a[mid] < value) return InsertionSearch(a, value, mid + 1, high); }
4、斐波那契查找
斐波那契查找与折半查找很相似,他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1,及n=F(k)-1;
开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种:
1)相等,mid位置的元素即为所求
2)>,low=mid+1,k-=2;
说明:low=mid+1说明待查找的元素在[mid+1,high]范围内,k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1)) = Fk-1-F(k-1) = Fk-F(k-1)-1=F(k-2)-1个,所以可以递归的应用斐波那契查找。
3)<,high=mid-1,k-=1。
说明:low=mid+1说明待查找的元素在[low,mid-1]范围内,k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个,所以可以递归 的应用斐波那契查找。
#include "stdafx.h" #include <memory> #include <iostream> using namespace std; const int max_size = 20; void Fibonacci(int *F) { F[0] = 0; F[1] = 1; for(int i = 0; i < max_size; ++i) F[i] = F[i - 1] + F[i - 2]; } int FibonacciSearch(int a[], int n, int key) { int low = 0; int hight = n - 1; int F[max_size]; Fibonacci(F); int k = 0; while(n > F[k] - 1) ++k; int *temp; temp = new int [F[k] - 1]; memcpy(temp, a, n*sizeof(int)); for(int i = n; i < F[k] - 1; ++i) temp[i] = a[n - 1]; while(low <= high) { int mid = low + F[k-1] - 1; if(key < temp[mid]) { high = mid - 1; k -= 1; } else if(key > temp[mid]) { low = mid + 1; k -= 2; } else { if(mid < n) return mid; else return n - 1; } } delete [] temp; return -1; }
5、二叉排序树上的查找
二叉树的查找
typedef struct node{ KeyType key; InfoType data; struct node *lchild, *rchild; }BSTNode;
/* 递归算法 */ BSTNode *SearchBST(BSTNode *bt, KeyType k) { if(bt == NULL || bt->key == k) return bt; if(k < bt->key) return SearchBST(bt->lchild, k); else return SearchBST(bt->rchild, k); } /* 非递归算法 */ BSTNode *SearchBST(BSTNode *bt, KeyType k) { while(bt != NULL) { if(k == bt->key) return bt; else if(k < bt->key) bt = bt->lchild; else bt = bt->rchild; } return NULL; }
二叉树的插入
int InsertBST(BSTNode *p, KeyType k) { if(p == NULL) { p = (BSTNode *)malloc(sizeof(BSTNode)); p->key = k; p->lchild = p->rchild = NULL; return 1; } else if(k == p->key) return 0; else if(k < p->key) return InsertBST(p->lchild, k); else return InsertBST(p->rchild, k); }
二叉树的生成
BSTNode *CreateBST(KeyType A[], int n) { BSTNode *bt = NULL; int i = 0; while(i < n) { InsertBST(bt, A[i]); i++; } return bt; }
二叉树的删除
int DeleteBST(BSTNode *bt, KeyType k) { if(bt == NULL) return 0; else { if(k < bt->key) return DeleteBST(bt->lchild, K); else if(k > bt->key) return DeleteBST(bt->rchild, k); else { Delete(bt); return 1; } } } void Delete(BSTNode *p) { BSTNode *q; if(p->rchild == NULL) { q = p; p = p->lchild; free(q); } else if(p->lchild == NULL) { q = p; p = p->rchild; free(q); } else Delete1(p, p->lchild); }
6、哈希查找
#include "stdio.h" #include "stdlib.h" #define HASHSIZE 7 #define NULLKEY -1 typedef struct { int *elem; int count; }HashTable; void Init(HashTable *hashTable) { int i; hashTable->elem = (int *)malloc(HASHSIZE*sizeof(int)); hashTable->count = HASHSIZE; for(i = 0; i < HASHSIZE; i++) hashTable->elem[i] = NULLKEY; } int Hash(int data) { return data % HASHSIZE; } void Insert(HashTable *hashTable, int data) { int hashAddress = Hash(data); while(hashTable->elem[hashAddress] != NULLKEY) hashAddress = (++hashAddress) % HASHSIZE; hashTable->elem[hashAddress] = data; } int Search(HashTable *hashTable, int data) { int hashAddress = Hash(data); while(hashTable->elem[hashAddress] != data) { hashAddress = (++hashAddress) % HASHSIZE; if(hashTable->elem[hashAddress] == NULLKEY || hashAddress == Hash(data)) return -1; } return hashAddress; } int main(){ int i,result; HashTable hashTable; int arr[HASHSIZE]={13,29,27,28,26,30,38}; //初始化哈希表 Init(&hashTable); //利用插入函数构造哈希表 for (i=0;i<HASHSIZE;i++){ Insert(&hashTable,arr[i]); } //调用查找算法 result= Search(&hashTable,29); if (result==-1) printf("查找失败"); else printf("29在哈希表中的位置是:%d",result+1); return 0; }
这篇关于查找算法汇总—手撕代码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南