C、C++、Java、Python、Go、Rust、Dart实现七大搜索算法

文章目录[隐藏]

• 搜索算法
• C实现七大查找算法
• C++实现七大查找算法
• Java实现七大查找算法
• Python实现七大查找算法
• Go实现七大查找算法
• Rust实现七大查找算法
• Dart实现七大查找算法

// 顺序查找 int LinearSearch(int *arr, int size, int key) { for (int i = 0; i < size; i++) { if (arr[i] == key) return i; } return -1; } // 分块查找 struct index { int key; int start; }newIndex[3]; int DisSearch(int *arr, int key) { int i = 0, start; while (i < 3 && key > newIndex[i].key) i++; if (i >= 3) return -1; start = newIndex[i].start; while (start <= start + 5 && arr[start] != key) start++; if (start > start + 5) return -1; return start; } // 二分查找，数据需已排序 int BinarySearch(int *arr, int size, int key) { int mid, low = 0, high = size - 1; while (low <= high) { mid = (low + high) / 2; if (arr[mid] == key) return mid; else if (arr[mid] < key) low = mid + 1; else high = mid - 1; } return -1; } // 插值查找，数据需已排序 int InsertSearch(int *arr, int size, int key) { int mid, low = 0, high = size - 1; while (low <= high) { mid = low + (key - arr[low]) * (high - low) / (arr[high] - arr[low]); if (arr[mid] == key) return mid; else if (arr[mid] > key) high = mid - 1; else low = mid + 1; } return -1; } void Fibonacci(int *f, int size) { f[0] = 1; f[1] = 1; for ( int i = 2; i < size; i++) f[i] = f[i-1] + f[i-1]; } // 斐波那契查找 int FibonacciSearch(int *arr, int size, int key) { int mid = 0, low = 0, high = size - 1; int k = 0; int F[size]; Fibonacci(F, size); while ( size > F[k] - 1) ++k; for (int i = size; i < F[k] - 1; ++i) arr[i] = arr[high]; while (low <= high) { mid = low + F[k-1] - 1; if (arr[mid] > key) { high = mid - 1; k--; } else if (arr[mid] < key) { low = mid + 1; k -= 2; } else { if (mid <= high) return mid; else return -1; } } return -1; } // 树表查找 /*file:biTree.h*/ #ifndef CHIYX_BITREE #define CHIYX_BITREE #ifndef NULL #define NULL 0 #endif typedef int DataType; //二叉树的节点结构 typedef struct BiTreeNode { DataType data; struct BiTreeNode *parent; struct BiTreeNode *left; struct BiTreeNode *right; }BiTreeNode, *BiTree; //查找：返回第一个等于data域等于key的节点，不存在返回NULL BiTreeNode *search(BiTree *biTree, DataType key); //返回二叉树的最小节点,空树返回NULL BiTreeNode *minImum(BiTree *biTree); //返回二叉树的最大节点,空树返回NULL BiTreeNode *maxImum(BiTree *biTree); //返回节点x的后继节点,不存在后继（节点x为最大节点）返回NULL BiTreeNode *successor(BiTreeNode *x); //返回节点x的前驱节点，不存在前驱（节点x为最小节点）返回NULL BiTreeNode *predecessor(BiTreeNode *x); //将值data插入到二叉树中（生成一个值为data的节点） void insertNode(BiTree *biTree, DataType data); //删除一个值为data的节点 void deleteNode(BiTree *biTree, DataType data); //中序遍历二叉树 void inorderTraversal(BiTree *biTree, void (*visitor)(BiTreeNode *node)); #endif /*file:biTree.c*/ #include <stdlib.h>#include "biTree.h" //查找：返回第一个等于data域等于key的节点，不存在返回NULL BiTreeNode *search(BiTree *biTree, DataType key) { BiTreeNode *curNode = *biTree; while (curNode != NULL && curNode->data != key) { if (key < curNode->data) curNode = curNode->left; else curNode = curNode->right; } return curNode; } //返回二叉树的最小节点,空树返回NULL BiTreeNode *minImum(BiTree *biTree) { BiTreeNode *curNode = *biTree; while (curNode != NULL && curNode->left != NULL) curNode = curNode->left; return curNode; } //返回二叉树的最大节点,空树返回NULL BiTreeNode *maxImum(BiTree *biTree) { BiTreeNode *curNode = *biTree; while (curNode != NULL && curNode->right != NULL) curNode = curNode->right; return curNode; } //返回节点x的后继节点,不存在后继（节点x为最大节点）返回NULL BiTreeNode *successor(BiTreeNode *x) { if (x == NULL) return NULL; //存在右子树，则后继节点为其右子树中最小的节点 if (x != NULL && x->right != NULL) return minImum(&(x->right)); while (x->parent != NULL && x->parent->right == x) x = x->parent; return x->parent; //错误版本为 x， 此处应该返回父结点 } //返回节点x的前驱节点，不存在前驱（节点x为最小节点）返回NULL BiTreeNode *predecessor(BiTreeNode *x) { if (x == NULL) return NULL; //存在左子树，则后继节点为其左子树中最大的节点 if (x != NULL && x->left != NULL) return maxImum(&(x->left)); while (x->parent != NULL && x->parent->left == x) x = x->parent; return x->parent; //错误版本为 x， 此处应该返回父结点 } void insertNode(BiTree *biTree, DataType data) { //创建节点 BiTreeNode *targetNode; targetNode = (BiTreeNode *)malloc(sizeof(BiTreeNode)); //没有足够内存 if (targetNode == NULL) return; targetNode->data = data; targetNode->parent = NULL; targetNode->left = NULL; targetNode->right = NULL; BiTreeNode *p, *y; p = *biTree; y = NULL; while (p != NULL ) { y = p; if (targetNode->data < p->data) p = p->left; else p = p->right; } //空树，将新节点置为树根 if (y == NULL) { *biTree = targetNode; } else { if (targetNode->data < y->data) y->left = targetNode; else y->right = targetNode; } targetNode->parent = y; } //删除一个值为data的节点 void deleteNode(BiTree *biTree, DataType data) { //查找待删除的节点 BiTreeNode *targetNode, *x, *y; targetNode = search(biTree, data); if (targetNode == NULL) return; //找出真正的删除节点，如果目标节点最多只有一个子树，则其为真正删除的节点 //否则其后继节点（最多只有一个子树，想想为什么）为真正删除的节点，然后将后继节点的值赋给目标节点 if (targetNode->left == NULL || targetNode->right == NULL) y = targetNode; else y = successor(targetNode); if (y->left != NULL) x = y->left; else x = y->right; if (x != NULL) x->parent = y->parent; //如果y是根节点, 则根节点变为x if (y->parent == NULL) *biTree = x; else if (y->parent->right == y) y->parent->right = x; else y->parent->left = x; if (y != targetNode) targetNode->data = y->data; //释放y占有的空间 free(y); } //中序遍历二叉树 void inorderTraversal(BiTree *biTree, void (*visitor)(BiTreeNode *node)) { BiTreeNode *curNode; curNode = *biTree; if (curNode != NULL) { inorderTraversal(&(curNode->left), visitor); //遍历左子树 visitor(curNode); //访问节点 inorderTraversal(&(curNode->right), visitor); //遍历右子树 } } // 哈希查找 #include <stdlib.h>#include <io.h>#include <math.h>#include <time.h> #define HASHSIZE 100 #define NULLKEY -32768 int L; typedef struct { int *elem; int count; } HashTable; bool initHashTable(HashTable *hashTable) { L = HASHSIZE; hashTable->elem = (int *) malloc(L*sizeof(int)); hashTable->count = L; for (int i = 0; i < L; i++) hashTable->elem[i] = NULLKEY; return true; } int HashCalc(int key) { return key % L; } void insert(HashTable *hashTable, int key) { int addr = HashCalc(key); while (hashTable->elem[addr] != NULLKEY) addr = (addr + 1) % L; hashTable->elem[addr] = key; } int HashSearch(HashTable *hashTable, int key) { int addr = HashCalc(key); while (hashTable->elem[addr] != key) { add = (addr + 1) % L; if (hashTable->elem[addr] == NULLKEY || add == Hash(key)) return 0; } return addr; }

// 顺序查找 template <typename T> int LinearSearch(T *arr, int size, T key) { for (int i = 0; i < size; i++) { if (arr[i] == key) return i; } return -1; } // 分块查找 struct index { T key; int start; }newIndex[3]; int DisSearch(T *arr, T key) { int i = 0, start; while (i < 3 && key > newIndex[i].key) i++; if (i >= 3) return -1; start = newIndex[i].start; while (start <= start + 5 && arr[start] != key) start++; if (start > start + 5) return -1; return start; } // 二分查找，数据需已排序 template<typename T> int BinarySearch(T *arr, int size, T key) { int mid, low = 0, high = size - 1; while (low <= high) { mid = (low + high) / 2; if (arr[mid] == key) return mid; else if (arr[mid] < key) low = mid + 1; else high = mid - 1; } return -1; } // 插值查找，数据需已排序 template <typename T> int InsertSearch(T *arr, int size, T key) { int mid, low = 0, high = size - 1; while (low <= high) { mid = low + (key - arr[low]) * (high - low) / (int) (arr[high] - arr[low]); if (arr[mid] == key) return mid; else if (arr[mid] > key) high = mid - 1; else low = mid + 1; } return -1; } void Fibonacci(int *f, int size) { f[0] = 1; f[1] = 1; for ( int i = 2; i < size; i++) f[i] = f[i-1] + f[i-1]; } // 斐波那契查找 template <typename T> int FibonacciSearch(T *arr, int size, T key) { int mid = 0, low = 0, high = size - 1; int k = 0; int F[size]; Fibonacci(F, size); while ( size > F[k] - 1) ++k; for (int i = size; i < F[k] - 1; ++i) arr[i] = arr[high]; while (low <= high) { mid = low + F[k-1] - 1; if (arr[mid] > key) { high = mid - 1; k--; } else if (arr[mid] < key) { low = mid + 1; k -= 2; } else { if (mid <= high) return mid; else return -1; } } return -1; } // 树表查找 /*file:biTree.h*/ #ifndef CHIYX_BITREE #define CHIYX_BITREE #ifndef NULL #define NULL 0 #endif typedef int DataType; //二叉树的节点结构 typedef struct BiTreeNode { DataType data; struct BiTreeNode *parent; struct BiTreeNode *left; struct BiTreeNode *right; }BiTreeNode, *BiTree; //查找：返回第一个等于data域等于key的节点，不存在返回NULL BiTreeNode *search(BiTree *biTree, DataType key); //返回二叉树的最小节点,空树返回NULL BiTreeNode *minImum(BiTree *biTree); //返回二叉树的最大节点,空树返回NULL BiTreeNode *maxImum(BiTree *biTree); //返回节点x的后继节点,不存在后继（节点x为最大节点）返回NULL BiTreeNode *successor(BiTreeNode *x); //返回节点x的前驱节点，不存在前驱（节点x为最小节点）返回NULL BiTreeNode *predecessor(BiTreeNode *x); //将值data插入到二叉树中（生成一个值为data的节点） void insertNode(BiTree *biTree, DataType data); //删除一个值为data的节点 void deleteNode(BiTree *biTree, DataType data); //中序遍历二叉树 void inorderTraversal(BiTree *biTree, void (*visitor)(BiTreeNode *node)); #endif /*file:biTree.c*/ #include <stdlib.h>#include "biTree.h" //查找：返回第一个等于data域等于key的节点，不存在返回NULL BiTreeNode *search(BiTree *biTree, DataType key) { BiTreeNode *curNode = *biTree; while (curNode != NULL && curNode->data != key) { if (key < curNode->data) curNode = curNode->left; else curNode = curNode->right; } return curNode; } //返回二叉树的最小节点,空树返回NULL BiTreeNode *minImum(BiTree *biTree) { BiTreeNode *curNode = *biTree; while (curNode != NULL && curNode->left != NULL) curNode = curNode->left; return curNode; } //返回二叉树的最大节点,空树返回NULL BiTreeNode *maxImum(BiTree *biTree) { BiTreeNode *curNode = *biTree; while (curNode != NULL && curNode->right != NULL) curNode = curNode->right; return curNode; } //返回节点x的后继节点,不存在后继（节点x为最大节点）返回NULL BiTreeNode *successor(BiTreeNode *x) { if (x == NULL) return NULL; //存在右子树，则后继节点为其右子树中最小的节点 if (x != NULL && x->right != NULL) return minImum(&(x->right)); while (x->parent != NULL && x->parent->right == x) x = x->parent; return x->parent; //错误版本为 x， 此处应该返回父结点 } //返回节点x的前驱节点，不存在前驱（节点x为最小节点）返回NULL BiTreeNode *predecessor(BiTreeNode *x) { if (x == NULL) return NULL; //存在左子树，则后继节点为其左子树中最大的节点 if (x != NULL && x->left != NULL) return maxImum(&(x->left)); while (x->parent != NULL && x->parent->left == x) x = x->parent; return x->parent; //错误版本为 x， 此处应该返回父结点 } void insertNode(BiTree *biTree, DataType data) { //创建节点 BiTreeNode *targetNode; targetNode = (BiTreeNode *)malloc(sizeof(BiTreeNode)); //没有足够内存 if (targetNode == NULL) return; targetNode->data = data; targetNode->parent = NULL; targetNode->left = NULL; targetNode->right = NULL; BiTreeNode *p, *y; p = *biTree; y = NULL; while (p != NULL ) { y = p; if (targetNode->data < p->data) p = p->left; else p = p->right; } //空树，将新节点置为树根 if (y == NULL) *biTree = targetNode; else { if (targetNode->data < y->data) y->left = targetNode; else y->right = targetNode; } targetNode->parent = y; } //删除一个值为data的节点 void deleteNode(BiTree *biTree, DataType data) { //查找待删除的节点 BiTreeNode *targetNode, *x, *y; targetNode = search(biTree, data); if (targetNode == NULL) return; //找出真正的删除节点，如果目标节点最多只有一个子树，则其为真正删除的节点 //否则其后继节点（最多只有一个子树，想想为什么）为真正删除的节点，然后将后继节点的值赋给目标节点 if (targetNode->left == NULL || targetNode->right == NULL) y = targetNode; else y = successor(targetNode); if (y->left != NULL) x = y->left; else x = y->right; if (x != NULL) x->parent = y->parent; //如果y是根节点, 则根节点变为x if (y->parent == NULL) *biTree = x; else { if (y->parent->right == y) y->parent->right = x; else y->parent->left = x; } if (y != targetNode) targetNode->data = y->data; //释放y占有的空间 free(y); } //中序遍历二叉树 void inorderTraversal(BiTree *biTree, void (*visitor)(BiTreeNode *node)) { BiTreeNode *curNode; curNode = *biTree; if (curNode != NULL) { inorderTraversal(&(curNode->left), visitor); //遍历左子树 visitor(curNode); //访问节点 inorderTraversal(&(curNode->right), visitor); //遍历右子树 } } // 哈希查找 #include <stdlib.h>#include <io.h>#include <math.h>#include <time.h> #define HASHSIZE 100 #define NULLKEY -32768 int L; typedef struct { T *elem; int count; } HashTable; template <typename T> bool initHashTable(HashTable *hashTable) L = HASHSIZE; hashTable->elem = (T *) new(L*sizeof(T)); hashTable->count = L; for (int i = 0; i < L; i++) hashTable->elem[i] = NULLKEY; return true; } template <typename T> int HashCalc(T key) { return int (key % L); } template <typename T> void insert(HashTable *hashTable, T key) { int addr = HashCalc(key); while (hashTable->elem[addr] != NULLKEY) addr = (addr + 1) % L; hashTable->elem[addr] = key; } template <typename T> int HashSearch(HashTable *hashTable, T key) { int addr = HashCalc(key); while (hashTable->elem[addr] != key) { add = (addr + 1) % L; if (hashTable->elem[addr] == NULLKEY || add == Hash(key)) return 0; } return addr; }

public class Search { public static void main(String[] args) { int[10] arr = {100,80,10,5,3,2,1,0,13,9}; // xxxSearch(arr); System.out.print(arr.toString()); } // 顺序查找 public static int <T extends Comparable<? super T>> linearSearch(T[] arr, T key) { for (int i = 0; i < arr.length; i++) { if (key == arr[i]) return i; } return -1; } // 二分查找 public static int <T extends Comparable<? super T>> binarySearch(T[] arr, T key) { int mid; int low = 0; int high = arr.length - 1; while (low <= high) { mid = (low + high) / 2; if (key == arr[mid]) { return mid; } else if (key < arr[mid]) { high = mid - 1; } else { low = mid + 1; } } return -1; } // 插值查找 public static int <T extends Comparable<? super T>> insertSearch(T[] arr, T key) { int mid; int low = 0; int high = arr.length - 1; while (low <= high) { mid = low + (key - arr[low]) * (high - low) / (arr[high] - arr[low]); if (arr[mid] == key) { return mid; } else if (arr[mid] > key) { high = mid - 1; } else { low = mid + 1; } } return -1; } // 斐波那契查找 public static int fibonacciSearch(int[] arr, int key) { int[arr.length] F; F[0] = 1; F[1] = 1; for (int i = 2; i < arr.length; i++) F[i] = F[i-1] + F[i-1]; int k = 0; while (arr.length > F[k] - 1) k++; for (int i = 0; i < arr.length, F[k] - 1) arr[i] = arr[high]; int mid; int low = 0; int high = arr.length - 1; while (low <= high) { mid = low + F[k-1] - 1; if (arr[mid] > key) { high = mid - 1; k--; } else if (arr[mid] < key) { low = mid + 1; k -= 2; } else { if (mid <= high) return mid; else return -1; } } return -1; } }

# 顺序查找 def LinearSearch(arr, key): for i in range(len(arr)): if key == arr[i]: return i return None # 二分查找 def BinSearch(arr, key): low, high = 0, len(arr) - 1 while low <= high: mid = (low + high) / 2 if key == arr[mid]: return mid elif key < arr[mid]: high = mid - 1 else: low = mid + 1 return None # 插值查找 def InsertSearch(arr, key): low, high = 0, len(arr) - 1 while low <= high: mid = low + (key - arr[low]) * (high - low) / (arr[high] - arr[low]) if arr[mid] == key: return mid elif arr[mid] > key: high = mid - 1; else: low = mid + 1; return -1 # 斐波那契查找 def FibonacciSearch(arr, key): #初始化斐波那契数列 F = [0]* len(arr) F[0], F[1] = 1, 1 for i in range(2, len(arr)): F[i] = F[i-1] + F[i-1] k = 0 while len(arr) > F[k] - 1: k += 1 for i in range(len(arr), F[k] - 1): arr[i] = arr[high] low, high = 0, len(arr) - 1 while low <= high: mid = low + F[k-1] - 1 if arr[mid] > key: high = mid - 1 k -= 1 elif arr[mid] < key: low = mid + 1 k -= 2 else: if mid <= high: return mid else: return None return None # 哈希查找 class HashStruct: def __init__(self): self.elem = HashStruct self.count = 0 def HashSearch(hashTable, key): addr = key % len(hashTable) while hashTable.elem[addr] != key: addr = (addr + 1) % L if hashTable.elem[addr] == None || addr == (key % len(hashTable)): return None; return addr

// 顺序查找 func LinearSearch(arr []int, key int) { for i, v := range arr { if key == v { return i } } return -1 } // 二分查找 func BinSearch(arr []int, key int) { mid, low , high := 0, 0, len(arr) - 1 for low <= high { mid = (low + high) / 2 if key == arr[mid] { return mid } else if key < arr[mid] { high = mid - 1 } else { low = mid + 1 } } return -1 } // 插值查找 func InsertSearch(arr, key) { mid, low, high := 0, 0, len(arr) - 1 for low <= high { mid = low + (key - arr[low]) * (high - low) / (arr[high] - arr[low]) if arr[mid] == key { return mid } else if arr[mid] > key { high = mid - 1 } else{ low = mid + 1 } } return -1 } // 斐波那契查找 func FibonacciSearch(arr, key){ var F [len(arr)]int F[0], F[1] = 1, 1 for i := 2; i < len(arr); i++ { F[i] = F[i-1] + F[i-1] } k, low, high := 0, 0, len(arr) - 1 for len(arr) > F[k] - 1 { k++ } for i := len(arr); i < F[k] - 1; i++ { arr[i] = arr[high] } for low <= high { mid = low + F[k-1] - 1 if arr[mid] > key { high = mid - 1 k-- } else if arr[mid] < key { low = mid + 1 k -= 2 } else { if mid <= high { return mid } else { return -1 } } } return -1 } // 哈希查找 type HashTable struct { elem *HashTable count int } func HashSearch(hashTable, key) { addr := key % len(hashTable) for hashTable.elem[addr] != key { addr = (addr + 1) % len(hashTable) if hashTable.elem[addr] == "" || addr == (key % len(hashTable)) { return -1 } } return addr }

usestd::cmp::{PartialEq,PartialOrd};// 顺序查找 fn LinearSearch<T:PartialEq>(arr: &[T],key: &T)-> Option<usize>{for(i,data)inarr.iter().enumerate(){ifkey==data{Some(i)}}None}// 二分查找 fn BinarySearch<T:PartialEq +PartialOrd>(arr: &[T],key: &T)-> Option<usize>{ifarr.is_empty(){None}letmutmid: usize;letmut(low,high)=(0,arr.len()-1);while(low<=high){mid=low+(high-low)/2;ifkey<&arr[mid]{high=mid-1;}elseifkey>arr[mid]{low=mid+1;}else{Some(mid)}}None}// 插值查找 fn InsertSearch<T:PartialEq +PartialOrd>(arr: &[T],key: &T)-> Option<usize>{letmutmid: usize;letmut(low,high)=(0,arr.len()-1);whilelow<=high{mid=low+(key-arr[low])*(high-low)/(arr[high]-arr[low]);ifkey==&arr[mid]{Some(mid)}elseifkey<&arr[mid]{high=mid-1;}else{low=mid+1;}}None}// 斐波那契查找 fn FibonacciSearch<T:PartialEq +PartialOrd>(arr: &[T],key: &T)-> Option<usize>{letmutF: [usize;arr.len()];F[0]=1;F[1]=1;foriin2..arr.len(){F[i]=F[i-1]+F[i-1];}letmutk=0;letmutmidusize;letmut(low,high)=(0,arr.len()-1);whilehigh>F[k]-1{k+=1;}foriinarr.len()..F[k]-1{arr[i]=arr[high];}whilelow<=high{mid=low+F[k-1]-1;ifkey<&arr[mid]{high=mid-1;k-=1;}elseifkey>&arr[mid]{low=mid+1;k-=2;}else{ifmid<=high{Some(mid)}else{None}}}None}// 哈希查找 fn HashSearch<T:PartialEq>(hashTable: &HashTable<T>,key: &T)-> Option<usize>{letmutaddr:usize;addr=key%len(hashTable);while&hashTable.elem[addr]!=key{addr=(addr+1)%&hashTable.len()if&hashTable.elem[addr]==""||addr==(key%&hashTable.len()){None}}Some(addr)}

// 线性查找 int LinearSearch(List<int> arr, int key) { for (int i = 0; i < arr.length; i++) { if (arr[i] == key) { return i; } } return -1; } // 二分查找 int BinarySearch(List<int> arr, int key) { if arr.length == 0 { return -1; } int low = 0; int high = arr.length - 1; int mid; while (low <= high) { mid = (low + high) ~/ 2; if (key == arr[mid]) { return mid; } else if (key < arr[mid]) { high = mid - 1; } else { low = mid + 1; } } return -1; } // 插值查找 int InsertSearch(List<int> arr, int key) { int mid; int low = 0; int high = arr.length - 1; while (low <= high) { mid = low + (key - arr[low]) * (high - low) ~/ (arr[high] - arr[low]); if (key == arr[mid]) { return mid; } else if (key < arr[mid]) { high = mid - 1; } else { low = mid + 1; } } return -1; } // 斐波那契查找 int FibonacciSearch(List<int> arr, int key) { List<int> F = List(); F[0] = 1; F[1] = 1; for (int i = 2; i < arr.length; i++) { F.add(F[i-1] + F[i-1]); } int k = 0; while ( arr.length > F[k] - 1) { k++; } int mid = 0; int low = 0; int high = arr.length - 1; for (int i = arr.length; i < F[k] - 1; i++) { arr[i] = arr[high]; } while (low <= high) { mid = low + F[k-1] - 1; if (key < arr[mid]) { high = mid - 1; k--; } else if (arr[mid] < key) { low = mid + 1; k -= 2; } else { if (mid <= high) { return mid; } else { return -1; } } } return -1; }