Transcription
Estrutura de Dadoscom Algoritmos e C
)WGVIZIV YQ PMZVS R S YQE XEVIJE J GMP RYRGE JSM 8SQE XIQTSI\MKI TIWUYMWE I HIHMGEª S 'SQS EW IHMXSVEW R S HIWINEQ QEMWTYFPMGEV IWXI X XYPS REHE QEMW REXYVEP UYI XIRXEV GSQIVGMEPM E PSRE JSVQE HI EVUYMZS WIQIPLERXI E YQ IFSSO 1EW IWXE EXMZMHEHIXEQF Q XSQE XIQTS I I\MKI HIHMGEª S4IRWERHS EWWMQ VIWSPZM PMFIVEV IWXI PMZVS TEVE GSRWYPXE T½FPMGEWI ZSG- EGLE UYI IWXI PMZVS XI ENYHSY I UYMWIV GSPEFSVEV GSQMKSTEWWI RYQE PSX VMGE I HITSWMXI S ZEPSV UYI EGLEV UYI HIZI8IVQMRSY HI TEKEV E GSRXE HI PY XIPIJSRI SY KYE I WSFVSYXVSGS ZSG- TSHI HITSWMXEV RE QMRLE GSRXE )Y EGVIHMXS UYI R¶WHSMW TSHIQSW WEMV KERLERHS ZSG- TSVUYI XIZI EGIWWS E YQFSQ QEXIVMEP UYI XI ENYHSY I IY GSQS MRGIRXMZS E GSRXMRYEVIWGVIZIRHS PMZVSW 'EWS HI GIVXS XEPZI SW TV¶\MQSW PMZVSW RIQWINEQ TYFPMGEHSW TSV YQE IHMXSVE I IWXINEQ PMFIVEHSW HMVIXEQIRXITEVE WYE GSRWYPXE5YEPUYIV ZEPSV HITSWMXEHS WIV HMVIGMSREHS TEVE E GSRXE TSYTERªEHS QIY PLS TEVE UYERHS IPI IWXMZIV RE QEMSVMHEHI XIV VIGYVWSWTEVE GSQIªEV YQ RIK¶GMS TV¶TVMS RERGMEV WIYW IWXYHSW IXG(EHSW TEVE HIT¶WMXS1EVGSW %YVIPMS 4GLIO 0EYVIERS&ERGS'EM\E )GSR·QMGE *IHIVEP%K-RGME3TIVEª S'SRXE'YVMXMFEHI QEVªS HI
Estrutura de Dadoscom Algoritmos e CMarcos Laureano
Copyright 2008 por Brasport Livros e Multimídia Ltda.Todos os direitos reservados. Nenhuma parte deste livro poderá ser reproduzida, sob qualquermeio, especialmente em fotocópia (xerox), sem a permissão, por escrito, da Editora.Editor: Sergio Martins de OliveiraDiretora Editorial: Rosa Maria Oliveira de QueirozAssistente de Produção: Marina dos Anjos Martins de OliveiraRevisão de Texto: Maria Helena A. M. OliveiraEditoração Eletrônica: Abreu’s System LTDA.Capa: Use DesignTécnica e muita atenção foram empregadas na produção deste livro. Porém, erros de digitação e/ou impressão podemocorrer. Qualquer dúvida, inclusive de conceito, solicitamos enviar mensagem para brasport@brasport.com.br,para que nossa equipe, juntamente com o autor, possa esclarecer. A Brasport e o(s) autor(es) não assumem qualquerresponsabilidade por eventuais danos ou perdas a pessoas ou bens, originados do uso deste livro.Dados Internacionais de Catalogação na Publicação (CIP)(Câmara Brasileira do Livro, SP, Brasil)BRASPORT Livros e Multimídia Ltda.Rua Pardal Mallet, 23 – Tijuca20270-280 Rio de Janeiro-RJTels. Fax: (21) 2568.1415/2568.1507/2569.0212/2565.8257e-mails: orial@brasport.com.brsite: www.brasport.com.brFilialAv. Paulista, 807 – conj. 91501311-100 – São Paulo-SPTel. Fax (11): 3287.1752e-mail:ilialsp@brasport.com.br
Aos meus genitores Luiz Otávio (in memoriam) e Natália.
AgradecimentosAgradeço à Brasport por mais esta oportunidade de publicar um livro sobreum tema em que vários autores já trabalharam (é claro que este livro tem umdiferencial em relação aos demais).Aos meus colegas professores e alunos que ajudaram a evolução deste material nos últimos anos.E para uma linda flor, que, além de alegrar os meus dias, corrigiu os assassinatos à língua portuguesa.
Sobre o autorMarcos Laureano é tecnólogo em Processamento de Dados pela ESEEI,Pós-graduado em Administração pela FAE Business School e Mestre em Informática Aplicada pela Pontifícia Universidade Católica do Paraná. Doutorandoem Informática Aplicada pela Pontifícia Universidade Católica do Paraná.Trabalha com programação em C no ambiente Unix (AIX/HP-UX) desde1997 e Linux desde 2000, sendo especialista em segurança de sistemas operacionais.É professor de graduação e pós-graduação, tendo lecionado em várias instituições nos últimos anos.É autor de vários guias de utilização/configuração de aplicativos para osambientes Unix e Linux. Possui artigos e livros publicados sobre programação,sistemas operacionais e segurança de sistemas. Dentre eles, Programando emC para Linux, Unix e Windows, também publicado pela Brasport.Atualmente leciona disciplinas relacionadas à segurança, programação, redes de computadores e sistemas operacionais em cursos de graduação e pós-graduação do Centro Universitário Franciscano (UNIFAE) e atua como consultorna área de projetos de desenvolvimento e segurança de sistemas.O autor pode ser contactado pelo e-mail marcos@laureano.eti.br ou através de sua página www.laureano.eti.br, onde está disponível vasto material sobre programação, segurança de sistemas e sistemas operacionais.
Sobre o LivroO crescimento dos cursos tecnológicos específicos e com curta duração (2a 3 anos) gerou uma demanda de livros que tratam diretamente o assunto demaneira clara e eficiente.Este livro é indicado aos cursos tecnológicos, para estudantes e profissionaisque precisem dominar os conceitos e os algoritmos de forma rápida e precisa.O material foi preparado com a experiência do autor em lecionar a disciplina, somada à sua experiência profissional. Outros professores e coordenadoresde cursos foram consultados; com isto, este material tem os assuntos pertinentesà área e pode ser adotado tranqüilamente em cursos de 40 ou 80 horas de Estrutura de Dados ou Programação de Computadores.Os algoritmos podem ser aplicados e convertidos para qualquer linguagemde programação, e os programas em C são simples e objetivos, facilitando oentendimento dos estudantes e profissionais que não dominam totalmente estalinguagem.
Sumário1. Estrutura de Dados . 11.1 Dados Homogêneos .21.1.1 Vetor .21.1.2 Matriz.51.1.3 Ponteiros .111.2 Dados Heterogêneos .161.3 Exercícios .182. Uso de Memória . 192.1 Alocação de memória Estática x Dinâmica .192.2 Alocação dinâmica de memória .202.3 Funções para alocação de memória .202.3.1 Função malloc .212.3.2 Função calloc .212.3.3 Função realloc.212.3.4 Função free .222.4 Utilizando as funções para alocação de memória .222.5 Alocação de memória e estruturas em C .252.6 Ponteiros para ponteiros – mistério ou não .272.7 Mais alocação de vetores e matrizes como ponteiros .292.7.1 Controle de agenda com ponteiros de estruturas e vetores.333. Pilha . 403.1 Representação das Operações com Pseudo-código .423.2 Pilhas em C .423.3 Exercícios .47
XIVEstrutura de Dados com Algoritmos e C4. Fila . 484.1 Representação de Filas com Pseudo-códigos.494.2 Filas em C .514.3 Exercícios .595. Recursividade . 605.1. Função para cálculo de Fatorial .615.2 Número triangular .635.3 Números de Fibonacci .665.4 Algoritmo de Euclides .685.5 Torres de Hanoi .715.6 Curiosidades com Recursividade.745.7 Cuidados com Recursividade .765.8 Vantagens .775.9 Exercícios .776. Lista . 796.1 Vetores ou alocação dinâmica? .826.2 Listas em C .846.3 Exercícios .937. Pesquisa . 947.1 Pesquisa Seqüencial .947.2 Pesquisa Binária .977.3 Exercícios .998. Ordenação. 1008.1 BubbleSort .1008.2 Ordenação por Seleção .1048.3 Ordenação por Inserção .1078.4 QuickSort .1118.5 MergeSort .1158.6 Exercícios .1249. Árvores Binárias . 1259.1 Analogia entre árvores .1259.2 Árvore binária .1269.2.1 Relações .127
SumárioXV9.2.2 Árvore Binária Completa .1289.3 Árvores de Busca Binária .1299.4 Operações em Árvores Binárias .1309.4.1 Inserção .1309.4.2 Pesquisa.1329.4.3 Exclusão .1339.4.4 Maior elemento .1369.4.5 Menor elemento .1369.4.6 Percorrendo uma árvore.1369.5 Representações de árvores em C .1389.6 Implementação em C .1399.7 Exercício .148Referências Bibliográficas . 149Índice Remissivo . 151
Lista de Programas1.1: Declaração de vetor em C .41.2: Exemplo de uso de vetores .51.3: Exemplo de uso de matrizes .91.4: Exemplo de uso de matrizes com várias dimensões .101.5: Exemplo de uso de ponteiros .121.6: Ponteiros como referência em funções .131.7: Aritmética com ponteiros .141.8: Vetor como ponteiro .151.9: Exemplo de estrutura .171.10: Exemplo de uso de estruturas com vetores .172.1: Declaração de vetor como ponteiro .222.2: Declaração de matriz como ponteiro .222.3: Exemplo de uso do malloc e realloc .232.4: Exemplo de uso do calloc .242.5: Exemplo de uso de estruturas com ponteiros .252.6: Ponteiro para ponteiro .282.7: Exemplo de uso de alocação de matrizes .302.8: Exemplo de uso de alocação de matrizes dentro de funções .32
XVIIIEstrutura de Dados com Algoritmos e C2.9: Exemplo completo de uso de vetor (ponteiros) de estruturas .333.1: Exemplo de manipulação de pilha.443.2: Exemplo de manipulação de pilha com estrutura .454.1: Exemplo de manipulação de fila em C .514.2: Reajuste da fila .534.3: Declaração de estrutura circular .544.4: Manipulação de fila circular em C .555.1: Fatorial (versão iterativa) .615.2: Fatorial (versão recursiva) .625.3: Descobrindo o número triangular (iterativo) .655.4: Descobrindo o número triangular (recursivo) .655.5: Cálculo do n-ésimo termo de Fibonacci (versão iterativa) .675.6: Cálculo do n-ésimo termo de Fibonacci (versão recursiva).675.7: Cálculo do MDC iterativo .695.8: Cálculo do MDC recursivo .695.9: Cálculo do MDC recursivo .705.10: Torre de Hanoi recursivo .735.11: Natori - Imprimindo as fases da lua .745.12: Dhyanh - Saitou, aku, soku e zan .756.1: Exemplo de manipulação de lista simples em C .846.2: Exemplo de manipulação de lista encadeada em C .866.3: Funções para manipulação de listas .887.1: Função para pesquisa seqüencial .967.2: Função para pesquisa binária .998.1: Função BubbleSort .1028.2: Função BubbleSort melhorado .1038.3: Função Select .106
Lista de ProgramasXIX8.4: Função Insert .1098.5: Ordenação QuickSort .1138.6: Ordenação MergeSort .1178.7: Ordenação MergeSort .1199.1: Representação com vetor de filhos.1389.2: Representação dinâmica .1389.3: Representação dinâmica de uma árvore binária.1399.4: Implementação das operações .139
Lista de Tabelas2.1: Operações com ponteiros .282.2: Operações com ponteiros de ponteiros .295.1: Cálculo de fatorial de 6 .627.1: Entradas e freqüências para cálculo de comparações médias .968.1: BubbleSort - primeira varredura .1018.2: BubbleSort - segunda varredura.1018.3: Seleção - o que ocorre em cada passo .1058.4: Inserção - o que ocorre em cada passo.1099.1: Comparações para busca de um elemento .130
Lista de Algoritmos1.1: Cálculo da posição de índices de um vetor na memória .41.2: Cálculo da posição de índices de uma matriz na memória .63.1: Verificação se a pilha está vazia (função EMPTY(S)) .423.2: Colocar um item na pilha (função PUSH(S,x)) .433.3: Retirada de um item da pilha (função POP(S)) .433.4: Pega o item do topo da pilha mas não desempilha (funçãoSTACKPOP(S)) .433.5: Tamanho da pilha (função SIZE(S)) .444.1: Inclusão de dados na fila (ENQUEUE(Q,x)) .504.2: Retirada de dados na fila (DEQUEUE(Q)).504.3: Verificação se a fila está vazia (função EMPTY(Q)) .504.4: Tamanho da fila (função SIZE(Q)) .514.5: Próximo elemento da fila (função FRONT(Q)) .515.1: Algoritmo de Euclides .695.2: Passar n peças de uma torre (A) para outra (C) .726.1: Inserção numa lista duplamente encadeada .826.2: Remoção numa lista duplamente encadeada.837.1: Pesquisa seqüencial.957.2: Pesquisa seqüencial com ajuste de freqüência .97
XXIIEstrutura de Dados com Algoritmos e C7.3: Pesquisa binária .988.1: Ordenação Bubble .1028.2: Ordenação por Seleção.1068.3: Ordenação por Inserção .1118.4: QuickSort .1138.5: Particiona - Divisão do vetor .1158.6: MergeSort .1218.7: Intercala .1228.8: MergeSort .1239.1: Inserir elemento na árvore - iterativo .1319.2: Inserir elemento na árvore - recursivo .1319.3: Pesquisar elemento na árvore - iterativo.1329.4: Pesquisar elemento na árvore - recursivo .1339.5: Exclusão na árvore .1359.6: Sucessor .1359.7: Maior elemento da árvore .1369.8: Menor elemento da árvore .1379.9: Operação Percorre - Pré-ordem .1379.10: Operação Percorre - Pós-ordem .1379.11: Operação Percorre - Em-ordem .137
Lista de Figuras1.1: Exemplo de Vetor .31.2: Representação de um vetor na memória .41.3: Matriz 2x2 - Cálculo de posição na memória .61.4: Cálculo de posição na memória .71.5: Exemplo de Matriz .71.6: Uma matriz de duas dimensões vista como dois vetores .81.7: Chamada de função com ponteiros .131.8: Vetor como Ponteiro em C .151.9: Registro de funcionário .172.1: Matriz como vetor de ponteiros .202.2: Exemplo de ponteiro na memória.272.3: Exemplo de ponteiro para ponteiro na memória.293.1: Exemplo de Pilha.403.2: Operações em uma pilha .424.1: Operações numa fila .494.2: Operações numa fila circular .555.1: Números triangulares .645.2: Descobrindo o quinto elemento triangular .645.3: Descobrindo o quinto elemento triangular de forma recursiva .65
XXIVEstrutura de Dados com Algoritmos e C5.4: O que ocorre a cada chamada .665.6: Torre de Hanoi .715.7: Movimentos conforme algoritmo .736.1: Exemplo de lista simplesmente encadeada .806.2: Exemplo de lista duplamente encadeada.816.3: Inclusão de novo elemento .816.4: Exclusão de elemento .826.5: Problemática do crescimento do vetor .836.6: Crescimento de uma lista sem utilizar vetor .847.1: Processo de pesquisa seqüencial .957.2: Busca binária .988.1: Exemplo de Ordenação por Seleção com números inteiros.1058.2: Exemplo de Ordenação por Inserção com números inteiros .1088.3: Seqüência de ordenação por inserção .1098.4: Algoritmo da ordenação por inserção .1108.5: Ordenação QuickSort .1128.6: Ordenação MergeSort .1168.7: Ordenação MergeSort .1179.1: Analogia entre árvores .1269.2: Representação de uma árvore.1279.3: Árvore Binária completa de nível 3 .1299.4: Árvore de busca binária - duas organizações diferentes .1299.5: Exclusão de folha .1339.6: Exclusão de um nó com um filho .1349.7: Exclusão de um nó com dois filhos .1349.8: Representação com vetores .1389.9: Representação dinâmica .139
1. Estrutura de Dados“Não existe vitória sem sacrifício!”Filme TransformersUm computador é uma máquina que manipula informações. O estudo daciência da computação inclui o exame da organização, manipulação e utilizaçãodestas informações num computador. Conseqüentemente, é muito importanteentender os conceitos de organização e manipulação de informações.A automatização de tarefas é um aspecto marcante da sociedade moderna,e na ciência da computação houve um processo de desenvolvimento simultâneoe interativo de máquinas (hardware) e dos elementos que gerenciam a execuçãoautomática (software) de uma tarefa.Nesta grande evolução do mundo computacional, um fator de relevante importância é a forma de armazenar as informações, já que, informática é a ciênciada informação. Então de nada adiantaria o grande desenvolvimento do hardwaree do software se a forma de armazenamento e tratamento da informação nãoacompanhasse esse desenvolvimento. Por isso a importância das estruturas de dados, que nada mais são do que formas otimizadas de armazenamento e tratamentodas informações eletronicamente.As estruturas de dados, na maioria dos casos, baseiam-se nos tipos de armazenamento vistos dia a dia, ou seja, nada mais são do que a transformação deuma forma de armazenamento já conhecida e utilizada no mundo real adaptadapara o mundo computacional. Por isso, cada tipo de estrutura de dados possuivantagens e desvantagens e cada uma delas tem sua área de atuação (massa dedados) otimizada.
Estrutura de Dados com Algoritmos e COs dados manipulados por um algoritmo podem possuir natureza distinta,isto é, podem ser números, letras, frases etc. Dependendo da natureza de umdado, algumas operações podem ou não fazer sentido quando aplicadas a eles.Por exemplo, não faz sentido falar em somar duas letras - algumas linguagens deprogramação permitem que ocorra a soma dos valores ASCII correspondentesde cada letra.Para poder distinguir dados de naturezas distintas e saber quais operaçõespodem ser realizadas com eles, os algoritmos lidam com o conceito de tipo dedados. O tipo de um dado deine o conjunto de valores que uma variável podeassumir, bem como
Sobre o autor Marcos Laureano é tecnólogo em Processamento de Dados pela ESEEI, Pós-graduado em Administração pela FAE Business School e Mestre em Infor-mática Aplicada pela Pontifícia Universidade Católica do Paraná.
