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;

};

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,080评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,422评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,630评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,554评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,662评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,856评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,014评论 3赞 408
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,752评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,212评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,541评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,687评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,347评论 4赞 331
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,973评论 3赞 315
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,777评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,006评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,406评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,576评论 2赞 349

推荐阅读更多精彩内容