好字符串频率统计507count1.cpp

设计一个算法

#include <iostream>
#include <fstream>
using namespace std;

#include "time.h"
clock_t start,finish;
ifstream in("input.txt");
ofstream out("output.txt");
int key=0;

class String
{
    public:
		String(char *s=" ");
		String(String &s);
		~String();
		String &operator=(String &s);
		bool operator==(String &s);
		int Length(){return size-1;};
		int readstring(istream &);
		void output();
		int count;
	private:
		char *str;
		int *pre;
		int size;

};
String::String(char *s)
{
	count=0;
	size=strlen(s)+1;
	str=new char[size];
	if(str==0)throw;
	strcpy(str,s);
	pre=new int[size];
	if(pre==0)throw;
}
String::String(String &s)
{
	count=0;
	size=s.size;
	str=new char[size];
	if(str==0)throw;
	strcpy(str,s.str);
	pre=new int[size];
	if(pre==0)throw;
}
String::~String()
{
	delete[]str;
	delete[]pre;
}
String &String::operator =(String &s)
{
	if(s.size!=size)
	{
		delete[]str;
		str=new char[s.size];
		if(str==0)throw;
		size=s.size;
	}
	strcpy(str,s.str);
	return *this;
}
bool String::operator ==(String &s)
{
	return strcmp(str,s.str)==0;
}
void String::output()
{
	out<<str;
}
int String::readstring(istream &istr)
{
	char tmp[200];
/*	char s;
	s=in.peek();
	if(s==' ')
	{
		in.ignore(1);
		return 0;
	}*/
	if(in>>tmp)
	{
		delete[]str;
		size=strlen(tmp)+1;
		str=new char[size];
		if(str==0)throw;
		strcpy(str,tmp);
		return size-1;
	}
	else return -1;
}

template<class T> class List;
template<class T>
class Node
{
	friend List<T>;
	private:
		T data;
		Node<T> *next;
};
template<class T>
class List
{
	private:
		Node<T> *first;
	public:
		List(){first=0;}
		void clearlist();
		bool empty(){return first==0;}
		int length();
		int Locate(T &x);
		List<T> &insert(int k,T &x);
		List<T> &Delete(int k,T &x);
		void output();
};
template<class T>
void List<T>::clearlist()
{
	Node<T> *next;
	while(first)
	{
		next=first->next;
		delete first;
		first=next;
	}
}
template<class T>
int List<T>::length()
{
	Node<T> *current=first;
	int len=0;
	while(current)
	{
		len++;
		current=current->next;
	}
	return len;
}
template<class T>
int List<T>::Locate(T &x)
{
	Node<T> *current=first;
	int index=1;
	while(current)
	{
		if(current->data==x)
		{
			current->data.count++;
			break;
		}
		current=current->next;
		index++;
	}
	if(current)return index;
	return 0;
}
template<class T>
List<T> &List<T>::insert(int k,T &x)
{
	if(k<0)throw;
	Node<T> *p=first;
	for(int i=1;i<k&&p;i++)
		p=p->next;
	if(k>0&&!p)throw;
	Node<T> *y=new Node<T>;
	y->data=x;
	if(k)
	{
		y->next=p->next;
		p->next=y;
	}
	else
	{
		y->next=first;
		first=y;
		y->data.count++;
	}
	return *this;
}
/*template<class T>
List<T> &List<T>::Delete(int k,T &x)
{
	if(k<1||!first)throw;
	Node<T> *p=first;
	if(k==1)first=first->next;
	else
	{
		Node<T> *q=first;
		for(int i=1;i<k-1&&q;i++)
			q=q->next;
		if(!q||!q->next)throw;
		p=q->next;
		q->next=p->next;
	}
	x=p->data;
	delete p;
	return *this;
}*/
template<class T>
void List<T>::output()
{
	Node<T> *current;
	for(current=first;current;current=current->next)
	{
		current->data.output();
		out<<" "<<current->data.count<<endl;
	}
}

template<class T>
int hashf(T x)
{
	int len=x.Length();
	return len%101;
}
template<class T>
class openhashtable
{
    public:
		openhashtable(int nbuckets,int hashf(T x));
		~openhashtable(){clear();}
		bool member(T &x);
		openhashtable<T> &insert(T x);
		openhashtable<T> &Delete(T &x);
		void output(int key);
	private:
		void clear();
		int size;
		int (*hf)(T x);
		List<T> *ht;
};
template<class T>
openhashtable<T>::openhashtable(int nbuckets,int hashf(T x)):size(nbuckets),hf(hashf),ht(new List<T>[size])
{}
template<class T>
void openhashtable<T>::clear()
{
	for(int i=0;i<size;i++)
		ht[i].clearlist();
}
template<class T>
bool openhashtable<T>::member(T &x)
{
	int i=int(hf(x)%size);
	if(ht[i].Locate(x))return true;
	else return false;
}
template<class T>
openhashtable<T> &openhashtable<T>::insert(T x)
{
	if(!member(x)){
	int i=int(hf(x)%size);
	if(i>key)key=i;
	ht[i]=ht[i].insert(0,x);
	}
	return *this;
}
template<class T>
openhashtable<T> &openhashtable<T>::Delete(T &x)
{
	T y;
	int i=int(hf(x)%size);
	if(int k=ht[i].Locate(x))ht[i]=ht[i].Delete(k,y);
	return *this;
}
template<class T>
void openhashtable<T>::output(int key)
{
	for(int i=0;i<=key;i++)
		ht[i].output();
}

void main()
{
	start=clock();
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	int i=0,j=0;
    openhashtable<String> bb(101,hashf);
	int x;
    do
	{
		String aa;
		x=aa.readstring(in);
		if(x==-1)break;
		bb.insert(aa);
	}while(1);
	
	bb.output(key);
	finish=clock();
	cout<<finish-start;
}