имитация отношения многие ко многим с использованием структур C.

#c #data-structures

#c #структуры данных

Вопрос:

Это проблема интервью. Мы должны спроектировать базу данных сотрудников с базовыми полями — emp_id, emp_name.

Но нам также необходимо поддерживать иерархию. чтобы мы могли поддерживать такие запросы, как :

учитывая emp_id / emp_name, найдите менеджера отчетов.
перечислите всех сотрудников, подчиняющихся конкретному менеджеру.

Вопрос в том, как реализовать это отношение «многие ко многим», используя структуры данных в C. В SQL мы можем легко поддерживать это, используя отдельную таблицу, где у нас есть сопоставление emp_id сотрудника с emp_id его менеджера.

Я думал об использовании хэш-таблицы с цепочкой для представления того же самого.

Редактировать: у сотрудника может быть несколько менеджеров в том смысле, что у них разные менеджеры на разных уровнях иерархии. например, менеджер по отчетности, старший менеджер и т. Д.

1. Больше похоже на проблему «многие к одному»: много сотрудников одному менеджеру. И это легко решить: если у вас есть набор сотрудников, легко выполнить поиск по нему, чтобы найти всех, у кого есть конкретный менеджер.

2. так что это ориентированный граф, не так ли?

3. Ваши «множественные менеджеры» на самом деле не «многие ко многим», это просто иерархия. Вы получаете менеджера сотрудника, затем вы получаете его менеджера и так далее по дереву.

4. @JoachimPileborg, да, вы правы, отредактировал вопрос о том, почему я думаю, что это отношения «многие ко многим».

5. Вы можете использовать любую структуру данных, которая хранит пары (employee's emp_id, manager's emp_id) и позволяет выполнять поиск по любому полю. Обычно это означает, что вы поддерживаете две отдельные структуры поиска, по одной для каждого поля, по которому вы хотите выполнить поиск, в которых хранятся ваши пары по ссылке . Хорошая хэш-таблица с цепочкой.

Ответ №1:

Возможно, структура, подобная следующей?

 typedef struct NODE_S
   {
   /* Parent node (manager).  Many (employees) to one (manager) */
   struct NODE_S *parent; 

   /* Peer-level employees. */
   struct NODE_S *prev;    /* Previous peer employee */
   struct NODE_S *next;    /* Next peer employee */

   /* Employees who report to this (manager) node. :: One (manager) to many (employees) */
   struct NODE_S *head;    /* First reporting employee. */
   struct NODE_S *tail;    /* Last reporting employee. */

   /* Employee data. */
   unsigned int  id;
   char         *name;
   char         *title;
   } NODE_T;

Пример тестового кода для этой структуры можно найти здесь .

1. спасибо, что поделились этим. Единственная проблема, я думаю, будет заключаться в том, что каждая структура будет иметь указатели head и tail, хотя будет очень мало менеджеров и много сотрудников, так что это может привести к большой потере пространства IMO.

Ответ №2:

Это то, что я, наконец, использовал:

 typedef struct emp_data_s{
    char *name;
    char *designation;
    unsigned long salary;
} emp_data_t, *pemp_data_t;

typedef struct emp_s{
    unsigned int id;
    unsigned int manager;
    pemp_data_t data;
    struct emp_s *next;
    struct emp_s *firstchild;
    struct emp_s *nextchild;
} emp_t, *pemp_t;