Linguagens e Ambientes de Programação (2022/2023)

Prática 07

Estruturas ligadas em C. Exercício 37.

37 - Use como ponto de partida deste exercício o código destes três ficheiros: LinkedList.h, LinkedList.c, Main.c. Os dois primeiros ficheiros definem o módulo fechado LinkedList, que voltará a ser estudado na aula teórica 12. O último ficheiro é um módulo cliente.

O objetivo deste exercício é acrecentar ao módulo LinkedList cinco novas funções públicas, descritas mais abaixo. Todas elas são para programar de forma imperativa, sem usar recursividade, usando iteração. A complexidade temporal das quatro primeiras funções deve ser linear (ou seja, não use a função ListPutAtEnd das aulas teóricas, pois isso originaria soluções quadráticas).

As funções vão precisar de manipular apontadores. Recordamos que se um apontador pt aponta para um nó, a sintaxe para aceder às duas partes do nó é: pt->data e pt->next.

Em duas das funções pedidas serão usadas duas técnicas que já apareceram na aula teórica 12 - a técnica do apontador para o último nó (que permite ir fazendo crescer a lista no final), e a técnica do apontador atrasado (que ajuda a adicionar e eliminar nós duma lista).

TÉCNICA DE PROGRAMAÇÃO - Na programação de funções sobre listas ligadas, recomendamos o uso da seguinte técnica:

No corpo da função, começar por escrever este código que percorre a lista argumento:
for( ; l != NULL ; l = l->next )

Desenhar a lista argumento, mostrando diversos nós ligados por arcos orientados.
Ainda no desenho, raciocinar sobre o que acontece quando o ciclo vai a meio (não quando o ciclo está a começar). Vão ser precisos apontadores auxiliares? Em que consiste cada passo do ciclo? Represente no desenho a sua ideia.
Agora que já definiu um plano, já pode escrever o código do interior do ciclo. Será preciso ajustar o for que foi escrito no ponto 1? Em alguns problemas sim, noutros não.
Só depois vale a pena pensar na inicialização. Por vezes, a inicialização é muito simples. Outras vezes, é mais complicada e às vezes até se descobre que o primeiro elemento da lista tem de ser tratado antes de se entrar no ciclo.
Depois, pense na finalização.
Verifique ainda se a função funciona corretamente para a lista vazia. Em alguns problemas, a lista vazia tem de ser tratada à parte com um if suplementar.
Olhar de forma crítica para o código, para ver se descobre algum problema. Se as circunstâncias o permitirem, fazer também algumas chamadas da função para a testar.

Eis a descrição das cinco funções públicas pedidas:

List listClone(List l) ; // Cria uma cópia duma lista, em que todos os nós são novos.
List listAppend(List l1, List l2) ; // No final de l1, acrescenta uma cópia da lista l2 (chamando listClone, claro)
List listRev(List l) ; // Inverte uma lista, duplicando todos os nós da lista original. [Repare que fica mais simples do que a função listClone, pois é mais simples ir acrescentando na cabeça do que no final.]
List listRevInPlace(List l) ; // Inverte uma lista, aproveitando os nós da lista original. Só se alteram os apontadores next
List listUniq(List l) ; // Elimina duma lista, todos os nós com valores repetidos. Mantenha a ordem dos elementos que ficam. No caso dos elementos repetidos, pode manter o nó que desejar. Use a operação free. Neste problema, espera-se que a complexidade da solução seja quadrática (ou seja, que a solução fique um pouco lenta).

38 - A biblioteca standard do C oferece diversas operações úteis e interessantes: uma operação para aceder ao relógio do sistema time; um gerador de números aleatórios com operações srand e rand; uma operação de ordenação genérica qsort.

a) Use as man pages do Linux para obter informação sobre estas operações;
- ```
man 3 time
```
- ```
man 3 rand
```
- ```
man 3 qsort
```

b) Escreva um pequeno programa que faça o seguinte: definir um vetor de inteiros com 30 componentes; inicializar o gerador de números aleatórios usando o tempo do sistema; preencher o vetor com valores inteiros aleatórios; ordenar crescentemente o vetor usando a função de biblioteca qsort; mostrar na consola o vetor ordenado. É já oferecido este ponto de partida:

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

#define N_ELEMS     30

void fill(int vect[], int n) {
    // FAZER
}

void sort(int vect[], int n) {
    // FAZER
}

void show(int vect[], int n) {
    int i;
    printf("----------------\n");
    for( i = 0 ; i < n ; i++ )
        printf("%12d\n", vect[i]);
    printf("----------------\n");
}

int main() {
    int vect[N_ELEMS];
    fill(vect, N_ELEMS);
    show(vect, N_ELEMS);
    sort(vect, N_ELEMS);
    show(vect, N_ELEMS);
    return 0 ;
}

Se tiver dúvidas sobre a passagem de vetores para funções, leia na teórica 11 a secção "Passagem de parâmetros para funções".

39 - Inspire-se no módulo fechado LinkedList das aula teórica 12 para programar em C um novo módulo fechado de árvores binárias de inteiros chamado BinTree. Implemente nele as funções newTreeNode, treeSize, mais as principais funções da aula prática 3

As operações "spring" e "fall" devem alterar diretamente as árvores passadas por argumento (ou seja, devem ser operações "destrutivas").

Note que, como se trata de árvores, faz sentido e é aconselhado usar recursividade em situações como esta. No entanto, para praticar, desenvolva uma solução não-recursiva com a ajuda duma pilha auxiliar (uma pilha que, ao encher, você faz crescer com a ajuda de realloc).

Vídeos antigos

Estes vídeos poderão estar um pouco desatualizados, pois foram feitos no contexto duma edição anterior do LAP. Contudo, partes dos vídeos poderão continuar a ter alguma utilidade.

Leiam bem o enunciado do exercício 37 e tentem resolver algumas alíneas! Se fizerem isso antes de ver o vídeo, irão perceber com maior profundidado o desenvolvimento do código.

Errata:

Nos minutos finais aparece escrito "new malloc" quando devia ser simplesmente "malloc".

(lap prática 07 parte2)