Durante esta actividad, los alumnos serán capaces de:
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.
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:
// Archivo: listas.c #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
Utiliza la utilería valgrind para cerciorarte de que no existan fugas de memoria (memory leaks) en tu programa.
Agrega en comentarios al inicio del archivo fuente los nombres y matrículas de los autores. Por ejemplo:
/*-------------------------------------------------------------------
* Práctica 6: Listas encadenadas
* Fecha: 14-Mar-2016
* Autores:
* A01166611 Pepper Pots
* A01160611 Anthony Stark
*-------------------------------------------------------------------*/
Para entregar el archivo listas.c, ingresa los siguientes datos:
Si la práctica fue desarrollada en equipo, basta que solo uno de los miembros la entregue. No se aceptan prácticas por ningún otro medio.
Fecha límite: Lunes, 14 de marzo.
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 | El programa fuente produce errores al momento de compilarlo. |
| 50-90 | Las funciones tienen algunos errores a tiempo de ejecución. |
| DA | La solución es un plagio. |