2014广工数据结构实验报告哈希表

1、 数据结构设计性实验报告 课程名称_数据结构实验 _ 题目名称 哈希表 学生学院_ 计算机学院_ 专业班级_ 学 号_ 学生姓名_ _指导教师_ _ 2015 年 7 月 2 日1. 题目采用哈希表为存储结构，实现抽象数据类型HashTable。ADT HAS数据对象D：D是具有相同特性的数据元素的集合。数据关系R：根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个连续的有限地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表。这一映像过程称为造表或散列，所得存储位置称哈希地址或散列地址。基本操作： InitHash(&H) 操作结果：初始化哈希表H。

2、 DestoyHash(&H) 初始条件：哈希表H已存在。 操作结果：销毁哈希表H。 CreateHash(&H) 初始条件：哈希表H已存在。 操作结果：构造哈希表H。 SearchHash(H) 初始条件：哈希表已存在。 操作结果：查找哈希表H中元素。 InsertHash(&H) 初始条件：哈希表H已存在。 操作结果：插入元素到哈希表 DeleteHash(&H, key, &e) 初始条件：哈希表已存在且非空。 操作结果：删除H的第i个元素，并用e返回其值，H的长度减1。 ADT List3. 算法设计#include <conio.h>

3、;#include <stdio.h>#include <stdlib.h>#include <string.h>#include<time.h>#define random(x) (rand()%x)#define OK 1#define SUCCESS 1#define UNSUCCESS 0#define DUPLICAPE -1#define OVERFLOW 0typedef int KeyType;typedef int Status;typedef struct KeyType key; int tag;RecordrdType,

4、RcdType;typedef struct RcdType *rcd; int size; int count;HashTable;int InitHash(HashTable *H, int size) /初始化哈希表int i;H->rcd=(RcdType*)malloc(size*sizeof(RcdType);if(NULL=H->rcd)return OVERFLOW;for(i=0;i<=size;i+)H->rcdi.tag=0;H->size=size;H->count=0;return OK;int DestoyHash(HashTab

5、le *H)/销毁哈希表 free(H->rcd);H->rcd=NULL;H->count=0;H->size=0;return OK;int SearchHash(HashTable H, KeyType key , int &p,int &c ) /查找哈希表 c=0;p=key%H.size;/求得哈希地址 while(H.rcdp.tag!=0&&(H.rcdp.key!=key|-1=H.rcdp.tag) p=(p+1)%H.size;c+;/求得下一探测地址 if(H.rcdp.key=key)return SUCCESS

6、;else return UNSUCCESS;int InsertHash(HashTable *H, RcdType e)/哈希表的插入int c=0,j;if(SUCCESS=SearchHash(*H,e.key,j,c)return -1;else H->rcdj=e;H->rcdj.tag=1;+H->count;return c;int DeleteHash(HashTable *H,KeyType key,RcdType e) /哈希表的删除int j,c;if(UNSUCCESS=SearchHash(*H,key,j,c)return UNSUCCESS;e

7、lse e=H->rcdj;H->rcdj.tag=-1;H->count-;return SUCCESS;void display(HashTable *H)printf("n哈希表数据:"); for(int i=1;i<H->count;i+) printf("%d ",H->rcdi); printf("n");4测试int main()int i,j,select,x1,x2,x3,x4,g,n,k,b,f;RcdType e;KeyType key;srand(time(0); /初始化

8、随机种子HashTable H;InitHash(&H,9);for(i=1;i<=10;i+)e.tag=1;e.key=random(50);InsertHash(&H,e);printf("nn"); do display(&H); printf("select 1 销毁哈希表 DestoyHash()n"); printf("select 2 哈希表的查找 SearchHash()n"); printf("select 3 哈希表的插入 InserchHash()n"); pr

9、intf("select 4 哈希表的删除 deleteHash()n"); printf("input your select: "); scanf("%d",&select); switch(select) case 1: printf("销毁哈希表,确定输入1，否则输入0n"); printf("输入数字为:"); scanf("%d",&x1); if(x1=1)return DestoyHash(&H); else break; case 2

10、: printf("请输入要查找的数据元素: "); scanf("%d",&key); k=SearchHash(H,key,b,g); if(k=1) printf("查找成功n"); printf("%d在哈希表中的位置为：%d,冲突次数为：%dn",key,b,g); else printf("查找失败n"); break; case 3: printf("请输入要插入的元素: "); scanf("%d",&e); if(Inse

11、rtHash(&H,e) printf("插入成功n"); else printf("插入失败n"); break; case 4: printf("请输入要删除的元素序号: "); scanf("%d",&x4); if(DeleteHash(&H,key,e) printf("删除成功n"); else printf("错误n"); break; while (select>0 && select <5); return OK;4. 程序测试结果使用VC+编译软件，使用c语言