ESTRUTURAS DE DADOS AULAS

Prévia do material em texto

AULA 1: APRESENTANDO AS ESTRUTURAS DE DADOS
 
 
 
SÍNTESE DA AULA
Nesta aula, você: 
Aprendeu as diferenças entre as Estruturas de Dados que estudaremos em nosso Curso tais como Fila, Lista, Pilha;
Compreendeu o conceito de função que será de muito importância nesse curso;
Compreendeu o conceito de struct;
Compreendeu o conceito de Ordenação e de Pesquisa;
REGISTRO DE FREQUÊNCIA
1. Selecione a Estrutura de Dados que melhor representa os diretórios ou pastas de arquivos do computador.
 1) Fila 
 2) Pilha 
 3) Árvore 
 4) Lista 
 5) Grafo 
2.Selecione a Estrutura de Dados que melhor representa os três estados que um processo pode assumir em um Sistema Operacional(Tanenbaum, A.S)
 1) Árvore 
 2) Lista Encadeada 
 3) Pilha 
 4) Grafo 
 5) Fila 
 
3.Assinale a afirmativa correta
 1) Fila, Árvore e Pilha são Estruturas de Dados lineares. 
 2) Árvore e Grafo não são Estruturas de Dados lineares. 
 3) Pilha, Fila e Grafo são Estruturas de Dados não lineares. 
 4) Grafo, Árvore e Listas Encadeadas são estruturas não lineares. 
 5) Struct não é uma estrutura de dados heterogêneos. 
4.A Estrutura de Dados conhecida pela sigla FIFO é
 1) Árvore 
 2) Pilha 
 3) Grafo 
 4) Lista Encadeada 
 5) Fila 
GABARITO
1-3; 2-4; 3-2; 4-5
 ESTRUTURA DE DADOS 195
AULA 2
	
	
Um programa pode ser formado por uma ou mais funções.
A função main sempre estará presente.
	
	
Fluxo do programa após o término da Função
Na instrução seguinte - void 
No lugar em que é chamada - com retorno
PASSAGEM POR VALOR
Exemplo: Você empresta seu caderno para xerocar.
PASSAGEM POR REFERÊNCIA &
Exemplo: Você entrega os originais da sua monografia para um revisor
PODE SER COLOCADA ANTES OU DEPOIS DA MAIN 
SE COLOCADA DEPOIS DA MAIN É NECESSÁRIO SE UTILIZAR PROTÓTIPO
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
2.5 Tipos de Funções
2.5.1 Função sem parâmetros
COMO É FEITA A CHAMADA DE UMA FUNÇÃO SEM RETORNO?
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. Vejamos a sintaxe abaixo.
Função com parâmetros
Para que possamos trabalhar com funções com parâmetros, primeiro precisamos saber como a passagem para esses parâmetros é feita.
Duas são as formas básicas de passagem dos 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.
Concordamos que para alguns poderá parecer confuso e, por essa razão vamos exemplificar com algo do cotidiano.
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).
 
Vamos usá-lo nos parâmetros formais da função. Observe o protótipo abaixo.
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 
Não se preocupe com os nomes usados por alguns autores para se referenciar a esse tipo: passagem por nome ou passagem por endereço. O importante é que o  uso de uma variável do tipo ponteiro é obrigatório. Embora a variável do tipo ponteiro não seja objeto de estudo aqui, vale a pena dizer que 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). Observe a figura ao lado.
PASSAGEM POR REFERÊNCIA
É a passagem que usa o tipo referência, já definida nesse tópico.
Como é feita a chamada de uma função que retorna valor?
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.
return ...;
Pode estar presente uma variável, uma constante, uma expressão.
EXEMPLO
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;
}
Uma função, que não seja a main, chamando outra função poderá causar algum problema?
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.
Antes de prosseguirmos, apresentaremos dois conceitos que permeiam este estudo.
VARIÁVEIS LOCAIS
A maioria dos exemplos apresentados até aqui teve 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.
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 SO. Sendo pontual, o return da main poderia ser dispensável, visto queele 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
Nossos exemplos só abordaram passagens de valores, ou de endereços, de variáveis numéricas, mas agora vamos aprender como passamos para uma função uma estrutura de dados homogênea. Em particular, uma matriz unidimensional (vetor).
Um dos conceitos já estudados anteriormente dizia respeito ao armazenamento na MP de um vetor. Falamos que só era armazenado o primeiro endereço do primeiro elemento do vetor. Vejamos as figuras do programa, do armazenamento na MP e das saídas do programa compilado no Dev-CPP e no Visual C++.
	
	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.
Vamos agora analisar alguns protótipos com passagem de vetores para funções.
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.
Agora estaremos escrevendo as definições dos quatro protótipos.
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;
}
SÍNTESE DA AULA
Nesta aula, você: 
Compreendeu a importância da modularizar nossos programas.
Aprendeu as diferenças entre funções por passagem de valor e por passagem de referência com suas variações.
Analisou protótipos de funções.
Compreendeu a diferença entre protótipo e cabeçalho.
Compreendeu a diferença entre declaração e definição de função.
Implementou funções de todos os tipos.
Construiu sua biblioteca.
REGISTRO DE FREQUENCIA
1.Analise as respostas abaixo e assinale a que corresponde ao protótipo de uma função que recebe um argumento inteiro e não retorna nenhum valor.
 1) int prod(int num); 
 2) void prod(int num) 
 3) void prod (num); 
 4) void prod(int); 
 5) int prod(int); 
2.Leia as sentenças abaixo e assinale a resposta correta:
I – Uma função pode ser criada dentro de outra função.
II – Uma função que não é a função main pode chamar outra função.
III- Toda definição de função tem que ser escrita antes da main.
IV- Protótipo e cabeçalho de função são sinônimos.
 1) Todas estão corretas. 		4) Só a II está correta. 
 2) Todas estão erradas. 		5) II e III estão corretas.
 3) I e II estão corretas. 
3.Qual a afirmativa verdadeira?
 1) Você pode retornar para um programa quantas variáveis de uma função desejar através do comando return. 
 2) Uma função só pode ter um comando return. 
 3) Os protótipos de função servem para declarar as funções, isto é, indicar para o compilador qual o seu nome, tipo de retorno, o número e tipos dos parâmetros. 
 4) Uma função pode retornar dois valores. 
 5) Funções só podem ser definidas antes da main. 
4.Qual das seguintes razões não é uma razão válida para o uso de funções na linguagem C++?
 1) Funções usam menos memória do que se repetirmos o mesmo código várias vezes. 
 2) Funções tornam a execução do programa mais rápida. 
 3) Funções fornecem um meio de esconder cálculos em uma "caixa preta" que pode ser usada sem a preocupação de detalhes internos de implementação. 
 4) Funções mantêm variáveis protegidas das outras funções do programa. 
 5) Funções possibilitam uma manutenção mais simples. 
GABARITO
1-4; 2-4; 3-3; 4-2
AULA 3: ESTRUTURAS HETEROGÊNEAS
OBJETIVOS DA AULA
Ao final desta aula, você será capaz de:
1. Compreender o uso das estruturas heterogêneas definidas pelo programador;
2. Definir e declarar estruturas heterogêneas localmente e globalmente;
3. Identificar que tipos de elementos podem ser membros de uma estrutura;
4. Implementar programas usando estruturas heterogêneas;
5. Construir funções usando estruturas heterogêneas;
Definindo...
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.
Como se define uma estrutura?
Para se definir uma estrutura, você precisa seguir a seguinte sintaxe:
A definição termina com um ;  porque é um comando. É bom ressaltar que nenhuma variável foi declarada.
	
	 
Como se declara uma variável do tipo definido pela estrutura?
1 Declarando após a definição
2 Definindo e declarando
3 Definindo/declarando Anônima
Agora que a variável foi declarada, o compilador aloca na Memória Principal todos os membros da estrutura.
Exemplo de estrutura/definindo
struct data
{
int dia, mes, ano;
};
Exemplo de declaração
	struct data
{
int dia, mes, ano;
};
data data1;
	struct produto
{
char nomeProd[21];
float valor;
}prod1;
As variáveis de uma estrutura são agrupadas por uma lógica e estão associadas a um mesmo nome. Para acessar cada membro, é muito fácil. Observe o próximo item.
 
Como se acessa um membro de uma estrutura?
 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.
	struct data
{
int dia, mes, ano;
};
	...data1.dia...
...data1.mes...
...data1.ano...
Atribuindo valores aos membros na declaração
struct data
{
int dia, mes, ano;
};
data data1={15,11,1918};
;
Atribuindo valores aos membros na definição/declaração
struct data
{
int dia, mes, ano; 
} data1={18,8,1917}
Atribuindo valores aos membros via teclado
struct data
{
int dia, mes, ano;
} data1;
cin>> data1.dia; cin>>data1.mes; 
cin>>data1.ano;
Declarando um array de estruturas
Um array de estruturas pode ser declarado da mesma forma que uma estrutura simples. 
struct dados
{
float peso, altura, IMC;
}atletas[1000];
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. A figura esclarece isso do lado esquerdo quando relaciona as variáveis estruturas com um par de colchetes e o deslocamento dentro dele(índice).
Depois, acrescentamos separado por um ponto, os membros da estrutura. Você poderá ver isso no lado direito da figura.
Cada retângulo está dividido por linhas tracejadas porque uma variável do tipo int, ou do tipo float, ocupa quatro posições de memória.
	
	
Gostaríamos de relembrar que os dados são alocados de forma contígua na Memória Principal como se fosse uma matriz unidimensional. A figura acima é meramente ilustrativa e tem como objetivo possibilitar uma melhor compreensão sobre um array de estruturas.
Algumas considerações
Temos duas formas de resolver o problema: uma matriz de estrutura ou três matrizes. Se preferirmos a segunda, percebe-se que não existe uma relação entre as matrizes e quando formos ordenar, precisaremos de muitos trechos para trocar as variáveis de lugar. Não que esteja errado, mas tudo ficaria mais extenso se continuássemos  usando somente as matrizes. Lembre-se que elas não desaparecem, mas se agregam.
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)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:
struct data
{
int dia, mes, ano;
};
struct dados
{
float peso, altura, IMC;
data niver;
}atletas[1000];
Acessando um membro de uma estrutura dentro de um array de estruturas
nomeDoArrayl[deslocamento no array].nomeDaEstruturaAninhada.membro
Observe que são dois pontos. O primeiro entre promissorias[1] e o membro venc. Mas como venc é uma estrutura e dia é membro de venc tem um ponto separando venc de dia. Esse é o segundo ponto.
O encontro das estruturas com as funções e das funções com as estruturas
	
	
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 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 PE UM VETOR – PASSAGEM POR ENDEREÇO
Já que provamos que o vetor é um endereço, vamos ao exemplo onde passaremos um membro da estrutura que é um vetor.
ESTRUTURA COMO PARÂMETRO DE UMA FUNÇÃO
Neste exemplo, apresentaremos uma função que recebe uma estrutura para ser manipulada dentro da 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
Neste exemplo, apresentaremos uma estrutura  cujos dois membros são funções. Uma com retorno e outra, sem retorno.
SÍNTESE DA AULA
Nesta aula, você: 
Compreendeu a importância das estruturas heterogêneas, visto que elas possibilitaram agrupar dados de tipos diferentes.
Aprendeu a diferença entre definir e declarar uma estrutura heterogênea;
Construiu programas usando estruturas heterogêneas;
Construiu funções que recebiam ou retornavam estruturas;
Construiu estruturas que tinham funções como membros;
REGISTRO DE FREQUÊNCIA
1.Se desejamos definir uma estrutura de nome cad que tenha dois membros: o primeiro do tipo inteiro e de nome cod e o segundo, um vetor real de 5 elementos e de nome notas, qual das definições abaixo estaria correta?
 1) struct cad{ int cod ; float notas[4];} 
 2) struct cad{ int cod ; float notas[5];} 
 3) struct cad{ int cod ; double notas[5];} 
 4) struct cad{ int cod ; float notas[5];}; 
 5) struct cad{ int cod ; double notas[4];}; 
 
2.Leia as sentenças abaixo e assinale a resposta correta:
I – Uma estrutura não pode ter uma função como membro.
II – Uma estrutura pode ser retorno de função.
III- Um membro de uma estrutura pode ser passado por valor e por referência.
IV- Não é permitido ter estruturas dentro de estruturas .
 1) Todas estão corretas. 
 2) Todas estão erradas. 
 3) II e IV estão corretas. 
 4) Só a II está correta. 
 5) II e III estão corretas. 
3.Qual a afirmativa verdadeira?
 1) Uma estrutura não pode ser anônima. 
 2) Uma estrutura pode ser atribuída a outra estrutura. 
 3) Uma estrutura definida localmente pode ser usada por todas as funções. 
 4) Não se pode construir um vetor de estruturas. 
 5) O operador, possibilita que acessemos o membro de uma estrutura. 
 
4.Observe as definições e declaração abaixo. Assinale a resposta correta se desejássemos atribuir o valor 23 ao quarto elemento da terceira variável do array de estruturas de nome números.
 struct num
 {
 int a[4];
 }; 
 int main() 
 {
 struct cad
 {
 num b;
 }numeros[5];
...
 }
 1) numeros[3].b[4]=23; 
 2) numeros[2].b[3]=23; 
 3) numeros[2].b.a[3]=23; 
 4) numeros[3].b.a[4]=23; 
 5) numeros[3].a[4]=23; 
 
GABARITO
1-4; 2-5; 3-2; 4-3
AULA 4
ORDENAÇÃO E PESQUISA
OBJETIVOS DA AULA
Ao final desta aula, você será capaz de:
Compreender  e usar o método de ordenação insertion sort, (inserção) em estruturas homogêneas e em estruturas heterogêneas;
Compreender  e usar o método de ordenação selection sort (seleção) em estruturas homogêneas e em estruturas heterogêneas;
Compreender  e usar o método de ordenação bubble sort (bolha) em estruturas homogêneas e em estruturas heterogêneas;
Compreender  e usar os método de pesquisa seqüencial em estruturas homogêneas e em estruturas heterogêneas;
Compreender  e usar os método de pesquisa binária em estruturas homogêneas e em estruturas heterogêneas; 
INT, FLOAT OU DOUBLE
Você pode comparar os conteúdos de vetores numéricos usando os operadores relacionais >, >=, 
<, <= , == e !=.
Para trocar os conteúdos das variáveis, o comando de atribuição poderá ser usado.
if(vet[0]>vet[1])
  {
    aux=vet[0];
    vet[0]=vet[1];
    vet[1]=aux;
  }
CHAR DE UM CARACTER
Essa é uma confusão muito comum no inicio, pois como fazer a diferença entre as declarações  char nome[30];  e char sexo[30]; ?
Aparentemente, nenhuma. A diferença só acontecerá quando você construir o  trecho de entrada de dados. Se usar um único comando, significa que todos os caracteres formam um conjunto unitário, mas se você possibilitar a entrada de 30 caracteres, como por exemplo o sexo de 30 pessoas, então esse é um conjunto de 30 elementos independentes.
Nesse exemplo, estamos nos referindo ao segundo caso e,sendo assim, você pode comparar os conteúdos usando os operadores relacionais >, >=, <, <= , == e !=.
Para trocar os conteúdos das variáveis, o comando de atribuição poderá ser usado.
if(vet[0]>vet[1])
  {
    aux=vet[0];
    vet[0]=vet[1];
    vet[1]=aux;
  }
VETOR DE CHAR
Nós agora vamos comparar vetores de char que juntos podem formam uma matriz bidimensional.
Você pode observar que 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 todo 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.
if(strcmp(vet[0],vet[1]) > 0)
  {
    strcpy(aux,vet[0]);
    strcpy(vet[0],vet[1]);
    strcpy(vet[1],aux);
  }
MEMBROS DE STRUCT
Neste último exemplo, estaremos comparando membros de structs que fazem parte de um vetor de structs. As regras da comparação seguirão as mesmas dos exemplos anteriores, isto é, depende do tipo do membro, mas, como o  tipo do escolhido é inteiro, poderemos usar os operadores relacionais  >, >=, <, <= , == e != e, para trocar os conteúdos das variáveis, o comando de atribuição.
if(candidatos[0].ninsc>candidatos[1].ninsc){
    aux=candidatos[0];
    candidatos[0]=candidatos[1];
    candidatos[1]=aux;
  }Entretanto, se tivéssemos escolhido o membro vetor de char, teríamos que proceder da mesma forma que no exemplo anterior.
	Métodos Simples 
indicados para conjuntos pequenos; 
usam muitas comparações; 
os códigos são pequenos; 
códigos de fácil entendimento; 
mais eficientes para pequenos arquivos. 
Exemplos: 
1. Selection Sort 
2. Insertion Sort 
3. Bubble Sort 
	Métodos Eficientes ou Sofisticados
indicados para conjuntos grandes; 
usam menos comparações; 
os códigos são grandes; 
alguns incluem conceito de recursividade, deixando-os muito complexos. 
Exemplos: 
1. Quick Sort 
2. Merge Sort 
Selection Sort 
O princípio básico desse método é sempre buscar o menor dos valores restantes e levá-lo às posições iniciais(ordenação crescente). 
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. 
Insertion Sort 
O princípio básico desse método é considerar o vetor como dois subvetores, um ordenado e o outro, desordenado, buscando posicionar o elemento que se encontra no subvetor desordenado, no vetor ordenado. 
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. 
#include<iostream>
using namespace std;
struct dados
{
 int matric;
 float CR;
}; 
void insercao(dados vetor[], int tam);
int main()
{
 dados vet[]={13,9.5, 23, 3, 8 , 10, 10};
 system("cls");
 cout<<"\nAntes da chamada da Funcao - INSERCAO\n";
 for(int x=0; x<3;x++)
 cout <<"\n"<<vet[x].matric<<"\t"<<vet[x].CR;
 cout<<"\n";
 insercao(vet, 3);
 cout<<"\n\nDepois da chamada da Funcao - INSERCAO\n";
 for(int x=0; x<3;x++)
 cout <<"\n"<<vet[x].matric<<"\t"<<vet[x].CR;
 cout<<"\n\n";
 system("pause");
}
void insercao(dados vetor[], int tam)
{
 int j,i;dados aux;
 for (i=1;i<tam;i++)
 {
 aux = vetor[i];
 for(j=i; j>0 && aux.CR <vetor[j-1].CR; j--)
 vetor[j]=vetor[j-1];
 vetor[j]=aux; 
 }
}
Bubble Sort
O princípio básico desse método é trocar de posições toda vez que forem encontrados valores de posições adjacentes fora de ordem. 
É o mais conhecido método. 
É muito simples. 
Muito lento. 
É considerado o pior dos três estudados. 
Afinal, qual seria o melhor método de ordenação?
Como disse no início, não teríamos como fazer um estudo incluindo muitos métodos de ordenação para que ao final, pudéssemos fazer uma análise consistente. Sendo assim, levantaremos somente alguns pontos sobre os três métodos estudados que são os mais simples, mas não são os indicados para grandes volumes de dados.
1) Suponha o vetor de 10 elementos.
2) Suponha que 18 é o número a ser procurado.
3) Vamos calcular o meio do vetor, sabendo-se que o início é 0 e o final é 9: (0+9)/2(divisão inteira). Logo, 4.
4) Como o número procurado é maior do que o meio, o início passa ser o seguinte do meio.
5) Calcula-se o novo meio: (5+9)/2=7
SÍNTESE DA AULA
Nessa aula você: 
Compreendeu a importância da ordenação para a pesquisa; 
Aprendeu a diferença entre os métodos de ordenação; 
Aprendeu a diferença entre a pesquisa seqüencial e a pesquisa binária;
REGISTRO DE PARTICIPAÇÃO
1.O método de ordenação que faz uma varredura no vetor para buscar o menor elemento e colocá-lo na primeira posição se estiver ordenando de forma crescente é:
1) Método da bolha.
2) Metódo Binário.
3) Método por Seleção.
4) Método por Inserção.
5) Método Sequencial.
 
2.Leia as sentenças abaixo e assinale a resposta correta.
É permitido usar o operador relacional == para comparar vetor de char.
A função strcmp(,) serve para comparar vetores de char.
Na ordenação, a variável que auxilia na troca deverá ser do mesmo tipo que as variáveis que estão sendo trocadas.
É permitido usar o comando de atribuição para vetores de char na troca de conteúdos de variáveis.
1) I e III estão corretas.
2) II e IV estão erradas.
3) III e IV estão corretas.
4) I e IV estão erradas.
5) Todas estão corretas.
3.Leia as sentenças abaixo e assinale a resposta correta.
A pesquisa seqüencial só funciona se o vetor estiver ordenado.
A pesquisa binária só funciona se o vetor estiver ordenado.
Se o vetor estiver ordenado, o método de inserção tem melhor desempenho do que o método da bolha e o de seleção.
O método da bolha é de simples compreensão, mas pouco difundido.
1) Todas estão corretas.
2) II e III estão corretas.
3) III e IV estão corretas.
4) II, III e IV estão corretas.
5) Todas estão erradas.
 
GABARITO
1-3; 2-4; 3-2
AULA 5
A ESTRUTURA DE DADOS – LISTA 
OBJETIVOS DA AULA 
Ao final desta aula, você será capaz de: 
Compreender o conceito da Estruturas de Dados – Lista Linear;
Identificar as diferenças entre Lista Linear Sequencial e Encadeada;
Compreender e usar a Estruturas de Dados – Lista Linear Sequencial;
Identificar as principais características da Lista Linear Sequencial;
Compreender e usar várias operações realizadas com Lista Linear Sequencial;
Aplicar os conceitos de ordenação e pesquisa com Lista Linear Sequencial; 
Todas as Estruturas de Dados têm suas importâncias e aplicações, mas, normalmente, começamos pelas Listas porque uma das formas mais simples de representá-las  é com  estruturas já conhecidas como as matrizes homogêneas e as matrizes heterogêneas. Além disso, elas servirão de base para que possamos implementar Estruturas de Dados que iremos estudar nas próximas aulas tais como Pilhas e Filas.
“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)
Da definição dos autores, vamos destacar alguns conceitos:
1) Nó ou nodo– é um item da lista.
	NÓ1
	NÓ2
	NÓ3
	NÓ4
	NÓ5
	NÓ6
	NÓ7
	NÓ8
	NÓ9
	NÓ10
2) 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.
3) 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.
ENCADEADO
O princípio básico da Lista Encadeada é 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.
Esta classificação que acabamos de estudar 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 e é o que estamos fazendo e iremos fazer até à aula 7. 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.
Estática - definida durante a programação
 (reservada no início da execução). 
Dinâmica - reservada durante a execução. 
Sequencial - elementos alocados de forma
 contígua. 
Encadeada - os elementos não são alocados de
 forma contígua
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 determinauma classificação mostrada na figura abaixo.
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.
	Criar uma Lista;
Verificar se a Lista esta vazia;
Verificar se a Lista esta cheia;
Inserir elemento na Lista;
Remover elemento da Lista;
Exibir o tamanho da lista;
Retornar a posição de um elemento da Lista;
	Exibir a Lista;
Exibir frequencia;
Pesquisar um elemento na Lista;
Alterar um elemento da Lista;
Ordenar a Lista;
Inserir ordenado na Lista;
Concatenar Lista;
Dividir Lista; 
Exemplo
Este exercício terá uma LISTA com 5 nós. Os elementos desta LISTA serão inteiros e códigos de produtos. Foram colocados, no menu, 4 trechos: 
Inserir elementos na Lista, 
Exibir os elementos da Lista, 
Exibir um elemento da Lista e 
Exibir o tamanho da Lista. 
Para os três primeiros, foram criadas funções, mas, para o último, por ser extremamente simples, não. 
A FUNÇÃO INSERIR
A FUNÇÃO EXIBIR LISTA
A FUNÇÃO EXIBIR UM ELEMENTO
MAIS FUNÇÕES
ORDENA LISTA
BUSCA SEQUEÊNCIAL
SÍNTESE DA AULA
Nessa aula você: 
Compreendeu a importância da Estrutura de Dados Lista Linear Sequencial;
Aprendeu a diferença entre Lista Linear Sequencial e Lista Linear Encadeada;
Compreendeu e usou várias operações que podem ser feitas com a Lista Linear Sequencial;
Aplicou os conceitos de ordenação e pesquisa com Lista Linear Sequencial;
REGISTRO DE PARTICIPAÇÃO
1.Leia com atenção as afirmativas e verifique quais são verdadeira e quais são falsa. Depois escolha a resposta correta.
( ) Não existe necessidade de se inicializar uma lista.
( ) Uma Lista Sequencial só pode ser estática
( ) Uma Pilha é um tipo de Lista
( ) Alocação estática é durante a compilação
 1) F F F F 
 2) F V V V 
 3) V V V V 
 4) F F V V 
 5) F V V F 
2.Existem quatro categorias possíveis no que diz respeito á Alocação de Memória. Assinale a única que contempla duas dessas categorias.
 1) estática dinâmica e estática encadeada. 
 2) estática encadeada e dinâmica sequencial. 
 3) sequencial encadeada e dinâmica sequencial. 
 4) estática dinâmica e sequencial encadeada. 
 5) duplamente encadeada e estática dinâmica. 
3. Observe a função abaixo. Suponha uma lista ordenada com 100 números que representam códigos dos vendedores das cem primeiras vendas da loja. Sabe-se que a loja só tem 12 vendedores.
Acompanhe a execução no teste de mesa e assinale a resposta correta.
void descobre(int codigos[], int t)
{
 int j=0, c=1,m= codigos [0];
 while(j<t)
 { 
 j++;
 if(codigos [j]== codigos [j-conta])
 { m= codigos [j];
 c++;
 }
 }
 cout<<"\n"<<m;
}
 1) Exibe o maior código. 
 2) Exibe o que menor código. 
 3) Exibe o código que mais aparece. 
 4) Exibe o código que é igual ao anterior. 
 5) Exibe todos os códigos que aparecem mais de uma vez. 
GABARITO
1-4; 2-2; 3-3
AULA 6: A ESTRUTURA DE DADOS – PILHA
OBJETIVOS DA AULA
Ao final desta aula, você será capaz de:
1. Conceituar a Estrutura de Dados Pilha;
2. Representar a Estrutura de Dados Pilha por contigüidade;
3. Compreender e implementar as operações com Pilhas;
4. Compreender e testar aplicação com Pilha sequencial;
Conceito de Pilha
“Uma pilha é um tipo especial de Lista Linear em que todas as operações de inserção 	e remoção são realizadas numa mesma extremidade, denominada topo.” (PEREIRA, Silvio. L., 2004, p. 35)
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).
Características da Pilha 
Inserção ou Remoção de um elemento sempre acontece na mesma extremidade.
Observe a figura abaixo.
 Inserção Remoção 
 
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.
Operações realizadas com Pilhas 
1) Inicializa () ou Init() 
2) Empilhar() ou Push() 
3) Desempilhar() ou Pop() 
4) acessoTopo() ou Top() 
5) verificaPilhaCheia() ou isFull() 
6) verificaPilhaVazia() ou isEmpty() 
ATENÇÃO
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.
ATENÇÃO - 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.
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.
ATENÇÃO
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 no topo  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 com 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.
ACESSOTOPO(...) OU 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.
situaçãoPilha (...)
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.
 
ATENÇÃO - 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.
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.
SÍNTESE DA AULA
Nessa aula você: 
Compreendeu a importância da Estrutura de Dados Pilha;
Compreendeu e usou várias operações que podem ser feitas com a Pilha;
Analisou aplicações da Pilha e acompanhou a execução de programas;
REGISTRO DE PARTICIPAÇÃO
1.Considerando que Push() coloca um elemento na pilha, Pop() remove um elemento da pilha e Top() exibe o elemento que se encontra no topo, assinale a resposta que indica o número que aparecerá após a sequencia de comandos abaixo, sabendo-se que os números deverão ser inseridos na sequencia em que se apresentam.
Sequencia: Push() / Push()/ Pop()/ Push()/Pop()/ Top()
Números: 8/ 15/ 23/ 13 / 18
 1) 13 
 2) 23 
 3) 8 
 4) 15 
 5) 18 
2.Analise as afirmativas e assinale a opção correta.
	Ordenar é uma operação que não se faz com pilha.
Inserir dados.
Remover dados em qualquer posição.
Não se exibe o total de elementos na pilha.
Inicializar é zerar toda a pilha.
	II e III estão corretas. 
I e IV estão corretas. 
I e II estão corretas. 
I, II e V estão corretas. 
I, II e IV estão corretas. 
3.Assinale a sigla que representa o critério usado pela PILHA para inserção/remoção dos elementos.
 1) FIFO 
 2) FSRD 
 3) FERD 
 4) LIFO 
 5) DEQUE 
 
GABARITO
1-3; 2-3; 3-4
AULA 7: A ESTRUTURA DE DADOS – FILA
OBJETIVOS DA AULA
Nesta aula, você irá: 
1. Conceituar a estrutura de dados Fila simples e Fila Circular;
2. Representar a estrutura de dados Fila por contigüidade (Fila simples);
3. Compreender e implementar as operações com Fila simples;
4. Representar a estrutura de dados Fila por contigüidade (Fila circular);
5. Compreender e implementar as operações com Fila circular;
À medida que vamos conhecendo novas estruturas de dados, passamos a contar com maiores recursos para elaborarmos nossos algoritmos mais próximos do ideal. Sei que no início pode parecer que estas estruturas de dados, que estamos estudando, não são necessárias, mas talvez porque nunca tenhamos construindo um grande sistema ou então, nossos sistemas estão restritos a determinadas áreas onde o “velho triângulo: entrar-armazenar-consultar” é a base do sistema que pode até prescindir destas estruturas.
Características da Fila
Inserção em uma extremidade e Remoção, em outra.
Inserção
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.
ATENÇÃO
Remoção 
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.
Operações possíveis com as Filas são semelhantes com as da Pilha. Vamos dar uma verificada, lembrando que vou, apresentá-las, também, com os nomes pelas quais são mais conhecidas embora possa usar o nome que desejar para as funções que você irá criar em seus programas.
1) Inicializa() ou Init()
Inicializa os indicadores de inicio e fim da Fila
2) Enfileira() ou Enqueue() 
Insere elemento no final da Fila
3) Desenfileira() ou Dequeue() 
Remove o elemento do início da Fila
4) elemPrimeiro () ou firstElem()
Retorna o primeiro elemento sem retirá-lo da Fila
5) verificaFilaCheia() ou isFull() 
Verifica se Fila está cheia
6) verificaFilaVazia() ou isEmpty() 
Verifica se Fila está vazia
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 homogêneas e matrizes heterogêneas(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.
DECLARAÇÃO NA MAIN 
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 () ou Init()
PROGRAMA EM C++
	#include <iostream>
#define TAM 5
using namespace std;
//variavel global
struct queue 
{ 
 float f[TAM]; 
 int inicio,fim; 
}; 
void enfileira(queue &fil);
void desenfileira(queue &fil);
void elemPrimeiro(queue &fil);
void situacaoFila(queue &fil);
	 cout<<"\n1- Inserir um valor na fila";
 cout<<"\n2- Remover um valor da fila";
 cout<<"\n3- Mostrar o elemento do inicio da fila";
 cout<<"\n4- Mostrar situacao da fila"; 
 cout<<"\n5- Sai"; 
 cout<<"\nOpcao: ";
 cin>>resp; op=atoi(resp);
 system("cls");
switch(op)
{ case 1: enfileira(fila);
 break;
 case 2: desenfileira(fila); 
 break;
	int main()
{
 charresp[10]; int op;
 
 queue fila; //declara a fila
// Inicializa a fila
 fila.inicio = 0; 
 fila.fim = -1; 
do
{ system("cls");
 system("color 71"); 
 cout<<"\nFILA( FIFO - First In - First Out )\n\n";
	 case 3: elemPrimeiro(fila);
 break;
 case 4: situacaoFila(fila);
 break;
 case 5: cout<<"\nPrograma basico da FILA\n";
 break;
 default: cout<<"\nOPCAO INVALIDA\n"; 
 } cout<<"\n\n";system("pause"); 
 }while(op!=5);
}
// TODAS AS FUNÇÕES CUJOS PROTÓTIPOS ESTÃO PRESENTES ANTES DA main() E QUE IREMOS ESTUDAR
Enfileira() ou 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.
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.
Desenfileira() ou 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.
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”.
ATENÇÃO
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 com a função enfileirar, a função desenfileirar é de fácil implementação e bem parecida.
elemPrimeiro () ou 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.
situacaoFila (fila)
Esta função testa se a Fila está vazia e, se não estiver, exibirá várias coisas sobre a Fila inclusive, exibe a Fila para que você possa acompanhar melhor a execução do programa.
Se você tiver prestado atenção às funções apresentadas, terá percebido que elas não são muito diferentes das que operaram a Pilha afinal, as duas estruturas são casos particulares da Lista Linear.
APLICAÇÕES COM FILAS
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.
Nesta aula, procurei selecionar exemplos interessantes para provar a importância desta estrutura e simplifiquei as soluções para facilitar o entendimento de cada função. Entretanto, anexei os originais para aqueles que têm mais experiência.
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 sobe uma mesa, perceberíamos que ela se fecharia em uma curva. Pronto. Encontramos a solução: uma Fila Circular.
DEFINIÇÃO DA VARIÁVEL GLOBAL			Inicializa () ou Init()
ENFILEIRAR 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 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 aquele 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.
LISTAR lista(fila)
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.
PROGRAMA EM C++
	#include <iostream>
#include <cstring>
#include <cctype>
#define MAX 5
using namespace std;
struct queue 
{
 float circular[MAX];
 int total, inicio, final;
}; 
void entra(queue &fil);
void deleta(queue &fil);
void lista(queue &fil) ;
int main()
{
 queue fila;
 int x;
 char resp[40],s;
 //inicializa 
 fila.inicio = 0; 
 fila.total = 0; 
 fila.final=0; 
for(;;)
 {
 system("cls");
 system("color 1e");
 cout<<"\n *************";
 cout<<"\n * I - Inserir *";
	 cout<<"\n * L - Listar *"; 
 cout<<"\n * R - Remover *";
 cout<<"\n * S - Sair *"; 
 cout<<"\n *************\n";
 cin.getline(resp,40); 
 s= toupper(resp[0]);
 system("cls");
switch(s)
 {
 case 'I': entra(fila);
 cin.get();//limpa buffer
 break;
 case 'L': lista(fila);
 break;
 case 'R': deleta(fila);
 break;
 case 'S': system("pause"); exit(0);
 }
 cout<<"\n\n";system("pause");
 }//fecha for
}
void entra(queue &fil)
{
 float valor;
 if(fil.total==MAX)
 cout<<"\nAtencao. Fila Cheia\n";
 else 
 {
	{
 cout<<"\nDigite valor: "; cin>>valor;
 fil.circular[fil.final]=valor;
 fil.final++; 
 if(fil.final==MAX)fil.final=0; 
 fil.total++; 
 }
}
void entra(queue &fil)
{
 float valor;
 if (fil.total==MAX)
 cout<<"\nAtencao. Fila Cheia|n";
 else
 {
 cout<<"\nDigite valor: ";
 cin>>valor;
 fil.circular[fil.final=valor;
 fil.final++;
 if(fil.final==MAX)fil.final=0;
 fil.total++;
 }
}
void deleta(queue &fil)
{
 if(fil.total==0)
 cout<<"\nAtencao. Fila Vazia\n";
 else 
	{ 
 cout<<"\nRemovido: "<<fil.circular[fil.inicio];
 fil.inicio++; 
 fil.circular[fil.inicio-1]=-999;
 if(fil.inicio==MAX)fil.inicio=0; 
 fil.total--; 
 }
}
void lista(queue &fil)
{
 if(fil.total==0)
 cout<<"\nAtencao. Fila Vazia\n";
 else
 {
 cout<<"\nProximo a ser removido na posicao: "<<fil.inicio;
 cout<<"\nValor\tPosicao\n";
 if(fil.inicio<fil.final)
 {for(int x=fil.inicio;x<fil.final;x++)
 cout<<"\n"<<fil.circular[x]<<"\t"<<x;
 }
 }
}
Espero que você tenha entendido esta aula porque a Fila é uma estrutura importante. Bem, todas são.
Foi uma aula muito ilustrada porque estou fazendo de tudo para que você se apaixone por Estruturas de Dados. Sei que não é fácil, mas se você se dedicar bastante, vai conseguir.
Saiba que estamos aqui para lhe ajudar no que for possível e preciso que você se dedique um pouquinho mais porque essas três últimas aulas têm um conteúdo mais complicado, mas tenha certeza que vou tentar, descomplicar. 
Até a próxima aula.
SÍNTESE DA AULA
Nesta aula, você: 
Compreendeu a importância da Estrutura de Dados Fila simples e circular;
Compreendeu e usou várias operações que podem ser feitas com a Fila simplese circular;
Analisou aplicações da Fila e acompanhou a execução de programas;
REGISTRO DE PARTICIPAÇÃO
1.Considerando que Enqueue() coloca um elemento da FILA, Dequeue() remove um elemento da Fila e firstElem() retorna o primeiro elemento sem removê-lo, assinale a resposta que indica o número que aparecerá após a sequencia de comandos abaixo, sabendo-se que os números deverão ser inseridos na sequencia em que se apresentam.
Sequencia: Enqueue() / firstElem()/ Enqueue()/ Enqueue()/ Dequeue()/ firstElem()/ Dequeue()/firstElem()
Números: 29/ 8/1918/ 13 / 18
 1) 1918 
 2) 29 
 3) 1989 
 4) 8 
2.Analise as afirmativas e assinale a opção correta.
I) A implementação de FILAS só pode ser feita por matrizes. 
II) A Fila é uma estrutura de dados não linear. 
III) A remoção de um elemento da Fila é no início.
IV) É proibido exibir o total de elementos na Fila.
V) Inicializar é atribuir valores a variáveis que controlam o inicio e o fim da Fila.
 1) II e III estão corretas. 
 2) I e IV estão corretas. 
 3) III e V estão corretas. 
 4) I, II e V estão corretas. 
 
3.Assinale a sigla que representa o critério usado pela FILA para inserção/remoção dos elementos.
 1) FIFO 
 2) LIFO 
 3) FERD 
 4) DEQUE 
GABARITO
1-1; 2-3; 3-1
AULA 8: ALOCAÇÃO DINÂMICA / LISTAS ENCADEADAS - INTRODUÇÃO
OBJETIVOS DA AULA 
Ao final desta aula, você será capaz de: 
1. Conceituar ponteiro; 
2. Conceituar os operadores & e 
3. Manipular ponteiro com os operadores & e 
4. Compreender o uso do operador ->;- 
5. Conceituar alocação dinâmica de memória;
6. Compreender o uso de ponteiro no estudo de Listas Lineares;
7. Conceituar listas lineares simplesmente encadeadas;
8. Representar listas lineares simplesmente encadeadas com poucos nodos;
 
 
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 vaiáveis locais, globais, matrizes homogêneas e matrizes heterogêneas.
 
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.
Afigura abaixo representa essas quatro regiões da memória principal e não significa que sempre será assim como afirma Schildt, H(1996, p.14):
“ 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.
No momento, só falaremos das funções desses operadores porque como usá-los, só depois que estudarmos ponteiros.
Defendo a teoria de que não se pode saber superficialmente um conceito que permeia a alocação dinâmica de memória. 
 
Não seremos só programadores e, sendo assim, temos que entender o que se passa na memória principal para  que possamos desenvolver códigos sem problemas e mais eficientes. Se isso não fosse verdade, nos nossos cursos não teríamos disciplinas tais como Organização de Computadores, Sistemas Operacionais entre outras.
 
Não posso me aprofundar no estudo de ponteiros, mas vou tentar explicar de uma forma simples para que você possa caminhar sozinho, se assim desejar.
A MP 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 declaramos 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.
Uma boa dica para entender como funciona a variável ponteiro.
Você leu no jornal um anúncio de uma loja que vende notebook, muito facilitado, para alunos que estão cursando ADS ou Sistemas de Informação.
Ao ligar para a loja, você pede o endereço e anota na sua agenda. Então, sua agenda aponta para a loja, visto que está anotado o endereço da loja (&loja).
Para dar uma olhada em outros modelos, você resolve ir até a loja(&loja) e chegando lá, viu o que estava dentro da loja(*loja).
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ê for alocar para armazenar um dado, deverá fazê-lo com new, mas se for para armazenar um array, use new[ ] 
Operador delete
Sua função é retornar para 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 nos dará garantia de que tudo ocorrerá sem problemas 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 mias 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 ela se torne nula.
A FRAGMENTAÇÃO EXTERNA OCORRE QUANDO UM BLOCO DE MEMÓRIA É ALOCADO E DEPOIS DESALOCADO.
A FRAGMENTAÇÃO INTERNA OCORRE POR ERRO DE DIMENSIONAMENTO DO BLOCO.
A VARIÁVEL PONTEIRO
& Precede o nome da variável, significando o endereço dela e não seu conteúdo.
* Precede o nome da variável na declaração para indicar que é uma variável ponteiro.
 Em outros momentos, precede a variável ponteiro para indicar o conteúdo da variável apontada pelo ponteiro.
Como se declara?
tipo *nomeDaVariávelPonteiro ; 
O que armazena?
O endereço de uma variável 
tipo - Quando declaramos uma variável ponteiro, precisamos informar o tipo de variável que será apontada pelo ponteiro,isto é, char, int, float ou double.
Por que temos que usar o * antes do nome da variável ponteiro?
Porque o asterisco é o caracter(alguns autores chamam de operador) que sinaliza que a variável está sendo declarada como ponteiro.
Com se inicializa uma variável ponteiro?
A inicialização poderá acontecer na declaração da mesma forma que fazemos com as variáveis simples ou depois da declaração através de um comando de atribuição onde a variável ponteiro receberá o endereço da variável que ela irá apontar.
int a, *pa;
a=23;
pa= &a;
ou
int a=23, *pa=&a ; 
ou
cout <<ano <<endl; 1989
cout<<&ano <<endl; 0x22ff74
cout<<ptrano <<endl; 0x22ff74
cout<<&ptrano<<endl; 0x22ff70
cout<<*ptrano<<endl; 1989
PONTEIROS PARA ESTRUTURAS
Nada nos impede de passarmos uma estrutura para uma função, entretanto isso sobrecarregaa pilha, aumentando o tempo de transferência dos dados entre as funções. 
 
Para minimizar esse problema e tendo em vista 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.
 
Para se atribuir o endereço de uma estrutura a um ponteiro, usamos um comando de atribuição:
Existem duas formas de se acessar o membro através do ponteiro. Usando o operador -> ou o *.
EXEMPLO 1
#include <iostream>
#include <cstring>
using namespace std;
struct data
{
 	 int dia, mes, ano;
};
int main()
{
 	data dataNasc, *ptr;
 	int d;
 	cout<<"\nDigite a data de nascimento no formato ddmmaa: ";
 	cin>>d;
 	ptr=&dataNasc;
 	ptr->dia=d/10000;
 	ptr->mes=(d/100 % 100);
 	ptr->ano=d%100;
 	cout<<"\n\nSua data de nacimento "<<ptr->dia<<"/ "<<ptr->mes<<"/ "<<ptr->ano;
 	cout<<"\n\n";
 	system("pause");
}
ANALISANDO O CÓDIGO
EXEMPLO 2
#include <iostream>
#include <cstring>
using namespace std;
struct CADASTRO
{
 	 char nome[30];
 	 float nota;
};
void exibe (CADASTRO *m);
int main()
{
 	CADASTRO aluno, *p;
 	cout<<"\nNome do aluno: ";cin.getline(aluno.nome,30);
 	cout<<"\nNota do aluno: ";cin>>aluno.nota;
 	p=&aluno;
 	exibe (p);
 	cout<<"\n\n"; system("pause");
}
void exibe (CADASTRO *m)
{
 	 int c;
 	 for (c=0;c<strlen(m->nome);c++)
 	 m->nome[c]=toupper(m->nome[c]);
 	 cout<<"\nDados do Aluno\n";
 	 cout<<"\n\nNome: "<<m->nome;
 	 cout<<"\nNota: "<<(*m).nota;
}
PONTEIRO E ALOCAÇÃO DINÂMICA
No início desta aula, vimos que a alocação dinâmica da memória na linguagem C++ é feita pelo operador new, mas como é retornado o primeiro endereço do bloco alocado, precisamos armazenar esse endereço e é ai que está a importância, no processo,  da variável ponteiro.
  
Declarando e Inicializando um ponteiro para alocar, dinamicamente, a memória.
Vamos entender cada parte destas duas sintaxes.
1ª SINTAXE
tipo – é o tipo do ponteiro.
* - operador que sinaliza que a variável é um ponteiro.
new – aloca a memória dinamicamente.
tipo – é o tipo do dado, compatível com o tipo do ponteiro.
2ª SINTAXE
tipo – é o tipo do ponteiro.
* - operador que sinaliza que a variável é um ponteiro.
new – aloca a memória dinamicamente.
tipo[...] – é o tipo do dado, compatível com o tipo do ponteiro. Aloca uma quantidade especificada dentro dos colchetes.
EXEMPLOS
	float *ptF= new float;
	Declara e inicializa um ponteiro que aponta para um lugar que armazena dado real. O ponteiro armazenará o primeiro endereço do bloco que armazena dado real.
	int *ptI= new int(25);
	
Declara e atribui o valor 25 ao endereço apontado por ptI.
	int *pt=new int[50];
	Declara e inicializa um ponteiro que aponta para array. O ponteiro armazenará o primeiro endereço do bloco que armazena dados inteiros.
EXEMPLO
#include <iostream>
using namespace std;
int main()
{
	int *pt = new int (1024);
	cout<<"\nValor que foi inicializado: "<<*pt<<"\n\n";
	system ("pause");
}
PONTEIRO E MATRIZ DE ESTRUTURAS
A relação entre matrizes e ponteiros é muito grande e, infelizmente, não temos como nos aprofundar nos assunto. Entretanto, como vamos trabalhar com estruturas, resolvi apresentar este exemplo de matrizes de estruturas com alocação dinâmica porque vou mostrar como acessar um elemento da matriz usando o ponteiro com deslocamento
Atenção para os passos.
Observe a struct e a linha de alocação dinâmica.
 
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<<"\nEndereco da primeira struct da matriz:"<<&ptr[0];
count<<"\nEndereco da segunda struct da matriz:"<<&ptr[1];
Observe que  de0x 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 pata int e 4 endereços pata float).
III.	(ptr+x) -> matric é equivalente à ptr[x].matric porque você pode tratar o ponteiro como se fosse uma matriz e a matriz, com se fosse um ponteiro:
#include <iostream>
#include <cstring>
using namespace std;
struct dados
{
	int matric;
	float sal;
};
int main()
{
	int x, nfunc;
	cout<<"\nQuantos funcionarios? ";
	cin>>nfunc;
	dados *ptr=new dados[nfunc];
	for(x=0; x<nfunc;x++)
	{
		cout<<"\nDigite a matricula do funcionario: ";
		cin>>ptr[x].matric;
		cout<<"\nDigite o salario do funcionario: ";
		cin>>ptr[x].sal;
	}
	system ("cls");
	cout<<"\nMatric\tSalario\n";
	for(x=0;x<nfunc;x++)
		cout<<"\n"<<(ptr+x)->matric<<"\t"<<(ptr+x)->sal;
	cout<<"\n\n"; system("pause");
}
Observe o código e a saída
Nosso estudo sobre ponteiros procurou lhe dar embasamento para que você possa começar seu estudo sobre as Estruturas de Dados Dinâmicas.
 
Não teve como objetivo se aprofundar na aritmética dos ponteiros, ponteiros para funções, matrizes de ponteiros, ponteiros para ponteiros, etc.
 
Como vamos usar esses conceitos muitas vezes, creio que acabaremos dominando com muita facilidade.
 
Vamos para a segunda parte da aula!!!
LISTAS ENCADEADAS
Nas aulas 5, 6 e 7 tivemos oportunidade de estudar as estruturas de dados lineares Lista, Pilhas e Filas com seus elementos armazenados na memória de forma contígua e estática.
Aprendemos também que as inserções e remoções nas Pilhas e nas Filas acontecem em extremidades determinadas enquanto que nas Listas, não existem regras sobre isso.
Na aula de hoje, começaremos a estudar as estruturas dinâmicas e, por essa razão, tivemos que conhecer a variável ponteiro porque sem ela, seria impossível implementar a alocação dinâmica, visto que o operador new , retorna, se bem sucedida a alocação, o primeiro endereço do bloco que precisa ficar armazenado. Em resumo, sem fazer trocadilho, tudo muito bem encadeado: 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, também conhecidas como listas ligadas, são consideradas uma das mais importantes estruturas de dados. Talvez a forma livre de inserir e remover elementos em qualquer posição e as aplicações importantes que fazem uso dela tenham lhe dado esse status.
Podemos enumerar algumas dessas aplicações:
Listas de debates;
Gerenciamento de memória;
Alocação encadeada de arquivos seqüenciais na tentativa de eliminar a fragmentação externa de um HD, entre outras.
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 Listas Encadeadas podem ser:
Encadeamento Simples–	cada nó é ligado por um ponteiro, permitindo que ela seja percorrida(cruzada) do primeiro ao último elemento.
Encadeamento duplo–	cada nó é ligado por dois ponteiros. Esse tipo de lista permite um cruzamento igual ao da Lista Simples, mas acrescenta a possibilidade da lista ser percorrida(cruzada) de trás para frente. 
Encadeadas circulares–	onde o último nó é ligado ao primeiro, significando que não existe NULL. 
As Listas Encadeadas Simples são formadas por nós que têm o seguinte o formato:
Pela figura, podemos observar que cada nó tem duas partes. Uma, armazena a informação e a outra, o endereço do próximo 
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 chegarmosmais próximos do nó da Lista, poderíamos nomear esta estrutura de no.
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.
Concordo que é meio complexo esse questionamento, mas se você fizer algumas leituras desse parágrafo, vais acabar entendendo que não tinha alternativa já que o ponteiro tinha que ser do mesmo tipo que o nó.
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++”. 
Agora, vamos construir a struct.
Pensei que só poderia ter um membro fora o ponteiro. Agora você diz que podem ser vários?
Fique tranqüila. Você já vem treinando struct desde a Aula 3.
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: nodo *Lista = NULL;
INSERIR NÓ
Após a criação da Lista, os nós podem ser inseridos, uma 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ó?
Como Insere na frente e Remove na frente, é a mesma filosofia da PILHA.
Etapas para inserir um nó no início da Lista
Foi criado um novo nó;
O novo nó foi inicializado com valor 15;
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;
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
O ponteiro que sinaliza o primeiro nó da Lista é reajustado para que o segundo nó passe a ser o primeiro.
Algo que você não poderia saber: 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).
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.
Mas, não vou assustá-lo. Vamos dar um passo de cada vez para que possamos aprender tudo. Afinal, essa parte da matéria é mais abstrata do que todas as outras e, se só escrevermos muito conteúdo, creio que não ficará bem fixado. Por essa razão, optei por um tipo de aula diferente das demais, isto é, explica e exemplifica.
Para que possamos fazer o passo a passo, vamos supor que nosso nó tenha como membro um número inteiro fora o ponteiro, é claro e vamos construir uma lista com um nó.
CRIANDO UMA LISTA DE UM NÓ
1) Declarando a struct 
2) Criando nó 
3) Atribuindo valores aos membros 
4) Exibindo 
5) Liberando 
#include <iostream>
using namespace std;
int main()
{
	struct nodo
	{
		int info;
		struct nodo*prox;
	};
	nodo *no1 = new nodo;
	no1->info=23;
	no1->prox=NULL;
	//exibindo
	cout<<"\nValor do no 1: "<<no1->info;
	//Liberando
	delete no1; no1=0;
	cout<<"\n\n"; system("pause");
}
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.
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
	struct nodo
	{
		int info;
		struct nodo*prox;
	};
	nodo *lista = new nodo;//Criando o primeiro no
	lista->info=23;
	lista->prox=NULL;
	lista->prox=new nodo;//Criando o segundo no
	lista->prox->info=15;
	lista->prox->prox=NULL;
	//exibindo
	cout<<"\nValor do primeiro no: "<<lista->info;
	cout<<"\nValor do segundo no: "<<lista->prox->info;
	cout<<"\nValor do endereco do primeiro no> "<<lista;
	cout<<"\nValor do endereco do segundo no> "<<lista->prox;
	//Liberando
	delete lista;
	cout<<"\nEndereco armazenado na variavel lista, mesmo depois do delete: "<<lista;
	lista=0;
	cout<<"\nEndereco armazenado na variavel lista, depois da atribuicao: "<<lista;
	cout<<"\n\n"; system("pause");
}
O trecho abaixo cria e atribui valores aos membros do struct, lembrando que o membro próximo é um ponteiro que irá receber o valor NULL(pode ser 0), supondo que não tem mais elemento na lista. 
13 nodo* lista=new nodo; 
14 lista->num=23;
15 lista->prox=NULL;
O trecho abaixo exibe na tela os valores armazenados nos membros num e os endereços de cada nó.
Reforçando que o endereço que retorna da alocação é o primeiro do bloco logo, é o endereço do primeiro nó e como o membro ponteiro aponta para o outro nó, para sabermos o endereço do segundo nó,  chamamos pelo primeiro membro ponteiro do primeiro nó.
 
21 cout<<"\nValor do primeiro no: "<<lista->num;
22 cout<<"\nValor do segundo  no: "<<lista->prox->num; 
23  cout<<"\n\nValor do endereco do primeiro no: "<<lista;    
24  cout<<"\n\nValor do endereco do segundo  no: "<<lista->prox;
Sei que nem tudo pode ser abordado em uma aula, mas vou apresentar agora como se insere um nó na frente de uma Lista e como se insere um nó atrás de uma Lista. Não usaremos ainda função.
Acredito que já tivemos oportunidade de entendermos o básico de uma Lista Encadeada e que estamos prontos para a 2a etapa.
Nesta etapa, os códigos não estão com funções porque espero que vocês as construam até a próxima aula, visto que apresentarei três programas que neles já estão presentes os trechos que deverão se transformar em funções.
 Para dar uma ajuda maior, darei destaque desses trechos para vocês.
Escolhi os trechos de inserção de nó na Frente da Lista, listar e remover nó no Início da Lista para começar.
1) Trecho principal do programa -Insere um nó na Frente da lista
 
Análise do código
I) Linha 11 
nodo *temp, *lista=NULL;   
Declara  temp que servirá para receber o novo nó e lista  que é inicializada, visto que recebeu NULL. Já vimos que podemos criar uma lista vazia.
II) Linhas 13-16 – Atenção para esse trecho porque ele irá se transformar em uma função.
13   temp = new nodo;   //aloca dinamicamente um nó do tipo nodo
14   temp->num = 23;   // atribui 23 ao membro num 
15   temp->prox=lista ; // atribui o endereço de lista ao membro ponteiro prox
16   lista= temp;           // atualiza lista
#include <iostream>
#include <cstdlib>
using namespace std;
struct nodo
{
	int num;
	struct nodo*prox;
};
int main()
{
	nodo *temp,*lista=NULL;
	//Criando o primeiro no
	temp = new nodo;
	temp->num = 23;
	temp->prox=lista;
	lista=temp;
	//Criando o segundo no
	temp = new nodo;
	temp->num = 13;
	temp->prox=lista;
	lista=temp;
	//Criando o terceiro no
	temp = new nodo;
	temp->num = 15;
	temp->prox=lista;
	lista=temp;
	//Criando o quarto no
	temp = new nodo;
	temp->num = 18;
	temp->prox=lista;
	lista=temp;
	//listando
	cout<<"\nInserindo no. na frente - Listando um a um\n";
	cout<<"\nValor do primeiro no: "<<lista->num;
	cout<<"\nValor do segundo