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

用散列表实现简单的英文词典2011年4月4日星期一一头文件：/文件名：Word.h/单词类的定义#include #include class Wordfriend ostream& operator(ostream &os, const Word & obj)/重载输出函数int n=strlen(obj.word);for(int i=0; in; +i) os obj.wordi;return os;public:char word25; /用于存放单词Word() for(int i=0; i25; +i) wordi=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 #include template class openHashTableprivate: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 openHashTable:openHashTable(int length, int(*f)(const Type &x)size = length;array = new node *size;key = f;for(int i=0; isize; +i) arrayi = new node;/析构函数的实现template openHashTable:openHashTable()node *p, *q;for(int i=0; inext;delete p;p = q;while(p!=NULL);delete array;/插入函数的实现template bool openHashTable:insert(Type &x)int pos;node *p;pos = key(x)%size; /计算相对应的关键字p = arraypos-next;while(p!=NULL & !(p-data=x) p = p-next;if(p=NULL)p = new node(x);p-next = arraypos-next;arraypos-next = p;return true;return false;/删除函数的实现template bool openHashTable:remove(Type &x)int pos; node *p, *q;pos = key(x)%size; /计算相对应的关键字 q = arraypos;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;/查找函数的实现templateint openHashTable:find(Type &x)int pos;node *p;pos = key(x)%size; /计算相对应的关键字p = arraypos;while(p-next!=NULL & !(p-next-data=x) ) p = p-next;if(p-next!=NULL) return pos; /找到返回相应的桶位else return 0; /没到找到就返回0/打印词典函数的实现templatevoid openHashTable:output()node *p;for(int i=0; inext!=NULL)p=arrayi-next;if(i10) cout 00 i 10&i100) cout 0 i ;while(p!=NULL) /打印同一桶位，即有冲突的单词cout data;if(p-next!=NULL) cout ;if(p-next=NULL) cout next;二Main函数的实现：/文件名：openHashTableServesAs-A-DictionaryTest.cpp/用散列表实现英文词典#include openHashTable.h#include Word.h#include #include int myHash(const Word &a); /求权重函数int power(int n); /求2的n次方函数void menu(); /打印菜单函数void main() Word w; char chioce;int n;bool flag=false;openHashTabledictionary(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 输入错误! =a&a.wordi=z) num += (a.wordi - 0- 17 -32)*power(i);else num += (a.wordi - 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 请选择：;