1

縮小する動的配列を設計する場合、最も使用頻度の高いインデックスを追跡する方法と、そのインデックスの保持オブジェクトが削除されたときに、新しく最も使用頻度の高い index を見つけます。

現時点では、aa を単純int last_usedにして、この変数を維持するコストを に請求することを考えることができます。func_deleteこれは、最高のものを削除するかどうかを確認する必要があり、削除する場合は、null 以外を探して小さい値をそれぞれ確認する必要があります。(配列は常に null 初期化されます)

if(last_index == deleted_index){

    while(last_index >0 && array[--last_index] != NULL)

    // if the array is now only half full, I realloc 
}

他にスマートな方法はありますか？

4

1 に答える 1

1

私には問題ないように見えますが、論理的には、関数が常に最高のアイテムを削除する場合、より小さいインデックスには値func_deleteが存在しないはずです。NULLしたがって、これは次のようにする必要があります。

if(last_index == deleted_index && array[last_index] != NULL) {
    //delete last item
    free(array[last_index]);
    //set to NULL and decrement
    array[last_index--] = NULL;
}

編集：

あなたのコメントに基づいて、私はあなたがやろうとしていることを理解しています。代わりに、挿入関数で最も使用されているインデックスを追跡することができると思います:

void array_insert(array , element e, int index) 
{
    if (index > arr->highest_index) {
       arr->highest_index = index;
    }
    //insert element
}

そして、削除するときに、インデックスが最高かどうかを確認します。あなたがやっているように、物事をさらに複雑にすることなく、それを行うためのより良い方法があるとは思わないでください。たとえば、別のソートされたインデックスのリストを保持できます。一定時間ですが、私が言ったように、それは物事を複雑にします。ただし、別のデータ構造の方が便利であると思います。たとえば、リンクされたリストは、ノードをランダムに削除する場合はより効率的ですが、ノードをランダムに挿入する場合は効率的ではありません。

于 2012-11-09T07:15:28.293 に答える