makigas - Una interesante expresión de la lista C vinculada

listas ligadas

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.

Digamos que tenemos un registro de lista enlazado definido así:

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

Necesitamos una función que inserte un nuevo registro para que toda la lista permanezca ordenada con respecto al valor 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 llama a la función, r apunta al puntero principal de la lista. Durante el ciclo while, r se actualiza para apuntar al next campo 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 next campo del registro anterior, que es bastante bueno.

Un par de preguntas:

• ¿Este idioma tiene un nombre o se menciona en alguna literatura?

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

Pensé que conocía muy bien a C y que los punteros y la indirección estaban bastante bien descifrados, pero me tomó un tiempo comprenderlo por completo.

Answer 1

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

Personalmente usarí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 2

En lugar de devolver el valor del nuevo nodo como parámetro de entrada / salida, es mejor que sea 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)

Te estás perdiendo el manejo de errores para el caso de falla malloc / strdup por cierto.

Answer 3

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 enormemente el código. .

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 del nodo x se convierte en un simple:

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

La eliminación del nodo x es simple:

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

El recorrido se ajusta para ignorar la cabeza y la cola externas:

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

Todo esto sirve para hacer que el código sea mucho más fácil de entender sin todo el manejo especial de los casos extremos, a costa de un par de nodos de memoria.

Answer 4

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 es 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 5

Yo diría que el modismo es "el tipo de código que le dio a ''c'' un mal nombre"

• Injustificadamente inteligente
• Incompatiblemente compacto
• Sorprendentes efectos secundarios en la persona que llama
• Sin errores de manejo en malloc
• Solo funciona para cadenas de inglés de EE. UU.

Answer 6

He usado algo similar para insertar en un árbol binario. Porque al iterar el árbol, generalmente se detiene cuando el puntero se convierte en NULL (se ejecutó fuera del árbol).

Entonces para insertar, tienes 3 opciones,

1: usa una variable que rastrea el valor anterior de tu puntero iterativo.

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

3: o una solución más elegante es simplemente usar un puntero a un puntero, por lo que puedes hacer: *it = new_node(); y lo agregará donde el NULL solía estar en tu á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 7

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

Answer 8

También he encontrado este uso de un doble puntero, lo he usado, pero realmente no me gusta. El código que se me ocurrió tiene este kernel para 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 las dos cláusulas if: la sintaxis es casi idéntica, 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 9

Esto es algo bien conocido: iteración de doble puntero (ese es mi nombre, no sé el nombre oficial). El objetivo es poder ubicar una posición en una sola lista vinculada, y luego insertarla antes de esa posición (insertarla después de que sea trivial). Implementado ingenuamente, esto requiere dos punteros (actual y anterior) y un código especial para el comienzo de la lista (cuando prev == NULL).

El código de la forma en que generalmente lo escribo es algo parecido a

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

Actualizar:

Olvidé el otro propósito para este truco, uno 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 10

a pesar de los trucos, ¿no se modificó la función de la "r" variable? ¿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 podía creer que esto pueda ejemplificarse (¡incluso en algún libro!). ¿Yo me perdí algo?

Si no devuelve ningún puntero (como los otros sugirieron), 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;
}

de hecho, probablemente otra forma mejor de hacerlo es usar el "nodo de cabeza falsa", que lo vincula 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;
    }

Answer 11

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 mejor implementación de ejemplo del enfoque centrado en el puntero.