跟踪链表的初始值

Question

遍历链表有时对我来说似乎很棘手（正如我正在学习的那样）。

我一直在递归地做事情，但我想迭代地做这件事。

下一个函数将列表 l 中的值添加到列表 mx，如果其值大于 x:

typedef struct slist *Lint;

typedef struct slist {
    int value;
    Lint next;
} Nodo;

void split(Lint l, int x, Lint *mx){
    Lint mxtmp=NULL;

    while (l!=NULL){
        if(l->value > x){
            *mx = (Lint) calloc(1,sizeof(Nodo));
            (*mx)->value = l->value;
            (*mx)->next = NULL;
            mxtmp = *mx;
            *mx = (*mx)->next;
        }

        l = l->next;
    }

    *mx = mxtmp;

}

打印 *mx 而不是列表给我一个值（使用适当的循环遍历列表）。

问题是，我似乎忘记了列表的开头；在这种情况下，我似乎无法跟踪指向列表 *mx 开头的指针，这是我正在更改的列表。

我该怎么办？

我对这个函数的另一个疑问是，我怎么能不将值归因于新列表，而是创建新的 mx 列表，只需指向主列表中的结构 l?

Answer 1

typedef struct slist *Lint;

typedef struct slist {
    int value;
    Lint next;
    } Nodo;

void split(Lint l, int x, Lint *mx){
     Lint mxtmp=NULL;
     int i = 0;
     while (l!=NULL){
         if(l->value > x){
             *mx = (Lint) calloc(1,sizeof(Nodo));
             (*mx)->value = l->value;
             (*mx)->next = NULL;
             if(!i) //mxtmp will keep track of the first allocated Nodo item
             {
               mxtmp = *mx;
               i++;
             }
             mx = &((*mx)->next); // with this, next( so *mx) will be initialized to point to a new Nodo item in the next loop
         }

         l = l->next;
     }

     mx = &mxtmp; //finally we make mx point to the first allocated Nodo item
}

我做了以下代码来测试它：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

typedef struct slist *Lint;

typedef struct slist {
    int value;
    Lint next;
    } Nodo;

void recurs_free(Lint f)
{
   if(!f)return;
   if(f->next)recurs_free(f->next);
   free(f);
}

void recurs_printf(Lint f)
{
   if(!f)return;
   printf("%d\n", f->value);
   if(f->next)recurs_printf(f->next);
}

void split(Lint l, int x, Lint *mx){
     Lint mxtmp=NULL;
     int i = 0;
     while (l!=NULL){
         if(l->value > x){
             *mx = (Lint) calloc(1,sizeof(Nodo));
             (*mx)->value = l->value;
             (*mx)->next = NULL;
             if(!i) //mxtmp will keep track of the first allocated Nodo item
             {
               mxtmp = *mx;
               i++;
             }
             mx = &((*mx)->next); // with this, next( so *mx) will be initialized to point to a new Nodo item in the next loop
         }

         l = l->next;
     }
     mx = &mxtmp; //finally we make mx point to the first allocated Nodo item
}

int main()
{
    void recurs_printf(Lint f);
    void recurs_free(Lint f);
    void split(Lint l, int x, Lint *mx);
    Lint t = NULL;
    Nodo a = {1, NULL}, b = {2, &a}, c = {3, &b}, d = {4, &c}, e = {5, &d};
    split(&e, 3, &t);
    recurs_printf(t);
    recurs_free(t);
    return 0;
}

Answer 2

诊断

您的问题出在这段代码中：

void split(Lint l, int x, Lint *mx){
    Lint mxtmp=NULL;

    while (l!=NULL){
        if(l->value > x){
            *mx = (Lint) calloc(1,sizeof(Nodo));

您对 *mx 的分配意味着您丢失了原始指针，无法正确更新您的列表。很少有平台使用 calloc() 不会将指针设置为 null，但是当您的代码显式设置结构的内容时使用 calloc() 毫无意义。

您可能需要更多类似的东西：

void split(Lint l, int x, Lint *mx)
{
    Lint mxtmp = NULL;

    while (l != NULL)
    {
        if (l->value > x)
        {
            mxtmp = (Lint) malloc(sizeof(*mxtmp));
            if (mxtmp == 0)
                …report error and do not continue…
            mxtmp->value = l->value;
            mxtmp->next = *mx;
            *mx = mxtmp;
        }
        l = l->next;
    }
}

这会以与 l 中出现的顺序相反的顺序插入 *mx 中的项目，因为它始终插入列表的前面。如果您愿意，可以安排附加到 *mx 的末尾。

如果您需要从源列表中删除条目，l，并将它们传输到 *mx，那么您需要将 Lint *l 传递给函数，以便如果需要将 l 中的第一项（或具有修改后的签名的 *l）转移到 *mx.

，则可以更新列表

说明

This does the job very well. Do you mind explaining what happens with the *mx? Because I don't seem to understand how the *mx is "increased"; it seems that the *mx is always in the same pointer value.

我对它的工作感到欣慰，因为我在这次更新之前没有机会测试它。

假设我们接到这样的电话：

Lint list1 = 0;
…populate list1…
Lint list2 = 0;
split(list1, 10, &list2);

指针list2有自己的地址。它保存一个值，最初是空指针。 list2指针的地址传给了split()，也就是说split()可以修改指针内容（就好像你有int i = 0; some_func(&i);，那么some_func()可以修改i).

中的值

如split()遍历链表，l，当找到需要复制的值时，新建一个mxtmp指向的节点，并填入价值。它使新节点的 next 指针指向当前位于列表头部的内容 (mxtmp->next = *mx;)，然后它修改 *mx 的地址——这实际上是 list1在示例调用的调用函数中 — 指向使其包含新节点的地址 (*mx = mxtmp;).

测试

这是我想出的测试代码，运行完全在valgrind下：

#include <stdlib.h>
#include <stdio.h>

typedef struct slist *Lint;

typedef struct slist
{
    int value;
    Lint next;
} Nodo;

static void error(const char *msg)
{
    fprintf(stderr, "%s\n", msg);
    exit(EXIT_FAILURE);
}

static void split(Lint l, int x, Lint *mx)
{
    // Note minor change compared to original suggested code.
    while (l != NULL)
    {
        if (l->value > x)
        {
            Lint mxtmp = (Lint) malloc(sizeof(*mxtmp));
            if (mxtmp == 0)
                error("Out of memory");
            mxtmp->value = l->value;
            mxtmp->next = *mx;
            *mx = mxtmp;
        }
        l = l->next;
    }
}

static void print_list(const char *tag, Lint list)
{
    printf("%s:", tag);
    while (list != NULL)
    {
        printf(" --> %d", list->value);
        list = list->next;
    }
    putchar('\n');
}

static void insert(Lint *list, int value)
{
    Lint node = malloc(sizeof(*node));
    if (node == 0)
        error("Out of memory");
    node->value = value;
    node->next = *list;
    *list = node;
}

static void destroy(Lint list)
{
    while (list != NULL)
    {
        Lint next = list->next;
        free(list);
        list = next;
    }
}

int main(void)
{
    Lint list1 = NULL;
    insert(&list1, 2);
    insert(&list1, 10);
    insert(&list1, 11);
    insert(&list1, 23);
    print_list("List 1", list1);

    Lint list2 = NULL;
    split(list1, 10, &list2);
    print_list("List 1", list1);
    print_list("List 2", list2);

    destroy(list1);
    destroy(list2);
    return 0;
}

编译

源文件名为 nodo.c，因此程序名为 nodo，我有一个 makefile 配置并启用了很多编译器警告选项。没有警告（来自 Mac OS X 10.10.3 上的 GCC 5.1.0）：

$ gcc -O3 -g -std=c11 -Wall -Wextra -Werror nodo.c -o nodo
$

我认为这是最低要求；在它安静地编译之前，我通常甚至运行代码。

示例输出：

List 1: --> 23 --> 11 --> 10 --> 2
List 1: --> 23 --> 11 --> 10 --> 2
List 2: --> 11 --> 23

打印list1两次是偏执狂，检查在split操作中没有损坏。注意split()函数要写成使用insert()函数。

调试打印还会打印节点地址和下一个指针：

static void print_list(const char *tag, Lint list)
{
    printf("%s:\n", tag);
    while (list != NULL)
    {
        printf("--> %3d  (%p, next %p)\n", list->value, (void *)list, (void *)list->next);
        list = list->next;
    }
    putchar('\n');
}

屈服，例如：

List 1:
-->  23  (0x10081f410, next 0x10081f3c0)
-->  11  (0x10081f3c0, next 0x10081f370)
-->  10  (0x10081f370, next 0x10081f320)
-->   2  (0x10081f320, next 0x0)

List 1:
-->  23  (0x10081f410, next 0x10081f3c0)
-->  11  (0x10081f3c0, next 0x10081f370)
-->  10  (0x10081f370, next 0x10081f320)
-->   2  (0x10081f320, next 0x0)

List 2:
-->  11  (0x10081f4b0, next 0x10081f460)
-->  23  (0x10081f460, next 0x0)

临别感言

我没有重新组织数据类型，但留给了我自己的设备，我可能会使用类似的东西：

typedef struct List List;
struct List
{
    int   value;
    List *next;
};

然后绕过List *和List **。这使用标记名称作为类型名称，这是 C++ 在没有显式 typedef.

的情况下自动执行的操作

跟踪链表的初始值

Keeping track of initial value of linked list

c

linked-list

诊断

说明

测试

编译

示例输出：

临别感言