查找——顺序、折半、插值、斐波那契与二叉树

顺序查找法

从头到尾简单的查找，可以利用哨兵进行改进
利用哨兵避免了if判断语句，加快了速度。
普通顺序查找法

int seq_search(int a[],int n,int key)
{
    for(int i = 1 ; i <= n ; i++)
      if(a[i] == key)
        return i;
     return 0;
}

哨兵改进

int seq_search(int a[],int n,int key)
{
    a[0] = key;

    while(a[n] != key)
        n--;

    return n;
}

折半查找法

即二分法查找，可以看做一颗二叉树。
mid = （start+end）/2 = start+(end-start)/2

int binary_search(int a[],int n,int key)
{
    int start = 1, end = n;
    int mid;

    while(start <= end)
    {
        mid = (start+end)/2;
        if(a[mid] > key)
            end = mid-1;
        else if(a[mid] < key)
            start = mid+1;
        else
            return mid;
    }
    return 0;
}

插值查找法
若你在字典中找单词apple必然是从头开始翻，找zoo必然从结尾开始，那么插值查找法就是这种原理，属于对折半查找法的改进（对折半的1/2进行改进）。
mid = start + （key-a【start】）/ (a【end】-a【start】) * （end-start）

int insert_search(int a[],int n,int key)
{
    int start = 1;
    int end = n;
    int mid;

    while(start <= end)
    {
        mid = start + (key-a[start])/(a[end]-a[start]) * (end-start);
        if(a[mid] > key)
            end = mid-1;
        else if(a[mid] < key)
            start = mid+1;
        else
            return mid;
    }

    return 0;
}

斐波那契查找法

利用黄金分割原理实现，算法复杂度也为O（logn）但因为不需要涉及乘除只需要加减，理论上比折半查找法快。

int fibo_search(int a[],int n,int key)
{
    int i,k;
    int low = 1;
    int high = n, mid;
    k = 0;
    while(n > f[k]-1)
        k++;

    for(i = n ; i < f[k]-1 ; i++)
        a[i] = a[n];

    while(low<=high)
    {
        mid = low + f[k-1] - 1;

        if(a[mid] > key)
        {
            high = mid - 1;
            k -= 1;
        }
        else if(a[mid] < key)
        {
            low = mid + 1;
            k -= 2;
        }
        else
        {
            if(mid <= n)
                return mid;
            else
                return n;
        }
    }
    return 0;
}

二叉树

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct treenode
{
    int data;
    struct treenode *left, *right;
}TreeNode,*BiTree;


bool Search(BiTree root,int key,BiTree f,BiTree *p)
{
    if(!root)
    {
        *p = f;
        return false;
    }

    if(key == root->data)
    {
        *p = root;
        return true;
    }
    else if(key > root->data)
        Search(root->right,key,root,p);
    else
        Search(root->left,key,root,p);
}

bool insert(BiTree *root,int data)
{
    BiTree p,s;

    if(!Search(*root,data,NULL,&p))
    {
        s = (BiTree)malloc(sizeof(TreeNode));
        s->data = data;
        s->left = NULL;
        s->right = NULL;


        if(!p)
            *root = s;
        else{
        if(data > p->data)
            p->right = s;
        else
            p->left = s;
        }

        return true;
    }

    return false;
}

void Delete(BiTree *p)  //要改变指针的指向只能用指针的指针
{
    BiTree s,q;

    q = *p;
    if(q->left == NULL)
    {
        *p = q->right;
        free(q);
    }
    else if(q->right == NULL)
    {
        *p = q->left;
        free(q);
    }
    else
    {
        s = q->left;
        while(s->right)
        {
            q = s;
            s = s->right;
        }
        (*p)->data = s->data;
        if(q != *p)
            q->right = s->left;
        else
            q->left = s->left;
        free(s);
    }
}

bool DeleteBST(BiTree *root,int key)
{
    if(!(*root))
        return false;

    if(key > (*root)->data)
        return DeleteBST(&((*root)->right),key);
    else if(key < (*root)->data)
       return DeleteBST(&((*root)->left),key);
    else
      Delete(root);

    return true;
}

void Init(int nums[],BiTree *root,int n)
{
    for(int i = 0 ; i < n ; i++)
        insert(root,nums[i]);
}


void free_all(BiTree root)
{
    if(root)
    {
        BiTree s = root->right;
        free_all(root->left);
        free(root);
        free_all(s);
    }
}

void Print_Mid(BiTree root)
{
    if(root)
    {
        Print_Mid(root->left);
        printf("%d ",root->data);
        Print_Mid(root->right);
    }
}

int main()
{
    int nums[10] = {35,37,47,51,58,62,73,88,93,99};
    BiTree root = NULL;
    Init(nums,&root,10);
    printf("打印二叉树:");
    Print_Mid(root);
    putchar('\n');
    DeleteBST(&root,47);
    printf("删除了47后的二叉树打印:");
    Print_Mid(root);
    free_all(root);
    return 0;
}