【算法】实验 1 查找

news/2024/11/28 1:30:05/

目录

【实验目的】

【实验预习】

【实验内容】

1. 编写程序，实现顺序查找和折半查找

2. 编写程序，实现哈希表的构造和查找及哈希冲突的检测方法

 

【实验目的】

1. 掌握查找表、动态查找表、静态查找表和平均查找长度的概念

2. 掌握线性表中顺序表查找和折半查找的方法

3. 学会哈希函数的构造方法，处理冲突的机制及哈希表的查找

4. 掌握二叉排序树的构造方法和查找过程

【实验预习】

1. 顺序查找。顺序查找的平均查找长度和查找不成功时的比较次数

2. 折半查找。折半查找的平均查找长度

3. 二叉排序树和平衡二叉树

4. 哈希表和哈希查找

5. 处理冲突的方法

【实验内容】

1. 编写程序，实现顺序查找和折半查找

（1）回答下面问题并与运行结果进行比较：

测试数据：{49,38,65,97,76,13,27,52,89}

① 顺序查找

查找key=76，查找成功比较次数 

查找key=25，查找不成功比较次数

② 折半查找

查找key=76，查找成功比较次数

查找key=25，查找不成功比较次数

（2）参考程序如下，请补充完整

#include<stdio.h>
#define MAX 100
#define KeyType int 
typedef struct{
    KeyType key;
}table;
int inputSeqData(table R[]);
int SeqSearch(table R[],int n,KeyType k);
int inputBinData(table R[]);
int BinSearch(table R[],int n,KeyType k);
int main(){
    table R[MAX];
    int select,n,i;
    KeyType k;
    do{
        printf("\n*********MENU**********\n");
        printf("1.输入顺序查找表\n");
        printf("2.顺序查找\n");
        printf("3.输入折半查找表\n");
        printf("4.折半查找\n");
        printf("0.EXIT");
        printf("\n*********MENU**********\n");
        printf("\ninput choice:");
        scanf("%d",&select);
        getchar();
        switch(select){
            case 1:
                printf("\n1-输入顺序查找表\n");
                n=inputSeqData(R);
                printf("\n顺序查找表元素：");
                for(i=1;i<n;i++){
                    printf("%d ",R[i].key);
                } 
                printf("\n");
                getchar();
                break;
            case 2:
                printf("\n2-顺序查找\n");
                printf("\n输入查找关键字：");
                scanf("%d",&k);
                i=SeqSearch(R,n,k);
                if(i==0){
                    printf("\n未找到key=%d\n",k);
                }else{
                    printf("\n查找成功！k=%d位置序号：%d\n",k,i);
                }
                getchar();
                break;
            case 3:
                printf("\n3-输入折半查找表\n");
                n=inputBinData(R);
                printf("\n折半查找表元素：");
                for(i=0;i<n;i++){
                    printf("%d ",R[i].key);
                }
                printf("\n");
                getchar();
                break;
            case 4:
                printf("\n4-折半查找\n");
                printf("\n输入查找关键字：");
                scanf("%d",&k);
                i=BinSearch(R,n,k);
                if(i==0){
                    printf("\n未找到key=%d\n",k);
                }else{
                    printf("\n查找成功！k=%d位置序号：%d\n",k,i+1);
                }
                getchar();
                break;
            case 0:
                break;
            default:
                break;
        }
    }while(select);
    return 0;
}
int inputSeqData(table R[]){
    int i;
    KeyType a;
    printf("\n输入顺序查找表元素（以非数值为输入结束）：");
    i=1;
    while(scanf("%d",&a)==1){
        R[i].key=a;
        i++;
    } 
    return i;
}
int SeqSearch(table R[],int n,KeyType k)
{
    int i=n;
    R[0].key=k;
    while(R[i].key!=k){
        i--;
    }    
    return i;
}
int inputBinData(table R[]){
    int i,j,t;
    KeyType a;
    printf("\n输入折半查找表元素（以非数值为输入结束）：");
    t=0;
    while(scanf("%d",&a)==1){
        for(i=0;i<t;i++){
            if(a<R[i].key){
                break;
            }
        }
        for(j=t;j>=i;j--){
            R[j+1].key=R[j].key;
        }
        R[i].key=a;
        t++;
    }
    return t;
}
int BinSearch(table R[],int n,KeyType k){
    int low,mid,high;
    low=1;
    high=n;
    while(low<high){
        mid=(low+high)/2;
        if(k==R[mid].key){
            return mid;
        }
        if(k<R[mid].key){
            high=mid-1;
        }else{
            low=mid+1;
        }
    }
    return 0;
}

2. 编写程序，实现哈希表的构造和查找及哈希冲突的检测方法

（1）回答下面问题，并域运行结果比较：

设关键字序列为{16 74 60 43 54 90 46 31 29 88 77 e}

①采用线性探测法，写出构造的哈希表

②采用二次探测法，写出构造的哈希表

③线性探测法哈希查找key值为74，查找成功探查        次

    线性探测法哈希查找key值为100，查找不成功探查        次

④二次探测法哈希查找key值为29，查找成功探查        次

    二次探测法哈希查找key值为2，查找不成功探查        次

（2）参考程序如下，请补充完整

#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 15
#define MAX 15
#define NULLKEY 0
#define KeyType int
#define P 13
#define OK 1
#define ERROR 0
typedef struct{
    KeyType key;
}HashNode;
typedef struct{
    HashNode data[MAXSIZE];
    int count;
    int sizeindex;
}HashTable;
int d1[MAX]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};
int d2[MAX]={0,1,-1,2*2,-2*2,3*3,-3*3,4*4,-4*4,5*5,-5*5,6*6,-6*6,7*7,-7*7};
int InsertHash(HashTable *H,int e,int d[]);
int CreateHash(HashTable *H,int d[]);
int SearchHash(HashTable *H,int e,int d[]);
void InitHash(HashTable *H);
void InitHash(HashTable *H){
    int i;
    for(i=0;i<MAXSIZE;i++){
        H->data[i].key=NULLKEY;
    }
    H->count=0;
    H->sizeindex=MAXSIZE;
}
int InsertHash(HashTable *H,int e,int d[]){
    int k,i=1;
    k=e%P;
    while(H->data[k].key!=NULLKEY){
        k=(e%P+d[i]+MAXSIZE)%MAXSIZE;
        i++;
        if(i>MAX) return ERROR;
    }
    H->data[k].key=e;
    H->count++;
    return OK;
}
int SearchHash(HashTable *H,int e,int d[]){
    int k,i=1;
    k=e%P;
    while(H->data[k].key!=NULLKEY&&H->data[k].key!=e){
        k=(e%P+d[i]+MAXSIZE)%MAXSIZE;
        i++;
        if(i>MAX) break;
    }
    if(H->data[k].key==e) return k;
    else return -1;
}
int CreateHash(HashTable *H,int d[]){
    KeyType a;
    printf("\n输入数据元素（以非数值为输入结束）：");
    while(scanf("%d",&a)==1){
        if(SearchHash(H,a,d)!=-1)
            continue;
        InsertHash(H,a,d);
        if(H->count>=MAXSIZE)
            return ERROR;
    }
    return OK;
}
int main(){
    HashTable h;
    KeyType e;
    int i,select,*q;
    do{
        printf("\n*************MENU*************\n");
        printf("1.线性探测构造哈希表\n");
        printf("2.二次探测构造哈希表\n");
        printf("3.线性探测哈希查找\n");
        printf("4.二次探测哈希查找\n");
        printf("0.EXIT");
        printf("\n*************MENU*************\n");
        printf("\ninput choice:");
        scanf("%d",&select);
        getchar();
        switch(select){
            case 1:
            case 2:
                if(select==1){
                    printf("\n1-线性探测构造哈希表\n");
                    q=d1;
                }else{
                    printf("\n2-二次探测构造哈希表\n");
                    q=d2;
                }
                InitHash(&h);
                if(!(i=CreateHash(&h,q)))
                    printf("\n哈希表构造失败！\n");
                else{
                    printf("\n哈希表：\n");
                    for(i=0;i<h.sizeindex;i++){
                        printf("%d ",h.data[i].key);
                    }
                }
                printf("\n");
                getchar();
                break;
            case 3:
            case 4:
                if(select==3){
                    printf("\n3-线性探测哈希查找\n");
                    q=d1;
                }else{
                    printf("\n4-二次探测哈希查找\n");
                    q=d2;
                }
                printf("\n输入查找关键字：");
                scanf("%d",&e);
                if((i=SearchHash(&h,e,q))==-1)
                    printf("\n%d未找到\n",e,i);
                else{
                    printf("\n%d在哈希表中下标为%d\n",e,i);
                }
                getchar();
                break;
            case 0:
                break;
            default:
                break;
        }
    }while(select);
    return 0;
}

 


http://www.ppmy.cn/news/3437.html

相关文章

基于opencv传统数字图像处理实现车道线检测详细过程（附源码）

基于opencv传统数字图像处理实现车道线检测详细过程（附源码）

车道线检测 &#xff08;Lane Detection&#xff09; 1、实验内容 本实验使用数字图像处理的基本方法&#xff0c;构建了一个车道线检测模型。该模型可以识别图像中所有的车道线&#xff0c;并得到完整的车道线信息。模型在tuSimple Lane Dataset大小为100的数据子集进行了测…
阅读更多...
外贸：圣诞新年祝福语语

外贸：圣诞新年祝福语语

每到圣诞或者元旦的时候&#xff0c;我都会习惯给过圣诞的客户制作一张卡片&#xff0c;写上祝福的话&#xff0c;然后再在卡片的周围添加上含有我们公司信息和主打产品的图片&#xff0c;这样一来&#xff0c;即祝福了客户&#xff0c;而且还介绍了我们的公司和产品&#xff0…
阅读更多...
【lssvm回归预测】基于遗传算法优化最小二乘支持向量机GA-lssvm实现数据回归预测附matlab代码

【lssvm回归预测】基于遗传算法优化最小二乘支持向量机GA-lssvm实现数据回归预测附matlab代码

✅作者简介&#xff1a;热爱科研的Matlab仿真开发者&#xff0c;修心和技术同步精进&#xff0c;matlab项目合作可私信。 &#x1f34e;个人主页&#xff1a;Matlab科研工作室 &#x1f34a;个人信条&#xff1a;格物致知。 更多Matlab仿真内容点击&#x1f447; 智能优化算法 …
阅读更多...
【PAT甲级 - C++题解】1132 Cut Integer

【PAT甲级 - C++题解】1132 Cut Integer

✍个人博客&#xff1a;https://blog.csdn.net/Newin2020?spm1011.2415.3001.5343 &#x1f4da;专栏地址&#xff1a;PAT题解集合 &#x1f4dd;原题地址&#xff1a;题目详情 - 1132 Cut Integer (pintia.cn) &#x1f511;中文翻译&#xff1a;切整数 &#x1f4e3;专栏定位…
阅读更多...
笔试强训48天——day25

笔试强训48天——day25

文章目录一. 单选1.一进程刚获得三个主存块的使用权&#xff0c;若该进程访问页面的次序是&#xff5b;1321215123&#xff5d;&#xff0c;采用LRU算法时&#xff0c;缺页数2. 以下关于多线程的叙述中错误的是&#xff08;&#xff09;3. 系统死锁的可能的原因是&#xff08;&…
阅读更多...
【JS020】原生JS实现AJAX

【JS020】原生JS实现AJAX

日期&#xff1a;2022年12月14日 作者&#xff1a;Commas 签名&#xff1a;(ง •_•)ง 积跬步以致千里,积小流以成江海…… 注释&#xff1a;如果您觉得有所帮助&#xff0c;帮忙点个赞&#xff0c;也可以关注我&#xff0c;我们一起成长&#xff1b;如果有不对的地方&#x…
阅读更多...
船东提单和货代提单差距这么大？

船东提单和货代提单差距这么大？

【船东提单和货代提单差距这么大&#xff1f;】 船东提单即指船公司签发的海运提单&#xff08;Master B/L&#xff0c;又叫主单&#xff0c;海单&#xff0c;简称M单&#xff09;&#xff0c;可以签发给直接货主&#xff08;此时货代不出提单&#xff09;&#xff0c;也可签发…
阅读更多...
关于迭代器遍历及auto关键词

关于迭代器遍历及auto关键词

在使用vector容器或者字符串时&#xff0c;很经常会用到一些遍历操作&#xff0c;除了使用下标遍历之外&#xff0c;使用迭代器遍历也是超级方便&#xff0c;但是迭代器也有有一些小坑&#xff0c;一不注意就会编译出错&#xff0c;所以特意总结一下。 迭代器 迭代器很很多接口…
阅读更多...
最新文章

Copyright @ 2022~2023