数据结构课程设计哈希表设计问题.doc

目 录

1 前言 1
2 需求分析 1
2.1 任务和规定 1
2.2 运营环境 1
2.3 开发工具 2
3 分析和设计 2
3.1 系统分析及设计思绪 2
3.2 重要数据结构及算法 2
3.3 函数流程图 3
4 具体代码实现 6
5 课程设计总结 15
5.1 程序运营结果或预期运营结果 15
5.2 设计结论 17
参考文献 17
致 谢 17

1 前言
从C语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子，如Java的语法与C语言基本相同。学习、掌握C语言是每一个计算机技术人员的基本功之一。
根据本次课程设计的规定，我设计小组将编写一个C语言程序来解决哈希表问题，通过这个程序，将针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完毕相应的建表和查表程序。

2 需求分析
2.1 任务和规定
针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完毕相应的建表和查表程序。
规定：假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法解决冲突。

2.2 运营环境
（1）WINDOWS2023/XP系统
（2）Visual C++ 6.0编译环境或TC编译环境

2.3 开发工具
C语言

3 分析和设计
3.1 系统分析及设计思绪
（1）创建哈希表
（2）姓名（结构体数组）初始化
（1） 用除留余数法构建哈希函数
（2） 用链表法解决冲突
(3)查找哈希表
在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度
(4) 显示哈希表
显示哈希表的的格式：

3.2 重要数据结构及算法
定义结构体typedef struct hashtable创建哈希表
定义函数Hash_Init(HashTable ht)来对哈希表初始化
定义函数Hash_Insert(HashTable ht, Node *node)来为哈希表分派地址
定义函数Hash_Init(ht)输入30个名字
定义函数Hash_Create(HashTable ht)来求哈希表长度
定义函数hash_output(HashTable h)来输出哈希表
定义函数Hash_Link()构造链表函数
定义函数int hash_search(int h[],int key)查找输入的名字
3.3 函数流程图
（1）哈希表的创建及初始化流程图

图3.1 哈希表的发明及初始化流程图

（2）创建哈希表链表的流程图

图3.2 发明哈希表链表的流程图

（3）查找输入数据的流程图

图3.3 查找输入数据的流程图
4 具体代码实现
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define P 30 /*除数余留法中的除数*/
#define NULLKEY 0
#define MAX 30 /*人名个数*/
#define hashlen 30 /*哈希表长度*/
int sum=0,k=0;
typedef struct Node /*哈希表结构体*/
{
char key_code[10]; /*哈希表地址*/
struct Node *next;
}Node;
typedef struct hashtable /*创建哈希表*/
{
int key;
struct Node *next;
}HashTable[MAX];
int Hash(int key)
{
int mode = key % P; /*除留余数法得到的余数*/
return mode;
}
void Hash_Init(HashTable ht) /*哈希表初始化*/
{
int i;
for(i = 0; i < MAX; i++)
{
ht[i].key = NULLKEY;
ht[i].next = NULL;
}
}
int CharToInt(char str[]){
return str[0]+str[1]+str[2];
}
int Hash_Insert(HashTable ht, Node *node) /*为哈希表分派地址*/
{
int key = Hash(CharToInt(node->key_code));
Node *p;
p=(Node*)malloc(sizeof(Node));
if(ht[key].key == NULLKEY)
{
ht[key].key = key;
ht[key].next = node;
k++;
}
else if(ht[key].key == key)
{
p = ht[key].next;
k++;
while(p->next!= NULL)
{
p = p->next;
k++;
}
p->next = node;
k++;
}
return 1;
}
Node* Hash_Search(HashTable ht, int key) /*查找函数*/
{
int p0 = Hash(key);

if(ht[p0].key == NULLKEY)
{sum++;return NULL;}
else if(ht[p0].key == p0)
{
Node *p = ht[p0].next;
while(p != NULL)
{
if(CharToInt(p->key_code) == key)
{ sum++;
return p;
}
p = p->next;
sum++;
}
}
return NULL;
}
int Hash_Create(HashTable ht) /*哈希表长度*/
{
int i;
Node *node;
Hash_Init(ht);
printf("请输入姓名："); /*输入30个姓名*/
for(i=0;i<30;i++)
{
node = (Node *)malloc(sizeof(Node));
scanf("%s",node->key_code);
node->next = NULL;
Hash_Insert(ht, node);
}
printf("\nCreate Successfully!\n");
return 1;
}
int hash_output(HashTable h) /*哈希表的输出部分*/
{
Node *a;
int i,j,count2=0;
a=(Node*)malloc(sizeof(Node));
j=0;
for(i=0;i<hashlen;i++)
{
printf("%4d",i);
printf("%4d",h[i].key);
if(h[i].next!=0)
count2++;
j=1;
a=h[i].next;
while(a)
{
printf("->%s",(*a).key_code);
a=(*a).next;
j++;
count2+=j;
}
printf("\n");
}
return count2;
}
void Hash_Link() /*链表法构造函数*/
{
int key;
int i;
Node *node;
HashTable ht;
Hash_Create(ht);
hash_output( ht);
printf("count=%d\n",k); /*查找总长度*/
printf("ASL=%d/8\n",k); /*平均查找长度*/
printf("请输入要查找的数据："); /*输入查找的姓名*/
scanf("%s",&key);
node = Hash_Search(ht, key);
printf("查找次数:%d\n",sum);
if(node != NULL)
printf("查找成功！");
else
printf("查找不成功！");
}
void hash_create(int h[],int status[],int data)
{
int address;
int di;
address=data%P;
if(status[address]==0)
{
h[address]=data;
status[address]=1;
}
else
{
for(di=1;di<=hashlen-1;di++)
{
address=((data%P)+di)%hashlen;
if(status[address]==0)
{
h[address]=data;
status[address]=1;
break;
}
}
}
return ;
}
int hash_search(int h[],int key)
{ int address, di;
address=key % P;
if(h[address]==key) /*哈希表中元素与查找元素是否相等*/

return 1;

else
{
for(di=1;di<=hashlen-1;di++)/*哈希表中元素与查找元素不相等，查找下一元素*/
{
address=((key%P)+di)%hashlen;
if(h[address]==key)
{
return di+1;
break;
}
}
}
if(di>=hashlen)
return 0;
}
int main() /*主函数*/
{
printf("\t\t\t************************\n");
printf("\t\t\t 哈希表设计\n");
printf("\n");
printf("\t\t\t************************\n");
printf("\n");

Hash_Link();
}

5 课程设计总结
5.1 程序运营结果或预期运营结果

图5.1程序运营结果1

图5.2程序运营结果2
说明：输入的数为30个姓的拼音，查找的为“pan”，输出的如上图所示。

5.2 设计结论
通过这次课程设计，我了解到了许多自身的局限性，有很多学习过的知识，在学过之后并没有反复的操作和复习，认为课堂上听懂就行了，在这课程设计中，这些局限性就显现了出来，导致经常要翻书，查找一些认为弄懂的问题，这次我了解到了，学习不仅仅是课堂上听讲，还要课后复习和操作。
课程设计是对我们这学期的学习成果的试金石，对我们来说是一个不小的考验，它是我们专业课程知识综合应用的实践训练。“自己动手，丰衣足食”，通过这次课程设计，我深深体会到这句千古名言的真正含义，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才干真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。
实验过程中，也对团队精神的进行了考察，让我们在合作起来更加默契，在成功后一起体会喜悦的心情。果然是团结就是力量，只有互相之间默契融洽的配合才干换来最终完美的结果。
参考文献
[1]张福祥. C语言程序设计[M]. 辽宁大学出版社，2023.1
[2] 张福祥，王萌．C语言程序设计习题解答与实验实训[M]．沈阳：辽宁大学出版社，2023．
[3] 牛莉，刘远军等．计算机等级考试辅导教程[M]．北京：中国铁道出版社，2023．
致 谢
本次课程设计在选题及进行过程中得到陈智老师的悉心指导，陈老师严谨求实的治学态度，热情洋溢的工作激情，将使我终生受益，在老师的影响下我学到了很多在书本上学不到的东西，我非常感谢她。谨再一次向陈老师致以真挚的谢意和崇高的敬意。此外我还要感谢组内的成员们，由于他们也帮我解决了不少难题，正是在大家的共同努力下，本次课程设计将随着论文的完毕划上圆满的句号!