2

У меня возникла проблема при перестановки в массиве.

Есть входной массив категорий {1, 2.1, 3, 4.1, 5.3}, 1 и 3 - это родительские категории, а 2.1, 4.1, 5.3 - соответственно, дочерние категории.

Нужно сделать перестановку, чтобы исходный массив выглядел как {1, 2.1, 4.1, 3, 5.3} независимо от количества родительских категорий и дочерних.

7
  • На каком из перечисленных языков?
    – br3t
    24 янв 2017 в 22:36
  • На любом из них
    – Nicholas
    24 янв 2017 в 22:37
  • [5.1, 4, 3.2, 2, 1.1, 1].sort() годится?
    – br3t
    24 янв 2017 в 22:37
  • А какого типа данные у вас? Строки? Классы? Действительные, упаси боже, числа?
    – VladD
    24 янв 2017 в 22:41
  • [{id: 1, name: parent}, {id:2, name: child, parent: 1}, {id:3, name: parent 2}, {id:4, name: child 2, parent: 1}, {id:5, name: child 3, parent: 3}] - Вот например, как выглядит массив. Нужно чтобы дочерние категории разместились под своей родительской категории.
    – Nicholas
    24 янв 2017 в 22:46

1 ответ 1

4

Вам по сути нужна разновидность топологической сортировки.

Воспользуемся стандартным методом слияния списков. Я пишу на C#, в нём LinkedList не умеет сливаться, так что я написал свой велосипед.

Вспомогательные классы:

class LinkedNode<T>
{
    public T Entry;
    public LinkedNode<T> Next;
}

class MergeableLinkedList<T>
{
    public LinkedNode<T> First, Last;

    public MergeableLinkedList(T head)
    {
        First = new LinkedNode<T>() { Entry = head };
        Last = First;
    }

    public void Merge(MergeableLinkedList<T> other) // other is destroyed
    {
        Last.Next = other.First;
        Last = other.Last;
    }
}

Ваша структура данных:

class Entry
{
    public int id;
    public int? parent;
}

Данные:

var data = new Entry[]
{
    new Entry() { id = 1 },
    new Entry() { id = 2, parent = 1 },
    new Entry() { id = 3 },
    new Entry() { id = 4, parent = 1 },
    new Entry() { id = 5, parent = 3 },
    new Entry() { id = 6, parent = 4 }
};

Сортировка:

// создаём списки
var lists = new Dictionary<int, MergeableLinkedList<Entry>>();
foreach (var d in data)
    lists[d.id] = new MergeableLinkedList<Entry>(d);

// сливаем их
foreach (var d in data)
{
    // если есть предок...
    if (d.parent != null)
    {
        var parentId = d.parent.Value;
        // свой список подцепляем в конец списка предка
        lists[parentId].Merge(lists[d.id]);
        lists[d.id] = lists[parentId];
    }
}

// и перепаковываем всё в новый массив
var newData = new Entry[data.Length];
var newDataIndex = 0;
foreach (var d in data)
{
    if (d.parent == null)
    {
        for (var curr = lists[d.id].First; curr != null; curr = curr.Next)
            newData[newDataIndex++] = curr.Entry;
    }
}

Вывод:

foreach (var d in newData)
{
    if (d.parent != null)
        Console.Write(d.parent + ".");
    Console.WriteLine(d.id);
}

Результат:

1
1.2
1.4
4.6
3
3.5

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.