c++ 查找
// 顺序查找
int SequentialSearch(vector<int>& v, int k) {
for (int i = 0; i < v.size(); ++i)
if (v[i] == k)
return i;
return -1;
}
// 二分查找（折半查找）：对于已排序，若无序，需要先排序
// 非递归
int BinarySearch(vector<int> v, int value)
{
if (v.size() <= 0)
return -1;
int low = 0;
int high = v.size() - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (v[mid] == value)
return mid;
else if (v[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
// 递归
int BinarySearch2(vector<int> v, int value, int low, int high)
{
if (low > high)
return -1;
int mid = low + (high - low) / 2;
if (v[mid] == value)
return mid;
else if (v[mid] > value)
return BinarySearch2(v, value, low, mid - 1);
else
return BinarySearch2(v, value, mid + 1, high);
}
//插值查找
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);
}
// 斐波那契查找
#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=2;i<max_size;++i)
F[i]=F[i-1]+F[i-2];
}
/*定义斐波那契查找法*/
int FibonacciSearch(int *a, int n, int key) //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
{
int low=0;
int high=n-1;
int F[max_size];
Fibonacci(F);//构造一个斐波那契数组F
int k=0;
while(n>F[k]-1)//计算n位于斐波那契数列的位置
++k;
int * temp;//将数组a扩展到F[k]-1的长度
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; //若相等则说明mid即为查找到的位置
else
return n-1; //若mid>=n则说明是扩展的数值,返回n-1
}
}
delete [] temp;
return -1;
}
int main()
{
int a[] = {0,16,24,35,47,59,62,73,88,99};
int key=100;
int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
cout<<key<<" is located at:"<<index;
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#define SUCCESS 1
#define UNSUCCESS 0
#define OVERFLOW -1
#define OK 1
#define ERROR -1
typedef int Status;
typedef int KeyType;
typedef struct{
KeyType key;
}RcdType;
typedef struct{
RcdType *rcd;
int size;
int count;
int *tag;
}HashTable;
int hashsize[] = { 11, 31, 61, 127, 251, 503 };
int index = 0;
Status InitHashTable(HashTable &H, int size){
int i;
H.rcd = (RcdType *)malloc(sizeof(RcdType)*size);
H.tag = (int *)malloc(sizeof(int)*size);
if (NULL == H.rcd || NULL == H.tag) return OVERFLOW;
for (i = 0; i< size; i++) H.tag[i] = 0;
H.size = size;
H.count = 0;
return OK;
}
int Hash(KeyType key, int m){
return (3 * key) % m;
}
void collision(int &p, int m){ //线性探测
p = (p + 1) % m;
}
Status SearchHash(HashTable H, KeyType key, int &p, int &c) {
p = Hash(key, H.size);
int h = p;
c = 0;
while ((1 == H.tag[p] && H.rcd[p].key != key) || -1 == H.tag[p]){
collision(p, H.size); c++;
}
if (1 == H.tag[p] && key == H.rcd[p].key) return SUCCESS;
else return UNSUCCESS;
}
void printHash(HashTable H) //打印哈希表
{
int i;
printf("key : ");
for (i = 0; i < H.size; i++)
printf("%3d ", H.rcd[i].key);
printf("\n");
printf("tag : ");
for (i = 0; i < H.size; i++)
printf("%3d ", H.tag[i]);
printf("\n\n");
}
Status InsertHash(HashTable &H, KeyType key); //对函数的声明
//重构
Status recreateHash(HashTable &H){
RcdType *orcd;
int *otag, osize, i;
orcd = H.rcd;
otag = H.tag;
osize = H.size;
InitHashTable(H, hashsize[index++]);
//把所有元素，按照新哈希函数放到新表中
for (i = 0; i < osize; i++){
if (1 == otag[i]){
InsertHash(H, orcd[i].key);
}
}
}
Status InsertHash(HashTable &H, KeyType key){
int p, c;
if (UNSUCCESS == SearchHash(H, key, p, c)){ //没有相同key
if (c*1.0 / H.size < 0.5){ //冲突次数未达到上线
//插入代码
H.rcd[p].key = key;
H.tag[p] = 1;
H.count++;
return SUCCESS;
}
else recreateHash(H); //重构哈希表
}
return UNSUCCESS;
}
Status DeleteHash(HashTable &H, KeyType key){
int p, c;
if (SUCCESS == SearchHash(H, key, p, c)){
//删除代码
H.tag[p] = -1;
H.count--;
return SUCCESS;
}
else return UNSUCCESS;
}
void main()
{
printf("-----哈希表-----\n");
HashTable H;
int i;
int size = 11;
KeyType array[8] = { 22, 41, 53, 46, 30, 13, 12, 67 };
KeyType key;
RcdType e;
//初始化哈希表
printf("初始化哈希表\n");
if (SUCCESS == InitHashTable(H, hashsize[index++])) printf("初始化成功\n");
//插入哈希表
printf("插入哈希表\n");
for (i = 0; i <= 7; i++){
key = array[i];
InsertHash(H, key);
printHash(H);
}
//删除哈希表
printf("删除哈希表\n");
int p, c;
if (SUCCESS == DeleteHash(H, 12)) {
printf("删除成功，此时哈希表为：\n");
printHash(H);
}
//查询哈希表
printf("查询哈希表\n");
if (SUCCESS == SearchHash(H, 67, p, c)) printf("查询成功\n");
//再次插入，测试哈希表的重构
printf("再次插入，测试哈希表的重构：\n");
KeyType array1[8] = { 27, 47, 57, 47, 37, 17, 93, 67 };
for (i = 0; i <= 7; i++){
key = array1[i];
InsertHash(H, key);
printHash(H);
}
}
/*
二叉搜索树的查找算法:
在二叉搜索树b中查找x的过程为：
1. 若b是空树，则搜索失败，否则：
2. 若x等于b的根节点的数据域之值，则查找成功；否则：
3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：
4. 查找右子树。
*/
// 在根指针T所指二叉查找树中递归地查找其关键字等于key的数据元素，若查找成功，
// 则指针p指向該数据元素节点，并返回TRUE，否则指针指向查找路径上访问的最终
// 一个节点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){
if(!T) { //查找不成功
p=f;
return false;
}
else if (key == T->data.key) { //查找成功
p=T;
return true;
}
else if (key < T->data.key) //在左子树中继续查找
return SearchBST(T->lchild, key, T, p);
else //在右子树中继续查找
return SearchBST(T->rchild, key, T, p);
}
#define BLACK 1
#define RED 0
#include <iostream>
using namespace std;
class bst {
private:
struct Node {
int value;
bool color;
Node *leftTree, *rightTree, *parent;
Node() : value(0), color(RED), leftTree(NULL), rightTree(NULL), parent(NULL) { }
Node* grandparent() {
if(parent == NULL){
return NULL;
}
return parent->parent;
}
Node* uncle() {
if(grandparent() == NULL) {
return NULL;
}
if(parent == grandparent()->rightTree)
return grandparent()->leftTree;
else
return grandparent()->rightTree;
}
Node* sibling() {
if(parent->leftTree == this)
return parent->rightTree;
else
return parent->leftTree;
}
};
void rotate_right(Node *p){
Node *gp = p->grandparent();
Node *fa = p->parent;
Node *y = p->rightTree;
fa->leftTree = y;
if(y != NIL)
y->parent = fa;
p->rightTree = fa;
fa->parent = p;
if(root == fa)
root = p;
p->parent = gp;
if(gp != NULL){
if(gp->leftTree == fa)
gp->leftTree = p;
else
gp->rightTree = p;
}
}
void rotate_left(Node *p){
if(p->parent == NULL){
root = p;
return;
}
Node *gp = p->grandparent();
Node *fa = p->parent;
Node *y = p->leftTree;
fa->rightTree = y;
if(y != NIL)
y->parent = fa;
p->leftTree = fa;
fa->parent = p;
if(root == fa)
root = p;
p->parent = gp;
if(gp != NULL){
if(gp->leftTree == fa)
gp->leftTree = p;
else
gp->rightTree = p;
}
}
void inorder(Node *p){
if(p == NIL)
return;
if(p->leftTree)
inorder(p->leftTree);
cout << p->value << " ";
if(p->rightTree)
inorder(p->rightTree);
}
string outputColor (bool color) {
return color ? "BLACK" : "RED";
}
Node* getSmallestChild(Node *p){
if(p->leftTree == NIL)
return p;
return getSmallestChild(p->leftTree);
}
bool delete_child(Node *p, int data){
if(p->value > data){
if(p->leftTree == NIL){
return false;
}
return delete_child(p->leftTree, data);
} else if(p->value < data){
if(p->rightTree == NIL){
return false;
}
return delete_child(p->rightTree, data);
} else if(p->value == data){
if(p->rightTree == NIL){
delete_one_child (p);
return true;
}
Node *smallest = getSmallestChild(p->rightTree);
swap(p->value, smallest->value);
delete_one_child (smallest);
return true;
}else{
return false;
}
}
void delete_one_child(Node *p){
Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
if(p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL){
p = NULL;
root = p;
return;
}
if(p->parent == NULL){
delete p;
child->parent = NULL;
root = child;
root->color = BLACK;
return;
}
if(p->parent->leftTree == p){
p->parent->leftTree = child;
} else {
p->parent->rightTree = child;
}
child->parent = p->parent;
if(p->color == BLACK){
if(child->color == RED){
child->color = BLACK;
} else
delete_case (child);
}
delete p;
}
void delete_case(Node *p){
if(p->parent == NULL){
p->color = BLACK;
return;
}
if(p->sibling()->color == RED) {
p->parent->color = RED;
p->sibling()->color = BLACK;
if(p == p->parent->leftTree)
rotate_left(p->sibling());
else
rotate_right(p->sibling());
}
if(p->parent->color == BLACK && p->sibling()->color == BLACK
&& p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
p->sibling()->color = RED;
delete_case(p->parent);
} else if(p->parent->color == RED && p->sibling()->color == BLACK
&& p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
p->sibling()->color = RED;
p->parent->color = BLACK;
} else {
if(p->sibling()->color == BLACK) {
if(p == p->parent->leftTree && p->sibling()->leftTree->color == RED
&& p->sibling()->rightTree->color == BLACK) {
p->sibling()->color = RED;
p->sibling()->leftTree->color = BLACK;
rotate_right(p->sibling()->leftTree);
} else if(p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
&& p->sibling()->rightTree->color == RED) {
p->sibling()->color = RED;
p->sibling()->rightTree->color = BLACK;
rotate_left(p->sibling()->rightTree);
}
}
p->sibling()->color = p->parent->color;
p->parent->color = BLACK;
if(p == p->parent->leftTree){
p->sibling()->rightTree->color = BLACK;
rotate_left(p->sibling());
} else {
p->sibling()->leftTree->color = BLACK;
rotate_right(p->sibling());
}
}
}
void insert(Node *p, int data){
if(p->value >= data){
if(p->leftTree != NIL)
insert(p->leftTree, data);
else {
Node *tmp = new Node();
tmp->value = data;
tmp->leftTree = tmp->rightTree = NIL;
tmp->parent = p;
p->leftTree = tmp;
insert_case (tmp);
}
} else {
if(p->rightTree != NIL)
insert(p->rightTree, data);
else {
Node *tmp = new Node();
tmp->value = data;
tmp->leftTree = tmp->rightTree = NIL;
tmp->parent = p;
p->rightTree = tmp;
insert_case (tmp);
}
}
}
void insert_case(Node *p){
if(p->parent == NULL){
root = p;
p->color = BLACK;
return;
}
if(p->parent->color == RED){
if(p->uncle()->color == RED) {
p->parent->color = p->uncle()->color = BLACK;
p->grandparent()->color = RED;
insert_case(p->grandparent());
} else {
if(p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) {
rotate_left (p);
rotate_right (p);
p->color = BLACK;
p->leftTree->color = p->rightTree->color = RED;
} else if(p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) {
rotate_right (p);
rotate_left (p);
p->color = BLACK;
p->leftTree->color = p->rightTree->color = RED;
} else if(p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) {
p->parent->color = BLACK;
p->grandparent()->color = RED;
rotate_right(p->parent);
} else if(p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) {
p->parent->color = BLACK;
p->grandparent()->color = RED;
rotate_left(p->parent);
}
}
}
}
void DeleteTree(Node *p){
if(!p || p == NIL){
return;
}
DeleteTree(p->leftTree);
DeleteTree(p->rightTree);
delete p;
}
public:
bst() {
NIL = new Node();
NIL->color = BLACK;
root = NULL;
}
~bst() {
if (root)
DeleteTree (root);
delete NIL;
}
void inorder() {
if(root == NULL)
return;
inorder (root);
cout << endl;
}
void insert (int x) {
if(root == NULL){
root = new Node();
root->color = BLACK;
root->leftTree = root->rightTree = NIL;
root->value = x;
} else {
insert(root, x);
}
}
bool delete_value (int data) {
return delete_child(root, data);
}
private:
Node *root, *NIL;
};
