0

我正在尝试为我的 LinkedList 类编写一个方法，该方法将按名称对 Person 对象的链接列表进行排序。我的方法编译得很好，但是当我尝试对人员列表进行排序时，输出不正确。它也永远不会停止运行。例如，这段代码

Person *p1 = new Person("K", "B");
Person *p2 = new Person("A", "A");
Person *p3 = new Person("S", "M");
Person *p4 = new Person("B", "M");

LinkedList ll;
ll.insertFront(*p1);
ll.insertFront(*p2);
ll.insertFront(*p3);
LinkedList newList = ll.insertionSort();
newList.print();
cout << endl;

给出这个输出

B, K

A, A

谁能帮我弄清楚我的算法哪里出错了？谢谢！

这是我用来按名字和名字对名字进行排序的方法：

int Person::compareName(Person p)
{
    if (lName.compare(p.lName) > 0)
    {
        return 1;
    }
    else if (lName.compare(p.lName) == 0)
    {
        if (fName.compare(p.fName) > 0)
        {
            return 1;
        }
        else return -1;
    }
    else return -1;
}

插入排序方法：

LinkedList LinkedList::insertionSort()
   {
    //create the new list
    LinkedList newList;
    newList.front = front;
    
    Node *n;
    Node *current = front;
    Node *trail = NULL;
    
   for(n=front->link; n!= NULL; n = n->link)//cycle through old chain
{
    Node* newNode = n;
    
    //cycle through new, sorted chain to find insertion point
    for(current = newList.front; current != NULL; current = current->link)
    {
        //needs to go in the front
        if(current->per.compareName(n->per) < 0)
        {
            break;
        }
        
        else
        {
            trail = current;
            
        }
    }
    
    //if it needs to be added to the front of the chain
    if(current == front)
    {
        newNode->link = newList.front;
        newList.front = newNode;
    }
    //else goes in middle or at the end
    else{
        newNode->link = current;
        trail->link = newNode;
    }

    return newList;
}
4

2 回答 2

0

你有 current->link 在你的内部 for 循环中，在 else 到内部 for 循环中。我假设你在 for 循环中确实有 current = current->link 或者它什么都不做。如果是这样，您将跳过所有其他元素。

您还有语言方面的问题-您不是在创建新节点，而是在更改原始列表中的节点。这意味着您在遍历列表时正在更改列表，这会在您对列表进行排序时损坏列表。行为未定义，取决于您添加元素的顺序。

于 2013-02-15T20:29:45.217 回答
0

即使在您修复了任何链表处理问题（我没有看过）之后，您的compareName()函数也有一个缺陷 - 当比较Person具有相同姓氏的对象时，它可能会从函数返回而不提供值（在以下情况下Name.compare(p.fName) <= 0）。

从比较函数中获得不确定的结果几乎会破坏任何类型。

由于这可能是家庭作业，因此我将把纠正问题留作练习。

于 2013-02-15T20:50:27.840 回答