objective-c - 如何用Objective-C构造一个trie数据结构？

Question

尽管 Objective-C 是 C 的超集，但我想就如何使用 Objective-C 创建 trie 数据结构提供反馈。我已经开始编写接口(interface)代码，但需要一些帮助来理解如何添加 Trie 节点(例如集合项)来存储单词。

@interface Trie : NSMutableArray {
   Trie *child;
   BOOL final;
}

@property(nonatomic, retain)Trie *child;
@property(nonatomic, assign)BOOL final;

-(void)addWord:(NSString *)_word;

@end

Answer 1

我为您编写了一个快速实现，应该或多或少具有功能性，至少它可以作为一个起点。请注意，我去掉了数组子类。你通常不想子类化 NSArrays 并且在这里你可以避免一般的子类化。 See inheritance vs composition .

@interface Trie : NSObject

@property (nonatomic, strong) NSMutableArray *children;
@property (nonatomic, strong) NSString *key;
@property (nonatomic, readonly) BOOL isFinal;

- (void) addWord:(NSString *)word;
- (id) initWithKey:(NSString *)key;

@end

@implementation Trie

// designated initializer, initializes our array of children and sets the key
- (id) initWithKey:(NSString *)key
{
    if(self = [super init])
    {
        _key = key;
        _children = [NSMutableArray new];
    }
    return self;
}

- (void) addWord:(NSString *)word
{
    // no more characters left, this is our base case
    if(! word.length)
    {
       return;
    }

    Trie *childToUse;
    NSString *firstCharacter = [word substringToIndex:1];

    // look for an existing node to dive into
    for(Trie *child in _children)
    {
        if([child.key isEqualToString:firstCharacter])
        {
            childToUse = child;
            break;
        }
    }

    // create a new node if there isn't one
    if(! childToUse)
    {
        childToUse = [[Trie alloc] initWithKey:firstCharacter];
        [_children addObject:childToUse];
    }

    // we now have a node, add the rest of the word into our trie recursively
    [childToUse addWord:[word substringFromIndex:1]];
}

// no actual ivar is stored for this property, its value is returned dynamically by looking at the array count, which can change when more elements are added
- (BOOL) isFinal
{
    if(! _children.count)
    {
        return YES;
    }
    else
    {
        return NO;
    }
}

@end

只需通过执行 [[Trie alloc] initWithKey:@""] 之类的操作来初始化您的根节点。