Estruturas Auto-Referenciadas e Listas

Arrays

Em C, a estrutura mais usual (e built-in) para guardar coleções de itens são vetores/arrays. São estruturas bastante versáteis: permitem guardar desde tipos de dados default como inteiros e caracteres como tipos mais sofisticados, estruturas, ou até mesmo outros vetores. São também estruturas que permitem acesso bastante eficiente (em tempo constante, até) ao seu n-ésimo elemento.

#define N 100
// declaração de arrays
int tab1[N];
int *tab2 = (int *) malloc(N * sizeof(int));
// acesso a elementos de uma array
x = tab2[i];
y = *(tab2 + i);

Esta simplicidade, contudo, traz também alguns pormenores desagradáveis, principalmente quanto à maneira como vetores são guardados em memória: são guardados de forma sequencial, isto é, em posições consecutivas de memória. É por essa razão que, em C, arrays têm de ter tamanho fixo, a não ser que sejam alocados dinamicamente (via malloc). Ora, ter vetores de tamanho fixo pode ser bastante chato, principalmente porque caso precisemos mesmo que o vetor aumente de tamanho, já que não vamos fugir a ter de realocar memória e copiar todos os elementos de uma posição em memória para outra, processo este relativamente ineficiente.

Ora, mas ainda antes de C aparecer, já havia sido pensada uma estrutura de dados que combatia alguns dos problemas supra-mencionados: em meados dos anos 50, um grupo de investigadores na RAND Corporation pensaram numa estrutura, as listas ligadas, que seria a estrutura de dados principal para a sua "Information Processing Language", IPL, utilizada por esta equipa em vários programas embrionários ligados à inteligência artificial.

Listas

Antes de falar de listas, será interessante definir estrutura auto-referenciada: uma estrutura em que um dos seus campos é um ponteiro para outra estrutura do mesmo tipo. No exemplo abaixo, podemos ver que a estrutura ponto tem um apontador para outro ponto, o seu "pai".

typedef struct point {
  double x;
  double y;
  struct point *origem;
} Point;

Utilizamos estruturas deste tipo principalmente em árvores e listas, onde manter referências de nós quanto à sua posição relativa na árvore/lista é bastante importante.

Lista Simplesmente Ligada

As listas simplesmente ligadas (singly linked lists em inglês) não são mais que uma maneira de organizar um conjunto de nós, onde cada nó contém, para além da respetiva informação útil (um valor, uma chave, etc.), um ponteiro para o próximo nó. Desta forma, tendo a cabeça da lista, podemos percorrer facilmente a lista completa, saltando de nó em nó recorrendo a ponteiros.

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

// ---

struct node {
  char *name;
  struct node *next;
};

Comparada com arrays, tem a vantagem de ter tamanho ilimitado - não sendo guardada de forma sequencial, não há necessidade de reservar blocos contíguos de memória, sendo apenas preciso guardar os ponteiros (que podem estar num sítio qualquer). Mais ainda, a alocação de memória é feita exclusivamente para os elementos que queremos representar, não havendo portanto desperdício. A inserção e remoção de elementos não tem nada que saber:

• Se quisermos inserir um nó t após x, apenas precisamos de:

t->next = x->next;
x->next = t;

• Remover o nó t, que vem a seguir de x, é igualmente simples:

t = x->next;
x->next = t->next;
free(t);

Apresenta, contudo, uma desvantagem quanto aos arrays: é inegavelmente menos eficiente aceder ao n-ésimo elemento numa lista ligada, já que na ausência da noção de indexação built-in acabamos por ter de percorrer a lista para a recriar. Mais ainda, para saber o número de elementos de uma lista, das duas uma: ou vamos mantendo um contador global, contador este que vai sendo atualizado sempre que inserimos ou removemos um nó, ou vemo-nos obrigados a percorrê-la sempre que queremos saber o seu comprimento:

int length(struct node* head) {
    int count = 0;
    struct node *x = head;
    while (x != NULL) {
        count++;
        x = x->next;
    }
    return count;
}

Temos ainda de ter em atenção que manter a cabeça destas listas é crucial: caso a percamos, perdemos a possibilidade de fazer uma procura completa por todos os nós da mesma.

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

struct node {
    int value;
    struct node *next;
};
static struct node *top;

void init() { /* inicializa a pilha */
    top = NULL;
}

void push(int value) { /* introduz novo elemento no topo */
    struct node *new;
    new = (struct node *) malloc(sizeof(struct node));
    new->value = value;
    new->next = top;
    top = new;
}

int is_empty() { /* pergunta se está vazia */
    return top == NULL;
}

int pop() { /* apaga o topo e retorna o valor apagado */
    int value;
    struct node *old;
    if (!is_empty()) {
        value = top->value;
        old = top;
        top = top->next;
        free(old);
        return value;
    } else {
        return -1;
    }
}

Lista Duplamente Ligada

Listas duplamente ligadas (doubly linked lists em inglês) são muito semelhantes às listas simplesmente ligadas, contando contudo com uma pequena diferença (com repercussões muito interessantes): cada nó, para além de guardar a sua chave e o ponteiro para o nó seguinte, guarda também um ponteiro para o nó anterior - podemos, portanto, percorrer a lista para trás e para a frente partindo de qualquer nó.

struct node {
    Item item;
    struct node *prev, *next;
};

* Nota: em IAED, é usual utilizar typedef's como Node e link para manipular estruturas auto-referenciadas. É uma notação algo controversa (a ausência do asterisco a indicar o ponteiro faz confusão a algumas pessoas), e não precisam de a usar necessariamente no vosso código, mas vai ser a que vai ser usada nesta e nas próximas secções.

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

typedef struct node Node;
typedef struct node* link;

int length(link head) {
  int count = 0;
  link x;
  for (x = head; x != NULL; x = x->next) {
      count++;
  }
  return count;
}

Abaixo seguem algumas implementações de funções clássicas utilizadas para manipular estas estruturas (retiradas dos slides da docência):

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

struct node {
    char text;
    struct node *next;
};
typedef struct node Node;
typedef struct node *link;

int main(int argc, char *argv[]) {
    int i;
    link head = NULL;

    /* inserir todos os elementos na lista */
    for (i = 1; i < argc; i++) {
        head = insert_end(head, argv[i]);
    }

    print_list(head); /* imprime toda a lista */

    /* remover o elemento na posição i (lido do stdin) */
    scanf("%d", &i);
    head = delete_node(head, argv[i]);

    print_list(head); /* voltamos a imprimir toda a lista */

    return 0;
}

/* Função auxiliar responável por alocar memória para
tudo o que é necessário para um novo nó */
link new_node(char *buffer) {
    /* reservar memória para novo nó */
    link x = (link) malloc(sizeof(struct node));
    /* reservar memória para nova string */
    x->text = (char *) malloc(sizeof(char) * (strlen(buffer) + 1));

    strcpy(x->text, buffer);
    x->next = NULL;
    return x;
}

link insert_beginning(link head, char *text) {
    link x = new_node(text);
    x->next = head;
    return x; /* retorna a nova "head" */
}

link insert_end(link head, char *text) {
    link x;
    if (head == NULL) {
        return new_node(text);
    }
    // loop para chegar ao fim da lista
    for (x = head; x->next != NULL; x = x->next);

    x->next = new_node(text);
    return head;
}

link lookup(link head, char *text) {
    link t;
    for (t = head; t != NULL; t = t->next) {
        if (strcmp(t->text, text) == 0) {
            return t;
        }
    }
    return NULL;
}

void print_list(link head) {
    link t;
    for (t = head; t != NULL; t = t->next) {
        printf("%s\n", t->text);
    }
}

link delete_node(link head, char *text) {
    link t, prev;
    for (t = head, prev = NULL; t != NULL;
         prev = t, t = t->next) {
        if (strcmp(t->text, text) == 0) {
            if (t == head) {
                head = t->next;
            } else {
                prev->next = t->next;
            }
            free_node(t);
            break;
        }
    }
    return head;
}

void free_node(link t) {
    free(t->text);
    free(t);
}

Passar Argumentos através da Linha de Comandos

Geralmente, é nesta altura em IAED que se costuma abordar a passagem de argumentos aos nossos programas através da linha de comandos.

Possivelmente, ao longo da vossa (não muito) extensa jornada a trabalhar com C já se depararam com declarações da main que incluem dois argumentos: int argc e char *argv[]. Estes dois argumentos correspondem, respetivamente, ao número de elementos passados como input na nossa shell e ao conjunto dos mesmos. Podem ser, claro, omitidos caso não nos interesse receber argumentos dessa forma.

A título de exemplo, experimentem, com o seguinte programa, executá-lo através de ./program this is a test:

#include <stdio.h>

int main(int argc, char *argv[]) {
  printf("Received %d arguments via command line\n", argc);
  for (int i = 0; i < argc; i++) {
    printf("Currently looking at this argument: %s\n", argv[i]);
  }
  return 0;
}

Em princípio, a vossa interação teve este aspeto:

$ ./program this is a test
Received 5 arguments via command line
Currently looking at this argument: ./program
Currently looking at this argument: this
Currently looking at this argument: is
Currently looking at this argument: a
Currently looking at this argument: test

A própria chamada ./program pertence aos argumentos, devendo portanto ter isso em atenção (os argumentos "relevantes" só começam a partir do índice $1$).

Podem, de seguida, ver uma aplicação mais prática da utilidade desta feature:

int main(int argc, char *argv[]) {
    int i;
    link head = NULL;

    /* inserir todos os elementos na lista*/
    for (i = 1; i < argc; i++) {
        head = insert_end(head, argv[i]);
    }

    print_list(head); /* imprime toda a lista*/

    /* remover o elemento na posição i (lido do stdin) */
    scanf("%d", &i);
    head = delete_node(head, argv[i]);

    print_list(head); /* voltamos a imprimir toda a lista */

    return 0;
}