c++ - 按排序顺序将节点插入到链表中

Question

我需要帮助将数据从类节点插入到链表中。列表是节点的容器。他们需要根据姓氏、名字和年龄进行排序。 (我已经有运算符函数来比较它们)我只是不确定如何使用指针来插入和排序它们。下面是我的两个类定义，以及到目前为止我对插入函数的定义。我还提供了一个来自以前项目的潜在选择排序算法，可以对其进行处理。谁能帮忙？

//类声明

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

//插入是如何在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]);
    }

}

Answer 1

如果您真的想对链表进行排序(不推荐这样做)，则必须调整算法以使用指针而不是数组索引。这看起来像这样:

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

您可以编写自己的适用于指针的交换算法，这可能很困难，除非您跟踪列表中发送的项目之前的项目。