lista-de-exercicios-de-algoritmos-e-estruturas-de-dados-segunda-lista-universidade-federal-do-rio-de-janeiro-ufrj-professor-heraldo-l-s-de-almeida-dsc-monitor-carlos-eduardo-marciano

Prévia do material em texto

Lista de Exercícios de Algoritmos e Estruturas de Dados 
Segunda Lista 
Universidade Federal do Rio de Janeiro – UFRJ 
Professor Heraldo L. S. de Almeida, D.Sc. 
Monitor Carlos Eduardo Marciano 
18/07/2016 
 
Elaborada por Carlos Eduardo Marciano 
 
 
 
 
 
 
Observações Iniciais 
Esta disciplina é lecionada em linguagem C. Para todos os exemplos de código, 
assuma que os devidos headers já estão inclusos. As respostas aqui encontradas não 
são necessariamente as únicas possíveis. 
 
Índice 
 
1. Pilhas ---------------------------------------------------------------------- Pág. 2 
2. Filas ------------------------------------------------------------------------ Pág. 4 
3. Listas ---------------------------------------------------------------------- Pág. 6 
4. Árvores ------------------------------------------------------------------- Pág. 9 
 A. Anexo A: Respostas --------------------------------------------------- Pág. 11 
 A.1 Pilhas ------------------------------------------------------------ Pág. 11 
 A.2 Filas -------------------------------------------------------------- Pág. 13 
 A.3 Listas ------------------------------------------------------------- Pág. 16 
 A.4 Árvores ---------------------------------------------------------- Pág. 21 
 B. Bibliografia -------------------------------------------------------------- Pág. 24 
 
1. Pilhas 
 
 
1.1) [Pilha sequencial] Projete uma estrutura do tipo pilha (stack/LIFO) sequencial de 
10 espaços para guardar informações de páginas da web visitadas. Essas informações 
estarão contidas na seguinte struct: 
#define MAX 10 
typedef struct{ 
 char adress[30]; 
 int connectionType; 
}PageData; 
Ao final do projeto, seu programa deve rodar as seguintes funções. Note que algumas 
delas retornam um código de erro. O output pode ser visto na imagem abaixo: 
Stack* inicializarPilha(); 
int push(Stack* pilha, char* adress, int connectionType); 
int pop(Stack* pilha); 
int main(){ 
 int errorCode; 
 Stack* pilha; 
 pilha = inicializarPilha(); //Pilha criada 
 errorCode = push(pilha, "http://fisica4.if.ufrj.br", 2); 
 errorCode = push(pilha, "http://www.youtube.com", 2); 
 errorCode = push(pilha, "https://www.facebook.com", 1); 
 errorCode = pop(pilha); 
 errorCode = push(pilha, "https://drive.google.com", 1); 
 errorCode = pop(pilha); 
 errorCode = pop(pilha); 
 errorCode = pop(pilha); 
} 
 
 
 
 
 
 
a) Crie uma struct para abrigar a pilha e defina-a como tipo Stack. Essa struct 
deve conter o array correspondente à LIFO e um int para guardar o topo da pilha. 
b) Escreva a função inicializarPilha que aloca memória para a pilha. 
c) Escreva a função push para adicionar um elemento à pilha. Se necessário, 
utilize a função strcpy(char* destino, const char* origem), da biblioteca padrão, para 
copiar strings. 
d) Escreva a função pop para remover e mostrar o último endereço da pilha. 
 
1.2) [Pilha encadeada] Projete uma estrutura do tipo pilha (stack/LIFO) encadeada 
para guardar números do tipo int. Utilize o código inicial abaixo: 
typedef struct Node{ 
 int valor; 
 struct Node* pProx; 
}Element; 
A ideia é criar as funções declaradas abaixo que permitam a execução do seguinte 
programa, resultando em um output similar ao da janela ao lado do código: 
void printPilha(Element* inicio); 
void push(Element** inicio, int valor); 
int pop(Element** inicio); 
int main(){ 
 int dado; 
 Element* pilha = NULL; //Pilha criada 
 push(&pilha, 3); 
 push(&pilha, 2); 
 push(&pilha, 7); 
 push(&pilha, 5); 
 printPilha(pilha); 
 dado = pop(&pilha); 
 dado = pop(&pilha); 
 printPilha(pilha); 
 push(&pilha, 9); 
 printPilha(pilha); 
} 
 
a) Escreva a função printPilha para ler os itens da pilha. 
b) Escreva a função push para adicionar um elemento à pilha. 
c) Escreva a função pop para remover um elemento da pilha e retornar seu 
valor associado. 
2. Filas 
 
 
2.1) [Fila sequencial] Projete uma estrutura do tipo fila (queue/FIFO) sequencial de 20 
espaços para guardar requerimentos de impressão para uma empresa de fotocópias. 
Essas informações estarão contidas na seguinte struct: 
#define MAX 20 
typedef struct{ 
 int customerId; 
 double price; 
}PrintingData; 
Ao final do projeto, seu programa deve rodar as seguintes funções. Note que algumas 
delas retornam um código de erro. O output pode ser visto na imagem abaixo: 
Queue* inicializarFila(); 
int inserir(Queue* fila, int customerId, double price); 
int remover(Queue* fila); 
int main(){ 
 int errorCode; 
 Queue* fila; 
 fila = inicializarFila(); //Fila criada 
 errorCode = inserir(fila, 1, 9.35); 
 errorCode = inserir(fila, 2, 5.45); 
 errorCode = inserir(fila, 3, 1.50); 
 errorCode = remover(fila); 
 errorCode = inserir(fila, 4, 3.40); 
 errorCode = remover(fila); 
 errorCode = inserir(fila, 5, 6.10); 
 errorCode = remover(fila); 
 errorCode = remover(fila); 
 errorCode = remover(fila); 
} 
 
a) Crie uma struct para abrigar a fila e defina-a como tipo Queue. Essa struct 
deve conter o array correspondente à FIFO e um int para guardar o fim da fila. 
b) Escreva a função inicializarFila que aloca memória para a fila. 
c) Escreva a função inserir para adicionar um elemento à fila. 
d) Escreva a função remover para extrair um elemento da fila e mostrar seu 
conteúdo. 
 
2.2) [Fila circular] Projete uma estrutura do tipo fila (queue/FIFO) circular de tamanho 
variável para guardar o ID dos usuários que esperam, por ordem de chegada, para 
comprar ingressos online para um dado show. O array users guarda IDs de clientes do 
tipo int. A estrutura da fila, portanto, é a seguinte: 
typedef struct{ 
 int* users; 
 int inicio, fim; 
 int capacidade; //Tamanho total da fila 
 int count; //Numero de usuarios na fila 
}CircQueue; 
Ao final do projeto, seu programa deve rodar as seguintes funções. Note que algumas 
delas retornam um código de erro. O output pode ser visto na imagem abaixo: 
CircQueue* inicializarFila(int capacidade); 
int inserir(CircQueue* fila, int userId); 
int remover(CircQueue* fila); 
int main(){ 
 int errorCode; 
 CircQueue* fila; 
 fila = inicializarFila(3); //Fila criada 
 errorCode = inserir(fila, 12342); 
 errorCode = inserir(fila, 23511); 
 errorCode = inserir(fila, 35234); 
 errorCode = remover(fila); 
 errorCode = remover(fila); 
 errorCode = inserir(fila, 43692); 
 errorCode = inserir(fila, 54217); 
 errorCode = remover(fila); 
 errorCode = remover(fila); 
 errorCode = inserir(fila, 66234); 
 errorCode = remover(fila); 
 errorCode = remover(fila); 
} 
 
a) Escreva a função inicializarFila que aloca memória para a fila e para seu 
array de elementos. 
b) Escreva a função inserir para adicionar um usuário à fila. 
c) Escreva a função remover para extrair um usuário da fila e permiti-lo 
comprar seu ingresso. 
 
3. Listas 
 
 
3.1) [Lista Sequencial Ordenada] Projete uma estrutura do tipo lista sequencial 
ordenada de 20 espaços para abrigar os inimigos ativos de um jogo de computador em 
ordem crescente de dificuldade (com relação ao número de pontos de vida). A 
estrutura que abriga essas informações é a seguinte: 
#define MAX 20 
typedef struct{ 
 int vida; 
 double ataque; 
}EnemyData; 
Deve ser possível adicionar ou remover um inimigo da lista à medida que este nasce ou 
é morto pelo jogador, através das funções e comandos abaixo: 
OrdList* inicializarLista(); 
int inserir(OrdList* lista, int vida, double ataque); 
int localizar(OrdList* lista, int vida); 
int dealDamage(OrdList*lista, int vida); 
int main(){ 
 int errorCode; 
 OrdList* lista = inicializarLista(); //Lista criada 
 errorCode = inserir(lista, 100, 4.42); 
 errorCode = inserir(lista, 50, 9.67); 
 errorCode = inserir(lista, 200, 2.56); 
 errorCode = inserir(lista, 150, 8.45); 
 printLista(lista); 
 errorCode = dealDamage(lista, 100); 
 errorCode = dealDamage (lista, 150); 
 printLista(lista); 
 errorCode = dealDamage (lista, 50); 
 errorCode = dealDamage (lista, 200); 
 printLista(lista); 
} 
A função dealDamage é equivalente à função “remover”, porém adaptada ao jogo: se 
um golpe de 100 pontos for desferido, o inimigo com esta vida deverá desaparecer. A 
fim de facilitar seu projeto, utilize a seguinte função para mostrar na tela todos os 
elementos da lista em um dado momento: 
void printLista(OrdList* lista){ 
 int i; 
 if (lista->count == 0){ 
 printf("Lista vazia: nenhum inimigo ativo!\n\n"); 
 } else { 
 printf("Conteudo da lista:\n"); 
 for (i=0; i<lista->count; i++){ 
 printf("-Inimigo %d com %.2f de vida.\n", lista-
>enemies[i].enemyId, lista->enemies[i].vida); 
 } 
 printf("\n"); 
 } 
} 
a) Crie uma struct para abrigar a lista e defina-a como tipo OrdList. Essa struct 
deve conter o array correspondente à lista e um int para guardar o número de 
inimigos dentro da lista. 
b) Escreva a função inicializarLista que aloca memória para a lista. 
c) Escreva a função inserir para adicionar um inimigo à lista. Neste primeiro 
momento, não há problema em inserir inimigos repetidos. 
d) Escreva a função localizar que retorna a posição, de 0 a count-1, em que o 
inimigo com dada vida se encontra na lista. Sua complexidade assintótica deve ser de 
O(logn), ou seja: implemente a busca binária. Caso não seja encontrado inimigo 
correspondente, a função retorna -1. 
e) Modifique a função inserir para que, através de uma chamada à função 
localizar, ela impeça a inserção de inimigos com vidas repetidas. 
 f) Escreva a função dealDamage que, utilizando a função localizar, remove da 
lista um inimigo com a vida correspondente e comunica ao jogador o resultado. 
 
 
 
 
3.2) [Lista Duplamente Encadeada] Projete uma estrutura do tipo lista 
duplamente encadeada para abrigar os IDs dos usuários ativos em uma certa 
aplicação. A estrutura de um nó da lista é a seguinte: 
typedef struct Node{ 
 int userId; 
 struct Node* pProx; 
 struct Node* pAnt; 
}Element; 
Ao final do projeto, seu programa deve rodar as seguintes funções. Note que algumas 
delas retornam um código de erro. O output pode ser visto na imagem abaixo: 
int inserir(Element** lista, int userId); 
int remover(Element** lista, int userId); 
void printLista(Element* lista); 
int main(){ 
 Element* lista = NULL; //Lista criada 
 int errorCode; 
 errorCode = inserir(&lista, 89); 
 errorCode = inserir(&lista, 45); 
 errorCode = inserir(&lista, 76); 
 errorCode = inserir(&lista, 21); 
 printlista(lista); 
 errorCode = remover(&lista, 21); 
 errorCode = remover(&lista, 89); 
 printlista(lista); 
 errorCode = inserir(&lista, 75); 
 printlista(lista); 
} 
a) Escreva a função inserir, que cria e insere um nó na primeira posição da lista 
duplamente encadeada. Para simplificar o projeto, não se preocupe em casos de 
inserção de um ID repetido. 
b) Escreva a função printLista, que mostra na tela todos os IDs dos usuários 
ativos num dado momento. 
c) Escreva a função remover, que exclui um certo ID de usuário da lista e 
mostra na tela o ID removido. 
 
 
 
4. Árvores 
 
 
4.1) [Árvore Binária de Busca] Projete uma estrutura do tipo Árvore Binária de Busca 
para armazenar produtos de uma loja de conveniência. A árvore será ordenada pelo 
número de matrícula dos produtos, que serão guardados na seguinte struct: 
struct Produto{ 
 int matricula; 
 float preco; 
}; 
Ao final do projeto, você deve ser capaz de executar o seguinte código. O output 
encontra-se na imagem abaixo: 
int adicionar (No** arv, int matricula, float preco); 
int preco(No** arv, int matricula); 
int main(){ 
 No* arv = NULL; 
 int errorCode; 
 errorCode = adicionar(&arv, 100, 5.90); 
 errorCode = adicionar (&arv, 200, 8.40); 
 errorCode = adicionar (&arv, 250, 2.20); 
 errorCode = adicionar (&arv, 500, 3.80); 
 errorCode = adicionar (&arv, 400, 5.60); 
 errorCode = adicionar (&arv, 150, 7.90); 
 errorCode = preco(&arv, 400); 
 errorCode = preco(&arv, 240); 
 errorCode = preco(&arv, 150); 
} 
 a) Crie uma struct para abrigar um nó da árvore e defina-a como tipo No. Esta 
struct deve conter um produto e os dois ponteiros correspondentes aos nós filhos. 
b) Escreva a função adicionar, que cria e insere um nó na árvore binária, 
indexando o produto pelo número de sua matrícula. 
c) Escreva a função preco, que busca na árvore binária pelo número de 
matrícula do produto desejado e imprime na tela seu preço correspondente. 
 
 
4.2) [Ordem de Busca] Suponha que produtos com códigos 770, 875, 007, 059, 068, 
682, 588, 067, 234, 411, 191 e 512 sejam inseridos, nesta ordem, em uma estrutura 
vazia do tipo Árvore Binária de Busca. 
a) Desenhe a árvore resultante (grafo) após a inserção de todos os itens, 
representando o código do produto dentro de cada nó. 
b) Determine em que sequência esses elementos seriam processados por um 
algoritmo que execute um percurso em pré-ordem. 
c) Determine em que sequência esses elementos seriam processados por um 
algoritmo que execute um percurso em pós-ordem. 
d) Determine em que sequência esses elementos seriam processados por um 
algoritmo que execute um percurso em ordem simétrica. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
A. Respostas 
A.1 Pilhas 
 
1.1) a) 
typedef struct{ 
 PageData itens[MAX]; 
 int topo; 
}Stack; 
 
 b) 
Stack* inicializarPilha(){ 
 Stack* pilha; 
 pilha = malloc(sizeof(Stack)); 
 if (pilha == NULL){ 
 printf("Erro ao inicializar pilha!\n\n"); 
 } 
 pilha->topo = 0; 
 return pilha; 
} 
 
 c) 
int push(Stack* pilha, char* adress, int connectionType){ 
 if (pilha == NULL){ 
 printf("Pilha nao inicializada!\n\n"); 
 return -1; 
 } 
 if (pilha->topo == MAX){ 
 printf("Pilha cheia! Impossivel inserir\n\n"); 
 return -2; 
 } 
 strcpy(pilha->itens[pilha->topo].adress, adress); 
 pilha->itens[pilha->topo].connectionType = connectionType; 
 pilha->topo++; 
 return 1; 
} 
 d) 
int pop(Stack* pilha){ 
 if (pilha == NULL){ 
 printf("Pilha nao inicializada!\n\n"); 
 return -1; 
 } 
 if (pilha->topo == 0){ 
 printf("Pilha vazia! Impossivel remover\n\n"); 
 return -2; 
 } 
 pilha->topo--; 
 printf("Endereco removido: %s, conectado com tipo %d\n\n", pilha->itens[pilha-
>topo].adress, pilha->itens[pilha->topo].connectionType); 
 return 1; 
} 
 
1.2) a) 
void printPilha(Element* inicio){ 
 Element* temp = inicio; 
 if (temp == NULL){ //Caso de pilha vazia 
 printf("Pilha vazia!\n\n"); 
 } else { 
 printf("Dados da pilha: "); 
 while (temp != NULL){ 
 printf("%d, ", temp->valor); //Percorre a pilha 
 temp = temp->pProx; 
 } 
 printf("\b\b.\n\n"); 
 } 
} 
 
 b) 
void push(Element** inicio, int valor){ 
 Element* nextNode; 
 //Aloca e configura o novo elemento:nextNode = malloc(sizeof(Element)); 
 if (nextNode == NULL){ 
 printf("Erro ao inicializar no!\n\n"); 
 return; 
 } 
 nextNode->valor = valor; 
 //Faz a cirurgia na fila, adicionando na 1a posicao: 
 nextNode->pProx = *inicio; 
 *inicio = nextNode; 
 return; 
} 
 
 c) 
int pop(Element** inicio){ 
 Element* temp; 
 temp = *inicio; 
 if (temp == NULL){ //Caso de pilha vazia 
 printf("Pilha vazia: nao ha nada a remover.\n\n"); 
 return 0; 
 } else { 
 int valor = temp->valor; 
 *inicio = temp->pProx; 
 free(temp); 
 printf("Valor %d removido com sucesso.\n\n", valor); 
 return valor; 
 } 
} 
 
 
A.2 Filas 
 
2.1) a) 
typedef struct{ 
 PrintingData itens[MAX]; 
 int fim; 
}Queue; 
 
 b) 
Queue* inicializarFila(){ 
 Queue* fila; 
 fila = malloc(sizeof(Queue)); 
 if (fila == NULL){ 
 printf("Erro ao inicializar fila!\n\n"); 
 } 
 fila->fim = 0; 
 return fila; 
} 
 
 c) 
int inserir(Queue* fila, int customerId, double price){ 
 if (fila == NULL){ 
 printf("Fila nao inicializada!\n\n"); 
 return -1; 
 } 
 if (fila->fim == MAX){ 
 printf("Fila cheia! Impossivel inserir\n\n"); 
 return -2; 
 } 
 fila->itens[fila->fim].customerId = customerId; 
 fila->itens[fila->fim].price = price; 
 fila->fim++; 
 return 1; 
} 
 
 
 d) 
 
int remover(Queue* fila){ 
 if (fila == NULL){ 
 printf("Fila nao inicializada!\n\n"); 
 return -1; 
 } 
 if (fila->fim == 0){ 
 printf("Fila vazia! Impossivel remover\n\n"); 
 return -2; 
 } 
 fila->fim--; 
 printf("Imprimindo para cliente %d por R$%.2f.\n\n", fila->itens[0].customerId, 
fila->itens[0].price); 
 int temp; 
 for (temp = 0; temp<(fila->fim); temp++){ 
 fila->itens[temp] = fila->itens[temp+1]; 
 } 
 return 1; 
} 
 
2.2) a) 
CircQueue* inicializarFila(int capacidade){ 
 CircQueue* fila; 
 fila = malloc(sizeof(CircQueue)); 
 if (fila == NULL){ 
 printf("Erro ao inicializar fila!\n\n"); 
 } 
 fila->inicio = 0; //Inicio sempre marca o primeiro elemento ocupado 
 fila->fim = 0; //Fim sempre marca o proximo elemento vazio 
 fila->count = 0; 
 fila->capacidade = capacidade; 
 if (capacidade > 0) { 
 fila->users = malloc(capacidade*sizeof(*(fila->users))); 
 } else { 
 printf("Capacidade invalida!"); 
 } 
 if (fila->users == NULL){ 
 printf("Erro ao alocar espaço para a fila!\n\n"); 
 } 
 return fila; 
} 
 b) 
int inserir(CircQueue* fila, int userId){ 
 if (fila == NULL){ 
 printf("Fila nao inicializada!\n\n"); 
 return -1; 
 } 
 if (fila->count == fila->capacidade){ 
 printf("Fila cheia! Impossivel inserir\n\n"); 
 return -2; 
 } 
 fila->users[fila->fim] = userId; 
 fila->count++; 
 fila->fim++; 
 if (fila->fim == fila->capacidade){ //Caso em que indice saiu do array 
 fila->fim = 0; 
 } 
 return 1; 
} 
 
 c) 
int remover(CircQueue* fila){ 
 if (fila == NULL){ 
 printf("Fila nao inicializada!\n\n"); 
 return -1; 
 } 
 if (fila->count == 0){ //Checagem de fila vazia 
 printf("Fila vazia! Impossivel remover\n\n"); 
 return -2; 
 } 
 //Imprime o inicio da fila: 
 printf("Usuario %d autorizado a comprar.\n\n", fila->users[fila->inicio]); 
 fila->count--; 
 fila->inicio++; 
 //Se o inicio da fila estourou o array, volta com ele pro indice zero: 
 if (fila->inicio == fila->capacidade){ 
 fila->inicio = 0; 
 } 
 return 1; 
} 
 
 
A.3 Listas 
 
3.1) a) 
typedef struct{ 
 EnemyData enemies[MAX]; 
 int count; 
}OrdList; 
 
 b) 
OrdList* inicializarLista(){ 
 OrdList* lista; 
 lista = malloc(sizeof(OrdList)); 
 if (lista == NULL){ 
 printf("Erro ao inicializar lista!\n\n"); 
 } 
 lista->count = 0; 
 return lista; 
} 
 
 c) 
int inserir(OrdList* lista, int vida, double ataque){ 
 if (lista == NULL){ 
 printf("Lista nao inicializada!\n\n"); 
 return -1; 
 } 
 if (lista->count == MAX){ 
 printf("Lista cheia! Impossivel inserir\n\n"); 
 return -2; 
 } 
 //Busca comecando do fim. Se a vida do elemento i for maior, move este para a 
direita: 
 int i; 
 for (i=(lista->count)-1; lista->enemies[i].vida>vida && i>=0; i--){ 
 lista->enemies[i+1].vida = lista->enemies[i].vida; 
 lista->enemies[i+1].ataque = lista->enemies[i].ataque; 
 } 
 //Quebra o loop caso o elemento i tiver uma vida menor. Logo, precisamos inserir 
em i+1: 
 lista->enemies[i+1].vida = vida; 
 lista->enemies[i+1].ataque = ataque; 
 //Incrementa o numero de itens da lista: 
 lista->count++; 
 return 1; 
} 
 
 
 d) 
int localizar(OrdList* lista, int vida) { 
 int i=0, f=(lista->count)-1, m, c; 
 while (i <= f) { 
 m = (i+f)/2; 
 c = lista->enemies[m].vida - vida; 
 if (c == 0){ 
 return m; 
 } else if (c > 0) { 
 f = m-1; 
 } else { 
 i = m+1; 
 } 
 } 
 return -1; 
} 
Idealisticamente, seria bom que esta função já retornasse a posição de inserção 
de um inimigo quando não encontrasse um resultado. Isto nos pouparia trabalho no 
item seguinte, que pede uma modificação na função de inserir. Porém, para manter 
certa simplicidade ao projeto, a função apenas retorna -1 nestes casos. 
 
 
 e) Após a checagem de lista cheia, insira as seguintes linhas: 
if (localizar(lista, vida) != -1){ 
 printf("Inimigo ja existente!\n\n"); 
 return -3; 
} 
 
 
 f) 
int dealDamage(OrdList* lista, int vida){ 
 if (lista == NULL){ 
 printf("Lista nao inicializada!\n\n"); 
 return -1; 
 } 
 if (lista->count == 0){ 
 printf("Lista vazia! Impossivel dealDamage\n\n"); 
 return -2; 
 } 
 //Busca pela posicao do inimigo: 
 int i = localizar(lista, vida); 
 if (i == -1){ 
 printf("Nao acertou nenhum inimigo!\n\n"); 
 return -3; 
 } 
 printf("Inimigo com %d de vida derrotado com sucesso!\n\n", lista-
>enemies[i].vida); 
 //Traz o restante da fila uma posicao para tras: 
 while (i<(lista->count-1)){ 
 lista->enemies[i].vida = lista->enemies[i+1].vida; 
 lista->enemies[i].ataque = lista->enemies[i+1].ataque; 
 i++; 
 } 
 lista->count--; 
 return 1; 
} 
 
3.2) a) 
int inserir(Element** lista, int userId){ 
 Element *nextNode; 
 //Aloca o proximo elemento: 
 nextNode = malloc(sizeof(Element)); 
 if (nextNode == NULL){ 
 printf("Falha ao alocar proximo no!\n\n"); 
 return -1; 
 } 
 nextNode->userId = userId; 
 //Faz com que nextNode aponte para o primeiro elemento: 
 if (*lista == NULL){ 
 //Caso lista vazia 
 nextNode->pProx = NULL; 
 } else { 
 nextNode->pProx = *lista; 
 (*lista)->pAnt= nextNode; 
 } 
 //Torna nextNode o primeiro elemento da lista: 
 nextNode->pAnt = NULL; 
 *lista = nextNode; 
 return 1; 
} 
 
 b) 
void printLista(Element* lista){ 
 Element* temp = lista; 
 if (temp == NULL){ //Caso de lista vazia 
 printf("Lista vazia!\n\n"); 
 } else { 
 printf("Usuarios na lista: "); 
 while (temp != NULL){ 
 printf("%d, ", temp->userId); 
 temp = temp->pProx; //Percorre a lista 
 } 
 printf("\b\b.\n\n"); 
 } 
} 
 
 c) 
int remover(Element** lista, int userId){ 
 Element* temp = *lista; 
 //Repete ate chegar no fim da fila: 
 while (temp != NULL){ 
 //Testa se o usuario foi encontrado: 
 if (temp->userId == userId){ 
 //Faz a cirurgia na lista: 
 if (temp->pAnt == NULL){ 
 //Caso primeiro elemento da fila: 
 *lista = temp->pProx; 
 if (temp->pProx != NULL) temp->pProx->pAnt = NULL; 
 } else { 
 //Proxima linha somente ocorre se temp nao for o ultimo elemento: 
 if (temp->pProx != NULL) temp->pProx->pAnt = temp->pAnt; 
 temp->pAnt->pProx = temp->pProx; 
 } 
 printf("Usuario %d removido da lista.\n\n", userId); 
 free(temp); 
 return 1; 
 } else { 
 temp = temp->pProx; 
 } 
 } 
 printf ("Usuario nao encontrado para remocao!\n\n"); 
 return -1; 
} 
 
 
A.4 A rvores 
 
4.1) a) 
typedef struct Elemento{ 
 struct Produto produto; 
 struct Elemento* esq; 
 struct Elemento* dir; 
}No; 
 
 b) 
int adicionar(No** arv, int matricula, float preco){ 
 No* newNode; 
 //Aloca memoria para o no: 
 newNode = malloc(sizeof(No)) 
 if (newNode == NULL){ 
 printf("Falha ao alocar novo no!\n\n"); 
 return -1; 
 } 
 //Configura os dados do no: 
 newNode->produto.matricula = matricula; 
 newNode->produto.preco = preco; 
 newNode->esq = NULL; 
 newNode->dir = NULL; 
 //Checa se a arvore esta vazia e, se sim, adiciona o no: 
 if (*arv == NULL){ 
 *arv = newNode; 
 return 1; 
 } 
 //Procura onde adicionar o elemento: 
 No* atual = *arv; 
 No* anterior = atual; 
 while (atual != NULL){ 
 anterior = atual; 
 if (atual->produto.matricula > matricula){ 
 //Indo pelo no da esquerda 
 atual = atual->esq; 
 } else { 
 //Indo pelo no da direita 
 atual = atual->dir; 
 } 
 } 
 //Saimos do loop para estabelecer se o no anterior deve apontar para esquerda ou 
para a direita. De quebra, ainda adicionamos uma checagem de produto repetido: 
 if (anterior->produto.matricula > matricula){ 
 anterior->esq = newNode; 
 return 1; 
 } else if (anterior->produto.matricula < matricula){ 
 anterior->dir = newNode; 
 return 1; 
 } else { 
 printf("Produto ja cadastrado!\n\n"); 
 return -2; 
 } 
} 
 
 c) 
int preco(No** arv, int matricula){ 
 //Checa se a arvore esta vazia: 
 if (*arv == NULL){ 
 printf("Erro: Arvore vazia!\n\n"); 
 return 0; 
 } 
 //Prepara para pesquisar na arvore: 
 No* atual = *arv; 
 No* anterior = atual; 
 while (atual->produto.matricula != matricula){ 
 anterior = atual; 
 if (atual->produto.matricula > matricula){ 
 //O percurso segue pelo no esquerdo 
 atual = atual->esq; 
 } else if (atual->produto.matricula < matricula){ 
 //O percurso segue pelo no direito 
 atual = atual->dir; 
 } 
 //Caso em que chegamos em um no inexistente e portanto o item nao foi 
encontrado: 
 if (atual == NULL){ 
 printf("Erro: Produto %d nao encontrado!\n\n", matricula); 
 return 0; 
 } 
 } 
 //Quando o loop quebra, o item foi encontrado e esta sendo apontado pela 
variavel 'atual': 
 printf("O produto %d custa R$%.2f.\n\n", matricula, atual->produto.preco); 
 return 1; 
} 
 
4.2) a) O esquema representando a árvore pode ser visto abaixo: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 b) Em pré-ordem, leríamos os elementos desta forma: 
 770 → 007 → 059 → 068 → 067 → 682 → 588 → 234 → 191 → 411 → 512 → 875 
 
 c) Em pós-ordem, leríamos os elementos desta forma: 
 067 → 191 → 512 → 411 → 234 → 588 → 682 → 068 → 059 → 007 → 875 → 770 
 
 d) Em ordem simétrica, leríamos os elementos desta forma: 
 007 → 059 → 067 → 068 → 191 → 234 → 411 → 512 → 588 → 682 → 770 → 875 
B. Bibliografia 
 
 CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. 
Algoritmos: Teoria e Prática. Tradução de: Introduction to Algorithms, 3rd ed. 
Rio de Janeiro: Elsevier, 2012. 
 Slides do professor Heraldo L. S. de Almeida. Disponível em: 
<http://www.del.ufrj.br/~heraldo/eel470.html>. Acessado em: 16/07/2016.