Notas de aula Estrutura de dados

Prévia do material em texto

1 
ED – Notas de Aula 01 
 
Capítulo 1 – Introdução 
 
 
 
 Ao concluir este capítulo, você deverá ser capaz de: 
 
- Conhecer as formas mais básicas de organizar os dados na memória de um computador, de 
forma que essa organização reflita bem o problema que está sendo tratado e torne mais efici-
entes os algoritmos que manipulem esses dados. 
 2 
Introdução 
 
 Na resolução de um problema através de um programa, a primeira providência é con-
ceber um algoritmo adequado. 
 
[Um algoritmo é um processo sistemático para a resolução de um problema, consistindo de 
uma seqüência de passos, ordenada e sem ambigüidades.] 
 
 A eficiência de um algoritmo está intimamente relacionada com a disposição, na me-
mória, dos dados que são tratados pelo programa. Por exemplo, se freqüentemente enfrenta-
mos o problema de descobrir o número do telefone de nossos conhecidos, é conveniente dis-
por de uma relação de números organizada em uma agenda. Se a organização for feita pela 
ordem alfabética, a agenda de fato ajuda. Se, porém, organizássemos nossa agenda pela ordem 
de altura das pessoas, com raras exceções, a agenda se tornaria difícil de manusear. 
 
 As estruturas de dados são formas de distribuir e relacionar os dados disponíveis, de 
modo a tornar mais eficientes os algoritmos que manipulam esses dados. 
 
 Vejamos alguns exemplos práticos 
 
Situação 1 
 
problema: Manipular um conjunto de fichas em um fichário. 
 
solução: Organizar as fichas em ordem alfabética. 
 
operações possíveis: Inserir ou retirar uma ficha, procurar uma ficha, etc. 
 
estrutura de dados: LISTA – seqüência de elementos dispostos em alguma ordem. 
 
 
 
 
 3 
 
Situação 2 
 
problema: Organizar as pessoas que querem ser atendidas em um guichê. 
 
solução: Colocar as pessoas em fila. 
 
operações possíveis: Atender uma pessoa no guichê, entrar uma pessoa no final da fila. Não 
é permitido “furar” a fila, ou seja, entrar uma pessoa entre outras que já estão presentes. 
 
estrutura de dados: FILA – seqüência de elementos dispostos em ordem, mas com uma 
regra para a entrada e saída dos elementos: o primeiro elemento que chega também é o pri-
meiro que sai da estrutura. 
 
 
 
 
 
 4 
 
Situação 3 
 
problema: Organizar um conjunto de pratos que estão sendo lavados, um a um, em um res-
taurante. 
 
solução: Colocar os pratos empilhados. 
 
operações possíveis: Colocar um prato limpo no alto da pilha, retirar um prato do alto da 
pilha. Não é permitido tirar um prato qualquer do meio da pilha. 
 
estrutura de dados: PILHA - seqüência de elementos dispostos em ordem, mas com uma 
regra para a entrada e saída dos elementos: o último que chega é o primeiro a sair da estrutura. 
 
 
 
 
 
 5 
Situação 4 
 
problema: Conseguir um modo de visualizar o conjunto de pessoas que trabalham em uma 
empresa, tendo em conta a função de cada pessoa. 
 
solução: Construir um organograma da empresa. 
 
operações possíveis: Inserir ou retirar certas funções, localizar uma pessoa, etc. 
 
estrutura de dados: ÁRVORE – estrutura de dados que caracteriza uma relação de hierar-
quia entre os elementos: uma pessoa não pode pertencer a dois departamentos diferentes, cada 
diretoria tem os seus próprios departamentos, etc. 
 
 
 
 
 
 6 
Situação 5 
 
problema: Estabelecer um trajeto para percorrer todas as capitais de um país. 
 
solução: Utilizar um mapa que indique as rodovias existentes, e estabelecer uma ordem pos-
sível para percorrer todas as cidades 
 
operações possíveis: Encontrar um modo de percorrer todas as cidades, determinar o cami-
nho mais curto para ir de uma cidade a outra, etc. 
 
estrutura de dados: GRAFO – estrutura que organiza vários elementos, estabelecendo rela-
ções entre eles, dois a dois 
 
 
 
 
 
 
 7 
 
 Os exemplos vistos correspondem exatamente aos tipos básicos de estruturas de dados 
utilizadas em computação: listas, filas, pilhas, árvores e grafos. 
 
 As estruturas de dados são abstratas, isto é, devem ser imaginadas como uma forma de 
organizar e relacionar dados na memória do sistema, de modo a permitir certas operações so-
bre esses dados, independentemente do modo como essas estruturas são implementadas. Elas 
podem ser implementadas de diversos modos, dependendo da capacidade da máquina e dos 
recursos oferecidos pela linguagem que se utiliza. 
 
 Neste curso, vamos implementá-las sempre utilizando ponteiros, de modo que o ge-
renciamento da memória seja dinâmico. Isto significa que as estruturas podem ser criadas, 
ampliadas, reduzidas ou removidas da memória em tempo de execução. Desta forma otimiza-
se o uso da memória disponível, em função do conjunto de dados que o programa está proces-
sando. 
 
 
 1 
ED – esquema para tutorial 02 
 
Capítulo 2 – Listas 
 
 
[página de abertura] 
 
 Ao concluir este capítulo, você deverá ser capaz de: 
 
- compreender o que são as listas 
- identificar os tipos mais importantes de listas 
- conhecer as operações básicas que se podem efetuar com as listas 
- tomar contato com algumas aplicações de listas 
 
2.1 Conceitos 
2.2 Implementação 
2.3 Tipos Básicos 
2.4 Algoritmos 
2.5 Aplicações 
 2 
2.1 Conceitos 
 
Uma lista é uma seqüência ordenada de elementos de mesmo tipo. Por exemplo, um conjunto 
de fichas de clientes de uma loja, organizadas pela ordem alfabética dos nomes dos clientes. 
Neste fichário é possível introduzir uma nova ficha ou retirar uma velha, alterar os dados de 
um cliente, etc. 
 
As operações mais básicas que se podem realizar sobre uma lista são: 
 
- construção da lista: montagem da lista na memória do computador, através da leitura dos 
dados de um arquivo. 
 
- percurso por todos os elementos da lista: percorrer todos os elementos da lista, possivel-
mente para obter algum dado ou fazer alguma alteração em todos os elementos da lista. 
 
- procura de um elemento: procura de um elemento na lista, possivelmente para fazer alguma 
alteração nos dados desse elemento. 
 
- inserção de um elemento novo: inserção do novo elemento na lista, tendo em conta a posição 
que ele deve ocupar para manter a lista ordenada. 
 
- remoção de um elemento da lista: retirar um determinado elemento da lista, sendo necessá-
rio para isso, primeiramente encontrar o elemento desejado. 
 
- destruição da lista toda: remover todos os elementos da lista, deixando-a vazia. 
 
 
Outras operações podem ser encontradas no módulo de Aplicações 
 3 
3.2 Implementação 
 
Como já foi dito, as estruturas de dados são abstratas e portanto podem ser implementadas de 
diversos modos. 
 
[estruturas abstratas devem ser imaginadas como uma forma de organizar e relacionar dados na 
memória do sistema, de modo a permitir certas operações sobre esses dados, independentemente do 
modo como essas estruturas são implementadas] 
 
 Para implementar as listas vamos utilizar a técnica de encadeamento por ponteiros. 
Cada elemento de uma lista é um registro que contém, entre outros campos, um campo de tipo 
ponteiro, que aponta para outro elemento da lista. 
 
struct objeto { 
 tipodado dado; 
 struct objeto *prox; 
}; 
 
 
 
 A título de exemplo, vejamos como se poderia construir uma lista contendo a seqüên-
cia de caracteres 'x', 'y', 'z'. Esta função está dividida em três blocos, cada um deles responsá-
vel por acrescentar um dos elementos na lista. 
 
struct elemento { 
 char x; 
 struct elemento *prox; 
}; 
 
struct elemento *pinicio, *p1; 
 
main () { 
 
 pinicio = NULL; 
 
 p1 = malloc (sizeof (struct elemento)); 
 p1->x = 'x'; 
 p1->prox = pinicio; 
 pinicio = p1; 
 
 p1 = malloc (sizeof(struct elemento)); 
 p1->x = 'y'; 
 p1->prox = pinicio; 
 pinicio = p1; 
 
 p1 = malloc (sizeof (struct elemento)); 
 p1->x = 'z'; 
 p1->prox = pinicio; 
 pinicio = p1; 
} 
 
 Se os três blocos forem unificados em apenas um, dentro de um laço comandado pela 
leitura de um arquivo, temos a possibilidade de construir a lista com qualquer número de ele-
Tira Teima 
 4 
mentos. O número de elementos da lista será o número de elementos presentes no arquivo de 
entrada. O programa ficaria do seguinte modo: 
 
struct elemento { 
 char x; 
 struct elemento *prox; 
} ; 
 
struct elemento *pinicio, *p1; 
 
main () { 
 FILE *arq; 
 int c; 
 
 arq = fopen ("t100.txt", "r"); 
 pinicio = NULL; 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 p1 = malloc (sizeof (struct elemento)); 
 p1->x = c; 
 p1->prox = pinicio; 
 pinicio = p1; 
 } 
 } 
Tira Teima 
 5 
3.3 Tipos Básicos de Listas 
 
 
 Há muitos modos de se implementar uma lista através de ponteiros, dependendo da 
disponibilidade de memória, eficiência desejada para os algoritmos, etc. Há dois critérios 
mais básicos para classificar as listas: abertas ou fechadas, com encadeamento simples ou 
encadeamento duplo, dando origem assim a quatro padrões básicos de listas: 
 
lista aberta com encadeamento simples 
 
[ 
] 
 
lista aberta com encadeamento duplo 
 
[ 
] 
 
lista fechada com encadeamento simples 
 
[ 
] 
 
lista fechada com encadeamento duplo 
 
[ 
] 
 
 Nas listas abertas, o último elemento tem seu campo prox valendo NULL (se o enca-
deamento for duplo, o mesmo acontece com o campo ant do primeiro elemento). Nas listas 
fechadas, o campo prox do último elemento aponta para o primeiro elemento (se o encadea-
mento for duplo, o campo ant do primeiro elemento aponta para o último elemento). 
 6 
 Nas listas com encadeamento simples, cada elemento tem apenas um campo do tipo 
ponteiro, apontando para o elemento seguinte na lista. Nas listas com encadeamento duplo, 
cada elemento tem dois ponteiros: o prox, apontando para o elemento seguinte, e o ant, apon-
tando para o elemento anterior. 
 
 Outros padrões e modos de implementação de listas podem ser encontrados no tópico 
de Aplicações. 
 7 
3.4 Algoritmos para Listas 
 
 Neste tópico veremos os algoritmos correspondentes às operações mais básicas [1] 
que podem ser efetuadas com as listas, aplicadas aos quatro tipos mais comuns [2]de listas. 
As operações de construção serão desmembradas em duas: construção com inserção do ele-
mento no início da lista e construção com inserção no final da lista. 
 
1 [construção da lista, percurso na lista, procura de um elemento em uma lista ordenada, inserção 
de um elemento em uma lista ordenada, remoção de um elemento da lista, remoção de todos os ele-
mentos da lista] 
 
2 [ aberta com encadeamento simples, aberta com encadeamento duplo, fechada com encadea-
mento simples, fechada com encadeamento duplo] 
 
 É interessante notar que, em vários algoritmos, há a necessidade de se analisar separa-
damente a situação genérica (em geral, o elemento que interessa está no meio da lista) e as 
situações particulares (que costumam ser as seguintes: lista vazia, elemento no começo da 
lista, elemento no final da lista, lista com apenas um elemento). Sempre que possível, convém 
que os casos particulares sejam tratados no mesmo trecho de programa que o caso geral, tor-
nando o programa mais sintético. Dependendo do tipo de lista escolhida, certas operações se 
tornam mais simples, pois os casos particulares podem ser tratados juntamente com o caso 
geral. 
 
 Em todas as funções que utilizam listas de encadeamento simples, o tipo de cada ele-
mento será: 
 
struct elemento { 
 char dado; 
 struct elemento *prox; 
} ; 
 
 Em todas as funções que utilizam listas de encadeamento duplo, o tipo de cada ele-
mento será: 
 
struct elemento { 
 char dado; 
 struct elemento *prox, *ant; 
} ; 
 
***** acrescentar uma observação a respeito da passagem de parâmetros do tipo “endereço 
para ponteiro” (ver esquema 4, árvores) 
 
 
 
3.4.1 Listas Abertas com Encadeamento Simples 
 
a) Construção com inserção dos elementos no início da lista 
 
 Neste caso, cada dado lido do arquivo é inserido no começo da lista. Dessa forma, a 
ordem dos elementos na lista fica invertida em relação à ordem original do arquivo. A função 
recebe como parâmetro o endereço do ponteiro pinicio, que aponta para o início da lista. 
 
void construir1(struct elemento **pinicio) { 
 FILE *arq; 
 8 
 struct elemento *p1; 
 char c; 
 
 arq = fopen ("t1.txt", "r"); 
 *pinicio = NULL; 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = c; 
 p1->prox = *pinicio; 
 *pinicio = p1; 
 } 
 } 
 fclose (arq); 
 return; 
} 
 
 
b) Construção com inserção dos elementos no final da lista 
 
 Neste caso, cada dado lido do arquivo é inserido no final da lista. Dessa forma, a or-
dem dos elementos na lista fica idêntica à ordem original do arquivo. A função recebe como 
parâmetro o endereço do ponteiro pinicio, que aponta para o início da lista. 
 
void construir2(struct elemento **pinicio) { 
 FILE *arq; 
 struct elemento *p1, *p2; 
 char c; 
 
 arq = fopen ("t5.txt", "r"); 
 *pinicio = NULL; 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = c; 
 p1->prox = NULL; 
 if (*pinicio == NULL) 
 *pinicio = p1; 
 else 
 p2->prox = p1; 
 p2 = p1; 
 } 
 } 
 fclose (arq); 
 return; 
} 
 
 
c) Percurso por todos os elementos da lista 
 
 Esta operação consiste em percorrer todos os elementos da lista, realizando alguma 
ação em cada um. Neste exemplo a ação consiste em escrever o dado na tela. A função recebe 
como parâmetro o ponteiro pinicio, que aponta para o início da lista. 
 
void percorrer(struct elemento *pinicio) { 
 struct elemento *p1; 
 
 if (pinicio == NULL) 
 printf ("lista vazia \n"); 
 else { 
 p1 = pinicio; 
 while (p1 != NULL) { 
 printf("elemento: %c \n", p1->dado); 
 p1 = p1->prox; 
 } 
 } 
 return; 
} 
Tira Teima 
Tira Teima 
Tira Teima 
 9 
 
d) Procura de um dado na lista 
 
 Esta operação consiste na procura de um determinado dado na lista. A função recebe 
como parâmetro o ponteiro pinicio, que aponta para o início da lista, e o dado a ser procurado, 
denominado aqui de chave, e retorna um ponteiro apontando para o elemento que contem o 
dado. Se o dado procurado não estiver presente na lista, a função retorna o valor NULL. 
 
void *procurar(struct elemento *pinicio, char chave) { 
 struct elemento *p1; 
 
 p1 = pinicio; 
 while ((p1 != NULL) && (p1->dado != chave)) 
 p1 = p1->prox; 
 return p1; 
} 
 
e) Inserção de um dado em uma lista ordenada 
 
 Esta operação consiste em inserir um novo dado na lista, no lugar que lhe corresponda. 
No exemplo a lista está ordenada em ordem crescente. A função recebe como parâmetro o 
ponteiro pinicio, que aponta para o início da lista, e o dado a ser inserido, denominado aqui de 
dadonovo. 
 
void inserir(struct elemento **pinicio, char dadonovo){ 
 struct elemento *p1, *p2; 
 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = dadonovo; 
 if (*pinicio == NULL) 
 *pinicio = p1; 
 else 
 if ((*pinicio)->dado > dadonovo) { 
 p1->prox = *pinicio; 
 *pinicio = p1; 
 } 
 else { 
 p2 = *pinicio; 
 while ((p2->prox != NULL) && (p2->prox->dado < dadonovo)) 
 p2 = p2->prox; 
 p1->prox = p2->prox; 
 p2->prox = p1; 
 } 
 return;} 
 
f) Remoção de um dado de uma lista 
 
 Esta operação consiste em remover um determinado dado da lista. Se o dado não esti-
ver presente, a função não faz nada. Se o dado estiver presente várias vezes na lista, todos os 
elementos correspondentes serão removidos. A função recebe como parâmetro o endereço do 
ponteiro pinicio, que aponta para o início da lista, e o dado a ser removido, aqui denominado 
chave. 
 
void remover(struct elemento **pinicio, char chave){ 
 struct elemento *p1, *p2; 
 int achou; 
 
 if (*pinicio == NULL) 
 printf("lista vazia \n"); 
 else { 
 p1 = *pinicio; 
 achou = 0; 
Tira Teima 
Tira Teima 
Tira Teima 
 10 
 while (p1 != NULL) { 
 if (p1->dado == chave) { 
 if (*pinicio == p1){ 
 *pinicio = (*pinicio)->prox; 
 p2 = *pinicio; 
 } 
 else 
 p2->prox = p1->prox; 
 free (p1); 
 p1 = p2; 
 achou =1; 
 } 
 else { 
 p2 = p1; 
 p1 = p1->prox; 
 } 
 } 
 if (!achou) 
 printf ("elemento nao presente \n"); 
 } 
 return; 
} 
 
g) Remoção de toda a lista 
 
 Esta operação consiste em desfazer totalmente uma lista, removendo todos os elemen-
tos, um a um, começando pelo início da lista. A função recebe como parâmetro o ponteiro 
pinicio, que aponta para o início da lista. 
 
void destruir(struct elemento **pinicio){ 
 struct elemento *p1; 
 
 while (*pinicio != NULL) { 
 p1 = *pinicio; 
 *pinicio = (*pinicio)->prox; 
 free (p1); 
 } 
 return; 
} 
 
 
 
3.4.2 Listas Abertas com Encadeamento Duplo 
 
a) Construção com inserção dos elementos no início da lista 
 
 Neste caso, cada dado lido do arquivo é inserido no começo da lista. Dessa forma, a 
ordem dos elementos na lista fica invertida em relação à ordem original do arquivo. A função 
recebe como parâmetro o endereço do ponteiro pinicio, que aponta para o início da lista. 
 
void construir1(struct elemento **pinicio) { 
 FILE *arq; 
 struct elemento *p1; 
 char c; 
 
 arq = fopen ("t1.txt", "r"); 
 *pinicio = NULL; 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = c; 
 p1->prox = *pinicio; 
 if (*pinicio != NULL) 
 (*pinicio)->ant = p1; 
 p1->ant = NULL; 
 *pinicio = p1; 
 } 
 } 
 fclose (arq); 
Tira Teima 
Tira Teima 
 11 
 return; 
} 
 
b) Construção com inserção dos elementos no final da lista 
 
 Neste caso, cada dado lido do arquivo é inserido no final da lista. Dessa forma, a or-
dem dos elementos na lista fica idêntica à ordem original do arquivo. A função recebe como 
parâmetro o endereço do ponteiro pinicio, que aponta para o início da lista. 
 
void construir2(struct elemento **pinicio) { 
 FILE *arq; 
 struct elemento *p1, *p2; 
 char c; 
 
 arq = fopen ("t5.txt", "r"); 
 *pinicio = NULL; 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = c; 
 p1->prox = NULL; 
 if (*pinicio == NULL) { 
 *pinicio = p1; 
 p1->ant = NULL; 
 } 
 else { 
 p2->prox = p1; 
 p1->ant = p2; 
 } 
 p2 = p1; 
 } 
 } 
 fclose (arq); 
 return; 
} 
 
c) Percurso por todos os elementos da lista 
 
 Esta operação consiste em percorrer todos os elementos da lista, realizando alguma 
ação em cada um. Neste exemplo a ação consiste em escrever o dado na tela. A função recebe 
como parâmetro o ponteiro pinicio, que aponta para o início da lista. 
 
void percorrer(struct elemento *pinicio) { 
 struct elemento *p1; 
 
 if (pinicio == NULL) 
 printf ("lista vazia \n"); 
 else { 
 p1 = pinicio; 
 while (p1 != NULL) { 
 printf("elemento: %c \n", p1->dado); 
 p1 = p1->prox; 
 } 
 p1 = pinicio; 
 while (p1->prox != NULL) 
 p1 = p1->prox; 
 while (p1 != NULL) { 
 printf("elemento (para tras): %c \n", p1->dado); 
 p1 = p1->ant; 
 } 
 } 
 return; 
} 
 
d) Procura de um dado na lista 
 
Tira Teima 
Tira Teima 
 12 
 Esta operação consiste na procura de um determinado dado na lista. A função recebe 
como parâmetro o ponteiro pinicio, que aponta para o início da lista, e o dado a ser procurado, 
denominado aqui de chave, e retorna um ponteiro apontando para o elemento que contem o 
dado. Se o dado procurado não estiver presente na lista, a função retorna o valor NULL. 
 
void *procurar(struct elemento *pinicio, char chave) { 
 struct elemento *p1; 
 
 p1 = pinicio; 
 while ((p1 != NULL) && (p1->dado != chave)) 
 p1 = p1->prox; 
 return p1; 
} 
 
e) Inserção de um dado em uma lista ordenada 
 
 Esta operação consiste em inserir um novo dado na lista, no lugar que lhe corresponda. 
No exemplo a lista está ordenada em ordem crescente. A função recebe como parâmetro o 
ponteiro pinicio, que aponta para o início da lista, e o dado a ser inserido, denominado aqui de 
dadonovo. 
 
void inserir(struct elemento **pinicio, char dadonovo){ 
 struct elemento *p1, *p2; 
 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = dadonovo; 
 if (*pinicio == NULL) { 
 *pinicio = p1; 
 p1->prox = NULL; 
 p1->ant = NULL; 
 } 
 else 
 if ((*pinicio)->dado > dadonovo) { 
 p1->prox = *pinicio; 
 p1->ant = NULL; 
 (*pinicio)->ant = p1; 
 *pinicio = p1; 
 } 
 else { 
 p2 = *pinicio; 
 while ((p2->prox != NULL) && (p2->prox->dado < dadonovo)) 
 p2 = p2->prox; 
 p1->prox = p2->prox; 
 p1->ant = p2; 
 if (p2->prox != NULL) 
 p2->prox->ant = p1; 
 p2->prox = p1; 
 } 
 return; 
} 
 
f) Remoção de um dado de uma lista 
 
 Esta operação consiste em remover um determinado dado da lista. Se o dado não esti-
ver presente, a função não faz nada. Se o dado estiver presente várias vezes na lista, todos os 
elementos correspondentes serão removidos. A função recebe como parâmetro o endereço do 
ponteiro pinicio, que aponta para o início da lista, e o dado a ser removido, aqui denominado 
chave. 
 
void remover(struct elemento **pinicio, char chave){ 
 struct elemento *p1, *p2; 
 int achou; 
 
 if (*pinicio == NULL) 
 printf("lista vazia \n"); 
 else { 
Tira Teima 
Tira Teima 
Tira Teima 
 13 
 p1 = *pinicio; 
 achou = 0; 
 while (p1 != NULL) { 
 if (p1->dado == chave) { 
 if (*pinicio == p1) 
 *pinicio = (*pinicio)->prox; 
 p2 = p1->prox; 
 if (p1->prox != NULL) 
 p1->prox->ant = p1->ant; 
 if (p1->ant != NULL) 
 p1->ant->prox = p1->prox; 
 free (p1); 
 p1 = p2; 
 achou =1; 
 } 
 else 
 p1 = p1->prox; 
 } 
 if (!achou) 
 printf ("elemento nao presente \n"); 
 } 
 return; 
} 
 
g) Remoção de toda a lista 
 
 Esta operação consiste em desfazer totalmente uma lista, removendo todos os elemen-
tos, um a um, começando pelo início da lista. A função recebe como parâmetro o ponteiro 
pinicio, que aponta para o início da lista. 
 
void removertudo(struct elemento **pinicio){ 
 struct elemento *p1; 
 
 while (*pinicio != NULL) { 
 p1 = *pinicio; 
 *pinicio = (*pinicio)->prox; 
 free (p1); 
 } 
 return; 
} 
 
 
3.4.3 Listas Fechadas com Encadeamento Simples 
 
a) Construção com inserção dos elementos no início da lista 
 
 Neste caso, cada dado lido do arquivo é inserido no começo da lista. Dessa forma, a 
ordem dos elementos na lista fica invertida em relação à ordem original do arquivo. A função 
recebe como parâmetro o endereço do ponteiro pinicio, que aponta para o início da lista.void construir1(struct elemento **pinicio) { 
 FILE *arq; 
 struct elemento *p1, *p2; 
 char c; 
 
 arq = fopen ("t1.txt", "r"); 
 *pinicio = NULL; 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = c; 
 if (*pinicio == NULL) { 
 p1->prox = p1; 
 *pinicio = p1; 
 } 
 else { 
 p1->prox = *pinicio; 
 p2 = *pinicio; 
 while (p2->prox != *pinicio) 
Tira Teima 
Tira Teima 
 14 
 p2 = p2->prox; 
 p2->prox = p1; 
 *pinicio = p1; 
 } 
 } 
 } 
 fclose (arq); 
 return; 
} 
 
b) Construção com inserção dos elementos no final da lista 
 
 Neste caso, cada dado lido do arquivo é inserido no final da lista. Dessa forma, a or-
dem dos elementos na lista fica idêntica à ordem original do arquivo. A função recebe como 
parâmetro o endereço do ponteiro pinicio, que aponta para o início da lista. 
 
void construir2(struct elemento **pinicio) { 
 FILE *arq; 
 struct elemento *p1, *p2; 
 char c; 
 
 arq = fopen ("t5.txt", "r"); 
 *pinicio = NULL; 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = c; 
 if (*pinicio == NULL) 
 *pinicio = p1; 
 else 
 p2->prox = p1; 
 p2 = p1; 
 p1->prox = *pinicio; 
 } 
 } 
 fclose (arq); 
 return; 
} 
 
c) Percurso por todos os elementos da lista 
 
 Esta operação consiste em percorrer todos os elementos da lista, realizando alguma 
ação em cada um. Neste exemplo a ação consiste em escrever o dado na tela. A função recebe 
como parâmetro o ponteiro pinicio, que aponta para o início da lista. 
 
void percorrer(struct elemento *pinicio) { 
 struct elemento *p1; 
 
 if (pinicio == NULL) 
 printf ("lista vazia \n"); 
 else { 
 p1 = pinicio; 
 do { 
 printf("elemento: %c \n", p1->dado); 
 p1 = p1->prox; 
 } 
 while (p1 != pinicio); 
 } 
 return; 
} 
 
d) Procura de um dado na lista 
 
 Esta operação consiste na procura de um determinado dado na lista. A função recebe 
como parâmetro o ponteiro pinicio, que aponta para o início da lista, e o dado a ser procurado, 
Tira Teima 
Tira Teima 
 15 
denominado aqui de chave, e retorna um ponteiro apontando para o elemento que contem o 
dado. Se o dado procurado não estiver presente na lista, a função retorna o valor NULL. 
 
void *procurar(struct elemento *pinicio, char chave) { 
 struct elemento *p1; 
 
 if (pinicio == NULL) 
 p1 = NULL; 
 else { 
 p1 = pinicio; 
 do 
 p1 = p1->prox; 
 while ((p1 != pinicio) && (p1->dado != chave)); 
 if ((p1 == pinicio) && (p1->dado != chave)) 
 p1 = NULL; 
 } 
 return p1; 
} 
 
e) Inserção de um dado em uma lista ordenada 
 
 Esta operação consiste em inserir um novo dado na lista, no lugar que lhe corresponda. 
No exemplo a lista está ordenada em ordem crescente. A função recebe como parâmetro o 
ponteiro pinicio, que aponta para o início da lista, e o dado a ser inserido, denominado aqui de 
dadonovo. 
 
void inserir(struct elemento **pinicio, char dadonovo){ 
 struct elemento *p1, *p2; 
 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = dadonovo; 
 if (*pinicio == NULL) { 
 p1->prox = p1; 
 *pinicio = p1; 
 } 
 else 
 if ((*pinicio)->dado > dadonovo) { 
 p1->prox = *pinicio; 
 p2 = *pinicio; 
 while (p2->prox != *pinicio) 
 p2 = p2->prox; 
 p2->prox = p1; 
 *pinicio = p1; 
 } 
 else { 
 p2 = *pinicio; 
 while ((p2->prox != *pinicio) && (p2->prox->dado < dadonovo)) 
 p2 = p2->prox; 
 p1->prox = p2->prox; 
 p2->prox = p1; 
 } 
 return; 
} 
 
f) Remoção de um dado de uma lista 
 
 Esta operação consiste em remover um determinado dado da lista. Se o dado não esti-
ver presente, a função não faz nada. Se o dado estiver presente várias vezes na lista, todos os 
elementos correspondentes serão removidos. A função recebe como parâmetro o endereço do 
ponteiro pinicio, que aponta para o início da lista, e o dado a ser removido, aqui denominado 
chave. 
 
void remover(struct elemento **pinicio, char chave){ 
 struct elemento *p1, *p2; 
 int achou; 
 
 if (*pinicio == NULL) 
Tira Teima 
Tira Teima 
Tira Teima 
 16 
 printf("lista vazia \n"); 
 else { 
 achou = 0; 
 while ((*pinicio != NULL) && ((*pinicio)->dado == chave)) { 
 if ((*pinicio)->prox == *pinicio) { 
 free (*pinicio); 
 *pinicio = NULL; 
 achou = 1; 
 } 
 else { 
 p1 = *pinicio; 
 *pinicio = (*pinicio)->prox; 
 p2 = *pinicio; 
 while (p2->prox != p1) 
 p2 = p2->prox; 
 p2->prox = p1->prox; 
 free (p1); 
 p1 = p2; 
 achou = 1; 
 } 
 } 
 if ((*pinicio != NULL) && ((*pinicio)->prox != NULL)) { 
 p1 = (*pinicio)->prox; 
 while (p1 != *pinicio) 
 if (p1->dado == chave) { 
 p2 = *pinicio; 
 while (p2->prox != p1) 
 p2 = p2->prox; 
 p2->prox = p1->prox; 
 free (p1); 
 p1 = p2->prox; 
 achou = 1; 
 } 
 else 
 p1 = p1->prox; 
 } 
 } 
 return; 
} 
 
g) Remoção de toda a lista 
 
 Esta operação consiste em desfazer totalmente uma lista, removendo todos os elemen-
tos, um a um, começando pelo início da lista. A função recebe como parâmetro o ponteiro 
pinicio, que aponta para o início da lista. 
 
void removertudo(struct elemento **pinicio){ 
 struct elemento *p1; 
 
 if (*pinicio != NULL) { 
 p1 = (*pinicio)->prox; 
 while (p1 != *pinicio) { 
 (*pinicio)->prox = p1->prox; 
 free (p1); 
 p1 = (*pinicio)->prox; 
 } 
 free (*pinicio); 
 *pinicio = NULL; 
 } 
 return; 
} 
 
 
3.4.4 Listas Fechadas com Encadeamento Duplo 
 
a) Construção com inserção dos elementos no início da lista 
 
Tira Teima 
 17 
 Neste caso, cada dado lido do arquivo é inserido no começo da lista. Dessa forma, a 
ordem dos elementos na lista fica invertida em relação à ordem original do arquivo. A função 
recebe como parâmetro o endereço do ponteiro pinicio, que aponta para o início da lista. 
 
void construir1(struct elemento **pinicio) { 
 FILE *arq; 
 struct elemento *p1; 
 char c; 
 
 arq = fopen ("t5.txt", "r"); 
 *pinicio = NULL; 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = c; 
 if (*pinicio == NULL) { 
 p1->prox = p1; 
 p1->ant = p1; 
 *pinicio = p1; 
 } 
 else { 
 p1->prox = *pinicio; 
 p1->ant = (*pinicio)->ant; 
 (*pinicio)->ant->prox = p1; 
 (*pinicio)->ant = p1; 
 *pinicio = p1; 
 } 
 } 
 } 
 fclose (arq); 
 return; 
} 
 
b) Construção com inserção dos elementos no final da lista 
 
 Neste caso, cada dado lido do arquivo é inserido no final da lista. Dessa forma, a or-
dem dos elementos na lista fica idêntica à ordem original do arquivo. A função recebe como 
parâmetro o endereço do ponteiro pinicio, que aponta para o início da lista. 
 
void construir2(struct elemento **pinicio) { 
 FILE *arq; 
 struct elemento *p1, *p2; 
 char c; 
 
 arq = fopen ("t5.txt", "r"); 
 *pinicio = NULL; 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = c; 
 if (*pinicio == NULL) { 
 p1->prox = p1; 
 p1->ant = p1; 
 *pinicio = p1; 
 } 
 else { 
 p1->prox = *pinicio; 
 p1->ant = p2;p2->prox = p1; 
 (*pinicio)->ant = p1; 
 } 
 p2 = p1; 
 } 
 } 
 fclose (arq); 
 return; 
} 
 
c) Percurso por todos os elementos da lista 
 
Tira Teima 
Tira Teima 
 18 
 Esta operação consiste em percorrer todos os elementos da lista, realizando alguma 
ação em cada um. Neste exemplo a ação consiste em escrever o dado na tela. A função recebe 
como parâmetro o ponteiro pinicio, que aponta para o início da lista. 
 
void percorrer(struct elemento *pinicio) { 
void percorrer(struct elemento *pinicio) { 
 struct elemento *p1; 
 
 if (pinicio == NULL) 
 printf ("lista vazia \n"); 
 else { 
 p1 = pinicio; 
 do { 
 printf("elemento: %c \n", p1->dado); 
 p1 = p1->prox; 
 } 
 while (p1 != pinicio); 
 do { 
 p1 = p1->ant; 
 printf("elemento (para tras): %c \n", p1->dado); 
 } 
 while (p1 != pinicio); 
 } 
 return; 
} 
 
d) Procura de um dado na lista 
 
 Esta operação consiste na procura de um determinado dado na lista. A função recebe 
como parâmetro o ponteiro pinicio, que aponta para o início da lista, e o dado a ser procurado, 
denominado aqui de chave, e retorna um ponteiro apontando para o elemento que contem o 
dado. Se o dado procurado não estiver presente na lista, a função retorna o valor NULL. 
 
void *procurar(struct elemento *pinicio, char chave) { 
 struct elemento *p1; 
 
 if (pinicio == NULL) 
 p1 = NULL; 
 else { 
 p1 = pinicio; 
 do 
 p1 = p1->prox; 
 while ((p1 != pinicio) && (p1->dado != chave)); 
 if ((p1 == pinicio) && (p1->dado != chave)) 
 p1 = NULL; 
 } 
 return p1; 
} 
 
e) Inserção de um dado em uma lista ordenada 
 
 Esta operação consiste em inserir um novo dado na lista, no lugar que lhe corresponda. 
No exemplo a lista está ordenada em ordem crescente. A função recebe como parâmetro o 
ponteiro pinicio, que aponta para o início da lista, e o dado a ser inserido, denominado aqui de 
dadonovo. 
 
void inserir(struct elemento **pinicio, char dadonovo){ 
 struct elemento *p1, *p2; 
 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = dadonovo; 
 if (*pinicio == NULL) { 
 p1->prox = p1; 
 p1->ant = p1; 
 *pinicio = p1; 
 } 
 else 
Tira Teima 
Tira Teima 
Tira Teima 
 19 
 if ((*pinicio)->dado > dadonovo) { 
 p1->prox = *pinicio; 
 p1->ant = (*pinicio)->ant; 
 (*pinicio)->ant->prox = p1; 
 (*pinicio)->ant = p1; 
 *pinicio = p1; 
 } 
 else { 
 p2 = *pinicio; 
 while ((p2->prox != *pinicio) && (p2->prox->dado < dadonovo)) 
 p2 = p2->prox; 
 p1->prox = p2->prox; 
 p1->ant = p2; 
 p2->prox->ant = p1; 
 p2->prox = p1; 
 } 
 return; 
} 
 
f) Remoção de um dado de uma lista 
 
 Esta operação consiste em remover um determinado dado da lista. Se o dado não esti-
ver presente, a função não faz nada. Se o dado estiver presente várias vezes na lista, todos os 
elementos correspondentes serão removidos. A função recebe como parâmetro o endereço do 
ponteiro pinicio, que aponta para o início da lista, e o dado a ser removido, aqui denominado 
chave. 
 
void remover(struct elemento **pinicio, char chave){ 
 struct elemento *p1, *p2; 
 int achou; 
 
 if (*pinicio == NULL) 
 printf("lista vazia \n"); 
 else { 
 achou = 0; 
 while ((*pinicio != NULL) && ((*pinicio)->dado == chave)) { 
 if ((*pinicio)->prox == *pinicio) { 
 free (*pinicio); 
 *pinicio = NULL; 
 achou = 1; 
 } 
 else { 
 p1 = *pinicio; 
 *pinicio = (*pinicio)->prox; 
 p2 = *pinicio; 
 while (p2->prox != p1) 
 p2 = p2->prox; 
 p2->prox = p1->prox; 
 p1->prox->ant = p2; 
 free (p1); 
 p1 = p2; 
 achou = 1; 
 } 
 } 
 if ((*pinicio != NULL) && ((*pinicio)->prox != NULL)) { 
 p1 = (*pinicio)->prox; 
 while (p1 != *pinicio) 
 if (p1->dado == chave) { 
 p2 = *pinicio; 
 while (p2->prox != p1) 
 p2 = p2->prox; 
 p2->prox = p1->prox; 
 p1->prox->ant = p2; 
 free (p1); 
 p1 = p2->prox; 
 achou = 1; 
 } 
 else 
 p1 = p1->prox; 
 } 
 } 
 return; 
Tira Teima 
 20 
} 
 
g) Remoção de toda a lista 
 
 Esta operação consiste em desfazer totalmente uma lista, removendo todos os elemen-
tos, um a um, começando pelo início da lista. A função recebe como parâmetro o ponteiro 
pinicio, que aponta para o início da lista. 
 
void removertudo(struct elemento **pinicio){ 
 struct elemento *p1; 
 
 if (*pinicio != NULL) { 
 p1 = (*pinicio)->prox; 
 while (p1 != *pinicio) { 
 (*pinicio)->prox = p1->prox; 
 free (p1); 
 p1 = (*pinicio)->prox; 
 } 
 free (*pinicio); 
 *pinicio = NULL; 
 } 
 return; 
} 
Tira Teima 
 21 
3.5 Aplicações 
 
 Neste tópico serão apresentadas algumas aplicações de listas. Algumas dessas aplica-
ções são apenas algoritmos aplicados sobre as listas já estudadas nos tópicos anteriores, como 
é o caso da ordenação. Outras aplicações são constituídas por novas formas de construir lis-
tas, como é o caso das listas com descritor e das listas ligadas a listas. 
 
3.5.1 Ordenação dos dados em uma lista sem alterar a estrutura da lista 
 
 São apresentados dois exemplos. No primeiro, trocam-se os conteúdos dos elementos 
na lista , sem alterar a ordem dos elementos da lista. No segundo trocam-se as posições dos 
elementos na lista, através da realocação dos ponteiros. Em ambos utiliza-se o algoritmo de 
Seleção Direta. 
 
[O algoritmo de Seleção Direta funciona do seguinte modo: percorre-se o conjunto de elementos, do 
primeiro ao último, selecionando-se o menor entre eles, e colocando-o na primeira posição. Em se-
guida percorre-se o conjunto formado pelos elementos entre a segunda posição e a última, selecio-
nando-se o menor deles, e colocando-o na segunda posição. Assim, sucessivamente, selecionam-se 
os menores elementos dos conjuntos restantes, até que esse conjunto fique vazio, e todos os ele-
mentos estejam ordenados.] 
 
Exemplo 1 
 
Neste caso, trocam-se os conteúdos dos elementos na lista, sem alterar a ordem dos elementos 
na lista. Se os dados de cada elemento da lista não ocupam muita memória, este algoritmo é 
mais adequado. No exemplo, a lista é aberta com encadeamento simples. No caso o ponteiro 
p1 ocupa sempre a posição em que será colocado o menor elemento do conjunto ainda desor-
denado. O ponteiro p2 percorre esse conjunto, à procura do menor elemento, e p3 aponta 
sempre para o menor elemento encontrado, até que a varredura termine. Em seguida são tro-
cados os dados dos elementos apontados por p1 e p3. 
 
void ordenarSelecaoDireta(struct elemento *pinicio) { 
 struct elemento *p1, *p2, *p3; 
 char aux; 
 
 if (pinicio != NULL) { 
 p1 = pinicio; 
 while (p1->prox != NULL) { 
 p3 = p1; 
 p2 = p1->prox; 
 while (p2 != NULL) { 
 if (p3->dado > p2->dado) 
 p3 = p2; 
 p2 = p2->prox; 
 } 
 if (p1 != p3) { 
 aux = p3->dado; 
 p3->dado = p1->dado; 
 p1->dado = aux; 
 } 
 p1 = p1->prox; 
 } 
 } 
 return; 
} 
 
Exemplo 2 
 
 Neste caso trocam-se as posições dos elementos na lista, através da realocação dos 
ponteiros. Este algoritmo é mais adequado na situação em que os dados da lista ocupam muito 
Tira Teima 
 22 
espaço, tornando computacionalmente a realocação dos ponteiros mais barata que a troca dos 
dados. Neste exemplo a lista é fechada com encadeamento duplo. 
 
void *ordenarAlteraPonteiros(struct elemento *pinicio) { 
 struct elemento*p1, *p2, *p3, *paux; 
 
 if (pinicio != NULL) { 
 p1 = pinicio; 
 while (p1->prox != NULL) { 
 p2 = p1->prox; 
 while (p2 != NULL) { 
 if (p1->dado > p2->dado) { 
 if (p1->prox == p2) { 
 p1->prox = p2->prox; 
 p2->ant = p1->ant; 
 if (!(p2->prox == NULL)) 
 p2->prox->ant = p1; 
 if (!(p1->ant == NULL)) 
 p1->ant->prox = p2; 
 p2->prox = p1; 
 p1->ant = p2; 
 if (pinicio == p1) 
 pinicio = p2; 
 paux = p1; 
 p1 = p2; 
 p2 = paux; 
 } 
 else { 
 p2->ant->prox = p1; 
 p1->prox->ant = p2; 
 if (!(p2->prox == NULL)) 
 p2->prox->ant = p1; 
 if (!(p1->ant == NULL)) 
 p1->ant->prox = p2; 
 paux = p1->ant; 
 p1->ant = p2->ant; 
 p2->ant = paux; 
 paux = p1->prox; 
 p1->prox = p2->prox; 
 p2->prox = paux; 
 if (pinicio == p1) 
 pinicio = p2; 
 paux = p1; 
 p1 = p2; 
 p2 = paux; 
 } 
 } 
 p2 = p2->prox; 
 } 
 p1 = p1->prox; 
 } 
 } 
 return pinicio; 
} 
 
3.5.2 Listas com descritor 
 
 As listas com descritor consistem em listas com um elemento especial, que não guarda 
dados como os outros elementos, mas apenas facilita o acesso à lista. Alguns algoritmos ficam 
simplificados através desse recurso, que pode ser aplicado a qualquer dos tipos de listas vistos 
anteriormente. 
 
 Apresentamos aqui dois exemplos. No primeiro, o nó descritor é do mesmo tipo que os 
outros nós da lista, mas não contém dados (esse nó também é conhecido como "nó bobo"). A 
simplificação que se consegue em alguns algoritmos decorre da facilidade no tratamento de 
elementos da lista colocados em posições especiais, como no começo ou no final da lista. 
 
Tira Teima 
 23 
 No segundo exemplo, o nó descritor é completamente diferente dos outros nós da lista, 
podendo eventualmente conter outras informações sobre a lista. No caso, o elemento descritor 
foi construído com dois ponteiros de acesso à lista: um apontando para o começo e outro para 
o final da lista. Desse modo, ficam simplificados os algoritmos que atuam no final da lista. 
 
Exemplo 1 
 
 O nó descritor é do mesmo tipo que os outros nós da lista, que é aberta e com encade-
amento simples. A função do exemplo faz a inserção de um novo elemento no início da lista. 
Tenha em conta que neste caso, uma lista vazia é formada pelo “nó bobo”; portanto pinicio 
não é NULL. 
 
void *inserir(struct elemento *pinicio, char dadonovo){ 
 struct elemento *p1, *p2; 
 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = dadonovo; 
 p1->prox = NULL; 
 if (pinicio->prox == NULL) 
 pinicio->prox = p1; 
 else { 
 p2 = pinicio; 
 while ((p2->prox != NULL) && (p2->prox->dado < dadonovo)) 
 p2 = p2->prox; 
 p1->prox = p2->prox; 
 p2->prox = p1; 
 } 
 return pinicio; 
} 
 
Exemplo 2 
 
 O nó descritor neste caso é um elemento diferente dos outros elementos da lista. Ele 
contém apenas dois ponteiros, um apontando para o primeiro elemento da lista e o outro apon-
tando para o último. A lista é aberta e com encadeamento simples. A função faz a construção 
da lista inserindo os elementos no final. 
 
[struct descritor { 
 struct elemento *acessoinicio, *acessofim; 
} ; 
struct descritor *pdescr; ] 
 
 
void *construir2() { 
 FILE *arq; 
 struct elemento *p1, *p2; 
 struct descritor *pdescritor; 
 char c; 
 
 pdescritor = malloc (sizeof (struct descritor)); 
 pdescritor->acessoinicio = NULL; 
 pdescritor->acessofim = NULL; 
 arq = fopen ("t1.txt", "r"); 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 p1 = malloc (sizeof (struct elemento)); 
 p1->dado = c; 
 if (pdescritor->acessoinicio == NULL) 
 pdescritor->acessoinicio = p1; 
 else 
 p2->prox = p1; 
 p2 = p1; 
 } 
 } 
Tira Teima 
Tira Teima 
 24 
 if (pdescritor->acessoinicio != NULL) { 
 p1->prox = NULL; 
 pdescritor->acessofim = p1; 
 } 
 fclose (arq); 
 return pdescritor; 
} 
 
 
3.5.3 Listas ligadas a listas 
 
 Há situações em que, em cada elemento de uma lista, um dos campos é um ponteiro 
que dá acesso a outra lista. A estrutura assim formada já não é uma lista, mas um conjunto de 
listas ligadas a outra lista. 
 
 Neste exemplo, a primeira lista é formada por elementos que identificam centrais tele-
fônicas, através de letras (A, B, C ...). A cada central telefônica está ligada uma lista formada 
por elementos que identificam números de telefone (110, 111, ...). O algoritmo usado como 
exemplo faz a montagem de toda a estrutura a partir de um arquivo text. 
 
 O arquivo contém, em cada linha, a letra identificadora da central, seguida por um 
número inteiro que indica quantos telefones existem nessa central, e em seguida os números 
dos telefones correspondentes. Note que a quantidade de telefones em cada central é variável 
(podendo ser também nula). O acesso a toda a estrutura é feito através de um único ponteiro 
(pacesso), que aponta para o início da lista de centrais. O acesso às listas de telefones é feito, 
para cada central, através do ponteiro que aponta para a lista de telefones correspondente a 
essa central. 
--------------------------------------- 
 
[ conteúdo das hotwords no programa:] 
 
struct elem_fone { 
 int fone; 
 struct elem_fone *proxf; 
} ; 
 
struct elem_central { 
 char central; 
 struct elem_central *proxc; 
 struct elem_fone *pfone; 
} ; 
 
struct elem_central *pac; 
 
----------------------------------------------- 
 
void *construirMalha(struct elem_central *pacesso) { 
 FILE *arq; 
 struct elem_central *pc1, *pc2; 
 struct elem_fone *pf1, *pf2; 
 char c; 
 int i,n,m; 
 
 arq = fopen ("t3.txt", "r"); 
 pacesso = NULL; 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 pc1 = malloc (sizeof (struct elem_central)); 
 pc1->central = c; 
Tira Teima 
 25 
 pc1->pfone = NULL; 
 pc1->proxc = NULL; 
 if (pacesso == NULL) 
 pacesso = pc1; 
 else 
 pc2->proxc = pc1; 
 pc2 = pc1; 
 fscanf (arq, "%d ", &n); 
 for (i=1; i !=n+1; i++) { 
 fscanf (arq, "%d ", &m); 
 pf1 = malloc (sizeof (struct elem_fone)); 
 pf1->fone = m; 
 pf1->proxf = NULL; 
 if (pc1->pfone == NULL) 
 pc1->pfone = pf1; 
 else pf2->proxf = pf1; 
 pf2 = pf1; 
 } 
 } 
 } 
 fclose (arq); 
 return pacesso; 
} 
 26 
[página de conclusão] 
 
 Neste capítulo estudamos as listas, que são as estruturas de dados mais simples deste 
curso. No entanto, se forem bem compreendidas, seu conhecimento poderá resolver inúmeros 
problemas computacionais que exigem gerenciamento dinâmico de memória, além de prepa-
rar o aluno para aprender com mais facilidade as outras estruturas que serão apresentadas a 
seguir. 
 
 
 
 1 
ED – esquema para tutorial 03 
 
Capítulo 3 – Pilhas e Filas 
 
 
[página de abertura] 
 
 Ao concluir este capítulo, você deverá ser capaz de: 
 
- compreender o que são as pilhas e filas 
- conhecer as operações básicas que se podem efetuar com as pilhas e com as filas 
- tomar contato com algumas aplicações de pilhas e de filas 
 2 
4.1 Introdução 
 
 Para certas aplicações, tornam-se úteis estruturas de dados constituídas por conjuntos 
de elementos organizados, não pelos valores dos dados, mas em função de uma determinado 
critério que regulamenta a entrada e a saída dos dados na estrutura. 
 
 Os critérios mais usados para regular a entrada e a saídados dados são: 
 
- lifo – last in, first out – dentre os elementos presentes na estrutura, o primeiro a sair dela 
será o último que nela entrou (como acontece com uma pilha de pratos: sempre se retira o de 
cima, que foi o último a entrar na pilha, caso contrário pode-se provocar um acidente). 
 
- fifo – first in, first out – dentre os elementos presentes na estrutura, o primeiro a sair dela 
será o primeiro que nela entrou (como acontece com uma fila de pessoas em um guichê: será 
atendida em primeiro lugar aquela que está há mais tempo na fila) {repetir aqui a figura da 
fila de pessoas, do módulo de introdução} 
 
 O critério LIFO dá origem à estrutura de dados denominada Pilha, e o critério FIFO dá 
origem à estrutura Fila. 
 
 As operações básicas que se podem realizar sobre uma pilha são: 
 
- inicializar a pilha 
- verificar se a pilha está vazia 
- retornar o elemento que está no topo da pilha 
- inserir um elemento na pilha 
- retirar um elemento da pilha 
 
 As operações básicas que se podem realizar sobre uma fila são: 
 
- inicializar a fila 
- verificar se a fila está vazia 
- retornar o elemento que está na primeira posição da fila 
- inserir um elemento na fila 
- retirar um elemento da fila 
 3 
4.2 Implementação 
 
 Como já foi dito, as estruturas de dados são abstratas, e portanto podem ser imple-
mentadas de diversos modos. 
 
[As estruturas abstratas devem ser imaginadas como uma forma de organizar e relacionar dados na 
memória do sistema, de modo a permitir certas operações sobre esses dados, independentemente do 
modo como essas estruturas são implementadas. ] 
 
 Em nosso caso, faremos a implementação das pilhas e das filas através de listas aber-
tas com encadeamento simples. O tipo dos elementos será, portanto, o mesmo para os dois 
casos, ficando a diferença apenas por conta das operações que se realizam em cada caso. É 
importante observar que, uma vez implementada a lista que representa uma pilha ou uma fila, 
o usuário da estrutura (pilha ou fila) apenas tem acesso às operações pré-definidas, não po-
dendo executar outras operações que seriam possíveis em listas. Ou seja, o usuário da pilha ou 
da fila não precisa saber como a estrutura foi implementada, apenas precisa saber utilizar as 
funções que permitem as operações básicas. 
 
 Para exemplificar a implementação das operações básicas utilizaremos as estruturas 
abaixo, nas quais o dado que se armazena é um caractere: 
 
struct tipopilha { 
 char dado; 
 struct tipopilha *prox; 
} ; 
 
struct tipofila { 
 char dado; 
 struct tipofila *prox; 
} ; 
 
4.2.1 Operações Básicas em Pilhas 
 
a) Inicializar a Pilha 
 
 Esta função consiste apenas em inicializar a pilha, ou seja, definir uma pilha vazia, que 
fica apta a ser utilizada. Recebe como parâmetro o endereço para o ponteiro pilha, que é um 
ponteiro que dá acesso à pilha. 
 
void InicializaPilha (struct tipopilha **pilha) { 
 *pilha = NULL; 
 return ; 
} 
 
 
 
 
b) Verificar se a Pilha está vazia 
 
 Esta função recebe como parâmetro o ponteiro pilha, que dá acesso à pilha, e retorna 1 
se a pilha estiver vazia, e 0 em caso contrário. 
 
int PilhaVazia (struct tipopilha *pilha) { 
 if (pilha == NULL) 
Tira Teima 
 4 
 return 1; 
 else 
 return 0; 
} 
 
 
c) Retornar o elemento que está no topo da pilha 
 
 Esta função recebe como parâmetro o ponteiro pilha, que dá acesso à pilha, e retorna o 
elemento que estiver no topo, sem retirá-lo da pilha. Esta operação só pode ser usada quando 
se tem certeza de que a pilha não é vazia, o que se pode testar com a função PilhaVazia. 
 
 
char TopoPilha(struct tipopilha *pilha) { 
 return pilha->dado; 
} 
 
 
 
d) Inserir um elemento na Pilha 
 
 Esta função recebe como parâmetros o valor dadonovo, a ser inserido, e o endereço 
do ponteiro pilha, que dá acesso à pilha. O resultado da operação é a inserção do dadonovo no 
topo da pilha. 
 
void InserePilha(struct tipopilha **pilha, char dadonovo) { 
 struct tipopilha *p1; 
 p1 = malloc (sizeof (struct tipopilha)); 
 p1->dado = dadonovo; 
 p1->prox = *pilha; 
 *pilha = p1; 
 return; 
} 
 
 
e) Retirar um elemento da Pilha 
 
 Esta função recebe como parâmetro o endereço do ponteiro pilha, que dá acesso à pi-
lha, e retorna o elemento que está no topo da pilha, retirando-o dela. Esta operação só pode 
ser usada quando se tem certeza de que a pilha não é vazia, o que se pode testar com a função 
PilhaVazia. 
 
char RetiraPilha(struct tipopilha **pilha) { 
 struct tipopilha *p1; 
 char car; 
 p1 = *pilha; 
 *pilha = p1->prox; 
 car = p1->dado; 
 free (p1); 
 return car; 
} 
 
 
 
4.2.2 Operações Básicas em Filas 
 
a) Inicializar a Fila 
 
Tira Teima 
Tira Teima 
Tira Teima 
Tira Teima 
 5 
 Esta função consiste apenas em inicializar a fila, ou seja, definir uma fila vazia, que 
fica apta a ser utilizada. Recebe como parâmetro o endereço para o ponteiro fila, que é um 
ponteiro que dá acesso à fila. 
 
void InicializaFila (struct tipofila **fila) { 
 *fila = NULL; 
 return; 
} 
 
 
 
b) Verificar se a Fila está vazia 
 
 Esta função recebe como parâmetro o ponteiro fila, que dá acesso à fila, e retorna 1 se 
a fila estiver vazia, e 0 em caso contrário. 
 
int FilaVazia (struct tipofila *fila) { 
 if (fila == NULL) 
 return 1; 
 else 
 return 0; 
} 
 
 
c) Retornar o elemento que está na primeira posição da fila 
 
 Esta função recebe como parâmetro o ponteiro fila, que dá acesso à fila, e retorna o 
elemento que estiver na primeira posição, sem retirá-lo da fila. Esta operação só pode ser usa-
da quando se tem certeza de que a fila não é vazia, o que se pode testar com a função FilaVa-
zia. 
 
 
char FrenteFila(struct tipofila *fila) { 
 return fila->dado; 
} 
 
 
d) Inserir um elemento na Fila 
 
 Esta função recebe como parâmetros o valor dadonovo, a ser inserido, e o endereço 
do ponteiro fila, que dá acesso à fila. O resultado da operação é a inserção do dadonovo no 
fim da fila. 
 
void InsereFila(struct tipofila **fila, char dadonovo) { 
 struct tipofila *f1, *f2; 
 f1 = malloc (sizeof (struct tipofila)); 
 f1->dado = dadonovo; 
 f1->prox = NULL; 
 if (*fila == NULL) 
 *fila = f1; 
 else { 
 f2 = *fila; 
 while (f2->prox != NULL) 
 f2 = f2->prox; 
 f2->prox = f1; 
 } 
 return; 
} 
 
e) Retirar um elemento da Fila 
 
Tira Teima 
Tira Teima 
Tira Teima 
Tira Teima 
 6 
 Esta função recebe como parâmetro o endereço do ponteiro fila, que dá acesso à fila, e 
retorna o elemento que está na primeira posição da fila, retirando-o dela. Esta operação só 
pode ser usada quando se tem certeza de que a fila não é vazia, o que se pode testar com a 
função FilaVazia. 
 
char RetiraFila(struct tipofila **fila) { 
 struct tipofila *f1; 
 char car; 
 f1 = *fila; 
 *fila = f1->prox; 
 car = f1->dado; 
 free (f1); 
 return car; 
} 
Tira Teima 
 7 
4.3 Aplicações 
 
 Serão apresentadas agora algumas aplicações de pilhas e de filas. A partir deste ponto, 
as pilhas e as filas, por serem estruturas abstratas, serão manipuladas sempre através das ope-
rações vistas anteriormente (InsereFila, RetiraPilha, etc...) Desta forma o usuário não precisa 
saber qual foi a implementação utilizada em cada caso, e não tem outro acesso às estruturas 
utilizadas, que não sejam as operações pré-definidas. 
 
Veremos as seguintes aplicações: 
 
- manipulação de uma seqüência de caracteres 
 
- avaliação de expressão totalmente parentetizada 
 
- avaliação de expressão na forma pós-fixada 
 
- conversão de expressão in-fixada para pós-fixada 
 
- simulação de recursividade 
 
- pilhas ou listas de uso geral 
 
4.3.1 Manipulação de uma seqüência de caracteres 
 
 É dada uma seqüência de caracteres formada por letras e algarismosalternados, come-
çando por uma letra. A função deve construir outra seqüência que contenha todas as letras da 
seqüência dada, na mesma ordem e posições originais, e todos os algarismos da seqüência 
dada, nas posições originais, mas em ordem invertida. Como exemplo são dadas abaixo uma 
seqüência de entrada e outra de saída correspondente: 
 
 Entrada: A 5 F 8 B 4 C 9 D 7 
 Saída: A 7 F 9 B 4 C 8 D 5 
 
 A função ManipulaCaracteres supõe que tenham sido definidos anteriormente os tipos 
tipofila e tipopilha. A seqüência original é lida do arquivo arq e a seqüência de saída é escri-
ta na tela. 
 
[struct tipopilha { 
 char dado; 
 struct tipopilha *prox; 
};] 
 
[struct tipofila { 
 char dado; 
 struct tipofila *prox; 
};] 
 
void ManipulaCaracteres () { 
 struct tipofila *f1; 
 struct tipopilha *p1; 
 char x; 
 FILE *arq; 
 
 InicializaFila (&f1); 
Tira Teima 
 8 
 InicializaPilha (&p1); 
 arq = fopen ("t2.txt", "r"); 
 while (!feof(arq)){ 
 x = getc(arq); 
 if ((x!='\n')&& (x!=EOF)) 
 InsereFila (&f1, x); 
 x = getc(arq); 
 if ((x!='\n')&& (x!=EOF)) 
 InserePilha (&p1, x); 
 } 
 fclose (arq); 
 while ((!FilaVazia(f1)) && (!PilhaVazia(p1))) { 
 printf ("%c", RetiraFila (&f1)); 
 printf ("%c", RetiraPilha(&p1)); 
 } 
} 
 
4.3.2 Avaliação de expressão totalmente parentetizada 
 
 É dada uma expressão numérica em que todas as operações são cercadas por parênte-
sis, independentemente de sua prioridade, como por exemplo: ( 2 * ( 5 - 1 ) ) 
 
 Supõem-se definidos anteriormente os tipos tipopilha e tipopilha2. A expressão é lida 
do arquivo arq. A função AvaliaExpressaoParentetizada utiliza a função ResolveOperacao, 
que retira da pilha de operadores o último operador e, em seguida, realiza a operação desejada 
e volta a inserir o resultado na pilha de números. 
 
void AvaliaExpressaoParentetizada () { 
 struct tipopilha *p1, *p2; 
 char car; 
 int i; 
 FILE *arq; 
 
//------------ 
void ResolveOperacao () { 
 
 char op, c1, c2, caux; 
 int x,y; 
 
 if (PilhaVazia (p2)) { 
 if (PilhaVazia (p1)) { 
 caux = 0+'0'; 
 InserePilha (&p1,0+'0'); 
 } 
 } 
 else { 
 op = RetiraPilha (&p2); 
 c1 = RetiraPilha (&p1); 
 x = c1 - '0'; 
 c2 = RetiraPilha (&p1); 
 y = c2 - '0'; 
 switch (op) { 
 case '+' : InserePilha (&p1, y+x+'0'); break; 
 case '-' : InserePilha (&p1, y-x+'0'); break; 
 case '*' : InserePilha (&p1, y*x+'0'); break; 
 case '/' : InserePilha (&p1, y%x+'0'); break; 
 } 
 } 
} 
//------------ 
 
 InicializaPilha (&p1); 
 InicializaPilha (&p2); 
 arq = fopen ("t3.txt", "r"); 
 while ((car = getc (arq)) != EOF) { 
 if (car != '\n') 
 if ((car>='0')&&(car<='9')) 
 InserePilha (&p1, car); 
 else 
 if (car == ')') 
Tira Teima 
 9 
 ResolveOperacao (); 
 else 
 if (car != '(') 
 InserePilha (&p2, car); 
 } 
 fclose (arq); 
 printf("%d \n", RetiraPilha (&p1)-'0'); 
} 
 
4.3.3 Avaliação de expressão na forma pós-fixada 
 
 A função deve fazer a avaliação de uma expressão dada em forma pós-fixada. A ex-
pressão se encontra no arquivo arq. A função supõe que tenha sido definido o tipo tipopilha. 
A função AvaliaExpressaoPosfixada utiliza a função ResolveOperacao, que executa a opera-
ção desejada entre dois operandos e retorna o resultado. 
 
[ Uma expressão algébrica é dita em forma pós-fixada, ou notação polonesa, quando o opera-
dor é colocado depois dos dois operandos. Vejamos alguns exemplos: 
 
notação in-fixada notação pós-fixada 
 
A + B A B + 
(A + B) * C A B + C * 
(A * B + C) / D A B * C + D / 
 
Uma das vantagens da notação polonesa é prescindir do uso de parênteses. ] 
 
 
void AvaliaExpressaoPosFixada () { 
 struct tipopilha *p1; 
 char c, c1, c2; 
 FILE *arq; 
 int w; 
 
//------------ 
int ResolveOperacao (char c1, char c, char c2) { 
 
 int x, y, z; 
 
 x = c1 - '0'; 
 y = c2 - '0'; 
 switch (c) { 
 case '+' : z = x+y; break; 
 case '-' : z = x-y; break; 
 case '*' : z = x*y; break; 
 case '/' : z = x/y; break; 
 } 
 return z; 
} 
//------------ 
 
 InicializaPilha (&p1); 
 arq = fopen ("t6.txt", "r"); 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 if ((c!='+')&&(c!='-')&&(c!='*')&&(c!='/')) 
 InserePilha (&p1, c); 
 else { 
 c2 = RetiraPilha (&p1); 
 c1 = RetiraPilha (&p1); 
 w = ResolveOperacao (c1, c, c2); 
 InserePilha (&p1, w+'0'); 
 } 
 } 
 } 
 printf ("resultado: %d \n", RetiraPilha (&p1)-'0'); 
 fclose (arq); 
} 
Tira Teima 
 10 
 
 
 
4.3.4 Conversão de expressão in-fixada para pós-fixada 
 
 
 A função ConversaoParaPosFixada lê de um arquivo arq1 uma expressão algébrica 
em forma in-fixada, e escreve na tela a mesma expressão, na forma pós-fixada. A função 
utiliza os tipos tipopilha e tipofila. A fila f1 armazena os operandos e a pilha p1 armazena 
os operadores e o sinal ‘(‘. A função Prioridade retorna a prioridade de execução de uma 
operação. A variável aux serve apenas para eliminar o caractere ‘(‘ quando este for encontra-
do no topo da pilha p1. 
 
[tabela de prioridades 
 
1. exponenciação 
2. multiplicação e divisão 
3. soma e subtração 
4. sinal '(' ] 
 
 
void ConversaoParaPosFixada () { 
 struct tipopilha *p1; 
 struct tipofila *f1; 
 char c, aux; 
 FILE *arq; 
 
//------------ 
int Prioridade (char c1) { 
 
 switch (c1) { 
 case '^' : return 1; break; 
 case '*' : case '/' : return 2; break; 
 case '+' : case '-' : return 3; break; 
 case '(' : return 4; break; 
 } 
} 
//------------ 
 
 InicializaPilha (&p1); 
 InicializaFila (&f1); 
 arq = fopen ("t8.txt", "r"); 
 while ((c = getc (arq)) != EOF) { 
 if (c != '\n'){ 
 if ((c!='^')&&(c!='+')&&(c!='-')&&(c!='*')&&(c!='/')&&(c!='(')&&(c!=')')) 
 InsereFila (&f1, c); 
 else 
 if (c==')') { 
 while (TopoPilha(p1) != '(') 
 InsereFila (&f1, RetiraPilha (&p1)); 
 aux = RetiraPilha (&p1); 
 } 
 else { 
 if ((c!='(') && (!PilhaVazia (p1))){ 
 while ((Prioridade (TopoPilha (p1)) <= Prioridade (c))&&(!PilhaVazia (p1))) 
 InsereFila (&f1, RetiraPilha (&p1)); 
} InserePilha (&p1,c); 
 } 
 } 
 } 
 fclose (arq); 
 while (!PilhaVazia (p1)) 
 InsereFila (&f1, RetiraPilha (&p1)); 
 while (!FilaVazia (f1)) 
 printf ("%c", RetiraFila (&f1)); 
} 
Tira Teima 
 11 
 
 
 
4.3.5 Simulação de recursividade 
 
 As pilhas podem ser utilizadas para simular a recursividade na resolução de certos 
problemas. É útil entender como as pilhas permitem a recursividade, pois é através delas que 
as linguagens implementam a recursividade. 
 
 Como exemplo tomemos a geração da seqüência de Fibonacci. 
 
 A seqüência de Fibonacci pode ser definida do seguinte modo: 
 
fib (0) = 1 
fib (1) = 1 
fib (n) = fib (n-1) + fib (n-2) , para n > 1 
 
 A seqüência gerada de acordo com esta definição é a seguinte: 
 
n 0 1 2 3 4 5 6 ... 
fib 1 1 2 3 5 8 13 ... 
 
A função abaixo calcula o n-ésimo termo, que fica armazenado na variável fib. Supõe-se defi-
nido o tipo tipopilha. 
 
 
int Fibonacci (int n) { 
 struct tipopilha *p1; 
 int fib, x; 
 
 InicializaPilha (&p1); 
 InserePilha (&p1, n); 
 fib = 0; 
 while (!PilhaVazia (p1)) { 
 x = RetiraPilha (&p1); 
 if ((x == 0) || (x == 1)) 
 fib = fib + 1; 
 else { 
 InserePilha (&p1, x-1); 
 InserePilha (&p1, x-2); 
 } 
 } 
 return fib; 
} 
 
 
4.3.6 Pilhas ou listas de usogeral 
 
 Em todas as aplicações vistas até aqui, sempre se supõe definidos os tipos tipopilha e 
tipofila, que são pilhas ou filas contendo caracteres. É interessante a criação de pilhas ou filas 
de uso geral, nas quais é possível armazenar qualquer tipo de dado. Isto é possível na lingua-
gem C, se utilizarmos um ponteiro apontando para void como informação contida na pilha ou 
na fila. Este ponteiro é de uso genérico, podendo apontar para qualquer tipo de estrutura. 
 
 
Tira Teima 
 12 
 Como exemplo de aplicação de uma pilha de uso geral, vamos resolver o problema das 
Torres de Hanói, simulando a recursividade através de uma pilha de uso geral. 
 
[ O problema das Torres de Hanói é um exemplo clássico de uso de recursividade. São dados três 
pinos A, B, e C, e um conjunto de discos furados, de diferentes tamanhos, que se encaixam nesses 
pinos. Os discos estão inicialmente no pino A e devem ser transferidos para o disco B, utilizando o 
pino C como auxiliar. Tanto na posição inicial como em qualquer posição intermediária, os discos 
devem estar dispostos de modo que nunca um disco maior fique sobre um disco menor. Os movimen-
tos devem ser feitos com um disco de cada vez. ] 
 
{ FIGURA DE TRÊS PINOS COM 3 DISCOS } 
 
 Para resolver o problema de forma recursiva, deve-se raciocinar da seguinte forma: 
para levar n discos de A para B, basta levar os n – 1 discos superiores de A para C, em segui-
da levar o disco maior de A para B, e depois levar os n – 1 discos de C para B. No entanto, a 
operação de transferir n – 1 discos não é permitida pela própria regra do problema, e deve 
então ser abordada como uma chama da recursiva ao mesmo problema, mas com o grau de 
dificuldade reduzido de n para n – 1. 
 
 Definamos, então, o movimento de n discos, do pino A para o pino B, utilizando o 
pino C como auxiliar, através da função Hanoi (A,B,C,n). Para todo n > 1, esta função pode 
ser decomposta em outras três: 
 
Hanoi (A,C,B,n-1) 
Hanoi (A,B,C, 1 ) 
Hanoi (C,B,A,n-1) 
 
 As três chamadas são recursivas, mas a primeira e a terceira diminuem o número de 
discos, de n para n-1, enquanto a segunda constitui um caso trivial, em que o número de dis-
cos é 1, ou seja, neste caso o movimento do disco é efetuado. 
 
 Definamos um tipo registro que contenha os parâmetros de Hanoi, do seguinte modo: 
 
struct reghanoi { 
 char o; 
 char d; 
 char a; 
 int k; }; 
 
 Definamos todas as operações de manipulação de uma pilha cujo tipo denominaremos 
tipopilhageral, que é uma pilha cujo elemento constituinte é um ponteiro que aponta para 
void, do seguinte modo: 
 
struct tipopilhageral { 
 void *dado; 
 struct tipopilhageral *prox; 
} ; 
 
 A função Hanoi pode então ser escrita, com a ajuda das funções EmpilhaHanoi e De-
sempilhaHanoi, que servem para criar ou eliminar os registros apontados pelos ponteiros da 
pilha de tipo tipopilhageral. 
 
 
 13 
 
 
 
 
 
//--------------------------------------------- 
void Hanoi (char origem, char destino, char auxiliar, int n) { 
 struct tipopilhageral *phanoi; 
 struct reghanoi { 
 char o; 
 char d; 
 char a; 
 int k; }; 
 
//--------------------------------------------- 
void *EmpilhaHanoi (struct tipopilhageral *pilha, char origem, char destino, char auxiliar, int n) { 
 struct reghanoi *paux1; 
 void *paux2; 
 paux1 = malloc (sizeof (struct reghanoi)); 
 paux1->o = origem; 
 paux1->d = destino; 
 paux1->a = auxiliar; 
 paux1->k = n; 
 paux2 = paux1; 
 InserePilha (&pilha, paux2); 
 return pilha; 
} 
 
//--------------------------------------------- 
void *DesempilhaHanoi (struct tipopilhageral *pilha, char *origem, char *destino, char *auxiliar, int *n) { 
 struct reghanoi *paux1; 
 void *paux2; 
 paux2 = RetiraPilha (&pilha); 
 paux1 = paux2; 
 *origem = paux1->o; 
 *destino = paux1->d; 
 *auxiliar = paux1->a; 
 *n = paux1->k; 
 free (paux2); 
 return pilha; 
} 
 
//---------------------------------------------- 
 InicializaPilha (&phanoi); 
 phanoi = EmpilhaHanoi (phanoi, origem, destino, auxiliar, n); 
 while (!PilhaVazia (phanoi)) { 
 phanoi = DesempilhaHanoi (phanoi, &origem, &destino, &auxiliar, &n); 
 if (n == 1) 
 printf ("movimento de %3c para %3c \n", origem, destino); 
 else { 
 phanoi = EmpilhaHanoi (phanoi, auxiliar, destino, origem, n-1); 
 phanoi = EmpilhaHanoi (phanoi, origem, destino, auxiliar, 1); 
 phanoi = EmpilhaHanoi (phanoi, origem, auxiliar, destino, n-1); 
 } 
 } 
} 
Tira Teima 
 14 
[página de conclusão] 
 
 O estudo das pilhas e filas fornece ao aluno um bom instrumental para resolver diver-
sos problemas computacionais, em especial aqueles que envolvem recursividade. Além disso, 
seu conhecimento é fundamental para auxiliar na solução de alguns problemas que utilizam 
estruturas que serão vistas nos próximos tópicos. 
 
 
 1 
ED – esquema para tutorial 04 
 
Capítulo 4 – Árvores 
 
 
[página de abertura] 
 
 Ao concluir este capítulo, você deverá ser capaz de: 
 
- compreender o que são as árvores 
- conhecer os algoritmos básicos que utilizam as árvores binárias 
- representar árvores genéricas por meio de árvores binárias 
- utilizar árvores binárias de pesquisa 
- fazer balanceamento de árvores binárias de pesquisa 
 2 
4.1 Conceitos 
 
 Uma árvore é uma estrutura de dados que se caracteriza por uma relação de hierarquia 
entre os elementos que a compõem. Exemplos de estruturas em forma de árvore são: 
 
- o organograma de uma empresa; 
- a divisão de um livro em capítulos, seções, tópicos; 
- a árvore genealógica de uma pessoa. 
 
 De um modo um pouco mais formal, podemos dizer que uma árvore é um conjunto 
finito de um ou mais nós, tais que: 
 
 a) existe um nó denominado raiz; 
 
 b) os demais nós formam m>=0 conjuntos disjuntos s1, s2, ... sm, tais que cada um 
desses conjuntos também é uma árvore (denominada sub-árvore). 
 
 As árvores podem ser representadas de diversos modos, como por exemplo: 
 
a) representação hierárquica 
 
{inserir desenho tirado, ou do livro, ou do CBT} 
 
Neste exemplo, A é a raiz da árvore. Os nós B e C são "filhos" de A, e dão origem a duas 
sub-árvores, nas quais D e E são "filhos” de B, e F é "filho" de C. 
 
b) representação por conjuntos 
 
{inserir desenho tirado, ou do livro, ou do CBT} 
 
A árvore aqui representada é a mesma do desenho anterior. Neste caso, cada nó é representa-
do por um conjunto formado por seus "filhos". 
 
c) representação por expressão parentetizada 
 
A mesma árvore pode ser representada pela expressão: 
 
( A ( B ( D ( ) E ( ) ) C ( F ( ) ) ) ) 
 
Cada conjunto de parêntesis correspondentes contém um nó e seus filhos. Se um nó não tem 
filhos, ele é seguido por um par de parêntesis sem conteúdo. 
 
d) representação por expressão não parentetizada 
 
Ainda utilizando a mesma árvore, podemos usar a representação abaixo: 
 
A 2 B 2 D 0 E 0 C 1 F 0 
 
Cada nó é seguido por um número que indica a quantidade de filhos desse nó, e em seguida 
por esses filhos, representados do mesmo modo. 
 3 
 
 Pode-se representar uma árvore de muitos outros modos, mas é interessante notar que, 
dentre os exemplos apresentados, a representação a) é a que permite uma melhor visualização, 
e que será utilizada a partir deste ponto. As representações c) e d) não permitem boa visuali-
zação da estrutura, mas podem ser úteis para guardar em arquivos os dados de uma árvore. 
 
 Como, por definição, os sub-conjuntos s1, s2, ... sm são disjuntos, cada nó só pode ter 
um "pai". Assim, o desenho abaixo, por exemplo, não representa uma árvore: 
 
{inserir desenho tirado, ou do livro, ou do CBT} 
 
Vejamos agora alguns termos utilizados para identificar algumas características de uma árvoreou de alguma parte dela. 
 
{ver o esquema montado no CBT para este caso, tente fazer algo igual ou parecido} 
 
- raiz – nó de origem da árvore 
- folhas – nós que não têm filhos 
- grau de um nó – número de filhos de cada nó 
- nível de um nó – por definição, é zero para a raiz, e, para os demais nós, é o número de 
 "linhas" que ligam o nó à raiz 
- altura da árvore – é o nível mais alto da árvore 
- floresta – conjunto de árvores disjuntas (eliminando-se a raiz de uma árvore, obtém-se 
 uma floresta 
 4 
4.2 Árvores Binárias 
 
 Árvores binárias são árvores em que todos os nós têm grau menor ou igual a dois. 
Desse modo, cada nó pode ter no máximo dois filhos, que são identificados como filho à es-
querda e filho à direita. 
 
4.2.1 Caminhamento em Árvores Binárias 
 
 Dada uma árvore binária, é possível estabelecer várias formas para percorrer todos os 
seus nós, sem repetir nenhum e sem deixar de passar por nenhum. Esta operação é denomina-
da caminhamento, que é usada, por exemplo, para consultar ou alterar as informações conti-
das nos nós. 
 
 As três maneiras mais usuais para percorrer os nós são: 
 
- caminhamento pré-fixado: 
 1. visita a raiz 
 2. percorre a sub-árvore da esquerda 
 3. percorre a sub-árvore da direita 
 
- caminhamento in-fixado: 
 1. percorre a sub-árvore da esquerda 
 2. visita a raiz 
 3. percorre a sub-árvore da direita 
 
- caminhamento pós-fixado: 
 1. percorre a sub-árvore da esquerda 
 2. percorre a sub-árvore da direita 
 3. visita a raiz 
 
Tomando como exemplo a árvore abaixo, temos, para cada tipo de caminhamento, a corres-
pondente seqüência de nós: 
 
{veja a animação do CBT, acho que podemos fazer uma animação como um applet} 
 
caminhamento pré-fixado: A B D E G C F H I 
 
caminhamento in-fixado; D B G E A C H F I 
 
caminhamento pós-fixado: D G E B H I F C A 
 
 
4.2.2 Implementação de Árvores Binárias 
 
Na implementação das árvores binárias, utilizaremos para cada nó um registro contendo um 
campo para dados (dado), um ponteiro que aponta a sub-árvore da esquerda (esq) e um pon-
teiro que aponta a sub-árvore da direita (dir). O acesso à árvore é feito através de um ponteiro 
que aponta para a raiz (ainicio). 
 
 
 5 
typedef struct nodo { 
 char dado; 
 struct nodo *esq, *dir; 
} arvore ; 
 
arvore *ainicio; 
 
 Pela própria definição, pode-se perceber que as árvores são estruturas adequadas para 
o uso de algoritmos recursivos. A própria definição formalizada acima para uma árvore é 
uma definição recursiva. 
 
[ 
De um modo um pouco mais formal, podemos dizer que uma árvore é um conjunto finito de um ou 
mais nós, tais que: 
 
 a) existe um nó denominado raiz; 
 
 b) os demais nós formam m>=0 conjuntos disjuntos s1, s2, ... sm, tais que cada um desses 
conjuntos também é uma árvore (denominada sub-árvore). ] 
 
4.2.3 Algoritmos Básicos em Árvores Binárias 
 
 A maior parte dos algoritmos apresentados aqui são recursivos. Para efeitos didáticos, 
em alguns casos se apresenta também o algoritmo que realiza a operação equivalente, fazendo 
uso de uma pilha de ponteiros tipo void, isto é, ponteiros que podem apontar para qualquer 
elemento. No caso, são utilizados apontando para os nós da árvore. Os algoritmos recursivos, 
em geral, são mais simples. 
 
 Muitas vezes, o acesso à árvore pode se modificar durante a execução de uma função. 
Neste caso, será passado como parâmetro o endereço do ponteiro de acesso à árvore, denomi-
nado eainicio. 
 
 As definições dessas variáveis ficam sendo então: 
 
arvore *ainicio; 
arvore **eainicio; 
 
 Por exemplo: 
 
Se uma função é definida como: 
 
void nome_da_funcao (arvore **eainicio) 
 
Então a chamada a essa função será efetuada da seguinte forma: 
 
nome_da_funcao (&aini) 
 
onde aini é um ponteiro para arvore, ou seja, fora da função foi definido que: 
 
arvore *aini; 
 
 
 6 
 Abaixo são examinados alguns dos algoritmos básicos que utilizam árvores binárias: 
 
a) Algoritmo de caminhamento em ordem pré-fixada utilizando pilha – versão 1 
 
//--- definição do tipo de pilha de uso geral 
typedef struct tipopilhageral { 
 void *dado; 
 struct tipopilhageral *prox; 
} pilhageral; 
 
//--------------------------------------------- 
void CaminhaPreComPilha1 (arvore *ainicio) { 
 arvore *a1; 
 pilhageral *p1; 
 char c; 
 
 a1 = ainicio; 
 InicializaPilha (&p1); 
 InserePilha (&p1, a1); 
 while (!PilhaVazia (p1)) { 
 a1 = RetiraPilha (&p1); 
 if (a1 != NULL) { 
 printf ("%c", a1->dado); 
 InserePilha (&p1, a1->dir); 
 InserePilha (&p1, a1->esq); 
 } 
 } 
} 
 
 
Observação: Nesta versão, a função de caminhamento insere na pilha os ponteiros NULL en-
contrados no caminhamento. Consequentemente, ela verifica se ainicio é NULL em cada reti-
rada da pilha. 
 
b) Algoritmo de caminhamento em ordem pré-fixada utilizando pilha – versão 2 
 
//--- definição do tipo de pilha de uso geral 
typedef struct tipopilhageral { 
 void *dado; 
 struct tipopilhageral *prox; 
} pilhageral; 
 
//--------------------------------------------- 
void CaminhaPreComPilha2 (arvore *ainicio) { 
 arvore *a1; 
 pilhageral *p1; 
 char c; 
 
 a1 = ainicio; 
 InicializaPilha (&p1); 
Tira Teima 
 7 
 if (a1 != NULL) 
 InserePilha (&p1, a1); 
 while (!PilhaVazia (p1)) { 
 a1 = RetiraPilha (&p1); 
 printf ("%c", a1->dado); 
 if (a1->dir != NULL) 
 InserePilha (&p1, a1->dir); 
 if (a1->esq != NULL) 
 InserePilha (&p1, a1->esq); 
 } 
} 
 
 
Observação: Nesta versão, a função de caminhamento não insere na pilha os ponteiros NULL 
encontrados no caminhamento. Consequentemente, ela não verifica se ainicio é NULL em 
cada retirada da pilha. Na primeira inserção na pilha, deve ser feito um teste para verificar se a 
árvore é vazia Comparando-se as duas versões, tem-se que a versão 1 executa muito mais 
inserções e retiradas de elementos nas pilhas (aproximadamente metade dos ponteiros de uma 
árvore binária são NULL). 
 
c) Algoritmo de caminhamento em ordem in-fixada utilizando pilha – versão 1 
 
 Para o caminhamento em ordem in-fixada, cada elemento da árvore entra na pilha duas 
vezes (acompanhe o funcionamento no TiraTeima). Para discernir se o elemento está entrando 
pela primeira ou pela segunda vez, criou-se um novo tipo de pilha, com um elemento int, que 
recebe o valor 0 quando a entrada é feita na primeira vez, e recebe o valor 1 quando a entrada 
é feita pela segunda vez. Para facilitar a compreensão, foi desenvolvida a função Empilha, 
interna à função de caminhamento, que procede à inserção na pilha. 
 
 A versão 1 processa o caso de ainicio ser igual a NULL. 
 
void CaminhaInComPilha1 (arvore *ainicio) { 
 
 pilhageral *pilha; 
 void *paux1; 
 struct reg { 
 arvore *arv; 
 int pri; 
 }; 
 struct reg *paux2; 
 arvore *a1; 
 
//------------------------------------- 
void Empilha (arvore *a, int n){ 
 paux2 = malloc (sizeof (struct reg)); 
 paux2->arv = a; 
 paux2->pri = n; 
 InserePilha (&pilha, paux2); 
} 
//-------------------------------------- 
Tira Teima 
Tira Teima 
 8 
 
 a1 = ainicio; 
 InicializaPilha(&pilha); 
 Empilha(a1, 1); 
 while (!PilhaVazia (pilha)) { 
 paux2 = RetiraPilha (&pilha); 
 a1 = paux2->arv; 
 if (a1 != NULL) { 
 if (!paux2->pri) printf ("%c", paux2->arv->dado); 
 else { 
 Empilha (a1->dir, 1); 
 Empilha (a1, 0); 
 Empilha (a1->esq, 1); 
 } 
 } 
 } 
} 
 
 
d) Algoritmo de caminhamento em ordem in-fixada utilizando pilha – versão 2 
 
 Neste caso a pilha utilizada é igual à da versão 1. A função de caminhamento não inse-
re nem retira da pilha os ponteiros iguais a NULL. Valem as mesmas observações feitas nos 
itens a)