Un idioma interesante de la lista C vinculada

Question

Estuve en una entrevista para una posición C en la que me presentaron un modismo que no había encontrado anteriormente. Este es un truco que simplifica la implementación de varios algoritmos que involucran listas enlazadas y me pregunto si alguien más se ha encontrado con esto.

decir que hemos definido un registro de lista enlazada de modo:

typedef struct _record 
{ 
    char* value; 
    struct _record* next; 
} record; 

Necesitamos una función que inserta un nuevo registro de modo que toda la lista ordenada se mantiene con respecto al valor de en los registros. La siguiente implementación es más simple que cualquier otra que hubiera usado, aunque menos legible.

void insert_sorted(record** r, const char* value) 
{ 
    record* newrec = NULL; 
    while(*r && strcmp(value, (*r)->value) > 0) 
     r = &((*r)->next); /* move r to point to the next field of the record */ 
    newrec = malloc(sizeof(record)); 
    newrec->value = strdup(value); 
    newrec->next = *r; 
    *r = newrec; 
} 

Cuando se invoca la función, r puntos al puntero de cabeza de la lista. Durante el ciclo while, r se actualiza para apuntar al campo next del registro que viene justo antes del punto en el que queremos colocar el nuevo registro. La última línea de la función actualiza el puntero principal de la lista (si el la inserción ocurre al principio) o el campo next del registro anterior, que es bastante bueno.

Un par de preguntas:

• ¿Este modismo tienen un nombre o parte se menciona en ninguna literatura?

• ¿Hay otros como él en el lenguaje C?

yo creía que sabía C bastante bien y tenía punteros y direccionamiento indirecto bastante bien resuelto, pero este me tomó un tiempo para entender completamente.

Answer 1

He utilizado algo similar para insertar en un árbol binario. Porque cuando se repite el árbol, por lo general, parar cuando el puntero se convierte en NULL (ejecutó fuera del árbol).

Así insertar, tiene 3 opciones,

1: Utilice una variable que mide el valor anterior de su puntero iteración.

2: pare cuando el puntero que seguiría es NULO antes de seguirlo, pero funciona un poco menos elegante en mi opinión.

3: o una solución más elegante es simplemente utilizar un puntero a un puntero, por lo que puede hacer: *it = new_node(); y lo agregará donde el NULL solía estar en su árbol.

Para una lista vinculada, aunque este código funciona bien, suelo usar una lista doblemente vinculada que hace que sea trivial insertarla en cualquier ubicación.

Answer 2

No veo nada que yo llamaría un idioma per se. Parece que la codificación estándar para cuando se trata de estructuras de datos en C.

Mi única queja sería que el puntero de las personas que llaman (* r) se modifica. Dependiendo del uso de la función, espero que sea un efecto secundario inesperado. Además de eliminar el efecto secundario inesperado, usar una variable local para desempeñar el papel de * r haría que el código sea más legible.

Answer 3

¿Cuál sería el modismo aquí? Seguramente no la implementación de una lista vinculada. ¿El uso de un puntero a construcción de puntero? ¿El lazo compacto?

Personalmente, utilizaría un valor de retorno de puntero en lugar de operar con un valor de entrada. Porque ver este tipo de datos de entrada sonaría, lo que me hace copiar mi valor antes de entregárselo a tu función.

Answer 4

No sé si tiene un nombre o si es un idioma especial, pero dado que la memoria es relativamente abundante hoy en día, mis listas vinculadas (donde las bibliotecas de idiomas no las ponen a disposición) son una variante especial que simplifica el código en gran medida.

Para empezar, siempre están doblemente vinculados, ya que esto facilita el recorrido en ambas direcciones, tanto para el procesamiento como para las operaciones de inserción/eliminación.

Una lista 'vacía' en realidad consiste en dos nodos, la cabeza y la cola. Al hacer esto, las inserciones y eliminaciones no necesitan preocuparse de si el nodo que están eliminando es la cabeza o la cola, simplemente pueden asumir que es un nodo intermedio.

La inserción de un nuevo nodo y antes de nodo x se convierten entonces en un simple:

x -> prev -> next = y 
y -> next = x 
y -> prev = x -> prev 
x -> prev = y 

Supresión del nodo x es un simple:

x -> prev -> next = x -> next 
x -> next -> prev = x -> prev 
free x 

Traversal se ajusta a ignorar la cabeza y la cola extraña :

n = head -> next 
while n != tail 
    process n 
    n = n -> next 

todo esto sirve para que el código sea mucho más fácil de entender, sin todo el manejo especial de las cajas de borde, a costa de un par de nodos de memoria.

Answer 5

yo diría que el lenguaje es "el tipo de código que dio 'c' un mal nombre"

• injustificadamente inteligentes
• injustificadamente compactos
• efectos secundarios sorprendentes sobre la persona que llama
• n el tratamiento de errores en malloc
• solo las cadenas de inglés de Estados Unidos

Answer 6

En lugar de devolver el valor del nuevo nodo como un parámetro de entrada/salida, que son mejor de tener que ser el valor de retorno de la función. Esto simplifica tanto el código de llamada como el código dentro de la función (puede deshacerse de todas esas feos indirectas dobles).

record* insert_sorted(const record* head, const char* value) 

Se ha perdido el tratamiento de error para el malloc/strdup failing case btw.

Answer 7

Esto es algo bien conocido - el doble iteración puntero (que es mi nombre para él, no sé el nombre oficial). El objetivo es ser capaz de localizar una posición en la lista enlazada simple y, a continuación, insertar antes de esa posición (después de la inserción es trivial). Implementado ingenuamente, esto requiere dos punteros (actuales y prev) y código especial de inicio de la lista (cuando prev == NULL).

El código de la forma en que suelo escribir es algo a lo largo de las líneas de

void insertIntoSorted(Element *&head, Element *newOne) 
{ 
    Element **pp = &head; 
    Element *curr; 
    while ((curr = *pp) != NULL && less(curr, newOne)) { 
    pp = &(pp->next); 
    } 
    newOne->next = *pp; 
    *pp = newOne; 
} 

Actualización:

He olvidado theother propósito para este truco - una más importante. Se utiliza para eliminar elementos de listas vinculadas individuales:

// returns deleted element or NULL when key not found 
Element *deleteFromList(Element *&head, const ElementKey &key) 
{ 
    Element **pp = &head; 
    Element *curr; 
    while ((curr = *pp) != NULL && !keyMatches(curr, key)) { 
    pp = &(pp->next); 
    } 
    if (curr == NULL) return NULL; 
    *pp = (*pp)->next; // here is the actual delete 
    return curr; 
} 

Answer 8

Para responder a la pregunta original, esto se conoce como un enfoque centrado en el puntero en lugar del enfoque centrado en el nodo ingenuo. El capítulo 3 de "Técnicas avanzadas de programación" de Rex Barzee, disponible en amazon.com, incluye una implementación de ejemplo mucho mejor del enfoque centrado en el puntero.

Answer 9

Este idioma se da en el Capítulo 12 de "Punteros en C". Se utiliza para insertar un nodo en una lista vinculada sin encabezado de lista.

Answer 10

También he encontrado este uso de un puntero doble, lo he usado, pero realmente no me gusta. El código que me ocurrió con este núcleo tiene que buscar ciertos objetos y eliminarlos de la lista:

Element** previous = &firstElement, *current; 
while((current = *previous)) { 
    if(shouldRemove(current)) { 
     *previous = current->next; //delete 
    } else { 
     previous = &current->next; //point to next 
    } 
} 

La razón por la que no me gusta mi código es la sutil diferencia entre los dos, si las cláusulas: la sintaxis es casi idéntico, pero el efecto es completamente diferente. No creo, deberíamos escribir código tan sutil como este, pero hacerlo de manera diferente hace que el código sea realmente extenso. Por lo tanto, de cualquier manera es malo, puede ir por brevedad o por legibilidad, es su elección.

Answer 11

a pesar de los trucos, ¿no se cambia la función de la variable "r"? ¿Cómo dice la persona que llama para qué sirve "* r" después de llamar? o después de la ejecución, ¿cuál es el encabezado de la lista?

No puedo creer que esto se pueda ejemplificar (incluso en algunos libros ?!). ¿Extraño algo?

Si no devuelve ningún puntero (como los otros sugeridos), sugeriría seguir los cambios para mantener el papel de la entrada.

void insert_sorted(record** head, const char* value) 
{ 
    record** r = head; 
    bool isSameHead = false; 
    record* newrec = NULL; 
    while(*r && strcmp(value, (*r)->value) > 0) { 
     r = &((*r)->next); isSameHead = true; } 
    newrec = malloc(sizeof(record)); 
    newrec->value = strdup(value); 
    newrec->next = *r; 
    *r = newrec; 
    if (!isSameHead) *head = newrec; 
} 

realidad, probablemente otra mejor manera de hacerlo es usando el "nodo de cabeza de maniquí", que une su próxima al principio de la lista.

void insert_sorted(record** head, const char* value) 
    { 
     record dummyHead; 
     dummyHead.next = *head; 
     record* r = &dummyHead; 
     while(r->next) { 
      if(strcmp(value, r->next->value) < 0) 
       break; 
      r = r->next;} 
     newrec = malloc(sizeof(record)); 
     newrec->value = strdup(value); 
     newrec->next = r->next; 
     r->next = newrec; 
     *head = dummyHead.next; 
    }