主页 / coding / 问题 / 78579039
Accepted
Mark
Asked: 2024-06-05 14:10:02 +0800 CST

对链表进行排序，将一些元素打包在一起

  • 772

我有一个链接列表：

MyLinkedList::LinkedList<Event *> list;

来自LinkedList这个库，并且Event是这个结构：

typedef struct 
{
    TimeSpan time;
    int value;

    bool queued;
} Event;

TimeSpan来自这个图书馆的地方。用一些项目填充列表后，我运行以下函数：

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;
}

该compare函数定义如下：

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());
}

它只是按元素的时间对元素进行排序。这段代码工作正常。

现在我需要处理queued结构中的标志。这里是一个示例输入数据：

时间 价值 排队
18:00 1 错误的
xx：xx 2 真的
xx：xx 3 真的
10:30 4 错误的
xx：xx 5 真的
08:15 6 错误的
06:45 7 错误的

queued排序时，设置了标志的项目必须位于前一个项目（queued 未设置）之后，无论其时间值如何（因此xx:xx在表中）。

预期输出是：

时间 价值 排队
06:45 7 错误的
08:15 6 错误的
10:30 4 错误的
xx：xx 5 真的
18:00 1 错误的
xx：xx 2 真的
xx：xx 3 真的

换句话说：如果queued是，则false元素将照常排序（按时间），如果是，则true它们必须遵循前一个元素（就像它们“分组”在一起）。

由于该compare函数只能处理两个项目，并且除了初始订单之外我没有其他信息，因此如何将这些queued项目与其“父”项目保留在一起？

c++

1 个回答

  1. Best Answer

    首先将您的列表分组。在你的例子中，[1, 2, 3, 4, 5, 6, 7]变成[[1, 2, 3], [4, 5], [6], [7]].

    然后按每组中第一个元素的时间戳对它们进行排序。[[1, 2, 3], [4, 5], [6], [7]]变成[[7], [6], [4, 5], [1, 2, 3]].

    然后压平该列表以获得[7, 6, 4, 5, 1, 2, 3].

    使用std::vector，这可能看起来像：

    #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";
        }
    }
}

    带输出：

    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

相关问题