1

我正在尝试构建一棵树来存储 USB 设备信息。我以为我会使用 NSMutableArray 和 NSMutableDictionary 来包含这些信息。我的问题是我从来没有学过软件工程——我边走边学——而且我对树理论一无所知。
我的树基于 USB 位置 ID，它有 8 个半字节长。据我了解，每个半字节代表树的一层（如果您明白我的意思）。我已经编写了一些测试代码，看看我是否可以正确地构建我的树 - 遗憾的是，我似乎做不到！

#import <Foundation/Foundation.h>

#define MAXCHILDREN 0xf

NSDictionary* AddItemToTree(NSDictionary* nodeEntry, unsigned int value, int depth)
{
    // Convert the value into a set of nibbles
    char *bytes = (char *)&value;
    char byte = bytes[depth];

    NSMutableDictionary* thisEntry = [[[NSMutableDictionary alloc] initWithDictionary:nodeEntry] autorelease];

    if (byte == 0)
    {
        [thisEntry setObject:[NSString stringWithFormat:@"%08x",value] forKey:@"Value"];
        [thisEntry setObject:[NSString stringWithFormat:@"%08x",byte] forKey:@"Byte"];
        [thisEntry setObject:[NSNumber numberWithInt:depth] forKey:@"Depth"];

        return thisEntry;
    }



    if(![[thisEntry allKeys]containsObject:@"ChildEntries"])
    {
        NSMutableArray* childArray = [[NSMutableArray alloc]init];
        NSMutableDictionary* newNode = [[NSMutableDictionary alloc] init];

        [childArray addObject:AddItemToTree(newNode,value,++depth)];

        [thisEntry setObject:[NSNumber numberWithInt:depth] forKey:@"Depth"];
        [thisEntry setObject:[NSString stringWithFormat:@"%08x",value] forKey:@"Value"];
        [thisEntry setObject:[NSString stringWithFormat:@"%08x",byte] forKey:@"Byte"];
        [thisEntry setObject:childArray forKey:@"ChildEntries"];


        [newNode release];
        [childArray release];

    }
    else
    {
        [[thisEntry objectForKey:@"ChildEntries"]addObject:AddItemToTree(thisEntry,value, ++depth)];

    }


    return thisEntry;
}

int main(int argc, char *argv[]) {
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];


    NSMutableDictionary* treenode=[[NSMutableDictionary alloc]init];

    char bytearray[4] = {0x0F, 0x0F, 0x02, 0x00};
    unsigned int *value = (unsigned int*)bytearray;
    char bytearray2[4] = {0x0F, 0x02, 0x00, 0x00};
    unsigned int *value2 = (unsigned int*)bytearray2;
    char bytearray3[4] = {0x0F, 0x02, 0x00, 0x00};
    unsigned int *value3 = (unsigned int*)bytearray3;


    [treenode setObject:[NSNumber numberWithInt:0] forKey:@"Depth"];
    [treenode setObject:[NSString stringWithFormat:@"%08x",*value] forKey:@"Value"];
    [treenode setObject:AddItemToTree(treenode,*value, 0) forKey:@"ChildEntries"];

//    [[treenode objectForKey:@"ChildEntries"]addObject:AddItemToTree(treenode,*value2, 0)];


    [treenode writeToFile:@"/Users/headbanger/Desktop/test.plist" atomically:YES];

    [pool release];
}

添加一个 USB 位置 ID 效果很好。添加第二个（通过取消注释 main 中的行）会导致 SIGABRT。我确信这非常简单，而且我犯了一个典型的新手错误。但是，这对我来说并不明显，您可以提供的任何帮助都将非常受欢迎。
我的树需要看起来像这样：

F-
 |--F-
 |   |--2
 |
 |--2

即使尝试添加第三个字节数组，这棵树也应该是真的。
如果您可以在不针对 USB 的情况下回答问题，那将是最有帮助的，因为我真的很想了解树木以及我做错了什么。也就是说，如果有一种快速简便的方法可以在 Objective-C 中为我构建一棵树，那么我很想听听。
所以请专家们，有人能告诉我我做错了什么吗？感谢您的时间。

4

1 回答 1

1

一个问题是您将字典设置为 ChildEntries 的类型：

[treenode setObject:AddItemToTree(treenode,*value, 0) forKey:@"ChildEntries"];

但在其他地方，您尝试将其用作 NSMutableArray（注意 addObject: 方法）：

[[thisEntry objectForKey:@"ChildEntries"]addObject:AddItemToTree(thisEntry,value, ++depth)];

要修复它，你可以做

[treenode setObject:[[NSMutableArray alloc] initWithObjects:AddItemToTree(treenode,*value, 0), nil]forKey:@"Children"];

但即使你的递归进展到 0x00 字节if (byte==0)，我认为，从精神上检查它，它会添加重复的孩子并产生一个非常深的树。

如果您没有收到警告您addObject使用 SIGABORT 的错误方法的消息，则说明您的环境有问题。

顺便说一句，很难阅读。像这样的线条

[treenode setObject:[[NSMutableArray alloc] initWithObjects:AddItemToTree(treenode,*value, 0), nil]forKey:@"Children"];

如果您编写以下代码，则更容易扫描并且不易出错：

NSString * const kChildren = @"Children";
// ...
NSMutableArray *children = [[NSMutableArray alloc] initWithObjects:AddItemToTree(treenode,*value, 0), nil];
[treenode setObject:children forKey:kChildren];

风格不是很客观-c-ish，您可以使用 NSUInteger 和 NSData 代替 unsigned int 和 char 数组。

您应该首先编写一个通用树，然后将其用于您的目的。这是我的树示例。它很丑，但它是我的。如您所见，这是常识。您可以设置条件，例如，每个节点有两个孩子，并且 left child < root < right child，然后您将获得一个具有更好的查找内容的属性的二叉搜索树。但我猜这会带你更多的代码。

#import <Foundation/Foundation.h>

typedef NS_ENUM(unsigned char, MyTreeVisitingOrder) {
    MyTreeOrderDepthFirst,
    MyTreeOrderValueFirst
};

#define Tree NSObject<MyTree>

@protocol MyTree
@property (nonatomic,strong) NSObject<NSCopying>* key;
@property (nonatomic,strong) NSObject *value;
@property (nonatomic,strong) NSMutableDictionary *children;
-(void) insertChild:(Tree*)node;
-(void) each:(void(^)(NSObject*))block order:(MyTreeVisitingOrder)order;
@end


@interface TreeImpl : NSObject <MyTree>
-(id) init __attribute__((unavailable("disabled")));
@end

@implementation TreeImpl

@synthesize key = _key;
@synthesize value = _value;
@synthesize children = _children;


-(id) initWithKey:(NSObject<NSCopying>*)key value:(NSObject*)value {
    self = [super init];
    if (self){
        _key = key;
        _value = value;
        _children = [NSMutableDictionary new];
    }
    return self;
}


-(void) insertChild:(Tree*)node {
    [_children setObject:node forKey:node.key];
}

-(void) each:(void(^)(NSObject*))block order:(MyTreeVisitingOrder)order {
    switch (order) {
        case MyTreeOrderDepthFirst:{
            if (_children) {
                for (id key in _children){
                    [[_children objectForKey:key] each:block order:order];
                }
            }
            block(_value);
            break;
        }
        case MyTreeOrderValueFirst:{
            block(_value);
            if (_children) {
                for (id key in _children){
                    [[_children objectForKey:key] each:block order:order];
                }
            }
            break;
        }
    }
}

@end


int main(int argc, char *argv[]) {
    @autoreleasepool {

        TreeImpl *a = [[TreeImpl alloc] initWithKey:@"A" value:@"A"];
        TreeImpl *b = [[TreeImpl alloc] initWithKey:@"B" value:@"B"];
        TreeImpl *c = [[TreeImpl alloc] initWithKey:@"C" value:@"C"];
        [a insertChild:b];
        [a insertChild:c];

        [a each:^(NSObject* value) {
            NSLog(@"> %@",value);
        } order:MyTreeOrderValueFirst];
        return EXIT_SUCCESS;
    }
}
于 2013-01-29T21:06:59.093 回答