“баг” с сортировкой односвязного списка с++

110
27 ноября 2020, 13:10

нужно отсортировать односвязный список по одному из информационных полей(в моем случае kol), написал вот такую функцию, но проблема в том, что после сортировки при выводе не хватает одного элемента, как мне это пофиксить?

void mysort(List *head)
{
    List *newH = NULL;
    while (head != NULL)
    {
        List *node = head;
        head = head->nxt;
        if (newH == NULL || node->kol < newH->kol)
        {
            node->nxt = newH;
            newH = node;
        }
        else
        {
            List *now = newH;
            while (now->nxt != NULL && !(node->kol < now->nxt->kol))
            {
                now = now->nxt;
            }
            node->nxt = now->nxt;
            now->nxt = node;
        }
    }
}

вот сам список

struct List {
string name;
int kol;
vector<string> v;
string date;
List *nxt;
};

вот вывод:

void vivod(List* head, int n) {//rabotaet
    List* tmp = head;
    for (int i = 0; i < n; ++i) {
        if (tmp == NULL) {
            break;
        }
        else {
            cout << " NOMER " << i << endl;
            cout << "------------------------------" << endl;
            cout <<"NAME: "<< tmp->name;
            cout << endl;
            cout << "KOLICHESTVO: "<<tmp->kol <<endl ;
            for (int i = 0; i < tmp->kol; ++i) {
                cout << tmp->v[i]<<" ";
            }
            cout << endl;
            cout<<"DATE :"<< tmp->date << endl;
            cout << "------------------------------" << endl;
            tmp = tmp->nxt;
        }
    }
}

вызов функции сортировки и последующий вывод:

mysort(head);
vivod(head, n);// n = razmer spiska

ну и объявление head:

List* head = new List();
Answer 1

Не разбираясь даже в деталях реализации алгоритма, можно сразу сказать, что эта функция никак не может корректно сортировать список уже потому, что в процессе сортировки списка у него может поменяться первый элемент, т.е. head. У вашей функции не предусмотрено никакой возможности сообщить вызывающему коду, что у списка поменялся head.

Так что ваше "не хватает одного элемента" - не более чем частное проявление проблемы в вашем конкретном тесте. "Не хватать" может сколько угодно элементов.

READ ALSO
явная специализация шаблонов C++

явная специализация шаблонов C++

При объявлении шаблонной функции с явной специализацией для строки( тип char*) появляется ошибка “отсутствуют экземпляры шаблон функции”

224
QT: repaint() не перерисовывает виджет

QT: repaint() не перерисовывает виджет

По ТЗ необходимо реализовать построчную закраску многоугольника в двух вариантах - с задержкой после отрисовки каждой линии и без нееЕсть...

115
Вынести функцию в отдельный поток

Вынести функцию в отдельный поток

есть программа, как в аргументы функции передать целый класс, и его изменять так, что-бы именения были видны в main()?

120
В чём разница между decltype(auto) и auto&amp;&amp;?

В чём разница между decltype(auto) и auto&&?

В чём разница между decltype(auto) и auto&&?

99