Prova de AED - Listas

Prévia do material em texto

Prova 1 – Algoritmos e Estrutura de Dados 1 – 2017-2
Valor: 35 pontos
Seja as estruturas abaixo para listas encadeadas. Considere esta organização para responder às perguntas.
typedef struct ListElmt_{
 int data;
 struct ListElmt_ *next;
} ListElmt;
typedef struct List_ {
 int size;
 ListElmt *head;
 ListElmt *tail;
} List;
void list_init(List *list) {
 list->size = 0;
 list->head = NULL;
 list->tail = NULL;
 return;
}
1) Faça uma função que receba uma lista válida (pode ser vazia), remova o primeiro elemento da lista e 
retorne em um parâmetro passado por referência. Se a lista for vazia, não faça nada (8 pontos) 
2) Faça uma função que receba uma lista válida (pode ser vazia), um número inteiro e insira um 
elemento no final da lista. (7 pontos) 
3) Faça uma função que receba uma lista válida (pode ser vazia), um inteiro i e remova o i-ésimo 
elemento da lista retornando o elemento em um parâmetro passado por referência. Por exemplo, se 
receber a lista [10, 20, 30], o inteiro 2, então a lista ficar [10, 30] e 20 atualizará a variável passada 
por referência. Não deve ser criada uma nova lista. A função deve verificar se i é válido. (10 pontos)
4) Faça uma função que receba uma lista válida, e destrua completamente a lista. Repare que esta 
função é diferente de list_init, quando a lista é não-vazia. (5 pontos)
5) Faça uma função que receba uma lista válida (pode ser vazia), receba uma posição i e um elemento n,
e insere o elemento n na posição i da lista. A primeira posição da lista é 1. Se a lista estiver vazia, 
somente é aceito inserir na posição 1. Para inserir um elemento no final da lista, a posição passada 
como parâmetro deve ser o tamanho da lista mais um. Se i for inválido, a função retorna sem fazer 
nada. (5 pontos) 
Observação: Você pode criar funções auxiliares e/ou reaproveitar suas funções que definiu.
int list_ins_next(List *list, ListElmt *element, int data) {
 ListElmt *new_element;
 if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
 return -1;
 new_element->data = data;
 if (element == NULL) {
 // Insercao na cabeca
 if (list_size(list) == 0)
 list->tail = new_element;
 new_element->next = list->head;
 list->head = new_element;
 } else {
 // Insercao nao na cabeca
 if (element->next == NULL)
 list->tail = new_element;
 new_element->next = element->next;
 element->next = new_element;
 }
 list->size++;
 return 0;
}