hash.cpp

利用哈希表统计文本文件中单词的个数

#include<iostream>
#include<string>
#include"stdio.h"
#include"ctype.h"
const int maxsize=91;
using namespace std;
struct Node
{
    string data;
	Node*next;
	bool link;
	Node()
	{
	next=NULL;
	link=false;
	}

    Node(string x,Node*link)
	{
	  data=x;
	  next=link;
      
	}
};

typedef Node*hashlist;//hashlist为指向Node节点类型的指针类型

class hashtable
{
public:
	 hashtable();
	void Clear_hashlist( );
	int Insert(const string &item);
	int Search_hashlist(const string &item);
	int H( string item);
	void Creat_hashtable();
	void Count();
	void print(const string&item)
	{
		int n=item.length ();
		for(int i=0;i<n;i++)
			cout<<item[i];
	}
private:
	
	hashlist HT[maxsize];
};

 

 hashtable::hashtable ()
{
	for(int i=0;i<maxsize;i++)
		HT[i]=NULL;
	
}

void hashtable::Clear_hashlist ()
{
	Node*p;
	for(int i=0;i<maxsize;i++)
	{
		p=HT[i];
		while(p!=NULL)
		{
			HT[i]=p->next;
			delete p;
			p=HT[i];
		}
	}
}


int hashtable::H(string item)//哈希函数--取模法
{
	int d=0;

	int m=item.length();
	for(int i=0;i<m;i++)
		d=d+item[i];
	d=d%91;
	return d;
}

int hashtable::Insert (const string &item)//插入单词到散列表
{
	int d=H(item);
	Node*p=new Node; 
	if(p==NULL)return 0;
	p->data =item;
    p->next=HT[d];
	HT[d]=p;
	return 1;
}


int hashtable::Search_hashlist (const string &item)
{
	int d=H(item);
	int n=0;//单词个数
	Node*p=HT[d];
	while(p!=NULL)
	{
		if(p->data ==item)
		{
			n++;
			p->link =true;//表示此单词已经被检索并计数
		}
		p=p->next ;
	}
	return n;
}

   void hashtable::Creat_hashtable ()
	{
		FILE*fp;
		char ch;
		char s[20];
		string filename;
        cout<<"请输入文件名。"<<endl;
		cin>>filename;
		if((fp=fopen("msp.txt","r"))==NULL)//以只读形式打开文件
		{
			cout<<"不能打开文件。"<<endl;
			exit(0);
		}
		else cout<<"open"<<endl;
		ch=fgetc(fp);
	    while(ch!=EOF)
		{    
			int i=0;
			if(!isalpha(ch))//不是字母
				ch=fgetc(fp);
			else
			{
				do
				{
					if(isupper(ch))ch=tolower(ch);
					s[i]=ch;
					i++;
					ch=fgetc(fp);
				} while(isalpha(ch));
				s[i++]='\0';
				Insert(s);
			}	
		}
	}
	
	
   void hashtable::Count ()
	{
		cout<<"统计的单词个数如下："<<endl;
		for(int i=0;i<maxsize;i++)
		{
			int n=0;
			Node*p=HT[i];
			while(p!=NULL)
			{   
				if(p->link ==true)
				{
					p=p->next ;
				    break;
				}
				print(p->data);
				cout<<": ";
				n=Search_hashlist(p->data );
				cout<<n<<'\t';
			}
		}
	}


void main()
{
	
	hashtable k;
	k.Clear_hashlist ();
    k.Creat_hashtable ();
    k.Count ();
}