Lista Estrutura de Dados

Prévia do material em texto

LISTAS LINEARES 
 
1) Desenvolva um programa com uma subrotina que permita a inclusão de um elemento em uma lista 
simplesmente encadeada que armazena valores inteiros, numa determinada posição. A subrotina 
deverá receber a lista, a informação e a posição em que a nova informação será incluída. Caso a 
posição seja maior que o número de elementos existentes na lista, a mesma deverá ser incluída no 
final. Considere a possibilidade da lista, no início estar vazia. 
 
2) Você deverá implementar um tipo abstrato de dados TConjunto (lista simplesmente encadeada) para 
representar conjuntos de números inteiros. Seu tipo abstrato deverá armazenar os elementos do 
conjunto e o seu tamanho N. Considere que o tamanho máximo de um conjunto é de 20 elementos e 
use arranjos de 1 dimensão (vetores) para a sua implementação. Seu TAD deve possuir procedimentos 
(ou funções quando for o caso) para: 
 
a) Criar um conjunto vazio; 
b) Ler os dados de um conjunto; 
c) Fazer a união de dois conjuntos; 
d) Fazer a intersecção de dois conjuntos; 
e) Verificar se dois conjuntos são iguais (possuem os mesmos elementos); 
f) Imprimir a união e a intersecção dos dois conjuntos ; 
 
3) Criar um programa que implemente uma lista simplesmente encadeada que armazene valores reais, 
estruturado com as seguintes operações: 
 
a) Inserir um dado elemento na primeira posição da lista; 
b) Inserir um dado elemento na última posição da lista; 
c) Modificar um elemento da lista, sendo dados a sua posição e o novo valor; 
d) Remover o primeiro elemento da lista; 
e) Remover o último elemento da lista; 
f) Remover um elemento dado o seu valor. 
 
4) Faça um programa que implemente uma subrotina para ordenar uma lista simplesmente encadeada 
de números inteiros, previamente lida em ordem crescente. Antes de construir a rotina, faça a definição 
do tipo da lista: RECORD e tipo apontador. Liste na tela a lista devidamente ordenada. 
 
5) Considere uma lista simplesmente encadeada que armazene dados literais (NOME), desenvolva um 
programa estruturado conforme o quadro abaixo: 
 
 
 
LISTA DE EXERCÍCIOS III – 4º Bimestre – LTP & LPI. 
Estruturas de Dados 
 
Profº.: Marcelo Cunha de Oliveira Turma: 1º AI/1º AM 
Aluno: Nº: 
 
 
 
OBS: observe que todas as operações precisam considerar que se trata de uma lista ordenada. 
 
6) Faça um programa que armazene o Nome, idade, e sexo de uma pessoa em uma estrutura 
simplesmente encadeada na memória. Implemente as seguintes operações: 
 
a) Inserir um registro lido no início da lista; 
b) Contar quantos elementos existem nesta lista simplesmente encadeada e imprimir na tela; 
c) Verificar se uma determina pessoa existe na lista. A consulta pode ser feita pelo Nome da pessoa. 
Listar os dados desta pessoa. 
d) Faça uma subrotina que elimine um determinado registro da lista. A consulta pode ser feita pelo 
Nome da pessoa. Pode ser que a lista não contenha o registro pesquisado, use mensagens. 
 
7) Considere uma lista (a sua escolha) que armazena os dados dos alunos da FNE (código e nome). 
Desenvolva um programa que implemente os seguintes módulos: 
 
a) Faça um procedimento recursivo para imprimir uma lista de alunos, na ordem da lista; 
b) Faça um procedimento recursivo para imprimir uma lista de alunos, na ordem inversa da lista; 
c) Faça um procedimento não recursivo para inserir um aluno no fim da lista; 
d) Faça um procedimento recursivo para remover um aluno com certo nome da lista; 
e) Faça um procedimento recursivo para duplicar e imprimir uma lista em ordem inversa. 
 
8) Desenvolva um programa com uma subrotina que permita a inclusão de um elemento numa lista 
duplamente encadeada em uma determinada posição. A subrotina deverá receber a lista, a informação 
(inteiros) e a posição em que a nova informação será incluída. Caso a posição seja maior que o número 
de elementos atualmente existentes na lista, a mesma deverá ser incluída no final. Considere a 
possibilidade da lista no início estar vazia. Liste a lista completa na saída. 
 
9) Faça um programa que armazene o Nome, idade, sexo e salário de uma pessoa em uma estrutura 
duplamente encadeada na memória. Estruture o programa com as seguintes operações: 
 
a) Desenvolva uma subrotina para inserir o registro no início da lista; 
b) Desenvolva uma subrotina para inserir o registro no final da lista; 
c) Faça uma subrotina que elimine o primeiro elemento da lista, se o mesmo existir. 
d) Faça uma subrotina que elimine o segundo elemento da lista, se o mesmo existir. 
e) Faça uma subrotina que elimine o último elemento da lista, se o mesmo existir; 
f) Desenvolva uma subrotina para listar os dados da lista. 
 
10) Crie um programa com uma subrotina para ordenar uma lista duplamente encadeada de números 
inteiros previamente lida em ordem crescente. Antes de construir a Rotina, faça a definição do tipo da 
lista: RECORD e o tipo apontador. Aproveitando a lista ordenada, faça também uma subrotina para 
listar o conteúdo da lista em ordem crescente. 
 
11) Desenvolva um programa com uma função que rearranja os elementos de uma lista duplamente 
encadeada dada, pondo todos os elementos que ocorrem nas posições pares antes de todos os 
elementos de ocorrem nas posições ímpares. Você deve preservar a ordem relativa dos elementos 
 
 
pares entre si, e a ordem relativa dos elementos Ímpares entre si. Imprima na saída a lista original e a 
lista posteriormente reorganizada. 
 
12) Quando temos uma lista ligada só podemos caminhar por esta lista apenas em um dos sentidos. Uma 
maneira de contornar este tipo de restrição é usar uma lista duplamente ligada. Neste tipo de lista 
temos em cada elemento dois campos de ligação. Um chamado próximo, que tem a mesma função que 
o campo próximo em listas ligadas e outro campo chamado anterior, que aponta para um elemento 
anterior na seqüência definida pelo campo próximo. O primeiro elemento da lista tem seu campo 
anterior com valor nil. A figura seguinte apresenta uma lista duplamente ligada com 4 elementos. Faça 
um programa com rotinas para inserção no início da lista, remoção do primeiro elemento, remoção de 
um elemento com um determinado nome e listagem dos dados da lista. 
 
13) Crie um programa com as definições de tipo necessárias para criar, uma estrutura na memória como a 
que é representada na figura abaixo: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
a) Dicionário é um vetor ( de “A” até “Z”) de pointers para uma estrutura duplamente encadeada onde 
além dos campos “Prox” e “Ant” , existem mais dois campos STRING os quais representam a 
palavra e o seu significado. 
 
b) A lista de palavras que estão ligadas ao índice “A” do vetor, corresponde àquelas palavras que 
iniciam com a letra “A”, e assim por diante. 
 
c) Desenvolva uma subrotina para inclusão de uma palavra e o seu significado no dicionário de 
palavras. Lembre-se que a palavra e o seu significado não devem ser incluídas em qualquer lista de 
forma aleatória, a inclusão dever ser feita somente na lista cujo índice do vetor corresponde à 
primeira letra da palavra. Desta forma, caso a palavra, fosse “Cavalo”, esta palavra, junto com o seu 
significado, deveriam ser incluídos na lista existente no índice “C” do vetor. 
 
14) Escreva um programa que simule uma pilha usando vetores e ponteiros. O programa deve implementar 
as seguintes operações sobre os dados da pilha: 
 
a) Inserir; 
b) Remover; 
c) Listar (do último inserido ao primeiro). 
A 
B NIL 
C 
D NIL 
... 
Z 
 
 
 
15) Escreva um programa uma função que imprime os elementos de uma pilha na mesma ordem em que 
eles foram empilhados, como no exemplo abaixo: 
 
 
 
O conteúdo da pilha deve ser o mesmo antes e depois da execução da função. Pode ser utilizado uma 
pilha auxiliar. 
 
16) Considere uma pilha que armazene dadosinteiros, desenvolva um programa estruturado conforme o 
quadro abaixo: 
 
 
 
17) Existem, basicamente, duas operaçöes a serem implementadas nas filas: adicionar e remover. É 
comum a utilizaçäo de um ponteiro para o início e outro para o fim da fila, facilitando assim as 
operaçöes. 
 
Adicionar - procedure adiciona (var inicio : ponteiro ; info : InfoType); 
Remover - function remove (var inicio : ponteiro) : InfoType; 
 
A partir dos protótipos descritos acima, desenvolva um programa que represente uma fila, 
implementando os módulos Adicionar e Remover. 
 
18) Considere uma fila que armazene dados reais, desenvolva um programa estruturado conforme o 
quadro abaixo: 
 
 
 
 
19) Uma fila simétrica permite a realização das operações de inserção e remoção em ambas as 
extremidades. Considere uma implementação em que o tipo Fila Simétrica é uma estrutura que contém 
apontadores para o primeiro e para o último elemento da fila, sendo esta implementada através de uma 
lista duplamente ligada. 
Implemente as funções para criar fila, enfileirar, desenfileirar e destruir a fila. 
 
 
 
 
 
20) Considere a figura abaixo: 
 
 
 
 
 
Da mesma forma que uma lista encadeada é representada por um ponteiro para o primeiro nó, a 
estrutura da árvore como um todo é representada por um ponteiro para o nó raiz. 
 
Como veremos as funções que manipulam árvores são, em geral, implementadas de forma recursiva, 
usando a definição recursiva da estrutura. Como uma árvore é representada pelo endereço do nó raiz, 
uma árvore vazia tem que ser representada pelo valor NIL. Para criar árvores não vazias, podemos ter 
uma operação que cria um nó raiz dadas à informação e suas duas sub-árvores, à esquerda e à direita. 
Essa função tem como valor de retorno o endereço do nó raiz criado. 
 
As duas funções inicializam e criam (direita e esquerda) representam os dois casos da definição 
recursiva de árvore binária. Usando as operações inicializa e cria, crie uma estrutura que represente a 
árvore da figura acima. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Feliz Natal!!!