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

嗨~~欢迎来到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不断前行的源泉✨！衷心感谢你的鼓励与陪伴🙏！
若你有任何疑问、见解或补充，欢迎随时留言💬，让我们在交流中共同成长📚！❤️
愿各位大佬们在技术的道路上，代码顺畅无阻💻，思路清晰如光💡，不断突破自我，向着更高的目标迈进，实现自己的梦想！🎉
再次感谢你的阅读🌸