Apontadores, parte II

O segundo exercício pode ser facilmente resolvido à custa do primeiro, assim:

void put2(Node** dict, int key, char* val)
{
    *dict = put1(*dict, key, val);
}

void del2(Node** dict, int key)
{
    *dict = del1(*dict, key);
}

// A função get é exactamente igual
char* get2(Node* dict, int key)
{
    return get1(dict, key);
}

Mas vamos fazer as coisas sem "máfias".

Para começar, o que é e para que serve dupla indirecção?

No primeiro exercício, sempre que a cabeça da lista era alterada, era necessário devolver a nova cabeça. Por causa disto, quando se chamavam as funções fazia-se assim:

dict = put(dict, 42, "foo");
dict = del(dict, 42);

Se nos esquecessemos da atribuição e a cabeça fosse alterada, dict continuaria a apontar para a antiga cabeça. Assim a nova cabeça estava perdida para sempre e perderíamos um bom bocado de tempo à procura deste erro. No mínimo, tinhamos uma memory leak.

Era porreiro se as funções put e del fizessem esta parte automaticamente não era? É aqui que entra a dupla indirecção. O que nós queremos é que o nosso apontador para a cabeça (a variável dict) seja corrigido sempre que necessário. Para isso vamos passar o endereço do nosso apontador para a função, e com isso ela pode alterá-lo directamente.

void put(Node* * dict, int key, char* val);

A função put pode ver ou alterar o conteúdo deste endereço com, precisamente, o operador de conteúdo (*), assim:

// Ler
aNode = *dict;
aKey = (*dict)->key;
aVal = (*dict)->val;
aNext = (*dict)->next;
// Escrever
*dict = aNode;
(*dict)->key = aKey;
(*dict)->val = aVal;
(*dict)->next = aNext;

E agora tanto a função put com a função del já podem ser escritas com base no exercício anterior, mas com cuidado para aceder ao conteúdo de dict e, em lugar de devolver a nova cabeça, substituindo o conteúdo de dict pela nova cabeça. O código fica então assim:

void put(Node** dict, int key, char* val)
{
    Node* prev = NULL;
    Node* curr;
    Node* elem = (Node*) malloc(sizeof(Node));
    elem->key = key;
    elem->val = val;
    curr = *dict;
    while(curr && curr->key < key)
    {
        prev = curr;
        curr = curr->next;
    }
    // Casos 1 & 2
    if(prev == NULL)
    {
        elem->next = curr;
        *dict = elem;
    }
    // Casos 3 & 4
    else
    {
        prev->next = elem;
        elem->next = curr;
    }
}

void del(Node** dict, int key)
{
    Node* prev = NULL;
    Node* curr = *dict;
    while(curr && curr->key < key)
    {
        prev = curr;
        curr = curr->next;
    }
    // Não existe na lista
    if(curr == NULL || curr->key != key)
    {
        return;
    }
    // A cabeça
    if(prev == NULL)
    {
        Node* newHead = (*dict)->next;
        free(*dict);
        *dict = newHead;
    }
    // Os outros    else
    {
        prev->next = curr->next;
        free(curr);
    }
}

E agora eu posso usar as funções assim?

put(dict, 42, "foo");

Não. Como já disse, temos de passar o endereço do nosso apontador e não o nosso apontador. Para isso usamos o operador de endereço (&), assim:

put(&dict, 42, "foo");

E assim já funciona.

Podem fazer o download do código aqui.