如何:链接列表的深层复制

Question

我在用C编写的程序遇到了一些问题,而且我已经超越了我的知识.总之,我需要将链接列表从一个列表深层复制到另一个列表.这些列表中包含malloc数据,我需要保留所有数据,而不需要指针指向相同的信息.

我只发布了我认为相关的代码.如果我遗漏了任何重要的背景信息,请告诉我.

这是代码:

matrix.h

typedef struct matrix {
        char *name;
        int R;
        int C;
        int dim;
        void (*concat_matrices)( struct matrix *A, struct matrix *B, struct matrix *ret );
} Matrix;

void concat_matrices( Matrix *A, Matrix *B, Matrix *ret ) {
        int L1 = strlen( A->name );
        int L2 = strlen( B->name );
        int len = L1 + L2;
        char *Ap = (char*)malloc(L1*sizeof(char)); strcpy(Ap,A->name);
        char *Bp = (char*)malloc(L2*sizeof(char )); strcpy(Bp,B->name);
        char *c = (char*)malloc(sizeof(char)*(len + 2));
        c[0] = '('; strcat(c, Ap); strcat(c, Bp); c[len+1] = ')';
        ret->name = (char*)malloc(sizeof(char)*(len + 2));
        strcpy(ret->name, c);
        ret->R = A->R; ret->C = B->C;
        ret->dim = ret->R*ret->C;
        free(Ap); free(Bp); free(c);
}

matrix_list.h

typedef struct node {
        Matrix *M;
        struct node *next;
        struct node *prev;
} Node;

typedef struct matrix_list {
        Node *head;
        Node *tail;
        int size;
        void (*append)( struct matrix_list *list, Matrix *M );
        void (*print)( struct matrix_list *list );
        void (*reverse_print)( struct matrix_list *list );
        void (*delete)( struct matrix_list *list, const char *name );
        void (*delete_tail)( struct matrix_list *list );
        void (*delete_head)( struct matrix_list *list );
        void (*release)( struct matrix_list *list );
        void (*clone_list)( struct matrix_list *from, struct matrix_list *to );
} MatrixList;

...

void clone_list( MatrixList *from, MatrixList *to ) {
        if( from->head == NULL ) {
                to = NULL;
        } else {
                Node *tmp = from->head;
                while( tmp != NULL ) {
                        Matrix *m_copy = (Matrix*)malloc(sizeof(Matrix*));
                        char *c_copy = (char*)malloc(sizeof(char*)*strlen(tmp->M->name));

                        strcpy(c_copy,tmp->M->name);
                        m_copy->name=c_copy;
                        m_copy->R=tmp->M->R;
                        m_copy->C=tmp->M->C;
                        m_copy->concat_matrices = concat_matrices;

                        to->append( to,m_copy );
                        tmp = tmp->next;
                }
        }
}

main.c中

chain->print(chain);

MatrixList *chain_copy = (MatrixList*)malloc(sizeof(MatrixList));
set_list_functions( chain_copy );
chain->clone_list(chain, chain_copy);
chain_copy->print(chain_copy);

当我尝试打印克隆时出现问题.因为我在克隆函数中是malloc'ing,所以我理解数据超出了范围.我怎么能这样复制,所以在调用函数后,clone有自己的数据版本？

---

更新:

首先,我要感谢大家花时间回答我的问题,并教我更多关于C.我只编写了大约3年的时间.我需要学习很多东西.可以在以下位置找到来自Valgrind的0错误的更新源.

http://matthewh.me/Scripts/c++/matrix_chain/让任何其他人试图找出像我这样的东西.用户=来宾密码=来宾.clone_list函数现在看起来像这样.

void clone_list( MatrixList *from, MatrixList *to ) {
        if( from->head == NULL ) {
                to = NULL;
        } else {
                Node *tmp = from->head;
                while( tmp != NULL ) {
                        Matrix *m_copy = (Matrix*)malloc(sizeof(Matrix));
                        m_copy->name = (char*)malloc(strlen(tmp->M->name) + 1);

                        sprintf( m_copy->name, "%s", tmp->M->name );
                        m_copy->R=tmp->M->R;
                        m_copy->C=tmp->M->C;
                        m_copy->concat_matrices = concat_matrices;

                        to->append( to,m_copy );
                        tmp = tmp->next;
                }
        }
}

如果其他人看到任何其他错误并想添加其他指针,请随时这样做.

Answer 1

您没有允许终止字符串的null,因此您有经典的缓冲区溢出.

你也不必名称复制3次.您当前的代码是:

int L1 = strlen( A->name );
int L2 = strlen( B->name );
int len = L1 + L2;
char *Ap = (char*)malloc(L1*sizeof(char)); strcpy(Ap,A->name);
char *Bp = (char*)malloc(L2*sizeof(char )); strcpy(Bp,B->name);
char *c = (char*)malloc(sizeof(char)*(len + 2));
c[0] = '('; strcat(c, Ap); strcat(c, Bp); c[len+1] = ')';
ret->name = (char*)malloc(sizeof(char)*(len + 2));
strcpy(ret->name, c);
ret->R = A->R; ret->C = B->C;
ret->dim = ret->R*ret->C;
free(Ap); free(Bp); free(c);

这应该是:

int   L1 = strlen(A->name);
int   L2 = strlen(B->name);

ret->name = (char *)malloc(L1 + L2 + sizeof("()"));  // That adds 3
sprintf(ret->name, "(%s%s)", A->name, B->name);

ret->R   = A->R;
ret->C   = B->C;
ret->dim = ret->R * ret->C;

这消除了Ap,Bp并且c完全避免了缓冲区溢出问题.我不确定我会像你一样把这两个名字一起打响,但这是你的选择.

显然,这还不足以解决问题......还有其他问题.

void clone_list( MatrixList *from, MatrixList *to ) {
    if (from->head == NULL) {
        to = NULL;
    } else {
        Node *tmp = from->head;
        while( tmp != NULL ) {
            Matrix *m_copy = (Matrix*)malloc(sizeof(Matrix*));
            char *c_copy = (char*)malloc(sizeof(char*)*strlen(tmp->M->name));

            strcpy(c_copy,tmp->M->name);
            m_copy->name=c_copy;
            m_copy->R=tmp->M->R;
            m_copy->C=tmp->M->C;
            m_copy->concat_matrices = concat_matrices;

            to->append( to,m_copy );
            tmp = tmp->next;
        }
    }
}

第一个赋值将本地指针归零; 它MatrixList作为目标传入并没有做任何事情.这可能应该是:

if (from->head == 0)
{
    *to = *from;
}

这是一个批量结构副本,但是将head和tail设置为null,并且函数指针都很好 - 它们可以被共享.假设size在from被正确为零,它将是正确的to了.(同样,这可能不是你正在行使的代码.)

下一个问题是内存分配:

Matrix *m_copy = (Matrix*)malloc(sizeof(Matrix*));

这会分配一个指针的内存,而不是一个Matrix的值.使用以下任何一种:

Matrix *m_copy = (Matrix *)malloc(sizeof(*m_copy));
Matrix *m_copy = (Matrix *)malloc(sizeof(Matrix));

这是你麻烦的主要原因(valgrind也很容易找到).

当+1忘记一次时,它会被遗忘很多次,但这次它不会导致问题,除非名称是空字符串,因为你乘以4或8(32位或64位),因为它sizeof(char *)不是打算sizeof(char).

char *c_copy = (char*)malloc(sizeof(char*)*strlen(tmp->M->name));
strcpy(c_copy,tmp->M->name);

这应该是:

m_copy->name = (char *)malloc(strlen(tmp->M->name) + 1);
strcpy(m_copy->name, tmp->M->name);

我可能会使用一个名字old而不是tmp.我也不在考虑以前你应该虔诚地检查每次内存分配的每一次返回.或者使用一组封面功能进行内存分配例程,为您进行检查(通常称为xmalloc()或emalloc()等).

下面的代码似乎没有复制dim成员,如果您依赖它,这是一个错误.

to在打电话之前,你似乎依赖于列表正确初始化,我并不完全高兴clone_list().尤其是head,tail和size成员在这里没有归零,函数指针没有设置.我会更高兴看到类似的东西:

*to = *from;  // Copy function pointers
to->head = 0;
to->tail = 0;
to->size = 0;
Node *old = from->head;
for (Node *old = from->head; old != NULL; old = old->next)
{
    Matrix *m_copy = clone_matrix(old->M);
    to->append(to, m_copy);
}

甚至:

matrixlist_initialize(to);
Node *old = from->head;
for (Node *old = from->head; old != NULL; old = old->next)
{
    Matrix *m_copy = clone_matrix(old->M);
    to->append(to, m_copy);
}

该clone_matrix()功能如下:

Matrix *clone_matrix(const Matrix *old)
{
    Matrix *m_copy = (Matrix*)malloc(sizeof(*m_copy));

    m_copy->name = (char*)malloc(strlen(old->name)+1);

    strcpy(m_copy->name, old->name);
    m_copy->R   = old->R;
    m_copy->C   = old->C;
    m_copy->dim = old->dim;
    m_copy->concat_matrices = concat_matrices;
    return(m_copy);
}

我下载了一个代码版本,它现在似乎工作,或多或少.您应该至少-Wall编译为编译器选项; 我拒绝使用任何更少的编译,通常也使用-Wextra.我做了太多简单到错的错误,没有充分利用编译器,当你在学习时,你也会这样做.(我只用C编写了超过四分之一世纪;编译器仍然可以捕获拼写错误和其他愚蠢的错误,但是一旦代码编译,我很少遇到大问题.)

当我打开时-Wall,(未使用)perm()函数出现问题,因为即使它表示它也不会返回值,并且存在问题,因为main()带参数的正确定义是int main(int argc, char **argv)并且您缺少其中一个星星.除此之外,它现在似乎工作正常 - 您可以继续开发.

POSIX中有一个函数strdup()可以可靠地复制字符串.这很有用,可以避免出现错误.

您应该查看标头的使用.它们主要用于声明.如果明确使用inline(您的代码尚未使用),则可以inline在头文件中包含函数,但是,函数体不应该在头文件中.它们应该在源文件中(.c后缀).每个标头应包含使用源提供的功能使用的代码的最低必要信息.它不应包含无关的标头,但它应包括所有必需的标头.在matrix.h,你包括<stdio.h>哪些是不必要的.如果您删除了代码,<string.h>也不<stdlib.h>需要也不需要.