赞
踩
一、实验目的
1、掌握哈希表的构造的方法及其解决冲突的机制(开放地址法)
2、掌握常见的查找方法,如折半查找等。
二、实验要求
1、认真阅读程序,见参考程序7.1。
2、用哈希法建立哈希表并对其进行查找、删除操作的源程序。请将他们输入计算机,编译、连接并运行。
3、保存和截图程序的运行结果,并结合程序进行分析。
三、实验内容和基本原理
1、哈希表的开放地址法解决冲突:设有一个数据元素的关键字为key,其在哈希表中的存储位置为D=H(key),此时在哈希表中的存储位置非空,则发生了冲突。那么关键字为key的数据元素在哈希表中的下一个存储位置应该是:
ND=(D+di)%m (I=1,2,3…,K(K小于等于 m-1))
这里:m是哈希表的表长;di是增量序列。
参考程序1
- //* * * * * * * * * * * * * * * * * * * * * * * *
-
- //*PROGRAM :哈希表的综合操作 *
-
- //*CONTENT :Insert,Search,Deltet *
-
- //* * * * * * * * * * * * * * * * * * * * * * * *
-
- #include <dos.h>
-
- #include <conio.h>
-
- #include <math.h>
-
- #include <stdio.h>
-
- #include <stdlib.h>
-
- #define MAXSIZE 12 //哈希表的最大容量,与所采//用的哈希函数有关
-
- enum BOOL{False,True};
-
- enum HAVEORNOT{NULLKEY,HAVEKEY,DELKEY};
-
- //哈希表元素的三种状态,没有记录、有记录、//有过记录但已被删除
-
- typedef struct //定义哈希表的结构
-
- {int elem[MAXSIZE]; //数据元素体
-
- HAVEORNOT elemflag[MAXSIZE]; //元素状态标//志,没有记录、有记录、有过记录但已被删除
-
- int count; //哈希表中当前元素的个数
-
- }HashTable;
-
- typedef struct
-
- {int keynum; //记录的数据域,只有关键字一项
-
- }Record;
-
- void InitialHash(HashTable&); //初始化哈希表
-
- void PrintHash(HashTable); //显示哈希表中的所//有元素
-
- BOOL SearchHash(HashTable,int,int&); //在哈希表 //中查找元素
-
- BOOL InsertHash(HashTable&,Record); //在哈//希表中插入元素
-
- BOOL DeleteHash(HashTable&,Record); //在哈//希表中删除元素
-
- int Hash(int); //哈希函数
-
- void main()
-
- {HashTable H; //声明哈希表H
-
- char ch,j='y';
-
- int position;
-
- Record R;
-
- BOOL temp;
-
- textbackground(3); //设定屏幕颜色
-
- textcolor(15);
-
- clrscr();
-
- //-------------------------程序说明-------------------------------
-
- printf("This program will show how to operate to a HashTable.\n");
-
- printf("You can display all elems,search a elem,\ninsert a elem,delete a elem.\n");
-
- //----------------------------------------------------------------
-
- InitialHash(H);
-
- while(j!='n')
-
- {printf("1.display\n");
-
- printf("2.search\n");
-
- printf("3.insert\n");
-
- printf("4.delete\n");
-
- printf("5.exit\n");
-
- scanf(" %c",&ch); //输入操作选项
-
- switch(ch)
-
- {case '1':if(H.count) PrintHash(H); //哈希表//不空
-
- else printf("The HashTable has no elem!\n");
-
- break;
-
- case '2':if(!H.count) printf("The HashTable has no elem!\n"); //哈希表空
-
- else
-
- {printf("Please input the keynum(int) of the elem to search:");
-
- scanf("%d",&R.keynum); //输入待查//记录的关键字
-
- temp=SearchHash(H,R.keynum,position);
-
- //temp=True:记录查找成功, //temp=False:没有找到待查记录
-
- if(temp) printf("The position of the elem is %d\n",position);
-
- else printf("The elem isn't exist!\n");
-
- }
-
- break;
-
- case '3':if(H.count==MAXSIZE) //哈希表//已满
-
- {printf("The HashTable is full!\n");
-
- break;
-
- }
-
- printf("Please input the elem(int) to insert:");
-
- scanf("%d",&R.keynum); //输入要插入//的记录
-
- temp=InsertHash(H,R);
-
- //temp=True:记录插入成功;//temp=False:已存在关键字相同的记录
-
- if(temp) printf("Sucess to insert the elem!\n");
-
- else printf("Fail to insert the elem.The same elem has been exist!\n");
-
- break;
-
- case '4':printf("Please input the keynum of the elem(int) to delet:");
-
- scanf("%d",&R.keynum); //输入要删除记//录的关键字
-
- temp=DeleteHash(H,R);
-
- //temp=True:记录删除成功;//temp=False:待删记录不存在
-
- if(temp) printf("Sucess to delete the elem!\n");
-
- else printf("The elem isn't exist in the HashTable!\n");
-
- break;
-
- default: j='n';
-
- }
-
- }
-
- printf("The program is over!\nPress any key to shut off the window!\n");
-
- getchar();getchar();
-
- }
-
- void InitialHash(HashTable &H)
-
- {//哈希表初始化
-
- int i;
-
- H.count=0;
-
- for(i=0;i<MAXSIZE;i++) H.elemflag[i]=NULLKEY;
-
- }
-
- void PrintHash(HashTable H)
-
- {//显示哈希表所有元素及其所在位置
-
- int i;
-
- for(i=0;i<MAXSIZE;i++) //显示哈希表中记录所在//位置
-
- if(H.elemflag[i]==HAVEKEY) //只显示标志为HAVEKEY(存放有记录)的元素
-
- printf("%-4d",i);
-
- printf("\n");
-
- for(i=0;i<MAXSIZE;i++) //显示哈希表中记录值
-
- if(H.elemflag[i]==HAVEKEY)
-
- printf("%-4d",H.elem[i]);
-
- printf("\ncount:%d\n",H.count); //显示哈希表当前 //记录数
-
- }
-
- BOOL SearchHash(HashTable H,int k,int &p)
-
- {//在开放定址哈希表H中查找关键字为k的数据元//素,若查找成功,以p指示
-
- //待查数据元素在表中的位置,并返回True;否则,//以p指示插入位置,并返回False
-
- int p1;
-
- p1=p=Hash(k); //求得哈希地址
-
- while(H.elemflag[p]==HAVEKEY&&k!=H.elem[p])
-
- //该位置中填有记录并且关键字不相等
-
- {p++; //冲突处理方法:线性探测再散列
-
- if(p>=MAXSIZE) p=p%MAXSIZE; //循环搜索
-
- if(p==p1) return False; //整个表已搜索完,没//有找到待查元素
-
- }
-
- if(k==H.elem[p]&&H.elemflag[p]==HAVEKEY) //查找成功,p指示待查元素位置
-
- return True;
-
- else return False; //查找不成功
-
- }
-
- BOOL InsertHash(HashTable &H,Record e)
-
- {//查找不成功时插入元素e到开放定址哈希表H //中,并返回True,否则返回False
-
- int p;
-
- if(SearchHash(H,e.keynum,p)) //表中已有与e有相//同关键字的元素
-
- return False;
-
- else
-
- {H.elemflag[p]=HAVEKEY; //设置标志为HAVEKEY,表示该位置已有记录
-
- H.elem[p]=e.keynum; //插入记录
-
- H.count++; //哈希表当前长度加一
-
- return True;
-
- }
-
- }
-
- BOOL DeleteHash(HashTable &H,Record e)
-
- {//在查找成功时删除待删元素e,并返回True,否//则返回False
-
- int p;
-
- if(!SearchHash(H,e.keynum,p)) //表中不存在待删 //元素
-
- return False;
-
- else
-
- {H.elemflag[p]=DELKEY; //设置标志为//DELKEY,表明该元素已被删除
-
- H.count--; //哈希表当前长度减一
-
- return True;
-
- }
-
- }
-
- int Hash(int kn)
-
- {//哈希函数:H(key)=key MOD 11
-
- return (kn%11);
-
- }
![](https://csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreWhite.png)
2、对有序表进行非递归折半查找。
- int BinSearch1(Seqlist A[],int n,KeyType k)
-
- int low=0,high=n-1,mid;
-
- while(low<=high)
-
- {
-
- mid=(low+high)/2;
-
- if(high==k)
-
- {
-
- printf("所找的元素%d下标为%d\n",k,mid);
-
- return mid;
-
- }
-
- else if(A[mid].key>k)
-
- {
-
- high=mid-1;
-
- }
-
- else
-
- {
-
- low=mid+1;/*将未完成的代码补全,提示:此处添加一条语句*/
-
- }
-
- return -1;
-
- }
![](https://csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreWhite.png)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。