苗火 Nicholas

[Data structures]Digital search tree - Double link tree

2019-7-15 萧 写技术

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

typedef struct _DLTree{
	char symbol; // key
	struct _DLTree *next;
	int kind; // 0-leaf; 1-branch
	union{
		char *infoptr; //Pointer to the data
		struct _DLTree *first;
	};
}DLTree;

void *SearchDLTree(DLTree *T, char *keys, DLTree **f, int *idx)
{
	int i = 0;
	DLTree *p = T->first;
	int n = strlen(keys);
	*f = T;
	*idx = i;
	while(p && i< n ){
		while(p && p->symbol != keys[i]){
			p = p->next;
		}
		if(p && i<n-1 ){
			*f = p;
			*idx = i+1;
			p = p->first;
		}
		i++;
	}

	if(!p){
		return NULL;
	}else{
		return p->infoptr;
	}
}

void InsertDLTree(DLTree *T, char *keys)
{
	DLTree *F;
	DLTree *p;
	int ret = 0;
	int i;
	int n = strlen(keys);

	while( !SearchDLTree(T, keys, &F, &i) ){
		p = (DLTree *)malloc(sizeof(DLTree));
		p->symbol = keys[i]; 
		p->next = NULL;
		if(i==n-1){
			p->kind = 0;
			p->infoptr = keys;
		}else{
			p->kind = 1;
			p->first = NULL;
		}
		if(!F->first){
			F->first = p;
		}else{
			F = F->first;
			while(F->next){
				F = F->next;
			}
			F->next = p;
		}
	}
}

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

	T.next = NULL;
	T.kind = 1;
	T.symbol = 0;
	T.first = NULL;

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

	printf("Insert double links tree:\n");
	InsertDLTree(&T, seq1);
	InsertDLTree(&T, seq2);
	InsertDLTree(&T, seq3);
	InsertDLTree(&T, seq4);
	InsertDLTree(&T, seq5);

	printf("Print the tree:\n");
	printf("%s", (char *)SearchDLTree(&T, seq2, &F, &i) );
	printf("\n");
}

标签: Data Structures data_structures