Пытаясь выбрать правильную структуру данных

Question

Итак, я хочу сохранить всех актеров из спектакля в графике.Таким образом, из ввода мы будем читать так:

Пусть N будет количеством фильмов, которые мы читаем, для каждого фильма, который мы читаем: название фильма, на следующей строке будет номеромактеры (пусть это будет nr), теперь в следующих nr строках будет имя каждого актера.В фильме каждый актер «связан» с любым другим актером.

Что я сделал до сих пор:

Я построил двоичное дерево поиска на основе имени актера, и в каждом «узле» этого двоичного дерева поиска, которое я сохранил: идентификаторактер, все фильмы, в которых он играл, и его / ее имя.

Так было бы так:

typedef struct binaryTree
{
    int size;
    int id;
    int movieSize;
    int movieCapacity;
    char **movieName;
    char *actorName;
    struct binaryTree *left;
    struct binaryTree *right;
} *BinaryTree;

Теперь, используя это двоичное дерево поиска, я хочу найти каждый фильми для каждого актера в этом фильме я хочу подключить их объединенные идентификаторы в графе.

Теперь вот проблема: я сделал BST, но теперь, ища каждое название фильма, мне придется искатьдля каждого актера, так что это будет O(nr) для каждого поиска, так что это не очень помогло мне.Какой еще способ думать об этом, чтобы сделать инициализацию графа более простой и эффективной?

РЕДАКТИРОВАТЬ:

Для лучшей визуализации данных:

Movie1:      Movie2:       Movie3:    Movie5:
Actor1       Actor1        Actor2     Actor6
Actor5       Actor3        Actor4     Actor7
Actor3       Actor4        Actor5     Actor8

Фактический ввод, который будет читаться:

4
Movie1
3
Actor1
Actor5
Actor3
Movie2
3
Actor1
Actor3
Actor4
Movie3
3
Actor2
Actor4
Actor5
Movie4
3
Actor6
Actor7
Actor8

Это будет читаться в следующем порядке: Movie1 с Actor1, Actor5, Actor3, Movie2 с Actor1, Actor3, Actor4 и т. Д. (Как вы можете видетькогда вы читаете Actor1 во второй раз, новый узел не будет добавлен, но он добавит новый фильм в список фильмов Actor 1. Также вот фотография двоичного дерева на основе этих данных:

Я хочу, чтобы моя структура данных поддерживала быстрый доступ между идентификатором и именем актера, а также быструю сортировку данных. Именно поэтому я подумал, что BST будет подходящим и оттуда будет созданГрафик с идентификаторами. Вопрос в том, как мне на самом деле действовать после создания этого двоичного дерева поиска по имени каждого актера с построением графа или есть другой (лучший) способ хранения / свершенийКак это?

Вот фотография графика, который я хочу построить, где каждый номер узла - это число внутри имени актера (для упрощения):

Answer 1

Возможно, вы захотите представить график актеров с помощью Списка смежности (см. https://www.geeksforgeeks.org/graph-and-its-representations/).

Для каждого актера A , вы создадите массив актеров, которые A связан с.

struct Actor {
  int   id;
  char  *name;
}

struct AdjacencyRow {
  struct Actor  *actor;
  unsigned      connected_actors_count;
  struct Actor  **connected_actors;
}

struct AdjacencyList {
  unsigned             row_count;
  struct AdjacencyRow  *rows;
}

Во время синтаксического анализа ввода каждый раз, когда вы встречаете нового Актера, вы выделяете ему новый struct Actor и выделяете новый struct AdjacencyRow в struct AdjacencyList дляего.

Затем в строке этого нового Актера вы добавляете указатели на других Актеров, играющих в том же Фильме (вам нужно запомнить их id для обработанного в данный момент Фильма), и вы добавляете указатели наэтот актер ко всем строкам других актеров.

Когда вы встречаете уже известного актера, вы просто добавляете указатели (хотя следите за дубликатами).

Это дает вам O(n log n) сложность(для n = количество актеров на фильм), так как k операции должны выполняться для k -го актера, добавляемого.

---

Таким образомвы в конечном итоге со структурой, которая позволяет вам найти непосредственно связанных актеров вO(e) время, актеры, которые оба подключены к одному и тому же актеру за O(e^2) время и т. Д. (Где e = среднее количество соединений на одного актера).

---

Приведенный выше пример можно упроститьполностью избавившись от id и просто создав массив имен и массив массивов типа int (как AdjacencyList).