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;

};