Apostila_AEDsII_ate_lista_encadeada_simples

Prévia do material em texto

AEDsII 
Material de uso restrito para a Disciplina de 
Algoritmos e Estruturas de Dados II do Curso de 
Engenharia Elétrica do UNI-BH 
 
 
 
 
 
 
 
 
 
 
 
Prof. Eduardo de Queiroz Braga 
 
 
 
2 
 
Índice: 
 
Índice: ------------------------------------------------------------------------------------------------------------ 2 
1. Ponteiros ------------------------------------------------------------------------------------------------ 3 
1.1. Operações com Ponteiros ------------------------------------------------------------------------ 4 
1.2. Aritmética de Ponteiros --------------------------------------------------------------------------- 5 
1.3. Acessando os Endereços ------------------------------------------------------------------------ 5 
1.4. Ponteiros e Vetores -------------------------------------------------------------------------------- 8 
1.5. Ponteiros e Matrizes ------------------------------------------------------------------------------ 11 
1.6. Ponteiros e Strings -------------------------------------------------------------------------------- 14 
1.7. Estruturas e Ponteiros para Estruturas ------------------------------------------------------- 15 
1.8. Ponteiros para Funções ------------------------------------------------------------------------- 24 
2. A Função main() e seus argumentos ------------------------------------------------------------ 25 
2.1. A função void main(int argc, char *argv[]) -------------------------------------------------- 25 
3. Alocação Dinâmica de Memória ------------------------------------------------------------------ 26 
4. Algoritmos de Ordenação e Pesquisa----------------------------------------------------------- 28 
4.2. Ordenação Bolha ---------------------------------------------------------------------------------- 28 
4.3. Ordenação por seleção -------------------------------------------------------------------------- 29 
4.4. Ordenação por inserção ------------------------------------------------------------------------- 29 
4.5. Ordenação Quicksort ----------------------------------------------------------------------------- 30 
5. Estruturas de Dados -------------------------------------------------------------------------------- 32 
5.1. Filas -------------------------------------------------------------------------------------------------- 32 
5.2. Filas Circulares ------------------------------------------------------------------------------------ 34 
5.3. Pilhas de dados ------------------------------------------------------------------------------------ 36 
5.4. Listas de dados com encadeamento --------------------------------------------------------- 37 
5.5. Árvores e Árvores Binárias ---------------------------------------------------------------------- 40 
5.6. Matrizes Esparsas -------------------------------------------------------------------------------- 40 
 
 
 
 
 
 
 
3 
 
1. Ponteiros 
Ponteiros são usados em situações em que é necessário conhecer o endereço onde está 
armazenada a variável e não o seu conteúdo. Um ponteiro é uma variável que contém um 
endereço de memória e não o conteúdo da posição. 
A memória de um computador pode ser vista como uma seqüência de bytes, cada um com 
seu próprio endereço. Não há dois bytes com o mesmo endereço. O primeiro endereço 
é sempre 0 e o último geralmente é uma potência de 2. Por exemplo, um computador com 
memória igual a 16 Mbytes tem 16x1024x1024 bytes. 
A Tabela 1 mostra um exemplo de um trecho de memória que contém duas variáveis num e 
res inteiras de tipo longo (4 bytes cada uma). Observar que os endereços estão pulando de 
quatro em quatro já que as variáveis são inteiras de tipo longo. Uma possível declaração 
destas variáveis dentro de um programa C/C++ poderia ser: 
long int num=10, res=120; 
 
Tabela 1: Mapa de Memória 
Endereços (em decimal) Conteúdo Variável 
996 --- --- 
1000 10 num 
1004 120 res 
Uma função pode receber os ponteiros que apontem para os endereços dos parâmetros. 
Assim, esta função pode modificar diretamente os conteúdos destas variáveis. Ou seja, 
ponteiros fornecem os meios pelos quais as funções podem modificar seus argumentos. 
 Uma aplicação importante de ponteiros é apontar para áreas de memória que são 
administradas durante a execução do programa. Com ponteiros é possível alocar as 
posições de memória necessárias para armazenamento de vetores somente quando o 
programa estiver rodando. O programador pode reservar o número exato de posições que 
o programa requer. 
Ponteiros são um dos aspectos mais fortes e mais perigosos de C/C++. Por exemplo, 
ponteiros não inicializados, também chamados de ponteiros selvagens, podem provocar 
uma quebra no sistema. 
 
 
 
 
 
 
 
4 
 
1.1. Operações com Ponteiros 
1.1.1. Declaração de Ponteiros 
Antes de serem usados os ponteiros precisam ser declarados, assim como variáveis. A 
forma geral da declaração de um ponteiro é a seguinte: 
 
tipo *nome; 
 
Onde tipo é qualquer tipo válido em C/C++ e nome é o nome da variável ponteiro. Por 
exemplo: 
 
int *res; /* ponteiro para uma variavel inteira */ 
float *div; /* ponteiro para uma variavel de ponto flutuante */ 
 
 
1.1.2. Os Operadores de Ponteiros 
Existem dois operadores especiais para ponteiros: * e &. Os dois operadores são unários, 
isto é, requerem somente um operando. 
 O operador & devolve o endereço de memória do seu operando. Por exemplo, 
pint = &soma; /* o endereco de soma e carregado em pint */ 
 
No exemplo seguinte considere a Tabela 1. Após a execução do trecho de programa 
abaixo a variável ponteiro p termina com o valor 1000. 
 
p = # 
 
O operador * é o complemento de &. O operador * devolve o valor da variável localizada no 
endereço que o segue. Por exemplo, o comando 
 
num = *p; 
significa que a variável num recebe o valor apontado por p. Estes operadores não devem 
ser confundidos com os já estudados em capítulos anteriores. O operador * para 
ponteiros não tem nada a ver com o operador multiplicação. O operador ponteiro * é 
 
 
5 
 
unário e, como o operador &, tem precedência maior que do que todos os operadores 
aritméticos. 
 
Observação: Nunca acesse o conteúdo de um ponteiro antes de inicializá-lo. 
 
1.2. Aritmética de Ponteiros 
Atribuição de Ponteiros 
 Do mesmo modo que uma variável comum, conteúdo de um ponteiro pode ser passado 
para outro ponteiro do mesmo tipo. As variáveis ponteiros devem sempre apontar para os 
tipos de dados corretos. Uma variável ponteiro declarada como apontador de dados 
inteiros deve sempre apontar para dados deste tipo. 
Observar que em C/C++ possível atribuir qualquer endereço a uma variável ponteiro. Deste 
modo é possível atribuir o endereço de uma variável do tipo float a um ponteiro inteiro. No 
entanto, o programa não irá funcionar da maneira correta. 
Por exemplo, no trecho de programa abaixo o endereço do terceiro elemento do vetor v é 
carregado em p1 e o endereço da variável i é carregado em p2. Além disso, no final o 
endereço apontado por p1 é carregado em p2. Os comandos cout imprimem os valores 
apontados pelos ponteiros respectivos. 
#include<iostream> 
#include<cstdlib> 
 
using namespace std; 
 
int main() 
{ 
 int vetor[] = { 10, 20, 30, 40, 50 }; 
 int *p1, *p2; 
 int i = 100; 
 
 p1 = &vetor[2]; 
 cout<<"*p1 = "<<*p1<<endl; 
 p2 = &i; 
 cout<<"*p2 = "<<*p2<<endl; 
 p2 = p1; 
 cout<<"*p2 = "<<*p2<<endl; 
 
 system("Pause"); 
 return 0; 
} 
1.3. Acessando os Endereços 
O programa abaixo faz com que o endereço da variável x seja carregado no ponteiro p. Em 
seguida o programa imprime o que está apontado por p. 
 
 
6 
 
#include<iostream>#include<cstdlib> 
 
using namespace std; 
 
int main() 
{ 
 float x=3.14, *p; 
 
 p = &x; //Ponteiro que carrega o endereço da variável x 
 cout<<"*p = "<<*p<<endl;; 
 
 system("Pause"); 
 return 0; 
} 
 
 
 
1.3.1. Incrementando e Decrementando Ponteiros 
 O exemplo abaixo mostra que operações de incremento e decremento podem ser 
aplicadas em operandos. O primeiro cout imprime 30 o segundo 40 e o terceiro 50. 
int main() 
{ 
 int vetor[] = { 10, 20, 30, 40, 50 }; 
 int *p1; 
 
 p1 = &vetor[2]; 
 cout<<*p1<<endl; 
 p1++; 
 cout<<*p1<<endl; 
 p1 = p1 + 1; 
 cout<<*p1<<endl; 
 
 system("Pause"); 
 return 0; 
} 
 
Pode parecer estranho que um endereço que aponte para um número inteiro, que é 
armazenado em quatro bytes, seja incrementado por um e passe para apontar para o 
próximo número inteiro. A resposta para isto é que sempre que um ponteiro é 
incrementado (ou decrementado) ele passa a apontar para a posição do elemento seguinte 
(ou anterior). Do mesmo modo somar três a um ponteiro, faz com que ele passe apontar 
para o terceiro elemento após o atual. Portanto, um incremento em um ponteiro que aponta 
para um valor que é armazenado em n bytes faz que n seja somado ao endereço. 
 É possível se usar o seguinte comando 
*(p+1)=10; 
 
 
 
7 
 
Este comando armazena o valor 10 na posição seguinte àquela apontada por p. É possível 
somar-se e subtrair-se inteiros de ponteiros. A operação abaixo faz com que o ponteiro p 
passe a apontar para o terceiro elemento após o atual. 
p = p + 3; 
 
A diferença entre ponteiros fornece quantos elementos do tipo do ponteiro existem entre os 
dois ponteiros. No exemplo abaixo é impresso o valor 3. 
int main() 
{ 
 float vetor[] = { 1.0, 2.0, 3.0, 4.0, 5.0 }; 
 float *p1, *p2; 
 
 p1 = &vetor[2]; // endereco do terceiro elemento 
 p2 = &vetor; // endereco do primeiro elemento 
 cout<<"Diferenca entre ponteiros %d\n"<<p1-p2; 
 
 system("Pause"); 
 return 0; 
} 
 
Observação: Não é possível multiplicar ou dividir ponteiros, e não se pode adicionar ou 
subtrair o tipo float ou o tipo double a ponteiros. 
 
 
 
1.3.2. Comparação de Ponteiros 
É possível comparar ponteiros em uma expressão relacional. Mas, só podemos comparar 
ponteiros de mesmo tipo. O trecho de programa abaixo ilustra um exemplo deste tipo de 
operações. 
char *c, *v; 
 
cin>>*c>>*v; 
if (c == v) // Cuidado com esse tipo de comparação!!! 
 cout<<"As variáveis estao na mesma posicao.\n"; 
else 
 cout<<"As variaveis nao estao na mesma posicao.\n"; 
 
 
1.3.3. Indireção Multipla 
 
 
 
8 
 
Ponteiros podem apontar para outro ponteiro que aponta para o valor final. Essa 
situação é chamada de indireção múltipla, ou também de ponteiros para ponteiros. O 
valor de um ponteiro convencional é o endereço de uma variável que contém um 
determinado valor. Já para o caso de um ponteiro para ponteiro, o primeiro ponteiro 
contém o endereço do segundo ponteiro, que finalmente contém o endereço da variável 
que contém o valor desejado. Observe a figura. 
 
 
Figura 1: Indireção Simples e Múltipla 
 
 
 
Exemplo: Observe o código abaixo: 
 
#include <stdio.h> 
 
Void main(void) 
{ 
 int x, *p, **q; 
 x=10; 
 p=&x; 
 q=&p; 
 cout < “O valor de x eh ”<<**q; 
} 
 
Observamos que o valor 10 é atribuído à variável x. Já p é um ponteiro do tipo int que 
passa a conter o endereço da variável x. Por outro lado, q é um ponteiro do tipo int que 
contém o endereço do ponteiro p. Isso é um caso de indireção múltipla. 
 
1.4. Ponteiros e Vetores 
 
Ponteiros e Vetores estão fortemente relacionados na linguagem C/C++. O nome de um 
vetor é um ponteiro que aponta para a primeira posição do vetor e todas as operações já 
mencionadas para ponteiros podem ser executadas com um nome de vetor. Por exemplo, 
a declaração: 
 
int v[100]; 
 
 
9 
 
 
declara um vetor de inteiros de 100 posições. Se p recebe o ponteiro para a primeira 
posição de v como na declaração abaixo: 
 
int *p=v; 
As seguintes declarações serão idênticas: 
v[i] == *(p+i) 
&v[i] == p+i 
 
Também são idênticas as próximas declarações: 
 
v[i] == *(v+i) 
&v[i] == v+i 
O exemplo ilustrado abaixo mostra as duas notações sendo usadas para imprimir o mesmo 
vetor. 
int main() 
{ 
 float v[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}; 
 int i; 
 for (i=0; i<9; i++) cout<<v[i]; 
 cout<<endl; 
 for (i=0; i<9; i++) cout<<*(v+i); 
 cout<<endl; 
 
 system("Pause"); 
 return 0; 
} 
Existe uma diferença fundamental entre declarar um conjunto de dados como um vetor ou 
através de um ponteiro. Na declaração de vetor, o compilador automaticamente reserva um 
bloco de memória para que o vetor seja armazenado. Quando apenas um ponteiro é 
declarado a única coisa que o compilador faz é alocar um ponteiro para apontar para a 
memória, sem que espaço seja reservado. 
O nome de um vetor é chamado de ponteiro constante e, portanto, não pode ter o seu 
valor alterado. Assim, os comandos abaixo não são válidos: 
 
int main() 
{ 
 int list[5], i; 
 
 list = &i; // O ponteiro list nao pode ser modificado 
 //recebendo o endereco de i 
 
 
10 
 
 
 list++; // O ponteiro list nao pode ser incrementado 
 
} 
Para percorrer um vetor além da maneira mostrada no exemplo é possível usar um 
ponteiro variável como ilustrado no exemplo abaixo. 
int main() 
{ 
 
 float v[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}; 
 int i; 
 float *p; 
 
 for(i=0; i<9; i++) cout<<v[i]<<" "; 
 cout<<endl; 
 for(i=0; i<9; i++) cout<<*(v+i)<<" "; 
 cout<<endl; 
 for(i=0, p=v; i<9; i++, p++) cout<<*p<<" "; 
} 
Observe como o ponteiro p recebe seu valor inicial e a maneira que ele é incrementado. 
 
 
 
11 
 
1.5. Ponteiros e Matrizes 
Um ponteiro aponta para uma área de memória que é endereçada de maneira linear. Deste 
modo, é necessário mapear o endereço de cada elemento na matriz, que é dado por linha 
coluna, em um endereço linear. 
Considere uma matriz chamada matriz de tamanho LIN,COL que poderia ser declarada e 
ter um de seus elementos lidos da seguinte maneira: 
#include<iostream> 
#include<cstdlib> 
 
using namespace std; 
 
const int LIN=3; 
const int COL=4; 
 
void leMatriz(float m[LIN][COL]); 
void imprimeMatriz(float m[LIN][COL]); 
 
int main() 
{ 
 float matriz[LIN][COL]; 
 
 cout<<"Entre com os dados da Matriz: \n"; 
 leMatriz(matriz); 
 
 cout<<"\nMatriz digitada: \n"; 
 imprimeMatriz(matriz); 
 cout<<endl; 
 
 system("pause"); 
 return 0; 
} 
void leMatriz(float m[LIN][COL]) 
{ 
 for(int i=0; i<LIN; i++) 
 { 
 for(int j=0; j<COL; j++) 
 { 
 cout<<"Elemento ["<<i<<"]["<<j<<"]: "; 
 cin>>m[i][j]; 
 } 
 } 
} 
 
void imprimeMatriz(float m[LIN][COL]) 
{ 
 for(int i=0; i<LIN; i++) 
 { 
 for(int j=0; j<COL; j++) 
 cout<<m[i][j]<<" "; 
 cout<<endl; 
 } 
 
 
12 
 
} 
Caso o programa utilizasse ponteiros ao invés de notação de matrizes constantes o 
programa ficaria maneira apresentada a seguir. 
Neste exemplo iremos criar um vetor de ponteiros que irá armazenar o endereço inicial de 
cada linha. Portanto, para obter um elemento da matriz primeiro devemos descobrir onde 
está a linha no vetor que armazena os endereços das linhas, em seguida procuramos na 
linha o elemento. A figura 1 ilustra como será feito o armazenamento desta matriz. 
 
Figura 2: Exemplo de implementação de Matriz 
#include<iostream> 
#include<cstdlib> 
 
usingnamespace std; 
 
void alocaMatriz(float **&m, int l, int c); 
void desalocaMatriz(float **&m, int lin); 
void leMatriz(float **m, int l, int c); 
void imprimeMatriz(float **m, int l, int c); 
 
int main() 
{ 
 int lin, col; 
 float **matriz; 
 
 cout<<"Entre com numero de linhas da Matriz: "; 
 cin>>lin; 
 while (lin<=0) 
 { 
 cout<<"Numero invalido! Digite valor maior que zero!"; 
 cout<<"Entre com numero de linhas da Matriz: "; 
 cin>>lin; 
 } 
 
 
 
13 
 
 
 cout<<"Entre com numero de colunas da Matriz: "; 
 cin>>col; 
 while (col<=0) 
 { 
 cout<<"Numero invalido! Digite valor maior que zero!"; 
 cout<<"Entre com numero de colunas da Matriz: "; 
 cin>>col; 
 } 
 
 alocaMatriz(matriz, lin, col); 
 
 cout<<"Entre com os dados da Matriz: \n"; 
 leMatriz(matriz, lin, col); 
 
 cout<<"\nMatriz digitada: \n"; 
 imprimeMatriz(matriz, lin, col); 
 cout<<endl; 
 
 desalocaMatriz(matriz, lin); 
 
 system("pause"); 
 return 0; 
} 
 
 
 
 
void alocaMatriz(float **&m, int l, int c) 
{ 
 //Aloca primeiro as linhas 
 m = new float*[l]; 
 
 //Aloca depois as colunas 
 for (int i=0; i<l; i++) 
 m[i]=new float[c]; 
} 
 
void desalocaMatriz(float **&m, int l) 
{ 
 //Desaloca primeiro as colunas 
 for (int i=0; i<l; i++) 
 delete [] m; 
 //Desaloca as linhas 
 delete [] m; 
 m=NULL; 
} 
 
void leMatriz(float **m, int l, int c) 
{ 
 for(int i=0; i<l; i++) 
 { 
 for(int j=0; j<c; j++) 
 { 
 cout<<"Elemento ["<<i<<"]["<<j<<"]: "; 
 cin>>m[i][j]; 
 
 
14 
 
 } 
 } 
} 
 
 
void imprimeMatriz(float **m, int l, int c) 
{ 
 for(int i=0; i<l; i++) 
 { 
 for(int j=0; j<c; j++) 
 cout<<m[i][j]<<" "; 
 cout<<endl; 
 } 
} 
1.6. Ponteiros e Strings 
Um string constante é escrito como no exemplo: 
 "Este e um string". 
Até agora um dos usos mais comuns de strings constantes tem sido na função cout, como 
no exemplo abaixo 
cout<<"Acabou o programa.\n"; 
 
Quando uma string como este é enviado para a função o que é passado é o ponteiro para 
a string. No exemplo abaixo aparece uma função que conta o número de caracteres de um 
string. Observe o ponteiro para o string constante e na função o ponteiro *(s+tam++) 
apontando caractere a caractere. 
 
#include<iostream> 
#include<cstdlib> 
 
using namespace std; 
 
int strtam(const char *s); // Prototipo de função 
 
int main() 
{ 
 char lista[]="Isto e um teste!"; 
 
 cout<<"O tamanho do string \""<<lista<<"\" e "; 
 cout<<strtam(lista)<<" caracteres.\n"; 
 
 system("pause"); 
 return 0; 
} 
 
int strtam(const char *s) 
{ 
 
 
15 
 
 int tam=0; 
 while(*(s + tam++) != '\0'); 
 return (tam-1); 
} 
 
Outro exemplo é ilustrado abaixo. E mostra uma função que copia uma string para outra. 
#include<iostream> 
#include<cstdlib> 
 
using namespace std; 
 
int strcop(char *d, const char *o); 
 
int main() 
{ 
 char destino[20]; 
 char origem[]="string de origem"; 
 
 strcop(destino, origem);//copia o string origem para o destino 
 cout<<"Origem: "<<origem<<endl; 
 cout<<"Destino: "<<destino<<endl; 
 
 system("pause"); 
 return 0; 
} 
 
 
int strcop(char *d, const char *o) 
{ 
 while ((*d++ = *o++) != '\0'); 
 return 1; 
} 
1.7. Estruturas e Ponteiros para Estruturas 
Uma estrutura agrupa várias variáveis numa só. Imagine uma ficha pessoal que 
contenha nome, telefone, endereço, etc. A ficha é uma estrutura onde cada campo será um 
tipo de dado diferente. A estrutura é um conjunto de dados não homogêneos ou um 
agrupamento de dados não similares, para formar um novo tipo de dados. Estruturas 
constituem um recurso importante para organizar os dados utilizados por um programa 
graças à possibilidade de tratar um grupo de valores como uma única variável. 
1.7.1. Criando uma Estrutura 
Para se criar uma estrutura usa-se o comando struct. Sua forma geral é: 
struct nome_do_tipo_da_estrutura 
{ 
tipo_1 nome_1; 
tipo_2 nome_2; 
... 
 
 
16 
 
tipo_n nome_n; 
}; 
A string após o comando struct representa o nome. Esta não é a variável ainda, 
mas o tipo que ela terá quando for declarada. Ou seja, o nome_do_tipo_da_estrutura é o 
nome que se dará para a estrutura. Um primeiro exemplo: 
struct est 
{ 
int i; 
float f; 
}; 
 
est a, b; 
Neste caso, est é o nome do tipo de uma estrutura de dados que conterá as 
variáveis i e f. Foram também declaradas duas variáveis, a e b. Elas são estruturas do 
tipo est. Isto é, a possui os campos i e f, o mesmo acontecendo com b. 
Vamos criar uma estrutura de endereço: 
struct tipo_endereco 
{ 
 string rua; 
 int numero; 
 string bairro; 
 string cidade; 
 string sigla_estado; 
 long int CEP; 
}; 
Vamos agora criar uma estrutura chamada ficha_pessoal com os dados pessoais: 
struct ficha_pessoal 
{ 
 string nome; 
 long int telefone; 
 tipo_endereco endereco; 
}; 
Observe que foi declarada dentro da estrutura ficha_pessoal os campos nome, 
telefone e endereço. Esta última é uma variável chamada endereço, que é uma estrutura 
do tidp tipo_endereco, ou seja, que contém os campos rua, numero, etc. Vemos que 
uma estrutura pode fazer parte de outra ( a estrutura tipo_endereco é usada pela 
estrutura ficha_pessoal). 
Vamos agora utilizar as estruturas declaradas na seção anterior para escrever um 
programa que preencha uma ficha. 
#include <iostream> 
 
 
17 
 
#include <cstdlib> 
#include <string> 
 
using namespace std; 
 
struct tipo_endereco 
{ 
 string rua; 
 int numero; 
 string bairro; 
 string cidade; 
 string sigla_estado; 
 long int CEP; 
}; 
 
 
 
 
struct ficha_pessoal 
{ 
 string nome; 
 long int telefone; 
 tipo_endereco endereco; 
}; 
 
int main () 
{ 
 ficha_pessoal ficha; 
 ficha.nome="Fulano de Tal"; 
 ficha.telefone=4921234; 
 ficha.endereco.rua="Rua das Flores"; 
 ficha.endereco.numero=10; 
 ficha.endereco.bairro="Cidade Velha"; 
 ficha.endereco.cidade="Belo Horizonte"; 
 ficha.endereco.sigla_estado="MG"; 
 ficha.endereco.CEP=31340230; 
 
cout<<endl<<"\t**** Dados da ficha pessoal ****"; 
cout<<endl<<endl; 
cout<<"Nome:\t"<<ficha.nome<<endl; 
 cout<<"Tel:\t"<<ficha.telefone<<endl; 
 cout<<"Rua:\t"<<ficha.endereco.rua<<endl; 
 cout<<"Numero:\t"<<ficha.endereco.numero<<endl; 
 cout<<"Bairro:\t"<<ficha.endereco.bairro<<endl; 
 cout<<"Cidade:\t"<<ficha.endereco.cidade<<endl; 
 cout<<"Estado:\t"<<ficha.endereco.sigla_estado<<endl; 
 cout<<"CEP:\t"<<ficha.endereco.CEP<<endl<<endl; 
 
 system("pause"); 
 return 0; 
} 
O programa declara a variável ficha do tipo ficha_pessoal e preenche os seus 
campos. O exemplo mostra como podemos acessar um elemento de uma estrutura: basta 
usar o ponto (.). Assim, para acessar o campo telefone de ficha, escrevemos: 
 
 
18 
 
ficha.telefone = 4921234; 
Como a struct ficha pessoal possui um campo, endereco, que também é uma 
struct mas do tipo tipo_endereco, podemos fazer acesso aos campos desta struct interna 
da seguinte maneira: 
ficha.endereco.numero = 10; 
ficha.endereco.CEP = 31340230; 
Desta forma, estamos acessando, primeiramente, o campo endereco da struct ficha 
e, dentro deste campo, estamos acessando os campos numero e CEP. 
1.7.2. Matrizes de estruturas 
Uma estrutura é como qualquer outro tipo de dado no C/C++. Podemos, portanto, 
criar matrizes de estruturas. Vamos ver como ficaria a declaração de umvetor de 100 
fichas pessoais: 
ficha_pessoal fichas [100]; 
Poderíamos então acessar a segunda letra da sigla de estado da décima terceira 
ficha fazendo: 
fichas[12].endereco.sigla_estado[1]; 
Analise atentamente como isto está sendo feito. 
Podemos atribuir duas estruturas que sejam do mesmo tipo. O C irá, neste caso, 
copiar uma estrutura, campo por campo, na outra. Veja o programa abaixo: 
#include <iostream> 
#include <cstdlib> 
#include <string> 
using namespace std; 
 
struct est1 { 
 int i; 
 float f; 
}; 
 
int main () 
{ 
 // Declara primeira e segunda como structs do tipo est1 
 est1 primeira, segunda; 
 
 primeira.i = 10; 
 primeira.f = 3.1415; 
 segunda = primeira; // A segunda struct e' agora igual a primeira 
 cout<<"Os valores armazenasdos na segunda struct sao: "; 
 cout<<segunda.i<<" e "<<segunda.f<<endl; 
 
 system("pause"); 
 
 
19 
 
 return 0; 
} 
São declaradas duas estruturas do tipo est1, uma chamada primeira e outra 
chamada segunda. Atribuem-se valores aos dois campos da struct primeira. Os valores 
de primeira são copiados na estrutura segunda apenas com a expressão de atribuição: 
segunda = primeira; 
Todos os campos de primeira serão copiados na segunda. Note que isto é 
diferente do que acontecia em vetores, onde, para fazer a cópia dos elementos de um 
vetor em outro, tínhamos que copiar elemento por elemento do vetor. Para structs é muito 
mais fácil! 
Porém, devemos tomar cuidado na atribuição de structs que contenham campos 
ponteiros. Veja abaixo: 
/* Este programa é um exemplo INCORRETO para atribuir 
 estruturas que contenham ponteiros */ 
 
#include <iostream> 
#include <cstdlib> 
#include <string.h> 
using namespace std; 
 
//Define a estrutura tipo_end com dois atributos 
struct tipo_end 
{ 
 char *rua; //A struct possui um campo que é um ponteiro 
 int numero; 
}; 
 
//Função Principal 
int main() 
{ 
 tipo_end end1, end2; 
 char buffer[50]; 
 
 cout<<"\nEntre o nome da rua:"; 
 gets(buffer); // Le o nome da rua em uma string de buffer 
 
 /* Aloca a quantidade de memoria suficiente 
 para armazenar a string */ 
 end1.rua = new char[strlen(buffer)+1]; 
 strcpy(end1.rua, buffer); // Copia a string 
 cout<<"\nEntre o numero:"; 
 cin>>end1.numero; 
 
 /* ERRADO end2.rua e end1.rua estao apontando 
 para a mesma regiao de memoria */ 
 end2 = end1; 
 
 cout<<"Depois da atribuicao:\n Endereco em end1 "; 
 cout<<end1.rua<<" "<<end1.numero; 
 
 
20 
 
 cout<<"\n Endereco em end2 "<<end2.rua<<" "<<end2.numero; 
 
 /* Uma modificacao na memoria apontada por end2.rua causara' 
 a modificacao do que e' apontado por end1.rua, o que, 
 esta' errado !!! */ 
 strcpy(end2.rua, "Rua Mesquita"); 
 
 end2.numero = 1100; //Nesta atribuicao nao ha problemas 
 
 cout<<" \n\nApos modificar o endereco em end2:\n "; 
 cout<<"Endereco em end1 "<<end1.rua<<" "<<end1.numero; 
 cout<<"\n Endereco em end2 "<<end2.rua<<" "<<end2.numero; 
 
 cout<<endl<<endl; 
 system("pause"); 
 return 0; 
} 
Neste programa há um ERRO GRAVE, pois ao se fazer a atribuição end2 = end1, o 
campo rua de end2 estará apontando para a mesma posição de memória que o campo rua 
de end1. Assim, ao se modificar o conteúdo apontado por end2.rua estaremos também 
modificando o conteúdo apontado por end1.rua !!! 
1.7.3. Passando estruturas como parâmetros de funções 
No exemplo apresentado no ítem usando, vimos o seguinte comando: 
strcpy (ficha.nome,"Luiz Osvaldo Silva"); 
Neste comando um elemento de uma estrutura é passado para a função strcpy, que 
vai copiar a string “Fulano de Tal” para a variável nome (campo dentro da estrutura ficha). 
Podemos também passar uma estrutura inteira como argumento para uma função. 
Veja a seguinte função: 
void PreencheFicha (ficha_pessoal ficha) 
{ 
... 
} 
Como vemos acima é fácil passar a estrutura como um todo para a função. 
Devemos observar que, como em qualquer outra função no C/C++, a passagem da 
estrutura é feita por valor. A estrutura que está sendo passada, vai ser copiada, campo por 
campo, em uma variável local da função PreencheFicha. Isto significa que alterações na 
estrutura dentro da função não terão efeito na variável fora da função. Mais uma vez 
podemos contornar este detalhe usando ponteiros e passando para a função um ponteiro 
para a estrutura. 
 
 
21 
 
1.7.4. Ponteiros para Estruturas 
Podemos ter um ponteiro para uma estrutura. Vamos ver como poderia ser 
declarado um ponteiro para as estruturas de ficha que estamos usando nestas seções: 
ficha_pessoal *p; 
Os ponteiros para uma estrutura funcionam como os ponteiros para qualquer outro 
tipo de dados no C/C++. Para usá-lo, haveria duas possibilidades. A primeira é apontá-lo 
para uma variável struct já existente, da seguinte maneira: 
ficha_pessoal ficha; 
ficha_pessoal *p; 
p = &ficha; 
A segunda é alocando memória para ficha_pessoal usando, por exemplo, new: 
/* Programa para cadastro de pessoal */ 
#include <iostream> 
#include <cstdlib> 
#include <cstdio> 
#include <string> 
using namespace std; 
 
//Definicao da estrutura para armazenar endereco 
struct tipo_endereco 
{ 
 string rua; 
 int numero; 
 string bairro; 
 string cidade; 
 string sigla_estado; 
 long int CEP; 
}; 
 
//Definicao da estrutura para armazenar dados do pessoal 
struct ficha_pessoal 
{ 
 string nome; 
 long int telefone; 
 tipo_endereco endereco; 
}; 
 
int main () 
{ 
 ficha_pessoal *p; // Faremos a alocacao dinamica de n fichas pessoais 
 int n; 
 
 cout<<"Entre com o numero de fichas:"; 
 cin>>n; 
 fflush(stdin); 
 
 
22 
 
 
 p = new ficha_pessoal[n]; 
 
 for (int i=0; i<n; i++) 
 { 
 cout<<endl<<"\t**** Dados da ficha pessoal "<<i<<" ****"; 
 cout<<endl; 
 cout<<"Nome:\t"; 
 getline(cin,p[i].nome); 
 fflush(stdin); 
 
 cout<<"Tel:\t"; 
 cin>>p[i].telefone; 
 fflush(stdin); 
 
 cout<<"Rua:\t"; 
 getline(cin,p[i].endereco.rua); 
 fflush(stdin); 
 
 cout<<"Numero:\t"; 
 cin>>p[i].endereco.numero; 
 fflush(stdin); 
 
 cout<<"Bairro:\t"; 
 getline(cin,p[i].endereco.bairro); 
 fflush(stdin); 
 
 cout<<"Cidade:\t"; 
 getline(cin,p[i].endereco.cidade); 
 fflush(stdin); 
 
 cout<<"Estado:\t"; 
 cin>>p[i].endereco.sigla_estado; 
 fflush(stdin); 
 
 cout<<"CEP:\t"; 
 cin>>p[i].endereco.CEP; 
 fflush(stdin); 
 } 
 
 for (int i=0; i<n; i++) 
 { 
 cout<<endl<<"\t**** Dados da ficha pessoal "<<i<<" ****"; 
 cout<<endl; 
 cout<<"Nome:\t"<<p[i].nome<<endl; 
 cout<<"Tel:\t"<<p[i].telefone<<endl; 
 cout<<"Rua:\t"<<p[i].endereco.rua<<endl; 
 cout<<"Numero:\t"<<p[i].endereco.numero<<endl; 
 cout<<"Bairro:\t"<<p[i].endereco.bairro<<endl; 
 cout<<"Cidade:\t"<<p[i].endereco.cidade<<endl; 
 cout<<"Estado:\t"<<p[i].endereco.sigla_estado<<endl; 
 cout<<"CEP:\t"<<p[i].endereco.CEP<<endl; 
 } 
 cout<<endl; 
 
 delete [] p; //Atenção a alocação dinamica 
 
 
23 
 
 
 system("pause"); 
 return 0; 
 
} 
Há um detalhe importante. Se apontarmos o ponteiro p para uma estrutura qualquer 
(como fizemos em p = &ficha;) e quisermos acessar um elemento da estrutura poderíamos 
fazer: 
(*p).nome 
Os parênteses são necessários, porque o operador . tem precedência maior que o 
operador * . Porém, este formato não é muito usado. O que é comum de se fazer é 
acessar o elemento nome através do operador seta, que é formado por um sinal de 
"menos"(-) seguido por um sinal de "maior que" (>), isto é: -> . Assim faremos: 
p->nome 
A declaração acima é muito mais fácil e concisa. Para acessarmos o elemento CEP 
dentro de endereco faríamos: 
p->endereco.CEP 
Exercício: 
Seja a seguinte struct que é utilizada para descrever os produtos que estão no 
estoque de uma loja : 
struct Produto 
{ 
 char nome[30]; // Nome do produto 
 int codigo; // Codigo do produto 
 double preco; // Preco do produto 
}; 
 
a) Escreva uma instrução que declare uma matriz de Produto com 10 itens de 
produtos; 
 
b) Atribua os valores "Pe de Moleque", 13205 e R$0,20 aos membros da posição 0 e 
os valores "Cocada Baiana", 15202 e R$0,50 aos membros da posição 1 da matriz 
anterior; 
 
c) Faça as mudanças que forem necessárias para usar um ponteiro para Produto ao 
invés de uma matriz de Produtos. Faça a alocação de memória de forma que se 
possa armazenar 10 produtos na área de memória apontada por este ponteiro e 
refaça as atribuições da letra b; 
 
d) Escreva as instruções para imprimir os campos que foram atribuídos na letra c. 
 
 
 
24 
 
1.8. Ponteiros para Funções 
Muito embora uma função não seja uma variável, ela ocupa uma posição física na 
memória, e assim, essa posição pode ser atribuída a um ponteiro. O endereço de uma 
função é chamado de ponto de entrada desta função, pois, quando a função é compilada, 
o código-fonte é transformado em código-objeto e um ponto de entrada é estabelecido 
para ela. Um ponteiro para a função pode ser usado para chamar a função, pois ele pode 
apontar para o ponto de entrada desta função. 
O endereço de uma função é obtido usando o nome da função sem parênteses ou 
argumentos. Observe o exemplo: 
 
#include <stdio.h> 
#include <string.h> 
 
void check (char *a, char *b, int (*cmp) ( const char *, const char *)); 
 
void main(void) 
{ 
char s1[80], s2[80]; 
int (*p)(); 
p=srtcmp; //p recebe o ponto de entrada de strcmp 
gets(s1); 
gets(s2); 
check(s1, s2, p); //chamada da função check() 
} 
 
void check (char *a, char *v, int (*cmp) (const char *, const char *)) 
{ 
cout <<”Testando igualdade de strings \n”; 
if(!(cmp)(a,b)) cout <<”igual”; //nesse ponto, a função strcmp é chamada 
else cout << “ Diferente” ; 
} 
 
Ao ser chamada a função check(), são passados dois strings s1 e s2 e um ponteiro p para 
função - que aponta para o ponto de entrada da função strcmp() - como argumentos. Na 
função check(), a função strcmp() é chamada através do ponteiro cmp (declarado no 
protótipo dela). Lembre-se de que cmp recebeu o conteúdo de p, que na verdade é o 
endereço da função strcmp() 
 
 
25 
 
2. A Função main() e seus argumentos 
 
2.1. A função void main(int argc, char *argv[]) 
 Muitas vezes é interessante passar parâmetros para um programa ao executá-lo. Esses 
argumentos são passados através da função main(). Um argumento na linha de comando é 
a informação que segue o nome do programa na linha de comando do sistema 
operacional. 
 
Ex: ao executarmos na linha de comando do prompt do Windows, o comando dir, por 
exemplo: 
 
c>\ dir /p 
 
Neste caso, estamos passando o parâmetro /p para o programa dir (lista conteúdo de 
diretório) que fará com haja uma pausa na listagem do conteúdo do diretório (tampem 
chamado de pasta) a cada vez que a tela do prompt é preenchida. 
 
Observe o código abaixo: 
 
#include <stdio.h> 
#include <stdlib.h> 
 
void main ( int argc, char *argv[]) 
{ 
 if (argc=!2){ 
 cout << “Voce esqueceu de digitar o seu nome. \n”; 
 exit (1) 
 } 
cout<<”Ola “<<argv[1]; 
} 
 
Se o nome do programa fosse chamada.exe e seu nome fosse Carlos, então, para rodar o 
programa, você digitaria chamada Carlos e a resposta seria: 
 
Ola Carlos 
2.1.1. O char argv[ ] e o int argc 
 
Os colchetes vazios indicam que a matriz é de tamanho indeterminado. Cada item da 
matriz de strings pode ser acessado indexando o argv. Ou seja, argv armazena cada um 
dos strings separados por espaço como um elemento desta matriz. 
Já o int argc armazena quantos strings foram digitados. O menor valor para argc é 1, que 
representa o nome do programa chamado. No caso do exemplo anterior, para imprimir Ola 
fulano, argc seria igual a 2 (nome do programa mais a string fulano) 
 
 
26 
 
3. Alocação Dinâmica de Memória 
As funções básicas de alocação dinâmica de memória em C++ são new e delete. 
O exemplo abaixo ilustra o uso das função new e delete. 
#include<iostream> 
#include<cstdlib> 
 
using namespace std; 
 
int main() 
{ 
 float *v; 
 int i, tam; 
 
 cout<<"Qual o tamanho do vetor? "; 
 cin>>tam; 
 v = new float[tam]; //Aloca a quantidade pedida pelo usuario 
 for (i=0; i<tam; i++) 
 { 
 cout<<"Elemento "<<i<<" ?"; 
 cin>>v[i]; 
 cout<<"Li valor "<<*(v+i)<<"\n"; 
 } 
 delete [] v; //Para todo new deve haver sempre um delete! 
 
 system("pause"); 
 return 0; 
} 
Outro exemplo, empregando a função new está mostrado no exemplo abaixo. Observe que 
neste exemplo também mostramos situações onde um endereço de variável foi passado 
para uma função de modo que a função main() possa receber um valor (vezes). 
 
#include<iostream> 
#include<cstdlib> 
 
using namespace std; 
 
void leVetor (float *v, int tam); 
float procuraMaior (float *v, int tam, int *vezes); 
 
int main() 
{ 
 float *v, maior; 
 int i, tam, vezes; 
 
 cout<<"Qual o tamanho do vetor? "; 
 cin>>tam; 
 v = new float[tam]; 
 
 leVetor(v, tam); 
 
 
27 
 
 maior = procuraMaior (v, tam, &vezes); 
 cout<<"O maior elemento e "<<maior; 
 cout<<" e aparece "<<vezes<<" vezes.\n\n"; 
 delete [] v; 
 
 system("pause"); 
 return 0; 
} 
 
void leVetor (float *v, int tam) 
{ 
 int i; 
 
 for (i=0; i<tam; i++) 
 { 
 cout<<"Elemento "<<i<<": "; 
 cin>>*(v+i); 
 cout<<"Li valor "<<*(v+i)<<"\n"; 
 } 
} 
 
 
float procuraMaior (float *v, int tam, int *vezes) 
{ 
 int i; 
 float maior; 
 
 maior = v[0]; *vezes = 1; 
 for (i=1; i<tam; i++) 
 { 
 if (v[i] > maior) 
 { 
 maior = v[i]; 
 *vezes = 1; 
 } 
 else if (maior == v[i]) 
 *vezes=*vezes+1;; 
 } 
 return maior; 
} 
 
Cuidado para não confundir a notação: 
int *p = new int(5); // aloca espaço para um int e armazena nele o 
 //valor 5 
int *q = new int[5]; // aloca espaço para um vetor com 5 
 //elementos do tipo int 
 
 
 
28 
 
4. Algoritmos de Ordenação e Pesquisa 
 
Duas das tarefas mais fundamentais e extensivamente utilizadas em relação às 
estruturas de dados são: a ordenação e a pesquisa. Algoritmos para essas tarefas são 
utilizadas em praticamente todos os programas de bancos de dados, bem como 
compiladores, interpretadores e sistemas operacionais. 
Ordenação é o processo de arranjar um conjunto de informações semelhantes 
em uma ordem crescente ou decrescente, utilizando para isso, uma parte da 
informação chamada chave de ordenação. Por exemplo, em uma lista postal, pode-se 
escolher uma ordenação pelo CEP ou por ordem alfabética, bastando para isso 
escolher como chave o campo CEP ou o campo nome. 
 
4.1.1. Tipos de algoritmos de ordenação 
 
 
 
4.2. Ordenação Bolha 
Observe o algoritmo abaixo: 
 
//Ordenação Bolha 
void bolha (char *item, int count) 
{ 
register int a, b; 
register char t; 
 
for (a=1; a<count; ++a) { 
for (b=count-1; b>=a; b--){ 
if (item[b-1] > item[b]) { 
t = item[b-1]; 
item[b-1]=item[b]; 
item[b] = t; 
} 
} 
} 
} 
 
Neste código, item é um ponteiro para uma matriz de caracteres a ser ordenanda e count 
é o númerode elementos da matriz. Há dois laços. O laço mais externo faz a matriz ser 
varrida cout-1 vezes. Isso garante que, na pior das hipóteses, todo elemento estará na 
posição correta quando a função terminar. No laço interno são feitas as comparações e 
trocas. 
Neste algoritmo é feito sempre o mesmo número de comparações e trocas, 
independentemente de os dados estarem mais ou menos ordenados ou totalmente 
desordenados. Isso é o ponto fraco desse algoritmo. Ou seja, independente de os dados 
estarem ordenados ou não, o número de passos do algoritmo continua o mesmo. Há 
outros algoritmos cujo esforço computacional é, na pior das hipóteses igual ao Bolha. 
 
 
 
29 
 
4.3. Ordenação por seleção 
No algoritmo de ordenação por seleção, o elemento, cuja chave possua o menor valor, é 
selecionado e trocado pelo primeiro elemento da lista. Então, para os n-1 elementos 
restantes, é encontrado o elemento de menor chave, que é trocado pelo segundo. E assim 
vai até que todos os n elementos estejam ordenados. Observe o algoritmo abaixo: 
 
//Ordenação por Seleção 
void selecao (char *item, int count) 
{ 
register int a, b, c; 
int Exchange; 
char t; 
 
for (a=0; a<count; ++a) { 
 exchange = 0; 
 c = a; 
 t = item[a]; 
 for(b=a+1; b<count; ++b){ 
 if(item[b]<t) { 
 c = b; 
 t = item[b]; 
 exchange = 1; 
 } 
 } 
 if (exchange) { 
 item[c] = item[a]; 
 item[a] = t; 
 } 
 } 
} 
 
Neste caso, embora o número de comparações seja o mesmo que para o Bolha, o número 
de trocas no caso médio ( dados mais ou menos ordenados...) é muito menor. 
 
4.4. Ordenação por inserção 
Neste algoritmo, primeiramente são ordenados os dois primeiros elementos da lista. Em 
seguida, insere-se o terceiro elemento em sua ordenação em relação aos dois primeiros. 
Posteriormente, insere-se o quarto elemento em relação aos três primeiros, e assim vai até 
que todos os elementos estejam inseridos e ordenados. Observe o código abaixo: 
 
//Ordenação por Insersão 
void insercao (char *item, int count) 
{ 
register int a, b; 
register char t; 
 
for (a=1; a<count; ++a) { 
 t = item[a]; 
for (b=a-1; b>=0 && t<item[b]; b--){ 
item[b+1]=item[b]; 
item[b+1] = t; 
 
 
30 
 
} 
} 
} 
} 
 
Ao contrário dos algoritmos anteriores, o número de comparações depende de como a lista 
está inicialmente ordenada. Se a lista estiver em ordem, o número de comparações será n-
1. Já se estiver fora de ordem, será um número muito grande, se aproximando do pior caso 
que é a Ordenação Bolha. 
 
4.5. Ordenação Quicksort 
 A ordenação quicksort foi inventada por C.A.R. Hoare1 e é superior a todas as 
anteriores. Geralmente é considerado o melhor algoritmo de ordenação de propósito geral 
atualmente disponível. O quicksort é baseado na idéia de partição. O procedimento geral 
é selecionar um valor, chamado de comparando e, então, fazer a partição da lista (ou 
matriz) de dados em duas seções: a primeira com todos os elementos cuja chave seja 
menor que a chave do comparando e a segunda, com todos os elementos cuja chave seja 
maior que a do comparando. Esse processo é repetido para cada seção recursivamente, 
até que toda a lista esteja ordenada. Observe o exemplo abaixo: 
 
// Ordenação Quicksort 
void quick(char *item, count-1) 
{ 
 qs(item, 0, count-1) 
} 
 
//O quicksort propriamente dito 
void qs (char *item, int left, int rigth) 
{ 
 register int i, j; 
 char x, y; 
 i = left; j = rigth; 
 x = item[(left+rigth)/2]; 
 
 do{ 
 while (item[i]<x && i<rigth) i++; 
 while (x<item[j] && j>left) j--; 
 
 if(i<=j) { 
 y = item[i]; 
 item[i] = item[j]; 
 item[j] = y; 
 i++; j--; 
 } 
 } while (i<=j); 
 
 if (left < j) qs(item, left, j); 
 if (i < rigth) qs(item, i, rigth); 
} 
 
1
 Sir Charles Antony Richard Hoare (Tony Hoare ou C.A.R. Hoare, nascido em 11 de janeiro de 1934) é um cientista 
da computação britânico, mais conhecido pelo desenvolvimento do Quicksort em 1960, o algoritmo de ordenação mais 
utilizado no mundo, e muito provavelmente o algoritmo mais usado dentre todos os tipos existentes 
 
 
 
31 
 
 
A função quick() executa a chamada à função de ordenação principal qs(). Após a primeira 
chamada de qs(), esta é chamada recursivamente até que todas as sub-seções sejam 
feitas e os dados sejam ordenados. em todos os exemplos, a chave é um caractere que 
está em uma determinada posição da matriz do tipo char apontada pelo ponteiro item. 
 
 
 
 
 
 
32 
 
5. Estruturas de Dados 
5.1. Filas 
As filas Uma fila (queue) é uma seqüência de n nodos de um determinado tipo, cujo 
comportamento simula uma fila de registros. Normalmente representamos uma lista por 
uma seqüência de elementos separados por vírgula x1, x2, x3, ...., xn. Onde n >= 0. 
O número n de elementos é o comprimento da fila. Se n > 0 então dizemos que x1 é o 
primeiro elemento da fila e xn é o último elemento. Sendo que x1 foi primeiro elemento e o 
xn é o último elemento a chegar. 
Se n = 0 então a fila está vazia. Uma propriedade importante da fila é que os elementos 
são inseridos no final e removidos no início. O primeiro registro a ser inserido é o primeiro a 
sair :FIFO (first in first out). . 
Também chamada de lista linear de informações, que é acessada na seguinte ordem: 
 
• Primeiro elemento a entrar, primeiro elemento a sair ( FIFO:First in, First Out). 
 
Ou seja, o primeiro colocado na fila é o primeiro a sair; o segundo colocado é o segundo a 
sair, etc. Uma maneira de visualizar uma fila é imaginá-la como uma fila de banco, onde a 
última pessoa a entrar será a última pessoa a sair: 
 
 
Figura 3: Modelo do funcionamento de uma Fila 
 
Imaginemos na figura acima como uma fila de Banco, onde cada célula representa um cliente 
a ser atendido. Os clientes, naturalmente, são ordenados na ordem de chegada (aqui não 
estamos colocando casos especiais, como gestantes, etc.). É de se esperar que os clientes 
sejam atendidos na mesma ordem quem que chegaram, ou seja, o primeiro, em seguida, o 
segundo, até o último. Caso não tenha mais nenhum elemento (cliente) na fila, dizemos que a 
fila está vazia. Caso o número de elementos ultrapasse a capacidade da fila, dizemos que a 
fila está cheia e incapaz de armazenar elementos seguintes. 
 
Uma fila tem por norma as seguintes funcionalidade: 
 
• add ou store – guardar um elemento na fila 
• remove ou retrieve– retirar um elemento da fila 
• top – retornar o elemento do topo da fila 
 
 
33 
 
• full – Verificar se a fila está cheia (não pode guardar mais elementos). 
• empty – Verificar se a fila está vazia (não contém elementos) 
• construct – Colocar a fila num estado “pronto” a ser utilizada (Prepará-la) 
 
Observe um modelo de fila simples (Schildt, 1997) onde são manipulados três elementos: 
A, B e C: 
 
Figura 4: Dinâmica dos ponteiros rpos e spos 
A função qstore() armazena os elementos A e B, em seguida, a função qretrieve() retira os dois 
elementos, e por fim, a função qstore() armazena o elemento C. Observe nessa 
implementação, que há um apontador spos que é responsável por indicar a primeira posição 
vazia apta a armazenar um elemento. Há também o apontador rpos que indica a posição do 
próximo elemento a ser retirado da fila. Um vetor de elementos poderia ser utilizado para a 
construção desta fila. É bom salientar que o elemento pode ser qualquer tipo de dados, ou 
seja, poderia ser char, int, float, uma estrutura, etc. 
 
Observe este modelo para as funções de retirada e inserção de elementos na fila: 
 
 
Função de inserção de um elemento na fila onde MAX representa o tamanho da fila. No caso, 
o elemento a ser inserido é um ponteiro *q que recebe o endereço de um vetor de caracteres( 
 
 
34 
 
ex: um nome). Chamamos a atenção para o fato de que só podemos inserir um elemento se a 
fila não estiver cheia ( spos não pode apontar para MAX). 
 
 
Na função qretrieve() os elementos são retirados.É claro que só será retirado elementos se 
houver elementos na fila. Daí o teste se rpos==spos. Observe que neste modelo, como rpos 
aponta para o próximo elemento a ser retirado, o elemento a ser retornado está indicado pela 
posição dada por rpos-1. 
 
5.2. Filas Circulares 
Observe o modelo de fila circular ilustrado abaixo (Schildt, 1997). Neste tipo de fila, o termo 
circular tem uma conotação de fila sem fim, ou seja, é como se as pontas (início e fim) da fila 
ficassem ligadas, fechando um ciclo sem fim. 
 
 
Figura 5: Modelo de fila circular 
 
Vamos tomar com exemplo, os apontadores spos e rpos utilizados na fila simples do item 
anterior. Vamos imaginar que a fila tenha 12 posições como na figura acima. Neste caso, se 
chegássemos na posição MAX, mas anteriormente, tivéssemos retirado uns três elementos do 
início da fila, por que não reutilizar os espaços que vagos? É aí que entra a fila circular. Nela, 
enquanto houver espaço devido à recuperação dos dados e conseqüente atualização de rpos , 
que mostra a posição do próximo elemento a ser retirado, spos poderia avançar para reutilizar 
estes espaços. 
Em outras palavras, a fila circular somente estaria cheia se os índices de armazenamento e de 
recuperação de dados forem iguais. Caso contrário, a fila terá espaços vagos. 
 
 
35 
 
 
 
Na função abaixo, há uma diferença no comando IF, se comparado com o da função qstore() 
anterior. Neste, são avaliados se spos+1 é igual a rpos ou se spos+1 é igual a Max e 
simultaneamente, se rpos é nulo. Isso é para garantir que a posição a inserir um dado nunca 
tenha um dado já armazenado e que não tenha sido ainda retirado da fila circular. Além disso, 
há outro if para reiniciar a inserção do elemento ajustando a para o início da fila. 
 
 
 
Observe que nesse algoritmo, p é um ponteiro de ponteiro, ou seja, ele armazena um vetor de 
ponteiros cujo tamanho é definido por MAX. Assim, na linha p[spos]=q; o que está sendo 
armazenado na posição spos de p é o endereço da variável que o ponteiro q aponta. 
 
Na última linha do código acima, o valor de spos é rejustado para 0, a fim de reiniciar a fila 
circular. 
 
 
 
 
 
36 
 
5.3. Pilhas de dados 
A pilha é uma estrutura de dados em que tanto a inserção quanto a remoção de elementos 
de uma sequência se faz pela mesma extremidade, geralmente designada por topo da 
pilha. Nela, o último elemento a ser inserido será o primeiro elemento a ser retirado. Este 
conceito é conhecido como LIFO = Last-in First-out. 
 
Figura 6: Funcionamento de uma Pilha de Dados 
 
Na seqüencia de códigos abaixo, temos duas funções para a pilha. A primeira é a função 
push(), usada para a inserção de um novo elemento. Para ser inserido, deve-se verificar 
se a pilha não está cheia. Para isso é executado o teste if sobre o ponteiro tos ( top of 
stack). A segunda função é a pop(). Nela o ponteiro p é ajustado para a posição do 
elemento a ser retirado. Isso por que p aponta sempre para a primeira posição livre da 
pilha. Antes de a função retornar o valor de p, deve-se verificar se já não chegou na base 
da pilha, ou seja “pilha vazia”. Para isso é feito o teste if sobre o ponteiro bos (base of 
stack). 
 
 
 
Um PC moderno usa pilhas ao nível de arquitetura, as quais são usadas no design básico 
de um sistema operacional para manipular interrupções e chamadas de função do sistema 
operacional. Outro exemplo do uso de pilhas está na Máquina virtual Java; a própria 
linguagem Java possui uma classe denominada "Stack". Um terceiro exemplo está na 
programação de micro-controladores em assembler, onde o controle do sp (stack pointer) é 
fundamental para os desvios e chamadas de funções. 
 
 
37 
 
5.4. Listas de dados com encadeamento 
 
5.4.1. Listas Encadeadas 
Uma lista encadeada é uma estrutura de dados linear e dinâmica. Ela é composta por 
células onde cada uma aponta para a próxima célula da lista. Um exemplo de célula: 
 
 
 
Para inserir dados ou remover dados é necessário ter um ponteiro que aponte para o 1º 
elemento e outro que aponte para o fim, porque se queremos inserir ou apagar dados que 
estão nessas posições, a operação é rapidamente executada. Caso seja necessário editar 
um nó que esteja no meio da lista haverá uma busca pela posição desejada: 
 
• O link entre uma célula ou elemento para outro é feito através de um ponteiro. 
• Há um ponteiro que aponta para o início da lista e outro que aponta para a última 
célula da lista. 
• Na última célula, o seu ponteiro ponteiro aponta para NULL. 
 
 
Figura 7: Modelo de uma lista simplesmente encadeada 
 
Ao inserir um novo elemento em uma lista com encadeamento simples, teremos uma das 
seguintes situações: 
 
• Inserindo um elemento no início da lista. Neste caso, deve-se fazer um ajuste nos 
ponteiros. O ponteiro inicio deverá ser ajustado para apontar para este novo 
elemento que estamos inserindo. Além disso, o ponteiro deste elemento inserido 
deverá apontar para o antigo primeiro elemento. 
struct funcionario 
{ 
 char inscricao[10]; 
 char nome[50]; 
 float salario; 
 funcionario *proximo; 
 }; 
 
 
 
 
38 
 
 
Figura 8: Inserindo um novo primeiro elemento 
 
• Inserindo um elemento no meio da lista: Neste caso, o ponteiro do elemento anterior 
a este (de acordo com o critério de ordenação adotado) deverá apontar para aquele 
que está sendo inserido. O ponteiro deste deverá apontar para o próximo elemento. 
 
 
Figura 9: Inserindo um elemento no meio da lista 
 
• Inserindo um elemento no fim da lista. Neste caso, devemos ajustar dois ponteiros. 
O ponteiro ultimo deverá apontar para este que está sendo inserido. O ponteiro 
deste elemento deverá apontar para NULL, a fim de indicar que ele é o último 
elemento da lista. 
 
 
Figura 10: Inserindo um elemento no fim da lista 
 
Algumas vantagens da lista encadeada são: 
 
• A inserção ou remoção de uma célula, ou elemento na lista não implica a mudança 
de lugar de outros elementos; 
• Não é necessário definir, no momento da criação da lista, o número máximo de 
elementos que esta poderá ter. Ou seja, é possível alocar memória "dinâmica-
mente", apenas para o número de nós necessários. 
 
 
 
39 
 
Algumas desvantagens da lista simplesmente encadeada: 
• A manipulação torna-se mais "perigosa" uma vez que, se o encadeamento (ligação) 
entre elementos da lista for mal feito, toda a lista pode ser perdida; 
• Para acessar o elemento na posição n da lista, deve-se percorrer os n - 1 anteriores.