Exercícios


1. (listas de inteiros) Considere uma lista simplesmente ligada de inteiros que obedece à seguinte definição:

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

Implemente uma função que insere um valor no início, uma função que insere um valor no fim, uma função que remove o primeiro elemento da lista e uma função que imprime todos os valores guardados na lista. (sugestão: consulte as aulas teóricas T19 e T18 e adapte o código dado).


2. (listas ligadas de strings com abstracção) Considere uma lista simplesmente ligada de strings que obedece à seguinte definição:

typedef struct node *link;

typedef char* Item;

struct node { 
        Item item; 
        link next; 
}; 

2.1. - Implemente as seguintes funções para manipulação de items:

a) Item newItem (char* s);

A função newItem devolve um novo Item (neste caso uma string) contendo a informação passada como argumento .

b) Crie uma função responsável por criar um novo nodo de uma lista ligada, contendo o Item i e devolvendo o endereço do tipo link.

link newNode (Item i); 

c) int itemCompare (Item i1, Item i2);

A função itemCompare devolve 0 se os items são iguais. Devolve um valor positivo se i1 > i2 ou um valor negativo caso contrário. 

d) void showItem (Item i);

A função showItem mostra o item i no standard output.

e) void deleteItem (Item i);

Liberta a memória associada ao item.

2.2. - Implemente a função link insertSorted(link head, Item i) que insere o Item i de forma ordenada na lista cujo primeiro elemento é apontado por head. A função deverá devolver o primeiro elemento da lista. A ordenação deverá ser crescente. Use as funções do exercício anterior.

2.3. - Implemente a função void show(link head) que mostra no standard output o conteúdo da lista cujo primeiro elemento é apontado por head. Use as funções do exercício 1. 

2.4 - Implemente a função int search(link head, Item i) que devolve 1 se o item i estiver na lista ou 0 caso contrário. 

2.5 - Implemente a função link removeNode(link head, Item i) que remove da lista a primeira ocorrência do Item i. A função deverá devolver o primeiro elemento da lista.

2.6 - Faça um programa que insira numa lista todos os argumentos fornecidos na linha de comandos, e que podem ser obtidos através da tabela argv. De seguida, mostre o conteúdo da lista.

2.7 - Defina que o tipo Item é um ponteiro para inteiro. Modifique as funções do exercício 1 de acordo com a nova definição e resolva os exercícios 2 a 5.


Nota: Se tiver dificuldade na resolução destes exercícios, tome os exemplos disponibilizados nos slides das aulas teóricas (T18, T19 e T20) como ponto de partida.