C语言 C 程序制作链表的第二个副本
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13633182/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C program to make a second copy of a linked list
提问by user
I was writing a C code to copy the contents of a Linked List onto another list. I want to know if there is a more efficient way of doing this.
我正在编写一个 C 代码来将链接列表的内容复制到另一个列表中。我想知道是否有更有效的方法来做到这一点。
Which is better?
哪个更好？
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;
}
OR
或者
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;
}
回答by axiom
For copying one linked list to another linked list, you have no other optionbut to iterate through one and keep copying the values to the second, in a total of O(n)time.
You are alreadydoing it. There is no wayto do better unless there is some relation among the elements that are stored.
要将一个链表复制到另一个链表，您别无选择，只能遍历一个链表并在总O(n)时间内将值复制到第二个链表。你已经在做。有没有办法做的更好，除非有被存储的元素之间有一定的关系。
A recursive solution may be better to look at, but it will in fact be less efficient.
递归解决方案可能更好看，但实际上效率较低。
Edit: For the changed question
编辑：对于更改后的问题
The Iterative version is better.
迭代版本更好。
Note : LOC has no direct relation with efficiency.
注意：LOC 与效率没有直接关系。
回答by wildplasser
Without going recursive, this is about the most compact you can get:
无需递归，这是您可以获得的最紧凑的：
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;
}
回答by Useless
For speed, there may in fact be a better way of doing it. As always, the only real way to tell is to benchmark it.
对于速度，实际上可能有更好的方法。与往常一样，唯一真正的判断方法是对其进行基准测试。
- Depending on the relative cost of iteration
- (which may itself depend on how and in what order you allocated your nodes, as well as cache and memory architecture)
- versus free store allocation
- (which may depend on what state your heap is in, how many other threads are likely to be accessing it, the physical memory status in the host OS, etc.)
it maybe faster to:
spend one iteration counting the length of the source list
int len = 0; for (start2 = start1; start2 != NULL; start2 = start2->link) ++len;allocate space for all required nodes in a single block
struct node *temp = malloc(len * sizeof(*temp));and then spend a second iteration linking up your array of nodes
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;
- 取决于迭代的相对成本
- （这本身可能取决于您分配节点的方式和顺序，以及缓存和内存架构）
- 与免费商店分配
- （这可能取决于您的堆处于什么状态，有多少其他线程可能正在访问它，主机操作系统中的物理内存状态等）
这样做可能会更快：
花一次迭代计算源列表的长度
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;
As I say, I'm not promising it willbe faster (and it's certainly uglier), but it maybe on some systems, with some compilers, under some conditions. Of course, it's a non-starter if the rest of your code assumes you can freeindividual nodes at will.
正如我所说，我不保证它会更快（而且它肯定更丑），但它可能会在某些系统上，在某些条件下使用某些编译器。当然，如果您的其余代码假设您可以随意使用free单个节点，那么它就不是初学者。
For elegance, recursion naturally wins.
对于优雅，递归自然胜出。
The simple iterative approach is usually going to be a good compromise, though, between elegant but might explode unless you have a fancy TCO-ing compilerand the above, which is frankly a bit ugly and would benefit from an explanatory comment.
然而，简单的迭代方法通常是一个很好的折衷方案，在优雅但可能会爆炸，除非你有一个花哨的 TCO-ing 编译器和上面的，坦率地说有点丑陋，并且会从解释性评论中受益。
