Вставка узлов в связанный список в отсортированном порядке

Мне нужна помощь, чтобы вставить данные из узла класса в связанный список. Список — это контейнер для узлов. Их нужно отсортировать по фамилии, имени и возрасту. (У меня уже есть операторные функции для их сравнения) Я просто не уверен, как использовать указатели для их вставки и сортировки.
Ниже приведены два определения моих классов и то, что у меня есть для моей функции вставки. Я также предоставил алгоритм выбора потенциального выбора из предыдущего проекта, который можно было бы использовать для работы с этим. Кто-нибудь может помочь?

// Объявления класса

 class node;
class list
{
public:
void insert(string f, string l, int a);
int length();

private:
node *head;
int listlength;
};
class node
{
friend list;
public:
node();                           // Null constructor
~node();                          // Destructor
void put(ostream &out);           // Put
bool operator == (const node &);  // Equal
bool operator < (const node &);   // Less than
private:
string first, last;
int age;
node *next;
};

// Как вызывается insert в MAIN

while (!infile.eof())
{
infile >> first >> last >> age;

// Process if okay

if (infile.good())
a.insert(first, last, age);
};

// Вставить функцию

  void list::insert(string f, string l, int a)
{
node *temp1, *temp2 = head;
temp1 = new node();
temp1->first = f;
temp1->last = l;
temp1->age = a;
temp1->next = NULL;
if (listlength == 0)
{
temp1->next = head;
}
else
while (temp2->next != NULL)
{
;
}

}

// Потенциальный алгоритм сортировки

 void sort(person b[], int count)
{
int i = 0, j = 0, indexofsmallest = i;
person smallest = b[i];

for (i = 0; i < count; i++)
{
smallest = b[i];
indexofsmallest = i;

for (j = i+1; j < count; j++)
{
if (b[j] < smallest)
{
smallest = b[j];
indexofsmallest = j;
}
}

//cstdlib swap function

swap(b[i], b[indexofsmallest]);
}

}

0

Решение

Если вы действительно хотите отсортировать связанный список, что не рекомендуется, вам придется настроить свой алгоритм для работы с указателями вместо индексов массива. Это будет выглядеть примерно так:

void sort(node* head, int count)
{
// int i = 0, j = 0,
node* smallest = head;

while (head != NULL)
{
smallest = head;
node* toTest = head->next;
while (toTest != NULL)
{
if (toTest->age < smallest->age)
{
smallest = toTest;
}
toTest = toTest->next;
}

//make your own swap function

pointerSwap(head, smallest);

head = head -> next;
}

}

Вы можете написать свой собственный алгоритм обмена, который применяется к указателям, это может быть сложно, если вы не отслеживаете элемент перед тем, который отправляете в список.

2

Другие решения

Из-за отсутствия быстрого доступа к каждому элементу в связанном списке, все обычные алгоритмы сортировки занимают слишком много времени, особенно в односвязном списке, поэтому один из подходов состоит в том, чтобы просто сохранять список отсортированным в процессе вставки. Худший случай O (n ^ 2)

1