键树
2013年10月12日
⁄ 综合
⁄ 共 4191字 ⁄ 字号
小 中 大
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/**//* ********************************************
* Digital Search Tree implementation 1:
*
* Double Link Tree
*
* Author: boriswang@gdnt.com.cn
* Modification History
* 2007-09-17 Inital Creation
* 2007-09-18 Add function DLTreeAddNode
* 2007-09-19 Add function DLTreeSearch (Testing pass)
* 2007-09-26 Add function DLTreeDeletePair
*
***********************************************/
/**//* Define the Key type */
#define MAX_KEY_LEN 32
#define END_SYMBOL '$'
typedef enum ...{false,true}bool;
/**//* Define the node type */
typedef enum...{LEAF,BRANCH} NodeType;
/**//* Define the DLTree node structure */
typedef struct _DLNode
...{
char symbol;
struct _DLNode* prev; /**//* point to the prev symbol node */
struct _DLNode * next; /**//* point to next brother */
NodeType type;
union...{
void* record;
struct _DLNode * first; /**//* point to the first child */
};
}DLNode;
typedef struct
...{
DLNode root;
int size;
}DLTree;
bool DLTreeInit(DLTree* tree)
...{
DLNode* root = NULL;
if(!tree) return false;
root = &(tree->root);
root->first = NULL;
root->next = NULL;
root->prev = NULL;
root->type= BRANCH;
root->symbol = END_SYMBOL;
tree->size = 0;
return true;
}
DLNode* DLTreeAddNode(DLTree* tree,DLNode* node, char ch, void* record)
...{
DLNode* newNode = NULL;
DLNode* cursor = NULL;
DLNode* anchor = NULL;
if(NULL == node) return NULL;
if(node->type == BRANCH)
...{
newNode = (DLNode*)malloc(sizeof(DLNode));
if(NULL == newNode) return NULL;
newNode->symbol = ch;
newNode->next = NULL;
newNode->prev = NULL;
tree->size++;
if(ch == END_SYMBOL)
...{
newNode->type = LEAF;
newNode->record = record;
}else
...{
newNode->type = BRANCH;
newNode->first = NULL;
}
/**//* add the new node to the end of node->first->next...next ->null */
if(node->first)
...{
cursor = node->first;
while(cursor)
...{
if(cursor->symbol == ch)
...{
/**//* debug log */
printf("----------- duplicate %c, don't add new node. ",ch);
free(newNode);
tree->size--;
return cursor;
}
anchor = cursor;
cursor = cursor->next;
}
/**//* anchor is the last one */
anchor->next = newNode;
newNode->prev = anchor;
/**//* debug log */
printf("Add %c at right of %c. ",
ch, anchor->symbol);
}else
...{
/**//* add the new node as its first */
node->first = newNode;
newNode->prev = node;
/**//* debug log */
printf("Add %c at under of %c. ",
ch, node->symbol);
}
}else if(node->type == LEAF)
...{
return NULL;
}
return newNode;
}
DLNode* DLTreeSmartSearch(DLTree* tree, char* str, int len)
...{
DLNode* p = tree->root.first;
int i=0;
while(p && i<len)
![]()