aboutsummaryrefslogblamecommitdiff
path: root/6.4/tree.c
blob: 7f121628b08000fa02519906f6254861e80fe36d (plain) (tree) 
3f761f6





















































































1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85





















































































                                                                         
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <error.h>
#include <errno.h>
#include "tree.h"

struct tnode *talloc(void);
void tlswap(struct tnode *l[], int p1, int p2);

struct tnode *addtree(struct tnode *p, char *w)
{
	int cond;

	if (p == NULL) {
		p = talloc();
		p->word = strdup(w);
		p->count = 1;
		p->left = p->right = NULL;
	} else if (!(cond = strcasecmp(w, p->word))) {
		p->count++;
	} else if (cond < 0) {
		p->left = addtree(p->left, w);
	} else if (cond > 0) {
		p->right = addtree(p->right, w);
	}

	return p;
}

int tlstore(struct tnode *p, struct tnode *l[], int lim)
{
	static int nt;

	if (p != NULL && nt < lim) {
		tlstore(p->left, l, lim);
		l[nt++] = p;
		tlstore(p->right, l, lim);
	}

	return nt;
}

void tlsort(struct tnode *l[], int lim)
{
	int gap, i, j;

	for (gap = lim/2; gap > 0; gap /= 2)
		for (i = gap; i < lim; ++i)
			for (j = i - gap; j >= 0 &&
				l[j]->count >= l[j+gap]->count; j -= gap)
				tlswap(l, j, j + gap);
}

void tlswap(struct tnode *l[], int p1, int p2)
{
	struct tnode *temp;

	temp = l[p1];
	l[p1] = l[p2];
	l[p2] = temp;
}

void printtl(struct tnode *l[], int lim)
{
	int i;

	for (i = 0; i < lim; ++i)
		printf("%4d %s\n", l[i]->count, l[i]->word);
}

void tfree(struct tnode *p)
{
	if (p != NULL) {
		tfree(p->left);
		tfree(p->right);
		free(p->word);
		free(p);
	}
}

struct tnode *talloc(void)
{
	return (struct tnode *) malloc(sizeof(struct tnode));
}