苗火 Nicholas

[Data structures]Digital search tree - Trie tree

2019-7-16 萧 写技术

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define MAX_LEN	8

typedef struct _TrieTree{
	int kind; // 0-leaf; 1-branch
	union{
		struct {char keys[MAX_LEN]; char *infoptr;} leaf; 
		struct {struct _TrieTree *ptr[27]; int num;} branch;
	};
}TrieTree;

char *SearchTrie(TrieTree *T, char *keys)
{
	TrieTree *p = T;
	int i=0;
	int c;
	int n = strlen(keys);
	while(p && p->kind == 1 && i<n){
		c = keys[i++] - 'a' + 1;
		p = p->branch.ptr[c];	
	}	
	if(p && p->kind == 0 && strcmp(p->leaf.keys, keys) == 0){
		return p->leaf.infoptr;
	}else{
		return NULL;
	}
}

void InsertTrie(TrieTree **T, char *keys)
{
	TrieTree *p = *T;
	TrieTree *q = NULL;
	int i=0;
	int j;
	int n = strlen(keys);
	int c;

	if(!p){
		q = malloc(sizeof(TrieTree));
		for(j=0; j<27; j++){
			q->branch.ptr[j] = NULL;
		}
		q->kind = 1;

		*T = q;
		p = *T;
	}

	for(i=0; i<n; i++){
		c = keys[i] - 'a' + 1;

		if(p->kind == 0){
			q = malloc(sizeof(TrieTree));
			for(j=0; j<27; j++){
				q->branch.ptr[j] = NULL;
			}
			q->kind = 1;

			*q = *p;	
			p->kind = 1;
			p->branch.ptr[0] = q;
		}

		if(!p->branch.ptr[c]){
			q = malloc(sizeof(TrieTree));
			for(j=0; j<27; j++){
				q->branch.ptr[j] = NULL;
			}
			if(i==n-1){
				q->kind = 0;
				strcpy(q->leaf.keys, keys);
				q->leaf.infoptr = keys;
			}else{
				q->kind = 1;
			}

			p->branch.ptr[c] = q;	
		}

		p = p->branch.ptr[c];
	}
}

void main()
{
	char seq1[] = "aboutge"; 
	char seq2[] = "hello"; 
	char seq3[] = "world"; 
	char seq4[] = "again"; 
	char seq5[] = "help"; 
	int i;
	TrieTree *F;
	TrieTree *T = NULL;


	printf("log.anycle.com\n\n");
	printf("Original data:\n");
	printf("%s\n", seq1);
	printf("%s\n", seq2);
	printf("%s\n", seq3);
	printf("%s\n", seq4);
	printf("%s\n", seq5);

	printf("Insert trie tree:\n");
	InsertTrie(&T, seq1);
	InsertTrie(&T, seq2);
	InsertTrie(&T, seq3);
	InsertTrie(&T, seq4);
	InsertTrie(&T, seq5);

	printf("Print the tree:\n");
	printf("%s", (char *)SearchTrie(T, seq2) );
	printf("\n");
}

标签: Data Structures data_structures