leng_yu的博客

在程序中我们对关键字key应用散列函数H(key)来判断关键字key是否在散列表中，即计算H(key)的值，H(key)值确定所存数据在散列表中的位置。这样一个数据元素的地址是通过函数来计算的，所以数据元素并不需要按照特定的顺序来存放。但是散列函数H(key)将关键字映射为一个整数时，有可能两个关键字的地址相同，所以构造散列函数时要考虑尽量减少冲突的发生。构造散列函数有多种方法，如：平方取中法、除留余数随机数法。本程序采用除留余数法。程序的具体实现如下：本程序是用模板类myhash来实现，包括protected和public属性成员。其中protected成员有*ht（自定义散列表指针）、*empty(bool类型指针，功能是将元素值空、m(散列表容量)、p(除留余数法的除数)以及辅助函数H(key)(散列函数)和collision(处理冲突的函数)；public成员包括构造函数、析构函数和复制构造函数以及=重载函数，其它成员函数主要有：traver(遍历散列表)、show()(打印出哈希表所存的元素)返回值为bool类型的函数search\insert\Delete。search函数（查询关键字为key的元素的位值）、insert函数(插入元素e到哈希表中)、Delete函数（删除关键字为key的元素）。本程序的main函数同样采用两种类型的数据来进行测试，int型和char型，主要测试元素的插入、删除和搜索。

本程序采用模板类实现，利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素，将数据类型为T的数据元素存储在数组中，用count记录存在数组中的元素个数。从具体的实现过程来看，本程序模板类mystack包括protected和public属性成员。Protected成员包括count(所用元素个数)、maxsize（栈所能存最大元素个数）、*p（动态开辟空间的指针）、辅助函数full()（判断栈是否已满）和init()(初始化栈)；public成员包括构造函数、析构函数、复制构造函数和=重载函数以及其它的成员函数，主要有length()(求栈长度)、empty()（判断栈是否为空）、clear()（清空栈）、traver()（遍历栈）、push_stack（入栈函数）、top_stck（返回栈顶元素）、pop_stack（出栈函数）。Main函数主要栈类的后进先出原则，实现n个数的倒序，这里我们采用int和char两种类型来验证。

采用c++源代码，并且包含简单的测试数据，容易研究理解，如果数据按照给出的格式，则可直接用来分类。