Estruturas de Dados e Algoritmos em C++

Prévia do material em texto

BIBLIOGRAFIA BÁSICA:  
 
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian,​ Estruturas de dados e seus algoritmos​, 2. ed. Rio de 
Janeiro: LTC, 1997. 
 
KOFFMAN, Elliot B., WOLFGANG, Paul A.T., ​Objetos, Abstração, Estrutura de dados e Projeto usando C++​, 
1.ed. Rio de Janeiro: LTC,2008.  
 
EDELWEISS,N, GALANTE,R.M., ​Estrutura de Dados​, Volume 18 – Série Livros Didáticos Informática UFRGS. 
1.ed.RS: Bookman, 2009. 
 
BIBLIOGRAFIA COMPLEMENTAR: 
 
DEITEL, H. M; DEITEL, P. J. ​C++ Como programar​ . 5. ed. Rio de Janeiro: Prentice Hall, 2006.  
 
STROUSTRUP, Bjarne. ​Linguagem de programação C++​. 3. ed. Porto Alegre: Bookman, 2002.  
 
CORMEN, Thomas H. et al. ​Algoritmos: teoria e prática​. Rio de Janeiro: Campus, 2002.  
 
FORBELLONE, André Luiz Villar; EBERSPACHER,Henri Frederico. ​Lógica de Programação: A construção de 
Algoritmos e Estrutura de Dados​. 3. ed. São Paulo: Makron Books, 2005.  
 
CELES, Waldemar; CERQUEIRA,Renato;RANGEL,José Lucas. ​Introdução a Estrutura de Dados com técnicas 
de programação em C​. Rio de Janeiro : Elsevier, 2004.  
 
PINTO, Wilson Silva. ​Introdução ao desenvolvimento de algoritmos e estrutura de dados.​ 6.ed. São Paulo: 
Editora Érica, 1990.   
 
>>>>  ​https://www.eecis.udel.edu/~portnoi/classroom/estrutura_dados/2007_1/estrutura_dados2007.1.html 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
AULA 1: ESTRUTURA DE DADOS 
 
Conceito de estruturas de dados 
 
• Uma estrutura de dados pode ser definida como sendo uma coleção de variáveis, podendo ser tipos 
iguais ou diferentes, reunidas sob um único nome. Vários autores denominam estrutura de dados 
como sendo registros. 
(Mizrahi, 2006) 
 
HOMOGÊNEA:​ VETORES E MATRIZES; SUBPARTES DO MESMO TIPO. 
HETEROGÊNEA:​ REGISTROS; SUBPARTES DE TIPOS DIFERENTES. 
 
MATRIZ UNIDIMENSIONAL ­ VETOR: 
 
• Matrizes e vetores permitem armazenar uma coleção de variáveis do mesmo tipo.  
 
• Enquanto a matriz possui varias dimensões, o vetor possui apenas uma dimensão. 
 
TIPOS DE DADOS E TIPOS ABSTRATOS DE DADOS: 
 
• Tipos de dados: ​são utilizados pelas linguagens de programação para definir o conjunto de valores que uma 
variável pode assumir.  
 
• Exemplos: 
– tipo de dado inteiro pode assumir valores como 1, 25, 1896, etc.; 
– tipo data pode assumir valores como “25/12/2015”, “07/09/1822”, etc. 
 
• Tipos abstratos de dados: ​são formados por um conjunto de tipos de dados e um conjunto de 
procedimentos (funções) que podem ser aplicados sobre este conjunto de tipos de dados. 
 
• Para que um tipo abstrato de dado seja implementado, são utilizadas as estruturas de dados. 
 
ÁRVORE, GRAFO, PILHA, FILA E LISTA: 
 
• Estruturas de dados ­ classificação 
– Lineares e não lineares. 
• Estruturas de dados lineares 
– Listas, Pilhas, Filas 
• Estruturas de dados não linear 
– Árvores e  Grafos 
 
LISTA: 
 
• Listas:​ são estruturas que permitem representar um conjunto de dados, que de alguma forma se relacionam, 
de forma que os elementos fiquem dispostos em sequência. 
(VELOSO, 1986)  
 
 
 
LISTA ­ OPERAÇÕES MAIS COMUNS: 
 
• Criar 
• Verificar lista vazia 
• Verificar lista cheia 
• Inserir 
• Alterar 
• Remover 
• Busca 
• Exibir a quantidade 
• Combinar 
• Dividir lista 
• Ordenar 
• Esvaziar 
 
PILHA: 
 
• Pilha​: é um tipo especial de lista onde os elementos a serem inseridos ou removidos ocorrem no topo da 
pilha. Esta característica é conhecida como ​LIFO ​(​Last In, First Out ​­ Último a Entrar, Primeiro a Sair). 
(TANENBAUM; LANGSAM; AUGENSTEIN 1995) 
 
 
 
PILHAS ­ OPERAÇÕES MAIS COMUNS: 
 
• Criar: ​cria uma pilha vazia. 
• Empilhar: ​insere um novo elemento no topo da pilha.  
• Desempilhar: ​remove um elemento do topo da pilha. 
• Exibir topo ou a quantidade​. 
• Esvaziar​: esvazia todos os elementos da pilha. 
 
FILA: 
• Fila​: um tipo especial de lista, onde os elementos são inseridos em uma extremidade, chamada início da fila, 
e retirados na extremidade oposta, chamada final da fila. Esta característica é conhecida como ​FIFO ​(​First In, 
First Out ​­ Primeiro a Entrar, Primeiro a Sair).  
 
 
 
FILAS ­ OPERAÇÕES MAIS COMUNS: 
 
• Criar: ​cria uma fila vazia. 
• Enfileirar: ​insere um elemento no fim da fila. 
• Desenfileirar: ​remover um elemento no início da fila. 
• Exibir início: ​exibe o elemento do início da fila. 
• Exibir a quantidade: ​retorna a quantidade de elementos da fila. 
• Esvaziar: ​esvazia a fila. 
 
ÁRVORES: ​A árvore é composta de nós e arestas (conexões).  
 
 
 
 
 
 
GRAFOS: 
 
 
 
 
 
 
Aula 2: Funções 
 
MODULARIZAÇÃO: 
 
O grau de complexidade que alcança alguns programas nos leva a dividi­lo em módulos para que possamos 
melhorar o entendimento do programa, depurar os erros com mais facilidade, simplificar a manutenção porque 
podemos trocar somente um determinado módulo, reutilizar o código no mesmo programa ou em outro programa, 
etc.  
Esses módulos são “pequenos programas”  com tarefas bem definidas.​ São conhecidos em algumas 
linguagens por procedimentos e, na linguagem C++,  por ​funções​. 
Chamamos essa técnica que decompõe um programa em partes menores de ​modularização​.  
 
FUNÇÃO: 
 
Por que criar funções se a linguagem C++ apresenta um conjunto razoável de funções pré­definidas? 
Porque, por maior que seja esse conjunto, nunca atenderá, totalmente, às necessidades de todos os programas. 
 
2.1 Conceito de Funções 
 
Uma função é um​ conjunto de comandos limitado por um par de chaves e precedido por um cabeçalho​.   
Na construção de uma função, todas as estruturas que você estudou na disciplina de Algoritmos poderão ser 
usadas no corpo da função, mas uma função é independente da outra e, por essa razão, ​jamais poderá ser criada 
dentro de outra função. 
 
Definição da função: 
 
 
Entendemos que a criação de uma função é resultado de uma necessidade que você constatou e da ausência de 
uma função pré­definida. 
Alguns exemplos de funções que você poderá criar: 
 
Função que reajusta salário, Função que exibe um menu, Função que calcule a média aritmética, Função que gera 
um outro vetor, Função que ordena um vetor, Função que remove elementos de uma fila… 
2.2 O Protótipo de uma Função 
 
O protótipo de uma função contém o ​tipo de retorno​ da função, o ​nome ​da função, ​seguido de um par de 
parênteses que podem ou não ter  parâmetros​. É finalizado, ​obrigatoriamente​, com o ​;(ponto­e­vírgula)​. 
Em outras palavras,​ ​o protótipo de uma função é o cabeçalho da função com ;(ponto­e­vírgula) ao final​. 
 
<TIPO DE FUNÇÃO> NOME_DA_FUNÇÃO (DECLARAÇÕES DOS PARÂMETROS); 
 
2.3 Localização das Funções 
As funções poderão ser colocadas ​antes​, ou ​depois​, da ​main​.  
 
Se colocadas ​antes ​da main, elas serão ​“conhecidas” pelo compilador antes de serem chamadas​, evitando 
maiores problemas, mas, à medida que o ​número de funções cresce,​ ​diminui a legibilidade​ do programa.  
 
Se colocadas ​depois ​da main, ​aumentamos a legibilidade​, mas criamos um ​problema​: ​função é chamada antes 
da identificação dela pelo compilador​. Esse contratempo foi ​resolvido ​de uma forma muito simples: os 
protótipos das funções​ serão localizados ​antes da main​ e as ​definições, depois da main​. 
 
 
 
ATENÇÃO:  
1 ­ Não confunda: Definição é o cabeçalho e o corpo enquanto que protótipo é o cabeçalho com ponto e 
vírgula ao final, podendo até se apresentar de forma simplificada como veremos mais adiante. 
 
2­ A prototipagem é uma técnica que declara funções através dos seus protótipos antes da main, indicando 
assim que as funções existem, mas se encontram em outro lugar. 
 
2.4 Chamada da função e o seu retorno:  
 
Quando uma função é chamada, o ​fluxo de controle​ é desviado para essa função e, à partir desse momento, os 
comandos da funçãosão executados e, ao ​finalizar o fluxo​ ​retorna​ ao comando ​seguinte ​daquele onde ela foi 
ativada (se for void)​ ou ao ponto de onde ela ​foi chamada​ em ​funções com​ ​retorno​. 
 
2.5 Tipos de Funções 
2.5.1 Função sem parâmetros 
 
Uma função que não retorna nada para a função chamadora é do tipo ​void ​e esse tipo de função pode ser 
considerado, hierarquicamente, abaixo da main, tendo em vista que ela faz tudo mesmo sem receber qualquer 
argumento. 
 
Vejamos alguns protótipos: 
void asteriscos(); 
void menu() ; 
void calculaReajuste(); 
 
ATENÇÃO:​ Você deve ter percebido que nada foi colocado entre os parênteses, mas poderia, embora seja 
dispensável, colocar a palavra void.  
Sendo assim, o primeiro protótipo poderia ser escrito da seguinte forma: ​void asteriscos(void); 
 
Uma função do tipo ​void​, tendo ou não parâmetros, ​é chamada pelo nome​, isto é, não precisará que um comando 
lhe anteceda. Se tiver parâmetros, eles estarão presentes entre os parênteses. 
 
nomeDafunção(...) 
 
Construa uma função que exiba 20 asteriscos: 
 
void asteriscos() 
{ 
  for(int x=1; x<=20; x++) 
   cout<<"*"; 
} 
 
 
 
 
Construa uma função que exiba um menu com os seguintes itens: pilha, fila, lista, arvore, grafo: 
 
void menu() 
{ 
  system("cls"); 
  cout<<"\nMenu\n"; 
  cout<<"\n1­Pilha"; 
  cout<<"\n2­Fila"; 
  cout<<"\n3­Lista";   
  cout<<"\n4­Arvore"; 
  cout<<"\n5­Grafo";   
  cout<<"\n6­Sair"; 
  cout<<"\nOpcao: ";   
} 
 
 
 
Construa uma função que calcule o reajuste salarial de uma pessoa, tendo em vista um valor de resjuste: 
 
void reajuste() 
{ 
  float valor, percentual, reajustado; 
  cout<<"\nDigite o valor que devera ser reajustado R$ "; 
  cin>>valor; 
  cout<<"\nDigite o valor do percentual de reajuste de 0 a 100: "; 
  cin>>percentual;  
  reajustado= valor + valor * percentual/100; 
  cout<<"\nValor reajustado R$ "<<reajustado; 
} 
 
 
 
 
FUNÇÃO COM PARÂMETROS: 
 
1 ­ Passagem por valor 
 
Na passagem por valor, uma ​cópia do valor​, ou valores, é ​passada para os parâmetros formais da função 
chamada através dos parâmetros reais da função chamadora​. Sendo que os​ parâmetros reais poderão estar 
representados por variáveis ou constantes​. 
A função chamada poderá operar esses valores, mas não alterará os valores da função chamadora. 
 
Suponha um autor de livro e um leitor. Ao tentar entender a solução de um problema, o leitor percebe que tem um 
erro. Ele corrige o erro, mas não corrige o original que está na editora, visto que ele recebeu uma cópia do livro. 
As funções pré­definidas que você viu em Algoritmos eram todas com passagem por valor. 
Funções com passagem por valor podem, ou não ter retorno. 
 
>>> Se a função tiver retorno, lembre­se de que uma função só poderá retornar um valor para a função 
chamadora. 
 
2 Passagem por referência 
 
       Na passagem por referência,​ o endereço da variável da função chamadora é passado para a função 
chamada​ e dessa forma, o valor poderá ser alterado. 
Na linguagem C, essa passagem tinha que ser feita através do uso da variável ponteiro e acarretava, quando não 
operado corretamente, em muitos problemas. 
Tendo em vista os problemas causados pela manipulação dos ponteiros, a linguagem C++ criou um tipo novo de 
dado, chamado referência que nada mais é do que uma forma de ​atribuir um nome alternativo(apelido ou alias) 
para um objeto​. 
  
Esse conceito aplicado aos parâmetros formais, parâmetros da função chamada, possibilitará  que a função 
chamada receba o endereço do valor da função chamadora, alterando­o. 
Esse tipo de passagem ficou mais simples do que o uso de ponteiros porque o compilador se responsabiliza por 
tudo. 
  
Como indicar uma referência? 
  
O operador ​&​ símbolo de endereço na linguagem ​C​ é usado com ​outra conotação na linguagem C++​ como 
afirma Saade, Joel:” ... assume o papel de ​declarador de referências​”(pág. 112). 
  
void troca(float&a, float&b);  
 
Então, concluímos que a passagem por referência, na linguagem C++, poderá ser feita de duas maneiras: 
 
Passagem por referência por ponteiros: ​uma variável do tipo ponteiro não guarda dado, mas o endereço de uma 
variável.  
 
Suponha uma variável inteira de nome ​a ​e uma variável inteira do tipo ponteiro de nome ​pa​. Assuma que a variável 
pa ​aponta para a variável ​a​, significando que o ​conteúdo ​de ​pa ​é o ​endereço ​de ​a​. Trabalhar com variável do tipo 
ponteiro implica no uso de dois operadores: ​&(endereço)​ e ​*(conteúdo do endereço apontado por pa).  
 
 
 
Passagem por referência: 
 
 
>>> referência não é ponteiro mas ambas manipulam endereço. 
 
 
 
 
 
 
FUNÇÃO  SIGNIFICADO 
void linha(char c, int n);  Função que recebe dois argumentos por passagem de 
valor. Um do tipo char e outro do tipo int, mas ​não 
retorna​ nada para função chamadora. 
int descobreIdade(int anoAtual, int anoNas);  Função que recebe dois argumentos por passagem de 
valor. Os dois do tipo inteiro e ​retorna​, para a função 
chamadora, um valor ​inteiro​. 
float areaRetangulo(float, float);  Função que recebe dois argumentos reais e ​retorna​, 
para a função chamada, um valor ​real​.  
void troca(float& , float&);  Função que recebe dois argumentos que são 
endereços que armazenam números reais, por 
passagem por referência. A função ​não retorna​ nada 
para a função chamadora. 
 
Uma função que retorna valor deverá ser chamada através de um comando, não importando se ela tem, ou não, 
parâmetros. 
 
O comando ​return 
Uma função que​ retorna valor terá, obrigatoriamente esse comando no corpo da função​. Isso não quer dizer 
que não poderá ter mais de um comando return no corpo da função. 
Quando existir múltiplas respostas, poderemos ter vários tipos de retorno. 
Pode estar presente uma variável, uma constante, uma expressão. 
 
variável = nomeDafunção(...); 
cout<<nomeDafunção(...); 
if(nomeDafunção(...)...); 
 
>>> Fique atento. Uma função só poderá retornar um valor! 
 
Construa uma função que receba valores que correspondem ao caracter e à quantidade de vezes que se 
deseja exibi­lo: 
 
void linha(char c, int n) 
{ 
  for(int x=1; x<=n; x++) 
   cout<<c; 
} 
 
 
Construa uma função que receba valores que correspondem ao ano atual e ao ano de nascimento de uma 
pessoa, retornando a idade que a pessoa terá até 31 de dezembro: 
 
int descobreIdade(int anoAtual, int anoNas) 
{ 
  return anoAtual ­ anoNas; 
} 
 
 
 
 
Construa uma função que receba valores que correspondem à base e à altura de um retângulo e retorne a 
área: 
 
float areaRetangulo(float b, float h) 
{ 
  return b*h; 
} 
 
 
 
 
Construa uma função que possa trocar valores de duas variáveis: 
 
void troca(float& a, float &b) 
{ 
 float aux; 
 aux=a; 
 a=b; 
 b=aux; 
} 
 
 
 
 
 ​Qualquer função poderá chamar outra função desde que a função chamada já esteja declarada, ou definida. 
 
Embora, a princípio, possa parecer mais simples, é sempre bom declarar as funções porque você não fica 
limitado à sequência das definições. Para dar maior legibilidade, seria melhor definir depois da main e, para 
isso, teria que declarar todas as funções. Já vimos que ​para declarar, é só colocar o protótipo antes da 
main​. 
 
Variáveis Locais: ​variáveis ​declaradas dentro das funções​. A esse tipo de declaração, onde as variáveis só são 
visualizadas nas funções onde foram declaradas, chamamos de variáveis locais.  
 
Variáveis Globais: ​Variáveis ​declaradas fora do escopo de todas as funções​ são chamadas de variáveis 
globais. Esse tipo de variável poderá ser ​manipulado por qualquer função​. 
 
E como fica a análise da função main()? 
 
Ao longo dos anos, vários ajustes foram feitos para que existisse um padrão. O tipo int  foi escolhido embora 
pudesse ser omitido. Mais tarde, aconteceu a remoção do int implícito.Sendo assim, o cabeçalho da main passou a 
ser: 
int main() 
 
Já vimos que é opcional o uso da palavra void entre os parênteses quando a função não tem parâmetros.  
Se a main é do tipo int, então tem retorno. Porque funciona sem return? 
 
A main é uma função chamada pelo sistema operacional e, ao finalizar, retorna, automaticamente, para o S.O. 
Sendo pontual, o return da main poderia ser dispensável, visto que ele serve para informar que o programa foi 
executado com sucesso e isso, podemos constatar. Entretanto seu retorno poderá ser usado pelo sistema 
operacional, mas isso é uma outra história. 
 
>>> Um bom hábito é escrever​ return 0;​ ou ​return EXIT_SUCCESS; ​em projetos maiores. 
 
Passando uma estrutura de dados homogênea para uma função: 
 
O armazenamento na MP de um vetor apenas é armazenado o​ primeiro endereço do primeiro elemento do 
vetor​.  
 
  
 
 
 
Considerações : 
1­ O endereço do 1o elemento do vetor é igual ao endereço do vetor. 
2­ Obtém­se o mesmo valor quando se pede para exibir o endereço do vetor e exibir o valor do vetor. 
 
PROTÓTIPO  SIGNIFICADO 
double media(double [ ], int tam);  Função que recebe ​dois argumentos​. O primeiro é 
o  endereço de um vetor do tipo real de dupla 
precisão (double). Enquanto que o segundo, por 
passagem de valor, recebe um número inteiro que 
corresponde ao tamanho do vetor. A função 
retorna ​um ​valor ​de ​dupla precisão​.  
int contaMaioresQueH(double [ ], int tam, double altP);  Função que recebe ​três argumentos​. O primeiro é 
o  endereço de um vetor do tipo real de dupla 
precisão (double). O segundo, por passagem de 
valor, recebe um número inteiro que corresponde 
ao tamanho do vetor e o terceiro, recebe, por 
passagem de valor, um número de dupla precisão 
(double) que corresponde a uma altura específica. 
A função ​retorna ​um ​valor inteiro​. 
void arredonda(double a[ ], int tam);  Função que recebe ​dois argumentos​. O primeiro é 
o  endereço de um vetor do tipo real de dupla 
precisão(double). Enquanto que o segundo, por 
passagem de valor, recebe um número inteiro que 
corresponde ao tamanho do vetor. A função ​não 
retorna valor​. 
void dobro(double [ ], double [ ], int tam);  Função que recebe ​três argumentos​. Os dois 
primeiros  são endereços  de dois vetores do tipo 
real de dupla precisão (double). Enquanto que o 
terceiro, por passagem de valor, recebe um número 
inteiro que corresponde ao tamanho do vetor. A 
função ​não retorna valor​. 
 
 
Construa uma função que receba o endereço um vetor que armazena notas dos alunos de uma turma e seu 
tamanho, retornando a média da turma: 
 
double media(double n[ ], int tam) 
{ 
   double soma=0; 
    for(int x=0; x<tam;x++) 
     soma+=n[x]; 
   return soma/tam; 
}  
 
 
 
Contrua uma função que receba o endereço de um vetor que armazena alturas de um grupo de atletas, seu 
tamanho e a altura mínima de corte, retornando a quantidade de atletas com altura superior ou igual ao 
corte. 
 
int contaMaioresQueH(double alts[ ], int tam, double altP) 
{ 
   int conta=0; 
    for(int x=0; x<tam;x++) 
     if(alts[x]>=altP)  
     conta++; 
   return conta; 
} 
 
 
 
 
Construa uma função que receba o endereço um vetor que armazena as notas da AV1 de uma turma e seu 
tamanho. A função deverá arredondar as notas para cima.  
 
void arredonda(double a[ ], int tam) 
{ 
 for(int x=0; x<tam;x++) 
  a[x]=ceil(a[x]); 
}  
 
 
 
Construa uma função que receba endereços de dois vetores e o tamanho deles. A função deverá gerar o 
vetor dobro. 
 
void dobro(double v1[ ], double v2[ ], int tam) 
{ 
    for(int x=0; x<tam;x++) 
 v2[x]= v1[x] * 2; 
}    
 
 
 
ESCOPO DE VARIÁVEIS (LOCAL E GLOBAL): 
 
PALAVRAS RESERVADAS: 
 
 
 
 
 
FUNÇÕES E VETORES COMO PARÃMETROS: 
 
 
 
 
 
 
Aula 3: Estruturas Heterogêneas 
 
Podemos definir uma estrutura como sendo​ um conjunto de elementos, geralmente, agrupados sob uma lógica 
e associados por um nome​. 
Esses elementos podem ser ​variáveis ​simples, ​matrizes​, outras ​estruturas ​e até ​funções​. 
Por essa definição, podemos concluir que uma estrutura pode ser formada por elementos de tipos diferentes. 
Cada elemento da estrutura é chamado de membro ou campo​. 
 
 
 
A definição termina com um ;  porque é um comando. É bom ressaltar que nenhuma variável foi declarada. 
Estruturas poderão ser definidas globalmente ou localmente. 
A declaração da estrutura pode ser feita ​antes ​ou ​depois ​da ​definição​. 
 
 
 
Existe ainda a estrutura ​anônima​:
 
 
Um ​membro ​da estrutura pode ser ​acessado ​usando o operador membro da estruturas​(.)​, chamado ​operador 
ponto​, colocado ​entre o nome da variável estrutura e o nome do membro.  
 
nomeDaVarávelEstrutura.nomeDoMembro 
 
EX: 
 
Nome da variável estrutura: ​a 
Nome do primeiro membro: ​x 
Nome do segundo membro: ​y 
Acessando o membro x da variável estrutura a: ​a. x 
Acessando o membro y da variável estrutura a: ​a. y 
Nome da variável estrutura: ​b 
Nome do primeiro membro: ​x 
Nome do segundo membro​: y 
Acessando o membro x da variável estrutura b: ​b. x 
Acessando o membro y da variável estrutura b: ​b. y 
 
1º método: Atribuindo valores aos membros 
Usando comando de atribuição na hora da declaração das variáveis. Atenção para as chaves e para a sequência 
correta dos dados. 
 
struct  coordenadas 
{ 
   int x, y; 
}; 
. 
. 
. 
coordenadas a={­5, 2}; 
coordenadas b={ 6, 5};   
 
 
 
 
2º método: Atribuindo valores aos membros 
Atribuição na hora da definição/declaração das variáveis 
 
struct  prod 
{ 
   char nomeProd[21]; 
   float valor; 
}produto1={“martelo”, 35.90}, produto2={“furadeira”, 256.75}; 
 
 
 
 
 
 
 
 
 
Neste exemplo, apresentamos uma das grandes vantagens do uso da variável estrutura na programação: a 
facilidade de se atribuir todo o conteúdo de uma variável estrutura a outra variável estrutura. Você deve estar 
lembrado que precisávamos usar ​strcpy ​para copiar vetores de char e comandos de atribuição para as demais 
variáveis.​ ​Usando variável estrutura, com um único comando de atribuição, copiamos todos os conteúdos 
dos membros mesmo que eles sejam vetores de char.​ Observe como teria ficado o programa sem o uso da 
variável estrutura. Imagine se a variável estrutura tivesse 10 membros? 
 
 
 
3º método: Atribuição através da leitura via teclado  
  
struct  prod 
{ 
   char nomeProd[21]; 
   float valor; 
}produto1, produto2; 
 
 
 
EXEMPLOS: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
CONSTRUINDO UM ARRAY DE ESTRUTURA: 
 
1º método 
Da mesma forma que declaramos as estruturas simples, podemos declarar os arrays de estruturas. 
A declaração é feita depois da definição.​ Se a definição for global, a declaração acontece em cada função. 
 
Struct ​<identificador> 
{ 
… 
}; 
<identificador>​ nomeDaVariável; 
Struct ​alCad 
{ 
… 
}; 
alCad ​alunos[15]; 
 
2º método 
A declaração é feita junta com a definição. 
 
Struct ​<identificador> 
{ 
… 
} 
nomeDaVariável; 
Struct ​alCad 
{ 
… 
} 
 ​alunos[15]; 
 
Acessando um elemento do array: 
 
Precisamos ter muito cuidado quando formos acessar um ​array de estruturas​ porque primeiro temos que escolher 
a ​variável do array​ como fazíamos com os​ arrays unidimensionais​. Depois, acrescentamos separado por um 
ponto, os membros da estrutura. 
 
Struct​ prodCad 
{ 
  int​ codigo; 
  ​float ​precoCompra, precoVenda; 
}; 
prodCad produtos[1000]​; 
 
 
 
EXEMPLOS: 
 
Exemplo 1 
Tomando como base o array de estruturas, construa um programa que armazene código e preço de compra de 
1000 produtos, calcule um reajuste de 60% para venda e exiba código, valor de compra e venda. 
Observação:​Para que você pudesse visualizar a entrada e a saída, foi usada a diretiva define que criou a 
constante TAM com valor 3 (deveria ser 1000) 
 
 
 
 
Exemplo 2 
 
Construa um array de estruturas com duas variáveis. O único membro da estrutura é um array de caracter 
(vetor de char) que deverá ser capaz de armazenar até 20 caracteres sem incluir o terminador. Os valores 
deverão ser lidos via teclado. 
 
Na saída, cada letra de cada vetor de char deverá ser exibida em uma linha, sendo que uma linha em branco 
separará as letras dos dois vetores. Além disso, a primeira letra da primeira palavra tem que estar em 
maiúscula mesmo que o usuário não tenha digitado assim. 
 
Na maioria dos exemplos anteriores, já tivemos como membro de uma estrutura, um vetor de char. Além disso, 
estudamos na disciplina de Algoritmos que o vetor de char tem um tratamento diferenciado dos demais vetores 
unidimensionais, pois ele é declarado como um vetor e tratado como uma variável simples exceto quando 
precisamos manipular uma letra de cada vez. Observe a visualização de um vetor de char e as saídas que 
obteremos com os comandos abaixo.​ Atente para os parênteses usados quando desejamos exibir um caracter 
do vetor. 
 
 
 
*** ​Você terá que usar a função ​toupper()​ da biblioteca ​cctype​ ​para converter para maiúscula a primeira letra da 
primeira palavra​. Observe a linha 36 do código fonte. 
 
Você poderá refazer o trecho que exibe uma letra em cada linha, usando a função ​strlen()​ da biblioteca ​cstring​. 
Preferimos controlar usando o terminador ​\0​. 
 
Observe que a estrutura do for não está sendo controlada pela variável ​y​ logo, neste exemplo, está sendo usada 
como se fosse a estrutura ​while​. Experimente trocar pelo trecho abaixo e veja se faz alguma diferença. 
 
 
 
Nosso array só terá dois elementos para que você possa visualizar a saída. Observe a definição/ declaração e a 
visualização do array de estruturas. 
 
 
 
Reforçando os conceitos: 
 
A estrutura criada tem nome : ​cad​. 
A estrutura só tem um membro cujo nome é: ​pal​. 
O nome do ​array ​de estruturas do tipo ​cad ​é: ​palavra​. 
Esse array tem duas ​variáveis estruturas​: ​palavra[0] e palavra[1]. 
Para acessar o único membro da estrutura, a variável ​palavra[0]​ precisa ser unida por um “​.”​  ao membro pal, 
ficando assim: ​palavra[0].pal​. Da mesma forma,  ​palavra[1].pal​.  
Quando usarmos um dos nomes acima com ​cout​, exibirá na tela todo o conteúdo de um dos elementos do vetor. 
Quando desejarmos acessar uma letra de uma das variáveis estruturas, precisaremos usar a seguinte sintaxe: 
 
nomeDoArray[deslocamento array].membro[deslocamento na variável] 
 
Exemplo: 
Se você desejar a terceira letra da segunda palavra: ​palavra[1].pal[2]. 
 
 
 
 
 
 
 
 
Estruturas aninhadas 
 
Muitas vezes, definimos estruturas que podem ser membros de várias estruturas. 
Em qualquer cadastro, por exemplo, tem data: data de nascimento, data de pagamento, data de recebimento, data 
de entrega, etc.  
Sendo assim, poderíamos definir uma estrutura data e visualizá­la da seguinte forma: 
 
 
E usarmos esta estrutura com membro de outra estrutura que iremos definir/declarar e visualizar assim: 
 
 
 
 
Acessando um membro de uma estrutura dentro de um array de estruturas: 
 
nomeDoArrayl[deslocamento no array].nomeDaEstruturaAninhada.membro 
 
Exemplo 
Acessando o dia da variável estrutura de deslocamento 1 = ​promissorias[1].venc.dia 
Vamos construir um programa para armazenar valores nesse array de estruturas aninhadas que declaramos acima. 
 
 
 
 
 
 
 
Na aula passada, estudamos que o uso de funções melhora a legibilidade e a manutenibilidade do programa logo, 
chegou o momento de criarmos funções com/para estruturas. 
Você verá algumas coisas interessantes que poderemos fazer ao construirmos funções com estruturas como por 
exemplo: ​estruturas poderão ser retornos de função, estruturas poderão conter função dentro delas além de 
tudo que já foi feito com os arrays homogêneos.  
 
Passagem por valor 
 
Da mesma forma que passamos o conteúdo de uma variável simples ou de um elemento do vetor, podemos passar 
um membro (campo) de uma estrutura. Vale a pena relembrar que, ​na passagem por valor, passamos uma 
cópia do conteúdo logo, o valor original não se altera​. 
 
Neste exemplo, chamaremos a função três vezes, passando os membros da estrutura de tal maneira que retorne o 
maior dos quatro números. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Passagem por referência  
 
Quando estudamos funções, para quem já tinha visto a linguagem C, notou que a​ passagem por referência 
simplificou o uso da passagem por endereço(ponteiros)​. Por isso, citamos SAADE, Joel(2003, p.112): 
“Pode­se dizer que a passagem por referência é uma forma disfarçada de ponteiro”​. 
 
Neste exemplo, passaremos o endereço de um membro do struct por referência. A função irá calcular a idade da 
pessoa em 2020 e irá alterar o valor do membro. 
 
 
 
 
 
 
 
 
Passagem de um membro que é um vetor ­ passagem por endereço 
 
Os arrays são em verdade, endereços tanto é que o que fica entre parênteses é o deslocamento em relação ao 
endereço base. Sendo assim, a passagem de um membro que é um vetor se dá de mesma forma que os arrays 
unidimensionais.  
 
 
 
 
Perceba que o endereço da estrutura é o mesmo da primeira variável do array de estruturas, pois o primeiro 
elemento do array tem valor 0(zero). E o endereço da segunda variável está distante 31 posições. 
 
Em hexadecimal, 10 equivale em decimal a 16(1*16 + 0) enquanto 2f seria equivalente a 47 (2*16 + 15). e 47 ­ 16 = 
31. 
 
Estrutura como parâmetro de uma função 
 
 
 
 
 
 
Estrutura como valor de retorno de função 
Neste exemplo, apresentaremos uma função do tipo estrutura logo, terá como  retorno,  uma estrutura. 
 
 
 
 
 
Funções como membros de estrutura 
apresentaremos uma estrutura  cujos dois membros são funções. Uma com retorno e outra, sem retorno. 
 
 
 
Já que provamos que o vetor é um endereço, vamos ao exemplo onde passaremos um membro da estrutura 
que é um vetor. 
 
 
 
 
Aula 4: Ordenação e Pesquisa 
 
 
if(vet[0]>vet[1]) 
  { 
    aux=vet[0]; 
    vet[0]=vet[1]; 
    vet[1]=aux; 
  } 
if(strcmp(vet[0],vet[1]) > 0) 
  { 
    strcpy(aux,vet[0]); 
    strcpy(vet[0],vet[1]); 
    strcpy(vet[1],aux); 
} 
 
Cada caracter ocupa um endereço na MP e se pedirmos para exibir o nome de um vetor de char, sairá o primeiro 
endereço de todos os endereços que são ocupados pelo conjunto. Por essa razão, foi criado um conjunto de 
funções para manipularem vetores de  char e nesse nosso estudo, usaremos duas delas: ​strcmp( abreviatura de 
string compare)​ cuja função é comparar dois vetores de char​ e ​strcpy(abreviatura de strng copy)​ ​cuja função é 
copiar o conteúdo de um vetor de char nas posições ocupadas por outro vetor de char​. Essas funções foram 
estudadas na AULA10 da disciplina de Algoritmos. 
 
 
 
Comparando Struct: 
 
if(candidatos[0].ninsc>candidatos[1].ninsc) 
  { 
    aux=candidatos[0]; 
    candidatos[0]=candidatos[1]; 
    candidatos[1]=aux; 
  } 
 
OS MÉTODOS DE ORGANIZAÇÃO 
 
Ordenar significa ​dispor elementos de um conjunto seguindo um determinado critério​. Este critério estará 
baseado em um atributo do elemento do conjunto (nome, matrícula, salário, coeficiente de rendimento, etc.) 
 
ORDENAÇÃO INTERNA E EXTERNA 
 
Quando o método de organização​ utiliza apenas a memória principal​ para realizar o processo de ordenação, é 
classificado como ​ordenação interna​, mas ​se usa uma memória auxiliar porque o arquivo é muito grande​, é 
uma ​ordenação externa​. 
 
MÉTODOS DE ORDENAÇÃO INTERNA 
 
 
 
 
 
 
 
 
SELEÇÃO:INSERÇÃO: 
 
 
 
 
void insercao(int vet[ ], int tam) 
{ 
  int j, i, aux; 
  for ( i=1; i<tam; i++ ) 
  { 
    aux = vet[i]; 
    for ( j=i; j>0 && aux <vet[j­1]; j­­ ) 
      vet[j] = vet[j­1]; 
      vet[j] = aux;   
  } 
} 
 
Observe que ​o for mais externo começa com a segunda posição do vetor porque o for de dentro sempre 
compara com os elementos anteriores​. O teste de ​j>0​ se justifica porque dentro dos colchetes, ele subtrai 
de 1 o valor de j e se deixasse j chegar a zero, o índice ficaria negativo o que não é permitido na linguagem 
C++.​ O elemento fundamental do for interno é o teste: ​j>0 && aux <vet[j­1] ​ porque  incorpora um teste 
interrompendo a repetição quando a condição ​aux <vet[j­1]​ não for mais atendida. O for usado desta forma 
é uma herança da linguagem C e talvez mais fácil de ser construído do que a estrutura do while. Nada 
contra a estrutura do while, mas como já havia dito, tentamos manter uma uniformidade na apresentação 
desses métodos. 
 
 
BOLHA: 
 
VALORES ADJACENTES SÃO COMPARADOS DE FORMA CONTÍNUA DANDO A IMPRESSÃO DE UM 
BORBULHAMENTO. 
 
 
 
 
void bolha(int vet[ ], int tam) 
{ 
  int j,i, aux; 
  for (i=0; i<tam ­1; i++) 
   for(j=tam­1; j>i; j­­) 
    if(vet[j] < vet[j­1] ) 
    {   
         aux=vet[j]; 
         vet[j]= vet[j­1]; 
         vet[j­1]=aux;   
     } 
} 
 
 
SELEÇÃO: 
Ideal para arquivos pequenos. 
Muito simples. 
Não melhora sua performance se 
o arquivo já estiver ordenado. 
Tem menos movimentos do que 
o Insertion Sort. 
INSERÇÃO: 
Só ordena quando necessário. 
Quando um elemento é inserido, 
todos os elementos maiores do 
que ele, são deslocados para a 
direita. 
É considerado o melhor dos três 
métodos estudados. 
BOLHA: 
É o mais conhecido método. 
É muito simples. 
Muito lento. 
É considerado o pior dos três 
estudados. 
 
 
 
SELEÇÃO: 
 
 
 
 
 
 
 
 
 
 
 
 
INSERÇÃO: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
BOLHA: 
 
 
PESQUISA SEQUENCIAL: 
 
PRIMEIRO TRECHO:  SEGUNDO TRECHO: 
cout<<"\n...? "; 
cin>>varProcura; 
achou=0; 
for(L=0;L<tamLinha;L++) 
{ 
  if(varProcura==vetor[L]) 
  { 
   achou=1;  posicao=L; 
  }   
} 
if(achou==1) 
 cout<<"\n...: "<<outroVetor[posicao]<<endl; 
else 
 cout<<"\nDado nao achado\n"; 
cout<<"\n...? "; 
cin>>varProcura; 
achou=0; 
for(L=0;L<tamLinha && achou==0;L++) 
{ 
  if(varProcura==vetor[L]) 
  { 
   achou=1;  posicao=L; 
  }   
} 
if(achou==1) 
 cout<<"\n...: "<<outroVetor[posicao]<<endl; 
else 
 cout<<"\nDado nao achado\n"; 
Esse trecho fará uma varredura em toda a 
matriz e mesmo depois de achar, continuará 
até o fim. 
Para melhorar o trecho anterior, vamos 
introduzir um teste da estrututra ​for​, assim 
que o elemento for achado o ​for​ será 
interrompido. 
 
 
 
TRECHO DA PESQUISA BINÁRIA: 
 
inicio=0; 
fim= tamanho ­ 1; 
meio=(inicio+fim)/2; 
while(procura != nomeVetor[meio] && inicio != fim) 
{ 
  if(procura > nomeVetor[meio])   
   inicio=meio+1; 
  else 
   fim=meio; 
  meio=(inicio+fim)/2;   
} 
if(nomeVetor[meio]==procura) 
 cout<<"\n....: "<<outroVetor[meio]<<endl; 
else 
 cout<<"\nDado nao encontrado\n"; 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
AULA 5 ­ A ESTRUTURA DE DADOS ­ LISTAS 
 
“A estrutura que permite representar um ​conjunto de dados​ de forma a ​preservar a relação de ordem 
linear​ (ou total) entre eles é a lista linear. Uma lista linear é composta de ​nós​, os quais podem conter, 
cada um deles, um ​dado primitivo​ ou um ​dado composto​.” 
                                                                         (VELOSO,P.,SANTOS,C., AZEREDO,P., FURTADO, A., 1983,79) 
 
Nó ​ou ​nodo ​– é um item da lista. 
Comprimento ou  tamanho de uma lista – números de nós de uma LISTA. Exemplo de uma LISTA de comprimento 
10 porque tem 10 nós. 
Se “uma Lista é composta de nós” então, uma Lista Vazia é uma lista que não tem nós. 
 
Os elementos de uma ​lista linear​ podem ser agrupados de duas formas: 
 
Sequencial​: 
          
 
Esse tipo de estrutura apresenta os ​nós ​em posições ​contíguas ​de memória, isto é, um após o outro como já 
vimos quando estudamos matrizes na disciplina de Algoritmos. Sendo assim, fica fácil identificarmos o endereço de 
qualquer nó de uma Lista Sequencial. 
 
• Vantagens  
– Qualquer elemento da lista pode ser acessado direto indexado. 
– Tempo constante para acesso a qualquer elemento da lista. 
 
• Desvantagem 
– Movimentação de todos os elementos da lista quando há uma inserção ou remoção de elemento. 
– O tamanho máximo da lista deve ser pré­estimado. 
 
 
Encadeado​: 
 
Um conjunto de nós (nodos) encadeados onde cada nó contém o ​dado ​e um ​apontamento ​para o ​próximo nó​, 
visto que eles não estão alocados de forma contígua. 
 
 
 
• Vantagens  
– Facilidade de inserir ou remover um elemento em qualquer ponto da lista.  
– Não há a necessidade de movimentar os elementos da lista quando há uma inserção ou remoção de 
elemento. 
• Desvantagem 
– Por utilizar ponteiros, a implementação deve ser feita com muito cuidado para que não ocorra um mal 
encadeamento (ligação) dos nós e consequentemente a lista seja perdida. 
– Encontrar um determinado elemento na posição n da lista é necessário percorrer os n­1 anteriores. 
– Necessidade de memória extra para armazenamento dos ponteiros. 
 
Esta classificação diz respeito à forma como os dados são armazenados na Memória Principal. Entretanto, não 
pode ser confundido com Alocação Estática ou Alocação Dinâmica. 
Alocação Estática é determinada durante a compilação. Já na Alocação Dinâmica, você poderá determinar o 
tamanho, ou acrescentar, durante a execução. 
Reunindo estas classificações, podemos concluir que existem quatro possibilidades de Alocação de Memória. 
 
 
 
A Lista Linear Sequencial é ideal para um ​conjunto pequeno de dados​. Apresenta a vantagem do acesso ao nó 
pelo índice e a desvantagem da movimentação quando se remove dado e insere se desejarmos deixar os vazios ao 
final. 
A forma de acesso à LISTA no que diz respeito à inserção e à remoção de um dado determina uma classificação 
 
 
 
Pilha ­ A inserção e a remoção é sempre realizada em um extremo da lista. 
Fila – A inserção é feita em um extremo e a remoção em outro. 
Fila Dupla – DEQUE( Double­Ended QUEue), significando fila de extremidade dupla. 
FDER – Fila Dupla de Entrada Restrita – Nesse tipo de Fila, a remoção do elemento pode acontecer em 
qualquer extremidade, mas a inserção, em apenas uma. 
FDSR  – Fila Dupla de Saida Restrita – Nesse tipo de Fila, a inserção do elemento pode acontecer em 
qualquer extremidade, mas a recuperação, em apenas uma. 
 
Inicializar uma lista é atribuir zero à variável​ que será responsável por ​armazenar a quantidade de dados​ que 
já se encontram na lista. 
 
 
OPERAÇÕES BÁSICAS COM LISTAS SEQUENCIAIS 
 
• Criar: 
• Verificar lista vazia: 
• Verificar lista cheia: 
• Inserir:  
• Alterar:  
• Remover:  
• Buscar: 
• Exibir a quantidade: 
• Combinar: 
• Dividir lista: 
• Ordenar:  
• Esvaziar: 
 
EXEMPLOS 
 
 
 
 
APLICAÇÃO: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
APLICAÇÃO: 
#include <iostream> 
using namespace std; 
void insere(int IDS[ ], int idade, int &t, int tamanho); 
void exibe(int IDS[ ], int t); 
void selecao(int IDS[ ], int t); 
void frequencias(int IDS[ ], int t); 
 
int main() 
{ 
  int tam, op, f3=0, idades[10], id; 
 ​ //Inicialização  
    tam = 0;  
 do 
 { 
  system("cls"); 
  cout<<"\nMenu 2 ­ LISTA \n";  
  cout<<"\n0­ Reinicar a LISTA";   
  cout<<"\n1­ Inserir idade na lista"; 
  cout<<"\n2­ Exibir lista"; 
  cout<<"\n3­ Ordenar lista";cout<<"\n4­ Exibe frequencia"; 
  cout<<"\n5­ Sair"; 
  cout<<"\nOpcao: "; 
  cin>>op; 
  system("cls"); 
  switch(op) 
  { 
   case 0:  ​//reinicialiação  
            tam = 0;   
            break;   
   case 1: 
         cout << "\nDigite idade(10­19) a ser inserida na Lista: "; 
         cin >> id;  
         while(id<10 || id >19) 
         { 
           cout<<"\nAtencao para o intervalo."; 
           cout<<"Digite idade(10­19) a ser inserida na Lista: "; 
           cin>>id; 
         }   
         insere(idades,id,tam, 10);  
         break; 
 
   case 2: exibe(idades,tam);  
           break; 
 
   case 3: ​//ordena Metodo selecao poderia ser insercao ou bolha 
           selecao(idades, tam); 
           f3=1; 
           break; 
 
   case 4:if(f3==1) 
          frequencias(idades,tam);   
          else 
           cout<<"\nOrdene primeiro o vetor\n";  
          break;   
 
   case 5: cout<<"\nFinalizando o programa da LISTA\n"; 
           break; 
   
   default: cout<<"\nOpcao invalida\n"; 
  }   
  cout<<"\n\n"; system("pause"); 
 }while(op !=5); 
} 
  
void insere(int IDS[ ], int idade, int &t, int tamanho) 
{ 
   if (tamanho == t) 
    cout << "\nAtencao! Lista cheia\n"; 
 else 
 { 
    IDS[t] = idade; 
     t++; 
 } 
}   
  
void exibe(int IDS[ ], int t) 
{ 
   int x; 
   if (t == 0) 
    cout << "\nAtencao! Lista vazia\n"; 
  else 
    for(x = 0; x < t; x++) 
      cout << "\n" << IDS[x]; 
} 
 
void selecao(int IDS[ ], int t) 
{int i, j, menor, temp; 
  if (t == 0) 
    cout << "\nAtencao! Lista vazia\n"; 
 else 
 { for(i=0; i<t ­1; i++) 
   { 
    menor=i; 
    for(j=i+1; j<t ; j++) 
 if(IDS[j] < IDS[menor]) 
  menor=j; 
temp=IDS[i]; 
IDS[i]=IDS[menor]; 
IDS[menor]=temp; 
   } 
  } 
  cout<<"\nLista Ordenada\n"; 
}   
 
void frequencias(int IDS[ ], int t) 
{ 
  int i, c, frequencia[ ]={0,0,0,0,0,0,0,0,0,0}; 
  if (t == 0) 
    cout << "\nAtencao! Lista vazia\n"; 
  else 
  {   
    for(i=0;i<t;i++) 
    {  frequencia[IDS[i]­10]++; 
       cout<<"\n"<<IDS[i]<<"\t"<< frequencia[IDS[i]­10]; ​//SÓ PARA FINS DIDÁTICOS 
    } 
   ​ // exibe frequência dos números sem repetição 
    cout<<"\n\nIdade\tFrequencia\n"; 
    cout<<"\n"<<IDS[0]<<"\t"<< frequencia[IDS[0]­10]; 
    for(i=1; i<t; i++) 
    if (IDS[i] != IDS[i­1] ) 
      cout<<"\n"<<IDS[i]<<"\t"<< frequencia[IDS[i]­10]; 
  } 
} 
 
 
 
 
 
 
 
 
APLICAÇÃO: 
 
 
 
 
 
 
 
 
 
 
 
 
ESTRUTURAS HOMOGÊNEAS ­ CRIAR 
 
 
ESTRUTURAS HOMOGÊNEAS ­ INSERIR 
 
 
 
 
 
 
ESTRUTURAS HOMOGÊNEAS ­ INSERIR EM UMA POSIÇÃO DETERMINADA  
 
 
ESTRUTURAS HOMOGÊNEAS ­ EXIBIR TODA A LISTA 
 
 
 
 
 
 
 
 
 
 
 
 
 
PESQUISAR UM DETERMINADO ELEMENTO E RETORNAR SUA POSIÇÃO 
 
 
REMOVER UM ELEMENTO EM UMA POSIÇÃO DETERMINADA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ESTRUTURA HETEROGÊNEA ­ CRIAR 
 
 
ESTRUTURA HETEROGÊNEA ­ INSERIR 
 
 
INSERIR UM ELEMENTO EM UMA POSIÇÃO DETERMINADA 
 
 
 
 
 
ESTRUTURAS HETEROGÊNEAS ­ EXIBIR TODA A​ LISTA 
 
 
PESQUISAR UM DETERMINADO ELEMENTO E RETORNAR SUA POSIÇÃO 
 
 
 
REMOVER UM ELEMENTO EM UMA POSIÇÃO DETERMINADA 
 
 
 
 
 
Aula 6: A Estrutura de Dados –​ Pilha 
 
Nesta aula, estudaremos a Pilha uma das mais simples Estruturas de Dados, mas com muitas aplicações. 
Lendo a definição acima, podemos concluir que ​a remoção do elemento acontece num processo inverso ao da 
inserção, isto é, o último a entrar é o primeiro a sair​.  Este critério que determina a sequência de entrada e 
saída desta forma, chama­se ​LIFO( Last In First Out)​. 
Observe a figura abaixo: 
 
Você percebe que o número 30 foi o último a entrar na Pilha e passa a se posicionar no topo. Na remoção, o 
número 30 é o primeiro a sair. 
Uma das características da Pilha é que a ​inserção​, ​remoção ​e ​acesso ​acontecem ​somente em uma 
extremidade​ como você pode observar na figura. Normalmente, apresento o vetor como uma matriz linha, mas 
para deixar mais parecido com uma Pilha, apresentei­o como matriz coluna e ainda dei um giro de 180º. Tudo pelo 
“bem da Pilha”.  
 
O número de operações que pode ser realizado com uma Pilha é muito pequeno, tendo em vista o critério LIFO.  
Três operações são consideradas básicas e, vou colocá­las no início, mas as demais também são necessárias para 
que as primeiras possam funcionar perfeitamente ou para fornecer alguma informação.  
 
Inicializa() ou Init()  Inicializa a Pilha 
Empilhar() ou Push()  Insere no topo da Pilha um elemento 
Desempilhar() ou Pop()  Remove do topo da Pilha um elemento 
acessoTopo() ou Top()  Tem acesso ao elemento que se encontra no topo da Pilha 
verificaPilhCheia() ou isFull()  Verifica se Pilha está cheia 
verificaPilhVazia() ou isEmpty()  Verifica se Pilha está vazia 
 
Muitos autores não destacam as três últimas operações porque, normalmente, elas estão embutidas nas demais 
ou, se não estiverem, um comando ​if​, ou de ​atribuição​, pode resolver o problema. 
Nós vamos construir trechos para uma Pilha que poderá armazenar até 5 números inteiros. 
Estarei apresentando, quando existir, o trecho que chama a função e a função. 
 
INICIALIZAR 
A inicialização da Pilha irá se resumir a um comando de ​atribuição​, preparando­a para receber os elementos que 
serão inseridos.  
Como na Pilha, o topo, isto é, ​a posição mais alta da Pilha é de maior importância​, uma variável sempre deverá 
conter este valor. Sendo assim,​ para inicializar uma Pilha, precisaremos colocar um valor que não seja possível ser 
índice de vetor na linguagem C++​. 
Gostaria de enfatizar que a inicialização não significa zerar todos os elementos da Pilha, mas é como se 
deixássemos engatilhado um ponteiro que seria acionado assim que o primeiro valor entrasse na pilha. 
Em programação, usamos uma variável e a inicialização foi feita na declaração. Observe o trecho: 
 
EMPILHAR (PUSH) 
Esta é uma operação básica da Pilha. ​Para que possa ser empilhado um elemento, é preciso testar se existe 
lugar na Pilha​. 
Verificar se a Pilha está cheia poderia ser feito em separado, mas preferi fazer junto, pois se resume a um ​if​, 
tornando­se mais rápido do que chamar uma função. 
Além disso, uma chamada de função implica em colocar o endereço da instrução seguinte em uma Pilha para que o 
retorno seja possível e, se a função for algo muito simples, talvez não valha a pena ser criada. Foi assim que 
pensei e por essa razão reuni duas operações nesta função. Observe. 
 
>>>​ A função recebe o endereço do vetor, o endereço da variável que contém a posição do elemento que se 
encontra no topo e o valor a ser inserido​. 
Os dois primeiros parâmetros precisam ter seus endereços passados porque serão alterados dentro da função​. 
Observe que antes de inserir na Pilha, a variável ​t​ é incrementada porque o topo passa a ser o valor que será 
inserido na instrução abaixo. É uma função de fácil implementação. 
 
Acompanhe agora, na figura abaixo, supondo que você digitou cinco números para serem empilhados. 
 
 
DESEMPILHAR (POP) 
Esta é outra operação básica da Pilha.​ Para que possa ser desempilhado um elemento, é preciso testar se a 
Pilha não está vazia​. 
Verificar se a Pilha está vazia poderia ser feito em separado, mas preferi fazer junto, pois se resume a um ​if​, 
tornando­se mais rápido do que chamar uma função. Esta função é do tipo ​int​, mas poderia ser do tipo ​void​. 
 
>>>​ ​A função recebe o endereço do vetor, o endereço da variável que contém a posição do elemento que se 
encontra no topo e o endereço da variável que vai receber o valor que será “desempilhado”. 
Todos os parâmetros precisam ter seus endereços passados porque serão alterados dentro da função. 
Observe que depois de copiar o conteúdo do elemento que estava notopo da Pilha, a variável t é decrementada.  
Em nenhum momento foi removido o valor que estava armazenado na posição. Só o topo que se deslocou.  
Sanou sua dúvida agora? Assim como a função empilhar, a função desempilhar é de fácil implementação e bem 
parecida. 
 
Acompanhe a agora, na figura abaixo, supondo que você escolheu desempilhar cinco números. 
 
 
ACESSO AO TOPO (TOP) 
A única posição que poderá ser acessada na Pilha é a que está no topo da Pilha​. Esta é uma função que possibilita 
que você visualize o elemento do topo sem “removê­lo”. 
Na verdade, você não precisaria criar esta função tal sua simplicidade. Poderia simplesmente colocar no case. Só 
criei para modularizar todos os casos. 
 
 
acesso topo(pilha, topo);  
 
void acessoTopo(int p[ ], int &t) 
{ 
  if(t == ­1) 
     cout<<’\nATENCAO. Pilha Vazia\n”; 
  else 
     cout<<”\nElemento do topo da PILHA: “<< p[t]; 
 
Esta função testa se a Pilha está cheia ou se a Pilha está vazia e, se não for nenhuma das duas opções, exibirá o 
total de elementos na Pilha e o espaço disponível. 
Você poderá escolher qual dos dois desejará exibir. 
 
Como todas as seis operações já foram apresentadas, vou apresentar mais uma. Nada importante, mas que poderá 
ser útil em algum momento. 
Assim como a função anterior, você não precisaria criá­la. 
 
situacaoPilha(pilha, topo); 
 
void situacaoPilha(int p[ ], int &t) 
{ 
  ​if(t == ­1) 
     cout<<’\nATENCAO. Pilha Vazia\n”; 
  else if(t == TAM)  
             cout<<”\nATENCAO. Pilha Cheia\n”; 
  else 
        { 
          cout<<”\nTotal de elementos na pilha: “<<t + 1<<\n”; 
          cout<<”\n\nEspaco disponivel na pilha: “<<TAM ­ (t+1)<<”\n”; 
        } 
} 
 
Depois de termos entendido o conceito de empilhar e desempilhar, acredito que seja mais fácil perceber a presença 
do uso desta estrutura de dados em várias aplicações. 
 
­ Histórico de páginas visitadas num navegador. 
­ Sequencia de desfazer em vários softwares, o famoso atalho Ctrl Z. 
­ Implementação de recursividade (a torre de Hanói que vimos na disciplina de Algoritmos). 
­ A cadeia de chamadas de funções num programa. 
­ Avaliação de expressões aritméticas. 
­ Conversão de Decimal para Binário, etc. 
 
Na aritmética, estamos acostumados com a notação ​infixa ​onde o operador é colocado ​entre ​dois operandos. 
Esta notação é problemática, pois requer conhecimento da hierarquia das operações, obrigando o uso dos 
parênteses para sobrepor esta hierarquia quando necessário. 
Existem duas outras notações, a ​prefixa ​e a ​posfixa​. 
Na notação prefixa(notação polonesa), o operador antecede os operandos enquanto que na notação posfixa 
(notação polonesa reversa),  os operandos antecedem o operador. A grande vantagem dessas notações é que elas 
não precisam de parênteses. 
 
 
Procure, a partir da esquerda para direita, colocar os operandos na ordem em que aparecem na expressão.  
Quanto aos operadores, eles devem estar depois dos seus operandos. 
Observe a expressão deste exemplo: tem duas operações onde a primeira tem hierarquia maior do que a segunda 
logo, a operação 4 * 3 é executada primeiro: 
Depois, o resultado será o primeiro operando da segunda operação.  
Observe a tabela abaixo. 
 
>>>​ ​Muita atenção. Algumas vezes, você poderá ter dois operadores juntos, pois tudo dependerá do número de 
operandos e da hierarquia das operações. Fique ligado. 
 
 
Neste exemplo, temos três operações. Duas delas têm a mesma hierarquia. Acompanhe no quadro como você 
deverá colocar esta expressão na notação posfixa. 
 
 
 
 
 
 
APLICAÇÕES VIDE ARQUIVO PDF DA 6ª AULA! 
 
ESTRUTURA DE DADOS ­ ​PILHA​ POR CONTIGUIDADE 
 
 
OPERAÇÕES MAIS COMUNS 
 
• Criar: ​cria uma pilha vazia. 
• Empilhar: ​insere um novo elemento no topo da pilha.  
• Desempilhar: ​remove um elemento do topo da pilha. 
• Exibir topo ou a quantidade​: 
• Esvaziar​: esvazia todos os elementos da pilha. 
 
PILHA ­ CRIAR 
 
 
PILHA ­ EMPILHAR (PUSH) 
 
 
 
EXIBIR O TOPO DA PILHA (STACKTOP) 
 
 
PILHA ­ EXIBIR TODA A PILHA (POP) 
  
 
PILHA ­ DESEMPILHAR 
 
 
 
 
 
EXEMPLO 
 
CRIAR UMA ESTRUTURA DE DADOS PARA A FICHA A SEGUIR: 
 
 
 
Aula 7: A Estrutura de Dados – ​Fila 
 
“Uma fila é um tipo especial de Lista Linear em que as inserções são realizadas num extremo, ficando as 
remoções restritas ao outro. O extremo onde os elementos são inseridos é denominado final da fila, e 
aquele de onde são removidos é denominado começo da fila.”    (PEREIRA, Silvio. L., 2004, p. 57) 
 
A Fila, assim como a Pilha, também é um caso particular de Lista Linear e se diferencia dela pela forma de acesso 
porque a inserção sempre acontece em uma extremidade e a remoção, em outra.  
 
O conceito da Fila na programação tem a mesma filosofia que a fila do mundo real onde o primeiro que chega é o 
primeiro a ser atendido. Este método é conhecido como ​First In, First Out(FIFO)​. 
 
 
A operação enqueue só poderá ser realizada se a fila não estiver cheia assim como a operação dequeue, se não 
estiver vazia. Percebe­se então que, pelo menos, mais duas operações serão necessárias.  
 
>>> Overflow ​na ​fila ​– Quando se ​deseja inserir um elemento, mas a fila está cheia​. Trecho de proteção evita 
este problema. 
 
Underflow ​na ​fila ​­ Quando se ​deseja remover um elemento, mas a fila está vazia​. Trecho de proteção evita 
este problema. 
 
As filas possuem uma operação semelhante a de uma pilha. A seguir, apresentaremos os nomes pelos quais elas 
são reconhecidas, porém,você pode usar outra nomenclatura para as funções que criar em seus programas: 
 
 
IMPLEMENTAÇÃO 
A implementação de filas pode ser feita por arrays (matrizes) ou ponteiros, mas, nesta aula, porque ainda não 
tivemos a oportunidade de estudarmos ponteiros, implementaremos com matrizes e structs. 
A vantagem de começarmos usando matriz é sua fácil implementação, mas temos que ter consciência das 
desvantagens, uma vez que, na alocação estática, precisaremos definir um espaço suficientemente grande para 
armazenar um grande volume de dados. Além disso, indicadores de inicio e fim da fila. 
Os indicadores serão variáveis que sinalizarão o estado da Fila em relação à possibilidade, ou não, da inserção de 
novos elementos. 
O indicador de fim de Fila será incrementado toda vez que um elemento é inserido na Fila, enquanto que o 
Indicador de início de Fila será incrementado quando um elemento for removido, sendo este um grande problema 
porque, após sucessivas remoções, teremos uma Fila com vários nodos disponíveis no início, mas que não 
poderão ser ocupados. 
 
Este problema será resolvido na aula de hoje quando conseguirmos visualizar o array de forma circular, mas vamos 
dar um passo de cada vez  
porque precisamos primeiro entender as operações básicas da Fila. 
Nós vamos construir trechos para uma Fila que poderá armazenar até 5 números inteiros. 
Estarei apresentando, quando existir, o trecho que chama a função e a função. 
Antes de apresentar as operações básicas, gostaria de mostrar a variável estrutura que foi criada para trabalhar 
com a Fila. 
Como no estudo da estrutura Pilha usei uma matriz e uma variável simples, achei que seria mais produtivo 
implementar com variável estrutura que apresento abaixo. 
 
 
INICIALIZAR 
A inicialização da Fila irá se resumir a comandos de atribuição, preparando­a para receber os elementos que serão 
inseridos.  
Na Fila, os dois extremos são importantes e, por esta razão, estaremos trabalhando com duas variáveis. Sendo 
assim, para inicializar uma Fila, precisaremos atribuir valores a essas duas variáveis. 
Não se preocupe porque não inicializarei da mesma forma nos exemplos para que você não ache que só existe 
uma maneira. 
  
Assim como na Pilha, inicializar não significa zerar todos os elementos da  Fila.  
Neste exemplo,​fila.fim​ foi inicializada com ​–1 ​porque é comum você encontrar assim com a justificativa que em um 
primeiro momento ​fila.inicio​ seria igual a ​fila.fim​, mas se você fizer os teste de fila vazia e fila cheia de forma 
correta, não tem problema começar por 0 as duas varáveis. 
 
//inicializa a fila 
  ​fila.inicio = 0; 
  fila.fim = ­1; 
 
EFILEIRAR(ENQUEUE) 
Esta é uma operação básica da Fila. Para que possa ser enfileirado um elemento, é preciso testar se existe lugar 
na Fila. 
Verificar se a Fila está cheia poderia ser feito em separado, mas, assim como fiz na Pilha, resolvi fazer neste 
trecho. 
 
enfileira(fila); 
 
 
 
>>> ​A função recebe, por referência, o endereço da variável estrutura e como todas as variáveis necessárias, 
inclusive o vetor, são membros da estruturas, tudo e passado de uma só vez, aumentando a legibilidade. 
Começa testando se a Fila está cheia e, se não estiver, o valor é solicitado, ​fil.fim​ é incrementado e o valor 
armazenado na Fila. É uma função de fácil implementação. 
 
Acompanhe agora, na figura abaixo, supondo que você digitou cinco números para serem enfileirados. 
 
 
DESENFILEIRAR(DEQUEUE) 
Esta é outra operação básica da Fila. Para que possa ser desenfileirado um elemento, é preciso testar se a Fila não 
está vazia. 
 
desenfileirar(fila); 
 
 
 
A função recebe, por referência, o endereço da variável estrutura cujo um dos membros contem a posição do 
elemento a ser “desenfileirado”. 
 
>>>​ Observe que depois de exibir o conteúdo do elemento que era o primeiro da Fila, a variável fil.inicio é 
incrementada.  
Em nenhum momento foi removido o valor que estava armazenado na posição. Só o início que se deslocou para a 
direita. Assim como a função enfileirar, a função de desenfileirar é de fácil implementação e bem parecida. 
 
Acompanhe a agora, na figura abaixo, supondo que você escolheu desempilhar cinco números. 
 
 
primeiro elemento (firstElem) 
Esta é uma função que possibilita que seja visualizado o primeiro elemento da Fila sem “removê­lo”. Na verdade, 
você não precisaria criar esta função tal sua simplicidade. Poderia simplesmente colocar no case. Só criei para 
modularizar todos os casos. 
elemPrimeiro(fila); 
situacaoFila(fila); 
 
 
>>>​ Esta função testa se a fila está vazia, se não estiver, exibirá vários dados sobre ela a fim de que você possa 
acompanhar melhor a execução do programa. Preste bem atenção às funções apresentadas e você verá que elas 
são muito diferentes das que operam a pilha, afinal, ambas as estruturas são casos particulares da Lista Linear.  
 
Aplicações com Filas 
 
As Filas têm muitas aplicações e acho que todos concordam que o uso mais comum seja em Sistemas 
Operacionais. 
Alguns exemplos: 
 
­ Fila de arquivos para impressão 
­ Atendimento de processos requisitados a um sistema operacional. 
­ Buffer para gravação de dados em mídia. 
­ O tratamento do armazenamento das teclas que estão sendo digitadas antes da tecla enter ser pressionada. 
 
UMA APLICAÇÃO ­ O PROGRAMA DA AGENDA 
O programa que será apresentado a seguir é uma adaptação do código fonte do livro C Completo e Total de 
Herbert Schildt, cujo site está indicado no Aprenda Mais desta aula para que você faça o download dos códigos. É 
um livro clássico e, nesta aula, selecionei dois programas dele.  
Evidentemente, algumas modificações foram necessárias porque os códigos estavam escritos na linguagem C e 
usavam matriz de ponteiros assunto que será estudado na próxima aula. 
Para este exemplo, mais uma vez, considerei uma matriz de 5 elementos para que você possa entender o 
funcionamento da aplicação. 
 
 
  
 
 
Este programa da Agenda de Compromissos é uma boa aplicação para Fila, principalmente, para quem está 
começando. 
Ele será adaptado, nesta aula para Fila circular onde será resolvido o problema dos espaços ociosos à medida que 
os elementos vão sendo “removidos”. 
 
FILA CIRCULAR 
Para resolvermos o problema do espaço ocioso, o ideal seria que a última posição antecedesse à primeira e, se 
pegássemos um pedaço de barbante e uníssemos suas pontas sobre uma mesa, perceberíamos que ela se 
fecharia em uma curva. 
 
 
 
Enfileirar (enqueue) 
 
entra(fila); 
 
 
>>>​ ​A função começa testando a variável ​fil.total​ para verificar se seu valor é igual ao máximo.  
Caso não seja, o valor é solicitado e inserido na Fila. Depois, a variável ​fil.final​ é incrementada e testada. Se atingir 
o valor final, será reinicializada. Lembre­se de que ela começou com zero. 
A variável ​fil.total​ é incrementada e, na próxima vez que se tentar inserir um elemento, a mensagem Atencao. Fila 
Cheia, irá aparecer até que um elemento seja removido. 
 
Desenfileirar (dequeue) 
 
deleta(fila) 
 
>>> ​Esta função também começa testando a variável ​fil​.​total​ para verificar se a Fila está vazia. 
A variável ​fil.inicio​ é incrementada porque um elemento foi removido e ​fil.total​, decrementada. 
Já falei nesta aula, que o trecho de remoção, não estava removendo valor da Fila, mas neste exemplo, resolvi,  
toda vez que fosse removido um elemento, atribuir o valor ​–999​ para que pudesse, no próximo trecho, listar os  
elementos da Lista Circular para aqueles que dizem:”Só acredito vendo! 
Não é para fazer disso um hábito, mas nunca se sabe se um dia você pode precisar usar algo parecido, não é?  
Meu objetivo foi didático. 
 
Função Lista  
Somente a primeira linha de código do ​else​ seria necessária para esta função. Todo o conjunto de comando foi 
acrescido para fins didáticos, visto que fica muito difícil visualizar, num primeiro momento, o comportamento da Fila 
Circular. Foi por esta razão que no trecho de remoção que atribui ​–999​ à posição quando era “removido” um 
elemento.  
 
lista(fila) 
 
 
 
 
 
 
 
 
 
 
 
 
 
Aula 8: Alocação Dinâmica / Listas Encadeadas ­ Introdução 
 
Alocação Dinâmica  
Durante todo esse tempo que estamos estudando Algoritmos e Estruturas de Dados, temos determinado quanto de 
memória nossos programas vão usar através das declarações que fazemos das variáveis locais, globais, matrizes, 
sejam elas de tipos primitivos ou de structs. 
Muitas vezes, sentimos necessidade de determinar durante a execução do programa a  
quantidade de elementos de uma matriz unidimensional, por exemplo, mas, ou nós superdimensionávamos 
alocando mais do que iria ser usado para que o usuário pudesse entrar com “qualquer valor(?)”, ou não 
conseguíamos fazer o que queríamos.  
 
A alocação dinâmica de memória vem suprir essa deficiência e possibilitar a criação de tipos de  
dados e estruturas de qualquer tamanho durante a execução do programa.  
Sabemos que durante a execução de um programa, o Sistema Operacional, ​aloca espaço na Memória Principal 
para as variáveis locais e globais, ​outro espaço é alocado para armazenar o código do programa​, outro espaço 
para armazenamento das funções​ e o ​que sobra, é chamado de Área de memória Livre(free store) ou Heap 
que é ​usada para alocação dinâmica de memória​.É bom frisar que a área da Pilha cresce em direção ao Heap e 
o Heap, em direção à área da Pilha. 
 
 
“ Embora a disposição física exata de cada uma das quatro regiões possa diferir entre tipos de CPU e 
implementações...” 
 
Operadores ​new ​e  ​delete 
  
Na linguagem C++, alocar dinamicamente é relativamente simples porque temos somente dois operadores para 
alocar e desalocar memória.  Entretanto, é imprescindível o conhecimento sobre ponteiros. 
   
Operador new 
Sua  função é fazer alocação dinâmica de memória, retornando o endereço inicial do bloco alocado. 
Você poderá alocar espaço para armazenar um dado ou um ​conjunto de dados(array)​. 
Se você foi alocar para armazenar um dado, deverá fazê­lo com ​new​, nas se for para armazenar um ​array​, use  
new[ ] 
 
Operador delete 
Sua função é retornarpara a área de memória livre o espaço que foi alocado dinamicamente. 
Se você for retornar uma área que estava armazenando um valor, deverá ​delete​, mas se for um array, use ​delete[ ] 
 
 
 
Só usarmos esse operador não no dará garantia de que tudo ocorrerá sem problema com afirma 
DROZDEK, A(2002, p.10) 
Se depois de emitirmos a declaração delete não apagarmos o endereço da variável ponteiro que participa 
da supressão do bloco de memória, o resultado é potencialmente perigoso e podemos fazer o programa 
entrar em colapso quando tentarmos acessar locais inexistentes, particularmente para objetos mais 
complexos do que valores numéricos. Isso que se chama de problema de referência pendente(grifo 
nosso). “ 
Uma das formas de se fazer isso, é atribuir 0(zero) à variável ponteiro para que a variável ponteiro se 
torne nula.   
 
Alocar e desalocar memória poderão trazer alguns problemas para a programação. Vamos entender melhor isso. 
Quando  desalocamos, uma porção da memória fica livre e, à medida que continuamos fazendo mais deslocações, 
poderemos ficar com uma área  de memória livre razoável mas que não poderá ser alocada porque está 
fragmentada e, não poderá ser feita uma alocação de um bloco de forma não contígua. 
 
A ​MP(Memória Principal) ​consiste de trilhões de posições para armazenamento do Sistema Operacional, dados, 
programas, etc. Seu tamanho depende de quanto sua placa mãe suporta porque se foi o tempo em que o dinheiro 
era o principal fator para se aumentar a memória, visto que hoje em dia ela está relativamente barata.  
Nós já vimos que, ao declararmos uma variável nas linguagens de alto nível e de nível intermediário, o "nome" dado 
é associado a uma posição de memória (endereço). Este tipo de variável que nós conhecemos, armazena dado.   
Hoje vamos conhecer a variável ponteiro. Esta é uma variável que armazena o endereço de outra variável, 
possibilitando receber o endereço que é retornado quando se aloca a memória dinamicamente. 
 
Declaração de uma variável ponteiro: 
 
tipo *nomeDaVariávelPonteiro; 
 
­ tipo: 
 
 
­ O “ * ” é o caractere ou operador que sinaliza que a variável está sendo declarada como ponteiro. 
­ O operador “ & “ será usado antes de uma variável quando quisermoso endereço da variável e não, 
seu conteúdo. 
­ inicialização 
 
 
Ponteiros para Estruturas 
 
Nada nos impede de passarmos uma estrutura para uma função, entretanto isso sobrecarrega a pilha, aumentando 
o tempo de transferência dos dados entre as funções.   
Para minimizar esse problema e tendo em vista que já estudamos funções, vamos aprender agora como passar 
somente um ponteiro como argumento para função, e, através dele, o endereço da estrutura.  
Saibam também que será de muita utilidade nas próximas aulas. 
  
Existem duas formas de se acessar o membro através do ponteiro. Usando o operador ​“­>”​ ou o ​“​ ​* “​. 
 
… nomeDaVariávelPonteiro ­> membro … 
… (*nomeDaVariávelPonteiro).membro ...  
 
Para se atribuir o endereço de uma estrutura a um ponteiro, usamos um comando de atribuição: 
 
nomeDaVariávelPonteiro = &nomeDaEstrutura; 
 
 
 
 
 
 
 
 
 
 
 
 
 
I. ​ptr ​é um ponteiro que aponta para uma matriz de ​struct​. 
II. ​ptr + x ​(considere x como sendo uma variável do for). Quando um ponteiro se desloca de um, na verdade, ele 
não se desloca para o endereço vizinho, ele avança tantos endereços quantos forem os bytes da variável/estrutura 
apontada por ele que neste caso, são 8. Se você incluísse, depois da linha 16, duas linhas que exibissem esses 
endereços, obteria a saída abaixo. 
 
 16  dados *ptr = new dados[nfunc]; 
       count<<&quot;\nEndereco da primeira struct da matriz:&quot;<<&ptr[0]; 
       count<<&quot;\nEndereco da segunda struct da matriz:&quot;<<&ptr[1]; 
Observe que  de 0x 3e3838 ate ox3e3840, endereços em hexadecimal, temos os seguintes endereços: 3e3838, 
3e3839, 3e383A, 3e383B, 3e383C, 3e383D, 3e383E e 3e383F, totalizando 8 endereços(4 endereços para int e 4 
endereços para float). 
 
III. ​(ptr+x) ­> matric​ é equivalente à ​ptr[x].matric​ porque você pode tratar o ponteiro como se fosse uma matriz e 
amatriz, com se fosse um ponteiro. 
 
ponteiro ­> alocação dinâmica ­> Listas Encadeadas. 
 
Listas de encadeamento simples, normalmente chamadas simplesmente de Listas Encadeadas, são 
compostas de elementos individuais, cada um ligado por um único ponteiro. Cada elemento consiste de 
duas partes: um membro de dados e um ponteiro. (LOUDON, K, 2000, p.56) 
 
 
As Listas Encadeadas são estruturas dinâmicas e, por essa razão, não existe restrição, a não ser de memória, de 
aumentar, ou diminuir, de tamanho durante a execução do programa. 
 
 
 
 
 
As lista encadeadas podem ser: 
 
 
Cada nó tem duas partes. Uma, armazena a informação e a outra, o endereço do próximo Nó.  
Se olharmos para este nó, podemos entendê­lo como uma estrutura, visto que ele é formado por dois tipos 
diferentes, sendo um, necessariamente um ponteiro. 
Se formos audaciosos, diríamos que é uma variável struct com dois membros e, para chegarmos mais próximos do 
nó da Lista, poderíamos nomear esta estrutura de nó. 
O tipo do membro que armazena a informação não será difícil de identificarmos porque dependerá da aplicação, 
mas qual será o tipo da variável ponteiro? 
No nosso breve estudo sobre ponteiros, aprendemos que o tipo do ponteiro tem que ser do mesmo tipo que o 
elemento que ele vai apontar. 
 
Acredito que a única dificuldade ficará por conta de permitir que esta definição possa acontecer dentro dela 
mesma. Como DROZDEK, A(2002,p.68) diz: “Essa circularidade, no entanto, é permitida em C++”.  
 
 
 
Operações que podem ser realizadas com as Listas Simplesmente Encadeadas 
 
Inicializar 
O processo de inicialização de uma Lista consiste em criar uma Lista vazia, isto é uma lista sem elementos. 
A Lista sempre será representada pelo ponteiro para o primeiro elemento e, se é uma lista vazia, seu valor será 
NULL(constante escrita com letras maiúsuculas)​. 
Você pode inicializar a Lista na declaração. Exemplo: ​no *Lista = NULL; 
 
Inserir um nó no início, no fim ou em qualquer posição 
Após a criação da Lista, os nós podem ser inseridos, um a um, ou aos grupos, dependendo como você  
implementou seu código. 
  
Como não existe restrição para posição de inserção na Lista, você vai escolher, mas você concluirá que a  
forma mais simples é a de inserir no ​início ​da Lista. 
 
Remover nó 
A remoção de um nó poderá ser mais simples, ou mais complexa. Tudo vai depender da sua posição na Lista. 
  
Insere nó na frente, em qualquer lugar ou insere nó atrás?  
Remove nó que está na frente, em qualquer lugar ou nó que está atrás? 
  
Quem lê pensa que estamos falando ora de Fila, ora de Pilha ou ora, de Lista já que não tem restrição todas. 
  
Claro que para implementar algumas formas são mais simples do que outras. Entretanto vamos tentar ensinar 
apresentar as três formas.  
  
Observe as figuras abaixo onde nós são inseridos e removidos e, depois de analisar, pense qual estrutura poderia 
ser essa, tendo onde os dados são inseridos/removidos e quais  seriam as etapas da inserção e da remoção de um 
nó? 
 
 
Resposta 
Como Insere na frente e Remove na frente, é a mesma filosofia da PILHA. 
Etapas para inserir um nó no início da Lista 
1 ­ Foi criado um novo nó; 
2 ­ O novo nó foi inicializado com valor 15; 
3 ­ Como o novo nó foi inserido na frente, o membro que contém o apontador deste novo nó se torna um ponteiro 
para o primeiro nó da lista atual; 
4 ­ O novo nó se torna o primeiro da lista e, sendo assim, o ponteiro que sinaliza o primeiro nó, é desviado para o 
nó incluído. 
 
Etapas para remover um nó no início da Lista 
1)O ponteiro que sinaliza o primeiro nó da Lista é reajustado para que o segundo nó passe a ser o primeiro. 
2) Algo que você não poderiasaber: Para que seja possível a etapa 1, a informação do nó removido é armazenada 
para que depois que finalizar a etapa 1, possa ser deletada(delete). 
 
 
Percorrer a lista 
Percorrer a lista significa ​“passar”por todos os nós​. Seja para ​exibir​ todos os nós, ​contar​ os nós, ​buscar​ um  
elemento para ​remoção​ ou para ​alterar​ seu valor. 
 
Além destas, ainda temos as seguintes operações: 
­ EXIBIR A LISTA; 
­ DETERMINAR O NÚMERO DE NÓS; 
­ LOCALIZAR UM NÓ; 
­ ALTERAR O CONTEÚDO DE UM NÓ, ENTRE OUTRAS. 
 
Para que possamos fazer o passo a passo, vamos supor que nosso nó tenha como membro um número 
inteiro fora o ponteiro. Assim, vamos  construir uma lista com um nó.  
 
­ Definindo a Struct 
 
­ Criando nó 
nodo* no1 = new nodo; 
 
­ atribuindo valores aos membros 
no1­>num = 23; 
     no1­>prox = NULL; 
 
­ Exibindo 
cout<< ”\nValor do no1:” << no1­>num; 
 
­ Liberando 
delete no1; 
                            no1=0;  ​ //pelo que falamos 
 
Agora que conseguimos, vamos construir uma lista com dois nós. Usaremos a mesma struct para facilitar. 
Observe que os dois nós serão dependentes da mesma variável ponteiro. 
 
 
 
 
 
 
 
Insere nó ao final 
 
 
 
 
 
Aula 9: Listas Encadeadas – Finalizando / Pilhas e Filas Dinâmicas 
 
LISTANDO A LISTA 
 
 
REMOVENDO ELEMENTO DA LISTA 
 
 
 
 
INSERINDO ELEMENTO DA LISTA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Aula 10: Listas Duplamente Encadeadas 
 
 
 
 
Vamos analisar como seria a remoção de um nó que se encontra no meio através da figura abaixo e de dois 
comandos que considero de maior dificuldade na função remover. 
 
 
 
Todas as operações realizadas com as Listas Simplesmente Encadeadas poderão ser realizadas com as 
Duplamente Encadeadas e algumas, com mais facilidade. 
Como na aula 8, já falamos sobre alocação dinâmica de Memória, sobre Lista Encadeada, explicamos da 
necessidade do ponteiro, constato que não temos muito que acrescentar de teoria nesta aula. Sendo assim, vou 
apresentar nosso último programa, evidentemente com menu como gosto e com algumas funções que considero 
básicas e que já fizemos com Listas simplesmente Encadeadas. 
 
 
 
 
 
 
 
 
 
 
 
 
Gostaria de deixar para você um presente. Então pensei: Professor deixa que tipo de presente? Um 
exercido que dê muito trabalho, é claro, pois o resultado é gratificante. 
 
Deixo então, uma função que estava originalmente neste programa. Gostaria que você analisasse antes de 
inserir no programa e descobrisse o que ela faz. 
Depois, pesquisasse na Internet e pensasse em algumas alterações que poderia fazer nesta função para 
que ela pudesse ter uma função mais ampla.