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

文章目录[隐藏]

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

// 分块查找
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;
}

// 分块查找
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;
}

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 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 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
}

// 二分查找
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;
}