字典树（已完成遍历、插入、删除整颗树） - C语言论坛

已结贴√ 问题点数：100 回复次数：43

字典树（已完成遍历、插入、删除整颗树）

刚想到的，个人觉得挺好玩，只是会占用大量空间。
目前只完成了插入，关于打印和遍历，我还需要再想想。

嗯……手头没有编译器，有人来当小白鼠么？

测试的时候，请连续输入两个一模一样的单词，如果第二次输入的单词被打印出来，就可以说暂时成功。

源文件.cpp后缀通不过编译，所以记得确保源文件后缀为.c

09：58 06/04
    已经可以运行，但是怎么遍历好坑的样子，我还需要再想想。
10：08 06/04
    遍历已完成。
11:58 06/04
    发现BUG一枚，还未解决。（已解决）
12：36 06/04
    发现新的BUG，当一个单词逐一减少字母，例如jack,jac,ja,j的时候，会出现判断错误。（已解决）
19：36 06/04
    完成删除整颗树，但始终怀疑会造成内存泄漏，这感觉真不好。（同一文件循环10次读取插入、删除整颗树获得结果，并没有内存泄漏）

程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define T List
typedef struct T *T;
struct T{
    T ChList[ 26 ];
    char *Word;
    };

void
InsertList( T *Root, char *src );

void
Print( T Root );

void
DelList( T *Root );

int
main( void )
{
    T Root;
    char word[ 100 ];

    Root = NULL;    
         
    while( NULL != fgets( word, 100, stdin ) )
    {
        word[ strlen( word ) - 1 ] = '\0';
        InsertList( &Root, word );
    }

    Print( Root );
    DelList( &Root );
    
    return 0;
}


void
InsertList( T *Root, char *src ) //目前还是初级版本，所以不检查src是否是单词，同时也不检查是否含有非字母，所以测试的时候请输入全字母组成的单词。
{
    T new;
    T next;
    char *dst;
    
    dst = src;
    
    while( '\0' != *src )
    {
        while( NULL == ( next = *Root ) ) 
        {
            new = ( T )calloc( 1, sizeof( struct T ) );
            if( NULL == new )
                exit( EXIT_FAILURE );
            new->Word = NULL;
            *Root = new;
        }

        Root = &next->ChList[ tolower( *src ) - 'a' ] ;   
        src++;
    }

    if( NULL == ( *Root ) )
    {
        new = ( T )calloc( 1, sizeof( struct T ) );
        if( NULL == new )
            exit( EXIT_FAILURE );
        new->Word = strdup( dst );
        *Root = new;
    }
    else if( NULL == ( *Root )->Word )
        ( *Root )->Word = strdup( dst );
    else
        printf( "%s 在表中\n", ( *Root )->Word );
}

void
Print( T Root )
{
    int ix;

    if( NULL == Root )
        return;
    if( NULL != Root->Word )
        printf( "%s\n",Root->Word );
    for( ix = 0; 26 > ix; ++ix )
        Print( Root->ChList[ ix ] );
}


void
DelList( T *Root )
{
    int ix;

    if( NULL == *Root )
        return;
    for( ix = 0; 26 > ix; ++ix )
        DelList( &( *Root )->ChList[ ix ] );
    if( NULL != ( *Root )->Word )
    {
        free( ( *Root )->Word );
        ( *Root )->Word = NULL;
    }
    free( *Root );
    *Root = NULL;
}