数据结构课程设计--哈希表设计问题[精品].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）WINDOWS2000/XP系统 （2）Visual C++ 6.0编译环境或编译环境 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, No