Требуется руководство по реализации двоичного дерева поиска в Objective-C

У меня есть частичная реализация двоичного дерева, которое не работает должным образом. Я считаю, что мне не хватает фундаментальных знаний об управлении структурной памятью в objective-c, но я не уверен, что это такое (кроме malloc). Когда я пытаюсь создать новый узел дерева на основе структуры, я получаю

Thread 1: EXC_BAD_ACCESS (code=1, address=0x0)

что привело меня к мысли, что я не создавал ячейку памяти для этого указателя на структуру. Как правильно это сделать в Objective-C? (Код ниже)

Спасибо, что нашли время ответить. Код кажется правильным с логической точки зрения, поэтому не уверен, в чем проблема.

РЕДАКТИРОВАТЬ Я изменил исходный код на основе ответа @trungduc. Но теперь я получаю переполнение стека в методе printDescription. проблема:

Thread 1: EXC_BAD_ACCESS (code=2, address=0x7ffeef3fffe8) // on line [self printDescription:root.left];

PS. Я видел этот вопрос, но не помогло. Я также видел это репо, но я не уверен, что доволен некоторыми деталями реализации, поэтому в итоге я не следил за ним. Кто-нибудь знает какие-нибудь хорошие руководства / учебники о том, как создавать деревья и графики в Objective-C?

Main.m

#import <Foundation/Foundation.h>

// BSTNode is an Objective-C class
@interface BSTNode : NSObject

@property (nonatomic, assign) int data;
@property (nonatomic, strong) BSTNode *left;
@property (nonatomic, strong) BSTNode *right;

@end

@implementation BSTNode

@end

@interface BST: NSObject

- (BSTNode *)insertNode:(BSTNode *)root withData:(int)data;
- (void)printDescription:(BSTNode *)root;

@end

@implementation BST

- (BSTNode *)initializeTreeNode {
    // By default, |data| is 0, |left| is nil, |right| is nil
    return [[BSTNode alloc] init];
}

- (BSTNode *)insertNode:(BSTNode *)root withData:(int)data {
    if (!root) {
        root = [self initializeTreeNode];
        root.data = data;
    } else if (root.data >= data) {
        root.left = [self insertNode:root.left withData:data];
    } else {
        root.right = [self insertNode:root.right withData:data];
    }

    return root;
}

- (void)printDescription:(BSTNode *)root {
    // in order left - root - right
    [self printDescription:root.left];
    NSLog(@"%d",root.data);
    [self printDescription:root.right];
}

@end

и внутри основного метода:

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

        BST *bst = [[BST alloc] init];;
        BSTNode *root = [[BSTNode alloc]init];
        [bst insertNode:root withData:20];
        [bst insertNode:root withData:15];
        [bst insertNode:root withData:25];
        [bst printDescription:root];
   }
    return 0;
}

Я бы не стал использовать структуру. Используйте класс; в конце концов, это Цель-C

Paulw11 03.08.2018 12:40

malloc (sizeof (BSTNode)) для нового узла

vivekDas 03.08.2018 12:42

Спасибо за ответ, хотя ваш ответ конкретно решает мою проблему с памятью. В итоге я выбрал более объектно-ориентированный подход, описанный ниже.

Matt 03.08.2018 18:14
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
3
130
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы получили сбой, потому что вы позвонили node->data, а node - это NULL.

В этом случае я предлагаю определить BSTNode как класс Objective-C. Вы можете попробовать мой код ниже.

// BSTNode is an Objective-C class
@interface BSTNode : NSObject

@property (nonatomic, assign) int data;
@property (nonatomic, strong) BSTNode *left;
@property (nonatomic, strong) BSTNode *right;

@end

@implementation BSTNode

@end

@interface BST: NSObject

- (BSTNode *)insertNode:(BSTNode *)root withData:(int)data;
- (void)printDescription:(BSTNode *)root;

@end

@implementation BST

- (BSTNode *)initializeTreeNode {
  // By default, |data| is 0, |left| is nil, |right| is nil
  return [[BSTNode alloc] init];
}

- (BSTNode *)insertNode:(BSTNode *)root withData:(int)data {
  if (!root) {
    root = [self initializeTreeNode];
    root.data = data;
  } else if (root.data >= data) {
    root.left = [self insertNode:root.left withData:data];
  } else {
    root.right = [self insertNode:root.right withData:data];
  }

  return root;
}

- (void)printDescription:(BSTNode *)root {
  if (!root) {
      return;
  }

  // in order left - root - right
  [self printDescription:root.left];
  NSLog(@"%d",root.data);
  [self printDescription:root.right];
}

@end

Спасибо за ответ. Хотя ваш ответ ясен и легок для понимания, я получаю переполнение стека в описании печати [self printDescription:root.left];. Любая идея, почему это должно быть? Обновил вопрос.

Matt 03.08.2018 18:16

@Matt Я обновил printDescription, вы можете проверить и попробовать еще раз.

trungduc 03.08.2018 18:27

@Matt Взгляните на github.com/EvgenyKarkan/EKAlgorithms/tree/master/EKAlgorithm‌ s /…, если вам нужен хороший образец

trungduc 03.08.2018 18:30

Я действительно следил за этим. Хотя по большей части это было полезно, мне не понравилось, как он использовал NSComparisonResultselector для методов вставки и поиска для BST. Есть ли у вас какие-либо альтернативные предложения для примеров BST и Graph?

Matt 03.08.2018 18:33

Я проверил, но ничего, связанного с NSComparisonResult, в файле EKBTree.m не нашел.

trungduc 03.08.2018 19:37

checkout EKBSTree.m реализация EKBTree.m была в порядке.

Matt 03.08.2018 20:24

Другие вопросы по теме