#include <stdio.h>
#include <string.h>
#include <malloc.h>

typedef struct _node
{
	char str[31];
	int count;
	struct _node *left;
	struct _node *right;
}node, *node_ptr;

double k      = 0.0;
node_ptr root = NULL;

void InsertTree(node_ptr z)
{
	node_ptr y = NULL;
	node_ptr x = root;
	int n;

	while (x != NULL)
	{
		y = x;
		
		n = strcmp(z->str, x->str);
		if (n == 0)
		{
			break;
		}
		else
		if (n < 0)
		{
			x = x->left;
		}
		else
		{
			x = x->right;
		}
	}

	if (y == NULL)
	{
		root = z;
	}
	else
	{
		if (x != NULL && strcmp(x->str, y->str) == 0)
		{
			x->count++;
			free(z);
			z = NULL;
		}
		else
		if (strcmp(z->str, y->str) < 0)
		{
			y->left = z;
		}
		else
		{
			y->right = z;
		}
	}
}

void PrintTree(node_ptr root)
{
	if (root != NULL)
	{
		PrintTree(root->left);
		printf("%s %.4f\n", root->str, root->count*100/k);
		PrintTree(root->right);
	}
}

int main()
{
	char str[31];

	while (gets(str) != NULL)
	{
		k++;
		node_ptr z = (node_ptr)malloc(sizeof(node));
		z->count = 1;
		strcpy(z->str, str);
		z->right = NULL;
		z->left  = NULL;

		InsertTree(z);
	}

	PrintTree(root);
	return 0;
}

• Re:纪念下第一个2叉排序 (1402) 08300240056 2009-11-07 00:12:26
  • Re:纪念下第一个2叉排序 (3) 08300240056 2009-11-07 00:12:52