Exercícios

Considere a definição de Item da aula passada e as seguintes funções:

typedef char* Item;

Item newItem (Item i);

int itemCompare (Item i1, Item i2);

void showItem (Item i);

void deleteItem (Item i);

 

Considere ainda uma fila de espera (ou queue), implementada através de uma lista ligada que obedece às seguintes definições (ver slides 28-34, disponíveis aqui)

typedef struct node { 
        Item item; 
        struct node* next; 
}*link; /* link é um ponteiro para a struct node */

typedef struct queue{ 
     link head; /* ponteiro para o primeiro "node" da lista */
     link tail; /* ponteiro para o ultimo "node" da lista */

     int size; /* numero de elementos da lista */  

} *Q; /* Q é um ponteiro para esta struct queue */

1. Implemente a função Q create() que cria uma nova queue. 

2. Implemente a função void insertBegin(Q q, Item i) que insere o Item i no início da lista. 

3. Implemente a função void insertEnd(Q q, Item i) que insere o Item i no fim da lista. 

4. Implemente a função void insertSorted(Q q, Item i) que insere o Item i de forma ordenada na lista l. A ordenação da lista deverá ser crescente. 

5. Implemente a função void show(Q q) que mostra no standard output o conteúdo de q. 

6. Implemente a função void clear(Q q) que liberta toda a memória associada com a lista q. Use a ferramenta valgrind para verificar a correcção da função. 

7. Implemente a função void removeFirst(Q q, Item i) que remove da lista a primeira ocorrência do Item i. 

8. Implemente a função void removeAll(Q q, Item i) que remove da lista todas as ocorrências do Item i.