hashlist1.cpp

实现散列表操作 大学数据结构教材要求实验

#include<iomanip.h>
#include<stdlib.h>
#include "hashList1.h"
const int NullTag=-100;
const int DeleteTag=-200;
void InitHashList(ArrayHashList& HT,int& m)
{
	cout<<"从键盘输入待建立的数组散列表的长度，它要不小于待";
	cout<<"散列存储的数据个数！"<<endl;
	cout<<"散列表长度为：";
	cin>>m;
	HT=new ElemType[m];
	for(int i=0;i<m;i++)HT[i]=NullTag;
}
void ClearHashList(ArrayHashList HT,int m)
{
	for(int i=0;i<m;i++)HT[i]=NullTag;
}
void DeleteHashList(ArrayHashList& HT)
{
	delete []HT;HT=NULL;
}
static int HashAdress(ElemType item,int m)
{
	return item% m;
}
void Insert(ArrayHashList HT,int m,ElemType item)
{
	int d=HashAdress(item,m);
	int temp=d;
	while (HT[d]!=NullTag&&HT[d]!=DeleteTag) {
		d=(d+1)%m;
		if (d==temp) {
			cerr<<"散列表无空间！"<<endl;
			exit(1);
		}
	}
	HT[d]=item;
}
int Search(ArrayHashList HT,int m,ElemType item)
{
	int d=HashAdress(item,m);
	int temp=d;
	while (HT[d]!=NullTag) {
		if(HT[d]==item)return d;
		else d=(d+1)%m;
		if(d==temp)return -1;
	}
	return -1;
}
void Delete(ArrayHashList HT,int m,ElemType item)
{
	int d=HashAdress(item,m);
	int temp=d;
	while (HT[d]!=NullTag) {
		if (HT[d]==item) {
			HT[d]=DeleteTag;
			return;
		}
		else
			d=(d+1)%m;
		if(d==temp) break;
	}
	cerr<<"散列表中无"<<item<<"元素！"<<endl;
	exit(1);
}
void PrintHashList(ArrayHashList HT,int m)
{
	for(int i=0;i<m;i++)
		cout<<setw(5)<<i<<':'<<setw(5)<<HT[i]<<endl;
}