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

《数据结构课程设计--哈希表设计问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录1前言12需求分析12.1任务和要求12.2运行环境12.3开发工具23分析和设计23.1系统分析及设计思路23.2主要数据结构及算法23.3函数流程图34具体代码实现65课程设计总结155.1程序运行结果或预期运行结果155.2设计结论17参考文献17致谢17151前言从C语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子，如Java的语法与C语言基本相同。学习、掌握C语言是每一个计算机技术人员的基本功之一。根据本次课程设计的要求，我设计小组将编写一个C语言程序来处理哈希表问题，通过这个程序，将针对自己的班集体中的“人名”设计一个哈希

2、表，使得平均查找长度不超过R，完成相应的建表和查表程序。2需求分析2.1任务和要求针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。要求：假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法处理冲突。2.2运行环境（1）WINDOWS2000/XP系统（2）VisualC++6.0编译环境或TC编译环境2.3开发工具C语言153分析和设计3.1系统分析及设计思路（1）创建哈希表（2）姓名（结构体数组）初始化（1）用除留余数法构建哈希函数（2）用链表法处理冲突(3)查找哈希

3、表在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度(4)显示哈希表显示哈希表的的格式：3.2主要数据结构及算法定义结构体typedefstructhashtable创建哈希表定义函数Hash_Init(HashTableht)来对哈希表初始化定义函数Hash_Insert(HashTableht,Node*node)来为哈希表分配地址定义函数Hash_Init(ht)输入30个名字定义函数Hash_Create(HashTableht)来求哈希表长度定义函数hash_output(HashTableh)来输出哈希表定义函数Hash_Link()构造链表函数定

4、义函数inthash_search(inth[],intkey)查找输入的名字3.3函数流程图（1）哈希表的创建及初始化流程图15图3.1哈希表的创造及初始化流程图（2）创建哈希表链表的流程图15图3.2创造哈希表链表的流程图15（3）查找输入数据的流程图图3.3查找输入数据的流程图154具体代码实现#include#include#include#include#defineP30/*除数余留法中的除数*/#defineNULLKEY0#defineMAX30/*人名个数*/#definehashlen30/*

5、哈希表长度*/intsum=0,k=0;typedefstructNode/*哈希表结构体*/{charkey_code[10];/*哈希表地址*/structNode*next;}Node;typedefstructhashtable/*创建哈希表*/{intkey;structNode*next;}HashTable[MAX];intHash(intkey){intmode=key%P;/*除留余数法得到的余数*/returnmode;}voidHash_Init(HashTableht)/*哈希表初始化*/{inti;for(i=0;i

6、LKEY;15ht[i].next=NULL;}}intCharToInt(charstr[]){returnstr[0]+str[1]+str[2];}intHash_Insert(HashTableht,Node*node)/*为哈希表分配地址*/{intkey=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++;}elseif(ht[key].key==key){p=ht[

7、key].next;k++;while(p->next!=NULL){p=p->next;k++;}p->next=node;k++;}return1;}15Node*Hash_Search(HashTableht,intkey)/*查找函数*/{intp0=Hash(key);if(ht[p0].key==NULLKEY){sum++;returnNULL;}elseif(ht[p0].key==p0){Node*p=ht[p0]