0

私は現在、データ構造の試験のために勉強していて、説明を使用できる問題に出くわしました。要素 i の後に k 個のゼロを挿入し、毎回インデックスをチェックして適切な例外をスローする関数 InsertZero(int k, int i) を作成することになっています。

私はこれを行いましたが、関数定義がクラスで要求している LinearList& を返す方法に固執しています。return *element、return &element、および他のいくつかを無駄にしようとしました。どこが間違っていますか？

さらに、関数の時間計算量を「リストの長さと k の関数」として与えることになっています。関数全体のステップを分析し（コメントを参照）、O（k）を思いつきました...これはリストの長さを使用していません。その方法について少し混乱しています。

どんな助けでも大歓迎です。答えだけでなく、理解を求めています。

template <class T>
LinearList<T>& LinearList<T>::InsertZero(int i, int k)
{   
    //Complexity statements are in the form of 
    // "Number of steps" * "Number of times executed" = total               

    if ( i<0 || i> (MaxSize-1) || k<0)           // 3 * 1 = 3
        cout<<"Bad input exception thrown"<<endl;// 1 * 1 = 1   
    else if (k > (MaxSize-i-1) )                 // 1 * 1 = 1
        cout<<"NoMem exception thrown"<<endl;    // 1 * 1 =1
    else
    {
        while (k!=0)        // 1 * k = k
        {
            element[i+1]=0; // 1 * k = k
            i++;            // 1 * k = k
            k--;            // 1 * k = k
        }                   
        return &element;    // 1 * 1 = 1
    }
            //Total = 3+1+1+1+k+k+k+k+1 = 4k+7 = O(k)
}
4

2 に答える 2

1

element配列はLinearListクラスのデータメンバーだと思います。elementは基本的な C++ 型 (int の配列)LinearListですが、派生型です。私はreturn *thisあなたの方法の最後にします。

于 2013-10-20T19:00:59.030 に答える
0

戻り値の型は、クラスと同じ型のようです。だからあなたは戻るべき*thisです。メンバー変数である必要があり、それelmentを返す必要はないようです。

于 2013-10-20T19:01:16.283 に答える