C++二叉树实现词频分析功能

2023-09-19 22:25:05 283

通过二叉树存单词，并且对总共的单词数量进行计数，二叉树自适应的将出现频率高的单词往上移动以减少二叉树的搜索时间。
代码如下

/***********************genSplay.h***********************/
#ifndef_GENSPLAY_H_
#define_GENSPLAY_H_

#include
usingnamespacestd;

//树节点
template
classSplayingNode
{
public:
Tinfo;
SplayingNode*left,*right,*parent;//节点指针
SplayingNode(){
left=right=parent=0;
}
SplayingNode(constT&el,SplayingNode*l=0,
SplayingNode*r=0,SplayingNode*p=0)
:info(el),left(l),right(r),parent(p){}
};
//二叉树
template
classSplayTree
{
protected:
SplayingNode*root;
voidrotateR(SplayingNode*);//向右旋转
voidrotateL(SplayingNode*);//向左旋转
voidcontinueRotation(SplayingNode*gr,SplayingNode*par,
SplayingNode*ch,SplayingNode*desc);//重新定义父节点指针
voidsemisplay(SplayingNode*);//更改树结构，将权值大的向上移动
voidinorder(SplayingNode*);//中序遍历
voidvirtualvisit(SplayingNode*){}//虚函数
public:
SplayTree(){
root=0;
}
voidinorder(){
inorder(root);
}
T*search(constT&);
voidinsert(constT&);
};

template
voidSplayTree::continueRotation(SplayingNode*gr,SplayingNode*par,
SplayingNode*ch,SplayingNode*desc)
{
if(gr!=0){
if(gr->right==ch->parent)
gr->right=ch;
else
gr->left=ch;
}
else
root=ch;
if(desc!=0)
desc->parent=par;
par->parent=ch;
ch->parent=gr;
}

template
voidSplayTree::rotateR(SplayingNode*p)
{
p->parent->left=p->right;
p->right=p->parent;
continueRotation(p->parent->parent,p->right,p,p->right->left);
}

template
voidSplayTree::rotateL(SplayingNode*p)
{
p->parent->right=p->left;
p->left=p->parent;
continueRotation(p->parent->parent,p->left,p,p->left->right);
}
template
voidSplayTree::semisplay(SplayingNode*p)
{
while(p!=root){
if(p->parent->parent==NULL){
if(p->parent->left==p)
rotateR(p);
else
rotateL(p);
}
elseif(p->parent->left==p){
if(p->parent->parent->left==p->parent){
rotateR(p->parent);
p=p->parent;
}
else{
rotateR(p);
rotateL(p);
}
}
else{
if(p->parent->parent->right==p->parent){
rotateL(p->parent);
p=p->parent;
}
else{
rotateL(p);
rotateR(p);
}
}
if(root==NULL)
root=p;
}
}

template
T*SplayTree::search(constT&el)
{
SplayingNode*p=root;
while(p!=NULL){
if(p->info==el){
semisplay(p);
return&p->info;
}
elseif(elinfo)
p=p->left;
else
p=p->right;
}
return0;
}

template
voidSplayTree::insert(constT&el)
{
SplayingNode*p=root,*prev=NULL,*newNode;
while(p!=0){
prev=p;
if(elinfo)
p=p->left;
else
p=p->right;
}
if((newNode=newSplayingNode(el,0,0,prev))==0){
cerr<<"noroomfornewnode.\n";
exit(1);
}
if(root==0)
root=newNode;
elseif(elinfo)
prev->left=newNode;
else
prev->right=newNode;
}

template
voidSplayTree::inorder(SplayingNode*p)
{
if(p!=0){
inorder(p->left);
visit(p);
inorder(p->right);
}
}

#endif//_GENSPLAY_H_

/***********************Splay.cpp***********************/
#include
#include
#include
#include
#include//exit(0)
#include"genSplay.h"
usingnamespacestd;

//用作计数对象的类
classWord
{
private:
char*word;
intfreq;
friendclassWordSplay;
//friendostream&operator<<(ostream&out,constWord&wd);
public:
Word(){
freq=1;
}
intoperator==(constWord&ir)const{
returnstrcmp(word,ir.word)==0;
}
intoperator<(constWord&ir)const{
returnstrcmp(word,ir.word)<0;
}
};

classWordSplay:publicSplayTree
{
private:
intdifferentWords,wordCnt;
voidvisit(SplayingNode*);
public:
WordSplay(){
differentWords=wordCnt=0;
}
voidrun(ifstream&,char*);
};

voidWordSplay::visit(SplayingNode*p)
{
differentWords++;
wordCnt+=p->info.freq;
}

voidWordSplay::run(ifstream&fin,char*filename)
{
charch='',i;
chars[100];
Wordrec;
while(!fin.eof()){
while(1){
if(!fin.eof()&&!isalpha(ch))
fin.get(ch);
else
break;
}
if(fin.eof())
break;
for(i=0;!fin.eof()&&isalpha(ch);i++){
s[i]=toupper(ch);
fin.get(ch);
}
s[i]='\0';
if(!(rec.word=newchar[strlen(s)+1])){
cerr<<"noroomfornewwords.\n";
exit(1);
}
strcpy(rec.word,s);
Word*p=search(rec);
if(p==0)
insert(rec);
else
p->freq++;
}
inorder();
cout<<"\n\nFile"<>Filename;
ifstreamfin(Filename);
if(fin.fail()){
cerr<<"cannotopen"<
有空回来补充相应的其他功能：
将对应的单词和文件写到文件里面去，先序遍历

优化性能
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

C++二叉树实现词频分析功能

热门推荐

随机推荐