4

我在准备面试时遇到了这个问题，很想知道它的不同写作方式。我在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 分配 (=) 来设置 int。4 个指针分配给设置头和 3 个下一个字段。稍加一点C语言的聪明和知识，这一切都可以用7个赋值操作（=）来完成。

4

5 回答 5

10

我做了六个作业。我能得到什么？

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)));
}
于 2009-02-06T20:37:27.880 回答
4 
node= malloc
node->data= 1
node->next= malloc
node->next->data= 2
node->next->next= malloc
node->next->next->data= 3
node->next->next->next= NULL

这是一个用两个来完成的：

node *make_node(node *new_node, int data, node *next) 
{ new_node->data= data; new_node->next= next; return new_node; }

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

node *BuildOneTwoThree(void) 
{ return create_node(1, create_node(2, create_node(3, NULL))); }
于 2009-02-06T20:34:24.857 回答
3

使用它总是构建 3 个节点的事实对 Christoph 的代码进行了 4 个分配的轻微修改：

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

struct node * build_123()
{
    struct node* head = malloc( sizeof(struct node) * 3);
    *head     = (struct node){ 1, head+1 };
    *(head+1) = (struct node){ 2, head+2 };
    *(head+2) = (struct node){ 3, NULL };
    return head;
}

编辑：从技术上讲（就汇编而言），使用结构初始化程序可能会导致至少 2 个分配，每个成员一个。所以它在 C 代码中看起来只是 4 个赋值，而实际上它是 7 个或更多。同样，MSN 的递归解决方案也会产生超过 2 个赋值，这些赋值是在递归中抽象出来的（不计算由于函数开销而可能发生的额外赋值，假设它没有内联）。

编辑：

好的，全局分配在堆栈上，因此即使在汇编中也没有分配。就链接列表（或其他任何东西）而言，糟糕的代码，但无论如何:-)

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

struct node g_nodes[3] = { {1, g_nodes+1}, {2, g_nodes+2}, {3, NULL} };    
struct node * build_123()
{
  return g_nodes;
}
于 2009-02-06T21:11:14.253 回答
3

您可以通过一次malloc()调用分配所有三个节点。我怀疑这是他们正在寻找的答案。虽然减少分配的数量不是一个实际问题，但将多个分配捆绑到一个malloc()中可以简化内存管理。我希望大多数高级 C 开发人员都熟悉这种技术。

struct node* BuildOneTwoThree() {
    struct node *list = malloc(3 * sizeof(struct node));

    list[0].data = 1;
    list[0].next = list+1;
    list[1].data = 2;
    list[1].next = list+2;
    list[2].data = 3;
    list[2].next = NULL;

    return list;
}
于 2009-02-06T21:12:56.980 回答
2

由于没有人说这不是 C++，这是一个 C++ 版本，除了在测试代码中没有分配：

#include <iostream>
using namespace std;

struct Node {

    int mVal;
    Node * mNext;

    Node( int v, Node * n ) 
        : mVal( v ), mNext( n ) {}

    ~Node() {
        delete mNext;
    }
};

int main() {

    // build the list
    Node n( 1, new Node( 2, new Node( 3, 0 ) ) );

    // test it
    Node * p = & n;
    while( p ) {
        cout << p->mVal << endl;
        p = p->mNext;
    }

    return 0;
}
于 2009-02-06T23:47:56.793 回答