如何在循环中创建节点并将它们插入链表

Question

这是我的结构：

typedef struct gene{
    char* name;
    int length;
    int* sequence;
} gene;

typedef struct genes{
    gene gene;
    struct genes* next;
} genes;

构造函数：

genes* createGenes(gene newGene){
    genes* geneArr = malloc(sizeof(genes));
    if (NULL != geneArr){
        geneArr->gene = newGene;
        geneArr->next = NULL;
    }
    return geneArr;
}

void deleteGenes(genes* geneArr){
    if(NULL != geneArr->next){
        deleteGenes(geneArr->next);
    }
    free(geneArr);
}

genes* addGene(genes* geneList, gene newGene){
    genes* toAdd = createGenes(newGene);
    if (NULL != toAdd){
        geneList->next = toAdd;
    }
    return geneList;
}

和一个函数（它创建一个具有给定长度的序列。对于 5 -> {2, 2, 2, 2, 2}）：

gene twosGene(char* name, int length){
    gene newGene;
    newGene.name = name;
    newGene.length = length;
    newGene.sequence = (int*)malloc(sizeof(int) * length);

    for(int i = 0; i < length; i++){
        newGene.sequence[i] = 2;
    }
    return newGene;
}

这是我的 main() 函数：

int main(){
    int count = 1;

    genes* geneArr = createGenes(twosGene("gene1", count++));

    for (int i = 0; i < 4; ++i) {
        geneArr = addGene(geneArr, twosGene("geneLoop", count++));
    }

    genes* iter;
    for (iter = geneArr; NULL != iter; iter = iter->next) {
        printf("gene=%d\n", iter->gene.length);
        free(iter->gene.sequence);
    }

    deleteGenes(geneArr);

    return 0;
}

我期望这样的输出：

gene=1
gene=2
gene=3
gene=4
gene=5

但我得到的是：

gene=1
gene=5

另外，当我使用 Valgrind 时，我的程序中有一些泄漏。

==20580== HEAP SUMMARY:
==20580==     in use at exit: 132 bytes in 6 blocks
==20580==   total heap usage: 11 allocs, 5 frees, 1,244 bytes allocated

我不明白为什么。感谢您的帮助。

Answer 1

在此函数内

genes* addGene(genes* geneList, gene newGene){
    genes* toAdd = createGenes(newGene);
    if (NULL != toAdd){
        geneList->next = toAdd;
    }
    return geneList;
}

你总是覆盖最初在语句中创建的节点的下一个数据成员

genes* geneArr = createGenes(twosGene("gene1", count++));

您似乎想在当前列表的末尾添加一个新节点。在这种情况下，函数看起来像

genes* addGene(genes* geneList, gene newGene){
    genes* toAdd = createGenes(newGene);
    if (NULL != toAdd){
        genes *current = geneList;

        while ( current->next != NULL ) current = current->next;
        current->next = toAdd;
    }
    return geneList;
}

但是通常这个函数定义也是无效的，因为最初 geneList 可以等于 NULL。所以使用你的方法应该按以下方式重写函数

genes* addGene(genes* geneList, gene newGene){
    genes* toAdd = createGenes(newGene);
    if (NULL != toAdd){
        if ( geneList == NULL )
        {
            geneList = toAdd;
        }
        else
        {
            genes *current = geneList;

            while ( current->next != NULL ) current = current->next;
            current->next = toAdd;
        }
    }

    return geneList;
}

然而，如果将指针传递给列表的头指针，即使这个函数实现也可以得到改进。

例如

int addGene( genes **geneList, gene newGene )
{
    genes* toAdd = createGenes(newGene);
    int success = toAdd != NULL;

    if ( success )
    {
        while ( *geneList != NULL ) geneList = &( *geneList )->next;
        *geneList = toAdd;
    }

    return success;
}

在这种情况下函数可以这样调用

genes* geneArr = createGenes(twosGene("gene1", count++));

for (int i = 0; i < 4; ++i) {
    addGene( &geneArr, twosGene("geneLoop", count++));
}

Answer 2

在：

genes* geneArr = createGenes(twosGene("gene1", count++));

for (int i = 0; i < 4; ++i) {
    geneArr = addGene(geneArr, twosGene("geneLoop", count++));
}

第一个分配链表的头部。在 for 循环中，接下来每次迭代都会覆盖这个 head。你 should/could 做了：

genes* geneArr = createGenes(twosGene("gene1", count++));

genes *geneNext= geneArr;
for (int i = 0; i < 4; ++i) {
    geneNext = addGene(geneNext, twosGene("geneLoop", count++));
}

此外，addGene 必须提前指针才能使上述工作正常。

genes* addGene(genes* geneList, gene newGene){
    genes* toAdd = createGenes(newGene);
    if (NULL != toAdd){
        geneList->next = toAdd;
        genelist= geneList->next;  // add this statement.
    }
    return geneList;
}

现在可以打印了，因为你还有头。

Answer 3

addGene 函数未添加到列表末尾。它只是将新基因与第一个基因联系起来。正如 Valgrind 所报告的，列表中第一个基因之后的任何内容都是 "forgotten"，导致内存泄漏。

这是 addGenes 函数的更新版本，应该可以使用：

genes* addGene(genes* geneList, gene newGene){
    genes* toAdd = createGenes(newGene);
    if (NULL != toAdd){
        if (geneList == NULL){
            geneList = toAdd;
        } else {
            genes *last = geneList;
            while (last->next != NULL){
                last = last->next;
            }
            last->next = toAdd;
        }
    }
    return geneList;
}

如何在循环中创建节点并将它们插入链表

How to create nodes in a loop and insert them to a linked list

c

struct

linked-list

singly-linked-list