Búsqueda en la lista en C -- ampo con linked-list campo con lookup campo con skip-list camp codereview Relacionados El problema

Lookups in list in C


4
vote

problema

Español

Leí sobre las miradas en listas y creo que eso es lo que hice. Me gustaría compararlo con una lista de saltos, una búsqueda binaria o un árbol B +.

  #include <stdio.h> #include <stdlib.h> #include <time.h>  typedef struct node {     int node_id;     int data;     struct node *left;     struct node *right; } node;   node *newNode(int data, int node_id) {     node *new_node = (node *) malloc(sizeof(node));     new_node->data = data;     new_node->node_id = node_id;     new_node->right = new_node->left = NULL;     return new_node; }  node *insert_node(node *root, int data, int node_id) {     if (root == NULL)         return newNode(data, node_id);     else {         node *cur;         if (node_id < root->node_id) {             cur = insert_node(root->left, data, node_id);             root->left = cur;         } else if (node_id > root->node_id) {             cur = insert_node(root->right, data, node_id);             root->right = cur;         }     }     return root; }   node *find_node_data(node *root, int node_id) {     if (root == NULL)         return NULL;     else if (root->node_id == node_id)         return root;     else if (root->node_id > node_id)         return find_node_data(root->left, node_id);     else         return find_node_data(root->right, node_id); }  void print(node *np) {     if (np) {         print(np->left);         printf("(%d, %d)", np->node_id, np->data);         print(np->right);     } }  int main() {     int T = 1000; //test case 1000 nodes     int data, node_id;     //printf("Input number of nodes:");     //scanf("%d", &T);     node *root = NULL;     srand (time (NULL));     while (T-- > 0) {         //printf("Input data. %d:", T);         //scanf("%d %d", &data, &node_id);         int r = rand() % 1000;         int r2 = rand() % 1000;         root = insert_node(root, r, r2);     }     print(root);     printf(" ");     printf("Find data at node:", T);     scanf("%d", &T);     printf("node data %d", find_node_data(root, T)->data);     return 0; }   
Original en ingles

I read about lookups in lists and I think that is what I did. I would like to compare it to a skip list, a binary search or a B+ tree.

#include <stdio.h> #include <stdlib.h> #include <time.h>  typedef struct node {     int node_id;     int data;     struct node *left;     struct node *right; } node;   node *newNode(int data, int node_id) {     node *new_node = (node *) malloc(sizeof(node));     new_node->data = data;     new_node->node_id = node_id;     new_node->right = new_node->left = NULL;     return new_node; }  node *insert_node(node *root, int data, int node_id) {     if (root == NULL)         return newNode(data, node_id);     else {         node *cur;         if (node_id < root->node_id) {             cur = insert_node(root->left, data, node_id);             root->left = cur;         } else if (node_id > root->node_id) {             cur = insert_node(root->right, data, node_id);             root->right = cur;         }     }     return root; }   node *find_node_data(node *root, int node_id) {     if (root == NULL)         return NULL;     else if (root->node_id == node_id)         return root;     else if (root->node_id > node_id)         return find_node_data(root->left, node_id);     else         return find_node_data(root->right, node_id); }  void print(node *np) {     if (np) {         print(np->left);         printf("(%d, %d)", np->node_id, np->data);         print(np->right);     } }  int main() {     int T = 1000; //test case 1000 nodes     int data, node_id;     //printf("Input number of nodes:");     //scanf("%d", &T);     node *root = NULL;     srand (time (NULL));     while (T-- > 0) {         //printf("Input data. %d:", T);         //scanf("%d %d", &data, &node_id);         int r = rand() % 1000;         int r2 = rand() % 1000;         root = insert_node(root, r, r2);     }     print(root);     printf("\n");     printf("Find data at node:", T);     scanf("%d", &T);     printf("node data %d", find_node_data(root, T)->data);     return 0; } 
           

Lista de respuestas

4
 
vote
vote
La mejor respuesta
 
  • Este es un árbol de búsqueda binario.

  • No lanza el valor de retorno de data91 . No tiene ningún propósito, y puede enmascarar un error grave (en caso de que 998877665554433192 no está incluido).

  • La búsqueda generalmente se implementa iterativamente:

      data93  
  • data94 puede usar menos sangría. El retorno temprano hace data95 innecesario:

      data96  
  • Es posible que desee informar a la persona que llama que la inserción falló debido a data97 ya presente.

 
  • This is a binary search tree.

  • Do not cast the return value of malloc. It serves no purpose, and may mask a serious bug (in case stdlib.h is not included).

  • Lookup is usually implemented iteratively:

    while (root) {     if (root->id == id) {         break;     }     root = (root->id < id)? root->right: root->left; } return root; 
  • insert_node may use less indentation. Early return makes else unnecessary:

    node *insert_node(node *root, int data, int node_id) {     if (root == NULL)         return newNode(data, node_id);     node *cur;     if (node_id < root->node_id) {         cur = insert_node(root->left, data, node_id);         root->left = cur;     } else if (node_id > root->node_id) {         cur = insert_node(root->right, data, node_id);         root->right = cur;     }     return root; } 
  • You may want to inform the caller that the insertion failed due to id already present.

 
 
   
   
3
 
vote

Qué dijo @vnp más

NewNode ()

Tienes que verificar que malloc() trabajado:

  node *newNode(int data, int node_id) {     node *new_node = (node *) malloc(sizeof(node));      // Its quite possible for malloc to fail so you need to check     // and only assign if the malloc worked (otherwise segfault probably).     if (new_node)     {         new_node->data = data;         new_node->node_id = node_id;         new_node->right = new_node->left = NULL;     }     return new_node; }   

INSERT_NODE ()

El retorno temprano no necesita una parte más.
También la variable extra 998877666554433265544332 es superfolous y no hace que sea más fácil de leer.

que conduce a esto:

  node *insert_node(node *root, int data, int node_id) {     if (root == NULL) {         return newNode(data, node_id);     }       if (node_id < root->node_id) {         root->left = insert_node(root->left, data, node_id);     } else if (node_id > root->node_id) {         root->right = insert_node(root->right, data, node_id);     }      return root; }   

Pero sabemos que el 9988776655544334 puede potencialmente fallar. Entonces, ¿por qué ir a todo el problema de la cascada, lanzó el árbol si newNode() eventualmente fallará? Para que también pueda hacer esto por adelantado y solo intente agregar el nodo si puede asignarlo.

  node *insert_node(node *root, int data, int node_id) {     node *item = newNode(data, nodeId);     return item ? insert_node_data(root, item) : root; } node* insert_node_data(node* root, node* item) {     if (!root) {         return item;     }     // I think you get the idea }   
 

What @vnp said plus

newNode()

You have to check that malloc() worked:

node *newNode(int data, int node_id) {     node *new_node = (node *) malloc(sizeof(node));      // Its quite possible for malloc to fail so you need to check     // and only assign if the malloc worked (otherwise segfault probably).     if (new_node)     {         new_node->data = data;         new_node->node_id = node_id;         new_node->right = new_node->left = NULL;     }     return new_node; } 

insert_node()

Early return does not need an else part.
Also the extra cur variable is superfolous and does not make it any easier to read.

Which leads to this:

node *insert_node(node *root, int data, int node_id) {     if (root == NULL) {         return newNode(data, node_id);     }       if (node_id < root->node_id) {         root->left = insert_node(root->left, data, node_id);     } else if (node_id > root->node_id) {         root->right = insert_node(root->right, data, node_id);     }      return root; } 

But we know that the newNode() can potentially fail. So why go to all the problem of cascading threw the tree if newNode() will eventually fail. So you may as well do this up front and then only try and add the node if you can allocate it.

node *insert_node(node *root, int data, int node_id) {     node *item = newNode(data, nodeId);     return item ? insert_node_data(root, item) : root; } node* insert_node_data(node* root, node* item) {     if (!root) {         return item;     }     // I think you get the idea } 
 
 

Relacionados problema

4  Implementación genérica de Skiplist en Java  ( Generic skiplist implementation in java ) 
Estoy interesado en implementar estructuras de datos avanzadas. Uno de ellos que hizo cosquillas mi fantasía es la 9988776655544330 . Quería saber si hay...

7  Implementación de Skiplist en Java  ( Skiplist implementation in java ) 
El código funciona bien, pero es probable que sea mejor. ¿Cómo puedo mejorarlo? de Wikipedia: Una lista de saltos es una estructura de datos que permite l...

4  Búsqueda en la lista en C  ( Lookups in list in c ) 
Leí sobre las miradas en listas y creo que eso es lo que hice. Me gustaría compararlo con una lista de saltos, una búsqueda binaria o un árbol B +. #includ...

3  Lista de saltos que utiliza una implementación de lista de enlaces individuales  ( Skip list that uses a singly linked list implementation ) 
Ayer implementé esta lista de saltos, y me gustaría sugerencias sobre cómo mejorar este código y mis prácticas de codificación. import java.util.ArrayList;...

3  Implementación de Skiplist  ( Skiplist implementation ) 
Esta es una versión de mi implementación de lista de saltos. En mi proyecto, almaceno mi clase personalizada que es similar a un par de blobs. Reemplacé mi cl...

8  Implementación genérica de la lista de omisión en C ++ Versión 3  ( Generic skip list implementation in c version 3 ) 
Este es un seguimiento de Skip no genérico Lista de implementación en la versión 2 de C ++ Si no sabe qué es una lista de Skip: https://en.wikipedia.org/...

5  SKIPLIST CPP para valores numéricos  ( Cpp skiplist for numeric values ) 
Revise mi código de lista SKIP que se implementa utilizando una lista vinculada. Es compatible con la inserción y eliminación de valores numéricos. Me gusta...

6  Implementación personalizada de Skiplist en Java  ( Custom skiplist implementation in java ) 
Recientemente estudié SkipList y pensé que crearía uno por mi cuenta. Esta implementación utiliza un skiplist de 2 capas donde el tamaño de la lista de sopo...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos