复制 link 列表 (C++)
Copying link list (C++)
struct n{//The definition of Linked List
int x;
struct n * next;
};
typedef struct n node;
int counter(node *r){ //Counting the node.
int y=0;
while(r != NULL){
y++;
r = r->next;
}
return y;
}
//The problem is down there
void cpyLl(node *r){ //Copying link list
int temp;
for (int y = counter(r); y > 0 ;y--){
temp = r -> x;
while (r -> next != NULL){
r = r -> next;
}
r -> next = (node *)malloc(sizeof(node));
r = r->next;
r -> x = temp;
}
}
int main(){
node * root;
root = (node *)malloc(sizeof(node));
root -> x = 10;
root -> next = (node *)malloc(sizeof(node));
root -> next -> x = 20;
root -> next -> next =(node *)malloc(sizeof(node));
root -> next -> next -> x =30;
root -> next -> next -> next = NULL;
cpyLl(root);
return 0;
}
我试图复制我的链接列表，当我调用 cpyLl() 时它进入了无限循环；功能。
我的预期输出是：
10 20 30 10 20 30
我实际上使用函数来定义节点，但我在 main 中编写它是为了 now.Because 的代码复杂性。
我正在使用 Dev-C++ 5.11。
您的编译器应该警告您存在未知类型 n：
struct n { //The definition of Linked List
int x;
n * next;
};
以上 n 的类型在您声明 n * next; 时未知。要解决此问题，您需要在 n 之前包含 struct，例如
struct n { //The definition of Linked List
int x;
struct n * next;
};
您的 typedef 中也存在此问题，例如
typedef n node;
同样 n 目前未知。相反，你需要。
typedef struct n node;
正如布鲁诺指出的那样，您在 counter 未初始化时通过使用 x 调用 未定义行为，例如：
int counter(node *r){ //Counting the node.
int x;
while(r != NULL){
x++; /* what is the value of x on the first iteration? */
...
初始化int x = 0补救
复制列表问题
首先在r = r->next;中->两边不要放空格，箭头运算符应该直接连接struct和member。
您的 cpyLl() 函数不复制任何内容。为了复制一个列表，你需要你的函数 return 一个指向新复制列表的指针。例如，这样做是有意义的：
/* cpyL1 should return a pointer to the head of the newly copied list */
node *cpyLl (node *r) {
在您的函数中，您需要 allocate/create 一个新的第一个节点并为副本分配第一个数据值，然后基本上重复其余节点循环遍历所有节点创建一个新分配的节点用于复制和复制价值。您需要将指向复制列表开头的指针保留到 return。 cpyL1 内根本不需要 counter。您有一个链表，您可以使用 next 指针遍历该列表。例如
/* cpyL1 should return a pointer to the head of the newly copied list */
node *cpyLl (node *r) {
node *copy = NULL, *p; /* pointers for new list - initialized NULL */
if (!r) { /* validate r is not NULL */
fputs ("error: list to copy is empty.\n", stderr);
return NULL;
}
copy = malloc (sizeof *copy); /* allocate 1st node of copy */
if (!copy) {
perror ("malloc-copy");
return NULL;
}
p = copy;
p->x = r->x;
while (r->next) { /* copy all nodes from r to copy */
p->next = malloc (sizeof *p->next); /* allocate each node */
if (!p->next) { /* validate the allocation */
perror ("malloc-p->next");
return copy; /* return partial copy of list */
}
r = r->next; /* advance to next node */
p = p->next;
p->x = r->x; /* set node value */
p->next = NULL;
}
return copy; /* return pointer to newly copied list */
}
（注意： 您必须验证每个分配。）
现在，如果您只想复制一个特定的节点，那么您可以迭代直到找到值或地址，然后只需复制一个节点。
把它放在一起并添加一个打印列表和空闲列表功能，你可以做类似的事情：
#include <stdio.h>
#include <stdlib.h>
struct n { //The definition of Linked List
int x;
struct n *next;
};
typedef struct n node;
int counter (node *r) //Counting the node.
{
int y = 0;
while (r != NULL) {
y++;
r = r->next;
}
return y;
}
/* cpyL1 should return a pointer to the head of the newly copied list */
node *cpyLl (node *r) {
node *copy = NULL, *p; /* pointers for new list - initialized NULL */
if (!r) { /* validate r is not NULL */
fputs ("error: list to copy is empty.\n", stderr);
return NULL;
}
copy = malloc (sizeof *copy); /* allocate 1st node of copy */
if (!copy) {
perror ("malloc-copy");
return NULL;
}
p = copy;
p->x = r->x;
while (r->next) { /* copy all nodes from r to copy */
p->next = malloc (sizeof *p->next); /* allocate each node */
if (!p->next) { /* validate the allocation */
perror ("malloc-p->next");
return copy; /* return partial copy of list */
}
r = r->next; /* advance to next node */
p = p->next;
p->x = r->x; /* set node value */
p->next = NULL;
}
return copy; /* return pointer to newly copied list */
}
void prnlist (node *l)
{
while (l) {
printf (" %d", l->x);
l = l->next;
}
putchar ('\n');
}
void freelist (node *l)
{
while (l) {
node *victim = l;
l = l->next;
free (victim);
}
}
int main (void) {
node *root, *p, *copy = NULL;
root = malloc (sizeof *root);
/* first node */
if (!root) { /* validate EVERY allocation */
perror ("malloc-root");
return 1;
}
root->x = 10;
p = root; /* assign pointer to root */
/* second node */
p->next = malloc (sizeof *p->next);
if (!p->next) { /* validate EVERY allocation */
perror ("malloc-p->next");
return 1;
}
p = p->next;
p->x = 20;
/* third node */
p->next = malloc (sizeof *p->next);
if (!p->next) { /* validate EVERY allocation */
perror ("malloc-p->next");
return 1;
}
p = p->next;
p->x = 30;
p->next = NULL; /* set p->next to NULL */
copy = cpyLl(root); /* copy root list to copy */
if (!copy) {
fputs ("error: copy is NULL\n", stderr);
return 1;
}
puts ("\noriginal list:\n");
prnlist (root);
puts ("\ncopy of list:\n");
prnlist (copy);
freelist (root); /* don't forget to free what you allocate */
freelist (copy);
return 0;
}
例子Use/Output
$ ./bin/structfwd
original list:
10 20 30
copy of list:
10 20 30
内存Use/Error检查
不要忘记验证您的内存使用是否有任何错误。
$ valgrind ./bin/structfwd
==12148== Memcheck, a memory error detector
==12148== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==12148== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==12148== Command: ./bin/structfwd
==12148==
original list:
10 20 30
copy of list:
10 20 30
==12148==
==12148== HEAP SUMMARY:
==12148== in use at exit: 0 bytes in 0 blocks
==12148== total heap usage: 6 allocs, 6 frees, 96 bytes allocated
==12148==
==12148== All heap blocks were freed -- no leaks are possible
==12148==
==12148== For counts of detected and suppressed errors, rerun with: -v
==12148== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
在 cpyLl() 中，您没有初始化分配的每个新 node 的 next 字段。 malloc() 不会将分配的内存清零（如果需要，请改用 calloc()）。
此外，for 循环中用于查找列表中最后一个节点的 while 循环确实应该在进入 for 循环之前移动。没有理由在每个 for 循环迭代中使用 while 循环，只需将新节点附加到您分配的前一个节点即可。
尝试更像这样的东西：
struct node {
int x;
node *next;
};
int countLinkedList(node *n, node **last = NULL) {
int count = 0;
if (last) *last = NULL;
while (n) {
++count;
if (last) *last = n;
n = n->next;
}
return count;
}
node* makeLinkedListNode(int x) {
node *n = new node; // (node*) malloc(sizeof(node));
n->x = x;
n->next = NULL;
return n;
}
void freeLinkedList(node *n) {
node *next;
while (n) {
next = n->next;
delete n; // free(n);
n = next;
}
}
void copyLinkedList(node *n) {
node *last;
for (int y = countLinkedList(n, &last); y > 0; --y) {
last->next = makeLinkedListNode(n->x);
last = last->next;
n = n->next;
}
}
void printLinkedList(node *n) {
while (n) {
std::cout << n->x << " ";
n = n->next;
}
std::cout << std::endl;
}
int main() {
node *root = makeLinkedListNode(10);
root->next = makeLinkedListNode(20);
root->next->next = makeLinkedListNode(30);
std::cout << "Before copy: ";
printLinkedList(root);
copyLinkedList(root);
std::cout << "After copy: ";
printLinkedList(root);
freeLinkedList(root);
return 0;
}
输出：
Before copy: 10 20 30
After copy: 10 20 30 10 20 30
也就是说，您确实应该改用标准 C++ 容器和算法，例如：
#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>
void printLinkedList(const std::list<int> &l) {
for(int x : l) {
std::cout << x << " ";
}
std::cout << std::endl;
}
int main() {
std::list<int> l;
l.push_back(10);
l.push_back(20);
l.push_back(30);
std::cout << "Before copy: ";
printLinkedList(l);
std:copy_n(l.begin(), l.size(), std::back_inserter(l));
std::cout << "After copy: ";
printLinkedList(l);
return 0;
}
输出：
Before copy: 10 20 30
After copy: 10 20 30 10 20 30
struct n{//The definition of Linked List
int x;
struct n * next;
};
typedef struct n node;
int counter(node *r){ //Counting the node.
int y=0;
while(r != NULL){
y++;
r = r->next;
}
return y;
}
//The problem is down there
void cpyLl(node *r){ //Copying link list
int temp;
for (int y = counter(r); y > 0 ;y--){
temp = r -> x;
while (r -> next != NULL){
r = r -> next;
}
r -> next = (node *)malloc(sizeof(node));
r = r->next;
r -> x = temp;
}
}
int main(){
node * root;
root = (node *)malloc(sizeof(node));
root -> x = 10;
root -> next = (node *)malloc(sizeof(node));
root -> next -> x = 20;
root -> next -> next =(node *)malloc(sizeof(node));
root -> next -> next -> x =30;
root -> next -> next -> next = NULL;
cpyLl(root);
return 0;
}
我试图复制我的链接列表，当我调用 cpyLl() 时它进入了无限循环；功能。
我的预期输出是：
10 20 30 10 20 30
我实际上使用函数来定义节点，但我在 main 中编写它是为了 now.Because 的代码复杂性。
我正在使用 Dev-C++ 5.11。
您的编译器应该警告您存在未知类型 n：
struct n { //The definition of Linked List
int x;
n * next;
};
以上 n 的类型在您声明 n * next; 时未知。要解决此问题，您需要在 n 之前包含 struct，例如
struct n { //The definition of Linked List
int x;
struct n * next;
};
您的 typedef 中也存在此问题，例如
typedef n node;
同样 n 目前未知。相反，你需要。
typedef struct n node;
正如布鲁诺指出的那样，您在 counter 未初始化时通过使用 x 调用 未定义行为，例如：
int counter(node *r){ //Counting the node.
int x;
while(r != NULL){
x++; /* what is the value of x on the first iteration? */
...
初始化int x = 0补救
复制列表问题
首先在r = r->next;中->两边不要放空格，箭头运算符应该直接连接struct和member。
您的 cpyLl() 函数不复制任何内容。为了复制一个列表，你需要你的函数 return 一个指向新复制列表的指针。例如，这样做是有意义的：
/* cpyL1 should return a pointer to the head of the newly copied list */
node *cpyLl (node *r) {
在您的函数中，您需要 allocate/create 一个新的第一个节点并为副本分配第一个数据值，然后基本上重复其余节点循环遍历所有节点创建一个新分配的节点用于复制和复制价值。您需要将指向复制列表开头的指针保留到 return。 cpyL1 内根本不需要 counter。您有一个链表，您可以使用 next 指针遍历该列表。例如
/* cpyL1 should return a pointer to the head of the newly copied list */
node *cpyLl (node *r) {
node *copy = NULL, *p; /* pointers for new list - initialized NULL */
if (!r) { /* validate r is not NULL */
fputs ("error: list to copy is empty.\n", stderr);
return NULL;
}
copy = malloc (sizeof *copy); /* allocate 1st node of copy */
if (!copy) {
perror ("malloc-copy");
return NULL;
}
p = copy;
p->x = r->x;
while (r->next) { /* copy all nodes from r to copy */
p->next = malloc (sizeof *p->next); /* allocate each node */
if (!p->next) { /* validate the allocation */
perror ("malloc-p->next");
return copy; /* return partial copy of list */
}
r = r->next; /* advance to next node */
p = p->next;
p->x = r->x; /* set node value */
p->next = NULL;
}
return copy; /* return pointer to newly copied list */
}
（注意： 您必须验证每个分配。）
现在，如果您只想复制一个特定的节点，那么您可以迭代直到找到值或地址，然后只需复制一个节点。
把它放在一起并添加一个打印列表和空闲列表功能，你可以做类似的事情：
#include <stdio.h>
#include <stdlib.h>
struct n { //The definition of Linked List
int x;
struct n *next;
};
typedef struct n node;
int counter (node *r) //Counting the node.
{
int y = 0;
while (r != NULL) {
y++;
r = r->next;
}
return y;
}
/* cpyL1 should return a pointer to the head of the newly copied list */
node *cpyLl (node *r) {
node *copy = NULL, *p; /* pointers for new list - initialized NULL */
if (!r) { /* validate r is not NULL */
fputs ("error: list to copy is empty.\n", stderr);
return NULL;
}
copy = malloc (sizeof *copy); /* allocate 1st node of copy */
if (!copy) {
perror ("malloc-copy");
return NULL;
}
p = copy;
p->x = r->x;
while (r->next) { /* copy all nodes from r to copy */
p->next = malloc (sizeof *p->next); /* allocate each node */
if (!p->next) { /* validate the allocation */
perror ("malloc-p->next");
return copy; /* return partial copy of list */
}
r = r->next; /* advance to next node */
p = p->next;
p->x = r->x; /* set node value */
p->next = NULL;
}
return copy; /* return pointer to newly copied list */
}
void prnlist (node *l)
{
while (l) {
printf (" %d", l->x);
l = l->next;
}
putchar ('\n');
}
void freelist (node *l)
{
while (l) {
node *victim = l;
l = l->next;
free (victim);
}
}
int main (void) {
node *root, *p, *copy = NULL;
root = malloc (sizeof *root);
/* first node */
if (!root) { /* validate EVERY allocation */
perror ("malloc-root");
return 1;
}
root->x = 10;
p = root; /* assign pointer to root */
/* second node */
p->next = malloc (sizeof *p->next);
if (!p->next) { /* validate EVERY allocation */
perror ("malloc-p->next");
return 1;
}
p = p->next;
p->x = 20;
/* third node */
p->next = malloc (sizeof *p->next);
if (!p->next) { /* validate EVERY allocation */
perror ("malloc-p->next");
return 1;
}
p = p->next;
p->x = 30;
p->next = NULL; /* set p->next to NULL */
copy = cpyLl(root); /* copy root list to copy */
if (!copy) {
fputs ("error: copy is NULL\n", stderr);
return 1;
}
puts ("\noriginal list:\n");
prnlist (root);
puts ("\ncopy of list:\n");
prnlist (copy);
freelist (root); /* don't forget to free what you allocate */
freelist (copy);
return 0;
}
例子Use/Output
$ ./bin/structfwd
original list:
10 20 30
copy of list:
10 20 30
内存Use/Error检查
不要忘记验证您的内存使用是否有任何错误。
$ valgrind ./bin/structfwd
==12148== Memcheck, a memory error detector
==12148== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==12148== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==12148== Command: ./bin/structfwd
==12148==
original list:
10 20 30
copy of list:
10 20 30
==12148==
==12148== HEAP SUMMARY:
==12148== in use at exit: 0 bytes in 0 blocks
==12148== total heap usage: 6 allocs, 6 frees, 96 bytes allocated
==12148==
==12148== All heap blocks were freed -- no leaks are possible
==12148==
==12148== For counts of detected and suppressed errors, rerun with: -v
==12148== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
在 cpyLl() 中，您没有初始化分配的每个新 node 的 next 字段。 malloc() 不会将分配的内存清零（如果需要，请改用 calloc()）。
此外，for 循环中用于查找列表中最后一个节点的 while 循环确实应该在进入 for 循环之前移动。没有理由在每个 for 循环迭代中使用 while 循环，只需将新节点附加到您分配的前一个节点即可。
尝试更像这样的东西：
struct node {
int x;
node *next;
};
int countLinkedList(node *n, node **last = NULL) {
int count = 0;
if (last) *last = NULL;
while (n) {
++count;
if (last) *last = n;
n = n->next;
}
return count;
}
node* makeLinkedListNode(int x) {
node *n = new node; // (node*) malloc(sizeof(node));
n->x = x;
n->next = NULL;
return n;
}
void freeLinkedList(node *n) {
node *next;
while (n) {
next = n->next;
delete n; // free(n);
n = next;
}
}
void copyLinkedList(node *n) {
node *last;
for (int y = countLinkedList(n, &last); y > 0; --y) {
last->next = makeLinkedListNode(n->x);
last = last->next;
n = n->next;
}
}
void printLinkedList(node *n) {
while (n) {
std::cout << n->x << " ";
n = n->next;
}
std::cout << std::endl;
}
int main() {
node *root = makeLinkedListNode(10);
root->next = makeLinkedListNode(20);
root->next->next = makeLinkedListNode(30);
std::cout << "Before copy: ";
printLinkedList(root);
copyLinkedList(root);
std::cout << "After copy: ";
printLinkedList(root);
freeLinkedList(root);
return 0;
}
输出：
Before copy: 10 20 30 After copy: 10 20 30 10 20 30
也就是说，您确实应该改用标准 C++ 容器和算法，例如：
#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>
void printLinkedList(const std::list<int> &l) {
for(int x : l) {
std::cout << x << " ";
}
std::cout << std::endl;
}
int main() {
std::list<int> l;
l.push_back(10);
l.push_back(20);
l.push_back(30);
std::cout << "Before copy: ";
printLinkedList(l);
std:copy_n(l.begin(), l.size(), std::back_inserter(l));
std::cout << "After copy: ";
printLinkedList(l);
return 0;
}
输出：
Before copy: 10 20 30 After copy: 10 20 30 10 20 30