Lista de Exercícios - Estrutura de Dados

Prévia do material em texto

Universidade Estadual da Paraíba 
Centro de Ciências e Tecnologia 
Departamento de Computação 
Disciplina: Linguagem de Programação C 
 
 
LISTA DE ESTRUTURA DE DADOS 
 
 
1) Elabore um algoritmo para a inclusão de elementos numa lista encadeada simples 
(um único ponteiro de célula) a partir do seu início. Lembre-se de verificar quando 
a célula é a primeira a ser inserida na lista. Faça a simulação desenhando os passos 
da inclusão. 
2) Declare a estrutura padrão das células da lista do exercício (1). 
3) Crie uma lista com 3 elementos inserindo os valores 2, 7 e 15 na ordem 
apresentada. 
4) Escreva os passos necessários em linguagem C para inserir o elemento 9 na lista 
do exercício (3) de forma que a lista permaneça ordenada. 
5) Exclua o elemento que contém o valor 7 da lista em (4). (sem perder os ponteiros!) 
6) Sendo o “inicio” o ponteiro para o começo da lista de (4) e “valor” o dado do tipo 
int de cada elemento, escreva o código para imprimir os valores de: 
a. inicio->valor 
b. inicio->prox->valor 
7) Escreva uma rotina em C para a inserção, uma para exclusão e uma para consulta 
de elementos numa fila implementada com vetores. 
8) Dada uma fila (representada por uma lista encadeada), elabore a função em C para 
consulta do primero elemento da fila. 
9) Elabore as rotinas de inclusão e exclusão de elementos de uma fila implementada 
com listas dinâmicas, supondo que a inclusão ocorre no início e a exclusão no 
final. Utilize uma lista duplamente encadeadas. 
10) Escreva uma função em C para a inclusão, uma para exclusão e uma para consulta 
de elementos numa pilha implementada com vetores. 
11) Elabore a rotina em C para consulta do primero elemento da pilha, supondo que 
esta foi implementada com listas dinâmicas. 
12) Elabore as rotinas de inclusão e exclusão de elementos numa pilha supondo que o 
topo da pilha se localiza no final da lista. 
13) Escreva uma função que conta o número de elementos de uma lista encadeada. 
14) Critique a função abaixo. Ao receber uma lista encadeada com cabeça e um 
inteiro x, ela promete devolver o endereço de uma célula com conteúdo x. Se tal 
célula não existe, promete devolver NULL. 
celula *busca( int x, celula *ini) { 
 int achou; 
 celula *p; 
 achou = 0; 
 p = ini->prox; 
 while (p != NULL && !achou) { 
 if (p->conteudo == x) achou = 1; 
 p = p->prox; } 
 if (achou) return p; 
 else return NULL; 
} 
 
15) Escreva uma versão da função busca para listas sem cabeça. 
16) Por que a seguinte versão de insere não funciona? 
void insere( int x, celula *p) { 
 celula nova; 
 nova.conteudo = x; 
 nova.prox = p->prox; 
 p->prox = &nova; 
} 
 
17) Critique a seguinte versão da função remove: 
void remove( celula *p, celula *ini) { 
 celula *morta; 
 morta = p->prox; 
 if (morta->prox == NULL) p->prox = NULL; 
 else p->prox = morta->prox; 
 free( morta); 
} 
18) Descreva, em linguagem C, a estrutura de uma das célula de uma lista duplamente 
encadeada. 
19) Escreva uma função que remove de uma lista duplamente encadeada a célula 
apontada por p. (Que dados sua função recebe? Que coisa devolve?) 
20) Escreva uma função que insira em uma lista duplamente encadeada, logo após a 
célula apontada por p, uma nova célula com conteúdo y. (Que dados sua função 
recebe? Que coisa devolve?) 
21) Escreva uma função para remover de uma lista encadeada todos os elementos que 
contêm y. 
22) Escreva funções empilha e desempilha para manipular uma pilha representada 
por array. Lembre-se de que uma pilha é um pacote com dois objetos: um vetor e 
um índice. Não use variáveis globais. Quais os parâmetros de suas funções? 
23) Implemente um pilha em uma lista encadeada sem célula-cabeça. A pilha será dada 
pelo endereço da primeira célula da lista (que é também o topo da pilha). 
24) Implemente uma fila em uma lista encadeada simples sem célula-cabeça. Será 
preciso manter um ponteiro ini para a primeira célula e um ponteiro fim para a 
última.