arte evisão da inguagem Culysseso.com/livros/ed1/TOC.pdf · Tabela de Conteúdo | xi goto 65 Uso de break e continue em Laços Aninhados 66 1 16 Outros Operadores 66 1.16.1 Operador

ix

Visão Geral da Obra �� v

Conteúdo Resumido ��vii

Conteúdo Completo �� ix

Lista de Figuras �� xxv

Lista de Tabelas �� xxxi

Lista de Algoritmos ��xxxiii

Lista de Lemas, Teoremas e Corolários �� xxxv

Prefácio ��xxxviiObjetivos e Público-alvo xxxviiOrganização do Livro xxxvii

Volume 1 xxxviiVolume 2 xxxixExemplos de Programação xlExercícios xlOrganizadores Prévios xli

Material Complementar xliRecursos Utilizados xliAgradecimentos xli

Parte 1: revisão da Linguagem C

x | Tabela de Conteúdo

1 Elementos Básicos da Linguagem C �� 451�1 A Linguagem C Padrão 1.1 461�2 Identificadores, Tipos Primitivos e Constantes 1.2 46

1.2.1 Identificadores 461.2.2 Tipos de Dados Primitivos 461.2.3 Constantes 47

1�3 Operadores Básicos 1.3 481.3.1 Propriedades de Operadores 481.3.2 Expressões 491.3.3 Operadores Aritméticos 491.3.4 Operadores Relacionais 491.3.5 Operadores Lógicos 49

1�4 Definições de Variáveis 1.4 501�5 Operadores de Atribuição 1.5 501�6 Conversões de Tipos 1.6 51

1.6.1 Conversões Implícitas 511.6.2 Conversão Explícita 52

1�7 Incremento e Decremento 1.7 521�8 Comentários 1.8 531�9 A Biblioteca Padrão de C 1.9 531�10 Escrita de Dados na Tela 1.10 541�11 Leitura de Dados via Teclado 1: Frágil 1.11 55

1.11.1 Função getchar() 551.11.2 Função scanf() 56

1�12 Constantes Simbólicas 1.12 571�13 Enumerações 1.13 571�14 Instruções 1.14 58

1.14.1 Tipos de Instruções 581.14.2 Sequências de Instruções 581.14.3 Instruções Vazias 58

1�15 Estruturas de Controle 1.15 591.15.1 Laços de Repetição 59

while 59do-while 60for 60Laços de Repetição Aninhados 62Laços de Repetição Infinitos 62

1.15.2 Desvios Condicionais 62if-else 62switch-case 63

1.15.3 Desvios Incondicionais 65break 65continue 65

Tabela de Conteúdo | xi

goto 65Uso de break e continue em Laços Aninhados 66

1�16 Outros Operadores 1.16 661.16.1 Operador Condicional 661.16.2 Operador Vírgula 671.16.3 O Operador sizeof e o Tipo size_t 67

1�17 Programas Monoarquivo 1.17 681.17.1 Estrutura de um Programa Simples em C 681.17.2 Como Criar um Programa-fonte 681.17.3 Criando um Programa Executável 68

1�18 Endereços e Ponteiros 1.18 691.18.1 Endereços 691.18.2 Ponteiros 691.18.3 Indireção de Ponteiros 701.18.4 Ponteiro Nulo 71

1�19 Exercícios de Revisão 1.19 71A Linguagem C Padrão (Seção 1.1) 71Identificadores, Tipos Primitivos e Constantes (Seção 1.2) 71Operadores Básicos (Seção 1.3) 72Definições de Variáveis (Seção 1.4) 72Operadores de Atribuição (Seção 1.5) 72Conversões de Tipos (Seção 1.6) 73Incremento e Decremento (Seção 1.7) 73Comentários (Seção 1.8) 73A Biblioteca Padrão de C (Seção 1.9) 73Escrita de Dados na Tela (Seção 1.10) 74Leitura de Dados via Teclado 1: Frágil (Seção 1.11) 74Constantes Simbólicas (Seção 1.12) 75Enumerações (Seção 1.13) 75Instruções (Seção 1.14) 75Estruturas de Controle (Seção 1.15) 75Outros Operadores (Seção 1.16) 77Programas Monoarquivo (Seção 1.17) 78Endereços e Ponteiros (Seção 1.18) 78

1�20 Exercícios de Programação 1.20 78

2 Funções e Programas Multiarquivo �� 812�1 Funções 2.1 82

2.1.1 Definições de Funções 822.1.2 Cabeçalho 822.1.3 Corpo de Função 832.1.4 Retorno de Função 832.1.5 Chamadas de Funções 842.1.6 Modos de Parâmetros 84

xii | Tabela de Conteúdo

2.1.7 Passagem de Parâmetros 852.1.8 Simulando Passagem por Referência em C 852.1.9 Alusões e Protótipos de Funções 87

2�2 Leitura de Dados via Teclado 2: Robusta 2.2 872.2.1 Entendendo Leitura de Dados via Teclado 872.2.2 Esvaziamento do Buffer de Entrada 882.2.3 Uso de Laços de Repetição em Leitura de Dados 89

2�3 Duração de Variáveis 2.3 902�4 Escopo 2.4 912�5 Diretivas de Pré-processamento 2.5 91

2.5.1 Macros 922.5.2 Compilação Condicional 942.5.3 Inclusão de Arquivos 95

2�6 Programas Multiarquivo 2.6 962.6.1 Variáveis Globais 962.6.2 Funções de Arquivo e Globais 972.6.3 Módulos 972.6.4 Como Construir Programas Multiarquivo 98

Utilizando um Ambiente Integrado de Desenvolvimento 98Utilizando Editor de Programas e Compilador 99Make e Arquivos Makefiles 100

2�7 Exemplos de Programação 2.7 1032.7.1 Um Módulo para Leitura de Dados Resiliente 1032.7.2 Comparando Números Reais 1072.7.3 Série de Taylor para Cálculo de Seno 1072.7.4 Raiz Quadrada Usando o Método de Newton e Raphson 109

2�8 Exercícios de Revisão 2.8 110Funções (Seção 2.1) 110Leitura de Dados via Teclado 2: Robusta (Seção 2.2) 112Duração de Variáveis (Seção 2.3) 112Escopo (Seção 2.4) 113Diretivas de Pré-processamento (Seção 2.5) 114Programas Multiarquivo (Seção 2.6) 114Exemplos de Programação (Seção 2.7) 115


3 Tipos de Dados Estruturados �� 1193�1 Arrays 3.1 120

3.1.1 Definições de Arrays 1203.1.2 Acesso a Elementos de um Array 1203.1.3 Iniciações de Arrays 1213.1.4 Tamanho de Array 121

3�2 Aritmética de Ponteiros 3.2 1223�3 Relações entre Ponteiros e Arrays 3.3 123

Tabela de Conteúdo | xiii

3�4 O Qualificador const 3.4 1243�5 Uso de Arrays com Funções 3.5 125

3.5.1 Declarando Arrays como Parâmetros Formais 1253.5.2 Arrays como Parâmetros Reais 1263.5.3 Retorno de Arrays e Zumbis 1263.5.4 Qualificação de Parâmetros com const 127

3�6 Arrays Multidimensionais 3.6 1273.6.1 Iniciações de Arrays Multidimensionais 1273.6.2 Acesso a Elementos de Arrays Multidimensionais 1283.6.3 Arrays Multidimensionais como Parâmetros de Funções 129

3�7 Strings e Caracteres 3.7 1293.7.1 Strings 1293.7.2 Funções de Biblioteca para Processamento de Strings 1303.7.3 Conversão de Strings Numéricos em Números 1313.7.4 Classificação de Caracteres: Funções isX() 1323.7.5 Transformação de Caracteres: tolower() e toupper() 132

3�8 Função main() com Parâmetros 3.8 1323�9 Tipos Definidos pelo Programador 3.9 1333�10 Estruturas e Uniões 3.10 133

3.10.1 Definições de Estruturas 1343.10.2 Estrutura com Autorreferência 1343.10.3 Iniciações de Estruturas 1353.10.4 Atribuições entre Estruturas 1353.10.5 Acesso a Campos de Estruturas 1353.10.6 Aninho de Estruturas 1363.10.7 Estruturas como Parâmetros de Funções 1373.10.8 Funções com Retorno de Estruturas 1373.10.9 Uniões 1383.10.10 Registros Variantes 138

3�11 Operadores de Acesso e Definidores de Tipos 3.11 1393�12 Exemplos de Programação 3.12 141

3.12.1 Incrementando o Módulo de Leitura Resiliente 1413.12.2 Ordenação de Arrays pelo Método da Bolha 1433.12.3 Validando Datas 1443.12.4 Operações com Vetores Reais 1463.12.5 Coordenadas Retangulares e Polares 148

3�13 Exercícios de Revisão 3.13 151Arrays (Seção 3.1) 151Aritmética de Ponteiros (Seção 3.2) 152Relações entre Ponteiros e Arrays (Seção 3.3) 152O Qualificador const (Seção 3.4) 153Uso de Arrays com Funções (Seção 3.5) 153Arrays Multidimensionais (Seção 3.6) 155Strings e Caracteres (Seção 3.7) 155

xiv | Tabela de Conteúdo

Função main() com Parâmetros (Seção 3.8) 156Tipos Definidos pelo Programador (Seção 3.9) 157Estruturas e Uniões (Seção 3.10) 157Operadores de Acesso e Definidores de Tipos (Seção 3.11) 157Exemplos de Programação (Seção 3.12) 158


4 Recursão e Retrocesso �� 1634�1 Funções Recursivas 4.1 1644�2 Cadeias Recursivas 4.2 1664�3 Pilha de Execução e Registros de Ativação 4.3 1664�4 Recursão de Cauda 4.4 1704�5 Retrocesso (Backtracking) 4.5 173

4.5.1 O Problema das N Rainhas 174Entendendo o Problema 175Implementação da Solução 178

4.5.2 Outros Problemas Propícios ao Uso de Retrocesso 1904�6 Como Pensar Recursivamente 4.6 1904�7 Quando Usar (e Não Usar) Recursão 4.7 1924�8 Exemplos de Programação 4.8 195

4.8.1 O (Cansativo) Problema das Torres de Hanói 1954.8.2 Fibonacci + Recursão = Ineficiência 1 1984.8.3 Calculando o Comprimento de um String Recursivamente 2004.8.4 Removendo Vogais de um String Recursivamente 2004.8.5 Exponenciação por Quadratura 1 2014.8.6 Invertendo Entradas 1 2024.8.7 Exibindo-se em Frente e Verso 2024.8.8 Resolvendo Sudoku 204

4�9 Exercícios de Revisão 4.9 207Funções Recursivas (Seção 4.1) 207Cadeias Recursivas (Seção 4.2) 210Pilha de Execução e Registros de Ativação (Seção 4.3) 211Recursão de Cauda (Seção 4.4) 211Retrocesso (Backtracking) (Seção 4.5) 211Como Pensar Recursivamente (Seção 4.6) 211Quando Usar (e Não Usar) Recursão (Seção 4.7) 212Exemplos de Programação (Seção 4.8) 212


Parte 2: Fundamentos

5 Conceitos Básicos de Estruturas de Dados �� 2175�1 Definições Fundamentais 5.1 2185�2 Tipos Abstratos e Estruturas de Dados 5.2 219

Tabela de Conteúdo | xv

5�3 Algoritmos 5.3 2205.3.1 Abordagem de Refinamentos Sucessivos 2215.3.2 Linguagem Algorítmica (Pseudolinguagem) 2215.3.3 Como Construir Algoritmos 2215.3.4 Paradigmas Algorítmicos 222

Algoritmos de Divisão e Conquista 222Algoritmos de Retrocesso 222Algoritmos Vorazes 223Algoritmos de Força Bruta 223

5�4 Tipos de Dados Transparentes e TADs em C 5.4 2235�5 Exemplos de Programação 5.5 225

5.5.1 Número Complexo como um Tipo de Dado Transparente 225Interface 225Implementação 226

5.5.2 Número Complexos como um TAD 227Interface 227Implementação 228

5�6 Exercícios de Revisão 5.6 229Definições Fundamentais (Seção 5.1) 229Tipos Abstratos e Estruturas de Dados (Seção 5.2) 230Algoritmos (Seção 5.3) 230Tipos de Dados Transparentes e TADs em C (Seção 5.4) 231Exemplos de Programação (Seção 5.5) 231


6 Análise de Algoritmos�� 2356�1 Complexidade de Algoritmos 6.1 2366�2 Análise Assintótica 6.2 2376�3 Notações Ó, Ômega e Teta 6.3 2386�4 Casos Melhor, Pior e Mediano 6.4 2446�5 Funções Comuns em Análise de Algoritmos 6.5 2466�6 Resultados Teóricos Importantes 6.6 2496�7 Regras Práticas para Análise Temporal de Algoritmos 6.7 250

6.7.1 Análise Temporal de Instruções Simples 2516.7.2 Análise Temporal de Sequências de Instruções 2516.7.3 Análise Temporal de Estruturas de Controle 251

Desvios Condicionais 251Desvios Incondicionais e Instruções de Retorno 252Laços de Repetição 252

6.7.4 Análise Temporal de Chamadas de Funções 2526�8 Análise de Custo Espacial de Algoritmos 6.8 2536�9 Algoritmos Recursivos e Relações de Recorrência 6.9 2546�10 Árvores de Recursão 6.10 255

6.10.1 Conceitos 255

xvi | Tabela de Conteúdo

6.10.2 Exemplos 257Equação de Recorrência 1: T(n) = 2·T(n/2) + n 257Equação de Recorrência 2: T(n) = T(n/2) + n 258Equação de Recorrência 3: 4·T(n) = T(n/2) + n 259

6.10.3 Análise 2606�11 Exemplos de Programação 6.11 261

6.11.1 Um Algoritmo com Custo Temporal θ(1) 2616.11.2 Um Algoritmo com Custo Temporal θ(n) 2616.11.3 Um Algoritmo com Custo Temporal θ(n2) 2616.11.4 Um Algoritmo com Custo Temporal θ(log n) 2626.11.5 Um Algoritmo com Custo Temporal θ(n log n) 2636.11.6 Quando Será o Fim do Mundo? 2646.11.7 Fibonacci + Recursão = Ineficiência 2 2666.11.8 Exponenciação por Quadratura 2 268

6�12 Exercícios de Revisão 6.12 268Complexidade de Algoritmos (Seção 6.1) 268Análise Assintótica (Seção 6.2) 268Notações Ó, Ômega e Teta (Seção 6.3) 269Casos Melhor, Pior e Mediano (Seção 6.4) 270Funções Comuns em Análise de Algoritmos (Seção 6.5) 270Resultados Teóricos Importantes (Seção 6.6) 271Regras Práticas para Análise Temporal de Algoritmos (Seção 6.7) 272Análise de Custo Espacial de Algoritmo (Seção 6.8) 275Algoritmos Recursivos e Relações de Recorrência (Seção 6.9) 275Árvores de Recursão (Seção 6.10) 275Exemplos de Programação (Seção 6.11) 276


Parte 3: estruturas de dados BásiCas

7 Listas Indexadas �� 2797�1 Listas sem Ordenação 7.1 280

7.1.1 Abstração 2807.1.2 Implementação Usando Arrays Estáticos 281

Definições de Tipos 282Iniciação 282Comprimento 282Acesso 282Inserção 283Acréscimo 284Remoção 285Checagem de Lista Vazia 286

7.1.3 Busca Sequencial 2867�2 Listas Ordenadas 7.2 288

Tabela de Conteúdo | xvii

7.2.1 Abstração 2887.2.2 Implementação Usando Arrays Estáticos 2887.2.3 Busca Binária 289

7�3 Análise de Operações sobre Listas Indexadas 7.3 2927�4 Tratamento de Exceções 7.4 2937�5 Aplicações de Listas 7.5 296

7.5.1 Representação de Polinômios 2967.5.2 Representação de Matrizes Esparsas 298

7�6 Exemplos de Programação 7.6 3017.6.1 Gerenciando uma Lista de Compras com Sensibilidade 3017.6.2 Lista Ordenada Armazenada em Arquivo 3077.6.3 Removendo Duplicatas de uma Lista 315

7�7 Exercícios de Revisão 7.7 316Listas sem Ordenação (Seção 7.1) 316Listas Ordenadas (Seção 7.2) 317Análise de Operações sobre Listas Indexadas (Seção 7.3) 317Tratamento de Exceções (Seção 7.4) 317Aplicações de Listas (Seção 7.5) 317Exemplos de Programação (Seção 7.6) 318


8 Pilhas e Filas �� 3218�1 Pilhas 8.1 322

8.1.1 Conceito 3228.1.2 Implementação 3248.1.3 Análise 325

8�2 Filas Lineares 8.2 3258.2.1 Conceito 3258.2.2 Implementação 3268.2.3 Análise 329

8�3 Filas Circulares 8.3 3298�4 Transformando Recursão em Iteração Usando Pilha 8.4 3338�5 Exemplos de Programação 8.5 338

8.5.1 Invertendo Entradas 2 3388.5.2 Casamento de Parênteses, Colchetes e Chaves 3398.5.3 Testando Palíndromos 3428.5.4 Fazendo, Desfazendo e Refazendo 3438.5.5 Simulação de Fila de Banco 352

8�6 Exercícios de Revisão 8.6 355Pilhas (Seção 8.1) 355Filas Lineares (Seção 8.2) 357Filas Circulares (Seção 8.3) 358Transformando Recursão em Iteração Usando Pilha (Seção 8.4) 358Exemplos de Programação (Seção 8.5) 358

xviii | Tabela de Conteúdo


9 Alocação Dinâmica de Memória �� 3619�1 Motivação e Justificativas 9.1 3629�2 Funções de Alocação e Liberação Dinâmica de Memória 9.2 363

9.2.1 malloc() 3639.2.2 calloc() 3639.2.3 free() 3649.2.4 realloc() 365

9�3 Ponteiros Genéricos e o Tipo void * 9.3 3669�4 A Partição de Memória Heap 9.4 3689�5 Testando Alocação Dinâmica de Memória 9.5 3699�6 Listas Indexadas Dinâmicas 9.6 369

9.6.1 Lista sem Ordenação 370Definições de Tipos e Constantes 370Criação 370Destruição 371Inserção 371Remoção 372Acréscimo de Elemento 373

9.6.2 Lista Ordenada 373Definições de Tipos e Constantes 373Criação 374Inserção em Ordem 375Remoção 375

9�7 Pilhas e Filas Implementadas com Arrays Dinâmicos 9.7 3769.7.1 TAD Pilha 1 376

Arquivo de Cabeçalho 376Arquivo de Implementação 377

9.7.2 TAD Fila 1 378Arquivo de Cabeçalho 378Arquivo de Implementação 378

9�8 Análise de Implementações com Arrays Dinâmicos 9.8 3809�9 Exemplos de Programação 9.9 380

9.9.1 Lendo Linhas (Praticamente) Ilimitadas 3809.9.2 A Urupema de Eratóstenes 3869.9.3 Concatenação Múltipla de Strings 389

9�10 Exercícios de Revisão 9.10 391Motivação e Justificativas (Seção 9.1) 391Funções de Alocação e Liberação Dinâmica de Memória (Seção 9.2) 391Ponteiros Genéricos e o Tipo void * (Seção 9.3) 393A Partição de Memória Heap (Seção 9.4) 393Testando Alocação Dinâmica de Memória (Seção 9.5) 393Listas Indexadas Dinâmicas (Seção 9.6) 394

Tabela de Conteúdo | xix

Pilhas e Filas Implementadas com Arrays Dinâmicos (Seção 9.7) 394Análise de Implementações com Arrays Dinâmicos (Seção 9.8) 394Exemplos de Programação (Seção 9.9) 394


10 Listas Encadeadas �� 39710�1 Deficiências de Arrays Dinâmicos 10.1 39810�2 Lista Simplesmente Encadeada sem Ordenação 10.2 399

10.2.1 Abstração 39910.2.2 Implementação 399

Definições de Tipos 399Iniciação 401Checagem de Lista Vazia 401Comprimento 401Inserção no Início 401Remoção 403Busca 406Destruição 407Acesso Sequencial 408

10�3 Lista Simplesmente Encadeada com Ordenação 10.3 40910.3.1 Abstração 40910.3.2 Implementação 410

Inserção em Ordem 410Busca 413

10�4 Outros Tipos de Listas Encadeadas 10.4 41310.4.1 Lista Duplamente Encadeada Linear 414

Inserção 414Remoção 415Acesso Sequencial Invertido 416

10.4.2 Lista Simplesmente Encadeada Circular 417Inserção 417Remoção 419Busca 420Destruição 420Acesso Sequencial 420

10.4.3 Lista Duplamente Encadeada Circular 420Inserção 420Remoção 422Busca 423Destruição 423Acesso Sequencial 423Acesso Sequencial Invertido 423

10.4.4 Lista Encadeada com Cabeça 424Iniciação 424

xx | Tabela de Conteúdo

Comprimento 424Inserção 425Remoção 425Busca 425Destruição 425Acessos Sequenciais Direto e Invertido 425

10�5 Pilhas e Filas Encadeadas 10.5 42610.5.1 TAD Pilha 2 426

Arquivo de Cabeçalho 426Arquivo de Implementação 426

10.5.2 TAD Fila 2 428Arquivo de Cabeçalho 428Arquivo de Implementação 428

10�6 Análise de Operações sobre Listas Encadeadas 10.5 43010�7 Exemplos de Programação 10.7 430

10.7.1 Invertendo uma Lista Simplesmente Encadeada 43010.7.2 Números Felizes 43210.7.3 Representação de Polinômios Usando Listas Encadeadas 43410.7.4 A História de Josephus 44010.7.5 Números Inteiros de Larguras Ilimitadas 443

10�8 Exercícios de Revisão 10.8 453Deficiências de Arrays Dinâmicos (Seção 10.1) 453Lista Simplesmente Encadeada sem Ordenação (Seção 10.2) 453Lista Simplesmente Encadeada com Ordenação (Seção 10.3) 455Outros Tipos de Listas Encadeadas (Seção 10.4) 456Pilhas e Filas Encadeadas (Seção 10.5) 458Análise de Operações sobre Listas Encadeadas (Seção 10.6) 458Exemplos de Programação (Seção 10.7) 458


11 Estruturas de Dados e Algoritmos Genéricos �� 46311�1 Ponteiros para Funções 11.1 464

11.1.1 Definição de Ponteiro para Função 46411.1.2 Atribuição de Valor a um Ponteiro para Função 46511.1.3 Chamada de Função Mediante Ponteiro 46611.1.4 Retorno de Ponteiro para Função 46611.1.5 Ponteiro para Função como Parâmetro de Função 467

11�2 Listas Generalizadas 11.2 46811.2.1 Conceitos 46811.2.2 Implementação 46911.2.3 Funções Recursivas para Listas Generalizadas 470

Clonagem 470Igualdade 470Profundidade 471

Tabela de Conteúdo | xxi

Exibição 47211�3 Estruturas de Dados Genéricas 11.3 47211�4 Implementação de Pilha Genérica 11.4 473

11.4.1 Definição de Tipo 47311.4.2 Criação 47311.4.3 Destruição 47411.4.4 Verificação de Pilha Vazia 47411.4.5 Empilhamento 47411.4.6 Desempilhamento 47511.4.7 Elemento do Topo 476

11�5 Usando bsearch() e qsort() 11.5 47611�6 Conversões e Avaliações de Expressões Aritméticas 11.6 478

11.6.1 Formas de Representação de Expressões Aritméticas 47811.6.2 Avaliação de Expressão Sufixa 48011.6.3 Conversão de Forma Infixa para Forma Sufixa 480

11�7 Exemplos de Programação 11.7 48411.7.1 Ordenação Generalizada de Listas Indexadas 48411.7.2 Implementando Conversão de Expressões Infixas em Sufixas 48511.7.3 Implementando Avaliação de Expressões Sufixas 490

11�8 Exercícios de Revisão 11.8 493Ponteiros para Funções (Seção 11.1) 493Listas Generalizadas (Seção 11.2) 493Estruturas de Dados Genéricas (Seção 11.3) 494Implementação de Pilha Genérica (Seção 11.4) 494Usando bsearch() e qsort() (Seção 11.5) 494Conversões e Avaliações de Expressões Aritméticas (Seção 11.6) 495Exemplos de Programação (Seção 11.7) 496


12 Árvores �� 49912�1 Conceitos Fundamentais 12.1 50012�2 Árvores Binárias 12.2 502

12.2.1 Degeneradas (ou Patológicas) 50312.2.2 Estritamente Binárias 50312.2.3 Perfeitas (ou Repletas) 50312.2.4 Completas 504

12�3 Caminhamentos em Árvores Binárias 12.3 50612.3.1 Caminhamento Prefixo 50612.3.2 Caminhamento Infixo 50712.3.3 Caminhamento Sufixo 50712.3.4 Exemplos 50712.3.5 Caminhamento em Largura (ou por Nível) 510

12�4 Implementação de Árvores Binárias 12.4 51012.4.1 Definição de Tipo 510

xxii | Tabela de Conteúdo

12.4.2 Criação de Nós 51112.4.3 Caminhamentos 51212.4.4 Altura 51212.4.5 Semelhança 51312.4.6 Clonagem 51412.4.7 Contagem de Nós 51412.4.8 Destruição 514

12�5 Árvores Binárias Baseadas em Caminhamentos 12.5 51412�6 Árvores Binárias Costuradas 12.6 51812�7 Conversões de Árvores Ordinárias e Florestas em Árvores Binárias 12.7 52112�8 Exemplos de Programação 12.8 524

12.8.1 Problema das Oito Moedas 52412.8.2 Codificação de Huffman 525

12�9 Exercícios de Revisão 12.9 538Conceitos Fundamentais (Seção 12.1) 538Árvores Binárias (Seção 12.2) 539Caminhamentos em Árvores Binárias (Seção 12.3) 542Implementação de Árvores Binárias (Seção 12.4) 544Árvores Binárias Baseadas em Caminhamentos (Seção 12.5) 546Árvores Binárias Costuradas (Seção 12.6) 546Conversões de Árvores Ordinárias e Florestas em Árvores Binárias (Seção 12.7) 546Exemplos de Programação (Seção 12.8) 547


aPêndiCes

A Precedência e Associatividade de Operadores da Linguagem C �� 553

B Elementos de Matemática �� 555B�1 Somatórios B.1 555B�2 Polinômios B.2 556B�3 O Método de Horner B.3 557B�4 Logaritmos B.4 559B�5 Matrizes B.5 559B�6 Funções Piso e Teto B.6 560B�7 Análise Combinatória B.7 561B�8 Indução Matemática B.8 562

B.8.1 Indução Fraca 562B.8.2 Indução Forte 563

B�9 Relações de Recorrência B.9 564B.9.1 Conjectura e Indução Matemática 565B.9.2 Relações de Recorrência Homogêneas 565

B�10 Propriedades de Análise Assintótica B.10 566

Tabela de Conteúdo | xxiii

B�11 Propriedades de Árvores Binárias B.11 569

C Guia de Nomenclatura Usada em Identificadores �� 573C�1 Regras Básicas de Escrita de Identificadores C.1 573

C.1.1 Variáveis e Parâmetros Formais 573C.1.2 Macros e Constantes de Enumeração 574C.1.3 Funções 574C.1.4 Tipos 574C.1.5 Rótulos de Estruturas 574

C�2 Glossário de Sufixos de Identificadores C.2 574

D Respostas e Sugestões para os Exercícios de Revisão �� 577Capítulo 1 — Elementos Básicos da Linguagem C Capítulo 1 .................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................577Capítulo 2 — Funções e Programas Multiarquivo Capítulo 2 ..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................582Capítulo 3 — Tipos de Dados Estruturados Capítulo 3 ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................586Capítulo 4 — Recursão e Retrocesso Capítulo 4 ...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................590Capítulo 5 — Conceitos Básicos de Estruturas de Dados Capítulo 5 ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................592Capítulo 6 — Análise de Algoritmos Capítulo 6 ..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................593Capítulo 7 — Listas Indexadas Capítulo 7 ......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................599Capítulo 8 — Pilhas e Filas Capítulo 8 ............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................601Capítulo 9 — Alocação Dinâmica de Memória Capítulo 9 .........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................604Capítulo 10 — Listas Encadeadas Capítulo 10 .........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................606Capítulo 11 — Estruturas de Dados e Algoritmos Genéricos Capítulo 11 ............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................610Capítulo 12 — Árvores Capítulo 12 ..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................611

reFerênCias

Bibliografia �� 621

Índice Remissivo �� 623

Documents

arte evisão da inguagem Culysseso.com/livros/ed1/TOC.pdf · Tabela de Conteúdo | xi goto 65 Uso de break e continue em Laços Aninhados 66 1 16 Outros Operadores 66 1.16.1 Operador