Livro Laboratório de Estrutura de Dados I - UEA

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Laboratório de
Estrutura de Dados I
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 1
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 2
Universidade do Estado do Amazonas
Tecnologia em Análise e Desenvolvimento de Sistemas
(Sistema Presencial Mediado)
Danielle Gordiano Valente
Danielle Pompeu Noronha Pontes
Salvador Ramos Bernardino da Silva
Laboratório de
Estrutura de Dados I
Manaus - AM
2008
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 3
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
Governo do Estado do Amazonas
Carlos Eduardo de Souza Braga
Governador do Estado
Omar José Abdel Aziz
Vice-Governador do Estado
Universidade do Estado do Amazonas
Marilene Corrêa da Silva Freitas
Reitora
Carlos Eduardo de Souza Gonçalves
Vice-Reitor
Fares Franc Abinader Rodrigues
Pró-Reitor de Administração
Osail Medeiros de Souza
Pró-Reitor de Planejamento
Edinea Mascarenhas Dias
Pró-Reitora de Ensino de Graduação
José Luiz de Souza Pio
Pró-Reitor de Pós-Graduação e Pesquisa
Rogelio Casado Marinho Filho
Pró-Reitor de Extensão e Assuntos Comunitários
Escola Superior de Tecnologia
Vicente de Paulo Queiroz Nogueira
Diretor
Curso Superior de Tecnologia em Análise e Desenvolvimento de Sistemas
(Sistema Presencial Mediado por Tecnologia)
Ednaldo Coelho Pereira
Coordenador Geral
Ângela Timótia Pereira Lima
Coordenadora Pedagógica
Nilo Barreto Falcão Neto
Coordenador de Tecnologia Educacional
Érica Lima
Projeto gráfico
Diana Maria da Câmara Gorayeb
Revisão
Valente, Danielle Gordiano.
V154lab Laboratório de Estrutura de Dados I / Danielle Gordiano Valente, Danielle
Pompeu Noronha Pontes, Salvador Ramos Bernardino da Silva – Manaus/AM: UEA
Edições, 2008.
144 p.: il. ; 23 cm.
Inclui bibliografia e anexo.
ISBN 978-85-89453-87-5
1.Estrutura de dados. 2. Programação (Computadores). I. Pontes, Danielle Pompeu
Noronha. II. Silva, Salvador Ramos Bernardino da. III. Título.
CDU (1997): 004.422.63
Ficha Técnica
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 4
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
Danielle Gordiano Valente
Professora da Escola Superior de Tecnologia (EST/UEA)
Mestre em Ciência da Computação
pela Universidade de Minas Gerais (UFMG)
Danielle Pompeu Noronha Pontes
Professora da Escola Superior de Tecnologia (EST/UEA)
Especialista em Informática
pela Universidade Federal do Ceará (UFC)
Salvador Ramos Bernardino da Silva
Professor da Escola Superior de Tecnologia (EST/UEA)
Especialista em Desenvolvimento de Sistemas pela Universidade
Federal do Amazonas (UFAM)
Perfil dos Autores
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 5
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 6
Dedico esta obra aos meus filhos adorados
Eric, Alexandre e André,
à minha mãe, presente em todas as horas
e a Deus que nos sustenta e ilumina em todos os momentos.
Danielle Gordiano Valente
Para Sofia, minha filha amada,
ao meu esposo e companheiro Pontes Filho
que sempre me incentiva.
Aos meus queridos e muito amados pais Ana e Batista,
irmãos Raphael e Thiago, por tudo que
representam em minha vida
e a Deus, sobre tudo, pois sem ele nada é possível.
Danielle Noronha Pontes
Ao meu pai (in memorian) e à minha mãe
Pela sólida base sobre a qual tudo o mais foi erguido.
Salvador Ramos Bernardino
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
Agradecimentos
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 7
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 8
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
Palavra da Reitora
Nos últimos anos, o avanço da tecnologia da informática mudou os conceitos de
ensino e de trabalho. A preocupação com o que se denominou de "inclusão digital"
passou a ser um problema urgente a ser enfrentado pelos dirigentes do País, já que
todos os processos de novas tecnologias deságuam no conhecimento de informática.
No Amazonas, a dificuldade de locomoção na região, por falta de rodovias, por sua
grande extensão territorial, pela baixa densidade demográfica e pelo subdesenvolvi-
mento secular imposto à população ribeirinha, torna-se árduo o esforço do Governo
para tornar realidade à inclusão digital.
A UEA, que já nasceu moderna, incorporando tecnologias educacionais de
ponta, utilizando-se particularmente da informática pela massificação do uso de
microcomputadores combinados com uma rede complexa de acesso à Internet, não
poderia ficar alheia a essa necessidade premente. Por isso, propôs e realizou o
primeiro vestibular para levar a 12 municípios um curso que formasse a mão-de-obra
inicial que tornasse a inclusão digital uma realidade em nosso Estado.
A proposta do curso de Tecnologia em Análise e Desenvolvimento de Sistemas
oferecido pela UEA vislumbra criar mão-de-obra qualificada em um número significa-
tivo de localidades do Estado, cabendo às pessoas beneficiadas com essa iniciativa
a tarefa de irradiar o uso de tecnologias de informática, abrindo caminhos novos e
suscitando novos empregos para a população local, consolidando, assim, o exercício
da cidadania.
Prof.a Dr.a Marilene Corrêa da Silva Freitas
Reitora da Universidade do Estado do Amazonas
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 9
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 10
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
Sumário
Lista de Figuras ........................................................................13
Lista de Algoritmos....................................................................15
Lista de Programas ....................................................................17
CAPÍTULO 1 - IMPLEMENTANDO TIPOS ABSTRATOS DE DADOS................21
1.1 INTRODUÇÃO.....................................................................21 
1.2 DEFININDO UMA ESTRUTURA (STRUCT) ......................................21
1.3 TIPOS DEFINIDOS PELO USUÁRIO..............................................25
1.4 UTILIZANDO FUNÇÕES PARA AS OPERAÇÕES DO TAD.......................27
1.5 INDEPENDÊNCIA DE REPRESENTAÇÃO.........................................30
CAPÍTULO 2 - PONTEIROS E ALOCAÇÃO DINÂMICA DE MEMÓRIA .............35
2.1 INTRODUÇÃO.....................................................................35
2.2 DECLARAÇÃO DE VARIÁVEL TIPO PONTEIRO.................................35
2.3 ALOCAÇÃO DE MEMÓRIA........................................................39
2.3.1 ALOCAÇÃO DE VETOR E REGISTRO .........................................41
CAPÍTULO 3 - LISTAS ..................................................................49
3.1 INTRODUÇÃO.....................................................................49
3.2 IMPLEMENTAÇÃO DE LISTA ESTÁTICA .........................................49
3.3 IMPLEMENTAÇÃO DE LISTA SIMPLESMENTE ENCADEADA ...................58
CAPÍTULO 4 - PILHAS .................................................................65
4.1 INTRODUÇÃO.....................................................................65
4.2 PILHAS IMPLEMENTADAS POR VETORES ......................................65
4.3 PILHAS IMPLEMENTADAS POR VARIÁVEIS DINÂMICAS .......................70
CAPÍTULO 5 - FILAS ...................................................................75
5.1 INTRODUÇÃO.....................................................................75
5.2 FILAS IMPLEMENTADAS POR VETORES ........................................75
5.3 FILAS IMPLEMENTADAS POR VARIÁVEIS DINÂMICAS .........................80
CAPÍTULO 6 - RECURSIVIDADE ......................................................87
6.1 INTRODUÇÃO.....................................................................87
6.2 REVISANDO O CONCEITO DE RECURSIVIDADE ...............................87
EXERCÍCIOS..............................................................................95
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 11
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
ANEXO A - Implementação do TAD Conta utilizando vetores ...................101
ANEXO B - Implementação do TAD Lista utilizando vetores ....................105
ANEXO C - Implementação do TAD Lista utilizando variáveis dinâmicas......109
ANEXO D- Implementação do TAD Pilha utilizando vetores .....................117
ANEXO E - Implementação de pilha utilizando alocação dinâmica ............121
ANEXO F - Implementação de fila utilizando vetores............................127
ANEXO G - Implementação de fila utilizando alocação dinâmica..............133
ANEXO H - Implementação de fila circular ........................................139
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 12
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
13
Lista de Figuras
Figura 2.1: Representação esquemática de espaços de memória.
Figura 2.2: Valor lido pelo Programa 2.2.
Figura 3.1: Esquema da variável lista.
Figura 3.2: Exemplo de valores constantes da lista.
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 13
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
14
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 14
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
15
Lista de Algoritmos
Algoritmo 2.1: Atribuição de endereços de variáveis a ponteiros.
Algoritmo 2.2: Operador CONTEUDO.
Algoritmo 2.3: Alocação dinâmica de memória.
Algoritmo 2.4: Alocação de um vetor de inteiros.
Algoritmo 2.5: Alocação de um registro.
Algoritmo 2.6: Alocação de vetor de registro.
Algoritmo 3.1: Estrutura da lista.
Algoritmo 3.2: Criação da lista vazia.
Algoritmo 3.3: Verifica se a lista está vazia.
Algoritmo 3.4: Estrutura para lista encadeada.
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 15
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
16
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 16
Lista de Programas
Programa 1.1: Forma geral para definição de uma estrutura.
Programa 1.2: Aplicação da forma geral para definição de uma
estrutura de cliente.
Programa 1.3: Aplicação declarando duas variáveis do mesmo
tipo.
Programa 1.4: Declaração de variáveis do tipo estrutura como
variáveis locais.
Programa 1.5: Forma geral de referenciar um campo de uma
variável estrutura.
Programa 1.6: Criando 100 conjuntos de variáveis.
Programa 1.7: Percurso em todos os elementos de uma matriz de
estruturas.
Programa 1.8: Forma geral de definição de tipo – typedef.
Programa 1.9: Exemplo de utilização do typedef.
Programa 1.10: Exemplo de utilização do typedef com struct.
Programa 1.11: Forma geral da definição de uma função.
Programa 1.12: Exemplo de TAD básico.
Programa 1.13: Arquivo tadconta.h.
Programa 1.14: Arquivo tadconta.c.
Programa 1.15: Arquivo contendo o programa com a função prin-
cipal, main().
Programa 2.1: Atribuição de endereços de variáveis a ponteiros.
Programa 2.2: Operador CONTEUDO.
Programa 2.3: Alocação dinâmica de memória.
Programa 2.4: Alocação dinâmica de um vetor.
Programa 2.5: Alocação de um registro.
Programa 2.6: Declaração de tipo de variável registro.
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
17
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 17
Programa 2.7: Alocação de um vetor de registros.
Programa 3.1: Estrutura da lista, no arquivo de cabeçalho
“lista.h”.
Programa 3.2: Criação da lista vazia.
Programa 3.3: Lista vazia.
Programa 3.4: Inserção de nós na lista.
Programa 3.5: Lista itens cadastrados.
Programa 3.6: Módulo principal.
Programa 3.7: Estrutura da lista encadeada.
Programa 3.8: Procedimento para apagar toda a lista.
Programa 3.9: Inserir dados na lista.
Programa 3.10: Imprime os nós da lista.
Programa 4.1. Definições de tipo e interface das operações do
TAD Pilha.
Programa 4.2. Procedimento Cria_Pilha.
Programa 4.3. Função Empilha.
Programa 4.4: Função Desempilha.
Programa 4.5: Função Consulta_Topo.
Programa 4.6: Função Pilha_Vazia.
Programa 4.8: Procedimento Cria_Pilha.
Programa 4.7: Definições de tipo e interface das operações do
TAD Pilha.
Programa 4.8: Procedimento Cria_Pilha.
Programa 4.9: Função Empilha com alocação dinâmica.
Programa 4.10: Função Desempilha com alocação dinâmica.
Programa 4.11. Função Consulta_Topo com alocação dinâmica.
Programa 4.12: Função Pilha_Vazia com alocação dinâmica.
Programa 5.1: Definições de tipo e interface das operações do
TAD Fila.
Programa 5.2: Procedimento Cria_Fila.
Programa 5.3: Função Enfileira.
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
18
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 18
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
19
Programa 5.4: Função Desenfileira.
Programa 5.5: Função Consulta_Frente.
Programa 5.6: Função Quantidade_Fila.
Programa 5.7: Função Fila_Vazia.
Programa 5.8: Definições de tipo e interface das operações do
TAD Fila.
Programa 5.9: Procedimento Cria Fila.
Programa 5.10: Procedimento Enfileira.
Programa 5.11: Função Desenfileira.
Programa 5.12: Função Consulta_Frente.
Programa 5.13: Função Quantidade_Fila.
Programa 5.14. Função Fila Vazia.
Programa 6.1: Programa não recursivo em C.
Programa 6.2: Programa Recursivo em C.
Programa 6.3: Fatorial com recursão em C.
Programa 6.4: Máximo recursivo em C.
Programa 6.5: MDC recursivo em C.
Programa 6.6: Soma recursiva em C.
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 19
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
20
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 20
CAPÍTULO 1
Implementando
Tipos Abstratos de Dados 
1.1 Introdução
Como foi apresentado em Estrutura de Dados I o conceito de Tipo
de Dados pode ser visto, não em termos do que um computador pode
fazer, mas em termos do que os usuários desejam fazer. Este conceito
de Tipo de Dados independente do hardware é chamado Tipo
Abstrato de Dados - TAD. Neste capítulo iremos tratar como imple-
mentar esta estrutura na Linguagem C.
Para implementar um TAD é necessário definir uma Estrutura de
Dados (ED) para representá-lo. A ED é definida a partir dos tipos
primitivos (inteiro, real, caractere, lógico) ou dos tipos compostos
(vetor, registro e matriz) da linguagem de programação, mais as
operações definidas sobre a estrutura definida. 
A Linguagem C permite ao programador criar tipos diferentes de
dados, que podem
ser agrupados de diversas formas. Com este recur-
so é possível implementar TAD usando os “tipos de dados definidos
pelo programador” conhecidos como: estruturas e tipos definidos pelo
usuário (typedef). 
1.2 Definindo uma estrutura (struct)
Uma estrutura é uma coleção de tipos, possivelmente diferentes,
referenciada por um nome, isto é, uma estrutura é uma forma de se
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
21
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 21
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
22
agrupar informações relacionadas. Estas informações são chamadas de
membros, elementos ou campos. Podem ser variáveis de tipos de
dados primitivos, vetores (tal como strings) ou até mesmo outras
estruturas.
O comando struct da Linguagem C é um tipo de dado, não existe
um espaço reservado na memória para ela até que seja declarada uma
variável para armazenar o tipo definido.
O Programa 1.1 apresenta a forma geral para definição de uma
estrutura. Esta estrutura é a base de um TAD. A lista de variáveis é
opcional.
Programa 1.1: Forma geral para definição de uma estrutura.
Observe, no exemplo no Programa 1.2, que TipoCliente é o nome
da estrutura. Na última linha do exemplo encontramos a definição da
variável cliente que será do tipo de estrutura TipoCliente. De acordo
com a definição da estrutura a variável possui três elementos: nome e
endereco ambos do tipo string e saldo do tipo ponto flutuante.
Programa 1.2: Aplicação da forma geral para definição de uma estrutura de cliente
O Programa 1.3 mostra que se existirem duas ou mais variáveis,
que sejam do mesmo tipo de estrutura, é possível declará-las juntas:
struct TipoCliente {
char nome[25];
char endereco[15];
float saldo;
} cliente;
struct nome_estrutura {
tipo nome_do_campo1;
tipo nome_da_campo2; 
...
}[<lista_de_variáveis>];
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 22
Programa 1.3: Aplicação declarando duas variáveis do mesmo tipo.
Outra forma de declarar uma variável estrutura é fora da
definição da estrutura. Preferencialmente, são declaradas como
variáveis locais de alguma função, como mostra o Programa 1.4.
Programa 1.4: Declaração de variáveis do tipo estrutura como variáveis locais.
Quando é necessário referenciar os elementos da estrutura uti-
liza-se o ponto como operador, conforme exemplo do Programa 1.5.
Programa 1.5: Forma geral de referenciar um campo de uma variável estrutura.
Baseado no Programa 1.3 observe como são referenciadas as
variáveis:
scanf(“%s”, clientePessoa.nome); 
strcpy(clienteEmpresa.nome, “MinhaEmpresa”);
clientePessoa.saldo = 2050.50; 
clienteEmpresa.saldo = 2000400;
nome_da_variavel.nome_do_campo;
struct cliente {
char nome[25];
char endereco[15];
float saldo;
};
main(){
struct cliente cliente1, cliente2, cliente3; 
…
}
struct TipoCliente {
char nome[25];
char endereco[15];
float saldo;
} clientePessoa, clienteEmpresa;
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
23
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 23
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
24
gets(cliempresa.nome);
scanf(“%s”, clienteEmpresa.endereco);
Agora observe como é definido um vetor baseado em estruturas.
O Programa 1.6 define um vetor de estruturas que cria 100 conjuntos
de variáveis.
Programa 1.6: Criando 100 conjuntos de variáveis.
Para entender como são referenciados os valores, observe a
matriz abaixo, onde as linhas são os registros dos vetores e as colunas
são as variáveis da estrutura.
Para referenciar cada elemento da matriz pode-se utilizar:
clientes[0].nome
clientes[0].saldo
clientes[2].nome
clientes[1].endereco
struct TipoCliente {
char nome[25];
char endereco[15];
float saldo;
} clientes[100];
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 24
De acordo com o exemplo anterior os respectivos valores das
referências são:
Para percorrer toda a estrutura podemos utilizar a estrutura do
for, como no exemplo do Programa 1.7:
Programa 1.7: Percurso em todos os elementos de uma matriz de estruturas.
1.3 Tipos definidos pelo usuário
Um TAD pode ser considerado uma generalização dos tipos primi-
tivos de dados já conhecidos e por isso podem ser usados para
encapsular os tipos de dados primitivos. Esta estratégia facilita qual-
quer tipo de alteração sobre o TAD, pois estão localizados em uma
única seção do programa. Na Linguagem C é permitido ao usuário
definir um novo nome para o tipo de dado que ele deseja declarar.
Essa forma de declaração é freqüentemente utilizada para tornar os
programas mais portáveis e também para documentação e
padronização. O Programa 1.8 mostra a forma geral para uso
do typedef.
for (x = 0; x < 100; x++)
{
gets(clientes[x].nome);
gets(clientes[x].endereco);
scanf(“%f”, clientes[x].saldo);
}
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
25
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 25
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
26
Programa 1.8: Forma geral de definição de tipo – typedef.
No Programa 1.9 homem e mulher são variáveis do tipo idade,
onde o tipo idade é um outro nome para o tipo primitivo inteiro.
Programa 1.9: Exemplo de utilização do typedef.
O recurso do typedef pode ser usado em conjunto com o
comando struct para padronizar um tipo de dado do tipo estrutura,
como mostrado no Programa 1.9
Programa 1.10: Exemplo de utilização do typedef com struct.
Para referenciar no programa usa-se: 
typedef struct {
int dia;
int mes;
int ano;
}TipoData;
typedef int idade;
idade homem, mulher;
typedef tipo novo_tipo;
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 26
Após a execução dos comandos acima, os campos da variável data
terão os seguintes valores:
Fundamentalmente, um TAD significa uma representação dos
dados e as operações que serão efetuadas sobre essa representação.
Para isso, a definição de um TAD envolve duas partes: a definição dos
dados e a definição das operações. Até aqui foi apresentado como
implementar a definição dos dados através dos comandos struct e
typedef. Agora será apresentado como definir as operações de um
TAD.
1.4 Utilizando funções para as operações do TAD
Na linguagem de programação C é possível implementar as
operações dos TADs através de funções. A função é um seguimento
independente do programa que executa uma tarefa específica,
tornando assim o programa modular. Além desta vantagem
destacam-se ainda a repetição das mesmas instruções de programa em
diferentes pontos do programa e clareza na representação de lógica.
Todo programa em C é formado por uma ou mais funções. Uma
dessas funções é a função main(). As funções adicionais do programa
estarão subordinadas à função main() ou a alguma outra função. Se um
programa contém várias funções, suas definições podem aparecer em
qualquer ordem. Uma função será executada quando for chamada.
Após a execução, o controle retorna para o ponto no qual a função foi
chamada. O Programa 1.11 mostra a forma geral de uma função em C.
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
27
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 27
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
28
Programa 1.11: Forma geral da definição de uma função.
Onde: 
tipo - define o tipo da informação que a função vai retornar,
podendo ser qualquer tipo válido. Se
nenhum tipo for
especificado o compilador assume que a função devolve um
resultado inteiro (default), quando a função não retorna nenhum
resultado coloca-se void;
nome_da_função – identificador criado pelo programador;
lista_de_parâmetros – são as informações passadas para a
função, também conhecidas como argumentos. Uma função pode
não conter argumentos, neste caso, uma lista vazia entre parên-
teses. Todos os parâmetros da função devem conter o tipo e o
nome da variável.
As variáveis declaradas dentro de uma função não podem
interagir com o código ou os dados definidos em outra função, são
chamadas de variáveis locais daquela função.
O padrão ANSI expandiu a declaração de funções colocando-se a
utilização de protótipos. Sua finalidade é a de informar ao compilador
a existência de outras funções no programa além da função main().
Isto faz com que o compilador avalie os tipos especificados nos
parâmetros evitando incompatibilidade de tipo na chamada a função.
Uma vez apresentado como a linguagem C implementa as
definições de dados e de funções, será apresentado como é definido
um TAD em C. Em uma forma básica de implementação, considere a
estrutura ContaCliente apresentada no início do Programa 1.12. Ela é
composta pelas variáveis numero, nome e saldo. Logo em seguida é
criada a variável conta do tipo ContaCliente.
tipo nome_da_funcao ([<lista_de_parametros>])
{
// corpo da função
}
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 28
Após a criação da variável clienteEmpresa encontra-se a definição
dos protótipos das operações, seguido de suas implementações. Na
última parte do programa está a implementação da função main().
Programa 1.12: Exemplo de TAD básico.
#include <stdio.h>
/* DEFINIÇÃO DA ESTRUTURA */
struct ContaCliente {
int numero;
char nome[50];
float saldo;
};
ContaCliente conta;
/* DEFINIÇÃO DO PROTÓTIPO DAS OPERAÇÕES */
void CadastrarConta(void);
void ExcluirConta(void);
void AlterarConta(void);
/* IMPLEMENTAÇÃO DAS OPERAÇÕES */
void CadastrarConta()
{
printf("Digite o numero da conta a ser incluída:");
scanf("%d",&conta.numero);
}
void ExcluirConta ()
{ ... }
void AlterarConta ()
{ ... }
/* CORPO DA FUNÇÃO PRINCIPAL DO PROGRAMA */
main()
{ ... }
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
29
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 29
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
30
1.5 Independência de representação
Esta é a forma mais simples de implementar um TAD. Entretanto,
a chave para se conseguir verdadeiramente implementar TAD é aplicar
o conceito de independência de representação. A aplicação deste
conceito é possível em linguagens de programação que suportem
módulos.
Um TAD pode ser implementado usando um módulo da seguinte
maneira:
1. O nome do módulo é o nome do TAD;
2. Apenas as operações da especificação abstrata são visíveis
externamente ao módulo, e
3. A representação concreta do TAD e outros componentes
auxiliares ficam ocultos dentro do módulo.
Com a linguagem C é possível implementar TAD usando o conceito
de módulos através de arquivos de programas separados em três
arquivos:
• Um arquivo de cabeçalho (header) “.h” para declaração das
estruturas, definições de tipo e dos protótipos das operações
(NomeTAD.h);
• Um arquivo fonte “.c” para implementação das funções
(NomeTAD.c);
• Um arquivo fonte “.c” para o programa principal (contendo a
função main()).
Exemplo 
Problema:
Utilizando TADs e registros construa um algoritmo, que realize o
cadastro de contas bancárias. São dadas as seguintes informações:
a) Número da conta;
b) Nome do cliente;
c) Saldo da conta.
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 30
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
31
O banco permitirá o cadastramento de apenas 10 contas e não
pode haver mais de uma conta com o mesmo número. Crie o menu de
opções abaixo:
Menu
1. Cadastro de contas;
2. Mostrar todas as contas de um determinado cliente;
3. Excluir a conta com menor saldo (supondo que não existam
saldos iguais);
4. Sair.
Resolução:
Passo1
• Crie um arquivo .h;
• Crie um registro e a definição de tipo;
• Crie o protótipo das operações.
Passo2
• Crie o arquivo .c;
• Crie um procedimento de cadastro de contas dos clientes
(número, nome e saldo);
• Crie um procedimento para mostrar as contas do cliente solici-
tado;
• Crie um procedimento para excluir a conta com o menor saldo.
Passo3
• Crie o arquivo main.c;
• Crie um menu de opções.
Acompanhe nos Programas de 1.13 a 1.15 a resolução do
exercício. O Programa 1.13 mostra o arquivo de cabeçalho,
o Programa 1.14 exibe o corpo das operações do TAD e finalmente, o
programa principal está mostrado no Programa 1.15.
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 31
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
32
Programa 1.13: Arquivo tadconta.h.
#define max 100
typedef struct tipo_conta {
int numero;
char nome[50];
float saldo;
}TConta;
void CadastrarConta (TConta c[]);
int VisualizarConta (TConta c]);
void ExcluirConta (TConta c[]);
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 32
Programa 1.14: Arquivo tadconta.c.
#include <stdio.h>
#include <string.h>
#include <values.h>
#include "tadconta.h"
void CadastrarConta(TConta c[]) { 
int num_conta;
printf("\nDigite o número da conta: ");
scanf("%d",&num_conta);
if (c[num_conta-1] != 0) //conta já existe
printf(“\nErro: Já existe conta com este número!”);
else {
printf("Informe nome do cliente: ");
scanf("%s", c[num_conta-1].nome);
printf("Informe saldo do cliente: ");
scanf("%f", &c[num_conta-1].saldo);
printf(“\nConta cadastrada com sucesso!”);
}
}
void VisualizarConta(TConta c[]){ 
int i;
char nome_cli[50];
printf("Digite o nome do Cliente a ser Consultado: ");
scanf(“%s”, nome_cli);
for(i = 0; i < 10; i++) {
if (! strcmp(c[i].nome, nome_cli) {
printf("\n\nNúmero da Conta: %d", c[i].numero);
printf("\nNome...........: %s", c[i].nome);
printf("\nSaldo..........: R$%.2f", c[i].saldo);
}
}
}
void ExcluirConta(TConta c[]){ 
int posicao = -1, i;
float menor_saldo = MAXFLOAT;
for(i = 0; i < 10; i++) {
if (c[i].numero != 0) { //conta já existe
if (c[i].saldo < menor_saldo) {
menor_saldo = conta[i].saldo;
posicao = i;
}
}
}
if (posicao == -1) {
printf("Nenhuma Conta foi Cadastrada");
else {
c[posicao].numero = 0;
c[posicao].saldo = 0;
strcpy(c[posicao].nome, “ ”);
printf("Conta excluída com sucesso", posicao+1);
}
}
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
33
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 33
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
34
Programa 1.15: Arquivo contendo o programa com a função principal, main().
#include <stdio.h>
#include <string.h>
#include "tadconta.h"
main(void)
{
TConta contas[max];
int i, op;
for(i = 0; i < 10; i++) {
contas[i].numero = 0;
strcpy(contas[i].nome, “ ”);
contas[i].saldo = 0;
}
while(op != 4) {
printf("\n\nMenu de Opções:");
printf("\n1 - Cadastrar Contas");
printf("\n2 - Visualizar Contas Cliente");
printf("\n3 - Excluir Conta de menor saldo");
printf("\n4 - Sair");
printf("\n\nDigite a sua Opção:");
scanf(“%d”, &op);
switch (op){
case 1:
CadastrarConta(contas); break;
case 2:
VisualizarConta(contas); break;
case 3:
ExcluirConta(contas); break;
default:
printf("\nErro: Opção Inválida");
}
}
} 
01_laboratorio_de_estrutura_de_dados_I.qxp
28/11/2008 13:29 Page 34
CAPÍTULO 2
Ponteiros e Alocação
Dinâmica de Memória
2.1 Introdução
Neste capítulo será estudado como declarar uma variável do tipo
ponteiro, bem como os diversos usos que se pode fazer desse tipo de
variável, como alocação dinâmica de memória e alocação de um vetor.
2.2 Declaração de variável tipo ponteiro
Ponteiros (ou apontadores) são variáveis que armazenam
endereço de memória e são associados a tipos de dados, ou seja, um
ponteiro endereça (ou aponta para) um dado de determinado tipo.
O Algoritmo 2.1 mostra exemplos de declarações de variáveis tipo
ponteiro e a atribuição de endereços de variáveis a esses ponteiros.
Algoritmo 2.1: Atribuição de endereços de variáveis a ponteiros.
var
i : inteiro
r : real
c : caractere
pi : Ponteiro inteiro
pr : Ponteiro real
pc : Ponteiro caractere
inicio
pi <- ENDERECO i
pr <- ENDERECO r
pc <- ENDERECO c
fimalgoritmo
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
35
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 35
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
36
A declaração de uma variável tipo ponteiro na linguagem C é feita
de acordo com a seguinte sintaxe:
tipo *nome_da_variável;
Onde: 
• tipo é um tipo primitivo da linguagem (int, char, etc.) ou
um tipo definido pelo programador, como um registro,
por exemplo.
• nome_da_variável é um descritor (nome de variável),
definido pelo programador, obedecendo às regras de definição de
descritores. Exemplo: int *pi;
O Algoritmo 2.1 mostra as declarações de uma variável simples e
uma variável tipo ponteiro, ambas do tipo inteiro, em linhas
diferentes. Como se tratam de variáveis do mesmo tipo, podem ser
declaradas no mesmo comando de declaração de variável. Exemplo:
int i, *pi;
As declarações de variáveis abaixo são equivalentes :
int * pi;
int *pi;
int* pi;
int*i;
O operador ENDEREÇO – & – já é utilizado desde que se aprendeu
o comando de leitura (scanf(“%d”, &i)), onde esse operador faz
com que o valor lido seja armazenado no endereço da variável, ou
seja, a variável é passada por referência para a função scanf, onde
terá o seu conteúdo modificado.
Ao trabalhar com ponteiro, esse operador pode ser usado para
atribuir a um ponteiro o endereço de uma variável.
Por exemplo: para as variáveis declaradas no exemplo acima,
o comando pi = &i; faz com que o endereço da variável i seja
armazenado no ponteiro pi.
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 36
O Algoritmo 2.1 pode ser codificado, em linguagem C, conforme o
Programa 2.1.
Programa 2.1: Atribuição de endereços de variáveis a ponteiros
Outro operador utilizado com ponteiros é o operador de indireção
(ou desreferenciação) CONTEUDO. Esse operador, aplicado a um
ponteiro, acessa o conteúdo de um espaço de memória apontado por
esse ponteiro.
Um exemplo de uso do operador conteúdo, considerando as
variáveis declaradas no Algoritmo 2.1 está no Algoritmo 2.2.
Algoritmo 2.2: Operador CONTEUDO.
O comando de leitura do Algoritmo 2.2 faz com que o valor lido
seja armazenado na posição de memória endereçada (apontada) pelo
ponteiro pi.
Vamos supor que a memória do computador possui o
endereçamento conforme o exemplo da Figura 2.1, onde estão
inicio
...
escreva(“Digite um valor inteiro”)
leia(CONTEUDO pi)
escreva(i) //escreve o valor lido
fimalgoritmo
#include <stdio.h>
int i, *pi;
float r, *pr;
char c, *pc;
main()
{ pi = &i;
pr = &r;
pc = &c;
}
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
37
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 37
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
38
representas apenas as variáveis i e pi, do Programa 2.1. O comando
pi <- ENDERECO i, (Algoritmo 2.1), faria a variável pi assumir o
valor 10533 e o comando leia(CONTEUDO pi), (Algoritmo 2.2),
guardaria o valor lido no espaço de memória endereçado por pi. 
Figura 2.1: Representação esquemática de espaços de memória.
Acrescentando-se o Algoritmo 2.2 ao Programa 2.1, temos o
Programa 2.2, conforme abaixo:
Programa 2.2: Operador CONTEUDO
O valor armazenado na variável i pode ser acessado e alterado
#include <stdio.h>
int i, *pi;
float r, *pr;
char c, *pc;
main() {
pi = &i;
pr = &r;
pc = &c;
printf(“Digite um valor inteiro”);
scanf(“%d”,pi);
printf(“Valor lido: %d%”,*pi);
}
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 38
através do ponteiro pi. Supondo que o valor lido pelo Programa 2.2
(linha 12) tenha sido 27, o esquema da Figura 2.1 assumiria a seguinte
configuração mostrada na Figura 2.2.
Figura 2.2: Valor lido pelo Programa 2.2.
A visualização do conteúdo do apontado pelo ponteiro pi
(Figura 2.2) pode ser obtida pelo comando printf(“Conteúdo do
ponteiro: %p”, *pi), que gera como saída o valor 27. 
A impressão do conteúdo de um ponteiro pode ser feita usando-se
a string de tipo “%p”. Dependendo das características do sistema
operacional, esse valor poderá ser em base hexadecimal.
2.3 Alocação de memória
Para fazer alocação dinâmica de memória, deve-se fazer uso de 3
recursos:
1. Ponteiro para o tipo escolhido;
2. Função de alocação de memória (ALOCAR);
3. Função para retornar o tamanho de um tipo (TAMANHO_DE).
Considere o exemplo de algoritmo de alocação de memória a
seguir:
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
39
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 39
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
40
Algoritmo 2.3: Alocação dinâmica de memória.
A codificação do Algoritmo 2.3, em linguagem C, pode ser da
seguinte forma:
Programa 2.3: Alocação dinâmica de memória.
O trecho do Programa 2.3 faz com que um espaço de memória do
tamanho ocupado por uma variável tipo inteiro seja reservado e o
endereço desse espaço seja armazenado na variável tipo ponteiro p.
Cabe destacar que, quando se trabalha com alocação dinâmica
de memória, os locais (espaços de memória) onde se guardam os
valores não são referenciados por um nome de variável, e sim, apenas
por um ponteiro.
#include <stdio.h>
#include <stdlib.h>
main()
{
int *p;
p = (int *) malloc(sizeof(int));
...
}
algoritmo “exemplo de alocação”
var
P: Ponteiro inteiro
inicio
P <- ALOCAR(TAMANHO_DE(inteiro))
...
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 40
As funções de alocação de memória malloc(), calloc() e
realloc() e a função de liberação de memória free (vista mais
adiante), são funções constantes no arquivo de cabeçalho stdlib.h,
o qual necessita ser declarado em uma diretiva de pré-processamen-
to #include.
2.3.1 Alocação de vetor e registro
Para fazer alocação de um vetor dinamicamente, declare um pon-
teiro do tipo que se quer criar o vetor. No comando de alocação de
memória multiplique a quantidade de posições do vetor pelo tamanho
do tipo. 
Exemplo: para alocar um vetor de inteiros com 50 posições,
primeiro é feita a declaração do ponteiro tipo inteiro. Na alocação do
ponteiro, multiplica-se o tamanho de inteiro por 50. Observe, no
Algoritmo 2.4, o comando de alocação de um vetor, cujo tamanho
dependerá do valor informado em tempo de execução.
Algoritmo 2.4: Alocação de um vetor de inteiros.
No exemplo acima, se for informado o valor 100 para a variável
tam, o vetor ocupará TAMANHO_DE(inteiro) * tam. Caso um
inteiro ocupe 2 bytes, o vetor ocupará 2 x 100 = 200 bytes.
algoritmo “Alocação de Vetor”
var
p: Ponteiro inteiro
tam, i: inteiro
inicio
leia(tam)
p <- ALOCAR(TAMANHO_DE(inteiro)
* tam)
para i de 1 ate tam faca
leia (p[i])
fimpara
fimalgoritmo
...
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
41
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 41
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
42
Um ponteiro para um espaço desse tipo guarda o endereço da primeira
posição e as demais são alocadas contiguamente.
Programa 2.4: Alocação dinâmica de um vetor.
No Programa 2.4 é feito um teste na linha 8: if p == NULL.
Esse teste é necessário para detectar algum possível problema
durante a alocação do vetor, como falta de memória para o vetor
requerido, por exemplo. 
Ressalta-se que a linguagem de algoritmos é genérica.
Um algoritmo pode ser codificado em diversas linguagens de
programação. No momento da implementação deve-se observar as
particularidades de cada uma. A linguagem C realiza a indexação a
partir do valor zero. Por isso, o índice do vetor, que no algoritmo
começa em 1 (para i de 1 ate tam faca), no Programa 2.4
foi implementado com a variável i iniciando com valor zero
(for(i = 0; i < tam; i++). Portanto, o índice vetor começa
com valor zero e termina em n – 1 (condição de parada do laço é
i >= tam).
1. /* Programa para alocação de vetor */
2. #include <stdio.h>
3. main(){
4. int *p, tam, i;
5. printf(“Informe o tamanho do vetor: “);
6. scanf("%d", &tam);
7. p = (int *)malloc(sizeof(int) * tam);
8. if(p == NULL) 
9. printf("Vetor não alocado");
10. else
11. {
12. printf("informe os valores do vetor:\n");
13. for (i = 0 ;i < tam; i++)
14. scanf("%i", &p[i]);
15. }
16.}
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 42
Outro detalhe é que depois da alocação do ponteiro p, o vetor
passa a ser usado como se tivesse sido declarada uma variável vetor
de inteiro. Por isso, na linha 14 do Programa 2.4, não foi usado o
operador de indireção CONTEUDO. Em outras palavras, a forma como
o vetor p foi criado no Programa 2.4 é equivalente à declaração de
variável int p[tam];. Conclui-se que a declaração de uma variável
tipo vetor é a declaração de um ponteiro para a primeira posição do
vetor.
Para fazer a alocação dinâmica de um registro, primeiro
declara-se o registro desejado. Essa declaração cria um novo tipo de
variável. Depois, declara-se uma variável ponteiro do tipo (registro)
criado. A seguir, é possível alocar um espaço de memória do tamanho
do registro, que será endereçado (apontado) pela variável ponteiro, a
qual foi declarada do tipo desse registro.
O Algoritmo 2.5 exemplifica a alocação de um registro.
Algoritmo 2.5: Alocação de um registro.
algoritmo “Alocação de Registro”
var
TFuncionario = registro
nome : caractere
salario: real
idade : inteiro
fimregistro
PF: Ponteiro TFuncionario
inicio
...
PF <- ALOCAR(TAMANHO_DE(TFuncionario))
leia(PF->nome, PF->salario, PF->idade)
...
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
43
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 43
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
44
Usando essa forma, a codificação do Algoritmo 2.5, em linguagem
C, pode ser feita como no Programa 2.5.
O acesso aos campos de um registro criado por alocação dinâmica
é feito usando uma seta na direção do campo, e não mais o ponto.
Exemplo: PF->nome, acessa o campo nome do registro
apontado por PF.
Programa 2.5: Alocação de um registro.
#include <stdio.h>
#include <stdlib.h>
struct TFuncionario
{ char nome[40];
float salario;
int idade;
};
main()
{
struct TFuncionario *PF;
PF = (struct TFuncionario *)malloc(sizeof(struct TFuncionario));
printf("\nDigite os dados do funcionário ");
printf("\nNome: ");
scanf("%s", PF->nome);
printf("Salario: ");
scanf("%f",&PF->salario);
printf("Idade: ");
scanf("%d",&PF->idade);
printf("\nConfira os dados digitados: ");
printf("\n\nNome: %s", PF->nome);
printf("\nSalario = %7.2f” ,PF->salário);
printf("\nIdade = %d", PF->idade);
return 0;
}
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 44
Como visto no Capítulo 1, codificando em linguagem C, pode-se
utilizar a criação de tipos de estrutura, com o uso de typedef.
Tem-se, portanto, uma declaração conforme mostrado no Programa 2.6.
Programa 2.6: Declaração de tipo de variável registro.
O uso de variável tipo registro resolve a situação de permitir
manter, em uma mesma estrutura, informações de tipos diferentes.
Entretanto, a manipulação de muitas informações continua sendo uma
limitação para o programador. Uma forma de superar esse aspecto é
criar um vetor de registros.
typedef struct Funcionario
{ char nome[40];
float salario;
int idade;
}TFuncionario;
TFuncionario *PF;
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
45
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 45
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
46
O Algoritmo 2.6 é um exemplo de alocação de vetor de registro.
Algoritmo 2.6: Alocação de vetor de registro.
A codificação do Algoritmo 2.6 é realizada pelo Programa 2.7, a
seguir. É importante notar que os campos de cada posição do vetor são
referenciados pelo nome da variável “ponto” nome do campo, mesmo
que o vetor tenha sido alocado dinamicamente. Isto acontece pois o
índice do vetor já identifica o registro. A partir daí, é necessário ape-
nas identificar o campo.
algoritmo “Alocação de Vetor de Registros”
var
TFuncionario = registro
nome: caractere
salario: real
idade: inteiro
fimregistro
vet: Ponteiro TFuncionario
tam, i: inteiro
inicio
...
leia (tam)
vet <- ALOCAR(TAMANHO_DE(TFuncionario) * tam)
para i de 1 ate tam faca
leia(vet[i].nome, PF[i].salario, PF[i].idade)
fimpara
...
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 46
Programa 2.7: Alocação de um vetor de registros.
/* Programa para alocação de vetor de registro */
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
char nome[40];
float salario;
int idade;
} TFuncionario;
main()
{
TFuncionario *vet;
int tam, i;
printf("Informe o tamanho do vetor");
scanf("%d", &tam);
vet = (TFuncionario *)malloc(sizeof(TFuncionario) * tam);
for (i = 0; i < tam; i++)
{
__fpurge(stdin); //Limpa o buffer do teclado
printf("\nDigite o nome: ");
scanf("%s", vet[i].nome);
printf("\nDigite o salario: ");
scanf("%f",&vet[i].salario);
printf("\nDigite a idade: ");
scanf("%d",&vet[i].idade);
}
return 0;
}
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
47
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 47
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
48
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 48
CAPÍTULO 3
Listas
3.1 Introdução
Listas são estruturas de dados constituídas por um conjunto de
informações e um conjunto de operações sobre os dados. Podem ser
construídas através de estruturas estáticas, como o vetor, ou de
alocação dinâmica de memória.
Vamos supor uma situação em que se deseja gerenciar as
informações dos produtos de uma empresa. Dispõem-se do código de
cada produto, da especificação (nome do produto), do preço unitário
de venda e da quantidade em estoque. A lista deverá permitir as
seguintes operações:
• Inserir um novo nó na lista;
• Listar os produtos constantes da lista;
• Verificar se um produto consta da lista, dado o código;
• Retirar um produto da lista, dado o código;
• Atualizar os dados de um produto, dado
o código;
• Informar a quantidade de produtos constante da lista.
3.2 Implementação de lista estática
Será usado um vetor para fazer a implementação estática da lista
proposta.
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
49
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 49
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
50
O primeiro passo é criar a estrutura da lista. Como se trata de
mais de uma informação a respeito de cada produto e de tipos
diferentes, deve-se utilizar um vetor de registros, onde cada registro
conterá todas as informações de um produto.
O Algoritmo 3.1 cria a estrutura da lista.
Algoritmo 3.1: Estrutura da lista
O registro TipoItem contém os campos com informações do pro-
duto. O registro TipoLista contém dois campos, o campo tamanho,
que conterá o número de itens da lista, e o campo item um vetor de
tamanho determinado pela variável max, onde cada posição tem três
campos. Se tamanho tiver valor zero indica que a lista está vazia.
Declarar uma variável lista, por exemplo, do tipo TipoLista,
significa que essa variável será composta de um vetor item e uma
variável inteira tamanho. Esquematicamente essa variável está
representada na Figura 3.1.
Max = 100 : constante inteiro
var TipoItem = registro
cod : inteiro
especif : caractere
preco : real
quant : inteiro
fimregistro
TipoLista = registro
item : vetor[1..max] de TipoItem
tamanho : inteiro
fimregistro
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 50
Figura 3.1: Esquema da variável lista.
A implementação da definição da estrutura da lista pode ser feita
como consta do Programa 3.1.
Programa 3.1: Estrutura da lista, no arquivo de cabeçalho “itens.h”.
#define max 100 //def. da constante com o valor maximo de itens
typedef struct tipo_item { // definicao da estrutura
int cod;
char especif[30];
float preco;
int quant;
}TItem;
typedef struct tipo_lista { //definição da estrutura do vetor
TItem item[max];
int tamanho;
}TLista;
void cria_lista_vazia(TLista *lista); //passagem por referencia
int vazia(TLista lista); //passagem por valor
void inserir(TLista *lista); 
void listar(TLista lista);
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
51
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 51
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
52
A variável lista pode ser declarada no módulo principal do
programa. A criação da lista vazia pode ser feita através de um
procedimento, no qual é atribuído o valor zero para o campo da
variável lista chamado tamanho. O Algoritmo 3.2 mostra uma forma
de fazer isto.
Algoritmo 3.2: Criação da lista vazia.
O Programa 3.2 corresponde ao Algoritmo 3.2. Como a atualização
do campo tamanho deve retornar ao módulo que chama esse
procedimento, a passagem do parâmetro se dá por referência.
Programa 3.2: Criação da lista vazia.
Em vários pontos do programa será necessário verificar se a lista
está vazia. Um exemplo de uma situação em que se fará essa verifi-
cação é antes de tentar imprimir a lista. Antes de iniciar a busca de
um item para eliminar é outro caso onde se deve verificar se a lista
está vazia. Em situações como essas, recomenda-se evitar reescrever
o mesmo trecho de código. Uma função para fazer tal verificação está
sendo apresentada no Algoritmo 3.3.
void cria_lista_vazia(TLista *lista){ 
lista->tamanho = 0;
}
procedimento cria_lista_vazia(var lista : TipoLista)
inicio
lista->tamanho <- 0
fimprocedimento
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 52
Algoritmo 3.3: Verifica se a lista está vazia.
A idéia usada no Algoritmo 3.3 é que na linguagem C o zero tem
valor lógico FALSO e qualquer valor diferente de zero resulta em
VERDADEIRO.
A implementação desse algoritmo pode ser vista no Programa 3.3.
Uma maneira de chamar esse procedimento é em forma de teste
lógico
Programa 3.3: Lista vazia.
Uma observação importante: no Algoritmo 3.2 para referenciar o
campo tamanho, da variável lista, foi utilizado o operador de
indireção ->, enquanto no Algoritmo 3.3 foi utilizado o ponto.
A diferença se deve ao fato da variável lista ter sido passada por
referência no primeiro procedimento e por valor no segundo.
Um procedimento para acrescentar informações na lista está
sendo apresentado no Programa 3.4. Entretanto, as informações estão
sendo armazenadas na ordem em que são digitadas. Fica a título de
int vazia(TLista lista)
{
if (lista.tamanho == 0)
return 1;
else
return 0;
}
funcao vazia(lista : TipoLista): logico
inicio
se lista.tamanho = 0 entao
retorne VERDADEIRO
senao
retorne FALSO
fimse
fimfuncao
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
53
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 53
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
54
exercício modificar o procedimento inserir para realizar a
construção da lista ordenada por ordem crescente de código, uma vez
que um critério de ordenação é uma das características da lista. Uma
forma de realizar essa tarefa é receber o código e buscar em que
posição será inserido. Caso não seja inserido no final da lista, deve-se
abrir um espaço, avançando uma posição no vetor todos os nós que
ficarão após o novo nó.
Programa 3.4: Inserção de nós na lista.
Exemplo:
Existem no vetor os códigos 344, 356, 363, 365 e deseja-se inserir
o código 347, que passará a ocupar a posição dois no vetor.
Faz-se necessário, portanto, deslocar os valores das posições 2, 3
e 4 para as posições 3, 4 e 5, respectivamente.
Para que não ocorra perda de nenhum valor, o vetor deve ser per-
corrido do final até a posição que deve resultar vazia.
No caso desse exemplo, deve-se copiar primeiro o valor da posição
4 para a posição cinco, depois da posição 3 para 4 e, por fim, da
posição 2 para 3.
Para realizar essa cópia, não é necessário copiar campo a campo
void inserir(TLista *l)
{
printf("\nDigite o codigo do produto: ");
scanf("%d", &l->item[l->tamanho].cod);
printf("Especificacao: ");
scanf("%s", l->item[l->tamanho].especif);
printf("Digite o preco: ");
scanf("%f", &l->item[l->tamanho].preco);
printf("Digite a quantidade: ");
scanf("%d", &l->item[l->tamanho].quant);
l->tamanho ++;
}
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 54
do registro de cada posição do vetor. É suficiente fazer a atribuição de
um registro a outro: lista.item[x] <- lista.item[y] e todos os
campos do registro item serão copiados da posição x para a posição y
do vetor. 
A Figura 3.2 traz um exemplo de informações digitadas para duas
posições do vetor. O campo lista.tamanho tem valor dois,
significando que dois registros foram implantados.
Figura 3.2: Exemplo de valores constantes da lista.
Outra funcionalidade da estrutura lista é realizar a impressão
(listagem) das informações constantes da mesma. Um procedimento
com essa finalidade está sendo mostrado no Programa 3.5.
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
55
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 55
Programa 3.5: Lista itens cdastrados
O módulo principal do programa deve declarar a variável lista e
conter um menu de opções que disponibilize ao usuário todas as fun-
cionalidades da lista, conforme especificado no início deste capítulo.
Uma versão do módulo principal que realiza a lista estática, com
as opções de inserir e imprimir dados, é apresentada a seguir, no
Programa 3.6.
void listar(TLista l)
{
int i;
if (vazia(l))
printf("Nao ha produto cadastrado");
else { 
printf("\n\nProdutos cadastrados:");
for (i = 0; i < l.tamanho; i++){
printf("\nCodigo: %5d",l.item[i].cod);
printf(" Especificacao: %s",l.item[i].especif);
printf(" Preco: %6.2f ", l.item[i].preco);
printf("Qtd: %3i, l.item[i].quant);
}
}
}
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
56
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 56
Programa 3.6: Módulo principal.
#include <stdio.h>
#include "lista.h"
main(void) {
char op = ' ';
TLista lista;
cria_lista_vazia(&lista);
while (op != '3') {
printf("\n\n\t\tCadastro de produtos");
printf("\n\n\t\t1 - Inserir dados
printf("\n\t\t2 - Listar");
printf("\n\t\t3 - Encerrar programa");
printf("\n\n\t\tOpcao escolhida: ");
__fpurge(stdin);
scanf("%c", &op);
switch(op) { 
case '1':
inserir(&lista); //argumento passado por ref.
break;
case '2':
listar(lista); //argumento passado por valor
break;
}
}
return 0;
}
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
57
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 57
3.3 Implementação de lista simplesmente encadeada
A implementação estática, por um lado, impõe a limitação do
tamanho do vetor e por outro lado, aloca memória que poderá não ser
usada durante a execução do programa.
A alocação dinâmica evita essas duas situações, já que aloca
memória somente quando for necessário e libera espaço de memória
alocado quando não necessitar de uma informação na estrutura (quan-
do remover uma informação).
Será usada como exemplo de implementação de uma lista simples-
mente encadeada a estrutura da lista estática. Faz-se necessário
acrescentar um ponteiro ao registro TipoItem. Esse ponteiro será o elo
de ligação de um registro com outro. A estrutura da lista está repre-
sentada no Algoritmo 3.4.
Algoritmo 3.4: Estrutura para lista encadeada.
Nota-se que o ponteiro proximo é do tipo do registro onde ele está
sendo declarado. Significa que endereçará uma estrutura TipoItem. 
var TipoItem = registro
cod : inteiro
especif: caractere
preco : real
quant : inteiro
proximo: Ponteiro TipoItem
fimregistro
TipoLista = registro
inicio : Ponteiro TipoItem
fimregistro
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
58
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 58
Haverá um ponteiro que guardará o primeiro nó (registro) da lista.
A partir do segundo nó o encadeamento será feito pelo nó anterior. Por
esse motivo, não é possível acessar diretamente um determinado nó,
exceto o primeiro.
De forma esquemática, a lista terá a representação mostrada na
Figura 4.
Figura 3.3: Esquema da lista encadeada.
O Programa 3.7 implementa a estrutura da lista. O ponteiro Início,
para o início da lista, do tipo TipoLista, será declarado no módulo prin-
cipal. Caso Início tenha valor nulo, significa que a lista está vazia.
Cada nó (ou célula) terá quatro campos de informação e um campo
ponteiro para o próximo nó, sendo que o último ponteiro terá valor
nulo, indicando que não há nó posterior. 
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
59
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 59
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
60
Programa 3.7: Estrutura da lista encadeada.
Para cada nó que se deseja acrescentar à lista, será alocada na
memória uma estrutura do tipo TipoCelula, definida no Programa
3.7. A cada eliminação de um nó da lista, o espaço de memória
correspondente será liberado. 
Cabe observar que o ponteiro Proximo poderia ter sido
declarado na estrutura TipoDado. Entretanto, como exemplo da
flexibilidade que a linguagem possui, foi criada a estrutura Celula,
com os mesmos campos da estrutura TipoDado mais o ponteiro
Proximo.
typedef int TipoChave;
typedef struct {
TipoChave cod;
char especif[30];
float preco;
int quant;
} TipoDado;
struct Celula {
TipoDado Dado;
struct Celula *Proximo;
}TipoCelula;
typedef struct {
TipoCelula *Inicio;
} TipoLista;
void CriaLista (TipoLista *lista);
int ListaVazia (TipoLista *lista);
int InsereOrdenadoLista (TipoLista *lista, TipoDado dado);
int RetiraLista (TipoLista *lista, TipoChave cod, TipoDado *dado);
void ListarItens(TipoLista *lista);
int ConsultaItem (TipoLista *lista, TipoChave cod, TipoDado *dado);
void ApagarLista (TipoLista *lista);
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 60
Ao final da execução do programa, devem ser desalocados da
memória todos os nós. Caso essa providência não seja tomada, mesmo
após o encerramento do programa a memória permanecerá ocupada. 
A liberação do espaço de memória é feita pelo comando
free(argumento), onde argumento é um ponteiro. No exemplo
abaixo, Programa 3.8, consta uma rotina com essa finalidade.
Programa 3.8: Procedimento para apagar toda a lista.
A inserção de nós na lista será feita pelo procedimento constante
do Programa 3.9, InsereOrdenadoLista. Como é necessário que as
alterações feitas na lista permaneçam após o encerramento do
módulo de inserção, a passagem do parâmetro com o endereço do iní-
cio da lista deve ocorrer por referência. 
void ApagarLista(TLista *lista)
{
TipoCelula *noatual, *aux;
noatual = lista->Inicio;
while (noatual != NULL){ // laço para desalocar todos os nós
aux = noatual->Proximo; 
free(noatual); // liberando a memória.
noatual = aux; 
}
lista->Inicio = NULL; 
}
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
61
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 61
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
62
Programa 3.9: Inserir dados na lista.
int InsereOrdenadoLista(TipoLista *lista, TipoDado dado) {
TipoCelula *aux1, *aux2, *novo;
novo = (TipoCelula *) malloc(sizeof(TipoCelula));
if (novo == NULL) {
printf("\n\nErro de alocacao de memoria!");
return 0;
} 
else {
novo->Dado = dado;
// busca do local de insercao
if (ListaVazia(*lista)) { //eh o primeiro item?
lista->Inicio = novo;
novo->Proximo = NULL;
} 
else {
if (lista->Inicio->Dado.cod > novo->Dado.cod) {
novo->Proximo = lista->Inicio;
lista->Inicio = novo;
}
else { // insere no meio ou no fim da lista
aux1 = lista->Inicio;
aux2 = lista->Inicio->Proximo;
while((aux2 != NULL) && (aux2->Dado.cod < novo->Dado.cod)) {
aux1 = aux2;
aux2 = aux2->Proximo;
} //ao fim do while, insere entre aux1 e aux2
aux1->Proximo = novo;
novo->Proximo = aux2;
}
}
}
return 1;
}
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 62
O ponteiro lista recebe o início da lista. A inserção de um nó
está ocorrendo de forma ordenada.
A Figura 3.4.a mostra uma lista com três registros e a Figura 3.4.b
ilustra a inserção do quarto registro entre dois nós. Observa-se que é
necessário atualizar o ponteiro do nó anterior para encadear com o
novo nó e o ponteiro deste último encadeará com o próximo.
Caso a inserção seja no início da lista, o ponteiro lista terá que ser
atualizado para endereçar (apontar) o novo nó e caso seja no final, o
ponteiro do novo nó receberá valor nulo.
Figura 3.4: Inserção ordenada de nós.
Para fazer a impressão das informações constantes da lista
deve-se cuidar para que o nó que guarda a referência (endereço) do
primeiro nó da lista não seja alterado. A chamada ao módulo de
impressão (listar) é feita passando a lista por valor, pois, dessa
forma, uma eventual alteração dos dados será considerada apenas a
nível local
ao procedimento.
A fim de evitar qualquer alteração do ponteiro que contém o
início da lista, mesmo sendo passado ao módulo chamado por valor,
lança-se mão de um ponteiro auxiliar para percorrer os nós da
estrutura. No exemplo foi usado o ponteiro noatual, que permite o
acesso às informações constantes de cada nó da lista.
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
63
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 63
Programa 3.10: Imprime os nós da lista.
void ListarItens(TipoLista lista) {
TipoCelula *aux;
if (ListaVazia(lista))
printf("Erro: Nao ha produtos cadastrados!");
else {
aux = lista.Inicio;
printf("\n\nProdutos cadastrados:");
do {
printf("\nCodigo: %5d", aux->Dado.cod);
printf("\nEspecificacao: %s", aux->Dado.especif);
printf("\nPreco: %6.2f ", aux->Dado.preco);
printf("\nQuantidade: %3i", aux->Dado.quant);
noatual = aux->Proximo;
} while (aux != NULL);
}
}
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
64
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 64
CAPÍTULO 4
Pilhas
4.1 Introdução
Para a implementação do Tipo Abstrato de Dados Pilha, é preciso,
inicialmente, definir os tipos necessários para a sua criação. Seguindo
a disciplina de acesso “o último que entra é o primeiro a sair” ou do
inglês LIFO (Last In, First Out), será mostrado o conteúdo dos
arquivos deste TAD: 
• Arquivo de cabeçalho (pilha.h). Contém as definições de tipo
(typedef) e a interface das funções;
• Arquivo fonte (pilha.c). Armazena a implementação das
operações definidas sobre o TAD Pilha.
As operações detalhadas neste capítulo são:
• Função Empilha;
• Função Desempilha;
• Função Consulta_Topo;
• Função Pilha_Vazia.
Nas próximas seções serão mostradas as implementações
utilizando as abordagens estática (com o uso de vetores) e dinâmica
(utilizando apontadores e alocação dinâmica de memória).
4.2 Pilhas implementadas por vetores
O TAD Pilha será mostrado nesta seção com a utilização de vetores
para o armazenamento dos dados a serem empilhados e
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
65
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 65
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
66
desempilhados. O código será mostrado em partes. O trecho de códi-
go mostrado no programa 4.1 mostra as definições de tipo. Note que
o TipoChave é definido como uma estrutura, de forma a facilitar a
personalização desta informação para cada aplicação. A mesma idéia
é vista na estrutura TipoDado. A Pilha propriamente dita é formada
pelo índice Topo e o vetor de dados, com tamanho definido com a
constante simbólica Max, descrita pela estrutura TipoPilha.
Programa 4.1: Definições de tipo e interface das operações do TAD Pilha.
O procedimento Cria_Pilha (Programa 4.2) é necessário a fim de
inicializar a variável Topo logo após a criação da variável Pilha. Na
Linguagem C, o primeiro elemento dos vetores é o 0 (zero), portanto,
o Topo inicia com uma unidade a menos, -1, indicando que a pilha
#ifndef PILHA_H_
#define PILHA_H_
#define Max 3
typedef int TipoChave;
typedef struct {
TipoChave chave;
/* outros campos */
} TipoDado;
typedef struct {
int Topo;
TipoDado Dados[Max];
} TipoPilha;
void Cria_Pilha(TipoPilha *pilha);
int Pilha_Vazia(TipoPilha pilha);
int Empilha(TipoPilha *pilha, TipoDado dado);
int Desempilha(TipoPilha *pilha, TipoDado *dado);
int Consulta_Topo(TipoPilha pilha, TipoDado *dado);
#endif /*PILHA_H_*/
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 66
está vazia. A variável pilha é recebida por referência, possibilitando a
atualização permanente dos seus dados.
Programa 4.2: Procedimento Cria_Pilha.
O processo de empilhar um dado foi implementado como uma
função a fim de permitir o retorno de um código de sucesso
(VERDADEIRO) ou insucesso (FALSO). A função Empilha (PUSH), é
mostrada no Programa 4.3. A variável pilha é passada por referência
à função e o dado é copiado do parâmetro dado para a próxima
posição livre na pilha (Topo). 
Primeiramente a função testa se a pilha está cheia. Em caso afir-
mativo, é mostrada uma mensagem de erro e é retornado um código
de erro, FALSO (0). Caso haja espaço no vetor, a variável Topo é incre-
mentada, representando a próxima posição livre no vetor, e o novo
dado é inserido no topo da pilha. Neste caso o sucesso é sinalizado
pelo valor de retorno VERDADEIRO (1).
Programa 4.3: Função Empilha
int Empilha(TipoPilha *pilha, TipoDado dado)
{
if (pilha->Topo == (Max - 1)) //pilha cheia
{
printf("\n\nErro: Pilha Cheia!");
return 0;
}
else
{
pilha->Topo++;
pilha->Dados[pilha->Topo] = dado;
return 1;
}
}
void Cria_Pilha(TipoPilha *pilha)
{
pilha->Topo = -1;
}
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
67
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 67
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
68
A fim de desempilhar (POP) os elementos da pilha, a função
Desempilha, mostrada no Programa 4.4, recebe por referência a
variável pilha e uma variável de apoio dado, que retornará, como
parâmetro o dado desempilhado. O valor de retorno trata do sucesso
ou insucesso da operação.
De início, a função testa se a pilha está vazia. Neste caso, sendo
impossível desempilhar um dado inexistente, uma mensagem de erro
é mostrada e o valor FALSO (0) é retornado. 
Se houver ao menos um dado da pilha, o dado a ser removido é
copiado para o parâmetro dado1 e a variável Topo é decrementada,
indicando que o novo elemento Topo é o item anterior. Nesta situação
o valor de retorno é o VERDADEIRO (1).
Programa 4.4: Função Desempilha.
A função lógica Consulta_Topo (Programa 4.5) pode ser utilizada
por aplicações que precisam conhecer o elemento do topo da pilha,
sem contudo, removê-lo. Sendo uma função lógica, retorna
VERDADEIRO (1) quando a consulta pode ser efetivada e FALSO (0) caso
contrário. O elemento consultado é retornado por parâmetro na
variável dado, passada por referência. Note que a pilha, por não ser
modificada pela função, não foi passada por referência, e sim, por
valor.
____________________________
1 Lembre-se de que a idéia de se retornar o item removido é poder utilizá-lo pela função que solicitou a remoção.
int Desempilha(TipoPilha *pilha, TipoDado *dado)
{
if (Pilha_Vazia(*pilha)) //pilha vazia
{
printf("\n\nErro: Pilha Vazia!");
return 0;
}
else
{
*dado = pilha->Dados[pilha->Topo];
pilha->Topo--;
return 1;
}
}
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 68
Programa 4.5: Função Consulta_Topo.
A função Pilha_Vazia, mostrada no Programa 4.6, auxilia a
implementação das demais funções. Ela testa se a pilha está vazia,
retornando o valor lógico VERDADEIRO (1) ou FALSO (0) conforme o
caso. Lembre-se de que o valor do Topo para a pilha vazia corresponde
ao -1. Esta função lógica é utilizada nas funções Consulta_Topo e
Desempilha.
Programa 4.6: Função Pilha_Vazia
No Anexo A é apresentada a implementação completa do
TAD Pilha utilizando vetores e um programa principal (aplicação)
exemplo.
int Pilha_Vazia(TipoPilha pilha)
{
if (pilha.Topo == -1)
return 1;
else
return 0;
}
int Consulta_Topo(TipoPilha pilha, TipoDado *dado)
{
if (Pilha_Vazia(pilha)) //pilha vazia
{
printf("\n\nErro: Pilha Vazia!");
return 0;
}
else
{
*dado = pilha.Dados[pilha.Topo];
return 1;
}
}
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
69
01_laboratorio_de_estrutura_de_dados_I.qxp
28/11/2008 13:29 Page 69
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
70
4.3 Pilhas implementadas por variáveis dinâmicas
Para implementar esta versão do TAD pilha, são necessários as
definições de tipo e interfaces das operações presentes no arquivo de
cabeçalho do TAD. Este arquivo é mostrado no Programa 4.7.
Programa 4.7: Definições de tipo e interface das operações do TAD Pilha.
#ifndef PILHAD_H_
#define PILHAD_H_
typedef int TipoChave;
typedef struct {
TipoChave chave;
/* outros campos */
} TipoDado;
typedef struct Celula {
TipoDado Dado;
struct Celula *Anterior;
}TipoCelula;
typedef struct {
TipoCelula *Topo;
} TipoPilha;
void Cria_Pilha(TipoPilha *pilha);
int Pilha_Vazia(TipoPilha pilha);
int Empilha(TipoPilha *pilha, TipoDado dado);
int Desempilha(TipoPilha *pilha, TipoDado *dado);
int Consulta_Topo(TipoPilha pilha, TipoDado *dado);
#endif /*PILHAD_H_*/
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 70
O procedimento Cria_Pilha, no Programa 4.8, inicializa o ponteiro
Topo com o valor NULL. Significa que este apontador não está
apontando para nenhuma área de memória. A variável pilha é passada
por referência ao procedimento.
Programa 4.8: Procedimento Cria_Pilha.
A função Empilha (PUSH) recebe a variável pilha por referência
e copia o dado para uma nova célula, recém alocada. Esta alocação é
testada para o caso de acontecer um erro, ocasionando o envio de
uma mensagem na tela e o retorno de um código FALSO (0),
indicando o insucesso. Caso a alocação seja bem-sucedida, a nova
célula é empilhada (aponta para a célula Topo) e o Topo recebe o
endereço da nova célula. Note que ao empilhar a primeira célula,
Novo irá apontar para NULL, valor inicial de Topo. Após o
empilhamento, a função, mostrada no Programa 4.9, retorna
VERDADEIRO (1).
void Cria_Pilha(TipoPilha *pilha)
{
pilha->Topo = NULL;
}
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
71
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 71
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
72
Programa 4.9: Função Empilha com alocação dinâmica.
A função Desempilha (POP) é vista no Programa 4.10. De início, é
verificado se a pilha está vazia. Caso afirmativo, uma mensagem de
erro é mostrada na tela e a função retorna FALSO. Isto acontece por
não ser possível desempilhar um item de uma pilha vazia. Caso a pilha
não esteja vazia, o dado a ser desempilhado (armazenado na célula
topo) é salvo no parâmetro dado. Em seguida, o endereço da célula
topo é salvo em um ponteiro auxiliar (aux), que é desalocado após o
Topo apontar para a célula anterior (de “baixo”). O Programa 4.10
mostra a função Desempilha. Perceba que ao remover a última
célula, o Topo passará a ser automaticamente igual a NULL.
int Empilha(TipoPilha *pilha, TipoDado dado)
{
TipoCelula *novo;
if((novo = (TipoCelula *) malloc(sizeof(TipoCelula))) == NULL)
{
printf("\n\nErro de alocacao de memoria!");
return 0;
}
else
{
novo->Dado = dado;
novo->Anterior = pilha->Topo;
pilha->Topo = novo;
return 1;
}
}
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 72
Programa 4.10: Função Desempilha com alocação dinâmica.
Para consultar a célula Topo a função vista no Programa 4.11
retorna por referência o dado daquela célula, mas apenas se houver
algum elemento na pilha. A função retorna VERDADEIRO ou FALSO,
indicando sucesso ou falha de consulta, respectivamente.
Programa 4.11: Função Consulta_Topo com alocação dinâmica.
int Consulta_Topo(TipoPilha pilha, TipoDado *dado)
{
if (Pilha_Vazia(pilha)) //pilha vazia
{
printf("\n\nErro: Pilha Vazia!");
return 0;
}
else
{
*dado = pilha.Topo->Dado;
return 1;
}
}
int Desempilha(TipoPilha *pilha, TipoDado *dado)
{
TipoCelula *aux;
if (Pilha_Vazia(*pilha)) //pilha vazia
{
printf("\n\nErro: Pilha Vazia!");
return 0;
}
else
{
*dado = pilha->Topo->Dado;
aux = pilha->Topo;
pilha->Topo = pilha->Topo->Anterior;
free(aux);
return 1;
}
}
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
73
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 73
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
74
A função Pilha_Vazia testa e retorna VERDADEIRO caso o
apontador Topo seja igual a NULL. Esta função é utilizada como apoio
aos demais procedimentos de manipulação de pilha. Esta função pode
ser vista no Programa 4.12.
Programa 4.12: Função Pilha_Vazia com alocação dinâmica.
int Pilha_Vazia(TipoPilha pilha)
{
if (pilha.Topo == NULL)
return 1;
else
return 0;
}
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 74
CAPÍTULO 5
Filas
5.1 Introdução
Nas Filas (em inglês queue), a disciplina de acesso é o primeiro
elemento que entra é o primeiro que sai. Trata-se da organização FIFO
(First In, Fist Out). A implementação deste Tipo Abstrato de Dados
inclui os arquivos:
• Arquivo de cabeçalho “fila.h”, contendo as definições de tipo e
as interfaces das operações do tipo abstrato de dados;
• Arquivo fonte “fila.c” com a implementação das operações de
acesso à fila.
As próximas seções detalham a implementação de filas utilizando
vetores e ponteiros com alocação dinâmica.
As operações do TAD Fila implementadas neste capítulo são:
• Função Enfileira;
• Função Desenfileira;
• Função Consulta_Frente;
• Função Fila_Vazia;
• Função Quantidade_Fila.
5.2 Filas implementadas por vetores
Para a implementação do TAD Fila utilizando vetores, são
necessárias as definições de tipo (typedef) , estruturas (structs) e as
interfaces das operações do TAD. O Programa 5.1 mostra estas
declarações de tipo inseridas no arquivo de cabeçalho (.h).
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
75
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 75
Tecnologia em Análise e
Desenvolvimento de Sistemas
Laboratório de
Estrutura de Dados I
76
Programa 5.1: Definições de tipo e interface das operações do TAD Fila.
O procedimento Cria_Fila, mostrado no Programa 5.2 inicializa
as variáveis do TAD fila->Frente e fila->Tras. Este procedimen-
to deve ser chamado pela aplicação antes de iniciar o uso da fila.
Programa 5.2: Procedimento Cria_Fila.
Para realizar o enfileiramento de um elemento, uma aplicação
utiliza a função mostrada no Programa 5.3. Esta função lógica recebe
a variável fila por referência e o dado a ser inserido por valor. O dado
void Cria_Fila(TipoFila *fila) {
fila->Frente = 0;
fila->Tras = -1;
}
#ifndef FILA_H_
#define FILA_H_
#define Max 100
typedef int TipoChave;
typedef struct {
TipoChave chave;
/* outros campos */
} TipoDado;
typedef struct {
int Frente, Tras;
TipoDado Dados[Max];
} TipoFila;
void Cria_Fila(TipoFila *fila);
int Fila_Vazia(TipoFila fila);
int Enfileira(TipoFila *fila, TipoDado dado);
int Desenfileira(TipoFila *fila, TipoDado *dado);
int Consulta_Frente(TipoFila fila, TipoDado *dado);
#endif /*FILA_H_*/
01_laboratorio_de_estrutura_de_dados_I.qxp 28/11/2008 13:29 Page 76
será inserido se a fila não estiver cheia. Caso a fila estiver cheia, uma
mensagem de erro será exibida e a função retorna um código de
insucesso (0). Caso haja espaço na fila, o elemento é inserido e a
função retorna um código de sucesso (1). 
Programa 5.3: Função Enfileira.
A função mostrada no Programa 5.4 é a Desenfileira. Esta
função retira um item do início da fila. As variáveis fila e dado são pas-
sadas por referência à função. Caso a fila esteja vazia, uma mensagem
de erro é exibida e a função retorna um