0

質問の名前が示すように。2 つの連結リストを取得し、最初の 2 つの連結リストに共通する要素のみから 3 つ目のリストを作成する必要があります。

ここに私が書いた関数があります

void computeC(DLL<int> &a, DLL<int> &b, DLL<int> &c)
{
    Node<int> *hunterA, *hunterB;
    hunterA = a.getHead();
    hunterB = b.getHead();


  while ( hunterA != NULL )
    {
        while ( hunterB != NULL )
        {
            int aData = hunterA->data, bData = hunterB->data;

            if ( aData == bData )
            {
                    int temp = bData;
                c.progAppend2(temp);
            }
            else
            {
                hunterB = hunterB->next;
            }   
        }
        hunterA = hunterA->next;
    }
    c.output();
}

ここに、二重リンク リスト クラスの progAppend2() 関数があります。

template <class Type>
void DLL<Type>::progAppend2(Type data)
{
    Node<Type> *newNode = new Node<Type>;
    newNode->data = data;

    if ( head == NULL )
    {
        head = newNode;
        tail = newNode;
        size++;
    }

    else
    {
         tail->next = newNode;
        newNode->prev = tail;
        tail = tail->next;
        size++;
    }
}

ここに main() があります

int main (void)
{   
    int a[9] = {3,7,10,15,16,9,22,17,32};
    int b[9] = {16,2,9,13,37,8,10,1,28};
    DLL<int> listA, listB, listC, listD;
    for ( int i = 0; i < 9; i++ )
    {
        listA.progAppend2(a[i]);
        listB.progAppend2(b[i]);
    }
    computeC(listA,listB,listC);
    listC.output();

    return 0;
}

私が抱えている問題は、何らかの理由で ListC が何も入力されておらず、output(); を呼び出したときに出力と空のリストが表示されることです。

問題はcomputeC関数にあると思います。外側の while ループは、listA 内の要素を指す HunterA を設定する必要があり、内側のループは、listB のすべての要素を、hunterA が指す要素と比較する必要があります。一致が見つかった場合、その要素は ListC にコピーされます。少なくともそれは私がそれがうまくいくべきだと思う方法です。助けていただければ幸いです。

4

2 に答える 2

1

@AEDrew はあなたに適切な提案をしていると思います。

追加したいのは、あなたの解決策は時間の複雑さO（長さ（A）*長さ（B））であり、より良い解決策はO（長さ（A）+長さ（B））です。すべての A リスト ノードをハッシュし、B リストを繰り返して、B ノードが A リストにあるかどうかを確認できます。

これも役立つことを願っています:)

于 2013-05-07T06:16:10.307 に答える