当前位置：首页 > article >正文

数据结构——实验六·散列表

article 2025/1/23 14:22:34

嗨~~欢迎来到Tubishu的博客🌸如果你也是一名在校大学生，正在寻找各种编程资源，那么你就来对地方啦🌟
Tubishu是一名计算机本科生，会不定期整理和分享学习中的优质资源，希望能为你的编程之路添砖加瓦⭐🔥
当然，如果你也好的资源推荐，欢迎在评论区分享，让我们共同打造一个丰富的编程资源库🔥🔥🔥
本文专栏 ➡️ 数据结构

散列表查找

本实验基于C实现散列表的创建、插入、查找。

实验目的：

掌握散列查找的基本思想
掌握散列表的构造方法
掌握散列表处理冲突的方法

实验内容:

假设有一个1000×1000的稀疏矩阵，其中 0.01%的元素为非零元素，现要求用散列表作存储结构。试设计一个散列表并编写相应算法，对给定的行值和列值确定矩阵元素在散列表上的位置。
在1000×1000的稀疏矩阵中，0.01%的元素为非零元素，即有100个非零元素，故选用散列函数为:H(k)-k%100，其中k是某一矩阵元素的第一下标与第二下标之和。采用拉链法解决碰撞，因此，设计若干条不带头结点的单链表，用于容纳同义词;然后设计一个指针数组，其中的元素分别指向各个单链表。
在设计时，首先建立散列表，散列表的建立可利用随机函数产生数组的行、列下标，再产生一个非零值，插入到散列表中。其次是查表，输入行、列坐标，即可输出该数组元素的值。

实验产出：

1.核心代码：

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

typedef int DataType; // 数组元素的类型

struct ZipNode {      // 结点的结构
    int row, column;  // 数组元素的行、列下标
    DataType value;
    ZipNode *next;
};

ZipNode *Hash[100];   // 散列表结构

// 查找散列表，查找成功，返回该结点的位置，查找失败返回NULL
ZipNode *Find_Hash(int row, int column) {
    int Hash_Value;
    ZipNode *ptr;
    Hash_Value = (row + column) % 100;
    ptr = Hash[Hash_Value];
    while (ptr) {
        if ((ptr->row == row) && (ptr->column == column))
            break; // 查找成功
        ptr = ptr->next;
    }
    return ptr;
}

// 在散列表中插入数组元素
void Insert_Hash(int row, int column, int value) {
    int Hash_Value;
    ZipNode *q;
    Hash_Value = (row + column) % 100;
    q = new(ZipNode);              // 申请一个结点
    q->row = row;
    q->column = column;
    q->value = value;
    q->next = Hash[Hash_Value];    // 按栈方式插入结点
    Hash[Hash_Value] = q;
}

void Create_Hash() {               // 创建散列表
    int i, row, column, value;
    for (i = 0; i < 100; i++) Hash[i] = NULL; // 初始化散列表
    srand((unsigned)time(NULL));              // 设置随机种子
    for (i = 0; i < 100; i++) {               // 产生100个非零元素
        row = rand() % 1000;                  // 产生行下标
        column = rand() % 1000;               // 产生列下标
        if (Find_Hash(row, column))           // 该数组元素已存在
            i--;
        else {
            value = rand() % 10000 + 1;      // 产生一个1-10000之间的随机数
            Insert_Hash(row, column, value); // 插入到散列表中
            printf("No.=%2d, row=%4d, column=%4d, value=%5d\n", i, row, column, value);
        }
    }
}

int main() {
    int row, column;
    ZipNode *ptr;
    Create_Hash(); // 建立散列表
    while (1) {    // 查找数组元素
    	printf("\n\t注意：行列号为（0-999）\n\n");
        printf("请输入行号(10000=结束):");
        scanf("%d", &row);
        if (row == 10000) break;
        printf("请输入列号：");
        scanf("%d", &column);
        if (row >= 1000 || row < 0 || column>=1000 || column < 0) {
        	printf("\t行列号错误！请重新输入！\n");
        	continue;
		}
        printf("row=%4d ", row);
        printf("column=%4d ", column);
        if ((ptr = Find_Hash(row, column))) { // 找到
            printf("value=%5d\n", ptr->value);
        } else {                              // 没找到
            printf("value=%5d\n", 0);
        }
    }
    return 0;
}

2.运行结果：
生成的散列表：
在这里插入图片描述
输入非零元素的行列号：

输出：

3.调试：
输入行列号错误调试：
输入不存在的行列号，验证程序是否能够正确检测到信息错误并输出相应的提示信息。
预期结果：程序应提示“行列号错误！请重新输入！”，并重新输入行列号。
在这里插入图片描述

如果你觉得这篇文章对你有所启发，请为博客点赞👍、收藏⭐️、评论💬或分享🔗，你的支持是Tubishu不断前行的源泉✨！衷心感谢你的鼓励与陪伴🙏！
若你有任何疑问、见解或补充，欢迎随时留言💬，让我们在交流中共同成长📚！❤️
愿各位大佬们在技术的道路上，代码顺畅无阻💻，思路清晰如光💡，不断突破自我，向着更高的目标迈进，实现自己的梦想！🎉
再次感谢你的阅读🌸

查看全文

http://www.kler.cn/a/514998.html