非诚勿扰广告时间

挺喜欢随风的，多大了？

我的代码是放弃版权的，谁都可以随便复制、分发、修改。唯一的要求是不要在不做任何修改的情况声称这段代码属于你。

但请注意silent_world的代码可有版权声明，不要随便复制哦。

有容没有兴趣参与么？

呵呵 我数据结构一直在徘徊，不过挺在意它的，有时间去搞搞看。

洗过澡了浑身清爽，开干，我是乙亥年的猪

[ 本帖最后由 随风飘荡 于 2012-8-5 22:21 编辑 ]

后生可畏。多交流代码，有助于你对理论的理解和应用能力的提高。

你属猪的？我大你这么多啊？OMG

前浪死在沙滩上，抓紧转行做项目管理

我妈把我当小孩子赶，这不你看我4点偷偷爬起来交作业了

void ternary_tree_delete(TERNARY_TREE * tree, char * string)
{
    int i, j, iStrlen;
    TERNARY_TREE *temp;

    if(ternary_tree_search(*tree,string) == 0) return;
    iStrlen = strlen(string);
    for(i=iStrlen; i>0; i--)
    {
        temp=tree;
        for(j=0; j<i-1; j++)
        {
            if( (*temp)->left != NULL && (*temp)->left->key == string[j] )
                temp = &((*temp)->left);
            if( (*temp)->right != NULL && (*temp)->right->key == string[j] )
                temp = &((*temp)->right);
            if( (*temp)->key != NULL && (*temp)->key == string[j] )
                temp = &((*temp)->mid);
        }
        if( (*temp)->left == NULL && (*temp)->mid == NULL && (*temp)->right == NULL )
        {       

            free(*temp);
            *temp = NULL;
        }
        else
        {
            if(i == iStrlen)
                (*temp)->value = 0;
            break;
        }
    }
}

这是测试结果，对于强度我不太自信，感觉有bug，请指教。
第一个想法是利用递归，可是想了半天感觉老鼠拉龟——无从下手。我不太熟悉递归，说真的我连汉诺塔问题都会弄的糊涂。
第二个是像历遍函数一样利用深度，但是感觉我没法跳出思维怪圈所以也放弃了
最后这个就是现在这个了。

aade <3>
ab <2>
abc <1>
hello boy <5>
hello world <4>
delete "ab"------------------------------------------------
aade <3>
abc <1>
hello boy <5>
hello world <4>
delete "aade"------------------------------------------------
abc <1>
hello boy <5>
hello world <4>
delete "abc"------------------------------------------------
hello boy <5>
hello world <4>
delete "hello boy"------------------------------------------------
hello world <4>
delete "hello world"------------------------------------------------
the value of "ab" is 0
按任意键继续...

这下能睡个安稳了

[ 本帖最后由 随风飘荡 于 2012-8-6 04:15 编辑 ]

不对

说来话长，现在我得去上班，中午回来慢慢解释给你，删除操作远比添加操作复杂。你也可以自己再好好想想。

不要着急，我们可以慢慢讨论这个问题，晚上还是尽量按时睡觉的好。

hehe，首先，非常感谢beyondyf对代码的评价。可能你不是做计算机软件的，对代码的看法，咱俩还有些不同的地方。
为什么要用到这个头指针呢？
1、这个embed_xuel做嵌入式，应该比较清楚，早期的平台，好些是不支持全局变量的，如早期brew，飞利浦。
   在开发过程中，基本采用设计模式中的单一模式，即再添加两个接口global_getXXXmodule() 和 global_setXXXmodule()；
2、代码复用原则。在软件工程中，有一项是代码封装性和复用性。作为对外模块，需保证操作的内闭性。
   大家可以看看一些软件工程的书籍。呵呵。
3、void指针的设置。如果作为一个公共使用模块，和代码封装有关。也保证代码在不同平台中，移植的方便性。
4、tstrie_destroy（）是采用树的深度优先释放，如果对树的线索化比较熟悉，应能明白。
   头指针的释放还存在问题，并且有crash现象，改为如下即可。
void tstrie_destroy(void *root)
{
     TERNARY_TRIE *me = (TERNARY_TRIE *)root;
     TERNARY_TRIE *preNode = 0, *curNode = 0;

     preNode = curNode = me->child_trie[TERNARY_MIDDLE];

     while(curNode)
     {
          while(curNode->child_trie[TERNARY_LEFT])curNode = curNode->child_trie[TERNARY_LEFT];
     
          if(curNode->child_trie[TERNARY_MIDDLE])
               curNode = curNode->child_trie[TERNARY_MIDDLE];
          else if(curNode->child_trie[TERNARY_RIGHT])
               curNode = curNode->child_trie[TERNARY_RIGHT];
          else
          {
               preNode = curNode->parent;

               if(preNode)
               {
                    if(preNode->child_trie[TERNARY_LEFT] == curNode)
                         preNode->child_trie[TERNARY_LEFT] = 0;
                    else if(preNode->child_trie[TERNARY_MIDDLE] == curNode)
                         preNode->child_trie[TERNARY_MIDDLE] = 0;
                    else if(preNode->child_trie[TERNARY_RIGHT] == curNode)
                         preNode->child_trie[TERNARY_RIGHT] = 0;
               }

               TSTRIE_DELNODE(curNode);

               curNode = preNode;
          }
     }
}

关于内存释放，建议大家做这么一个事情，对malloc和free再封装一层，添加一些地址打印语句，就可以看出来内存释放的问题了。
呵呵，偶最近忙得一塌糊涂，实在没有时间测试。

代码本身也还存在一些bug，多谢beyondyf指出。

非常感谢各位对代码关注。呵呵，代码也没有什么版权的问题。
偶只是开发习惯而已，大家可以随意操作



[ 本帖最后由 silent_world 于 2012-8-6 13:25 编辑 ]

这样的三叉树 经过多次插入字符串后 一个结点对应于一个唯一的字符 但是这个唯一字符（结点）可以映射到
多个字符串（即为多个字符串一部分） 所以要想删除一个字符串而不影响其他的字符串 就必须先判断这个结点是否曾经被重复插入相同字符
并记录 重复次数count_insert_repeat.
如果一个字符串在树中，先将字符串末结点的value值置零。
如果此字符串一结点的count_insert_repeat > 1 不删除这个结点 但是把他的值减一
反之count_insert_repeat == 1 直接删除此结点 并且如果此结点还有子树 就用一个办法把删除此结点后散乱的
子树结合到原树上 貌似实现起来很复杂啊

不知道我说的对不对 很多地方迷迷糊糊地。


[ 本帖最后由 有容就大 于 2012-8-6 11:34 编辑 ]