1、目 录 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 1 前言前言 从 C 语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行 编程语言中，都能看到 C 语言的影子，如 Java 的语法与 C 语言基本相同。学习、掌 握 C 语言是每一个计算机技术人员的
2、基本功之一。 根据本次课程设计的要求，我设计小组将编写一个 C 语言程序来处理哈希表问 题，通过这个程序，将针对自己的班集体中的“人名”设计一个哈希表，使得平均查 找长度不超过 R，完成相应的建表和查表程序。 2 需求分析需求分析 2.1 任务和要求 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过 R， 完成相应的建表和查表程序。 要求：假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有 30 个， 取平均查找长度的上限为 2。哈希函数用除留余数法构造，用链表法处理冲突。 2.2 运行环境 （1）WINDOWS2000/XP 系统 （2）Visual C+ 6.0 编
3、译环境或 TC 编译环境 2.3 开发工具 C 语言 2 3 分析和设计分析和设计 3.1 系统分析及设计思路 （1）创建哈希表 （2）姓名（结构体数组）初始化 （1） 用除留余数法构建哈希函数 （2） 用链表法处理冲突 (3)查找哈希表 在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的 平均查找长度 (4) 显示哈希表 显示哈希表的的格式： 3.2 主要数据结构及算法 定义结构体 typedef struct hashtable 创建哈希表 定义函数 Hash_Init(HashTable ht)来对哈希表初始化 定义函数 Hash_Insert(HashTable ht,
4、 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 图 3.1 哈希表的创造及初始化流程图 （2）创建哈希表链表的流程图 int mode=key%p; 开始 i=0 returnmode; hti.key=NULLKEY int i; inext!= NULL) p = p-next; k+; p-next = node; k+; return 1; 8 Node* Hash_Search(HashTable ht, int key) /*查找函数*/ int p0 = Hash(key); if(htp0.key = NULLK
