как отсортировать список по любому ключу?

Question

#include<iostream>
using namespace std;


struct Travelers
{
    int ticket_code;
    string lastname;
    int numberofthings;
    int luggage_weight;
    Travelers* Next;
};

Travelers* Head = 0;
struct Date {
    int day;
    int month;
    int year;
    Date* Next;
};
Date* Head2 = 0;
void Insert_Traveler(Travelers** list, Travelers* t, unsigned int pos)
{
    if (pos == 0 || *list == 0) { 
        t->Next = *list;   
        *list = t;
    }
    else if (pos == 0) {
        t->Next = *list;
        *list = t;
    }
    else {
        Travelers* p = *list;
        for (unsigned int i = 0; p->Next; i++, p = p->Next)
            if (i == pos - 1)
                break;
        t->Next = p->Next;
        p->Next = t;
    }
}
Travelers* Choose_Travelers(Travelers* list, unsigned int pos)
{
    while (list && pos)
    {
        list = list->Next;
        --pos;
    }

    return list;
}
Travelers* Choose_NextAndBefore1(Travelers* list, unsigned int pos) {
    return Choose_Travelers(list, pos + 1);
}
Travelers* Choose_NextAndBefore2(Travelers* list, unsigned int pos) {
    return Choose_Travelers(list, pos - 1);
}
int Location(Travelers* list, string key) {
    Travelers* p = list;
    unsigned int n = 0;
    for (; p; n++, p = p->Next) {
        if (p->lastname == key) break;
    }
    return n;
}
Travelers* Delete_Traveler(Travelers** list, unsigned int pos)
{
    Travelers* d = 0;

    if (pos == 0) {
        d = *list;
        *list = d->Next;
    }
    else {
        Travelers* p = *list;
        for (unsigned int i = 0; p->Next; i++, p = p->Next)
            if (i == pos - 1) {
                d = p->Next;
                p->Next = d->Next;
                break;
            }
    }

    return d;
}

void Print_Travelers(Travelers* list)
{
    for (Travelers* p = list; p; p = p->Next)
        cout << "code: " << p->ticket_code
        << "  " << p->lastname
        << " nth: " << p->numberofthings
        << " weight: " << p->luggage_weight
        << '\n';
    cout << '\n';
}


int main()
{
    for (int i = 0; i < 10; i++) {
        char nm[10];
        Travelers* p = new Travelers;
        p->ticket_code = rand() % 1000;
        sprintf_s(nm, "tr_%d", i);
        p->lastname = nm;
        p->numberofthings = rand() % 5 + 1;
        p->luggage_weight = (rand() % 10 + 1) * p->numberofthings;

        Insert_Traveler(&Head, p, i);
    }

    cout << "list of travelers\n";
    Print_Travelers(Head);

    cout << "delete some travelers\n";
    Travelers* p = Delete_Traveler(&Head, 9);
    if (p) {
        cout << "delete as pos " << 9 << "  "
            << "code: " << p->ticket_code
            << "  " << p->lastname
            << " nth: " << p->numberofthings
            << " weight: " << p->luggage_weight
            << '\n';
        delete p;
    }


    for (int i = 0; i < 10; i++) {
        p = Delete_Traveler(&Head, i);
        if (p) {
            cout << "delete as pos " << i << "  "
                << "code: " << p->ticket_code
                << "  " << p->lastname
                << " nth: " << p->numberofthings
                << " weight: " << p->luggage_weight
                << '\n';
            delete p;
        }
    }

    cout << "------\n";
    cout << "\nlist of travelers after deletions\n";
    Print_Travelers(Head);
    int pos;
    cout << "Choose index" << endl;
    cin >> pos;
    Travelers* k = Choose_Travelers(Head, pos);
    if (!k)
        std::cout << "NOT FOUND" << std::endl;
    else
    {
        cout << "code: " << k->ticket_code
            << "  " << k->lastname
            << " nth: " << k->numberofthings
            << " weight: " << k->luggage_weight
            << '\n';
    }
    cout << "Enter a key you want to choose" << endl;
    string key;
    cin >> key;
    int t = Location(Head, key);
    cout << t<<endl;
    int poss;
    cout << "Choose index" << endl;
    cin >> poss;
    Travelers* e = Choose_NextAndBefore1(Head, poss);
    if (!e)
        std::cout << "NOT FOUND" << std::endl;
    else
    {
        cout << "code: " << e->ticket_code
            << "  " << e->lastname
            << " nth: " << e->numberofthings
            << " weight: " << e->luggage_weight
            << '\n';
    }
    Travelers* b = Choose_NextAndBefore2(Head, poss);
    if (!b)
        std::cout << "NOT FOUND" << std::endl;
    else
    {
        cout << "code: " << b->ticket_code
            << "  " << b->lastname
            << " nth: " << b->numberofthings
            << " weight: " << b->luggage_weight
            << '\n';
    }

}

Answer 1

Надо написать функцию сортировки списка, например, с вот таким прототипом

void Sort_travelers_list (Travelers **list, int (*cmpf)(Travelers *s1, Travelers *s2));

которая при сравнении элементов будет вызывать передаваемую ей функцию-компаратор cmpf.

Этот компаратор должен возвращать число меньшее, равное или большее нуля в зависимости от сравнения полей в переданных элементах списка (поле в первой структуре меньше, равно или больше, чем то же поле во второй структуре).

Для сравнения по каждому из полей (или их комбинации) надо написать по одной функции.
Например:

int cmpf_ticket (Travelers *s1, Travelers *s2) {
  return s1->ticket_code - s2->ticket_code;
}

int cmpf_lastname (Travelers *s1, Travelers *s2) {
  int rc = 0;
  if (s1->lastname < s2->lastname)
    rc = -1;
  else if (s1->lastname > s2->lastname)
    rc = 1;
  return rc;
}

БЛОГ НА HUSL

как отсортировать список по любому ключу?

Ответы (1 шт):