jtahstu的博客

Git仓库   英文博客  

最新碎语:以后没事写写小的知识点吧

您的位置:jtahstu的博客 >算法> 数据结构与算法从入门到懵逼 - 查找算法

数据结构与算法从入门到懵逼 - 查找算法

基础查找(顺序、折半、差值、斐波那契查找)

#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */

typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码,如OK等 */

int F[100]; /* 斐波那契数列 */

/* 无哨兵顺序查找,a为数组,n为要查找的数组个数,key为要查找的关键字 */
int Sequential_Search(int *a,int n,int key) {
    int i;
    for(i=1; i<=n; i++) {
        if (a[i]==key)
            return i;
    }
    return 0;
}
/* 有哨兵顺序查找 */
int Sequential_Search2(int *a,int n,int key) {
    int i;
    a[0]=key;
    i=n;
    while(a[i]!=key) {
        i--;
    }
    return i;
}

/* 折半查找 */
int Binary_Search(int *a,int n,int key) {
    int low,high,mid;
    low=1;	/* 定义最低下标为记录首位 */
    high=n;	/* 定义最高下标为记录末位 */
    while(low<=high) {
        mid=(low+high)/2;	/* 折半 */
        if (key<a[mid])		/* 若查找值比中值小 */
            high=mid-1;		/* 最高下标调整到中位下标小一位 */
        else if (key>a[mid])/* 若查找值比中值大 */
            low=mid+1;		/* 最低下标调整到中位下标大一位 */
        else {
            return mid;		/* 若相等则说明mid即为查找到的位置 */
        }

    }
    return 0;
}

/* 插值查找 */
int Interpolation_Search(int *a,int n,int key) {
    int low,high,mid;
    low=1;	/* 定义最低下标为记录首位 */
    high=n;	/* 定义最高下标为记录末位 */
    while(low<=high) {
        mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */
        if (key<a[mid])		/* 若查找值比插值小 */
            high=mid-1;		/* 最高下标调整到插值下标小一位 */
        else if (key>a[mid])/* 若查找值比插值大 */
            low=mid+1;		/* 最低下标调整到插值下标大一位 */
        else
            return mid;		/* 若相等则说明mid即为查找到的位置 */
    }
    return 0;
}

/* 斐波那契查找 */
int Fibonacci_Search(int *a,int n,int key) {
    int low,high,mid,i,k=0;
    low=1;	/* 定义最低下标为记录首位 */
    high=n;	/* 定义最高下标为记录末位 */
    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 (key<a[mid]) {
            high=mid-1;
            k=k-1;
        } else if (key>a[mid]) {
            low=mid+1;
            k=k-2;
        } else {
            if (mid<=n)
                return mid;		/* 若相等则说明mid即为查找到的位置 */
            else
                return n;
        }

    }
    return 0;
}

int main(void) {

    int a[MAXSIZE+1],i,result;
    int arr[MAXSIZE]= {0,1,16,24,35,47,59,62,73,88,99};

    for(i=0; i<=MAXSIZE; i++) {
        a[i]=i;
    }
    result=Sequential_Search(a,MAXSIZE,MAXSIZE);
    printf("Sequential_Search:%d \n",result);
    result=Sequential_Search2(a,MAXSIZE,1);
    printf("Sequential_Search2:%d \n",result);

    result=Binary_Search(arr,10,62);
    printf("Binary_Search:%d \n",result);


    result=Interpolation_Search(arr,10,62);
    printf("Interpolation_Search:%d \n",result);


    F[0]=0;
    F[1]=1;
    for(i = 2; i < 100; i++) {
        F[i] = F[i-1] + F[i-2];
    }
    result=Fibonacci_Search(arr,10,62);
    printf("Fibonacci_Search:%d \n",result);

    return 0;
}

二叉排序树

#include<stdio.h>
#include<stdlib.h>

typedef struct Node {
    int data;
    struct Node *lchild;
    struct Node *rchild;
} NODE,*BSTree;

/*
在指针T所指的二叉排序树中递归查找关键字为key的元素,
若查找成功,则返回指向该元素节点的指针,否则返回NULL
*/
BSTree SearchBST(BSTree T,int key) {
    if(!T || T->data == key) //查找到时返回的T为该元素节点,没查找到时为NULL
        return T;
    else if(key < T->data)            //如果key小于当前节点的值,则在其左子树中递归查找
        return SearchBST(T->lchild,key);
    else                                //如果key大于当前节点的值,则在其右子树中递归查找
        return SearchBST(T->rchild,key);
}

/*
在指针T所指的二叉排序树中递归查找关键字为key的元素,
若查找成功,则返回ture,并查找到的数据对应的节点指针保存在p中,
否则返回false,并将查找路径上访问的最后一个节点指针保存在p中。
这里的参数parent指向每次递归遍历的子树的根节点的父节点,即始终是参数T的父节点,
它的初始值为NULL,其目的是跟踪查找路径上访问的当前节点的父节点(即上一个访问节点)
该函数用来被后面的插入函数调用。
*/
bool SearchBST(BSTree T,int key,BSTree parent,BSTree &p) {
    if(!T) {       //如果T为NULL,则查找不成功
        //这里包含了树空,即T为NULL的情况
        p = parent;
        return false;
    } else {         //否则,继续查找
        if(key == T->data) {         //如果相等,则查找成功
            p = T;
            return true;
        } else if(key < T->data)      //在左子树中递归查找
            return SearchBST(T->lchild,key,T,p);
        else                            //在右子树中递归查找
            return SearchBST(T->rchild,key,T,p);
    }
}

/*
当在T所指向的二叉排序树中查找不到关键字为key的数据元素时,
将其插入该二叉排序树,并返回ture,否则返回false。
树空时插入会改变根节点的值,因此要传入引用。
*/
bool InsertBST(BSTree &T,int key) {
    BSTree p;
    if(!SearchBST(T,key,NULL,p)) {      //如果查找失败,则执行插入操作
        //为新节点分配空间,并对各域赋值
        BSTree pNew = (BSTree)malloc(sizeof(NODE));
        pNew->data = key;
        pNew->lchild = pNew->rchild = NULL;

        if(!p)                          //如果树空,则直接置pNew为根节点
            T = pNew;
        else if(key < p->data)            //作为左孩子插入p的左边
            p->lchild = pNew;            //作为右孩子插入p的右边
        else
            p->rchild = pNew;
        return true;
    } else
        return false;
}

/*
采用第一种算法从二叉排序树中删除指针p所指向的节点,
并在保持二叉排序树有序的情况下,将其左右子树重接到该二叉排序树中.
该函数主要用来被后面的删除函数调用
*/
void DeleteNode1(BSTree &p) {
    BSTree q,s;
    if(!p->lchild) {
        //如果左子树为空,则只需重接其右子树
        //这里包含了左右子树均为空的情况
        q = p;
        p = p->rchild ;
        free(q);
    } else if(!p->rchild) {
        //如果右子树为空,则只需重接其左子树
        q = p;
        p = p->lchild;
        free(q);
    } else {
        //如果左右子树都不为空,我们采取第一种方法来重接左右子树,
        //我们这里采取修改左子树的方法,也可以修改右子树,方法类似
        s = p->lchild;       //取待删节点的左节点

        //一直向右,最终s为待删节点的前驱节点
        //如果将各节点元素按从小到大顺序排列成一个序列,
        //则某节点的前驱节点即为序列中该节点的前面一个节点
        while(s->rchild)
            s = s->rchild;
        s->rchild = p->rchild;    //将p的右子树接为s的右子树
        q = p;
        p = p->lchild;       //将p的左子树直接接到其父节点的左子树上
        free(q);
    }
}

/*
采用第二种算法从二叉排序树中删除指针p所指向的节点,
并在保持二叉排序树有序的情况下,将其左右子树重接到该二叉排序树中.
该函数主要用来被后面的删除函数调用
*/
void DeleteNode2(BSTree &p) {
    BSTree q,s;
    if(!p->lchild) {
        //如果左子树为空,则只需重接其右子树
        //这里包含了左右子树均为空的情况
        q = p;
        p = p->rchild ;
        free(q);
    } else if(!p->rchild) {
        //如果右子树为空,则只需重接其左子树
        q = p;
        p = p->lchild;
        free(q);
    } else {
        //如果左右子树都不为空,我们采取第二种方法来重接左右子树,
        //我们这里采取修改左子树的方法,也可以修改右子树,方法类似
        q = p;
        s = p->lchild;       //取待删节点的左节点
        while(s->rchild) {
            //一直向右,最终s为待删节点的前驱节点。
            //如果将各节点元素按从小到大顺序排列成一个序列,
            //则某节点的前驱节点即为序列中该节点的前面一个节点
            q = s;
            s = s->rchild;
        }
        //用s来替换待删节点p
        p->data = s->data;
        //根据情况,将s的左子树重接到q上
        if(p != q)
            q->rchild = s->lchild;
        else
            q->lchild =s->lchild;
        free(s);
    }
}

/*
若T所指向的二叉排序树中查找到关键字为key的数据元素,
则删除该元素对应的节点,并返回true,否则返回false
如果要删除的恰好是根节点,则会改变根节点的值,因此要传入引用
*/
bool DeleteBST(BSTree &T,int key) {
    //不存在关键字为key的节点
    if(!T)
        return false;
    else {
        if(key == T->data) {     //查找到关键字为key的节点
            DeleteNode1(T);
            //          DeleteNode2(T);
            return true;
        } else if(key < T->data) //继续查找左子树
            return DeleteBST(T->lchild,key);
        else                        //继续查找右子树
            return DeleteBST(T->rchild,key);
    }
}

/*
根据所给的长为len的arr数组,按数组中元素的顺序构建一棵二叉排序树
*/
BSTree CreatBST(int *arr,int len) {
    BSTree T = NULL;
    int i;
    //按顺序逐个节点插入到二叉排序树中
    for(i=0; i<len; i++)
        InsertBST(T,arr[i]);
    return T;
}

/*
递归中序遍历二叉排序树,得到元素从小到大有序排列的序列
*/
void inTraverse(BSTree T) {
    if(T) {
        if(T->lchild)
            inTraverse(T->lchild);
        printf("%d ",T->data);
        if(T->rchild)
            inTraverse(T->rchild);
    }
}

int main() {
    int i;
    int num;
    printf("请输入节点个数:");
    scanf("%d",&num);

    //输入num个整数
    int *arr = (int *)malloc(num*sizeof(int));
    printf("请依次输入这%d个整数(必须互不相等):",num);
    for(i=0; i<num; i++)
        scanf("%d",arr+i);

    //中序遍历该二叉排序树,使数据按照从小到大的顺序输出
    BSTree T = CreatBST(arr,num);
    printf("中序遍历该二叉排序树的结果:");
    inTraverse(T);
    printf("\n");

    //查找给定的整数
    int key;
    printf("请输入要查找的整数:");
    scanf("%d",&key);
    if(SearchBST(T,key))
        printf("查找成功\n");
    else
        printf("查找不到该整数\n");

    //插入给定的整数
    printf("请输入要插入的整数:");
    scanf("%d",&key);
    if(InsertBST(T,key)) {
        printf("插入成功,插入后的中序遍历结果:");
        inTraverse(T);
        printf("\n");
    } else
        printf("插入失败,该二叉排序树中已经存在整数%d\n",key);

    //删除给定的整数
    printf("请输入要删除的整数:");
    scanf("%d",&key);
    if(DeleteBST(T,key)) {
        printf("删除成功,插入后的中序遍历结果:");
        inTraverse(T);
        printf("\n");
    } else
        printf("删除失败,该二叉排序树中不存在整数%d\n",key);

    return 0;
}

散列表

#include <stdio.h>
#define HASH_LEN 13
#define TABLE_LEN 8
int data[TABLE_LEN]={69,65,90,37,92,6,28,54}; //原始数据 
int hash[HASH_LEN]={0};//哈希表,初始化为0 
void InsertHash(int hash[],int m,int data) //将关键字data插入哈希表hash中 
{
    int i;
    i=data % 13;//计算哈希地址 
    while(hash[i]) //元素位置已被占用
        i=(++i) % m; //线性探测法解决冲突
    hash[i]=data;
}
void CreateHash(int hash[],int m,int data[],int n)
{
    int i;
    for(i=0;i<n;i++) //循环将原始数据保存到哈希表中 
        InsertHash(hash,m,data[i]); 
}
int HashSearch(int hash[],int m,int key)
{
    int i;
    i=key % 13;//计算哈希地址 
    while(hash[i] && hash[i]!=key) //判断是否冲突 
        i=(++i) % m; //线性探测法解决冲突
    if(hash[i]==0) //查找到开放单元,表示查找失败 
        return -1;//返回失败值 
    else//查找成功 
        return i;//返回对应元素的下标 
}
int main()
{
    int key,i,pos;
    CreateHash(hash,HASH_LEN,data,TABLE_LEN);//调用函数创建哈希表 
    printf("哈希表各元素的值:"); 
    for(i=0;i<HASH_LEN;i++)
        printf("%ld ",hash[i]);
    printf("\n");
    printf("输入查找关键字:");
    scanf("%ld",&key);
    pos=HashSearch(hash,HASH_LEN,key); //调用函数在哈希表中查找 
    if(pos>0)
        printf("查找成功,该关键字位于数组的第%d个位置。\n",pos);
    else
        printf("查找失败!\n");
    getch();
    return 0;
}

---

本文章采用 知识共享署名2.5中国大陆许可协议 进行许可,欢迎转载,演绎或用于商业目的。

---

二维码加载中...

扫一扫移动端访问O(∩_∩)O

发表评论

25 + 26 =
路人甲 表情
看不清楚?点图切换 Ctrl+Enter快速提交
正在加载中……