C++英文词典的简单实现.doc

用散列表实现简单的英文词典
2011年4月4日星期一
一．头文件：
//文件名：Word.h
//单词类的定义

#include <cstring>
#include <iostream.h>

class Word{
friend ostream& operator<<(ostream &os, const Word & obj)//重载输出函数
{
int n=strlen(obj.word);

for(int i=0; i<n; ++i) os << obj.word[i];
return os;
}
public:
char word[25]; //用于存放单词

Word(){ for(int i=0; i<25; ++i) word[i]='\0';}
bool operator==(Word &r)//重载判断相等符号
{
if(strcmp(word,r.word)==0) return true;
else return false;
}
void operator=(Word &r) { strcpy(word,r.word); }//重载赋值运算符
};

//文件名：openHashTable.h
//开散列表

#include <cstring>
#include <iostream.h>

template <class Type>
class openHashTable{
private:
struct node{//私有结点
Type data;
struct node *next;

node(){ next = NULL; }
node(Type &d){ data = d; next = NULL;}
};

node **array;
int(*key)(const Type &x);//关键字
static int defaultKey(const int &k) { return k; }//缺省值
int size;

public:
openHashTable(int length =101 , int(* f)(const Type &x) = defaultKey);
~openHashTable();

int find(Type &x); //查找函数
bool insert(Type &x); //插入函数
bool remove( Type &x); //删除函数

void output(); //输出词典函数
};

//======================开散列表函数的实现=====================================

//构造函数的实现
template <class Type>
openHashTable<Type>::openHashTable(int length, int(*f)(const Type &x))
{
size = length;
array = new node *[size];
key = f;
for(int i=0; i<size; ++i) array[i] = new node;
}

//析构函数的实现
template <class Type>
openHashTable<Type>::~openHashTable()
{
node *p, *q;

for(int i=0; i<size; ++i)
{
p = array[i];//分别析构每一个桶的相应链
do{
q = p->next;
delete p;
p = q;
}while(p!=NULL);
}

delete [] array;
}

//插入函数的实现
template <class Type>
bool openHashTable<Type>::insert(Type &x)
{
int pos;
node *p;

pos = key(x)%size; //计算相对应的关键字
p = array[pos]->next;

while(p!=NULL && !(p->data==x)) p = p->next;

if(p==NULL)
{
p = new node(x);
p->next = array[pos]->next;
array[pos]->next = p;

return true;
}

return false;
}

//删除函数的实现
template <class Type>
bool openHashTable<Type>::remove(Type &x)
{
int pos;
node *p, *q;

pos = key(x)%size; //计算相对应的关键字
q = array[pos];
p = q->next;

while(p!=NULL&& !(p->data==x))
{
q = p;
p = p->next;
}

if(p==NULL) return false; //没有找到
else{
q->next = p->next; //找到后删除
delete p;

return true;
}
}

//查找函数的实现
template<class Type>
int openHashTable<Type>::find(Type &x)
{
int pos;
node *p;

pos = key(x)%size; //计算相对应的关键字
p = array[pos];
while(p->next!=NULL && !(p->next->data==x) ) p = p->next;

if(p->next!=NULL) return pos; //找到返回相应的桶位
else return 0; //没到找到就返回0
}

//打印词典函数的实现
template<class Type>
void openHashTable<Type>::output()
{
node *p;

for(int i=0; i<size; ++i)
{
if(array[i]->next!=NULL)
{
p=array[i]->next;
if(i<10) cout << " [00" << i << "] ";//输出单词的桶位
if(i>10&&i<100) cout << " [0" << i << "] ";

while(p!=NULL) //打印同一桶位，即有冲突的单词
{
cout << p->data;
if(p->next!=NULL) cout << " --> ";
if(p->next==NULL) cout << endl;
p = p->next;
}
}
}
}

二．Main函数的实现：
//文件名：openHashTableServesAs-A-DictionaryTest.cpp
//用散列表实现英文词典

#include "openHashTable.h"
#include "Word.h"
#include <cstring>

#include <iostream.h>

int myHash(const Word &a); //求权重函数
int power(int n); //求2的n次方函数
void menu(); //打印菜单函数

void main()
{
Word w;
char chioce;
int n;
bool flag=false;
openHashTable<Word>dictionary(101,myHash); //定义一个名为dictionary的开散列表，即作为词典

while(!flag)
{
menu();
cin >> chioce;
switch(chioce)
{
case 'i': cout << " 请输入单词：";
cin.ignore(1,'\n');
cin.getline(w.word,25);
if(dictionary.insert(w)) cout << " 插入成功!" << endl;
else cout << " 这个单词已存在!" << endl;
break;

case 'd': cout << " 请输入单词：";
cin.ignore(1,'\n');
cin.getline(w.word,25);
if(dictionary.remove(w)) cout << " 删除成功!" << endl;
else cout << " 这个单词不存在!" << endl;
break;

case 's': cout << " 请输入单词：";
cin.ignore(1,'\n');
cin.getline(w.word,25);
n = dictionary.find(w);
if(n!=0) cout << " 已找到,单词在第 " << n << " 桶中"<< endl;
else cout << " 这个单词不存在!" << endl;
break;

case 'v': cout << " 词典如下所示：" << endl;
dictionary.output();
break;

case 'q': flag = true;
break;

default: cout << " 输入错误!" << endl;
break;
}
}

}

//求权重函数的实现
int myHash(const Word &a)
{
unsigned long int num=0;
//从a（A）到z（Z）的权重依次为0到26
for(int i=0; a.word[i]!='\0'; ++i)//将单词的从左到右分别乘上的2排位次方，如第四位乘2的3次方
{
if(a.word[i]>='a'&&a.word[i]<='z') num += (a.word[i] - '0'- 17 -32)*power(i);
else num += (a.word[i] - '0'-17)*power(i);
}

return num;
}

//求2的n次方函数的实现
int power(int n)
{
int num=1;

for(int i=1; i<=n; ++i) num *=2;

return num;
}

//打印菜单函数的实现
void menu()
{
cout << "\n==================== Menu =============================\n"
<< " i--insert d--delete s--search v--view q--exit \n"
<< " 请选择：";
}