DAS5102 - Listas Encadeadas
De Aulas
Voltar para DAS5102 Fundamentos da Estrutura da Informação
Exemplo
lista.c
1#include <stdlib.h>
2#include <string.h>
3#include <unistd.h>
4#include "list.h"
5
6void list_init(List *list, void (*destroy)(void *data))
7{
8 list->size = 0;
9 list->destroy = destroy;
10 list->head = NULL;
11 list->tail = NULL;
12 return;
13}
14
15void list_destroy(List *list)
16{
17 void *data;
18 while (list_size(list) > 0)
19 {
20 if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL)
21 {
22 // Call a user-defined function to free dynamically allocated data.
23 list->destroy(data);
24 }
25 }
26 // clear the structure as a precaution
27 memset(list, 0, sizeof(List));
28 return;
29}
30
31int list_ins_next(List *list, ListElmt *element, const void *data)
32{
33 ListElmt *new_element;
34 if ((new_element = (ListElmt *) malloc(sizeof(ListElmt))) == NULL) return -1;
35 new_element->data = (void *) data;
36 if (element == NULL)
37 {
38 if (list_size(list) == 0)
39 list->tail = new_element;
40 new_element->next = list->head;
41 list->head = new_element;
42 }
43 else
44 {
45 if (element->next == NULL)
46 list->tail = new_element;
47 new_element->next = element->next;
48 element->next = new_element;
49 }
50 list->size++;
51 return 0;
52}
53
54int list_rem_next(List *list, ListElmt *element, void **data)
55{
56 ListElmt *old_element;
57 if (list_size(list) == 0) return -1;
58 if (element == NULL)
59 {
60 *data = list->head->data;
61 old_element = list->head;
62 list->head = list->head->next;
63 if (list_size(list) == 1) list->tail = NULL;
64 }
65 else
66 {
67 if (element->next == NULL) return -1;
68 *data = element->next->data;
69 old_element = element->next;
70 element->next = element->next->next;
71 if (element->next == NULL) list->tail = element;
72 }
73 free(old_element);
74 list->size--;
75 return 0;
76}
77
78void *list_dataN(List *list, int n)
79{
80 ListElmt *e = list->head;
81 int i;
82 for (i = 0; i < n; i++)
83 {
84 if (e == NULL) return NULL;
85 e = e->next;
86 }
87 return e->data;
88}
lista.h
1#ifndef LIST_H_INCLUDED
2#define LIST_H_INCLUDED
3
4typedef struct ListElmt_
5{
6 void *data;
7 struct ListElmt_ *next;
8} ListElmt;
9
10typedef struct List_
11{
12 int size;
13 int (*match)(const void *key1, const void *key2);
14 void (*destroy)(void *data);
15 ListElmt *head;
16 ListElmt *tail;
17} List;
18
19void list_init(List *list, void (*destroy)(void *data));
20
21void list_destroy(List *list);
22
23int list_ins_next(List *list, ListElmt *element, const void *data);
24
25int list_rem_next(List *list, ListElmt *element, void **data);
26
27void *list_dataN(List* list, int n);
28
29#define list_size(list) ((list)->size)
30
31#define list_head(list) ((list)->head)
32
33#define list_tail(list) ((list)->tail)
34
35#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)
36
37#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)
38
39#define list_data(element) ((element)->data)
40
41#define list_next(element) ((element)->next)
42
43#endif // LIST_H_INCLUDED
main.c
1#include <stdio.h>
2#include <stdlib.h>
3#include "list.h"
4
5void destroy(void *data)
6{
7 free(data);
8 data = NULL;
9}
10
11int main()
12{
13 int i;
14 List *list = (List*) malloc(sizeof(List));
15 list_init(list, destroy);
16 for (i = 0; i < 5; i++)
17 {
18 int *data = malloc(sizeof(int));
19 *data = i;
20 printf("%d\n", *data);
21 list_ins_next(list, list->head, data);
22 }
23 int data = *((int*) list_dataN(list, 3));
24 printf("%d\n", data);
25 list_destroy(list);
26 return 0;
27}
Roteiro
1. Altere o TAD list.h e list.c vistos em aula para incluir a seguinte operação:
1void *list_dataN(List* list, int n);
Retornar os dados associados com o n-esimo elemento da lista, ou NULL caso a lista tenha menos que n elementos.
2. Faça um programa de teste que use list para testar a nova operação criada.
