Início / coding / Perguntas / 78579039
Accepted
Mark
Asked: 2024-06-05 14:10:02 +0800 CST

Classificando uma lista vinculada mantendo alguns elementos agrupados

  • 772

Eu tenho uma lista vinculada:

MyLinkedList::LinkedList<Event *> list;

de onde LinkedListvem desta biblioteca e Eventé esta estrutura:

typedef struct 
{
    TimeSpan time;
    int value;

    bool queued;
} Event;

de onde TimeSpanvem esta biblioteca. Após preencher a lista com alguns itens executo a seguinte função:

bool Events::Save()
{
    // order the elements by the time
    _listEvents.sort(compare);

    // open a file for writing    

    for (int i = 0; i < _listEvents.size(); i++)
    {
        Event *event = _listEvents.get(i);
        // write the item to the file
        writeEvent(file, *event);
    }

    file.close();
    return true;
}

a comparefunção é definida da seguinte forma:

int compare(Event *&ev1, Event *&ev2)
{
    if (ev1->time.hours() > ev2->time.hours()) return true;
    if (ev1->time.hours() < ev2->time.hours()) return false;
    return (ev1->time.minutes() > ev2->time.minutes());
}

Apenas ordena os elementos pelo seu tempo. Este código funciona bem.

Agora preciso lidar com o queuedsinalizador na estrutura. Aqui está um exemplo de dados de entrada:

Tempo Valor Enfileiradas
18:00 1 falso
xx:xx 2 verdadeiro
xx:xx 3 verdadeiro
10h30 4 falso
xx:xx 5 verdadeiro
08:15 6 falso
06:45 7 falso

Ao ordenar, os itens com o queuedsinalizador definido devem seguir o item anterior (com queued não definido), independentemente do seu valor de tempo (daí o valor xx:xxna tabela).

A saída esperada é:

Tempo Valor Enfileiradas
06:45 7 falso
08:15 6 falso
10h30 4 falso
xx:xx 5 verdadeiro
18:00 1 falso
xx:xx 2 verdadeiro
xx:xx 3 verdadeiro

Em outras palavras: if queuedis falseos elementos serão ordenados normalmente (por seu tempo), if is trueeles devem seguir o elemento anterior (como se estivessem "agrupados" juntos).

Como a comparefunção pode lidar apenas com dois itens e não tenho outras informações além do pedido inicial, como posso manter os queueditens com o item “pai”?

c++

1 respostas

  1. Best Answer

    Primeiro agrupe sua lista. No seu exemplo, [1, 2, 3, 4, 5, 6, 7]torna-se [[1, 2, 3], [4, 5], [6], [7]].

    Em seguida, classifique-os pelo carimbo de data/hora do primeiro elemento de cada grupo. [[1, 2, 3], [4, 5], [6], [7]]torna-se [[7], [6], [4, 5], [1, 2, 3]].

    Em seguida, nivele essa lista para obter [7, 6, 4, 5, 1, 2, 3].

    Usando std::vector, isso pode ser algo como:

    #include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>

struct Event {
    std::string time;
    int value;
    bool queued;
};

int main() {
    std::vector<Event> events {
        {"18:00", 1, false},
        {"xx:xx", 2, true},
        {"xx:xx", 3, true},
        {"10:30", 4, false},
        {"xx:xx", 5, true},
        {"08:15", 6, false},
        {"06:45", 7, false}
    };

    std::vector<std::vector<Event>> grouped;

    for (auto &e : events) {
        if (!e.queued) grouped.emplace_back();

        grouped.back().push_back(e);
    }

    for (auto &g : grouped) {
        std::cout << "Group:\n";

        for (auto &e : g) {
            std::cout << e.value << "\n";
        }
    }

    std::sort(
        grouped.begin(), grouped.end(),
        [](auto &g1, auto &g2) {
            return g1[0].time < g2[0].time;
        }
    );

    std::cout << "\nAfter sorting\n\n";

    for (auto &g : grouped) {
        std::cout << "Group:\n";

        for (auto &e : g) {
            std::cout << e.value << "\n";
        }
    }
}

    Com saída:

    Group:
1
2
3
Group:
4
5
Group:
6
Group:
7

After sorting

Group:
7
Group:
6
Group:
4
5
Group:
1
2
3
    • 2

relate perguntas