Práctica 6: Listas encadenadas

Objetivos

Durante esta actividad, los alumnos serán capaces de:

Resolver diferentes problemas de programación con listas encadenadas en lenguaje C.

Esta actividad promueve las siguientes habilidades, valores y actitudes: análisis y síntesis, capacidad para resolver problemas, creatividad, y uso eficiente de la informática y las telecomunicaciones.

Descripción

Esta actividad puede ser elaborada de manera individual o en parejas.

Se tiene el siguiente programa incompleto en lenguaje C, llamado listas.c, que sirve para manipular listas sencillamente encadenadas:

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

typedef struct node node_t;

void add(node_t **pp, int data) {
    node_t *new = malloc(sizeof(node_t));
    new->data = data;
    new->next = NULL;
    while (*pp) {
        pp = &((**pp).next);
    }
    *pp = new;
}

void print(node_t *p) {
    printf("[");
    bool first = true;
    while (p) {
        if (first) {
            first = false;
        } else {
            printf(", ");
        }
        printf("%d", p->data);
        p = p->next;
    }
    printf("]\n");
}

size_t size(node_t *p) {
    // Coloca aquí tu código
    return 0;    
}

int get(node_t *p, size_t index) {
    // Coloca aquí tu código
    return 0;    
}

void insert(node_t **pp, size_t index, int data) {
    // Coloca aquí tu código 
}

void reverse(node_t **pp) {
    // Coloca aquí tu código
}

void delete(node_t **pp, int data) {
    // Coloca aquí tu código
}

void clear(node_t **pp) {
    // Coloca aquí tu código
}

int main(void) {
    node_t *lst = NULL;
    print(lst);
    printf("size: %zu\n", size(lst));
    
    add(&lst, 8);
    add(&lst, 15);
    add(&lst, 23);
    print(lst);
    printf("size after adds: %zu\n", size(lst));

    printf("gets: %d, %d, %d, %d, %d\n", get(lst, 0), get(lst, 1),
        get(lst, 2), get(lst, 3), get(lst, 100));

    insert(&lst, 2, 16);
    print(lst);
    printf("size after insert: %zu\n", size(lst));
    insert(&lst, 0, 4);
    print(lst);
    printf("size after insert: %zu\n", size(lst));
    insert(&lst, 100, 42);
    print(lst);
    printf("size after insert: %zu\n", size(lst));

    node_t *lst2 = NULL;
    insert(&lst2, 0, 7);
    print(lst2);
    printf("size after insert: %zu\n", size(lst2));

    node_t *lst3 = NULL;
    reverse(&lst3);
    print(lst3);
    printf("size after reverse: %zu\n", size(lst3));

    reverse(&lst);
    print(lst);
    printf("size after reverse: %zu\n", size(lst));

    reverse(&lst);
    print(lst);
    printf("size after reverse: %zu\n", size(lst));

    reverse(&lst2);
    print(lst2);
    printf("size after reverse: %zu\n", size(lst2));

    delete(&lst, 16);
    print(lst);
    printf("size after delete: %zu\n", size(lst));

    delete(&lst, 42);
    print(lst);
    printf("size after delete: %zu\n", size(lst));

    delete(&lst, 4);
    print(lst);
    printf("size after delete: %zu\n", size(lst));

    delete(&lst, 7);
    print(lst);
    printf("size after delete: %zu\n", size(lst));

    clear(&lst);
    print(lst);
    printf("size after clear: %zu\n", size(lst));

    clear(&lst2);
    print(lst2);
    printf("size after clear: %zu\n", size(lst2));

    clear(&lst3);
    print(lst3);
    printf("size after clear: %zu\n", size(lst3));

    return 0;
}

En este mismo archivo, implementa las funciones que se describen a continuación:

size_t size(node_t *p);

Devuelve el número de elementos (nodos) con los que cuenta una lista encadenada, en donde p apunta al primer nodo de la lista o a NULL si la lista está vacía.
int get(node_t *p, size_t index);

Devuelve el valor del elemento en la posición index de una lista encadenada, en donde p apunta al primer nodo de la lista o a NULL si la lista está vacía. Las posiciones se empiezan numerando desde el 0. Devuelve 0 si index es mayor al número de elementos de la lista menos uno.
void insert(node_t **pp, size_t index, int data);

Crea un nuevo nodo con valor data y lo inserta en la posición index de una lista encadenada, en donde *pp apunta al primer nodo de la lista o a NULL si la lista está vacía. Las posiciones se empiezan numerando desde el 0.
void reverse(node_t **pp);

Invierte el orden de todos los nodos de una lista encadenada, en donde *pp apunta al primer nodo de la lista o a NULL si la lista está vacía. No se deben crear nodos nuevos, ni tampoco se deben modificar los contenidos (el campo data) de los nodos existentes.
void delete(node_t **pp, int data);

Remueve de una lista encadenada un nodo cuyo valor es igual a data, en donde *pp apunta al primer nodo de la lista o a NULL si la lista está vacía. Solo elimina el nodo con la primera ocurrencia de data, si es que existe, de lo contrario hace nada. El nodo eliminado debe ser liberado usando la función free().
void clear(node_t **pp);

Elimina completamente todos los nodos de una lista encadenada, en donde *pp apunta al primer nodo de la lista o a NULL si la lista está vacía. Los nodos eliminados deben ser liberados usando la función free(). Al terminar esta función, *pp debe quedar apuntado a NULL.

Al correr el programa, esta es la salida esperada:

[]
size: 0
[8, 15, 23]
size after adds: 3
gets: 8, 15, 23, 0, 0
[8, 15, 16, 23]
size after insert: 4
[4, 8, 15, 16, 23]
size after insert: 5
[4, 8, 15, 16, 23, 42]
size after insert: 6
[7]
size after insert: 1
[]
size after reverse: 0
[42, 23, 16, 15, 8, 4]
size after reverse: 6
[4, 8, 15, 16, 23, 42]
size after reverse: 6
[7]
size after reverse: 1
[4, 8, 15, 23, 42]
size after delete: 5
[4, 8, 15, 23]
size after delete: 4
[8, 15, 23]
size after delete: 3
[8, 15, 23]
size after delete: 3
[]
size after clear: 0
[]
size after clear: 0
[]
size after clear: 0

¿Qué se debe entregar?

Sigue las siguientes indicaciones para entregar tu actividad:

Agrega en comentarios al inicio del archivo fuente los nombres y matrículas de los autores. Por ejemplo:

/*-------------------------------------------------------------------
 * Práctica 6: Listas encadenadas
 * Fecha: 24-Feb-2014
 * Autores:
 *          1166611 Pepper Pots  
 *          1160611 Anthony Stark
 *-------------------------------------------------------------------*/

Sube el archivo listas.c usando el Sistema de Entrega de Tareas Automatizado. Si la práctica fue desarrollada en equipo, basta que solo uno de los miembros la entregue. No se aceptan tareas por ningún otro medio.

Fecha límite: Lunes, Febrero 24.

Evaluación

Esta actividad será evaluada usando los siguientes criterios:

100	La actividad cumple con todos los requerimientos.
-10	No se incluyó en comentario los datos de los autores.
10	Los programas fuentes producen errores al momento de compilarlos.
50-90	Los programas tiene algunos errores a tiempo de ejecución.
DA	Los programas son un plagio.

Programación avanzada

Práctica 6: Listas encadenadas

Objetivos

Descripción

¿Qué se debe entregar?

Evaluación