统计单词出现次数--hash表，二叉树，标准库

我一直很喜欢用标准库，非常非常方便。但是有时候你根本不知道它为你做了什么，我喜欢知道自己写的程序每一步都干了什么！！！

//////////////////////////////////
/////////////////////////////////
//标准模板库
//////////////////////////////////
/*
#include <time.h>
#include <map>
#include <string>
#include <fstream>
#include <iostream>
using namespace std;

int main()
{
	double beginTime = clock();
	ifstream in("source.txt");
	map<string, int> M;
	map<string, int>::iterator j;
	string t;
	while( in >> t )
	{
		M[t]++;
	}
	for ( j = M.begin(); j != M.end(); j++)
	{
		cout << j->first << "   " << j->second << endl;
	}

	double endTime = clock();
	cout << "time: " << endTime -  beginTime << "ms " << endl;
	return 0;
}

*/

//////////////////////////////////
/////////////////////////////////
// 编程珠玑十五章，珍珠字符串
//用Hash表实现之
//////////////////////////////////
/*
#include <time.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NHASH 29989
#define MULT 31

typedef struct node *nodeptr;
typedef struct node
{
	char *word;
	int count;
	nodeptr next;
}node;

nodeptr bin[NHASH];

unsigned int hash( char *p)
{
	unsigned int h = 0;

	for( ; *p; p++)
	{
		h = MULT * h + *p;
	}
	return h % NHASH;
}
void incword( char *s)
{
	int h = hash( s );
	nodeptr p = NULL;
	for ( p = bin[h]; p != NULL; p = p->next)
	{
		if ( strcmp( s, p->word) == 0)
		{
			p->count ++;
			return;
		}
	}

	p = NULL;
	p = new node;
	if ( p == NULL)
	{
		return;
	}
	p->count = 1;
	p->word = new char[ strlen(s) + 1];
	strcpy( p->word, s);
	p->next = bin[h];
	bin[h] = p;
}
int main()
{

	double beginTime = clock();
	int i = 0;
	FILE *fp = NULL;
	fp = fopen("source.txt","r");
	if ( fp == NULL )
	{
		printf("文件打开错误");
		return 1;
	}
	//ifstream in("source.txt");
	for ( i = 0; i < NHASH; i++)
	{
		bin[i] = NULL;
	}
	char tempWord[100];

	while( fscanf(fp, "%s", tempWord) != EOF )
	{
		incword( tempWord );
	}

	nodeptr p = NULL;
	for ( i = 0; i < NHASH; i++)
	{
		p = NULL;
		for ( p = bin[i]; p != NULL; p = p->next)
		{
			//cout << p->word<< "  " << p->count << endl;
			printf("%s  %d\n", p->word, p->count);
		}
	}
	double endTime = clock();
	printf("time:%g ms", endTime - beginTime );
	return 0;
}
*/


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
typedef struct node *nodeptr;
typedef struct node
{
	char *word;
	int count;
	nodeptr lchild;
	nodeptr rchild;
}node;

nodeptr setUp( nodeptr root, char *s)
{
	if ( root == NULL )
	{
		root = (nodeptr)malloc( sizeof(node));
		root->word = (char *)malloc(strlen(s) + 1);
		strcpy( root->word, s);
		root ->lchild = NULL;
		root ->rchild = NULL;
		root->count = 1;
		return root;
	}
	int flag = strcmp( root->word, s);
	if( !flag) 
	{
		root ->count ++;
		return root;
	}
	else if ( flag < 0 )
	{
		root ->rchild = setUp( root->rchild, s);
	}
	else
	{
		root->lchild = setUp(root->lchild, s);
	}
	return root;
}

void Traverse( nodeptr root)
{
	if ( root != NULL)
	{
		if ( root->rchild != NULL)
		{
			Traverse(root->rchild);
		}
		printf("%s  %d\n", root->word, root->count);
		if ( root->lchild != NULL)
		{
			Traverse(root->lchild);
		}
	}
		return ;
	
}
int main()
{
	nodeptr root = NULL;
	double beginTime = clock();
	int i = 0;
	FILE *fp = NULL;
	fp = fopen("source.txt","r");
	if ( fp == NULL )
	{
		printf("文件打开错误");
		return 1;
	}
	char tempWord[100];

	while( fscanf(fp, "%s", tempWord) != EOF )
	{
		root = setUp(root, tempWord );
	}
	
	Traverse(root);
	double endTime = clock();
	printf("time:%g ms", endTime - beginTime );
	return 0;

}