c - 最小数の代入演算子で 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;
}

Q: 上記のメモリ構造を構築する割り当て (=) の数が最も少ないコードを記述してください。A: malloc() を 3 回呼び出す必要があります。int をセットアップするための 3 つの int 割り当て (=)。セットアップヘッドと 3 つの次のフィールドへの 4 つのポインターの割り当て。C 言語の少しの賢さと知識があれば、これはすべて 7 つの代入演算 (=) で実行できます。

score 10 · Accepted Answer

私は6つの課題でそれをやりました。何を得るか？

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

コードロジックの答えに触発された、単一の割り当てを使用した別のバージョンを次に示します。

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

score 4 · Accepted Answer

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

そして、これは2つでそれを行うものです:

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

score 3 · Accepted Answer

常に 3 つのノードを構築しているという事実を使用して、4 つの割り当てで Christoph のコードをわずかに変更します。

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

編集: 技術的には (アセンブリに関して)、構造体初期化子を使用すると、メンバーごとに 1 つずつ、少なくとも 2 つの割り当てが発生する可能性があります。そのため、C コードでは 4 つの割り当てのようにしか見えませんが、実際には 7 つ以上です。同様に、MSN の再帰的ソリューションでも 2 つ以上の代入が発生しますが、これは再帰で抽象化されます (関数のオーバーヘッドが原因で発生する可能性が高い追加の代入は、インライン化されていないと仮定して数えません)。

編集：

OK、グローバルにスタックに割り当てられているため、アセンブリであっても割り当てはありません。リンクされたリスト（またはその他のもの）が行く限りひどいコードですが、何でも:-)

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

score 3 · Accepted Answer

1 回の呼び出しで 3 つのノードすべてを割り当てることができmalloc()ます。これが彼らが求めている答えだと思います。割り当ての数を減らすことは実際的な問題ではありませんが、複数の割り当てを 1 つにまとめると、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;
}

score 2 · Accepted Answer

これが 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;
}

c - 最小数の代入演算子で OneTwoThree リンク リストを作成するにはどうすればよいですか?

5 に答える 5

Related

Reference

c - 最小数の代入演算子で OneTwoThree リンクリストを作成するにはどうすればよいですか?