Estoy tratando de crear una lista vinculada sin usar estructuras en C. Quiero poder almacenar una variable int en cada nodo y un puntero al siguiente nodo, agregar números ilimitados a la lista, eliminar el primer elemento, imprimir todos los elementos, etc.

Estaba pensando que cada nodo de tipo int** debería tener 2 punteros de tipo int*. el primero apuntará a una dirección int y el segundo apuntará a NULL. Luego, si me gusta agregar un número a la lista, usaré el último puntero para apuntar a un nuevo nodo asignado de tipo int** y así sucesivamente.

Sin embargo, tengo problemas para escribir el código adecuado para esto y parece que no puedo alcanzar los valores reales de int. Ver la imagen a continuación: explicación

-1
Infected 30 dic. 2016 a las 01:15

3 respuestas

La mejor respuesta

Aquí hay una solución completa de LinkedList administrada como int ** punteros.

Paso 1 : la función addNode() para agregar un nodo a int **head.

int **addNode(int **head, int ival)
{
    int **node = malloc(2 * sizeof(int *));

    // don't forget to alloc memory to store the int value
    node[0] = malloc(sizeof(int));
    *(node[0]) = ival;
    // next is pointing to NULL
    node[1] = NULL;

    if (head == NULL) {
        // first node to be added
        head = node;
    }
    else {
        int **temp;

        temp = head;
        // temp[1] is the next
        while (temp[1]!=NULL) {
            // cast needed to go to the next node
            temp = (int **)temp[1];
        }
        // cast needed to store the next node
        temp[1] = (int *)node;
    }
    return (head);
}

Paso 2 : una función display() para explorar la lista vinculada actual.

void display(int **head)
{
    int **temp;
    int i = 0;

    temp = head;
    printf("display:\n");
    while (temp!=NULL) {
        // temp[0] is pointing to the ivalue
        printf("node[%d]=%d\n",i++,*(temp[0]));
        temp = (int **)temp[1];
    }
    printf("\n");
}

Paso 3 : la función popNode() para eliminar el primer nodo.

int **popNode(int **head)
{
    int **temp;

    if (head!=NULL) {
        temp = (int **)head[1];
        // don't forget to free ivalue
        free(head[0]);
        // then free the next pointer
        free(head[1]);
        head = temp;
    }
    return (head);
}

Paso 4 - luego un ejemplo de la función main() usando la lista vinculada.

int main()
{
    int **head = NULL;

    head = addNode(head,111);
    head = addNode(head,222);
    head = addNode(head,333);

    display(head);
    // display:
    // node[0]=111
    // node[1]=222
    // node[2]=333

    head = popNode(head);

    display(head);
    // display:
    // node[0]=222
    // node[1]=333

    while ((head = popNode(head))!=NULL);

    display(head);
    // display:

    return (0);
}
0
J. Piquard 30 dic. 2016 a las 20:21

Puede lograr esto asignando dos uintptr_t cada vez: el primer espacio de memoria asignado será responsable de almacenar el valor del entero y el segundo apuntará a la siguiente ubicación de memoria.

uintptr_t nodeFirst = malloc(2 * sizeof(uintptr_t));
...
...
uintptr_t nodeNext = malloc(2 * sizeof(uintptr_t));
....
....
*nodeFirst = someIntValue;
*(nodeFirst + 1) = nodeNext;
...

El hecho es que mi solución anterior todavía está usando la analogía de la estructura, pero sin la palabra clave struct.

1
ssd 29 dic. 2016 a las 22:50

Asigne dos matrices, las cuales se almacenan como punteros. En C, pueden ser los punteros que obtienes de calloc(). El primero contiene sus datos de nodo. Podemos llamarlo nodes. El segundo es una matriz de punteros (o compensaciones integrales). Podemos llamarlo nexts. Siempre que actualice la lista, actualice nodes para que cada nexts[i] se vincule al siguiente nodo después del que contiene nodes[i], o un valor no válido como NULL o {{ X7}} si es la cola. Para una lista de doble enlace, necesitarías befores o usar el truco XOR. Necesitará un puntero de cabeza y algún tipo de indicador de qué elementos en su grupo no están asignados, lo que podría ser algo simple como un primer índice libre o algo más complicado como un campo de bits.

Aún necesitaría envolver todo esto en una estructura para obtener más de una lista vinculada en su programa, pero eso le da una lista vinculada sin usar otra estructura de datos que punteros.

Este desafío es una locura, pero una estructura de matrices no lo es, y es posible que vea un gráfico o una lista de vértices almacenados de manera similar. Puede asignar o desasignar su grupo de nodos de una vez en lugar de hacerlo en pequeños fragmentos, podría ser más eficiente usar compensaciones de 32 bits en lugar de los siguientes punteros de 64 bits, y el almacenamiento contiguo le proporciona la localidad de referencia.

-1
Davislor 30 dic. 2016 a las 20:10