按第一个值和第二个值将输入排序到一个链表中

Question

在过去的几天里，我一直在努力解决这个问题。免责声明:这是家庭作业。我一直在自己做，但我真的不知道我做错了什么。

我得到了一个航空公司航班行李信息列表，格式为航空公司，目的地，行李车号码。

我必须把这个列表整理成一个新的列表。新列表必须按航空公司排序，并且在每个航空公司中必须按目的地排序。

• 新加坡巴尔的摩176
• ATA Allentown 1549
• 大陆桥港915
• 新加坡伯克利878
• 新加坡利沃尼亚1462
• Quantas Fremont 1610

将排序为:

• ATA Allentown 1549
• 大陆桥港915
• Quantas Fremont 1610
• 新加坡巴尔的摩176
• 新加坡伯克利878
• 新加坡利沃尼亚1462

这是我现在正在做的:

#Main.cpp#
int main()
{
    Node * head = NULL;
    ifstream fin("planes.txt");
    string airline, destination;
    int carNum;
    while(!fin.eof())
    {
        fin >> airline >> destination >> carNum;
        insertNode(airline, destination, carNum, head);
    }
    cout << endl;
    system("pause");
    return 0;
}

#Node.cpp#
void insertNode(string value1, string value2, int value3, Node *&head)
{
    Node * ptr = head;
    if (ptr == NULL || ptr->getString1() > value1)
    {
        insertAtHead(value1, value2, value3, head);
    }
    else
    {
        while (ptr->getNext() != NULL && ptr->getNext()->getString1() < value1)
        {
            ptr = ptr->getNext(); // advance to next node in list
        }
        insertValue(value1, value2, value3, ptr);
    }
}
void insertValue (string value1, string value2, int value,Node *afterMe)
{
    afterMe->setNext(new Node(value1, value2, value, afterMe->getNext()));
}
void insertAtHead (string value1, string value2, int value3,Node *&head)
{
    head = new Node(value1, value2, value3, head);
}

我将省略我的node.h，因为它只保存函数声明和简单的访问器函数。

我当前的insertNode函数只按第一个值排序。这是insertNode函数的一个变体，我尝试按第一个和第二个值开始排序。

它相当丑。即使在笔记本纸上写了好几页，我还是被这些乱七八糟的东西困住了。

void insertNode(string value1, string value2, int value3, Node *&head)
{
    Node * ptr = head;
    if (ptr == NULL || ptr->getString1() > value1)
    {
        insertAtHead(value1, value2, value3, head);
    }
    else
    {
        while (ptr->getNext() != NULL)  //Keep going as long as I am not at the end of the list
        {
            if (ptr->getNext()->getString1() < value1) //If Airline in list is smaller then the Airline I am adding
            {
                ptr = ptr->getNext(); //Move onto the next value in the list
            }
            else if (ptr->getNext()->getString1() == value1) //If Airline in list is equivalent to the Airline I am adding
            {
                if(ptr->getNext()->getString2() < value2)   //The airlines matched up. How do the destinations compare?
                {
                    ptr = ptr->getNext(); //If the destination in the list is less than the one I am adding, move on
                }
                else
                {
                    insertValue(value1, value2, value3, ptr); //If one I am adding is not less than the list, add it here.
                }
            }
            else
            {
                insertValue(value1, value2, value3, ptr);
            }
        }
    }
}

Answer 1

需要传递一个函数对象或指向比较两个节点的函数的指针。

这将允许一个链表函数通过传递比较函数对象或指向比较函数的指针来排序。

例如:std::sort。

Answer 2

在不知道您的确切需求的情况下，您似乎将此问题复杂化了。如果您只是创建一个包含Airline + Destination + luggage Car的新字符串，并将其插入已排序的列表中，就可以实现您的数据目标。

是否有任何理由你必须保持你的数据元素在一个列表行分开?换句话说:

string strToBeSorted = strAirline;
strToBeSorted += " ";
strToBeSorted += strDestination;
strToBeSorted += " ";
strToBeSorted += strBaggageCar;

则插入strToBeSorted。这将给你一个可以排序的字符串。这使得对所有条目进行排序变得很简单。您将能够知道strToBeSorted到哪里去，直到航空公司，目的地，甚至行李车按什么顺序去。