如何构建链表赋值运算符的最小数量OneTwoThree？ [英] How do I build a OneTwoThree linked list with a minimum number of assignment operators?

问题描述

我碰到这个问题来了，而接受记者采访时preparing和好奇，想知道有多种不同的方式可以将它写入。我发现这个在 http://cslibrary.stanford.edu/103/ 并给予了问题，因为是的。

I came across this problem while preparing for an interview and curious to know the diffrent ways it can be written. I found this at http://cslibrary.stanford.edu/103/ and have given the problem as it is.

这里是一个code，以生成列表{1,2,3}

here is a code to build the list {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;
}

问：写code与将建立的分配数量最少（=）
以上的内存结构。答：这需要3调用malloc（）。 3 INT赋值（=）设置
的整数。 4指针赋值设置头和3下一个领域。随着一点点的小聪明
和C语言的知识，这都可以与7分配操作（=）完成。

Q: Write the code with the smallest number of assignments (=) which will build the above memory structure. A: It requires 3 calls to malloc(). 3 int assignments (=) to setup the ints. 4 pointer assignments to setup head and the 3 next fields. With a little cleverness and knowledge of the C language, this can all be done with 7 assignment operations (=).

推荐答案

我有六个任务做了。我会得到什么？

I did it with six assignments. What do I get?

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;
}

---

---

此外，该运动是不是非常有用。如果我想从一组已知整数建立一个链表，我会做这样的事情：

Also, the exercise isn't very useful. If I wanted to build a linked list from a known set of integers, I'd do something like this:

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;
}

然后，您可以建立一个任意列表

Then, you can build an arbitrary list with

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

---

---

下面是一个使用单一的分配另一个版本，由<一个启发href=\"http://stackoverflow.com/questions/522010/build-onetwothree-linked-list-with-minimum-assignment-operators/522193#522193\">$c$clogic's回答：

Here's another version using a single assignment, inspired by codelogic's answer:

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])
    );
}

---

---

最后，我稍微修改<一个href=\"http://stackoverflow.com/questions/522010/build-onetwothree-linked-list-with-minimum-assignment-operators/522055#522055\">MSN's解决方案 - 现在，有没有在所有分配：

Finally, I slightly modified MSN's solution - now, there's no assignment at all:

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)));
}

这篇关于如何构建链表赋值运算符的最小数量OneTwoThree？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！