如何使用最少数量的赋值运算符构建OneTwoThree链表？

Question

我在准备面试时遇到了这个问题,并且很想知道它可以写出的不同方式.我在http://cslibrary.stanford.edu/103/找到了这个,并且已经给出了问题.

这是构建列表{1,2,3}的代码

struct node* BuildOneTwoThree() {
    struct node* head = NULL;
    struct node* second = NULL;
    struct node* third = NULL;
    head = malloc(sizeof(struct node)); // allocate 3 nodes in the heap
    second = malloc(sizeof(struct node));
    third = malloc(sizeof(struct node));
    head->data = 1; // setup first node
    head->next = second; // note: pointer assignment rule
    second->data = 2; // setup second node
    second->next = third;
    third->data = 3; // setup third link
    third->next = NULL;
    // At this point, the linked list referenced by "head"
    // matches the list in the drawing.
    return head;
}

问:编写具有最少数量的赋值(=)的代码,这将构建上述内存结构.答:它需要3次调用malloc().3 int assignments(=)设置整数.4个指针分配给设置头和3个下一个字段.有了C语言的一点聪明和知识,这可以通过7个赋值操作(=)来完成.

Answer 1

我做了六个任务.我能得到什么？

struct node
{
    int data;
    struct node * next;
};

struct node * build_123()
{
    struct node * first = malloc(sizeof(*first));
    struct node * second = malloc(sizeof(*second));
    struct node * third = malloc(sizeof(*third));

    assert(first && second && third);

    *first = (struct node){ 1, second };
    *second = (struct node){ 2, third };
    *third = (struct node){ 3, NULL };

    return first;
}

此外,练习不是很有用.如果我想从一组已知的整数构建一个链表,我会做这样的事情:

struct node
{
    int data;
    struct node * next;
};

#define build_list(...) \
    _build_list((sizeof((int []){ __VA_ARGS__ }))/(sizeof(int)), \
    (int []){ __VA_ARGS__ })

struct node * _build_list(size_t count, int values[count])
{
    struct node * next = NULL;

    for(size_t i = count; i--; )
    {
        struct node * current = malloc(sizeof *current);
        assert(current);
        *current = (struct node){ values[i], next };
        next = current;
    }

    return next;
}

然后,您可以使用构建任意列表

struct node * list = build_list(1, 2, 3);

这是使用单一作业的另一个版本,受codelogic的回答启发:

struct node * build_123(void)
{
    struct node * list = malloc(sizeof(struct node [3]));
    return memcpy(
        list,
        (struct node []){ { 1, list + 1 }, { 2, list + 2 }, { 3, NULL } },
        sizeof(struct node [3])
    );
}

最后,我稍微修改了MSN的解决方案 - 现在,根本没有任何作业:

struct node
{
    int data;
    struct node * next;
};

struct node * make_node(struct node * new_node, int data, struct node * next)
{
    return memcpy(new_node, &(struct node){ data, next }, sizeof(*new_node));
}

struct node * create_node(int data, struct node * next)
{
    return make_node(malloc(sizeof(struct node)), data, next);
}

struct node * build_123(void)
{
    return create_node(1, create_node(2, create_node(3, NULL)));
}