0

Personオブジェクトのリンクリストを名前で並べ替えるLinkedListクラスのメソッドを作成しようとしています。私のメソッドは正常にコンパイルされますが、人のリストを並べ替えようとすると、出力が正しくありません。また、実行を停止することはありません。たとえば、このコード

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

内側のforループにcurrent->linkがあり、elseには内側のforループがあります。forループにcurrent=current-> linkがあるか、何もしないと思います。もしそうなら、あなたは他のすべての要素をスキップするでしょう。

また、言語もあります。新しいノードを作成するのではなく、元のリストのノードを変更するのです。これは、リストを歩きながら変更していることを意味します。これにより、リストを並べ替えると破損します。動作は未定義であり、要素を追加する順序によって異なります。

于 2013-02-15T20:29:45.217 に答える
0

リンクされたリストの処理の問題 (私は見ていません) を修正した後でも、関数には欠陥があります。同じ姓を持つオブジェクトをcompareName()比較すると、値を提供せずに関数から返される可能性があります ( ）。 PersonName.compare(p.fName) <= 0

比較関数から不確定な結果を取得すると、ほとんどすべての並べ替えが中断されます。

これはおそらく宿題なので、問題の修正は演習として残します。

于 2013-02-15T20:50:27.840 に答える