查找基本方法小结

转自：http://www.cnblogs.com/marrywindy/archive/2010/08/19/1803288.html

代码

二：查找
：顺序查找
（整型与零的比较，int i，用if（i!=0)，或if(i==0)。

#include "stdio.h"

bool SequenceSearch(int*& p,int k,int n,int& pos)
{
    int i=0;
    while (i<n && p[i]!=k)
    {
        i++;
    }
    if (i>=n)
    {
        return false;
    }
    pos=i;
    return true;
}

int main()
{
    int a[10]={4,7,1,3,2,9,8,0,5,6};
    int* ptr=a;
    int status;
    bool flag;
    flag=SequenceSearch(ptr,62,10,status);
    if (flag)
    {
        printf("Success:The No is %d \n",status);
    }
    else
        printf("Failure...\n");
    return 0;
}
:折半查找
    (前提是被查找序列必须是有序的，这次就忘记了，搞砸了！~~~~(>_<)~~~~ ，）
#include "stdio.h"

bool BinarySearch(int*& p,int key,int len,int& pos)
{
    int low,high,mid;
    low=0;
    high=len-1;
    while (low<=high)
    {
        mid=(low+high)/2;
        if (key<p[mid])
        {
            high=mid-1;
        }
        else if (key>p[mid])
        {
            low=mid+1;
        }
        else
        {
            pos=mid;
            break;
        }
    }
    if (low>high)
    {
        return false;
    }
    return true;
}

int main()
{
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    int* ptr=a;
    int status;
    bool result=BinarySearch(ptr,1,10,status);
    if (result)
    {
        printf("Success:the sequence No. is %d \n",status);
    }
    else
        printf("Failure...\n");

    return 0;
}
:分块查找
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"

/*
    分块查找，又称索引顺序查找，结合了顺序查找和索引查找。
: 索引查找过程中，采用的是二分法查找。
: 顺序查找过程中，采用的是顺序查找。
    索引表是有序的，分块表是块内无序，块间有序，前一个块的最大关键字要小于后一个块的最小关键字；但块内是无序的。
    现在主要是建立索引表的问题。
*/

typedef struct IndexTable
{
    int key;
    int address;
}Index;


bool IndexSearch(Index*& pIndex,int Indexlen,int*& p,int len,int k,int& pos)
{
    int low=0,high=Indexlen-1,mid;
    int b=len/Indexlen;
    while (low<=high)
    {
        mid=(low+high)/2;
        if (k>pIndex[mid].key)
        {
            low=mid+1;
        }
        else
            high=mid-1;
    }
    int i;
    if (low<Indexlen)
    {
        for (i=pIndex[low].address;i<=pIndex[low].address+b-1 && p[i]!=k;i++);
        if (i<=pIndex[low].address+b-1)
        {
            pos=i;
            return true;
        }
        else
            return false;
    }
    return false;
}

int main()
{
    int a[16]={9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82};
    int* ptr=a;
    Index* pInd=(Index*)malloc(sizeof(Index)*4);
    if (NULL==pInd)
    {
        exit(1);
    }
    for (int i=0;i<4;i++)
    {
        scanf("%d ,%d ",&pInd[i].key,&pInd[i].address);
    }
    bool flag;
    int status;
    flag=IndexSearch(pInd,4,ptr,16,38,status);
    if (flag)
    {
        printf("Success: The sequence No. is %d \n",status);
    }
    else
        printf("Failue...\n");
    return 0;
}
:二叉排序树的基本操作的实现
    二叉排序树：一颗空的二叉树，或者是一颗具有如下性质的二叉树：
    （1）：若左子树非空，则左子树上的所有结点的值均小于根结点的值
    （2）：若右子树非空，则右子树上的所有结点的值均小于根结点的值
    （3）：左，右子树又各是一颗二叉排序树
    
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"

typedef struct BTnode
{
    char data;
    struct BTnode* left,*right;
}BTree;

//创建一颗二叉树
BTree* Create()
{
    BTree* tree;
    char ch;
    scanf_s("%c",&ch);
    getchar();
    if (ch=='#')
    {
        return NULL;
    }
    else
    {
        tree=(BTree*)malloc(sizeof(BTree));
        if (NULL==tree)
        {
            return NULL;
        }
        tree->data=ch;
        tree->left=Create();
        tree->right=Create();
        return tree;
    }
}

//前序遍历
void Preorder(BTree* t)
{
    if (t!=NULL)
    {
        printf("%c ",t->data);
        Preorder(t->left);
        Preorder(t->right);
    }
}

//中序遍历
void Inorder(BTree* t)
{
    if (t!=NULL)
    {
        Inorder(t->left);
        printf("%c ",t->data);
        Inorder(t->right);
    }
}

//后序遍历
void Postorder(BTree* t)
{
    if (t!=NULL)
    {
        Postorder(t->left);
        Postorder(t->right);
        printf("%c ",t->data);
    }
}

//查找某一个结点
BTree* Search(BTree* t,char ch)
{
    if (NULL==t)
    {
        return NULL;
    }
    else
    {
        if (t->data==ch)
        {
            return t;
        }
        if (ch<t->data)
        {
            return Search(t->left,ch);
        }
        else
        {
            return Search(t->right,ch);
        }
    }
}

//插入一个结点
void Insert(BTree*& t,BTree* s)
{
    if (NULL==t)
    {
        t=s;
    }
    else if (s->data==t->data)
    {
        return;
    }
    else if (s->data<t->data)
    {
        Insert(t->left,s);
    }
    else if (s->data>t->data)
    {
        Insert(t->right,s);
    }
}

int main()
{
    BTree* bt1=Create();
    Preorder(bt1);
    printf("\n");
    Inorder(bt1);
    printf("\n");
    Postorder(bt1);
    printf("\n");

    BTree* bt2=Search(bt1,'c');
    if (bt2!=NULL)
    {
        printf("Success...\n");
        printf("The number is:%c \n",bt2->data);
    }
    else
        printf("Failure...\n");

    BTree* bt3=(BTree*)malloc(sizeof(BTree));
    if (NULL==bt3)
    {
        exit(1);
    }
    bt3->data='e';
    bt3->left=NULL;
    bt3->right=NULL;
    Insert(bt1,bt3);
    Preorder(bt1);
    printf("\n");
    return 0;
}