实验（训）项目名称

查找算法的实现

实验（训）地点

明远楼C110计算机网络与信息安全实验室

实验（训）日期

6.16

小组成员

小组成员

分工情况

个人

实验（训）所用设备、材料、软件等：

Win10操作系统计算机

VC++ 2010学习版软件

实验（训）目的：

掌握线性表和哈希表查找的思想和实现过程；理解线性表和哈希表查找方法的特点，并能加以灵活应用；掌握查找线性表和哈希表的时间复杂度分析方法。

实验（训）内容、步骤、结果、心得体会：

一、实验内容

1.线性表的查找

（1）输入一个整数，利用顺序查找法在查找表中查找该整数是否存在。若查找成功，返回该整数在表中的位置；查找失败则返回0。

（2）输入一个整数，利用折半查找法在有序表中查找该整数是否存在。若查找成功，返回该整数在表中的位置；查找失败则返回0。

2.哈希表的查找

（1）设计哈希函数及处理冲突的方法；

（2）键盘输入数据，利用设计的哈希函数及线性探测法生成哈希表；

二、实验步骤

1.代码：

#include <stdio.h>

#include <stdlib.h>

#define MAXSIZE 100

/* 顺序查找 */

int seq_search(int a[], int n, int key)

{

    for (int i = 0; i < n; i++)

        if (a[i] == key)

            return i + 1;

    return 0;

}

/* 折半查找 */

int bin_search(int a[], int n, int key)

{

    int low = 0, high = n - 1, mid;

    while (low <= high) {

        mid = (low + high) / 2;

        if (key == a[mid])

            return mid + 1;

        else if (key < a[mid])

            high = mid - 1;

        else

            low = mid + 1;

    }

    return 0;

}

int main()

{

    int a[MAXSIZE], b[MAXSIZE];

    int n, key, pos;

    printf("【顺序查找】\n");

    printf("请输入元素个数：");

    scanf("%d", &n);

    printf("请输入 %d 个整数：", n);

    for (int i = 0; i < n; i++)

        scanf("%d", &a[i]);

    printf("请输入要查找的整数：");

    scanf("%d", &key);

    pos = seq_search(a, n, key);

    if (pos)

        printf("查找成功，位置：%d\n\n", pos);

    else

        printf("查找失败，返回0\n\n");

    printf("【折半查找】\n");

    printf("请输入有序表中元素个数：");

    scanf("%d", &n);

    printf("请输入 %d 个有序整数：", n);

    for (int i = 0; i < n; i++)

        scanf("%d", &b[i]);

    printf("请输入要查找的整数：");

    scanf("%d", &key);

    pos = bin_search(b, n, key);

    if (pos)

        printf("查找成功，位置：%d\n", pos);

    else

        printf("查找失败，返回0\n");

    return 0;

}

2.结果：

2.代码：

#include <stdio.h>

#include <stdlib.h>

#define M 13       /* 哈希表长 */

#define NULLKEY -999

/* 哈希函数：除留余数法 */

int h(int key)

{

    return key % M;

}

/* 插入（线性探测法） */

int insert(int t[], int key)

{

    int addr = h(key);

    for (int i = 0; i < M; i++) {

        int d = (addr + i) % M;

        if (t[d] == NULLKEY) {

            t[d] = key;

            return d;

        }

    }

    return -1;

}

/* 查找 */

int search(int t[], int key)

{

    int addr = h(key);

    for (int i = 0; i < M; i++) {

        int d = (addr + i) % M;

        if (t[d] == NULLKEY)

            return -1;

        if (t[d] == key)

            return d;

    }

    return -1;

}

/* 打印哈希表 */

void print(int t[])

{

    printf("\n哈希表：\n");

    for (int i = 0; i < M; i++) {

        if (t[i] == NULLKEY)

            printf("%2d: Ø\n", i);

        else

            printf("%2d: %d\n", i, t[i]);

    }

}

int main()

{

    int t[M];

    int n, key, pos, choice;

    /* 初始化 */

    for (int i = 0; i < M; i++)

        t[i] = NULLKEY;

    printf("哈希函数：H(key) = key %% %d\n", M);

    printf("冲突处理：线性探测法\n\n");

    printf("请输入元素个数：");

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {

        printf("第 %d 个关键字：", i + 1);

        scanf("%d", &key);

        insert(t, key);

    }

    print(t);

    while (1) {

        printf("\n1.查找  0.退出  请选择：");

        scanf("%d", &choice);

        if (choice == 0) break;

        printf("输入要查找的整数：");

        scanf("%d", &key);

        pos = search(t, key);

        if (pos >= 0)

            printf("查找成功，下标：%d\n", pos);

        else

            printf("查找失败\n");

    }

    return 0;

}

结果：

心得体会：

通过本次实验，我深入理解了顺序查找、折半查找和哈希表查找的基本原理与实现方法。顺序查找算法简单直观，适用于无序表，但时间复杂度为O(n)，效率较低；折半查找要求数据必须有序，时间复杂度为O(log n)，查找效率显著提高，让我体会到算法设计中对数据预处理的重要性。哈希表查找通过哈希函数直接定位，理想情况下时间复杂度可达O(1)，但冲突处理是关键问题，线性探测法实现简单却容易产生聚集现象。实验中我掌握了不同查找方法的适用场景，认识到在实际应用中需根据数据特点和需求选择合适的查找策略，这对今后编写高效程序具有重要指导意义。

教师评语：

成绩评定

教师签名