数据结构查找实验顺序、折半

#include

#include

typedef int Elemtype;

void caidan()            //菜单函数

{

    printf("欢迎来到查找实验！\\n");

    printf("实验内容：\\n");

    printf("    1)建立一个无序表并实现其上的顺序查找；\\n");

    printf("    2)建立一个有序表并实现其上的折半查找（用递归和非递归两种算法实现）。\\n");

    printf("********************************************\\n");

    printf("* 1.顺序查找·····\\n");

    printf("* 2.折半查找递归···\\n");

    printf("* 3.折半查找非递归··\\n");

    printf("* 4.退出·······\\n");

    printf("**************************\\n");

    printf("请选择：");

}

int SeqSeach(Elemtype a[],int n, Elemtype key)            //顺序查找

{

    int i;

    for (i=0;i    {

        if (key==a[i])

        {

            return i+1;

        }

    }

    return 0;

}

void shuchu(Elemtype a[])            //输出函数

{

    int i;

    printf("数组里的数据：\\n");

    for (i=0;i<20;i++)

    {

        printf("%4d",a[i]);

    }

    printf("\\n");

}

void shunzhao()                //顺序查找

{

    int x,i;

    Elemtype test[20]={234,123,345,44,33,22,11,55,66,77,88,99,87,76,65,1,2,3,4,5};

    shuchu(test);

    printf("请输入要查找的数据：\\n");

    scanf("%d",&x);

    i=SeqSeach(test,20,x);

    if(1<=i && i<=20)

    {

        printf("查找成功！这个数是数组的第%d个数，下标为：%d\\n",i,i-1);

        printf("\\n");

    }

    else

    {

        printf("对不起！查找失败！\\n");

        printf("\\n");

    }

    shuchu(test);

}

int BinSeach1(Elemtype a[],int low,int high, Elemtype key)        //递归

{

    int mid;

    mid=(low+high)/2;

    if(a[mid]==key)

    {

        return mid+1;

    }

    else 

    {

        if (low==high && a[mid]!=key)

        {

            return 0;

        }

    }

    if (a[mid]>key)

    {

        return BinSeach1(a,low,mid-1,key);

    }

    else

    {

        return BinSeach1(a,mid+1,high,key);

    }

}

void zhezhaod()                //折半查找递归

{

    int i,x,low=0,high=19;

    Elemtype test[20]={20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39};

    shuchu(test);

    printf("请输入要查找的数据：\\n");

    scanf("%d",&x);

    i=BinSeach1(test,low,high,x);

    if (i>=1 && i<=20)

    {

        printf("查找成功！此数据是数组的第%d个数，下标是：%d\\n",i,i-1);

        printf("\\n");

    }

    else 

    {

        printf("对不起！查找失败！\\n");

        printf("\\n");

    }

    shuchu(test);

}

int BinSeach2(Elemtype a[],int low,int high, Elemtype key)    //非递归

{

    int mid;

    while (low<=high)

    {

        mid=(low+high)/2;

        if (a[mid]==key)

            return mid+1;

        else 

        {

            if (a[mid]>key)

                high=mid-1;

            else 

                low=mid+1;

        }

    }

    return 0;

}

void zhezhaofd()        //折半查找非递归

{

    int i,x,low=0,high=20;

    Elemtype test[20]={20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39};

    shuchu(test);

    printf("请输入要查找的数据：\\n");

    scanf("%d",&x);

    i=BinSeach2(test,low,high,x);

    if (i>=1 && i<=20)

    {

        printf("查找成功！此数据是数组的第%d个数，下标是：%d\\n",i,i-1);

        printf("\\n");

    }

    else 

    {

        printf("对不起！查找失败！\\n");

        printf("\\n");

    }

    shuchu(test);

}

void main()            //主函数

{

    int flag=1,c;

    while (flag)

    {

        caidan();            //调用菜单

        scanf("%d",&c);

        switch (c)

        {

            case 1:

                shunzhao();        //调用顺序查找

                getch();

                system("CLS");

                break;

            case 2:

                zhezhaod();        //折半查找（递归）

                getch();

                system("CLS");

                break;

             case 3:

                zhezhaofd();    //折半查找非递归

                getch();

                system("CLS");

                break;

            default:

                flag=0;

                printf("实验结束！谢谢使用！欢迎提出改进建议！\\n");

                break;

        }

    }

}