trid_tree.c

完全由C语言实现的图的相关操作

#include "trid_tree.h" 
Status initNode(node* t)
{ //初始化结点
    t->num =-1; //表示出现在数组中的位置，-1表示没有出现过
    memset(t->child,0,sizeof(t->child));
    return OK;
}

Status init_trid_tree(trid_tree* T)
{ // 对字母树进行初始化
    T->vexnum =0;
    T->root = (node*) malloc (sizeof(node));
    initNode(T->root);  
    return OK;    
} 

 int insert(trid_tree* T,char* word)
 { //初始条件：字母树T存在，要插入的字符串存在
  //操作结果：判断word是否已经在T中，在返回出现的位置，不在T中插入word，且返回出现的位置
   node* r = T->root;
  int xiabiao; //下标
  while(r && *word)
  {
    xiabiao = *word-'a';
   if(r->child[xiabiao]==NULL)
   { 
     r->child[xiabiao] = (node*) malloc(sizeof(node));
     initNode((r->child[xiabiao]));
   }
   r=r->child[xiabiao];
   ++word;
  }
  if(r->num == -1)
   r->num = T->vexnum++; 
  return r->num ;    
       
 } 
 
 int delete_node(trid_tree* T,char* word)
{//初始条件：存在一棵字母树的根是t,和要删除的单词word
//操作结果：结点内存没有释放，就是把num值改为-1
    node*  r= T->root ;
    int xiabiao; //下标
    while(r&&*word)
    {
        xiabiao = *word-'a';
      if(r->child[xiabiao]==NULL)
     { 
        return -1;
     }
      r=r->child[xiabiao];
      ++word;
    }
    r->num = -1;
    return 0;
}

void adjust_num(node* t,int xiabiao)
{//初始条件：存在一棵字母树的根是T，和一个整数为xiabiao
//操作结果：把树t中所有t的num值大于xiabiao的，都分别减1 
   int i; 
   if(t!=NULL)
   {
     for( i=0;i<26;i++)  
       if(t->child[i]!=NULL)
        adjust_num(t->child[i],xiabiao);
     if(t->num >xiabiao) t->num--;    
   }  
}

int find(trid_tree* T,char* word)
{//初始条件：字母树T存在，要查找的字符串存在
//操作结果：判断word是否已经在T中，是返回在的位置，不在返回-1
    node*  r= T->root ;
    int xiabiao; //下标
    while(r&&*word)
    {
        xiabiao = *word-'a';
      if(r->child[xiabiao]==NULL)
     { 
        return -1;
     }
      r=r->child[xiabiao];
      ++word;
    }
    return r->num;
}

void Traverse(node* t)
{//初始条件：存在一棵字母树的根是t
//操作结果：深度优先遍历整棵字母树，输入num的值
   int i; 
    if(t!=NULL)
    {
      for(i=0;i<26;i++)
       if(t->child[i]!=NULL)
        Traverse(t->child[i]);
      printf("%d ",t->num);
    }
}
 
int destoryTree(trid_tree* T)
{//初始条件：存在一棵字母树T，
//操作结果：销毁T这棵树
    delete_Tree(T->root);
    T->vexnum =-1;
    return OK;
}

void delete_Tree( node*  T)
{
 //初始条件：存在一棵字母树的根是T
//操作结果：销毁了以T为根的那棵字母树
 int i; 
 if(T!=NULL)
 {
   for(i=0;i<26;i++)
   if(T->child[i]!=NULL)
    delete_Tree(T->child[i]);
      free(T);
 }
  
}