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

为了将一个链表复制到另一个链表，您别无选择，只能遍历一个链表并将值复制到第二个链表，总共需要O(n)一段时间。你已经在做。除非存储的元素之间存在某种关系，否则没有办法做得更好。

递归解决方案可能更好看，但实际上效率较低。

编辑：对于改变的问题

迭代版本更好。

注：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

对于速度，实际上可能有更好的方法。与往常一样，唯一真正的判断方法是对其进行基准测试。

  • 取决于迭代的相对成本
    • （这本身可能取决于您分配节点的方式和顺序，以及缓存和内存架构）
  • 与免费商店分配相比
    • （这可能取决于您的堆处于什么状态，有多少其他线程可能正在访问它，主机操作系统中的物理内存状态等）

  • 可能会更快：

    • 花一次迭代计算源列表的长度

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

    • 为单个块中的所有必需节点分配空间

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

    • 然后花费第二次迭代链接你的节点数组

      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 回答