Técnicas de programação

Prévia do material em texto

PROF. MATEUS CONRAD BARCELLOS DA COSTA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
TÉCNICAS DE PROGRAMAÇÃO AVANÇADA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
[ Cidade Ex. VITÓRIA ] 
[ Ano ] 
 
 
Governo Federal 
Ministro de Educação 
Fernando Haddad 
CEFETES – Centro Federal de Educação Tecnológica do Espírito Santo 
Diretor Geral 
Jadir José Pela 
Diretor de Ensino 
Denio Rebello Arantes 
Coordenadora do CEAD – Centro de Educação a Distância 
Yvina Pavan Baldo 
Coordenadoras da UAB – Universidade Aberta do Brasil 
Yvina Pavan Baldo 
Maria das Graças Zamborlini 
Designer Instrucional 
Danielli Veiga Carneiro 
 
Curso de Tecnologia em Análise e Desenvolvimento de Sistemas 
Coordenação de Curso 
Isaura Nobre 
Professor Especialista/Autor 
Mateus Conrad Barcellos da Costa 
 
DIREITOS RESERVADOS 
Cefetes – Centro Federal de Educação Tecnológica do Espírito Santo 
Av. Vitória – Jucutuquara – Vitória – ES - CEP - (27) 3331.2139 
Créditos de autoria da editoração 
Capa: Leonardo Tavares Pereira 
Projeto gráfico: Danielli Veiga Carneiro 
Iconografia: Moreno Cunha 
Editoração eletrônica: Mateus Conrad Barcellos da Costa 
Revisão de texto: Karina Bersan Rocha 
COPYRIGHT – É proibida a reprodução, mesmo que parcial, por qualquer meio, sem 
autorização escrita dos autores e do detentor dos direitos autorais. 
 
Catalogação na fonte: Rogeria Gomes Belchior - CRB 12/417 
1. 
 
 
 
 
 
 
 
 
Técnicas de Programação Avançada / Mateus Conrad Barcellos da Costa. – Vitória: CEFETES, 
2008. 
 128 p. : il. 
1. Programação (Computadores). I. Centro Federal de Educação Tecnológica do 
Espírito Santo. II. Título. 
 
CDD 005.43 
 
 
Olá, Aluno(a)! 
 
 
 
 
 
 
É um prazer tê-lo conosco. 
O Cefetes oferece a você, em parceria com as Prefeituras e com o 
Governo Federal, o Curso Tecnologia em Análise e Desenvolvimento 
de Sistemas, na modalidade a distância. Apesar de este curso ser 
ofertado a distância, esperamos que haja proximidade entre nós, pois, 
hoje, graças aos recursos da tecnologia da informação (e-mails, chat, 
videoconferência, etc.) podemos manter uma comunicação efetiva. 
É importante que você conheça toda a equipe envolvida neste curso: 
coordenadores, professores especialistas, tutores a distância e tutores 
presenciais, porque quando precisar de algum tipo de ajuda, saberá a 
quem recorrer. 
Na EaD – Educação a Distância, você é o grande responsável pelo 
sucesso da aprendizagem. Por isso, é necessário que se organize para 
os estudos e para a realização de todas as atividades, nos prazos 
estabelecidos, conforme orientação dos Professores 
Especialistas e Tutores. 
Fique atento às orientações de estudo que se encontram 
no Manual do Aluno! 
A EaD, pela sua característica de amplitude e pelo uso de 
tecnologias modernas, representa uma nova forma de aprender, 
respeitando, sempre, o seu tempo. 
Desejamos-lhe sucesso! 
 
 
 
Equipe do CEFETES 
 
 
 
 
 
ICONOGRAFIA 
 
Veja, abaixo, alguns símbolos utilizados neste material para guiá-lo em seus estudos. 
 
 
 
Fala do professor. 
 
 
Conceitos importantes. Fique atento! 
 
 
Atividades que devem ser elaboradas por você, após a leitura dos textos. 
 
 
Indicação de leituras complementares, referentes ao conteúdo estudado. 
 
 
Destaque de algo importante, referente ao conteúdo apresentado. Atenção! 
 
 
Reflexão/questionamento sobre algo importante, referente ao conteúdo 
apresentado. 
 
 
Espaço reservado para as anotações que você julgar necessárias. 
 
 
 
 
Sumário 
1. ABSTRAÇÃO DE DADOS.......................................................................................................................... 9 
1.1 INTRODUÇÃO .......................................................................................................................................... 9 
1.2 CONCEITOS DE ABSTRAÇÃO DE DADOS ................................................................................................. 12 
1.2.1 Abstração em Computação.............................................................................................................. 12 
1.2.2 Abstração de Procedimentos ........................................................................................................... 14 
1.2.3 Tipos Abstratos de Dados................................................................................................................ 16 
1.2.4 Implementação de Tipos Abstratos de Dados.................................................................................. 23 
1.2.5 Avaliação de Implementações de Tipos Abstratos de Dados .......................................................... 25 
2. TIPOS ABSTRATOS DE DADOS FUNDAMENTAIS .......................................................................... 30 
2.1 PILHAS.................................................................................................................................................. 30 
2.1.1 Especificação do TAD Pilha............................................................................................................ 32 
2.1.2 Implementação de Pilhas em Arranjos............................................................................................ 34 
2.2 FILAS .................................................................................................................................................... 37 
2.2.1 Especificação do TAD FILA............................................................................................................ 39 
2.2.2 Implementação de Filas em arranjos com deslocamento................................................................ 42 
2.2.3 Implementação de Filas com Arranjos circulares........................................................................... 45 
2.3 IMPLEMENTAÇÃO DE TADS COM ALOCAÇÃO DINÂMICA DE MEMÓRIA................................................. 47 
2.3.1 Revisão de Alocação Dinâmica de Memória................................................................................... 47 
2.3.2 Implementação do TAD Pilha ......................................................................................................... 55 
2.3.3 Implementação do TAD Fila ........................................................................................................... 59 
3. LISTAS E ÁRVORES................................................................................................................................ 65 
3.1 LISTAS CIRCULARES ............................................................................................................................. 65 
3.2 LISTA CIRCULAR DUPLAMENTE ENCADEADA ....................................................................................... 75 
3.3 ÁRVORES BINÁRIAS.............................................................................................................................. 82 
3.3.1 Árvore Binária de Pesquisa............................................................................................................. 83 
3.3.2 O TAD Árvore Binária de Pesquisa ................................................................................................ 84 
3.3.3 Implementação do TAD árvore Binária de Pesquisa ...................................................................... 85 
4. PESQUISA EM MEMÓRIA PRIMÁRIA................................................................................................ 99 
4.1 PESQUISA SEQÜENCIAL ...................................................................................................................... 101 
4.1.1 Implementação da Pesquisa Seqüencial........................................................................................ 102 
4.1.2 Tempo de execução de algoritmos................................................................................................. 103 
4.2 PESQUISA BINÁRIA .............................................................................................................................106 
4.3 TABELAS HASH................................................................................................................................... 108 
4.3.1 Operações de Inserção e Pesquisa em Tabelas Hash.................................................................... 111 
4.3.2 Tratamento de Colisões ................................................................................................................. 114 
4.3.3 Tratamento de Colisão usando endereçamento Aberto................................................................. 116 
5. ORDENAÇÃO EM MEMÓRIA PRIMÁRIA ....................................................................................... 118 
5.1 CONCEITOS BÁSICOS DE ORDENAÇÃO ................................................................................................ 118 
5.1.1 Operações Típicas de processos de Ordenação ............................................................................ 119 
5.2 MÉTODOS DE ORDENAÇÃO ................................................................................................................. 119 
5.2.1 Ordenação por Seleção ................................................................................................................. 120 
5.2.2 Método da Inserção ....................................................................................................................... 121 
5.2.3 Método da Bolha ........................................................................................................................... 123 
5.2.4 Desempenho dos métodos de Seleção, Inserção e Bolha............................................................... 124 
5.2.5 Método de Shell ............................................................................................................................. 124 
5.2.6 O Método Quicksort ...................................................................................................................... 128 
REFERÊNCIAS ................................................................................................................................................ 132 
 
 
 
 
 
 
Olá! 
Meu nome é Mateus Barcellos Costa, sou 
professor e pesquisador do CEFET-ES desde 
2005. Atuo na área de Engenharia de Software e 
sou professor de disciplinas de Programação. Se 
voce quiser mais informações sobre mim e sobre 
os trabalhos que desenvolvo, pode visitar minha 
página pessoal em 
http://www.sr.cefetes.br/~mcosta. 
Produzi o material que ora lhe apresento como 
instrumento básico para o estudo da disciplina de 
Técnicas de Programação Avançada. Nesta 
disciplina iremos aprofundar nossos 
conhecimentos em Programação de 
Computadores usando uma linguagem imperativa 
ou procedimental. Exemplos destas linguagens 
são C e Pascal. Como de costume no nosso 
Curso, iremos adotar a linguagem C, em nossos 
exemplos e implementações. No entanto, é 
preciso que você saiba que os conceitos estudados 
aqui vão além da linguagem e podem ser 
aplicados em diversos cenários, na programação 
e na Engenharia de Software como um todo. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Técnicas de Programação Avançada
Página 9Centro Federal de Educação Tecnológica
1. ABSTRAÇÃO DE DADOS. 
 
 
Olá! Neste Capítulo iremos discutir e aprender 
sobre Abstração de Dados. Abstração de Dados é 
uma técnica de programação que visa simplificar 
o desenvolvimento de programas. Sua aplicação 
pode se dar no desenvolvimento de programas 
menores. Mas podemos afirmar que seria 
impossível o desenvolvimento de sistemas que 
temos hoje, com milhões de linhas de código, 
sem o uso de abstração de dados. 
 
1.1 INTRODUÇÃO 
Um programa de computador desenvolvido para atender alguma 
finalidade prática é, normalmente, um artefato complexo. Por esse 
motivo, a atividade de desenvolvimento desses artefatos, a 
programação de computadores, está entre as atividades mais 
complexas desempenhadas pelo homem. Se você cursou disciplinas 
introdutórias de programação, pode estar se questionando: Ora, 
desenvolver um programa não é tão complexo assim! Basta 
compreender o problema, suas entradas e suas saídas e construir a 
solução usando uma linguagem de programação. Simples não? Não! 
A história da programação tem dado provas que programar não é tão 
simples assim. 
 
 
Figura 1: O Gap Semântico. 
Programar é uma atividade complexa por diversos aspectos, tanto de 
cunho teórico quanto prático. Dentre estes aspectos destacamos os 
seguintes: 
1. Programar um computador significa desenvolver programas de 
computadores (formais e precisos) para atender a finalidades 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 10
 
práticas definidas em termos de conceitos do mundo real 
(informais e imprecisos). Existe um abismo entre o mundo 
dos problemas reais e o mundo das soluções. Esse abismo é 
chamado na computação de gap semântico. Transpor o abismo 
é um dos desafios centrais da programação de computadores e 
da Engenharia de Software como um todo. A Figura 1 é uma 
alegoria que busca mostrar a função do desenvolvedor de 
software: Transpor o abismo entre o mundo informal (dos 
problemas) e o mundo formal (das soluções computacionais). 
Nessa transposição existem muitos desafios e perigos que 
podem dificultar a trajetória do desenvolvedor. 
2. Muitas vezes, em disciplinas iniciais de programação, 
deparamo-nos com o desenvolvimento de programas mais 
simples, de cunho didático. Por exemplo, programas para 
calcular médias ou somatórios. Em outros momentos fazemos 
programas para aprender a usar um certo mecanismo, por 
exemplo, apontadores. Aqui, estamos nos referindo a 
programas de computadores para ajudar pessoas a resolverem 
problemas do mundo real, problemas grandes e complexos! 
Exemplos desses problemas incluem: 
a. Gerenciar as operações financeiras de uma empresa; 
b. Controlar uma aeronave; 
c. Controlar os trens de uma malha ferroviária; 
d. Produzir edições diárias de um jornal; 
e. Gerenciar o processo de produção de um filme. 
3. Problemas como esses não são simples de se resolver. 
Conseqüentemente, programas voltados para essas finalidades 
são complexos, levam muito tempo para ficar prontos, têm de 
ser desenvolvidos por uma equipe de pessoas, utilizando 
diversas tecnologias e seguindo um processo de 
desenvolvimento sistemático. 
4. Para atender às funcionalidades esperadas, um programa deve 
apresentar um conjunto de características que juntas vão 
tornar o programa efetivamente útil e determinarão a 
qualidade do mesmo. Essas características são as seguintes: 
a. Um programa deve estar correto, livre de erros; 
b. Um programa deve ser robusto. Um programa robusto 
ou sistema robusto é aquele que consegue funcionar, 
mesmo que precariamente, diante de uma adversidade. 
Por exemplo, suponha que um programa precise dos 
dados x, y e z para realizar uma tarefa. Se este for 
robusto, na falta de um dos dados, o programa pode 
Técnicas de Programação Avançada
Página 11Centro Federal de Educação Tecnológica
 
 
tentar realizar o processamento possível com a 
ausência dado; 
c. Um programa deve ser eficiente. A eficiência de um 
programa está relacionada ao seu tempo de execução 
(eficiência na execução) ou ao espaço em memória 
(eficiência na ocupação) de que necessita para executar 
(área de dados). Para um problema há infinitas 
soluções (programas). Quanto menores esses valores 
mais eficiente o programa. Em computação pode-se 
verificar se uma solução é ótima (mais eficiente 
possível) para um problema; 
d. Um programa deve ser compatível com outros 
programas; 
e. Um programa deve ser fácil de usar; 
f. Um programa deve ser portável, podendo funcionar em 
diferentes plataformas ou sistemas operacionais; 
g. Um programa deve ser íntegro, ou seja, deve evitar que 
os dados sejam corrompidos ou violados; 
h. O processamento realizado pelo programa deve ser 
verificável; 
i. O programa ou partes dele devempoder ser utilizados 
em outros cenários diferentes daquele para o qual o 
programa foi originalmente desenvolvido. 
5. Por último, devemos considerar a atividade de programação 
como atividade econômica. Assim como outras atividades 
econômicas, o desenvolvimento de software é regido por leis 
de mercado que impõem severas exigências aos 
desenvolvedores. De acordo com essas leis, não basta apenas 
desenvolver um programa que atenda à finalidade esperada. 
Esses programas devem ser desenvolvidos dentro dos prazos e 
custos estabelecidos. Além disso, o programa precisa ter 
outras características importantes que permitam a sua 
evolução. Essas características são chamadas de fatores 
internos. São eles: 
a. Facilidade de manutenção; 
b. Facilidade de evolução; 
c. Facilidade de entendimento; 
d. Modularidade. 
Pelos motivos discutidos acima, o desenvolvimento de programas 
requer a aplicação de princípios, métodos e técnicas que diminuam a 
complexidade desse desenvolvimento. A Abstração de Dados envolve 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 12
 
uma série de conceitos e princípios para esse fim. A seguir 
discutiremos esses conceitos. 
 
 
Atividades 
 Nesta introdução foram levantados cinco aspectos que 
tornam o desenvolvimento de software uma tarefa 
difícil. Para atacar esses aspectos e tornar o 
desenvolvimento de software mais simples são 
consideradas três dimensões: Processo de 
desenvolvimento, Pessoas (partes interessadas: 
clientes, desenvolvedores) e Tecnologias de 
desenvolvimento. Releia os cinco motivos e tente 
escrever um texto resumido, estabelecendo uma 
relação entre esses 5 motivos e essas três dimensões. 
 
 
1.2 CONCEITOS DE ABSTRAÇÃO DE DADOS 
1.2.1 Abstração em Computação 
A abstração é um dos conceitos mais importantes da computação. 
Sem o uso deste conceito podemos afirmar que a evolução 
apresentada pela computação teria sido mais lenta. 
Segundo o dicionário Michaelis, temos a seguinte definição para a 
palavra Abstração: 
1. O ato ou efeito de abstrair. Consideração das qualidades 
independentemente dos objetos a que pertencem. Abstrair: Considerar 
um dos caracteres de um objeto separadamente; 2. Excluir, prescindir 
de. 
A finalidade principal de uso de abstração em qualquer área do 
conhecimento é colocarmos foco em um sub-conjunto dos aspectos 
de um sistema ou processo complexo. Considere, por exemplo, o 
processo de pintar um quadro. A Figura 2 mostra, à esquerda um 
esquema inicial mostrando as linhas principais do quadro que se 
encontra do lado direito (A Virgem, o Menino e Sant’Ana, Leonardo 
Da Vinci). 
Técnicas de Programação Avançada
Página 13Centro Federal de Educação Tecnológica
 
 
 
 
 
 
 
 
 
 
 
Figura 2: Abstração na Pintura. 
Observe que, no desenho, as proporções, os detalhes das posturas e 
feições são já determinados. Esse processo ajuda o pintor, pois, no 
momento da idealização do quadro, ele não precisa se preocupar com 
outros aspectos complexos, como cores, nuances de sombras e 
reflexos, para definir a estrutura e a sua aparência geral. Podemos 
dizer então que o desenho à esquerda é uma abstração do quadro. 
Em computação, abstração também possui finalidades semelhantes. 
Em programação, especificamente, esse conceito está presente quase o 
tempo todo, seja nas construções existentes nas linguagens, seja nos 
métodos de programação empregados. 
Uma das principais abstrações das linguagens de programação é o 
conceito de variável. Uma variável é um conceito abstrato que 
esconde diversos aspectos técnicos que não interessam ao 
programador. Quando declaramos uma variável em um programa, essa 
declaração implica em “coisas” que não irão interferir no seu 
desenvolvimento. Por exemplo, por trás de uma variável do tipo 
inteiro em C, (ex. int x;), estão “escondidas” as características físicas 
do armazenamento da variável em memória, a saber: 
- A forma de representação de números inteiros usando base 2 
(por exemplo, complemento de 2); 
- O padrão usado pelo hardware (ex. little endian, big endian); 
- O número de bytes que uma variável do tipo inteiro ocupa; 
- O endereço da variável na memória principal; 
- O conjunto de bits responsável por armazenar o sinal do 
número inteiro. 
Para o programador em C, geralmente, nenhuma dessas 
informações é importante. O que o programador deseja é utilizar a 
variável realizando as operações permitidas aos números inteiros 
(operações aritméticas e comparações), atribuir, recuperar e 
modificar o valor contido na variável. 
 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 14
 
Assim podemos dizer que uma variável permite ao programador 
abstrair-se de detalhes que não interessam e não irão influenciar no 
comportamento do programa. 
 
Atividades 
 Os itens 1,2 e 3 são abstrações. Para cada um deles 
descreva os aspectos que estão sendo escondidos e 
os aspectos que realmente importam ao 
programador: 
1. O comando 
 
2. Um arquivo 
3. A função scanf 
 
1.2.2 Abstração de Procedimentos 
Podemos afirmar que a grande maioria dos elementos de linguagem 
utilizados em uma linguagem de programação de alto nível são 
abstrações. Essas abstrações facilitaram o desenvolvimento de 
programas mais complexos e sofisticados, evitando que 
programadores precisassem manipular bits e endereços de memória e 
interagir diretamente com o sistema operacional. 
Uma outra abstração de programação importante é a Abstração de 
Procedimento. 
 
Abstração de Procedimento 
A abstração de procedimento permite que o programa-
dor crie, ele mesmo, sua “forma de abstrair”, utilizando 
os comandos disponíveis na linguagem. A possibilidade 
de criar procedimentos permite ao programador criar 
funcionalidades mais abstratas que “escondem” a 
sequencia de operações necessária para a realização de 
uma tarefa complexa. 
 
Técnicas de Programação Avançada
Página 15Centro Federal de Educação Tecnológica
 
 
Por exemplo, sabemos que na linguagem C não existe um comando 
que seja capaz de ordenar um vetor de inteiros em ordem crescente. 
Seria muito bom que pudéssemos contar com esse comando, certo? 
Mas, como não temos esse comando, iremos criar uma função 
(abstração de procedimento) que realize essa tarefa para nós. A função 
ordena na Figura 3 é essa abstração. 
Figura 3: Função ordena: Cria uma abstração do procedimento de ordenação. 
Após a implementação da função ordena, quando o programador 
precisar ordenar um vetor, basta que ele invoque a função, passando 
os parâmetros necessários. Ou seja, ao usar o procedimento, o 
programador irá se preocupar apenas com o que a função faz e não 
mais com os detalhes de sua implementação. 
Uma abstração de procedimento deve realizar uma tarefa (por 
exemplo, ordenar um vetor de inteiros) que deve ser independente da 
forma como este vai ser implementado. O programador deve antes de 
tudo ver o procedimento como uma caixa preta, cuja especificação 
deve conter três elementos básicos (Figura 4): 
 Entrada: O conjunto de dados de entrada necessário; 
 Saída: O conjunto de dados produzido pelo procedimento; 
 Função: A descrição do que o procedimento faz. 
 
 
 
Figura 4: Os elementos considerados na definição de um procedimento. 
 
Na especificação do procedimento, o programador não deve estar 
preocupado com a implementação, mas sim com o comportamento 
(função) do mesmo. Qualquer implementação que realize a função 
especificada irá servir como solução. Para o caso da ordenação, 
veremos adiante neste curso que existem diferentes métodos de 
ordenar um vetor. O método utilizado na função ordena se chama 
ordenação por inserção. A implementação interna poderia ser 
 
 
ENTRADA SAÍDA 
FUNÇÃO 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 16
 
substituída por qualquer outro método de ordenação. A própria 
linguagem C oferece em sua biblioteca padrão stdlib, uma função 
chamada qsort, que pode serusada para ordenar vetores. Essa 
função utiliza um outro método de ordenação muito conhecido e 
também muito rápido, chamado de Quick Sort. 
 
 
Atividades 
 1. Suponha que você tenha disponíveis as 
seguintes funções em C: 
 Int CalculaMedia(int *notas); 
 Void 
DeterminaMaiorEMenorNotas(int 
*v, int * maior, int *menor); 
 Void leNotas(int *notas); 
 Void MostraResultados(int 
media,int maiorNota, int 
menorNota); 
Utilizando essas funções, desenvolva um programa em 
C que leia as notas de 5 turmas e para cada uma delas, 
imprima a média, a maior e a menor nota. 
1.2.3 Tipos Abstratos de Dados 
A abstração de dados visa aos mesmos objetivos que a abstração de 
procedimentos, mas com relação às estruturas de dados utilizadas nos 
programas. A abstração de dados visa criar novos tipos de dados 
definidos em temos de seu comportamento. Esses novos tipos são 
chamados de Tipos Abstratos de Dados - TAD. 
É muito importante que você perceba que um tipo abstrato de dados 
não se resume a uma nova estrutura de dados. Vamos então discutir 
um pouco sobre essa diferença. 
Primeiramente, uma estrutura de dados pode ser definida 
simplesmente como uma variável capaz de armazenar mais de um 
valor simultaneamente. Assim, um vetor, uma matriz ou um registro 
(struct em C) são exemplos de estruturas de dados. A combinação 
desses elementos em estruturas mais complexas dá origem a outras 
estruturas de dados. A Figura 5 apresenta as declarações de struct 
ponto e struct reta, como exemplos de tipos de estruturas 
de dado. 
 
Técnicas de Programação Avançada
Página 17Centro Federal de Educação Tecnológica
 
 
 
 
 
 
 
Figura 5: Estruturas de Dados ponto e reta. 
Ao definir a struct ponto, passamos a contar com mais uma 
alternativa para definição de tipos de variáveis e, conseqüentemente, 
para a composição de novos tipos de estruturas. Assim a struct 
reta foi definida como uma composição de duas variáveis do tipo 
struct ponto. Essas estruturas podem ser usadas para declarar 
tanto variáveis como argumentos de funções. 
Em C temos ainda a cláusula typedef, que permite definir o nome 
do novo tipo. Nesse caso, não precisamos usar a palavra reservada 
struct na declaração de variáveis do tipo definido. Na Figura 6 
temos o uso de typedef. Veja que na definição do tipo Reta, o 
nome Ponto é usado sem a palavra reservada struct. 
 
 
 
 
 
Figura 6: Definição dos tipos Reta e Ponto. 
 
 
Estrutura de Dados versus Tipo Abstrato de Dados 
A definição de uma estrutura de dados se preocupa em 
demonstrar como o objeto é representado na memória 
de um computador (representação). Nessa definição são 
considerados aspectos do tipo: quais as informações que 
serão armazenadas ali e qual a quantidade destas 
informações. A definição de um Tipo Abstrato de 
Dados segue uma abordagem diferente. Essa definição é 
feita em termos das operações que podem ser realizadas 
sobre o tipo. 
A definição de um Tipo Abstrato de Dado (TAD) é 
chamada de especificação e consiste, basicamente, em 
definir as operações relacionadas ao tipo. Dizemos que 
essas operações definem o comportamento do TAD. 
 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 18
 
Vamos aplicar o conceito de TAD considerando os objetos Reta e 
Ponto. Um passo importante na definição do TAD, que já ajuda na 
programação de uma maneira geral, é que não conseguimos defini-lo 
sem conhecermos a sua finalidade e o contexto no qual será usado. 
Em nosso exemplo precisamos saber para quê nós queremos um 
ponto e uma reta. Geralmente essa informação é conseguida a partir 
do enunciado do problema. Assim, vamos supor a seguinte descrição 
para o nosso problema envolvendo retas e pontos: 
Problema A. É necessário um programa de computador que realize 
operações geométricas envolvendo pontos e retas localizadas no 
plano cartesiano. O programa deve permitir: calcular a distância do 
ponto até a origem do plano cartesiano; calcular a distância entre 
dois pontos; dada a representação da reta por dois pontos, calcular o 
ângulo de inclinação da reta, fornecer os parâmetros a e b 
correspondentes a equação da reta ax + b. Determinar a distância de 
uma reta a um ponto. Evidentemente, o programa deve permitir a 
leitura e impressão de pontos e retas conforme a necessidade das 
operações. 
Com base na descrição acima podemos identificar a necessidade do 
TAD ponto e do TAD Reta, bem como suas operações. Essas 
operações aparecem sublinhadas no texto do problema e são 
apresentadas nas Figuras 7 e 8. 
 
 
 
 
 
 
 
Figura 7: operações do TAD Ponto para o problema A. 
 
 
 
 
 
 
 
 
 
Figura 8: operações do TAD Reta para o problema A. 
Técnicas de Programação Avançada
Página 19Centro Federal de Educação Tecnológica
 
 
Agora, considere que estejamos desenvolvendo um programa para o 
problema abaixo: 
Problema B. É necessário um programa de computador para 
apresentar graficamente figuras geométricas formadas por pontos e 
retas, usando o monitor do computador como plano. O programa 
deve permitir: ler um ponto, plotar um ponto na tela, ligar dois pontos 
por um segmento de reta; dada uma reta passando por esse ponto, 
deslocar um outro ponto com base na equação dessa reta; dada uma 
reta representada por dois pontos, plotar esta reta no monitor; dada 
uma reta e um valor d, criar uma reta paralela à reta dada a uma 
distancia d da reta. 
As operações necessárias aos TAD Ponto e Reta neste problema são 
apresentadas nas Figuras 9 e 10. 
 
 
 
 
 
Figura 9: operações do TAD Ponto para o problema B. 
 
 
 
 
Figura 10: operações do TAD Reta para o problema B. 
 
 
Note que nos dois problemas foram definidos os tipos 
Ponto e Reta. No entanto, a abstração necessária difere 
de um problema para o outro, interferindo na definição 
das operações. Embora existam essas diferenças, iremos 
sempre tentar criar abstrações mais genéricas o quanto 
for possível. Quanto mais genérico um TAD, maior o 
número de problemas em que esse poderá ser aplicado. 
 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 20
 
 
Embora as operações não informem nada a respeito da 
representação interna de um TAD, elas fornecem ao 
programador tudo o que ele precisa para manipular o 
TAD. As operações de um TAD especificam a sua 
interface com o restante do programa. Isso significa que 
qualquer ação relacionada ao TAD deve ser feita 
mediante uma de suas operações. 
Temos como resultado prático que o programador, ao 
usar o TAD, não vai precisar se preocupar com sua im-
plementação interna. Iremos agora analisar esse aspecto 
considerando os TAD Ponto e Reta e o problema A. 
 Na implementação, ponto e reta foram definidos e implementados, 
originando dois módulos independentes: o módulo Ponto e o módulo 
Reta. Cada módulo em C é normalmente implementado por dois 
arquivos: o arquivo .h e o arquivo .c. No arquivo .c teremos a 
implementação das operações do TAD e no arquivo .h teremos a 
especificação da interface do TAD. A Figura 11 e a Figura 12 
apresentam as interfaces dos módulos Ponto e Reta, respectivamente. 
Figura 11: Interface do TAD Ponto. 
Figura 12: Interface do TAD Reta. 
Com a implementação dos TADs Ponto e Reta concluídas e 
devidamente testadas, qualquer outro módulo do programa poderá 
utilizar esses tipos por meio das operações definidas para os mesmos. 
Quando um módulo A utiliza um módulo B em programação, 
dizemos que o módulo A é cliente do módulo B. Essa relação de 
“clientela” entre os módulos (ou TADs) de um programa pode ser 
representada graficamente por meio de um diagrama de estrutura 
modular - DEM. 
Técnicas de Programação Avançada
Página 21Centro Federal de Educação Tecnológica
 
 
 
Diagrama de Estrutura Modular 
Um diagrama de estrutura modular é formado por 
retângulos e linhas direcionadas relacionando os 
retângulos. Cada retângulo representa um módulo. As 
linhas direcionadas significam “cliente de” e indicam o 
acionamentode operações contidas no módulo apontado 
pelo módulo cliente. Esses digramas também são 
chamados diagramas hierárquicos, pois apresentam a 
hierarquia dos módulos, iniciando por um módulo que 
inicia o programa e acionam os demais módulos. 
Como exemplo, suponha que tenhamos também, junto aos módulos 
Ponto e Reta, um módulo chamado principal. Esse módulo é cliente 
dos módulos Ponto e Reta. A Figura 13 a seguir ilustra o DEM deste 
programa. O módulo que inicia o programa é o módulo principal (e 
deve conter uma função main()). Ele aciona as operações tanto do 
módulo ponto quanto do módulo reta. Reta, por sua vez, também é 
cliente do módulo ponto. 
 
 
 
 
 
Figura 13: DEM com módulos Ponto, Reta e Principal. 
A Figura 14 ilustra a implementação de um módulo Principal. Note 
que a única forma de acesso aos TADs Ponto e Reta é por meio das 
operações definidas em suas respectivas interfaces. 
 
Use diagramas de estrutura modular sempre que for 
iniciar um novo projeto. Defina os TADs e estabeleça o 
relacionamento entre eles por meio de DEMs. Junto às 
linhas, você pode especificar as operações do TAD que 
são acionadas pelo cliente. Isso vai ajudar você na 
especificação dos TADs. 
 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 22
 
 
Atividades 
 Implementar as operações do TadPonto e do TadReta 
considerando o enunciado do problema 1, da Seção 1.2.3 
do texto, e desenvolver um programa usando a função 
principal (do quadro a seguir) de forma a testar as 
operações. 
Figura 14: Módulo Principal para o Problema A. 
Técnicas de Programação Avançada
Página 23Centro Federal de Educação Tecnológica
 
 
 
Até o momento, em nosso exemplo envolvendo Ponto e 
Reta, não abordamos a questão de como as operações 
serão implementadas propositalmente. É que até a 
parte que apresentamos do desenvolvimento não 
precisamos saber mesmo. Você por acaso lembra como 
se calcula a distância entre dois pontos? E a distância 
entre uma reta e um ponto? Pois bem, o importante é 
que você tenha compreendido a discussão feita e o 
exemplo dado, mesmo sem saber responder essas duas 
perguntas. Assim espero! 
 
1.2.4 Implementação de Tipos Abstratos de Dados 
 
Um dos principais benefícios da abstração de dados é 
separar o comportamento do TAD, especificado por 
meio da definição de suas operações, da sua 
implementação. Em nosso exemplo, o que definimos a 
respeito dos TAD Ponto e Reta foi o seu 
comportamento, as suas operações. Nesta seção, 
discutiremos melhor como separar em um projeto a 
definição do comportamento e da implementação de um 
TAD. 
 
O projeto completo de um TAD consiste de dois passos: 
1. Especificação - Consiste na especificação do comportamento 
do TAD; 
2. Implementação – Implementação das operações e estruturas 
de dados. 
Especificação 
A especificação de um TAD descreve o que TAD faz, mas omite 
informações sobre como o mesmo é implementado. Por omitir 
detalhes de implementação, uma única especificação permite muitas 
implementações diferentes. 
A especificação é feita por meio da definição das operações do TAD. 
Para detalhar melhor cada uma destas operações, devemos estabelecer, 
para cada operação, dois elementos: 
- Pré-condições: definem as condições necessárias para que a 
operação possa ser realizada. Por exemplo, suponha que 
desejamos especificar o TAD Conjunto com a operação 
listarConjunto. Uma pré-condição para essa operação é 
que o Conjunto não esteja vazio. 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 24
 
- Pós-condições: definem o estado do TAD após a execução da 
operação. Por exemplo, suponha a operação 
inserirElemento no TAD conjunto. Uma pós-condição 
para essa operação seria: elementos no conjunto = elementos 
no conjunto + novo elemento. A Figura 15 ilustra a definição 
do TAD conjunto. 
 
 
 
 
 
 
 
 
 
Figura 15: Especificação do TAD Conjunto. 
Implementação 
Um TAD é implementado por um módulo de um programa. Uma 
única especificação permite diferentes implementações para um 
mesmo TAD. Uma implementação está correta se esta provê o 
comportamento especificado para o TAD. Implementações corretas 
podem diferir uma da outra, por exemplo, em termos do algoritmo ou 
da estrutura de dados que elas usam. Essas diferenças interferem na 
eficiência (desempenho em tempo de execução, ou ocupação de 
espaço) apresentado pelo TAD para realização das operações. 
 
Encapsulamento 
Para uma abstração funcionar corretamente, a sua 
implementação deve ser encapsulada. Se a 
implementação for encapsulada, nenhum outro módulo 
do programa vai depender de detalhes de 
implementação do TAD. Encapsulamento garante que 
módulos do programa podem ser implementados e re-
implementados independentemente, sem afetar os outros 
módulos do programa. 
 
O encapsulamento geralmente é conseguido por meio da separação da 
interface e da implementação do módulo. Conforme já vimos 
anteriormente, em C a implementação de um TAD por meio de um 
módulo consiste em duas partes: a especificação da interface do 
Técnicas de Programação Avançada
Página 25Centro Federal de Educação Tecnológica
 
 
módulo por meio do arquivo header (com extensão.h) e da implemen-
tação das operações por meio de um arquivo com extensão .c. 
1.2.5 Avaliação de Implementações de Tipos Abstratos de 
Dados 
 
É fundamental para um programador saber criticar e 
avaliar a qualidade de uma implementação! Uma 
implementação baseada em Abstração de Dados é um 
indicativo de boa qualidade. Nesta Seção, discutiremos 
elementos que permitem que você verifique se uma 
implementação realmente está de acordo com essa 
técnica. 
 
Embora a linguagem C não ofereça um mecanismo que impeça 
realmente que o programador tenha acesso à estrutura interna do TAD, 
esta é uma regra fundamental e deve ser respeitada pelo programador. 
Esta regra ou característica de TADs é o encapsulamento, discutido na 
seção anterior. Dizemos que um TAD é encapsulado por suas 
operações no sentido de que a estrutura interna do TAD fica 
preservada e invisível ao restante do programa. Violar essa regra 
significa não usar corretamente a Abstração de Dados. 
 
Localidade 
O maior benefício do encapsulamento chama-se 
princípio da Localidade. Esse princípio permite que um 
programa seja implementado, entendido e modificado 
um módulo de cada vez. A localidade aumenta a 
qualidade do software que está sendo desenvolvido. 
 
Dentre os benefícios oriundos do princípio da localidade temos: 
1. O programador de uma abstração sabe o que é necessário pelo 
que está descrito na especificação. Dessa forma, ele não 
precisa interagir com programadores de outros módulos (ou, 
pelo menos, essa interação vai ser bem limitada). 
2. De forma análoga, o programador de um módulo que usa a 
abstração sabe o que esperar desta abstração, apenas pelo 
comportamento descrito em sua especificação. 
 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 26
 
 
Uma ferramenta que pode contribuir para esse 
entendimento é a documentação do TAD. Ou seja, a 
explicação sobre o seu funcionamento e sobre como 
utilizá-lo. Procure sempre fazer uma boa documentação 
do TAD. Essa documentação pode vir como um 
documento à parte que acompanha o módulo. 
 
3. É necessário apenas o raciocínio local (por módulo), para saber 
o que o programa faz e se está fazendo a coisa certa. Para 
estudar e compreender o programa podemos dividi-lo em 
módulos, e analisar um módulo de cada vez. Em cada caso, 
preocupamo-nos em saber se o módulo faz o que é suposto que 
faça. Ou seja, se ele cumpre o que está na especificação. 
Pode-se assim limitar a atenção para um módulo, ignorando 
tanto os módulos usados por este quanto os que o utilizam. Os 
módulos que utilizam o módulo estudado podem ser ignorados 
porque dependem apenas de sua especificação e não da sua 
implementação. Os módulos utilizados são ignorados, 
raciocinando-sesobre o que eles fazem utilizando apenas sua 
especificação em vez de sua codificação. Com isso, tem-se 
uma grande economia de esforço, dado que as especificações 
são muito menores que as implementações. Observando-se 
apenas as especificações evita-se também um efeito cascata. 
Por exemplo, se tivermos que olhar o código do módulo que 
utilizamos, teremos que olhar também o código dos módulos 
que são utilizados pelos módulos que utilizamos e assim por 
diante. 
4. Finalmente, a modificação do programa pode ser feita módulo 
por módulo. Se uma abstração particular necessita ser 
reimplementada para prover um melhor desempenho, corrigir 
um erro ou prover uma nova funcionalidade, o módulo 
implementado anteriormente pode ser trocado por uma nova 
implementação sem afetar os outros módulos. 
 
Prototipagem 
Localidade também provê uma base firme para a 
prototipação ou prototipagem. Um protótipo é uma 
implementação inicial, rudimentar e incompleta de 
um programa a ser desenvolvido. Se mantivermos o 
princípio da localidade no desenvolvimento do 
protótipo, essa implementação inicial pode ir sendo 
completada ou substituída por implementações 
melhores sem grande esforço nem re-trabalho. 
Técnicas de Programação Avançada
Página 27Centro Federal de Educação Tecnológica
 
 
Localidade também provê suporte para evolução. Abstrações 
podem ser utilizadas nesse caso para encapsular modificações 
potenciais no programa. Por exemplo, suponha que desejamos um 
programa para ser executado em diferentes máquinas. Podemos 
tratar esse problema inventando abstrações que escondam as 
diferenças entre as máquinas de forma que, para mover o 
programa para uma máquina diferente, apenas essas abstrações 
precisem ser reimplementadas. Um bom princípio de projeto é 
pensar sobre modificações esperadas e organizar o 
desenvolvimento utilizando abstrações que encapsulem as 
mudanças. 
 
 
Domínio da complexidade 
Os benefícios da localidade são particularmente 
importantes para a abstração de dados. Estruturas de 
dados são muitas vezes complicadas e a visão mais 
abstrata mais simples provida pela especificação torna o 
resto do programa mais simples. Ainda, mudanças nas 
estruturas de armazenamento são uma das principais 
formas de evolução de programas. Portanto, os efeitos 
dessas mudanças devem ser minimizados encapsulando 
essas estruturas de dados em abstrações de dados. 
 
Se avaliarmos um programa segundo o critério da abstração de 
dados, devemos observar os seguintes fatores: 
1. Os TADs estão realmente encapsulados? 
a. O entendimento de cada módulo do programa 
independe dos demais módulos? 
b. O efeito cascata é evitado na depuração? 
c. É possível reimplementar um módulo sem afetar os 
outros? 
2. Potenciais mudanças foram previstas no projeto do TAD? 
3. Os TADs oferecem abstrações suficientemente simples das 
estruturas de dados que encapsulam? 
 
 
Atividades 
 Os códigos a seguir especificam as interfaces de dois 
módulos: Aluno e Turma. 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 28
 
/******** aluno.h ***********/ 
typedef struct aluno{ 
 char nome[30]; 
 int matricula; 
 int cdgcurso; 
} Aluno; 
void leAluno(Aluno *); 
void imprimeAluno(Aluno); 
void AlteraAluno(Aluno *); 
 
/******** turma.h **********/ 
#include "aluno.h" 
#define MAXTURMA 100 
typedef struct turma { 
 int nalunos; 
 Aluno alunos[MAXTURMA]; 
}Turma; 
void insereAluno(Turma *,Aluno); /*insere o 
aluno passado como paramentro na turma */ 
void localizaAluno(Turma *, char *); /* 
localiza um aluno na turma pelo nome */ 
void imprimeTurma(Turma); 
void atualizaAlunoDaTurma(Turma *, char *); 
 
Agora, suponha que tenhamos o seguinte módulo principal, 
utilizando esses módulos: 
 
/************ Modulo Principal 
**************/ 
#include "turma.h" 
Turma turma1; 
 
void principal(){ 
int opcao,i; 
aluno a; 
char nome[30]; 
 
do{ 
 scanf("%d",&opcao); 
 switch(opcao){ 
 case 1: /* cadastrar aluno */ 
 lealuno(&a); 
 insereAluno(&turma1,a); 
 break; 
 case 2: 
 scanf("%s",nome); 
 a= localizaAluno(&turma1, nome); 
 printf("%s - %d - %d",a.nome, 
a.matricula,a.cdgcurso); 
 break; 
 case 3: /* imprimir turma */ 
 for (i=0;i<turma.nalunos;i++) 
 
imprimeAluno(turma.alunos[i]); 
 break; 
 case 4: 
Técnicas de Programação Avançada
Página 29Centro Federal de Educação Tecnológica
 
 
 scanf("%s",nome); 
 atualizaAlunoDaTurma(&turma1, 
nome); 
 break; 
 } 
} 
 
Tarefas: 
 a) Critique a implementação do módulo acima com 
base nos critérios de avaliação de TADs discutidos 
acima. 
 b) Faça uma implementação da operação 
atualizaAlunoDaTurma, respeitando os princípios de 
programação baseada em tipos abstratos de dados. 
 
 
 
 
Dijkstra (1930-2002) foi, sem dúvida, um dos 
cientistas que mais contribuíram para o 
desenvolvimento da Programação de Computadores. 
Terminamos este capítulo com uma frase dele, que 
resume o conceito de abstração: 
“O propósito da abstração não é ser vaga, mas sim, 
criar um novo nível semântico no qual ela possa ser 
absolutamente precisa”. 
Edsger. W. Dijkstra, The Humble Programmer (O 
programador Mediocre), Communications of the 
ACM, 15(10), 1972. 
 Reflita sobre isso! 
 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 30
 
 
2. TIPOS ABSTRATOS DE DADOS 
FUNDAMENTAIS 
 
 
Olá! Após o estudo e a compreensão dos con-
ceitos que definem a técnica de Abstração de 
Dados, utilizaremos esses conceitos em nosso estu-
do até o final da disciplina. Portanto, se você não 
compreendeu ou não se sente ainda plenamente 
convencido de que deve utilzar Abstração de 
Dados em seus programas, recomendo que retorne 
ao Capítulo 2. O motivo disso é muito simples. 
Daqui para frente estudaremos problemas e solu-
ções mais complexos, que exigem muito do estu-
dante em sua capacidade de abstração. Neste 
Capítulo, em particular, iniciamos nosso estudo de 
um conjunto de TADs muito comuns e 
importantes: Os TAD Pilha e Fila. 
 
No decorrer da evolução da programação, padrões e práticas comuns 
têm sido observadas e transformadas em conceitos, modelos e meca-
nismos que podem ser utilizados em mais de uma situação diferente. 
Dentre esses elementos temos uma coleção de tipos abstratos de dados 
que são comuns a diversas situações e aplicáveis na solução de uma 
grande quantidade de problemas. Dois desses TADs são as Pilhas e as 
Filas, que estudaremos em profundidade neste capítulo. 
2.1 PILHAS 
No mundo real uma pilha corresponde a um agregado de objetos que 
são acomodados um sobre o outro. A Figura 1 ilustra uma pilha em 
que os objetos são caixas. 
Técnicas de Programação Avançada
Página 31Centro Federal de Educação Tecnológica
 
 
 
Figura 1: Uma Pilha de Caixas 
 
Os números nas caixas indicam a ordem de empilhamento. Se 
quisermos agora remover as caixas da pilha (desempilhar), temos que 
remover a caixa 4 primeiro, depois a 3, a 2 e finalmente a 1. Não 
podemos remover as caixas abaixo da que está no topo da pilha sem 
antes remover a do topo. Esse comportamento pode ser definido pela 
estilo: O último a entrar é o primeiro a sair. 
No mundo real temos diversas situações em que esse comportamento 
deve ser respeitado. Assim, o uso de pilhas pode facilitar a solução 
de vários problemas. Um exemplo típico de uso de pilha é a 
operação desfazer, presente na maior parte dos editores de texto. 
Quando voce executa a operação desfazer, a última operação 
realizada é que deverá ser desfeita primeiro. Se você executar o 
desfazer novamente, a penúltima operação deverá ser desfeita, e assim 
sucessivamente. Concluindo, precisamos ter sempre a informação de 
qual foi a última operação realizada. Uma pilha é uma forma eficiente 
de obtermos esa informação. Se tivermos uma pilha em que 
empilhamos a operação que foi feita, teremos no topo da pilha semprea operação que devemos desfazer. 
Realmente, editores texto que possuem a operação desfazer mantém 
uma pilha que guarda informações sobre as ações que vão sendo 
realizadas durante a edição. Por exemplo, no momento em que este 
texto era digitado, as informações passadas via teclado e mouse eram 
também empilhadas. 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 32
 
 
A aplicação de pilhas em editores de texto é um 
exemplo de uma funcionalidade muito comum de uso de 
pilha. Essa funcionalidade está presente em outros 
cenários, como em jogos, programas de logistica, 
robótica e redes de computadores. O que esses cenários 
têm em comum é a necessidade de retroceder por um 
caminho de dados ou ações que tenha realizado. Esse 
retocesso se dá também em algoritmos de backtracking, 
(algo como voltar na trilha) e é muito comum em 
algoritmos de busca e recuperação de informação. Veja 
a discussão sobre esses algoritmos em 
http://pt.wikipedia.org/wiki/Backtracking. 
 
 
2.1.1 Especificação do TAD Pilha 
O TAD Pilha pode ser descrito pela seguinte especificação 
apresentada na Figura 2. Nessa especificação são definidas as 
operações Empilha, que insere elementos na Pilha e Desempilha, que 
remove elementos da Pilha. São definidas também as pré-condições e 
pós-condições dessas operações. 
Figura 2: especificação do TAD Pilha. 
Além das operações empilha e desempilha, temos também a operação 
inicializaPilha, que coloca a Pilha em um estado inicial, com a pilha 
vazia. A Figura 3 ilustra uma possível implementação do TAD Pilha 
limitado a 5 (cinco) posições. Cada posição possui um índice. O topo 
mantém o índice do valor que está presente no topo. Nesse exemplo, 
Técnicas de Programação Avançada
Página 33Centro Federal de Educação Tecnológica
 
 
temos o elemento do topo na posição de índice 5, conforme indica a 
figura. Se convencionarmos que os elementos foram inseridos na pilha 
na ordem L I C A F, temos que: 
O primeiro elemento empilhado foi o L, seguido do I, C, A e F. Logo, 
podemos concluir que nessa implementação de pilha a atualização do 
topo consiste em incrementar de 1 na operação empilha e decrementar 
de 1 na operação desempilha. As pré-condições também podem ser 
obtidas da implementação. A operação Pilha Vazia pode ser verificada 
por meio do teste do valor do topo. Por exemplo, se iniciarmos a pilha 
com topo valendo 0, podemos usar o teste topo == 0 para verificar se 
pilha está vazia. Já a pré-condição pilha cheia pode ser verificada 
considerando o limite da implementação. No nosso exemplo esse 
limite é 5. Se o topo == 5, a pilha está cheia. Com isso, fica definida 
também a operação inicializaPilha que deve fazer o topo valer 0 
(zero). 
 
 
 
 
 
 
 
Figura 3: Implementação de uma Pilha. 
 
 
É importante neste momento notar que existem muitas 
implementações possíveis para a especificação do TAD 
pilha (conforme discutido no Capitulo 1). Esse exemplo 
apresentado é apenas uma das possíveis soluções. 
Um outro detalhe é que, além das operações empilhar e 
desempilhar, as pré-condições de pilha Cheia e pilha 
Vazia podem também se tornar operações do TAD Pilha 
na implementação. Na próxima seção discutiremos 
algumas implementações de Pilha usando arranjos 
estáticos. 
 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 34
 
 
Atividades 
 1. Na seqüência a seguir, uma letra significa 
empilha e um asterisco significa desempilha. 
Determine a seqüência de valores retornados 
pela operação desempilha quando essa 
seqüência de operações é realizada sob uma 
pilha inicialmente vazia. 
E A S * Y * Q U E * * * S T * * * I O * N * * * 
 
2. Suponha que uma seqüência misturada de 
operações empilha e desempilha é realizada. 
As operações empilha empilham inteiros de 0 
até 9 ordenadamente. A operação desempilha 
desempilha e imprime o valor desempilhado. 
Qual das seqüências abaixo não poderá ser 
impressa? 
 (a) 4 3 2 1 0 9 8 7 6 5 
 (b) 4 6 8 7 5 3 2 9 0 1 
 (c) 2 5 6 7 4 8 9 3 1 0 
 (d) 4 3 2 1 0 5 6 7 8 9 
 
2.1.2 Implementação de Pilhas em Arranjos 
A Figura 3 ilustra por meio de um diagrama uma implementação de 
Pilha. Usando arranjos estáticos (vetores) e fazendo algumas 
adaptações, podemos criar essa implementação em C. A 
implementação, conforme discutido na Seção 1.2.4, será formada de 
duas partes, a interface (arquivo com extensão .h) e a 
implementação das operações (arquivo com extensão .c). É 
recomendado primeiro a definição do arquivo de interface e depois a 
implementação das operações. A seguir discutiremos uma possível 
implementação do TAD Pilha, utilizando arranjos. 
A Figura 4 mostra o arquivo de interface tadpilha.h. Foi definido 
um novo tipo chamado Pilha, formado por dois elementos 
principais: Uma variável inteira topo e o vetor itens, que servirá 
de contêiner para a pilha. O vetor itens é do tipo Elemento, que é 
apenas uma redefinição do tipo char. A definição desse tipo 
Elemento facilita posteriores modificações no tipo básico da pilha. Se 
quisermos, por exemplo, alterar a pilha para que esta empilhe e 
desempilhe valores inteiros, basta redefinir o tipo Elemento como 
Técnicas de Programação Avançada
Página 35Centro Federal de Educação Tecnológica
 
 
int. Foram definidas assinaturas (protótipos) das funções 
correspondentes às operações inicializaPilha, empilha, 
desempilha e aos testes das pré-condições, pilhaCheia e 
pilhaVazia. Observe que estamos seguindo a notação de 
protótipos padrão de C. Nessa notação, apenas os tipos dos 
argumentos (parâmetros das funções) são identificados, sendo os 
nomes mesmos desses argumentos apenas na implementação. Note 
também que a operação desempilha retorna um Elemento. Isso é 
bastante comum, pois normalmente se deseja fazer alguma coisa com 
o elemento desempilhado. 
Figura 4: Interface do TAD Pilha com arranjos estáticos. 
Na Figura 5, temos a implementação das operações feitas no arquivo 
tadPilha.c. A operação inicializaPilha faz o topo da Pilha 
receber 0 (zero). PilhaCheia verifica se topo igual a MAX 
(tamanho máximo que a pilha pode ter) e PilhaVazia verfica se 
topo igual a 0. Na operação empilha temos a seguinte ordem: insere 
o elemento e depois incrementa o topo. Isso é necessário porque em C 
a primeira posição de um arranjo é a 0 (zero) e com a Pilha vazia o 
topo está em zero. Assim, o topo estará sempre com um índice do 
elemento no topo + 1. Para compensarmos isso, na operação 
desempilha devemos decrementar o topo retornando o elemento 
somente após o topo ser decrementado. 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 36
 
Figura 5: Implementação das operações do TAD Pilha. 
 
Atividades 
 1. Empilhamento decrescente. Uma empilhadeira
carrega caixas de 7, 5 e 3 toneladas. Há três pilhas
A, B e C. A pilha A é onde se encontram todas as
caixas que chegam no depósito. Com um detalhe: 
caixas maiores não podem ser empilhadas sobre
caixas menores. Elabore uma função
chegaNoDeposito (Caixa* nova, 
Pilha* A) que efetue o controle das caixas, de 
forma que, caso uma caixa de maior peso do que
uma que já está em A deva ser empilhada, então, 
todas as caixas que estão em A são movidas para as
pilhas auxiliares B (contendo somente caixas de 5
Técnicas de Programação Avançada
Página 37Centro Federal de Educação Tecnológica
 
 
toneladas) e C (contendo somente caixas de 3
toneladas) até que se possa empilhar a nova caixa.
Depois, todas as caixas são movidas de volta para a 
pilha A. 
2. Implementar o TAD PilhaDupla, usando um 
arranjo de 100 posições. PilhaDupla deve usar 
um único arranjo para implementar as duas pilhas.
Além disso, a ocupação da Pilha deve maximizar o
uso do espaço do arranjo, ou seja, enquanto houver
espaço no arranjo qualquer uma das duas pilhas
pode utilizá-lo. 
 
2.2 FILAS 
Em nosso cotidiano nos deparamos constantemente com filas. Ou 
melhor, estamos constantemente entrandoe saindo de filas! Muitas 
pessoas se aborrecem com as filas. Todavia, podemos dizer que elas 
são um mal necessário. Por exemplo, imaginem se, para entrarem em 
um ônibus em uma cidade, as pessoas não fizessem uma fila e 
simplesmente se amontoassem na porta. Seria um tumulto, as pessoas 
que estivessem no ponto há mais tempo poderiam não conseguir entrar 
ou ficar sem assento. O mais incrível é que isso acontecia há uns 20 
anos e ainda acontece em muitos lugares do Brasil e do mundo! 
 
Figura 6: Fila: O primeiro que chega é o primeiro a ser atendido. 
Esse exemplo ilustra a idéia de que o emprego de filas no dia-a-dia é 
fundamental para a organização das atividades feitas pelas pessoas, 
sempre que o número de clientes de um recurso é maior que a 
capacidade de atendimento desse recurso. No caso do ônibus, o 
recurso é a porta de entrada, que só atende uma pessoa por vez. Com 
mais de uma pessoa no ponto esperando para entrar, é necessário que 
elas formem uma fila. Um outro exemplo é fila em um banco, cujo 
recurso necessário é o caixa. Quando entram mais clientes do que o 
número de caixas, os clientes devem formar uma fila. 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 38
 
O comportamento de uma fila pode ser descrito pelo estilo: O 
primeiro que chega é o primeiro a ser atendido. Em uma Fila 
organizada e sem prioridades (Figura 6, por exemplo), essa regra é 
sempre obedecida. 
Na programação aplicamos o conceito de fila para tratar casos 
semelhantes ao do ônibus e ao do banco. Alguns exemplos de 
aplicação de filas são: 
 Fila de espera de passagens aéreas – Suponha, por exemplo, 
que você esteja desenvolvendo um sistema de reservas de 
passagens aéreas. Nesse tipo de sistema, as pessoas fazem 
reservas até o recurso (número de assentos no vôo) se esgotar. 
Quando isso acontece, se houver mais pessoas que querem 
viajar naquele vôo, elas entram em uma fila de espera. Se 
houver uma desistência das reservas, a primeira pessoa dessa 
fila será atendida. 
 Fila de mensagens – Suponha que você esteja desenvolvendo 
um programa A que envie constantemente mensagens a um 
programa B. O programa B precisa receber essas mensagens e 
processá-las. Se o número de mensagens que o programa A 
envia em um tempo x é maior do que a capacidade de 
processamento das mensagens no mesmo tempo x pelo 
programa B, o programa B deverá usar uma fila para guardar 
as mensagens até que elas possam ser processadas. Esse é um 
caso muito comum na Internet. Quando fazemos a requisição 
de uma página Web, o navegador (programa A) envia uma 
mensagem ao servidor Web (programa B). Esse servidor pode 
receber mais requisições (mensagens) do que a sua capacidade 
de processamento. Nesse caso, ele deve enfileirar as 
requisições para que elas não sejam perdidas e para que sejam 
atendidas na ordem de chegada. 
 
Teoria das Filas 
O estudo das Filas, do ponto de vista estatístico e 
probabilístico, denomina-se Teoria das Filas e 
compreende uma disciplina de grande interesse de 
diversas áreas da engenharia, computação e 
administração. Essa disciplina permite, dentre outras 
coisas, estimar a capacidade de recursos a serem 
construídos (p.exemplo, aeroportos, pontes, 
armazéns de estocagem), identificar gargalos 
(pontos de atraso) em sistemas e estimar o tempo 
para a realização de uma tarefa. Em nosso estudo, 
nos concentraremos apenas na implementação e 
emprego de filas em programação, e não na 
Teoria das Filas. 
Técnicas de Programação Avançada
Página 39Centro Federal de Educação Tecnológica
 
 
2.2.1 Especificação do TAD FILA 
 
O tipo abstrato de dados fila pode ser descrito pela especificação da 
Figura 7. 
Figura 7: Especificação do TAD Fila. 
As operações fundamentais do TAD Fila são inserir e remover. 
Para garantir o comportamento esperado em uma fila, definimos que a 
inserção é feita no final da fila e a remoção é feita no começo da fila. 
Temos também a operação inicializaFila, que coloca a fila em um 
estado inicial, no qual a fila deve estar vazia. A partir dessas 
operações e de suas pré e pós-condições podemos deduzir que serão 
necessárias as operações de teste de fila cheia e teste de fila vazia. 
Assim como na implementação da pilha precisamos de alguma forma 
de identificar o topo, na fila iremos necessitar de alguma maneira de 
identificar o seu inicio e seu o fim. 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 40
 
Figura 8: Inserções e remoções em um TAD Fila. 
O diagrama da Figura 8 ilustra uma fila com capacidade para cinco 
elementos implementada em uma estrutura semelhante a um vetor. O 
digrama também ilustra a inserção de cinco elementos (M1..M5) e 
duas operações de remoção. Note que os valores de início e fim são 
usados para armazenar as posições atuais do início e do fim da fila. 
Inicialmente o valor de início está em zero. Podemos usar essa 
condição para detectarmos se a fila está vazia. Quando o elemento M1 
é inserido, este é colocado na posição 1 e o início e o fim são 
atualizados, ambos para 1. À medida que outros elementos são 
inseridos, o fim é atualizado. Quando o fim chega a 5, temos que a fila 
não comporta mais nenhuma inserção, isto é , a fila está cheia. Assim, 
podemos usar essa condição para detectarmos se a fila está cheia ou 
vazia. 
Técnicas de Programação Avançada
Página 41Centro Federal de Educação Tecnológica
 
 
À medida que as remoções ocorrem, o inicio da fila é atualizado, de 
forma a identificar sempre o elemento a ser removido. Um problema 
dessa implementação é que uma vez que fim atingiu o valor máximo 
(5 neste caso), não são possíveis mais inserções, mesmo havendo 
outros espaços. Isso é ruim, pois torna a fila muito limitada. Para 
contornarmos esse problema veremos duas implementações 
diferentes: Remoção com deslocamento e Fila circular. Na remoção 
com deslocamento, à medida que os elementos são removidos, os 
elementos remanescentes são deslocados para o início do arranjo. 
 
Figura 9: Implementação com Deslocamento. 
A Figura 9 mostra a implementação com deslocamento. Note que, 
nessa implementação, após a remoção de todos os elementos, o valor 
de início permaneceu com 1 e o valor de fim passou a ser zero. Assim, 
a condição de fila vazia não pode ser verificada pelo teste de início = 
0. Um possível teste é fim = 0 ou fim menor que início. A seguir 
vamos ver uma implementação em C usando arranjos para essa fila. 
Posteriormente veremos a implementação utilizando fila circular. 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 42
 
 
Atividades 
 Ordenar uma fila utilizando 2 pilhas como variáveis
auxiliares. Ao final da ordenação o elemento no início da
fila deve ser menor que o segundo da fila e assim 
sucessivamente. A ordenação deve ser feita apenas em
termos das operações insere, remove, filaVazia, 
empilha, desempilha e pilhaVazia. A função 
deve ter a seguinte organização: 
void ordena_2p (Fila* f){ 
 Pilha p1, p2; 
 ... 
} 
2.2.2 Implementação de Filas em arranjos com 
deslocamento 
De forma similar à da implementação de Pilha iremos definir um 
módulo em C para implementação da Fila. Na Figura 10 temos a 
definição da interface (arquivo filaecd.h) do TAD Fila. 
Figura 10: Interface do TAD Fila. 
A Figura 11 apresenta o arquivo filaecd.c, contendo a implementação 
das operações da Fila com deslocamento na remoção. 
Técnicas de Programação Avançada
Página 43Centro Federal de Educação Tecnológica
 
 
Figura 11: Implementação do TAD Fila Com deslocamento. 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 44
 
O código está comentado e pretende ser auto-explicativo. A operação 
insereNaFila insere os elementos passados como parâmetro 
(elem). Para inserir na fila, inicialmente o valor de fim é 
incrementado, visto que este foi inicializado com valor –1. Dessa 
forma a primeira inserção insere na posição 0 do vetor, a segunda na 
posição 1 eassim sucessivamente. A operação mais complexa é a 
remoção. Para remover, inicialmente o elemento no início da fila é 
passado por referência por meio do parâmetro (elem *). 
Posteriomente os elementos remanescentes na Fila são deslocados de 
uma posição. Dessa forma o elemento do início da fila ocupa 
novamente a posição 0 do vetor. 
O código da Figura 12 (arquivo principal.c) permite testar a Fila. 
Figura 12: Módulo para teste do TAD Fila. 
A função testeFilaecd declara uma fila (q) inicializa a fila, insere os 
inteiros de 0 a 9 e depois remove os elementos e os imprime. Note que 
todo o processamento é feito usando as operações do Tad Fila. 
 
 
Atividades 
 4. Implementar as operações imprimir Fila para o TAD Fila
implementado anteriormente. 
Técnicas de Programação Avançada
Página 45Centro Federal de Educação Tecnológica
 
 
2.2.3 Implementação de Filas com Arranjos circulares 
 
 
Analisando a implementação do TAD Fila da seção 
anterior podemos notar que, embora a fila esteja 
corretamente implementada, existe um problema de 
eficiência na remoção de um elemento. Estou me 
referindo aos deslocamentos necessários para que a 
remoção seja feita e os espaços vagos no vetor 
possam ser reaproveitados. Veremos agora outra 
maneira de implementar o TAD Fila, em que esses 
deslocamentos não são necessários. Essa 
implementação chama-se Fila Circular. 
Função Sucessor 
Em um arranjo simples, cujas posições vão de 0 a t, podemos 
identificar facilmente qual o elemento que sucede uma determinada 
posição i. Por exemplo, se i =0, o sucessor de i = 1, se i=1 sucessor de 
i = 2. Ou seja, o sucessor de i = i+1, para i variando entre 0 e t-1. 
Nesse caso, não existe o sucessor de t. 
Agora, se definimos que o sucessor de t = 0, temos então que todos os 
índices do arranjo possuem sucessor. A Figura 13 ilustra essa situação. 
Conforme pode ser observado, existe uma circularidade entre os 
índices. 
Figura 13: Fila Circular. 
Com vetores variando entre 0 a N-1, que é o caso da linguagem C, a 
função sucessor pode ser obtida elegantemente por meio da função: 
 sucessor(i) = (i+1) mod n, onde mod é o operador 
resto. 
Quando utilizamos essa função para avançarmos o índice de um 
arranjo para a próxima, dizemos que estamos usando um arranjo 
circular. 
TAD FILA baseado em Arranjo Circular 
Com um arranjo circular, é possível deslocar o início e o fim da fila 
por todo o vetor, sem correr o risco da perda de espaço e sem a 
necessidade de realocar os elementos da fila. Nessa implementação as 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 46
 
operações de inserir e remover, bem como as condições de Fila Cheia 
e Fila vazia precisam ser baseadas na função sucessor. A Figura 14 
apresenta a lógica dessas operações, agora definida em termos da 
função sucessor. 
 
Figura 14: Especificação das operações de um TAD Fila Circular. 
A Figura 15 apresenta a implementação das operações. Note que não é 
necessário um novo arquivo header, pois este é o mesmo da 
implementação do módulo filaecd. Esse fato ilustra um aspecto 
importante da implementação de TADs: A implementação pode ser 
modificada sem necessidade de se alterar a interface. Outro aspecto da 
implementação com arranjo circular, é que uma das posições do 
arranjo é perdida. Isso é necessário para diferenciar as condições de 
Fila Vazia e Fila Cheia. 
 
Atividades 
1. Reimplemente a Fila Circular, considerando que o elemento a ser
inserido é um paciente de hospital (pessoa). Os seguintes dados são
importantes para o paciente: nome, idade, horário de chegada e
enfermidade. 
2. Implemente também a operação imprimeFila para essa nova Fila. 
 
Técnicas de Programação Avançada
Página 47Centro Federal de Educação Tecnológica
 
 
Figura 15: Implementação das operações de Fila em um arranjo Circular. 
 
2.3 IMPLEMENTAÇÃO DE TADS COM ALOCAÇÃO 
DINÂMICA DE MEMÓRIA 
2.3.1 Revisão de Alocação Dinâmica de Memória 
O objetivo da alocação dinâmica de memória é utilizar espaços da 
memória de tamanho arbitrário. Em adição, a alocação dinâmica de 
memória permite criar estruturas de dados encadeadas. A alocação de 
espaço sob demanda é utilizada quando o espaço de memória 
necessário para um conjunto de dados varia durante a execução do 
programa. Já o encadeamento provê um estilo eficiente de representar 
conjuntos de dados em C e de implementar as estruturas de 
armazenamento de Tipos Abstratos de Dados. 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 48
 
A alocação dinâmica de memória necessita de suporte da Linguagem 
de Programação. Em C, esse suporte é fornecido por um conjunto de 
funções disponíveis na biblioteca alloc. As principais funções dessa 
biblioteca são a função malloc, que aloca um espaço na memória e 
retorna um ponteiro para o espaço alocado e a função free, que 
libera espaços de memória alocados por meio da função malloc. 
Exemplo de uso de alocação de espaço sob demanda 
Uma das vantagens da alocação dinâmica é permitir a alocação de 
espaço de acordo com a necessidade. Por exemplo, suponha que um 
programa necessite de um arranjo para guardar N números inteiros. 
Usando alocação estática de memória, como não sabemos a 
quantidade precisa de números, devemos fazer uma estimativa do 
valor máximo de número e declarar o vetor com base nessa estimativa. 
A função alocEstatica da Figura 16 ilustra esta situação. 
Figura 16: Alocação Estática de memória. 
Note que o valor lido para n pode variar de 1 a 100. Quanto menor o 
valor de n, maior o desperdício de espaço alocado. 
Usando alocação dinâmica teremos o valor de n que, lido, pode ser 
usado como parâmetro da chamada da função malloc, para alocar um 
conjunto de n inteiros, ou seja, um vetor de n inteiros. A função 
alocDinamica na Figura 17 é idêntica em termos de 
funcionalidade à função alocEstatica. Contudo, esta utiliza 
alocação dinâmica. 
Técnicas de Programação Avançada
Página 49Centro Federal de Educação Tecnológica
 
 
Figura 17: Vetor com Alocação dinâmica. 
Note que na alocação dinâmica não há limites para n, e este poderá 
assumir, em teoria, qualquer valor maior que zero (n>0). A função 
malloc possui apenas um parâmetro formal: o número de bytes a 
serem alocados. Normalmente esse número de bytes é determinado 
multiplicando o tamanho em bytes do tipo base a ser alocado pelo 
número de elementos. No exemplo, o tipo base é o int. Foi usada a 
macro sizeof para determinar o tamanho exato do tipo int, que 
pode variar entre diferentes máquinas, sistemas operacionais e 
linguagens. Qualquer tipo pode ser utilizado como parâmetro de 
sizeof, inclusive tipos definidos pelo usuário. 
Listas Simplesmente Encadeadas 
Uma outra finalidade do uso de alocação dinâmica e apontadores é 
permitir a implementação de estruturas encadeadas utilizando 
estruturas auto referenciadas.Uma estrutura auto referenciada 
possui, dentro seus campos, um campo que pode referenciar estruturas 
idênticas a ela mesma. Portanto, uma estrutura auto referenciada pode 
apontar para outra estrutura do mesmo tipo que ela. 
O código na Figura 18 define um tipo Ponto que é auto referenciável. 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 50
 
 
 
Figura 18: Estrutura auto referenciada. 
O tipo Ponto definido pelo typedef é um tipo ponteiro para a 
struct ponto. Essa struct por sua vez, possui dentro dela os 
campos x,y (coordenadas do ponto), cor (cor do ponto) e 
proximoPonto, que é uma variável do tipo ponteiro para struct 
ponto. A variável proximoPonto é que permite que uma variável 
do tipo struct ponto possa se ligar (apontar) a outra estrutura do 
tipo struct ponto. 
 
Figura 19: A struct ponto. 
 
Lista simplesmente Encadeada 
A estrutura de dados encadeada mais simples que temos 
é a lista simplesmente encadeada. Uma lista 
simplesmente encadeada é um agregado de elementos 
de um mesmo tipo, em que cada elemento é armazenado 
em um espaçoalocado dinamicamente. À medida que 
elementos são inseridos na lista, esses espaços são 
criados e vão sendo encadeados de forma que: 
- O endereço do primeiro ou do último elemento da lista 
é mantido em uma variável do tipo ponteiro; 
- Os demais elementos são acessados a partir do seu 
início ou do seu fim. Isto é possível porque cada nodo 
da lista possui um campo que aponta para o próximo 
elemento da lista. 
 
 
A struct ponto pode servir para implementarmos uma lista. 
Visualmente, uma lista encadeada de pontos pode ser ilustrada pela 
Figura 20 a seguir: 
Técnicas de Programação Avançada
Página 51Centro Federal de Educação Tecnológica
 
 
 
Figura 20: Exemplo de lista simplesmente encadeada. 
 
lPontos é uma variável do tipo ponteiro para struct ponto 
(Ponto com P maiúsculo). Inicialmente a lista está vazia. Assim é 
conveniente fazermos a variável lPontos apontar para um valor 
“Seguro”, evitando possíveis invasões de espaço de memória 
indevidos. Este valor seguro é NULL. 
Para inserirmos um nodo na lista de pontos, criamos o nodo, 
utilizando malloc e guardamos o endereço deste nodo em 
lPontos; 
Para manter o encadeamento, devemos fazer o proximoPonto do 
nodo alocado apontar para o endereço anteriormente contido em 
lPontos. O excerto de código apresentado na Figura 21 implementa 
esta operação de inserção. 
Figura 21: Inserindo um ponto na lista de pontos. 
Note que foi necessário guardar o valor de lPontos em aux, Isso 
ocorre porque, quando malloc é chamada para criar o novo Ponto, o 
endereço retornado é atribuído a lPontos fazendo com que o seu 
endereço anterior seja perdido. 
É conveniente implementar uma lista simplesmente encadeada como 
um TAD, encapsulando sua estrutura por meio de operações bem 
definidas. Essas operações compreendem a inserção, a remoção 
e outras que por ventura sejam necessárias (por exemplo, 
imprimeLista). A seguir, iremos implementar uma lista encadeada 
cujo objetivo é armazenar uma lista de pessoas. Cada pessoa é 
definida pelo seu nome, seu código e seu telefone. Na implementação 
definimos um módulo elemento e o módulo Tadlista. As Figuras 22 e 
23 apresentam a definição da interface desses dois módulos: 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 52
 
Figura 22: Interface do TAD Elemento. 
Figura 23: Interface do TAD Lista. 
A implementação da operação inicializaLista (Figura 24) 
consiste em atribuir o valor NULL a Lista passada por referência. 
Segue essa implementação: 
Figura 24: Implementação da operação inicializaLista. 
A implementação da inserção (Figura 25) segue exatamente o mesmo 
procedimento usado no exemplo da lista de pontos. 
Figura 25: Implementação da operação insereNaLista. 
A operação de remoção visa remover um elemento da lista tendo sido 
informado o código do elemento. Esse procedimento deve também 
retornar o elemento a ser removido. A remoção deve usar a função 
free para liberar o espaço alocado pelo nodo removido. Além disso, 
deve ser também preservado o encadeamento da lista. De acordo com 
esses objetivos temos que realizar uma pesquisa na lista com o 
objetivo de encontrar o nodo a ser eliminado. Como resultado dessa 
pesquisa existem duas possibilidades: 
Técnicas de Programação Avançada
Página 53Centro Federal de Educação Tecnológica
 
 
* O elemento está na lista. A pesquisa pára quando encontrar o 
elemento. 
* O elemento não está na lista. A pesquisa chega até o fim da lista 
(NULL). 
Formulamos então o algoritmo recursivo apresentado na Figura 26. 
Figura 26: algoritmo para remoção de um elemento na Lista. 
A Figura 27 apresenta uma implementação para a operação de 
remoção baseada no algoritmo da Figura 26. 
Figura 27: Implementação da operação removeDaLista. 
A operação pesquisaNaLista visa retornar um elemento cujo 
código é passado como parâmetro. Essa pesquisa é feita por meio de 
um loop, que percorre a lista até encontrar o elemento ou chagar ao 
seu final. Temos novamente duas situações: busca com sucesso ou 
busca sem sucesso. Na Figura 28, temos a implementação desta 
operação. 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 54
 
Figura 28: Implementação da operação pesquisaNaLista. 
A Figura 30 apresenta a implementação da operação 
imprimeLista, que utiliza a operação imprimeElemento do 
TAD elemento (Figura 29). A operação imprimeLista deve 
percorrer a lista até o final imprimindo o conteúdo de seus elementos. 
Seguem as implementações das operações imprimeElemento 
arquivo elemento.c) e imprimeLista (arquivo tadLista.c). A 
operação imprimeLista é recursiva. A cada chamada da 
recursividade, é passado um apontador para o próximo elemento da 
lista. A condição de parada da recusividade é chegar ao final da Lista 
(NULL). 
Figura 29: Implementação da operação imprimeElemento do TAD Elemento. 
 
 
Figura 30: Implementação da operação imprimeLista. 
 
Técnicas de Programação Avançada
Página 55Centro Federal de Educação Tecnológica
 
 
 
Atividades 
 1. Implementar uma operação para o TAD Lista 
que insira os elementos no seu final. 
2. Implementar uma operação para o tadLista 
que transforme a lista em uma lista ordenada. 
Essa operação deve inserir os elementos de 
modo que a lista permaneça sempre em ordem 
crescente a partir de seu inicio. A chave de 
ordenação a ser utilizada deve ser o código do 
elemento. 
 
2.3.2 Implementação do TAD Pilha 
A implementação do TAD Pilha com alocação dinâmica de memória 
possui como vantagem principal o fato de podermos considerar a sua 
capacidade de armazenamento como sendo infinita. Ou seja, usando 
alocação dinâmica não precisamos testar se a Pilha está cheia para 
fazer um empilhamento. Outra vantagem está na simplicidade da 
implementação. O quadro abaixo ilustra a definição do tipo Pilha 
como uma estrutura dinâmica encadeada. Podemos afirmar que uma 
pilha é uma lista onde os elementos são inseridos no início e 
removidos do início. Para efeitos de implementação da pilha, 
chamamos o início de topo. 
A Figura 31 apresenta o arquivo de interface TadPilhaAD.h com a 
definição da estrutura de dados Pilha e das operações. Note 
novamente que as operações são as mesmas apresentadas no módulo 
Pilha.h visto anteriormente. 
Técnicas de Programação Avançada
Centro Federal de Educação TecnológicaPágina 56
 
Figura 31: Interface do TAD Pilha com alocação dinâmica 
Para a definição da Pilha dinâmica, é definido o tipo Nodo que é um 
tipo ponteiro para struct nodo (em minúsculo). Pilha é uma estrutura 
que contém apenas uma variável: o topo. Esse topo, por sua vez, é do 
tipo Nodo. 
Uma variável do tipo Pilha é uma variável estática. Essa variável é 
uma estrutura contendo como único campo o topo. O topo, por sua 
vez, é que é um apontador. 
Pilha p; 
p.topo=NULL; 
 
 
 
 
 
Figura 32: Representação do da estrutura de dados dinâmica Pilha. 
Topo é uma variável do tipo ponteiro para struct nodo. Assim 
topo pôde ser inicializado com NULL. Essa condição pode ser 
utilizada para detectarmos se a Pilha está vazia. A Figura 33 apresenta 
as operações inicializaPilha e pilhaVazia seguindo exatamente essas 
decisões de implementação. 
p
NULL 
topo 
 
Técnicas de Programação Avançada
Página 57Centro Federal de Educação Tecnológica
 
 
Figura 33: Implementação das operações inicializaPilha e pilhaVazia. 
 
A operação empilha pode ser especificada da seguinte forma: 
1. Cria uma nova estrutura do tipo struct nodo; 
2. Faz o prox da nova estrutura apontar para a estrutura para a 
qual o topo da Pilha aponta; 
3. Faz o topo da pilha apontar para o novo nodo. 
Seguindo os passos acima, após inserirmos o primeiro elemento na 
pilha (valor 1), e supondo que o nodo foi alocado a partir do 
endereço 300h da memória, teremos a configuração apresentada na 
Figura 34. 
 
 
 
 
 
 
 
Figura 34: Diagrama da Pilha com um nodo (um elemento empilhado). 
Se empilharmos agora um segundo elemento (valor