Структура базы данных для древовидной структуры данных
Используйте fgets для чтения ввода в консоль:
int res = 2;
while (res == 2) {
char buf[100];
fgets(buf, sizeof(buf), stdin);
res = sscanf(buf, "%f %f", &real, &img);
if (res == 2)
c[i++] = real + img * I;
}
c[i++] = 1 + 0*I; // most significant coefficient is assumed to be 1
return i;
4 ответа
Вы упомянули наиболее часто используемую реализацию, а именно список смежности: https://blogs.msdn.microsoft.com/mvpawardprogram/2012/06/25/hierarchies-convert-adjacency-list-to-nested-sets
Существуют и другие модели, включая материализованный путь и вложенные наборы: http://communities.bmc.com/communities/docs/DOC-9902
Джо Селко написал книгу по этой теме, которая является хорошей справочной информацией с общей точки зрения SQL (она упоминается во вложенном установите ссылку на статью выше).
Кроме того, Ицик Бен-Ганн имеет хороший обзор наиболее распространенных опций в своей книге «Внутри Microsoft SQL Server 2005: запросы T-SQL».
Основные моменты, которые следует учитывать при выборе модели:
1) Частота изменения структуры - как часто изменяется фактическая структура дерева. Некоторые модели обеспечивают лучшие характеристики обновления структуры. Однако важно отделить изменения структуры от других изменений данных. Например, вы можете смоделировать организационную структуру компании. Некоторые люди будут моделировать это как список смежности, используя идентификатор сотрудника, чтобы связать сотрудника с его руководителем. Обычно это неоптимальный подход. Подход, который часто работает лучше, - это моделирование организационной структуры отдельно от самих сотрудников и сохранение сотрудника как атрибута структуры. Таким образом, когда сотрудник покидает компанию, сама организационная структура не нуждается в изменениях, только связь с ушедшим сотрудником.
2) Является ли дерево тяжелым для записи или чтения - некоторые структуры работают очень хорошо. хорошо при чтении структуры, но несут дополнительные накладные расходы при записи в структуру.
3) Какие типы информации вам нужно получить от структуры - некоторые структуры превосходно предоставляют определенные виды информации о структуре. Примеры включают поиск узла и всех его дочерних узлов, поиск узла и всех его родителей, определение количества дочерних узлов, удовлетворяющих определенным условиям, и т. Д.
Для меня имеет смысл иметь таблицу с внешним ключом для самой себя.
Затем вы можете использовать обычное табличное выражение в SQL или предыдущий оператор подключения в Oracle для построения вашего дерева.
Взгляните на Управление иерархическими данными в MySQL . В нем обсуждаются два подхода к хранению и управлению иерархическими (древовидными) данными в реляционной базе данных.
Первый подход - это модель списка смежности, которую вы, по сути, описываете: наличие внешнего ключа, который ссылается на саму таблицу. Хотя этот подход прост, он может быть очень неэффективным для определенных запросов, таких как построение всего дерева.
Второй подход, обсуждаемый в статье, - это модель вложенных множеств. Этот подход гораздо более эффективен и гибок. См. Статью для подробного объяснения и примеров запросов.
Я использовал следующую реализацию на SQL SERVER 2005. Проверьте здесь