As estruturas de dados como listas, pilhas ou filas são em geral utilizadas com vários tipos de dados. De facto podemos ter listas, pilhas e filas de inteiros, de cadeias de caracteres ou de estruturas. No entanto as operações de inserção e de remoção sobre estas estruturas são idênticas quer os elementos a gerir sejam inteiros, sequências de caracteres ou estruturas. Portanto, o código pode (e deve) ser reutilizado e, por outro lado, podemos abstrair os detalhes de implementação destas estruturas de dados.
Os tipos de dados abstractos, ou Abstract Data Types (ADT), são úteis para manipular e gerir colecções de objectos. As operações típicas sobre ADTs incluem a comparação entre objectos, operações de entrada e saída (leitura e escrita), inserção em colecções, remoção de colecções, e alteração de propriedades (e.g., prioridade). ADTs deste género são em geral denominados filas generalizadas.
O desenvolvimento de ADTs envolve em geral três problemas distintos:
- definição da interface;
- implementação do ADT;
- desenho e implementação dos clientes.
A abordagem baseada em ADTs tem várias vantagens: permite em geral obter uma solução elegante; permite separar os problemas de alto nível (interface de operações sobre tipo de dados) dos problemas de baixo nível (como manter as estruturas de dados); permite comparar diferentes implementações; permite e promove a reutilização de código. A alternativa é juntar e confundir tudo, o que leva a uma maior complexidade da solução e limita fortemente a reutilização de código.
Listas ligadas
Vejamos o concretização de listas ligadas enquanto ADT. Vamos começar por considerar a implementação de uma lista ligada de inteiros:
struct node {
int value;
struct node *next;
};
typedef struct node *link;
void insert(link x, int value)
{
link t;
t = (link) malloc(sizeof(struct node));
t->value = value;
t->next = x->next;
x->next = t;
}Se quisermos considerar agora a implementação de uma lista ligada de cadeias de caracteres quais serão as diferenças em relação à implementação anterior?
struct node {
char *value;
struct node *next;
};
typedef struct node *link;
void insert(link x, char *value)
{
link t;
t = (link) malloc(sizeof(struct node));
t->value = strdup(value);
t->next = x->next;
x->next = t;
}Na prática temos de mudar o tipo do campo value e a forma de guardar o valor nesse campo na função insert, em que utilizamos a função strdup.
Podemos portanto implementar a lista ligada para um tipo genérico da seguinte forma:
struct node {
Item value;
struct node *next;
};
typedef struct node *link;
void insert(link x, Item value) {
link t;
t = (link) malloc(sizeof(struct node));
t->value = NEW(value);
t->next = x->next;
x->next = t;
}Neste caso o tipo do campo value passa a ser o tipo genérico Item e assumimos que está definida a função NEW que, dado um elemento do tipo Item, retorna uma cópia do mesmo.
Se quisermos agora utilizar a implementação genérica para guardar inteiros basta incluir o ficheiro Item.h com o seguinte conteúdo:
typedef int Item; #define NEW(value) (value)
E se quisermos utilizar a implementação genérica para guardar cadeias de caracteres basta incluir o ficheiro Item.h com o seguinte conteúdo:
typedef char *Item;
char *NEW(char *value)
{
return strdup(value);
}Esta implementação genérica tem no entanto algumas desvantagens, só podemos utilizar uma instância da mesma definida para um dado tipo genérico Item.
Abstracções
Em geral a realização de ADTs depende da capacidade de abstrairmos algumas operações comuns a vários tipos de dados. Por exemplo, se pensarmos na comparação de igualdade entre dois valores A e B, temos que podemos abstrair essa operação como uma função int eq(Item A, Item B) sobre um tipo genérico Item que, no caso dos inteiros, pode ser definida como
typedef int Item; #define eq(A,B) ((A)==(B))
e no caso das cadeias de caracteres pode ser definida como
typedef char* Item; #define eq(A,B) (!strcmp(A,B))
Portanto, a ideia fundamental é abstrair as operações comuns entre vários tipos de dados por forma a podermos definir ADTs da forma mais genérica possível.
ADT para stack/pilha (LIFO)
Vejamos como definir e implementar um ADT LIFO ou pilha.
Operações:
/** * @file stack.h */ void STACKinit(int); int STACKempty(); void STACKpush(Item); Item STACKpop();
Podemos ter várias implementações alternativas. Implementação com tabela:
/**
* @file stack_array.c
*/
#include <stdlib.h>
#include "Item.h"
#include "stack.h"
static Item *s;
static int N;
void STACKinit(int maxN) {
s = malloc(maxN*sizeof(Item));
N = 0;
}
int STACKempty() {
return N == 0;
}
void STACKpush(Item item) {
s[N++] = item;
}
Item STACKpop() {
return s[--N];
}Implementação com lista:
/**
* @file stack_list.c
*/
#include <stdlib.h>
#include "Item.h"
#include "stack.h"
struct STACKnode {
Item item;
struct STACKnode* next;
};
typedef struct STACKnode* link;
static link head;
link NEW(Item item, link next) {
link x = (link)malloc(sizeof(STACKnode));
x->item = item;
x->next = next;
return x;
}
void STACKinit(int maxN) {
head = NULL;
}
int STACKempty() {
return head == NULL;
}
void STACKpush(Item item) {
head = NEW(item, head);
}
Item STACKpop() {
Item item = head->item;
link t = head->next;
free(head->item);
free(head);
head = t;
return item;
}ADT para filas de espera (FIFO)
Vejamos como definir e implementar um ADT FIFO ou fila.
Operações:
/** * @file queue.h */ void QUEUEinit(int); int QUEUEempty(); void QUEUEput(Item); Item QUEUEget();
Podemos novamente ter várias implementações alternativas. Implementação com lista:
/**
* @file queue_list.c
*/
#include <stdlib.h>
#include "Item.h"
#include "queue.h"
typedef struct QUEUEnode* link;
struct QUEUEnode {
Item item;
link next;
};
static link head, tail;
void QUEUEinit(int maxN) {
head = NULL;
tail = NULL;
}
int QUEUEempty() {
return head == NULL;
}
link NEW(Item item, link next) {
link x = malloc(sizeof(struct QUEUEnode));
x->item = item;
x->next = next;
return x;
}
void QUEUEput(Item item) {
if (head == NULL) {
head = (tail = NEW(item, head));
return;
}
tail->next = NEW(item, tail->next);
tail = tail->next;
}
Item QUEUEget() {
Item item = head->item;
link t = head->next;
free(head);
head = t;
return item;
}Implementação com tabela:
/**
* @file queue_array.c
*/
#include <stdlib.h>
#include "Item.h "
#include "queue.h"
static Item *q;
static int N, head, tail;
void QUEUEinit(int maxN) {
q = malloc((maxN+1)*sizeof(Item));
N = maxN+1;
head = N;
tail = 0;
}
int QUEUEempty() {
return head % N == tail;
}
void QUEUEput(Item item) {
q[tail++] = item;
tail = tail % N;
}
Item QUEUEget() {
head = head % N;
return q[head++];
}Esta implementação é usualmente conhecida por circular buffer ou ring buffer.
ADTs de primeira ordem
Nos ADTs estudados só é possível ter uma instância da estrutura de dados. Notar em particular que a informação da estrutura de dados é guardada em variáveis globais e, portanto, as funções operam sobre uma única estrutura de dados.
Como fazer quando pretendemos ter várias instâncias do mesmo ADT? Por exemplo, múltiplas FIFOS?
Solução: em vez da informação da estrutura de dados ser guardada em variáveis globais, é guardada numa estrutura que é passada como argumento a cada função.
/** * @file queue.h */ typedef struct queue *Q; void QUEUEdump(Q); Q QUEUEinit(int); int QUEUEempty(Q); void QUEUEput(Q, Item); Item QUEUEget(Q);
Possível cliente deste ADT:
#include <stdio.h>
#include <stdlib.h>
#include "Item.h"
#include "QUEUE.h"
#define M 10
int main(int argc, char *argv[]) {
int i, j, N = atoi(argv[1]);
Q queues[M];
for (i = 0; i < M; i++)
queues[i] = QUEUEinit(N);
for (i = 0; i < N; i++)
QUEUEput(queues[rand() % M], i);
for (i = 0; i < M; i++, printf("\n"))
for (j = 0; !QUEUEempty(queues[i]); j++)
printf("%3d ", QUEUEget(queues[i]));
return 0;
}Implementação do ADT:
/**
* @file queue.c
*/
#include <stdlib.h>
#include "Item.h"
#include "queue.h"
typedef struct QUEUEnode* link;
struct QUEUEnode { Item item; link next; };
struct queue { link head; link tail; };
link NEW(Item item, link next) {
link x = malloc(sizeof(struct QUEUEnode));
x->item = item;
x->next = next;
return x;
}
Q QUEUEinit(int maxN) {
Q q = (Q)malloc(sizeof(struct queue));
q->head = NULL;
q->tail = NULL;
return q;
}
int QUEUEempty(Q q) {
return q->head == NULL;
}
void QUEUEput(Q q, Item item) {
if (q->head == NULL) {
q->tail = NEW(item, q->head);
q->head = q->tail;
return;
}
q->tail->next = NEW(item, q->tail->next);
q->tail = q->tail->next;
}
Item QUEUEget(Q q) {
Item item = q->head->item;
link t = q->head->next;
free(q->item);
free(q->head);
q->head = t;
return item;
}Embora com esta nova abordagem possamos ter várias instâncias, como é que podemos fazer para ter no mesmo programa, por exemplo, um FIFO com inteiros e um outro FIFO com cadeias de caracteres?
Complexidade: vectores vs listas ligadas
Comparação da complexidade das operações mais comuns sobre vectores e listas ligadas, com $n$ elementos:
| Vector/Tabela | Lista (head apenas) | Lista (head e tail) | Lista (duplamente ligada, head e tail) | |
|---|---|---|---|---|
| Acesso | $O(1)$ | $O(n)$ | $O(n)$ | $O(n)$ |
| Inserção/remoção no início | $O(n)$ | $O(1)$ | $O(1)$ | $O(1)$ |
| Inserção/remoção no fim | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$ |
| Inserção/remoção no meio | $O(n)$ | $T_{procura} + O(1)$ | $T_{procura} + O(1)$ | $T_{procura} + O(1)$ |
Funções lsearch, bsearch e qsort
Existem algumas funções definidas em stdlib.h e search.h que nos permitem também gerir colecções de elementos de tipo arbitrário. Na prática estas funções assumem que temos um vector do tipo void *, ou seja, um vector de qualquer coisa. Dada uma função de comparação com o tipo int(*compar)(const void *, const void *), podemos utilizar estas funções para fazer pesquisas sobre qualquer vector que estejamos a utilizar.
A função de comparação deverá retornar zero se os ponteiros dados como argumento apontarem para elementos iguais, um valor menor do que zero se o primeiro elemento apontado for menor que o segundo, e um valor maior do que zero caso contrário. De facto, no caso da pesquisa linear, basta que a função retorne um valor diferente de zero no caso dos elementos apontados serem diferentes uma vez que a ordem relativa não interessa neste caso.
Exemplo de uma função de comparação para inteiros:
int
intcmp(const void * x, const void * y)
{
return *((const int *) x) - *((const int *) y);
}Pesquisa linear (funções lsearch e lfind):
void *lfind(const void *key, const void *base, size_t *nmemb,
size_t size, int(*compar)(const void *, const void *));
void *lsearch(const void *key, void *base, size_t *nmemb,
size_t size, int(*compar)(const void *, const void *));A função lsearch insere o novo elemento se não o encontrar. Ambas as funções retornam um ponteiro para o elemento se este existir. A função lfind retorna NULL se o elemento não existir.
Pesquisa binária (função bsearch definida em stdlib.h):
void *bsearch(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *));A função retorna um ponteiro para um elemento com a chave dada se existir algum, retorna NULL se o elemento não existir.
Notar que para utilizar esta função precisamos que o vector seja previamente ordenado, segundo a função de comparação dada, utilizando por exemplo a função qsort (definida também em stdlib.h):
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));Exemplo de utilização destas funções:
/**
* @file search.c
* @brief Experiencias com funcoes de pesquisa.
*
* Experiencias com as funcoes de pesquisa lsearch, lfind e bsearch.
*/
#include <stdio.h>
#include <stdlib.h>
#include <search.h>
#define BUFFER_SIZE 16
#define STEPS 32
/**
* @brief Funcao de comparacao para ints.
*
* Funcao de comparacao que implementa a ordem natural dos inteiros.
*
* @param x ponteiro para inteiro.
* @param y ponteiro para inteiro.
* @return valor menor do que zero se *x é menor do que *y, valor zero
* se *x é igual a *y, e valor maior do que zero se *x é maior
* do que *y.
*/
static int
intcmp(const void * x, const void * y)
{
return *((const int *) x) - *((const int *) y);
}
int
main(int argc, char *argv[])
{
int buffer[BUFFER_SIZE], value, i, *p;
size_t buffer_n = 0, old_n;
/* Se tivermos um argumento vamos tentar utiliza-lo como semente. */
if (argc > 1)
srand(atoi(argv[1]));
/* Colocar BUFFER_SIZE elementos em STEPS passos de forma aleatoria.
* O vector buffer pode nao ficar completo no final. */
for (i = 0; i < STEPS; i++) {
/* Valor aleatorio entre 0 e 99. */
value = rand()%100;
/* Ainda podemos colocar novos valores? */
if (buffer_n < BUFFER_SIZE) {
/* Guardar o numero de valores anteriores. */
old_n = buffer_n;
/* Procurar o novo valor e inserir o mesmo se não existir. */
p = lsearch(&value, buffer, &buffer_n, sizeof(int), intcmp);
/* Se o numero de elementos mudou, entao o valor era novo. */
if (buffer_n > old_n)
printf("New value: %d\n", value);
else /* Caso contrario ja existia. */
printf("Value %d found at %lu\n", value, p - buffer);
} else { /* Ja nao podemos colocar novos valores. */
/* Procurar apenas o novo valor. */
p = lfind(&value, buffer, &buffer_n, sizeof(int), intcmp);
/* Foi encontrado? */
if (p != NULL)
printf("Value %d found at %lu\n", value, p - buffer);
else
printf("Value %d not found!\n", value);
}
}
/* Mostrar o conteudo do buffer. */
printf("%lu values:", buffer_n);
for (i = 0; i < buffer_n; i++)
printf(" %d", buffer[i]);
printf("\n");
/* Ordenar o buffer. */
qsort(buffer, buffer_n, sizeof(int), intcmp);
/* Mostrar o conteudo do buffer depois de ordenar. */
printf("%lu sorted values:", buffer_n);
for (i = 0; i < buffer_n; i++)
printf(" %d", buffer[i]);
printf("\n");
/* Procurar valores com pesquisa binaria de forma aleatoria. */
for (i = 0; i < STEPS; i++) {
value = rand()%100;
p = bsearch(&value, buffer, buffer_n, sizeof(int), intcmp);
if (p != NULL)
printf("Value %d found at %lu\n", value, p - buffer);
else
printf("Value %d not found!\n", value);
}
return EXIT_SUCCESS;
}Compilar e executar:
[aplf@darkstar ~]$ gcc -Wall -ansi -pedantic -o search search.c [aplf@darkstar ~]$ ./search 10 New value: 95 New value: 8 New value: 78 New value: 25 New value: 18 New value: 77 New value: 75 New value: 71 New value: 47 New value: 7 New value: 23 New value: 73 New value: 28 Value 73 found at 11 New value: 44 New value: 81 New value: 20 Value 38 not found! Value 71 found at 7 Value 68 not found! Value 68 not found! Value 44 found at 13 Value 55 not found! Value 81 found at 14 Value 62 not found! Value 28 found at 12 Value 12 not found! Value 23 found at 10 Value 88 not found! Value 66 not found! Value 57 not found! Value 83 not found! 16 values: 95 8 78 25 18 77 75 71 47 7 23 73 28 44 81 20 16 sorted values: 7 8 18 20 23 25 28 44 47 71 73 75 77 78 81 95 Value 27 not found! Value 88 not found! Value 60 not found! Value 45 not found! Value 65 not found! Value 35 not found! Value 69 not found! Value 12 not found! Value 43 not found! Value 92 not found! Value 85 not found! Value 23 found at 4 Value 17 not found! Value 81 found at 14 Value 56 not found! Value 38 not found! Value 20 found at 3 Value 27 not found! Value 58 not found! Value 88 not found! Value 23 found at 4 Value 65 not found! Value 21 not found! Value 37 not found! Value 93 not found! Value 33 not found! Value 60 not found! Value 82 not found! Value 0 not found! Value 70 not found! Value 17 not found! Value 27 not found! [aplf@darkstar ~]$