c - 将节点添加到单链列表的中间

Question

所以我有下面要显示的代码

struct GraphicElement {
char* fileName;
struct GraphicElement* pNext;
    };
struct RasterGraphic {
struct GraphicElement* GraphicElements;
    };

并且

void InsertGraphicElement(struct RasterGraphic* pA)
{
int counter = 1;
int response = 0;
char tempString[256];
struct GraphicElement *newNode = malloc(sizeof(*newNode));
if (newNode == NULL) return;
newNode->fileName = malloc(256 * sizeof(char));
if (newNode->fileName == NULL) return;
newNode->pNext = NULL;


printf("Insert a GraphicElement in the RasterGraphic\nPlease enter the GraphicElement filename: ");
scanf("%s", newNode->fileName);


if (pA->GraphicElements == NULL)
{
    pA->GraphicElements = newNode;
    printf("This is the first GraphicElement in the list\n");
}
else
{

    struct GraphicElement *tempHead = pA->GraphicElements;
    while (tempHead->pNext != NULL)
    {
        tempHead = tempHead->pNext;
        counter++;
    }

    printf("There are %d GraphicElement(s) in the list. Please specify the position (<= %d) to insert at :", counter, counter);
    scanf("%d", &response);

    if (response == counter) {
        tempHead->pNext = newNode;
        return;

    }
}

return;
}

如您所见，我有一个结构定义，然后有一个将节点插入列表的函数。我拥有它，以便如果它插入的第一个节点并告诉用户它是列表中的第一个元素。我遇到的问题是添加更多元素。现在，代码在按顺序添加新节点方面没有问题。询问用户要在列表中插入的位置。现在，只要他们选择按顺序添加它，它就可以完美运行。我已经尝试了很多事情，但我无法弄清楚循环的逻辑，并且无法在列表的中间添加一个节点，因此示例输出将如下所示。

清单包含1、2、3
用户添加了第四个元素4，但想将其添加到位置1，这是2所在的位置，因此新的更新列表看起来像1、4、2、3。

Answer 1

在链接列表中的任何地方插入都是不可思议的，唯一真正的挑战是在处理三个条件时保持指针笔直：


插入第一节点（或新的第一节点）；
在现有的第一个和最后一个节点之间的某个位置之间插入一个节点；和
插入列表的末尾。


第一种情况，插入第一个（或新的第一个）节点仅需要分配一个新节点，然后将其插入列表中的第一个节点，或者如果头节点已经存在，则设置newnode->next = head;和head = newnode;

在末尾插入没有太大区别，您只需迭代到最后一个节点并设置last->next = newnode;

在两者之间插入节点的情况需要更多考虑。使指针保持笔直的最简单方法是拔出铅笔和纸并绘制列表的指针图，然后将列表分成两部分，在其中插入新节点，并弄清楚拾取前所需的步骤。键盘（这样会更容易）

不需要花哨的东西，只需一个带有next（或pNext）指针的节点连接的框图即可。一个简单的列表将由两个节点（A和B）完成，例如

       A           B
    +------+    +------+
    | node |    | node |
    | next |--> | next |-->NULL
    +------+    +------+

然后只需在要插入新节点的位置断开列表，例如

       A               B
    +------+    |   +------+
    | node |    /   | node |
    | next |--> \   | next |-->NULL
    +------+    /   +------+
                |
               new
            +------+
            | node |
            | next |-->
            +------+

这使您可以可视化所需的步骤。找到node A，设置new->next = B;，设置A->next = new;（注意：您必须在要插入新节点的位置之前停在该节点上），结果将是：

       A           new         B
    +------+    +------+    +------+
    | node |    | node |    | node |
    | next |--> | next |--> | next |-->NULL
    +------+    +------+    +------+

了解完处理插入操作所需的确切内容后，现在拿起键盘并实现该逻辑。

正如@WhozCraig所述，由于您将具有一个插入函数来处理所有三种情况，因此在处理列表操作（或通常需要在函数内分配新的内存块来更改指针地址的指针）时，它有助于将指针的地址传递给函数（以便函数接收指针本身-而不是指针的副本）。

无论您是需要初始分配给列表包装器，还是需要分配一个新节点作为列表中的第一个节点的简单列表，传递指针的地址都可以在函数中进行更改而不必返回并在调用函数中将返回值分配为新地址。

为gelement_t类型添加几个typedefs struct GraphicElement，为rgraphic_t类型添加struct RasterGraphic，这两者都是为了减少键入，消除了某些MixedCase样式笨拙的情况，您可以考虑以下内容中的InsertGraphicElement函数：以下方式。

首先，您的InsertGraphicElement函数将成功或失败，因此请选择一个有意义的返回类型以表明成功或失败。在处理列表时，返回指向新插入的节点的指针很有帮助，并且即使失败也可以返回NULL，例如

gelement_t *InsertGraphicElement (rgraphic_t **pA)

由于要传递指向RasterGraphic结构的指针，因此可以向该结构中添加数据，使其对实际列表的包装更加有用。添加节点计数器是一种方便的方式，可以跟踪单链接列表中的节点数量，而不必每次都遍历该列表。

typedef struct RasterGraphic {
    size_t nelements;
    gelement_t *GraphicElements;
} rgraphic_t;

在函数内，您应该验证是否已分配了指针，如果没有，则为RasterGraphic结构分配，例如

    int position = 0;

    if (!*pA) {                         /* if list NULL - allocate new list */
        puts ("allocating new list.");
        *pA = malloc (sizeof **pA);
        if (!*pA) {                     /* validate every allocation */
            perror ("malloc-*list");
            exit (EXIT_FAILURE);
        }
        (*pA)->nelements = 0;           /* initialize values */
        (*pA)->GraphicElements = NULL;
    }

接下来，您可以分配并验证新节点以添加为第一个节点或添加到某个位置，例如

    gelement_t *node = malloc (sizeof *node);   /* allocate node */
    if (!node) {    /* validate */
        perror ("malloc-node");
        exit (EXIT_FAILURE);
    }

接下来收集您的文件名和位置信息，并将node->fileName设置为一个新分配的块，其中包含用户输入的文件名（几个帮助函数使此操作变得更加容易），例如

    node->fileName = get_filename_stdin();  /* request filename */
    if (!node->fileName) {  /* validate */
        free (node);
        return NULL;
    }
    node->pNext = NULL; /* set next pointer NULL */

    position = get_int_stdin (*pA);    /* request position */

现在，您可以在函数中处理答案开头标识的3种情况的位置。如果还没有(*pA)->GraphicElements节点，则将添加第一个节点（因此您不需要询问位置）。如果不是第一个节点，并且请求的位置是0，则作为新的第一个节点插入。 （两者都可以在单个案例中处理）

如果请求的位置大于零，那么您将迭代到插入点之前的节点并按照上图所示进行插入，然后将节点插入到该位置。

一种方法是：

    gelement_t *p = (*pA)->GraphicElements;

    if (!p || position == 0) {  /* insert as new head */
        node->pNext = p;
        (*pA)->GraphicElements = node;
    }
    else {  /* insert at position (default end) */
        int n = 0;
        while (n < position - 1 && p->pNext) {  /* locate node before */
            p = p->pNext;
            n++;
        }
        node->pNext = p->pNext; /* set node->pNext to current pNext */
        p->pNext = node;        /* set current pNext to node */
    }

    (*pA)->nelements++; /* increment number of elements in list */

它将根据用户输入处理您的插入。剩下的就是：

    return node;    /* meaningful return to indicate success/failure */
}

（请注意：当您熟悉列表操作逻辑时，可以将此功能分解为几个单独处理这些功能的功能，例如create_list()，create_node()和add_node()。（在其中创建RasterGraphic列表中的GraphicElement节点，最后将该节点添加到列表中的给定位置-留给您）

放在一起并添加辅助函数，一个简短的例子是：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>     /* for PATH_MAX */

typedef struct GraphicElement {
    char* fileName;
    struct GraphicElement* pNext;
} gelement_t;

typedef struct RasterGraphic {
    size_t nelements;
    gelement_t *GraphicElements;
} rgraphic_t;

char *get_filename_stdin (void)
{
    char filename[PATH_MAX] = "";
    char *newname = NULL;

    fputs ("enter filename : ", stdout);

    if (fgets (filename, PATH_MAX, stdin)) {
        size_t len = strlen (filename);
        if (len && filename[len-1] == '\n') {
            filename[--len] = 0;
            if (!len) {
                fputs ("error: filename empty.\n", stderr);
                return NULL;
            }
        }
        else if (len == PATH_MAX) {
            fputs ("error: filename exceeds PATH_MAX\n", stderr);
            return NULL;
        }
        newname = malloc (len + 1);
        if (!newname) {
            perror ("malloc-newname");
            exit (EXIT_FAILURE);
        }
        memcpy (newname, filename, len + 1);
    }

    return newname;
}

int get_int_stdin (rgraphic_t *list)
{
    char buf[PATH_MAX];
    int pos = 0;

    if (!list->nelements) {
        puts ("inserting as head.");
        return 0;
    }
    fputs ("index to insert: ", stdout);

    if (fgets (buf, PATH_MAX, stdin))
        if (sscanf (buf, "%d", &pos) != 1 || pos < 0 || 
            pos > (long)list->nelements)
            return list->nelements;

    return pos;
}

gelement_t *InsertGraphicElement (rgraphic_t **pA)
{
    int position = 0;

    if (!*pA) {                         /* if list NULL - allocate new list */
        puts ("allocating new list.");
        *pA = malloc (sizeof **pA);
        if (!*pA) {                     /* validate every allocation */
            perror ("malloc-*list");
            exit (EXIT_FAILURE);
        }
        (*pA)->nelements = 0;           /* initialize values */
        (*pA)->GraphicElements = NULL;
    }

    gelement_t *node = malloc (sizeof *node);   /* allocate node */
    if (!node) {    /* validate */
        perror ("malloc-node");
        exit (EXIT_FAILURE);
    }

    node->fileName = get_filename_stdin();  /* request filename */
    if (!node->fileName) {  /* validate */
        free (node);
        return NULL;
    }
    node->pNext = NULL; /* set next pointer NULL */

    position = get_int_stdin (*pA);     /* request position */

    gelement_t *p = (*pA)->GraphicElements;

    if (!p || position == 0) {  /* insert as new head */
        node->pNext = p;
        (*pA)->GraphicElements = node;
    }
    else {  /* insert at position (default end) */
        int n = 0;
        while (n < position - 1 && p->pNext) {  /* locate node before */
            p = p->pNext;
            n++;
        }
        node->pNext = p->pNext; /* set node->pNext to current pNext */
        p->pNext = node;        /* set current pNext to node */
    }

    (*pA)->nelements++; /* increment number of elements in list */

    return node;    /* meaningful return to indicate success/failure */
}

/* loop over list printing values */
void prn_list (rgraphic_t *list)
{
    size_t n = 0;
    gelement_t *node = list->GraphicElements;

    printf ("\n\n%zu nodes in list\n", list->nelements);

    for (; node; node = node->pNext)
        printf ("%2zu: %s\n", 1 + n++, node->fileName);    
}

/* loop over list freeing memory (pay attention to victim) */
void free_list (rgraphic_t *list)
{
    gelement_t *node = list->GraphicElements;

    while (node) {
        gelement_t *victim = node;
        node = node->pNext;
        free (victim->fileName);
        free (victim);
    }

    free (list);
}

int main (void) {

    rgraphic_t *list = NULL;
    puts ("\nNOTE: pressing [Enter] for index - inserts at end!\n"
        "      [Ctrl+d] at \"filename: \" prompt to end input.\n");

    while (InsertGraphicElement(&list)) {}  /* create list/insert nodes */

    prn_list (list);    /* print list */
    free_list (list);   /* free list */
}

使用/输出示例

$ ./bin/ll_single_insert_ptp

NOTE: pressing [Enter] for index - inserts at end!
      [Ctrl+d] at "filename: " prompt to end input.

allocating new list.
enter filename : one
inserting as head.
enter filename : four
index to insert: 1
enter filename : two
index to insert: 1
enter filename : three
index to insert: 2
enter filename : five
index to insert:
enter filename :

5 nodes in list
 1: one
 2: two
 3: three
 4: four
 5: five

内存使用/错误检查

在您编写的任何可以动态分配内存的代码中，对于任何分配的内存块，您都有2个责任：（1）始终保留指向该内存块起始地址的指针，因此，（2）在不分配该内存块时可以将其释放需要更长的时间。

必须使用一个内存错误检查程序来确保您不尝试访问内存或不要在分配的块的边界之外/之外进行写入，不要尝试在未初始化的值上读取或建立条件跳转，最后确定您可以释放已分配的所有内存。

对于Linux，valgrind是通常的选择。每个平台都有类似的内存检查器。它们都很容易使用，只需通过它运行程序即可。

$ valgrind ./bin/ll_single_insert_ptp
==9747== Memcheck, a memory error detector
==9747== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==9747== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==9747== Command: ./bin/ll_single_insert_ptp
==9747==

NOTE: pressing [Enter] for index - inserts at end!
      [Ctrl+d] at "filename: " prompt to end input.

allocating new list.
enter filename : one
inserting as head.
enter filename : four
index to insert: 1
enter filename : two
index to insert: 1
enter filename : three
index to insert: 2
enter filename : five
index to insert:
enter filename :

5 nodes in list
 1: one
 2: two
 3: three
 4: four
 5: five
==9747==
==9747== HEAP SUMMARY:
==9747==     in use at exit: 0 bytes in 0 blocks
==9747==   total heap usage: 12 allocs, 12 frees, 136 bytes allocated
==9747==
==9747== All heap blocks were freed -- no leaks are possible
==9747==
==9747== For counts of detected and suppressed errors, rerun with: -v
==9747== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

始终确认已释放已分配的所有内存，并且没有内存错误。

仔细检查一下，如果您还有其他问题，请告诉我。