Comment créer une liste liée OneTwoThree avec un nombre minimum d'opérateurs d'affectation?

Question

Je suis tombé sur ce problème en préparant une interview et curieux de connaître les différentes façons dont il peut être écrit. J'ai trouvé cela au http://cslibrary.stanford.edu/103/ et j'ai donné le problème tel quel.

est ici un code pour construire la liste {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: Recopiez le code avec le plus petit nombre d'affectations (=) qui construira la structure de la mémoire ci-dessus. R: Cela nécessite 3 appels à malloc(). 3 int attributions (=) pour configurer les int. 4 affectations de pointeur à la tête d'installation et les 3 champs suivants. Avec un peu d'intelligence et la connaissance du langage C, tout cela peut être fait avec 7 opérations d'affectation (=).

Answer 1

Je l'ai fait avec six missions. Qu'est-ce que je reçois?

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

---

En outre, l'exercice est pas très utile. Si je voulais construire une liste chaînée à partir d'un ensemble connu d'entiers, je ferais quelque chose comme ceci:

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

Ensuite, vous pouvez créer une liste arbitraire avec

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

---

Voilà une autre version à l'aide d'une seule cession, inspirée par 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]) 
    ); 
} 

---

Enfin, je légèrement modifié MSN's solution - maintenant, il n'y a pas d'affectation du tout:

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

Answer 2

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 

Et voici une qui le fait avec deux:

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

Answer 3

Légère modification du code de Christoph avec 4 missions en utilisant le fait qu'il a toujours la construction de 3 nœuds:

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

EDIT : Techniquement (en termes d'assemblage), l'utilisation d'un initialiseur de structure entraînerait probablement au moins 2 affectations, une pour chaque membre. Donc, il semble que ce soit 4 affectations en code C, quand il fait 7 ou plus. De même, la solution récursive de MSN aboutira à plus de 2 affectations, qui sont abstraites dans la récursivité (sans compter les affectations supplémentaires qui se produiront probablement en raison de la surcharge de la fonction, en supposant qu'elle ne soit pas en ligne).

---

EDIT:

Ok, répartis sur la pile globale, donc pas de missions, même dans l'assemblage. le code Terrible listes dans la mesure liés (ou quoi que ce soit d'autre) va, mais tout :-)

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

Answer 4

Vous pouvez allouer tous les trois nœuds avec un seul appel malloc().Je soupçonne que c'est la réponse qu'ils recherchent. Bien que la réduction du nombre d'affectations ne soit pas un problème pratique, le regroupement de plusieurs allocations en un seul malloc() peut simplifier la gestion de la mémoire. Je m'attends à ce que la plupart des développeurs C soient familiers avec cette technique.

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

Answer 5

Comme personne ne dit rien à ce sujet ne pas C++, voici une version C++ sans affectation, sauf dans le code de test:

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