SWUST软件技术基础实验（3）查找算法的实现

港控/mmm° 2021-09-23 10:54 220阅读 0赞

实验目的：  
1.掌握顺序表上查找的实现及监视哨的作用。  
2.掌握折半查找所需的条件、折半查找的过程和实现方法。  
3.掌握二叉排序树的创建过程，掌握二叉排序树查找过程的实现。  
4.掌握哈希表的基本概念，熟悉哈希函数的选择方法，掌握使用线性探测法和链地址法进行冲突解决的方法。

实验内容：  
通过具体算法程序，进一步加深对各种查找方法的掌握，以及对实际应用中问题解决方法的掌握。  
各查找算法的输入序列：26 5 37 1 61 11 59 15 48 19

实验要求：  
1.顺序查找：首先从键盘输入一个数据序列生成一个顺序表，然后从键盘上任意输入一个值，在顺序表中进行查找。  
2.折半查找：任意输入一组数据作为各数据元素的键值，首先将此序列进行排序，然后在该有序表上使用折半查找算法进行对给定值key的查找。  
3.二叉树查找：任意输入一组数据作为二叉排序树中结点的键值，首先创建一颗二叉排序树，然后在此二叉排序树上实现对给定值k的查找过程。  
4.哈希表查找：任意输入一组数值作为各元素的键值，哈希函数为Hash(key)=key%11，用线性探测再散列法解决冲突问题。

代码一：删除了结构体elemtype 使代码更简洁 并替换了一些变量的命名

//查找算法实现
    //顺序查找，首先从键盘输入一个数据序列生成一个顺序表，然后从键盘上任意输入一个值，在顺序表中进行查找
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    const int MAX=100;
    typedef int datatype;
    typedef struct
    { 
        datatype elem[MAX+1];
        int length;
    } Stable;
    void create(Stable *l)//创建顺序表
    { 
        int i;
        printf("请输入顺序表的内容:\n");
        for(i=0; i<l->length; i++)
        { 
            printf("l.elem[%d]=",i+1);
            scanf("%d",&l->elem[i]);
        }
    }
    void s_search(Stable *l,datatype k)
    { 
        int i=0,flag=0;
        while(i<l->length)
        { 
            if(l->elem[i]==k)
            { 
                printf("查找成功.\n");
                flag=1;
                printf("l.elem[%d]=%d",i+1,k);
            }
            i++;
        }
        if(flag==0)
        { 
            printf("没有找到数据%d！\n",k);
        }
    }
    int main()
    { 
        Stable *l,table;
        datatype key;
        int i;
        l=&table;
        printf("请输入顺序表的长度:");
        scanf("%d",&l->length);
        create(l);
        printf("创建的顺序表内容:\n");
        for(i=0; i<l->length; i++)
        { 
            printf("l.elem[%d]=%d\n",i+1,l->elem[i]);
        }
        printf("输入查找关键字:");
        scanf("%d",&key);
        s_search(l,key);
    }

代码2:

#include<cstdio>
    #include<cstring>
    #include<cstdlib>
    //折半查找
    using namespace std;
    const int MAX=100;
    typedef struct{ 
        int element[MAX+1];
        int length;
    }Stable;
    void create_seq(Stable* l)
    { 
        int i;
        printf("请输入顺序表的内容:\n");
        for(i=0; i<l->length; i++)
        { 
            printf("l.elem[%d]=",i+1);
            scanf("%d",&l->element[i]);
        }
    }
    int sort_seq(Stable* l){ 
        int i,j,flag,t;
        for(i=0;i<l->length-1;i++){ 
            flag=0;
            for(j=0;j<(l->length)-1-i;j++){ 
                if(l->element[j]>l->element[j+1]){ 
                    t=l->element[j+1];
                    l->element[j+1]=l->element[j];
                    l->element[j]=t;
                    flag=1;
                }
            }
            if(flag==0)
            return 1;
        }
    }
    int sea_self(Stable *l,int k,int low,int high){ 
        int mid;
        if(low>high){ 
            printf("没有找到查找的值\n");
            return 0;
        }
        mid=(low+high)/2;
        if(l->element[mid]==k){ 
            printf("查找成功\n");
            printf("l[%d]=%d\n",mid+1,k);
            return mid;
        }
        else{ 
            if(l->element[mid]<k)
                return sea_self(l,k,mid+1,high);
            else
                return sea_self(l,k,low,mid-1);
        }
    }
    int main(){ 
        Stable* l,table;
        int i,key;
        l=&table;
        printf("请输入线性表的长度：");
        scanf("%d",&l->length);
        create_seq(l);
        sort_seq(l);
        printf("排序后的数据\n");
        for(i=0;i<l->length;i++){ 
            printf("l[%d]=%d\n",i+1,l->element[i]);
        }
        printf("\n请输入查找的值：\n");
        scanf("%d",&key);
        sea_self(l,key,0,(l->length)-1);
    }

代码3：

#include<cstdio>
    #include<cstdlib>
    #include<cstring>
    using namespace std;
    typedef struct bitnode{ 
        int key;
        struct bitnode* lchild;
        struct bitnode* rchild;
    }bnode;
    void ins_bit(bnode* p,int k){ 
        bnode *q;
        if(p->key>k&&p->lchild){ 
            ins_bit(p->lchild,k);
        }
        else{ 
            if(p->key<=k&&p->rchild)
                ins_bit(p->rchild,k);
            else{ 
                q=(bnode*)malloc(sizeof(bnode));//申请没有子结点的结点
                q->key=k;
                q->lchild=NULL;
                q->rchild=NULL;
                if(p->key>k)
                    p->lchild=q;
                else
                    p->rchild=q;
            }
        }
    }
    void sea_bit(bnode* p,int k){ 
        if(p->key>k&&p->lchild){ 
            sea_bit(p->lchild,k);
        }
        else{ 
            if(p->key<k&&p->rchild){ 
                sea_bit(p->rchild,k);
            }
            else{ 
                if(p->key==k)
                    printf("查找成功！\n");
                else
                    printf("%d不存在！\n",k);
            }
        }
    }
    void inorder(bnode* p){ //中序
        if(p){ 
            inorder(p->lchild);
            printf("%3d",p->key);
            inorder(p->rchild);
        }
    }
    int main(){ 
        int k;
        bnode *p;
        p=NULL;
        printf("请输入二叉树结点的值，输入0结束：\n");
        scanf("%d",&k);
        p=(bnode*)malloc(sizeof(bnode));
        p->key=k;
        p->lchild=NULL;
        p->rchild=NULL;
        scanf("%d",&k);
        while(k>0){ 
            ins_bit(p,k);
            scanf("%d",&k);
        }
        printf("\n");
        printf("二叉树排序的结果：");
        inorder(p);
        printf("\n请输入查找的值：\n");
        scanf("%d",&k);
        sea_bit(p,k);
    }

代码4：

#include<cstdio>
    #include<cstdlib>
    #include<cstring>
    using namespace std;
    const int maxs=11;
    void ins_hash(int hashs[],int key)
    { 
        int k,k1,k2;//本函数实现将值key存入哈希表相应位置中
        k=key%maxs;
        if(hashs[k]==0)
        { 
            hashs[k]=key;
        }
        else
        { 
            k1=k+1;//线性探测法在k+1到maxs之间的范围
            while(k1<maxs&&hashs[k1]!=0)
            { 
                k1++;
            }
            if(k1<maxs)
            { 
                hashs[k1]=key;
            }
            k2=0;//线性探测法在0到k-1之间的范围
            while(k2<k&&hashs[k2]!=0)
            { 
                k2++;
            }
            if(k2<k)
            { 
                hashs[k2]=key;
            }
        }
    }
    void out_hash(int hashs[])
    { 
        int i;
        for(i=0; i<maxs; i++)
        { 
            if(hashs[i])
            { 
                printf("hashs[%d]=%d\n",i,hashs[i]);
            }
        }
    }
    void sea_hash(int hashs[],int key)
    { 
        int k,k1,k2,flag=0;
        k=key%maxs;
        if(hashs[k]==key)
        { 
            printf("hashs[%d]=%d\n",k,key);
            flag=1;
        }
        else
        { 
            k1=k+1;//线性探测法在k+1到maxs之间的范围
            while(k1<maxs&&hashs[k1]!=key)
            { 
                k1++;
            }
            if(k1<maxs)
            { 
                printf("hashs[%d]=%d\n",k1,key);
                flag=1;
            }
            k2=0;//线性探测法在0到k-1之间的范围
            if(!flag)//如果在前面的范围没有找到
            { 
                while(k2<k&&hashs[k2]!=key)
                { 
                    k2++;
                }
                if(k2<k)
                { 
                    printf("hashs[%d]=%d\n",k2,key);
                    flag=1;
                }
            }
        }
        if(flag)
        { 
            printf("查找成功！\n");
        }
        else
        { 
            printf("查找失败！\n");
        }
    }
    int main()
    { 
        int i,key,k,sum=0;
        int hashs[maxs];
        for(i=0; i<maxs; i++)
        { 
            hashs[i]=0;
        }
        printf("请输入数据，以0结束:\n");
        scanf("%d",&key);
        sum++;
        while(key&&sum<maxs)
        { 
            ins_hash(hashs,key);
            scanf("%d",&key);
            sum++;
        }
        printf("\n");
        out_hash(hashs);
        printf("\n");
        printf("请输入查找的值:");
        scanf("%d",&k);
        sea_hash(hashs,k);
        printf("\n");
    }