5

リンク リストの内容を別のリストにコピーする C コードを書いていました。これを行うより効率的な方法があるかどうか知りたいです。

どちらが良いですか？

struct node *copy(struct node *start1)
{
struct node *start2=NULL,*previous=NULL;

while(start1!=NULL)
{
    struct node * temp = (struct node *) malloc (sizeof(struct node));
    temp->info=start1->info;
    temp->link=NULL;

    if(start2==NULL)
    {
        start2=temp;
        previous=temp;
    }
    else
    {
        previous->link=temp;
        previous=temp;          
    }
    start1=start1->link;
}
return start2;
}

また

struct node *copy(struct node *start1)
{
    if(start1==NULL) return;
    struct node *temp=(struct node *) malloc(sizeof(struct node));
    temp->info=start1->info;
    temp->link=copy(start1->link);
    return temp;
}
4

3 に答える 3

6

あるリンクリストを別のリンクリストにコピーする場合、他のオプションはありません。1つを繰り返し処理し、合計O(n)時間で値を2番目にコピーし続ける必要があります。あなたはすでにそれをやっています。格納されている要素間に何らかの関係がない限り、これを改善する方法はありません。

再帰的な解決策を検討する方が良いかもしれませんが、実際には効率が低下します。

編集：変更された質問の場合

反復バージョンの方が優れています。

注：LOCは効率と直接の関係はありません。

于 2012-11-29T19:31:38.743 に答える
1

再帰的になることなく、これはあなたが得ることができる最もコンパクトなものです：

struct node *copy(struct node *org)
{
struct node *new=NULL,**tail = &new;

for( ;org; org = org->link) {
    *tail = malloc (sizeof **tail );
    (*tail)->info = org->info;
    (*tail)->link = NULL;
    tail = &(*tail)->link;
    }
return new;
}
于 2012-11-29T19:40:15.427 に答える
1

速度については、実際にはもっと良い方法があるかもしれません。いつものように、実際に判断する唯一の方法は、ベンチマークを行うことです。

  • 反復の相対的なコストに応じて
    • （それ自体は、ノードを割り当てた方法と順序、およびキャッシュとメモリのアーキテクチャに依存する場合があります）
  • 対無料ストア割り当て
    • (これは、ヒープの状態、ヒープにアクセスする可能性のある他のスレッドの数、ホスト OS の物理メモリの状態などによって異なります。)

  • 次のほうが速い場合があります。

    • ソースリストの長さを数えて1回の反復を費やす

      int len = 0;
for (start2 = start1; start2 != NULL; start2 = start2->link)
    ++len;

    • 単一ブロック内のすべての必要なノードにスペースを割り当てます

      struct node *temp = malloc(len * sizeof(*temp));

    • 次に、ノードの配列をリンクするために 2 回目の反復を行います

      int i = 0;
for (start2 = start1; start2 != NULL; start2 = start2->link) {
    temp[i].info = start2->info;
    temp[i].link = &temp[i+1];
}
temp[len-1].link = NULL;

私が言うように、私はそれが高速になるとは約束していません(そして確かに醜いです) 。もちろん、コードの残りの部分で、自由にfreeノードを個別にできると想定している場合、それは初心者ではありません。

エレガンスの場合、再帰が自然に勝ちます。

ただし、単純な反復アプローチは通常、洗練されていますが、派手な TCO-ing コンパイラーを使用しない限り爆発する可能性があり、率直に言って少し見苦しく、説明コメントが役立つ上記の方法との間の適切な妥協点になります。

于 2012-11-29T19:53:59.520 に答える