c++基于链地址法的哈希表类模板设计与实现.docx

学院专业学生姓名学号设计题目基于链地址法的哈希表类模板设计与实现内容及要求：实现哈希表类模板，数据元素可以是char, int, float等多种数据类型，包括以下功能：（1）实现哈希表的建立，散列函数采用除留余数法；（2）使用链地址法处理冲突；（3）实现哈希表元素的插入；（4）实现哈希表元素的删除；（5）实现哈希表的查找；（6）将上述功能作为类的成员函数实现，编写主函数测试上述查找功能。进度安排：第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；第18周：程序的设计、调试与实现；第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师（签字）：年 月 日学院院长（签字）年 月 日课 程 设 计 任 务 书目 录1 需求分析32 算法基本原理33 类设计44 详细设计64.1 类的接口设计64.2 类的实现74.3 主函数设计105 DOS界面程序运行结果及分析115.1 程序运行结果115.2运行结果分析136 基于MFC的图形界面程序开发136.1 基于MFC的图形界面程序设计136.2 程序测试256.3 MFC程序编写总结287 参考文献291 需求分析（1）对于保存在顺序容器的无序列表来说，顺序查找的时间效率为O(n),对于有序列表，二分查找可以提供O（log2n）的查找时间。最理想的情况是，我们可以设计一个容器，它访问数据的时间复杂度为O（1）。如果这样，访问某数据的时间就和容器中其他数据没有关系了。此时，这样的结构我们称为哈希表，其中，表中的元素都有唯一的键与之对应。（2）哈虚函数根据键求出索引值，并利用索引值来定位表中的某项数据： 键-值 0定位器“哈希函数” 1 键 2 i in-2n-12 算法基本原理（1） 除留余数法原理取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即H（key）=keyMODp, p=m 如：关键字分别为：13 29 35 64 77 87 96 105当p=7,m=8时，根据哈希函数H（key）=keyMODp得H（key）=keyMOD7，计算结果如下表：关键字 13 29 35 64 77 87 96 105哈希地址 6 1 0 1 0 3 5 0（2） 链地址法处理冲突原理将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间（0，m-1）上，则设立一个指针型变量Hm，其每个分量的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针Hi的链表中。在链表中的插入位置可以在表头也可以在表尾，也可以在中间，以保持同义词在同一线性链表中按关键字有序。如以（1）中的关键字为例，则链地址法处理冲突可形象地表示如下：105 7735064 29 12 87 34 96 513 63 类设计类模板就是设计一种类的框架，可以适用不同的数据类型，只是一种类的抽象，因此，利用类模板可以针对不同的数据类型定义出具有共性的一组类。定义形式如下：template class 类名类声明体；与函数模板类似，通过使用类模板可以使得所定义的类中的某些数据成员某些成员函数的参数某些成员函数的返回值都可以是任意的数据类型（包括基本类型和自定义类型）。所以，可以通过类模板将程序所处理的对象的类型参数化，从而使得同一段程序可用于处理多种不同类型的对象，提高了程序的抽象层次和可重用性。由于哈希表中的数据元素可以是char, int, float等多种数据类型，因此可以使用类模板来构造本程序的实现框架。具体定义如下：template class hash public: typedef node* linknode; typedef node ln; hash(); hash(); void insert(t1 key,t2 data); void remove(t1 key); t2 query(t1 key); void display(); linknode *array; private: int func(char *); int func(string); int func(int); int func(char); int func(float); string type; ; 同时，程序中也定义了结构体的模板，具体如下：template struct node t1 key; t2 data; node *next; ; 该类模板经过实例化后得到的模板类的UML图表示如下： hash - type: string- array: linknode*- linknode: node *- ln: node+hash()+hash()+func(string): int+func(int): int +func(char): int +func(float): int +func(char *): int+query(t1 key ): t2 +display(): void +insert(t1 key,t2 data): void+remove(t1 key): void类hash用UML图的完整表示4 详细设计整个类分别使用了insert(t1 key,t2 data) 实现哈希表元素的插入，remove(t1 key)实现哈希表元素的删除，query(t1 key) 实现哈希表元素的查找，display()实现哈希表元素的显示。具体设计如下：4.1 类的接口设计#include #include using namespace std; template /结构体模板的声明struct node t1 key; t2 data; node *next; ; template /类模板的声明class hash public: typedef node* linknode; /定义指向结点的指针 typedef node ln; hash(); /构造函数 hash(); /析构函数 void insert(t1 key,t2 data); /实现哈希表元素的插入void remove(t1 key); /实现哈希表元素的删除 t2 query(t1 key); / 实现哈希表元素的查找void display();/实现哈希表元素的显示 linknode *array; private: / 哈希函数重载 int func(char *); int func(string); int func(int); int func(char); int func(float); string type; /判断参数类型 ; 4.2 类的实现template /构造函数的实现hash:hash() array=new linknode7; for(int i=0;i7;i+) arrayi=NULL; template /析构函数的实现hash:hash() for(int i=0;inext; delete n1; template /插入元素的函数实现 void hash:insert(t1 key,t2 data) int sum=func(key)%7; if(arraysum!=NULL) ln *n=new ln; n-key=key; n-data=data; n-next=NULL; linknode p=arraysum; while(p-next!=NULL) p=p-next; p-next=n; else ln *n=new ln; n-key=key; n-data=data; n-next=NULL; arraysum=n; template /查询元素的函数实现t2 hash:query(t1 key) int sum=func(key)%7;linknode p=arraysum; while(p) if(type=char*) if(stricmp(char*)(int)p-key,(char*)(int)key)=0) cout关键字key的data值为:data; else p=p-next; else if(type=void*) if(int)p-key=(int)key) cout关键字key的data值为:data; else p=p-next; else if(p-key=key) cout关键字key的data值为:data; else p=p-next; return 您所查询的关键字在该哈希表中不存在！; template void hash:display()/显示哈希表元素的函数实现 for(int i=0;i7;i+) if(arrayi!=NULL) ln *n=arrayi; while(n!=NULL) coutarrayi为keynext; else coutarrayi为空！endl; template /整型关键字哈希函数实现int hash:func(int i) type=int; return i; template /浮点型关键字哈希函数实现 int hash:func(float i) type=float; int s=i*100; return s; template /指向字符型指针关键字哈希函数实现int hash:func(char *i) type=char*; int s=strlen(i)*i0; return s; template /字符型关键字哈希函数实现int hash:func(char i) type=char; int s=(int)i; return s; template /字符串型关键字哈希函数实现int hash:func(string i) type=string; int s=i.length()*(int)i0; return s; template void hash:remove(t1 key)/删除元素的哈希函数实现 int sum=func(key)%7; linknode p=arraysum; if(p!=NULL) if(p-next!=NULL) if(p-key=key) arraysum=p-next;delete p;cout关键字key已被删除！next!=NULL&p-next-key!=key) p=p-next; linknode p2=p-next; p-next=p2-next; delete p2; cout关键字key已被删除！endl; else arraysum=NULL;delete p;cout关键字key已被删除！endl; else cout对不起！您删除的关键字key在本哈希表中不存在！endl; 4.3 主函数设计 int main() hash h;/实例化类模板，其中t1,t2分别为char *,char *型,并定义hash类对象hchar a10,b10,c10,d10;/定义字符数组以接收用户输入的信息int k;h.insert(sds,etew);/初始化哈希表h.insert(45,45);/初始化哈希表h.insert(4.5765k,2);/初始化哈希表h.insert($345,6);/初始化哈希表h.insert(43.r,55);/初始化哈希表h.insert(sx,24);/初始化哈希表cout显示初始化表如下:endl;h.display();/h对象调用display（）函数wang:/goto语句识别标志coutendl*菜单*endl1.插入 2.查询 3.删除 4.退出 k;/接收菜单选项switch (k)/switchcase结构 case 1: cout请分别输入key和data:ab; h.insert(a,b);/ h对象调用insert（）函数 h.display();/h对象调用display（）函数 goto wang;/goto语句 break; case 2: cout请输入要查询的关键字:c; couth.query(c); /h对象调用query（）函数 goto wang; /goto语句 break; case 3: cout请输入要删除的关键字:d; h.remove(d);/ h对象调用remove()函数 h.display();/h对象调用display（）函数 goto wang; /goto语句 break; case 4: cout程序运行已结束！endl;exit(1); return 0; 5 DOS界面程序运行结果及分析5.1 程序运行结果 DOS界面程序运行结果（上） DOS界面程序运行结果（下）5.2运行结果分析从上述运行结果可知，本程序已经顺利地完成了哈希表元素的初始化、插入、查找、删除，其中使用了菜单选项很方便地实现了用户的数据输入。虽然goto语句容易造成程序运行混乱，但在不是很复杂的程序中使用它同样会很方便，例如本程序中利用goto语句很方便地使运行界面返回到菜单界面，供用户选择执行项目。6 基于MFC的图形界面程序开发MFC的图形界面程序设计可在上述类设计的基础上进行改造，MFC的图形界面程序与DOS界面程序的主要不同点是：MFC图形界面程序与DOS界面程序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，主要通过cin，cout等I/O流实现，而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出，因此必须在MFC类的框架下加入上面所设计的哈希表类并通过图形界面的输入输出改造来完成。6.1 基于MFC的图形界面程序设计（1）界面设计首先在VC中建立MFC AppWizard(exe)工程，名称为WANG，并在向导的Step1中选择Dialog based，即建立基于对话框的应用程序，如下图的6-1图6-1建立MFC AppWizard(exe)工程 然后点击确定，会自动弹出如图6-2的窗口图6-2建立基于对话框的应用程序在如图6-2的窗口中，选择基本对话框（D），然后点击完成即可，系统将自动弹出如图6-3的窗口。然后，将对话框资源中的默认对话框利用工具箱改造成如下界面，如图6-3所示。图6-3实现哈希表元素各种操作界面图图6-3所示的界面中包含了3个Static Text控件，4个Button控件，和3个Edit Box控件，控件的基本信息列表如下表6-4所示：控件类别控件ID控件Caption说明Static TextIDC_STATIC哈希表说明下方的编辑框key接收关键字data接收内容值BottonIDC_Insert插入插入元素IDC_Query查询查询元素IDC_Remove IDCANCLE删除取消删除元素退出程序Edit BoxIDC_EDIT1显示哈希表元素显示哈希表元素IDC_EDITKEY输入key输入keyIDC_EDITDATA输入data输入data表6-4控件基本信息（2）代码设计为了能够将对话框界面上的控件能够与代码联系起来，需要为3个Edit Box控件建立Member Variables，按Ctrl+w键进入MFC ClassWizard界面，选择Member Variables选项卡，可显示成员变量设置界面，如图6-5所示:图6-5成员变量设置界面通过该界面设置与3个Edit Box控件对应的成员变量，具体如表6-6所示。控件ID成员变量类型成员变量名称IDC_EDIT1CStringm_HXIDC_EDITKEYCStringm_keyIDC_EDITDATACStringm_data表6-6控件基本信息 以下是使Botton与具体的函数代码相衔接的具体方法：为3个Botton控件建立Member Variables，按Ctrl+w键进入MFC ClassWizard界面，选择Member Variables选项卡。(1).为“插入”控件实现代码 图6-7先选中IDC_Insert项，然后选中BN_CLICKED,再点击Add Function,则系统会自动弹出以下窗口： 图6-8在编辑框中为插入控件添加代码函数，直接填入函数名即可，此处写为OnInsert，然后点击OK即可。(2)为“删除”控件实现代码 图 6-9先选中IDC_Query项，然后选中BN_CLICKED,再点击Add Function,则系统会自动弹出以下窗口： 图6-10在编辑框中为插入控件添加代码函数，直接填入函数名即可，此处写为OnQuery,然后点击OK即可。 (3)为“查询”控件实现代码 图 6-11先选中IDC_Remove项，然后选中BN_CLICKED,再点击Add Function,则系统会自动弹出以下窗口: 图 6-12在编辑框中为插入控件添加代码函数，直接填入函数名即可，此处写为OnRemove,然后点击OK即可。由于“取消”按钮已被软件激活为可用状态，所以在此不再敖述。下面是编写代码的重要阶段，可以借鉴在设计基于DOS界面的控制台应用程序的代码，并将其作必要的改写，具体改写的步骤与内容如下。（1） 首先将原来从类模板实例化后得到的hash类中添加一个CString类型的成员变量str，在以后的代码中将依据str来实现数据的交互。（2） 将hash类中所有的的cout语句全部注释掉，因为在用MFC创建交互式的对话框时，不需要也不能够使用cout流实现输出。（3） 点击工作界面窗口的“文件”，建立一个头文件命名为yan.h，并将修改后的hash类添加到该头文件中，更重要的是把该头文件一定要放在WANGDlg.cpp代码中，以便在执行WANGDlg.cpp时，顺利地调用hash类中必要的数据成员和成员函数完成基本对话框的顺利实现。（注意：在WANGDlg.cpp中添加yan.h文件时一定要写成如下格式：#include yan.h）（4） 编写读入数据按钮的消息处理函数insert()和remove()时，要及时地选择UpdateData()函数刷新界面，以便执行结果更加明显地区别。具体的修改后的实现代码如下：/ WANGDlg.cpp : implementation file/#include stdafx.h/系统给出的头文件声明#include WANG.h/系统给出的头文件声明#include WANGDlg.h/系统给出的头文件声明#include yan.h/手动添加的头文件其中包含hash类#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE = _FILE_;#endifhash h;/将实例化的hash类对象声明为全局的以便以下函数使用/ CAboutDlg dialog used for App Aboutclass CAboutDlg : public CDialogpublic:CAboutDlg();/ Dialog Data/AFX_DATA(CAboutDlg)enum IDD = IDD_ABOUTBOX ;/AFX_DATA/ ClassWizard generated virtual function overrides/AFX_VIRTUAL(CAboutDlg)protected:virtual void DoDataExchange(CDataExchange* pDX); / DDX/DDV support/AFX_VIRTUAL/ Implementationprotected:/AFX_MSG(CAboutDlg)/AFX_MSGDECLARE_MESSAGE_MAP();CAboutDlg:CAboutDlg() : CDialog(CAboutDlg:IDD)/AFX_DATA_INIT(CAboutDlg)/AFX_DATA_INITvoid CAboutDlg:DoDataExchange(CDataExchange* pDX)CDialog:DoDataExchange(pDX);/AFX_DATA_MAP(CAboutDlg)/AFX_DATA_MAPBEGIN_MESSAGE_MAP(CAboutDlg, CDialog)/AFX_MSG_MAP(CAboutDlg)/ No message handlers/AFX_MSG_MAPEND_MESSAGE_MAP()/ CWANGDlg dialogCWANGDlg:CWANGDlg(CWnd* pParent /*=NULL*/): CDialog(CWANGDlg:IDD, pParent)/AFX_DATA_INIT(CWANGDlg)m_HX = _T();m_key = _T();m_data = _T();/AFX_DATA_INIT/ Note that LoadIcon does not require a subsequent DestroyIcon in Win32m_hIcon = AfxGetApp()-LoadIcon(IDR_MAINFRAME);void CWANGDlg:DoDataExchange(CDataExchange* pDX)CDialog:DoDataExchange(pDX);/AFX_DATA_MAP(CWANGDlg)DDX_Text(pDX, IDC_EDIT1, m_HX);DDX_Text(pDX, IDC_EDIT2, m_key);DDX_Text(pDX, IDC_EDIT3, m_data);/AFX_DATA_MAPBEGIN_MESSAGE_MAP(CWANGDlg, CDialog)/AFX_MSG_MAP(CWANGDlg)ON_WM_SYSCOMMAND()ON_WM_PAINT()ON_WM_QUERYDRAGICON()ON_BN_CLICKED(IDC_insert, Oninsert)ON_BN_CLICKED(IDC_query, Onquery)ON_BN_CLICKED(IDC_remove, Onremove)/AFX_MSG_MAPEND_MESSAGE_MAP()/ CWANGDlg message handlersBOOL CWANGDlg:OnInitDialog()CDialog:OnInitDialog(); h.insert(sds,etew);/初始化哈希表 h.insert(n25,45);/初始化哈希表 h.insert(4.5765k,2);/初始化哈希表h.insert($345,6);/初始化哈希表 h.insert(43.r,55);/初始化哈希表h.insert(yan,24);/初始化哈希表h.display();/h对象调用display()函数以显示哈希表元素 m_HX=h.str; UpdateData(0);/在编辑框处显示哈希表元素/ Add About. menu item to system menu./ IDM_ABOUTBOX must be in the system command range.ASSERT(IDM_ABOUTBOX & 0xFFF0) = IDM_ABOUTBOX);ASSERT(IDM_ABOUTBOX AppendMenu(MF_SEPARATOR);pSysMenu-AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);/ Set the icon for this dialog. The framework does this automatically/ when the applications main window is not a dialogSetIcon(m_hIcon, TRUE);/ Set big iconSetIcon(m_hIcon, FALSE);/ Set small icon/ TODO: Add extra initialization herereturn TRUE; / return TRUE unless you set the focus to a controlvoid CWANGDlg:OnSysCommand(UINT nID, LPARAM lParam)if (nID & 0xFFF0) = IDM_ABOUTBOX)CAboutDlg dlgAbout;dlgAbout.DoModal();elseCDialog:OnSysCommand(nID, lParam);/ If you add a minimize button to your dialog, you will need the code below/ to draw the icon. For MFC applications using the document/view model,/ this is automatically done for you by the framework.void CWANGDlg:OnPaint() if (IsIconic()CPaintDC dc(this); / device context for paintingSendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);/ Center icon in client rectangleint cxIcon = GetSystemMetrics(SM_CXICON);int cyIcon = GetSystemMetrics(SM_CYICON);CRect rect;GetClientRect(&rect);int x = (rect.Width() - cxIcon + 1) / 2;int y = (rect.Height() - cyIcon + 1) / 2;/ Draw the icondc.DrawIcon(x, y, m_hIcon);elseCDialog:OnPaint();/ The system calls this to obtain the cursor to display while the user drags/ the minimized window.HCURSOR CWANGDlg:OnQueryDragIcon()return (HCURSOR) m_hIcon;void CWANGDlg:Oninsert() /“插入”按钮的响应函数/ TODO: Add your control notification handler code herechar a10=,b10=;UpdateData();if(m_key!=&m_data!=) memcpy(a,m_key,m_key.GetLength(); memcpy(b,m_data,m_data.GetLength();h.insert(a,b);h.display();m_HX= ;UpdateData(0);m_HX=h.str;UpdateData(0);else MessageBox(您还没有输入哈希表元素！); /MessageBox(LPCTSTR)h.str);void CWANGDlg:Onquery() /“查询”按钮的响应函数/ TODO: Add your control notification handler code here char c10=; UpdateData(); memcpy(c,m_key,m_key.GetLength(); h.query(c); MessageBox(LPCTSTR)h.str);void CWANGDlg:Onremove() /“删除”按钮的响应函数/ TODO: Add your control notification handler code herechar d10=;UpdateData();memcpy(d,m_key,m_key.GetLength();h.remove(d);MessageBox(h.str);h.display();m_HX= ;UpdateData(0);m_HX=h.str; UpdateData(0);6.2 程序测试运行程序后，首先出现的界面如图6-13所示: 图 6-13（1） 实现插入操作当分别在key和data编辑框中输入相应的元素时，如：在key的编辑框中输入wang,在data编辑框中输入yanjun时，输入后点击插入按钮时，则该记录值将在左边的哈希表编辑框中显示。具体运行结果如图6-14： 图 6-14（2） 实现查询操作当在key编辑框中输入相应的关键字时，如：在key的编辑框中输入$345时，输入后点击