• Дата реєстрації: 08.06.2012
  • Повідомлень: 2 031
    • Репутація: 743

Тема: Допоможіть із алгоритмом побудови дерева

От уже яку годину сиджу, і ніяк не можу придумати нормальний і дієвий алгоритм для побудови дерева з даних.
Отож. Є в мене два масиви:
Масив із індексами, та масив із іменами тек.
Масив із індексами

Array
(
    [0] => 004
    [1] => 004
    [2] => 004
    [3] => 021
    [4] => 021
    [5] => 014
    [6] => 030
    [7] => 039
    [8] => 049
    [9] => 056
)

Масив із назвами

Array
(
    [0] => Розділ 1
    [1] => Параграф 1
    [2] => Завадання 1
    [3] => Завадання 2
    [4] => Параграф 2
    [5] => Завадання 3
    [6] => Завадання 4
    [7] => Завадання 5
    [8] => Завадання 6
    [9] => Завадання 7

Що з того має вийти, та яка суть цього.
З цього має вийти таке собі дерево каталогів.
Зрозуміло, що "Розділ 1" - головна тека(але ці ж розділи мають міститися у одній єдиній теці, цих розділів може бути багато)
В теці "Розділ 1" має бути тека "Параграф 1" та "Параграф 2", а теці "Параграф 1" теки "Завадання 1" та "Завадання 2".(Ща має бути у теці "Параграф 2" думаю не варто пояснювати).
Тепер щодо індексів. Для чого вони взагалі. Тут вони якраз і мають допомогти мені зрозуміти, де має створюватися розділ, де параграф а де просто тека із завданнями.

Ото, візьмемо до прикладу перші три елементи масиву з індексами, бачимо що всі три значення співпадають між собою, тобто якщо підряд іде три однакових значення, це означає, що має створитися розділ, якщо два підряд однакових значення - параграф, і відповідно якщо тільки якесь одне значення тека із завданнями.
Отож, знаю завдання досить складне, але може хтось має якісь думки щодо такого ?

UPD: тобто результатом має бути список таких тек:

/Розділ1/Параграф1/Завдання1/
/Розділ1/Параграф1/Завдання2/
/Розділ1/Параграф1/Завдання3/
/Розділ1/Параграф1/Завдання4/
/Розділ1/Параграф1/Завдання5/

2 Відповідь від User 298

  • User 298
  • Гість

Re: Допоможіть із алгоритмом побудови дерева

Трохи зустрічних грабель питань:

1. Яка максимальна кількість таких груп кожного типу? Скільки для того розрядів знадобиться?
2. Як щодо параграфа без завдань або розділа без параграфів?
3. Що заважає збудувати табличку у БД з полями Id та MasterId та уможливити цим дерево N-вимірної вкладності?
4. А що взагалі куримо?) Як та з якими інструментами той алгоритм має бути реалізований?

  • Дата реєстрації: 08.06.2012
  • Повідомлень: 2 031
    • Репутація: 743

Re: Допоможіть із алгоритмом побудови дерева

Bartash написав:

Трохи зустрічних грабель питань:

1. Яка максимальна кількість таких груп кожного типу? Скільки для того розрядів знадобиться?
2. Як щодо параграфа без завдань або розділа без параграфів?
3. Що заважає збудувати табличку у БД з полями Id та MasterId та уможливити цим дерево N-вимірної вкладності?
4. А що взагалі куримо?) Як та з якими інструментами той алгоритм має бути реалізований?

1. Максимум 50 кожного типу
2. Така ситуація виключена, оскільки я у 99.9% випадків, отримую потрібні масиви з правильно сформованою інформацією.
3. Проблема у тому, що мені якраз з вхідних даних(двох масивів) потрібно визначити де розділ де параграф, а де завдання, тому щоб вставити в БД всеодно потрібно зробити аналіз для того щоб знати куди, що запихати.
4. Та мені впринципі потрібна лише сама ідея алгоритму, а далі вже буду застосовувати або на bash або на php.

4 Відповідь від koala Востаннє редагувалося koala (20.12.2013 12:52:41)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Допоможіть із алгоритмом побудови дерева

Ну власне так і робити, як ви сказали. Псевдокодом:

count = 0;
last = 2;//максимальний рівень
for( i = 0; i < index.size; i++ )
{
  level = last;
  for( j = i + 1;( j < index.size ) && ( names[ i ] == names[ j ] ); j++ )
  {
    --level;
  }
  result[ count ][ level ] = names[ i ];
  if( level == last )//якщо не було повторів 
  {
    print( result[ count++ ][ 0 .. last] );
  }
  else //якщо були повтори - копіюємо початок з попереднього
  {
    result[ count ][ 0 .. level - 1 ] = result[ count - 1 ][ 0 .. level - 1 ];
  }
}

І порада - об'єднайте масиви в масив структур, щоб індекс з назвою були разом.

Подякували: Пам'ять не може бути READ1

koala вебсайт

5 Відповідь від Torbins Востаннє редагувалося Torbins (20.12.2013 12:24:10)

  • Torbins
  • Torbins
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 07.05.2012
  • Повідомлень: 3 082
    • Репутація: 2280

Re: Допоможіть із алгоритмом побудови дерева

Hanter
А не можна індекси якось іншим чином формувати? На зразок такого:

    Array
    (
    [0] => 001
    [1] => 002
    [2] => 003
    [3] => 003
    [4] => 002
    [5] => 003
//...
    )

Або навіть так:

    Array
    (
    [0] => 1 * 10000 + 1
    [1] => 2 * 10000 + 2
    [2] => 3 * 10000 + 3
    [3] => 3 * 10000 + 4
    [4] => 2 * 10000 + 5
    [5] => 3 * 10000 + 6
//...
    )

2. Така ситуація виключена, оскільки я у 99.9% випадків, отримую потрібні масиви з правильно сформованою інформацією.

Цікава стаття на тему: Один на миллион - это в следующий вторник.

Подякували: Пам'ять не може бути READ1