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

用散列表实现简单的英文词典2011年4月4日星期一一．头文件：//文件名：Word.h//单词类的定义#includecstring#includeiostream.hclassWord{friendostream&operator(ostream&os,constWord&obj)//重载输出函数{intn=strlen(obj.word);for(inti=0;in;++i)osobj.word[i];returnos;}public:charword[25];//用于存放单词Word(){for(inti=0;i25;++i)word[i]='\0';}booloperator==(Word&r)//重载判断相等符号{if(strcmp(word,r.word)==0)returntrue;elsereturnfalse;}voidoperator=(Word&r){strcpy(word,r.word);}//重载赋值运算符};//文件名：openHashTable.h//开散列表#includecstring#includeiostream.htemplateclassTypeclassopenHashTable{private:structnode{//私有结点Typedata;structnode*next;node(){next=NULL;}node(Type&d){data=d;next=NULL;}};node**array;int(*key)(constType&x);//关键字staticintdefaultKey(constint&k){returnk;}//缺省值intsize;public:openHashTable(intlength=101,int(*f)(constType&x)=defaultKey);~openHashTable();intfind(Type&x);//查找函数boolinsert(Type&x);//插入函数boolremove(Type&x);//删除函数voidoutput();//输出词典函数};//======================开散列表函数的实现=====================================//构造函数的实现templateclassTypeopenHashTableType::openHashTable(intlength,int(*f)(constType&x)){size=length;array=newnode*[size];key=f;for(inti=0;isize;++i)array[i]=newnode;}//析构函数的实现templateclassTypeopenHashTableType::~openHashTable(){node*p,*q;for(inti=0;isize;++i){p=array[i];//分别析构每一个桶的相应链do{q=p-next;deletep;p=q;}while(p!=NULL);}delete[]array;}//插入函数的实现templateclassTypeboolopenHashTableType::insert(Type&x){intpos;node*p;pos=key(x)%size;//计算相对应的关键字p=array[pos]-next;while(p!=NULL&&!(p-data==x))p=p-next;if(p==NULL){p=newnode(x);p-next=array[pos]-next;array[pos]-next=p;returntrue;}returnfalse;}//删除函数的实现templateclassTypeboolopenHashTableType::remove(Type&x){intpos;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)returnfalse;//没有找到else{q-next=p-next;//找到后删除deletep;returntrue;}}//查找函数的实现templateclassTypeintopenHashTableType::find(Type&x){intpos;node*p;pos=key(x)%size;//计算相对应的关键字p=array[pos];while(p-next!=NULL&&!(p-next-data==x))p=p-next;if(p-next!=NULL)returnpos;//找到返回相应的桶位elsereturn0;//没到找到就返回0}//打印词典函数的实现templateclassTypevoidopenHashTableType::output(){node*p;for(inti=0;isize;++i){if(array[i]-next!=NULL){p=array[i]-next;if(i10)cout[00i];//输出单词的桶位if(i10&&i100)cout[0i];while(p!=NULL)//打印同一桶位，即有冲突的单词{coutp-data;if(p-next!=NULL)cout--;if(p-next==NULL)coutendl;p=p-next;}}}}二．Main函数的实现：//文件名：openHashTableServesAs-A-DictionaryTest.cpp//用散列表实现英文词典#includeopenHashTable.h#includeWord.h#includecstring#includeiostream.hintmyHash(constWord&a);//求权重函数intpower(intn);//求2的n次方函数voidmenu();//打印菜单函数voidmain(){Wordw;charchioce;intn;boolflag=false;openHashTableWorddictionary(101,myHash);//定义一个名为dictionary的开散列表，即作为词典while(!flag){menu();cinchioce;switch(chioce){case'i':cout请输入单词：;cin.ignore(1,'\n');cin.getline(w.word,25);if(dictionary.insert(w))cout插入成功!endl;elsecout这个单词已存在!endl;break;case'd':cout请输入单词：;cin.ignore(1,'\n');cin.getline(w.word,25);if(dictionary.remove(w))cout删除成功!endl;elsecout这个单词不存在!endl;break;case's':cout请输入单词：;cin.ignore(1,'\n');cin.getline(w.word,25);n=dictionary.find(w);if(n!=0)cout已找到,单词在第n桶中endl;elsecout这个单词不存在!endl;break;case'v':cout词典如下所示：endl;dictionary.output();break;case'q':flag=true;break;default:cout输入错误!endl;break;}}}//求权重函数的实现intmyHash(constWord&a){unsignedlongintnum=0;//从a（A）到z（Z）的权重依次为0到26for(inti=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);elsenum+=(a.word[i]-'0'-17)*power(i);}returnnum;}//求2的n次方函数的实现intpower(intn){intnum=1;for(inti=1;i=n;++i)num*=2;returnnum;}//打印菜单函数的实现voidmenu(){cout\n====================Menu=============================\ni--insertd--deletes--searchv--viewq--exit\n请选择：;}