Estrutura de dados usando C
904 pág.

Estrutura de dados usando C


DisciplinaAlgoritmos e Programação 2145 materiais3.827 seguidores
Pré-visualização50 páginas
MAKRONBooks
Estruturas de Dados
Usando C
EDITORA AFILIADA
MAKRON
Books Estruturas de Dados
Usando C
Aaron Ai Tenenbaum, Yedidyah Langsam,
Moshe J. Augenstein
Tradução
Teresa Cristina Félix de Souza
Revisão Técnica e Adaptação dos Programas
Roberto Carlos Mayer
Professor do Departamento de Ciência da Computação
da Universidade de São Paulo
Diretor da MBI \u2014 Mayer & Bunge Informática S/C Ltda
MAKRON Books do Brasil Editora Ltda.
São Paulo
Rua Tabapuã, 1348 Itaim Bibi
CEP 04533-004
(011) 829-8604 e (011) 820-6622
Rio de Janeiro \u2022 Lisboa \u2022 Bogotá \u2022 Buenos Aires \u2022 Guatemala \u2022 Madrid \u2022 México \u2022
New York \u2022 Panamá \u2022 San Juan \u2022 Santiago
Auckland \u2022 Hamburg \u2022 Kuala Lumpur \u2022 London \u2022 Milan \u2022 Montreal \u2022 New Delhi \u2022
Paris \u2022 Singapore \u2022 Sydney \u2022 Tokyo \u2022 Toronto
Do original
Data Structures Using C
Copyright © 1989 by Prentice Hall, Inc.
Original em inglês publicado pela McGraw-Hill, Inc.
Copyright.© 1995 da MAKRON Books do Brasil Editora ]
Todos os direitos para a língua portuguesa reservados pela MAKRON Books do Brasil
Editora Ltda.
Nenhuma parte desta publicação poderá ser reproduzida, guardada pelo sistema "retrieval"
ou transmitida de qualquer modo ou por qualquer outro meio, seja este eletrônico, mecânico,
de fotocópia, de gravação, ou outros, sem prévia autorização, por escrito, da Editora.
EDITOR: MILTON MIRA DE ASSUMPÇÃO FILHO
Gerente Editorial: Daisy Pereira Daniel
Produtora Editorial: Mônica Franco Jacintho
Produtor Gráfico: José Rodrigues
Editoração Eletrônica e Fotolitos: E.R.J. Informática Ltda.
Dados Internacionais de Catalogação na Publicação (CIP)
(Câmara Brasileira do Livro, SP, Brasil)
Tenenbaum, Aaron M.
Estruturas de dados usando C / Aaron M. Tenenbaum,
Yedidyah Langsam, Moshe J. Augenstein ; tradução
Teresa Cristina Félix de Souza ; revisão técnica e
adaptação dos programas Roberto Carlos Mayer. \u2014
São Paulo : MAKRON Books, 1995.
ISBN 85-346-0348-0
1. C (Linguagem de programação para computadores)
2. Dados - Estruturas (Ciência da computação)
I. Langsam, Yedidyah, 1952- II. Augenstein, Moshe
J., 1947- III. Título.
95-0783 CDD-005.73
Índices para catálogo sistemático:
1. Dados : Estruturas : Processamento de dados
005.73
2. Estruturas de dados : Processamento de dados
005.73
À minha esposa, Miriam (AT)
A minha esposa, Vivienne Esther (YL)
A minha filha, Chaya (MA)
MAKRON
Books
Sumário
Prefácio XVII
1. Introdução às Estruturas de Dados
1.1 Informações e Significado
Inteiros Binários e Decimais
Números Reais
Strings de Caracteres
Hardware & Software
0 Conceito de Implementação
Um Exemplo
Tipos de Dados Abstratos
Seqüências Como Definições de Valores
Um TDA para Strings de Caracteres de Tamanho Variável
Tipos de Dados em C
Ponteiros em C 
Estruturas de Dados e C
Exercícios
1.2. Vetores em C
0 Vetor Como um TDA
Usando Vetores Unidimensionais
,1
1
4
6
7
9
11
12
18
23
25
27
27
30
32
34
36
37
VII
VIII Estruturas de Dados Usando C
Implementando Vetores Unidimensionais
Vetores Como Parâmetros
Strings de Caracteres em C
Operações com Strings de Caracteres
Vetores Bidimensionais
Vetores Multidimensionais
Exercícios
1.3. Estruturas em C
Implementando Estruturas
Uniões
Implementação de Uniões
Parâmetros de Estrutura
Representando Outras Estruturas de Dados
Números Racionais
Alocação de Armazenamento e Escopo de Variáveis
Exercícios
2. A Pilha
2.1. Definição e Exemplos
Operações Primitivas
Um Exemplo
A Pilha Como um Tipo de Dado Abstrato
Exercícios
2.2. Representando Pilhas em C
Implementando a Operação POP
Verificando Condições Excepcionais
Implementando a Operação Push
Exercícios
2.3. Um Exemplo: Infixo, Posfixo e Prefixo
Definições Básicas e Exemplos
Avaliando uma Expressão Posfixa
Programa para Avaliar uma Expressão Posfixa
Limitações do Programa
Convertendo uma Expressão da Forma Infixa para a Posfíxal
Programa para Converter uma Expressão da Forma Infixa na Forma Posfixa .
Exercícios
39
43
44
45
46
50
53
57
62
65
68
69
73
73
77
83
.86
86
88
91
95
96
97
102
105
105
109
111
111
114
116
119
120
126
129
Sumário IX
3. Recursividade
3.1. Definições Recursivas e Processos
A Função Fatorial
Multiplicação de Números Naturais
A Seqüência de Fibonacci
A Busca Binária
Propriedades das Definições ou Algoritmos Recursivos
Exercícios
3.2. Recursividade em C
Fatorial em C
Os Números de Fibonacci em C
Busca Binária em C
Cadeias Recursivas
Definição Recursiva de Expressões Algébricas
Exercícios
3.3. Escrevendo Programas Recursivos
0 Problema das Torres de Hanoi
Conversão da Forma Prefixa para a Posfixa Usando Recursividade
Exercícios
3.4. Simulando a Recursividade
Retorno de uma Função
Implementando Funções Recursivas
Simulação de Fatorial
Aprimorando a Rotina Simulada
Eliminando Gotos
Simulando as Torres de Hanoi
Exercícios
3.5. Eficiência da Recursividade
Exercícios
4. Filas e Listas
4.1. A Fila e sua Representação Seqüencial
A Fila Como um Tipo de Dado Abstrato
Implementação de Filas em C
132
132
133
136
137
138
142
143
145
145
150
152
154
155
159
162
164
171
176
180
182
184
185
190
192
195
202
204
206
207
207
209
X Estruturas de Dados Usando C
A Operação Insert
A Fila de Prioridade
Implementação em Vetor de uma Fila de Prioridade
Exercícios
4.2. Listas Ligadas
Inserindo e Removendo Nós de uma Lista
Implementação Ligada de Pilhas
As Operações Getnode e Freenode
Implementação Ligada de Filas
Listas Ligadas Como Estrutura de Dados
Exemplos de Operações de Lista
Implementação em Lista de Filas de Prioridade
Nós de Cabeçalho
Exercícios
4.3. Listas em C
Implementação de Listas em Vetor ,
Limitações da Implementação em Vetor
Alocando e Liberando Variáveis Dinâmicas
Listas Ligadas Usando Variáveis Dinâmicas
Filas Como Listas em C
Exemplos de Operações de Listas em C
Listas Não-Inteiras e Não-Homogêneas
Comparando a Implementação em Vetor e a Dinâmica de Listas
Implementando Nós de Cabeçalho
Exercícios ,
4.4. Um Exemplo: Simulação Usando Listas Ligadas
0 Processo de Simulação
Estruturas de Dados
0 Programa de Simulação
Exercícios
4.5. Outras Estruturas de Lista
Listas Circulares
A Pilha Como uma Lista Circular
A Fila Como uma Lista Circular
Operações Primitivas Sobre Listas Circulares
0 Problema de Josephus
215
216
218
220
223
225
230
231
233
235
238
241
241
244
245
245
249
250
256
258
260
262
264
265
265
268
269
271
272
276
279
279
281
282
283
285
Sumário XI
Nós de Cabeçalho
Soma de Inteiros Positivos Longos Usando Listas Circulares
Listas Duplamente Ligadas
Soma de Inteiros Longos Usando Listas Duplamente Ligadas
Exercícios
5. Árvores
5.1. Árvores Binárias
Operações Sobre Árvores Binárias
Aplicações de Árvores Binárias
Exercícios
5.2. Representações de Árvores Binárias
Representação de Nós de Árvores Binárias
Nós Internos e Externos
Representação Implícita em Vetores de Árvores Binárias
Escolhendo uma Representação de Árvore Binária
Percursos de Arvores Binárias em C
Árvores Binárias Encadeadas
Percurso Usando um Campo Father
Árvores Binárias Heterogêneas
Exercícios
5.3. Um Exemplo: o Algoritmo de Huffman
0 Algoritmo de Huffman
Um Programa em C
Exercícios
5.4. Representando Listas Como Árvores Binárias
Localizando o Késimo Elemento 
Eliminando um Elemento
Implementando Listas Representadas Por Arvores em C
Construindo uma Lista Representada Por Árvore
Revisitando o Problema de Josephus
Exercícios
5.5. Árvores e Suas Aplicações
Representações de Árvores em C 
Percurso de Árvores
287
288
291
294
300
303
303
311
312
318
320
320
324
325
330
331
335
340
343
346
350
353
355
360
361
364
366
371
374
376
377
378
381
385
XII Estruturas
Eliadela
Eliadela fez um comentário
Gostaria de materia que fala de vetores e matrizes
0 aprovações
Sales
Sales fez um comentário
válida
0 aprovações
Carregar mais