1. MAKRONBooksEstruturas de DadosUsando CEDITORA AFILIADA

2. MAKRONBooks Estruturas de DadosUsando CAaron Ai Tenenbaum, Yedidyah Langsam,Moshe J. AugensteinTraduoTeresa Cristina Flix de SouzaReviso Tcnica e Adaptao dos ProgramasRoberto Carlos MayerProfessor do Departamento de Cincia da Computaoda Universidade de So PauloDiretor da MBI Mayer & Bunge Informtica S/C LtdaMAKRON Books do Brasil Editora Ltda.So PauloRua Tabapu, 1348 Itaim BibiCEP 04533-004(011) 829-8604 e (011) 820-6622Rio de Janeiro Lisboa Bogot Buenos Aires Guatemala Madrid Mxico New York Panam San Juan SantiagoAuckland Hamburg Kuala Lumpur London Milan Montreal New Delhi Paris Singapore Sydney Tokyo Toronto 3. Do originalData Structures Using CCopyright 1989 by Prentice Hall, Inc.Original em ingls publicado pela McGraw-Hill, Inc.Copyright. 1995 da MAKRON Books do Brasil Editora ]Todos os direitos para a lngua portuguesa reservados pela MAKRON Books do BrasilEditora Ltda.Nenhuma parte desta publicao poder ser reproduzida, guardada pelo sistema "retrieval"ou transmitida de qualquer modo ou por qualquer outro meio, seja este eletrnico, mecnico,de fotocpia, de gravao, ou outros, sem prvia autorizao, por escrito, da Editora.EDITOR: MILTON MIRA DE ASSUMPO FILHOGerente Editorial: Daisy Pereira DanielProdutora Editorial: Mnica Franco JacinthoProdutor Grfico: Jos RodriguesEditorao Eletrnica e Fotolitos: E.R.J. Informtica Ltda.Dados Internacionais de Catalogao na Publicao (CIP)(Cmara Brasileira do Livro, SP, Brasil)Tenenbaum, Aaron M.Estruturas de dados usando C / Aaron M. Tenenbaum,Yedidyah Langsam, Moshe J. Augenstein ; traduoTeresa Cristina Flix de Souza ; reviso tcnica eadaptao dos programas Roberto Carlos Mayer. So Paulo : MAKRON Books, 1995.ISBN 85-346-0348-01. C (Linguagem de programao para computadores)2. Dados - Estruturas (Cincia da computao)I. Langsam, Yedidyah, 1952- II. Augenstein, MosheJ., 1947- III. Ttulo.95-0783 CDD-005.73ndices para catlogo sistemtico:1. Dados : Estruturas : Processamento de dados005.732. Estruturas de dados : Processamento de dados005.73 4. minha esposa, Miriam (AT)A minha esposa, Vivienne Esther (YL)A minha filha, Chaya (MA) 5. MAKRONBooksSumrioPrefcio XVII1. Introduo s Estruturas de Dados1.1 Informaes e SignificadoInteiros Binrios e DecimaisNmeros ReaisStrings de CaracteresHardware & Software0 Conceito de ImplementaoUm ExemploTipos de Dados AbstratosSeqncias Como Definies de ValoresUm TDA para Strings de Caracteres de Tamanho VarivelTipos de Dados em CPonteiros em CEstruturas de Dados e CExerccios1.2. Vetores em C0 Vetor Como um TDAUsando Vetores Unidimensionais,114679111218232527273032343637VII 6. VIII Estruturas de Dados Usando CImplementando Vetores UnidimensionaisVetores Como ParmetrosStrings de Caracteres em COperaes com Strings de CaracteresVetores BidimensionaisVetores MultidimensionaisExerccios1.3. Estruturas em CImplementando EstruturasUniesImplementao de UniesParmetros de EstruturaRepresentando Outras Estruturas de DadosNmeros RacionaisAlocao de Armazenamento e Escopo de VariveisExerccios2. A Pilha2.1. Definio e ExemplosOperaes PrimitivasUm ExemploA Pilha Como um Tipo de Dado AbstratoExerccios2.2. Representando Pilhas em CImplementando a Operao POPVerificando Condies ExcepcionaisImplementando a Operao PushExerccios2.3. Um Exemplo: Infixo, Posfixo e PrefixoDefinies Bsicas e ExemplosAvaliando uma Expresso PosfixaPrograma para Avaliar uma Expresso PosfixaLimitaes do ProgramaConvertendo uma Expresso da Forma Infixa para a PosfxalPrograma para Converter uma Expresso da Forma Infixa na Forma Posfixa .Exerccios39434445465053576265686973737783.86868891959697102105105109111111114116119120126129 7. Sumrio IX3. Recursividade3.1. Definies Recursivas e ProcessosA Funo FatorialMultiplicao de Nmeros NaturaisA Seqncia de FibonacciA Busca BinriaPropriedades das Definies ou Algoritmos RecursivosExerccios3.2. Recursividade em CFatorial em COs Nmeros de Fibonacci em CBusca Binria em CCadeias RecursivasDefinio Recursiva de Expresses AlgbricasExerccios3.3. Escrevendo Programas Recursivos0 Problema das Torres de HanoiConverso da Forma Prefixa para a Posfixa Usando RecursividadeExerccios3.4. Simulando a RecursividadeRetorno de uma FunoImplementando Funes RecursivasSimulao de FatorialAprimorando a Rotina SimuladaEliminando GotosSimulando as Torres de HanoiExerccios3.5. Eficincia da RecursividadeExerccios4. Filas e Listas4.1. A Fila e sua Representao SeqencialA Fila Como um Tipo de Dado AbstratoImplementao de Filas em C132132133136137138142143145145150152154155159162164171176180182184185190192195202204206207207209 8. X Estruturas de Dados Usando CA Operao InsertA Fila de PrioridadeImplementao em Vetor de uma Fila de PrioridadeExerccios4.2. Listas LigadasInserindo e Removendo Ns de uma ListaImplementao Ligada de PilhasAs Operaes Getnode e FreenodeImplementao Ligada de FilasListas Ligadas Como Estrutura de DadosExemplos de Operaes de ListaImplementao em Lista de Filas de PrioridadeNs de CabealhoExerccios4.3. Listas em CImplementao de Listas em Vetor ,Limitaes da Implementao em VetorAlocando e Liberando Variveis DinmicasListas Ligadas Usando Variveis DinmicasFilas Como Listas em CExemplos de Operaes de Listas em CListas No-Inteiras e No-HomogneasComparando a Implementao em Vetor e a Dinmica de ListasImplementando Ns de CabealhoExerccios ,4.4. Um Exemplo: Simulao Usando Listas Ligadas0 Processo de SimulaoEstruturas de Dados0 Programa de SimulaoExerccios4.5. Outras Estruturas de ListaListas CircularesA Pilha Como uma Lista CircularA Fila Como uma Lista CircularOperaes Primitivas Sobre Listas Circulares0 Problema de Josephus215216218220223225230231233235238241241244245245249250256258260262264265265268269271272276279279281282283285 9. Sumrio XINs de CabealhoSoma de Inteiros Positivos Longos Usando Listas CircularesListas Duplamente LigadasSoma de Inteiros Longos Usando Listas Duplamente LigadasExerccios5. rvores5.1. rvores BinriasOperaes Sobre rvores BinriasAplicaes de rvores BinriasExerccios5.2. Representaes de rvores BinriasRepresentao de Ns de rvores BinriasNs Internos e ExternosRepresentao Implcita em Vetores de rvores BinriasEscolhendo uma Representao de rvore BinriaPercursos de Arvores Binrias em Crvores Binrias EncadeadasPercurso Usando um Campo Fatherrvores Binrias HeterogneasExerccios5.3. Um Exemplo: o Algoritmo de Huffman0 Algoritmo de HuffmanUm Programa em CExerccios5.4. Representando Listas Como rvores BinriasLocalizando o Ksimo ElementoEliminando um ElementoImplementando Listas Representadas Por Arvores em CConstruindo uma Lista Representada Por rvoreRevisitando o Problema de JosephusExerccios5.5. rvores e Suas AplicaesRepresentaes de rvores em CPercurso de rvores287288291294300303303311312318320320324325330331335340343346350353355360361364366371374376377378381385 10. XII Estruturas de Dados Usando CExpresses Gerais Como rvoresAvaliando uma rvore de ExpressesConstruindo uma rvoreExerccios5.6. Um Exemplo: rvores de JogosExerccios6. Classificao6.1. Viso GlobalConsideraes Sobre a EficinciaNotao 0Eficincia da ClassificaoExerccios6.2. Classificaes Por TrocaClassificao Por BolhaQuicksortEficincia do QuicksortExerccios6.3. Classificao Por Seleo e Por rvoreClassificao de Seleo DiretaClassificaes por Arvore Binria ..HeapsortO Heap Como uma Fila de PrioridadeClassificao Usando um HeapO Procedimento HeapsortExerccios6.4. Classificaes Por InseroInsero SimplesClassificao de ShellClassificao por Clculo de EndereoExerccios ,6.5. Classificaes por Intercalao e de RaizO Algoritmo de Cook-KimClassificao de RazesExerccios387390393395398406.408408411415418421424424427436439441442444448449452455457459459462466469472476477482 11. Sumrio XIII7. Operao de Busca7.1 Tcnicas Bsicas de Pesquisa0 Dicionrio Como um Tipo de Dado AbstratoNotao AlgortmicaOperao de Busca SeqencialEficincia da Operao de Busca SeqencialReoordenando uma Lista para Obter a Eficincia Mxima de BuscaOperao de Busca Numa Tabela OrdenadaA Busca Seqencial IndexadaA Busca BinariaBusca por InterpolaoExerccios7.2. Busca em rvoresInsero Numa rvore de Busca BinariaEliminao Numa Arvore de Busca BinariaEficincia das Operaes de Arvore de Busca BinariaEficincia das Arvores de Busca Binaria No-Uniformesrvores de Busca timasrvores BalanceadasExerccios7.3. rvores de Busca Geralrvores de Busca MultidirecionaisPesquisando uma rvore MultidirecionalImplementando uma rvore MultidirecionalPercorrendo uma rvore MultidirecionalInsero Numa rvore de Busca Multidirecionalrvores-BAlgoritmos para a Insero na Arvore-BComputando Father e IndexEliminao em rvores de Busca MultidirecionaisEficincia das rvores de Busca MultidirecionaisAprimorando a Arvore-Brvores-Brvores de Busca DigitaisTries486486488490491493495497498501504506510513514517521523526535537537541542545548554563566571576580585587593 12. XIV Estruturas de Dados Usando CExerccios7.4 EspalhamentoSolucionando Colises de Espalhamento Com o Endereamento aBerto .Eliminando Itens de uma Tabela de espalhamentoEficincia dos Mtodos de RecomprovaoReordenamento da Tabela de EspalhamentoMtodo de BrentEspalhamento em rvore BinriaAperfeioamentos Com Memria AdicionalEspalhamento CombinadoEncadeamento SeparadoEspalhamento em Armazenamento ExternoO Mtodo SeparadorEspalhamento Dinmico e Espalhamento ExtensvelEspalhamento LinearSelecionando uma Funo de EspalhamentoFunes de Espalhamento PerfeitasClasses Universais de Funes de EspalhamentoExerccios8. Grafos e Suas Aplicaes .8.1. GrficosUma Aplicao de GrafosRepresentaes de Grafos em CFechamento TransitivoAlgoritmo de WarshallUm Algoritmo de Menor CaminhoExerccios8.2. Um Problema de FluxoMelhorando uma Funo de FluxoUm ExemploO Algoritmo e o ProgramaExerccios8.3. Representao Ligada de GrafosRevisitando o Algoritmo de Dijkstra593595.598603604607609612616620624628632633641649653659661.664664668670672676678681683686690692697699706 13. Sumrio XVOrganizando o Conjunto de Ns de GrafoUma Aplicao no Escalonamento0 Programa em CExerccios8.4. Percurso de Grafos e Florestas GeradorasMtodos de Percurso de Grafos .Florestas GeradorasGrafos No-Orientados e Seus PercursosPercurso em ProfundidadeAplicaes do Percurso em ProfundidadeEficincia do Percurso em ProfundidadePercurso em LarguraArvores Geradoras MnimasAlgoritmo de KruskalO Algoritmo da Fila de rvoresExerccios9. Gerenciamento de Armazenamento9.1. Listas GeraisOperaes que Modificam uma ListaExemplosA Representao em Lista Ligada de uma ListaRepresentao de ListasA Operao Crlist0 Uso de Cabealhos de ListasLiberando Ns de ListaListas Gerais em CLinguagens de Programao e ListasExerccios9.2. Gerenciamento Automtico de Listas0 Mtodo de Contagem de RefernciasColeta de LixoAlgoritmos para Coleta de LixoColeta e CompactaoVariaes da Coleta de Lixo708710715719722723728729733737740740742745746747750750753755757760763764766770773775777777784786794802 14. XVI Estruturas de Dados Usando CExerccios9.3. Gerenciamento da Memria DinmicaCompactao de Blocos de ArmazenamentoPrimeira Escolha, Melhor Escolha, Pior EscolhaAprimoramentos no Mtodo da Primeira EscolhaLiberando Blocos de Armazenamento0 Mtodo da Marca Limtrofe0 Sistema em TurmasOutros Sistemas em TurmaExercciosBibliografia e Refernciasndice Analtico804806808810818819822825834837841865 15. PrefcioMAKRONBooksEste texto foi elaborado para um curso de dois semestres sobre estruturasde dados e programao. Durante vrios anos, ministramos um curso sobreestruturas de dados para estudantes que passaram por um curso de umsemestre de programao com linguagens de alto nvel e por um curso de umsemestre de programao usando linguagem de montagem.Descobrimos que investimos muito tempo ensinando tcnicas deprogramao porque os estudantes ainda no possuam experincia suficien-teem programao nem conseguiam implementar estruturas abstratas porconta prpria. Os alunos mais brilhantes ocasionalmente percebiam o queestvamos fazendo. Os mais fracos nunca conseguiram. Baseados nessaexperincia, chegamos concluso de que um primeiro curso de estruturasde dados deveria ser ministrado paralelamente a um segundo curso sobreprogramao. Este livro representa o resultado dessa concluso.O texto apresenta conceitos abstratos, demonstra como esses concei-tosso teis para a soluo de problemas e, em seguida, mostra como asabstraes podem concretizar-se por meio do uso de uma linguagem deprogramao. nfase igual atribuda s verses abstrata e concreta de umconceito para que os estudantes aprendam o conceito propriamente dito, suaimplementao e sua aplicao. A linguagem usada neste texto C. Essalinguagem bem adequada a esse tipo de curso porque dispe das estruturasde controle necessrias para tornar os programas legveis, e permite queestruturas de dados bsicas, como as pilhas, as listas ligadas e as rvores,sejam implementadas de vrias maneiras. Esse aspecto possibilita aosXVII 16. XVIII Estruturas de Dados Usando Cestudantes acompanhar as opes e os compromissos que um programadorenfrenta numa situao real. C est tambm amplamente disponvel emvrios computadores diferentes e continua a crescer em popularidade. Se-gundoKernighan e Ritchie, C "uma linguagem agradvel, expressiva everstil".O nico pr-requisito para os estudantes que usarem este texto umcurso de um semestre em programao. Os estudantes que passaram por umcurso de programao usando linguagens como FORTRAN, Pascal ou PL/Ipodem utilizar este texto juntamente com um dos textos elementares sobreC listados na bibliografia. O Captulo 1 fornece tambm informaes neces-sriaspara que tais estudantes se acostumem com a linguagem C.O Captulo 1 uma introduo s estruturas de dados. A Seo 1.1apresenta o conceito de uma estrutura de dados abstrata e o conceito de umaimplementao. As Sees 1.2 e 1.3 introduzem os vetores e as estruturasem C. As implementaes dessas duas estruturas de dados, alm de suasaplicaes, so descritas tambm. O Captulo 2 discute as pilhas e suaimplementao em C. Como esta a primeira estrutura de dados novaapresentada, inclumos uma ampla anlise dos detalhes de sua implemen-tao.A Seo 2.3 traz as notaes posfixas, prefixas e infixas. O Captulo 3aborda a recursividade, suas aplicaes e sua implementao. O Captulo 4apresenta filas, filas de prioridade e listas ligadas e suas implementaes usandoum vetor de ns disponveis e o armazenamento dinmico. O Captulo 5 discuteas rvores e o Captulo 6 apresenta a notao O, alm de cobrir a classificao.O Captulo 7 discute a operao de busca interna e externa. O Captulo 8apresenta os grafos; e o Captulo 9 analisa o gerenciamento do armazenamento.No final do livro, inclumos uma ampla bibliografia com cada refe-rnciaclassificada pelo captulo ou seo a que se aplica.Um curso de um semestre de estruturas de dados consiste na Seo1.1, Captulos 2-7, sees 8.1 e 8.2, e parte da 8.4. Partes dos Captulos 3, 6,7 e 8 podem ser omitidas se o tempo for escasso.O texto adequado para o curso C82 e partes dos cursos C87 e C813do Curriculum 78 (Communications of the ACM, maro de 1979); cursos UC1e UC8 dos Programas de Graduao em Sistemas de Informao (Communi-cationsof the ACM, dezembro de 1973) e curso I1 do Curriculum 68(Communications of the ACM, maro de 1968). Em particular, o texto cobreem parte ou no todo os tpicos P1, P2, P3, P4, P5, S2, Dl, D2, D3 e D6 doCurriculum 78. 17. Prefcio XIXOs algoritmos so apresentados como intermedirios entre as des-criesem portugus e os programas em C. Estes foram escritos em estilo Cmisturado com comentrios em portugus. Os algoritmos permitem que oleitor se concentre no mtodo usado para solucionar um problema, sem sepreocupar com declaraes de variveis e peculiaridades da linguagem real.Ao transformar um algoritmo num programa, apresentamos essas questese destacamos os problemas que as acompanham.O padro de endentao usado para os programas em C e algoritmos uma verso livre do formato sugerido por Kernighan e Ritchie (The CProgramming Language, Prentice-Hall, 1978), que achamos bastante til.Adotamos tambm a conveno de indicar por meio de comentrios aconstruo sendo encerrada por cada ocorrncia de uma chave de fechamento(}). Juntamente com o padro de endentao, essa uma valiosa ferramentapara aprimorar a compreenso do programa. Distinguimos entre algoritmose programas usando o primeiro em itlico e o ltimo em romano.A maioria dos conceitos deste livro ilustrada por vrios exemplos.Alguns deles so tpicos importantes (isto , notao posfixa, aritmtica demltiplas palavras etc.) e podem ser tratados como tal. Outros ilustramdiferentes tcnicas de implementao (como o armazenamento seqencial dervores). O instrutor poder discutir quantos exemplos quiser. Os exemplospodem ser tambm passados para os estudantes como leitura adicional.Prevemos que um instrutor no conseguir discutir todos os exemplos comdetalhes suficientes durante um curso de um ou dois semestres. Achamos que,no estgio de desenvolvimento de um estudante para o qual este texto foielaborado, mais importante discutir vrios exemplos em detalhes do que umaampla variedade de tpicos superficialmente.Todos os algoritmos e programas deste livro foram testados e depu-rados.Gostaramos de agradecer a Miriam Binder e Irene LaClaustra porseu inestimvel apoio nessa tarefa. Sua dedicao ultrapassou a responsa-bilidadede ambas e suas sugestes foram sempre importantssimas. Evidente-mente,quaisquer erros remanescentes so de total responsabilidade dos autores.Os exerccios variam muito em termos de tipo e dificuldade. Algunsso exerccios de treinamento para assegurar a compreenso de tpicosapresentados no livro. Outros envolvem modificaes de tpicos e algoritmos.Outros ainda introduzem novos conceitos e so bastante desafiantes. Fre-qentemente,um grupo de exerccios sucessivos inclui o desenvolvimentocompleto de um novo tpico que pode ser usado como base para um projetoou como leitura adicional. O instrutor deve ter cuidado ao solicitar a resoluo 18. XX Estruturas de Dados Usando Cdos exerccios para que o grau de dificuldade seja adequado ao nvel dosestudantes. imperativo que os estudantes desenvolvam vrios projetos deprogramao (de cinco a doze, dependendo do nvel de dificuldade) por semestre.Procuramos usar a linguagem C, conforme especificado na primeiraedio do livro de K & R. No usamos nenhum recurso encontrado atualmen-teem vrios compiladores de computadores pessoais (por exemplo, o Micro-soft(R) C e o Turbo C (R), da Borland), embora alguns desses recursostenham sido includos no padro ANSI. Em particular, passamos ponteirospara estruturas como parmetros, mesmo que o novo padro permita passara estrutura em si. Kernighan e Ritchie comentam em sua segunda edioque mais eficiente passar um ponteiro quando a estrutura grande. Nousamos tambm nenhuma funo que retorne uma estrutura como resultado.Evidentemente, necessrio informar aos estudantes quaisquer idiossincra-siasdo compilador em questo que eles estejam usando. Inclumos tambmalgumas referncias a vrios compiladores C para computadores pessoais.Miriam Binder e Irene LaClaustra passaram horas digitando e corri-gindoo manuscrito original, e gerenciando uma grande equipe de estudantesque mencionamos a seguir. Sua cooperao e pacincia com a nossa mudanacontnua de idias sobre incluses e eliminaes so apreciadas sinceramente.Gostaramos de agradecer a Shaindel Zundel-Margulis, CynthiaRichman, Gittie Rosenfeld-Wertenteil, Mindy Rosman-Schreiber, NinaSilverman, Helene Turry e Devorah Sadowsky-Weinschneider por sua ines-timvelcolaborao.A equipe do City University Computer Center merece meno espe-cial.Eles foram muito teis auxiliando-nos no uso das excelentes instalaesdo Centro. A mesma coisa pode-se dizer da equipe do Brooklyn CollegeComputer Center.Gostaramos de agradecer aos editores e equipe da Prentice-Halle principalmente aos revisores por seus teis comentrios e sugestes.Finalmente, agradecemos a nossas esposas, Miriam Tenenbaum,Vivienne Langsam e Gail Augenstein, por seus conselhos e estmulos durantea longa e rdua tarefa de produzir um livro como este.Aaron TenenbaumYedidyah LangsamMoshe Augenstein 19. MAKRONBooksCaptulo 1Introduo s Estruturas de DadosUm computador uma mquina que manipula informaes. O estudo dacincia da computao inclui o exame da organizao, manipulao e utili-zaodestas informaes num computador. Conseqentemente, muitoimportante para um estudante da cincia da computao entender os con-ceitosde organizao e manipulao de informaes para continuar o estudodo campo.1.1 INFORMAES E SIGNIFICADOSe a cincia da computao fundamentalmente o estudo da informao, aprimeira pergunta que surge : o que significa a informao? Infelizmente,embora o conceito de informao seja a base do campo inteiro, essa perguntano pode ser respondida com exatido. Por um lado, o conceito de informaona cincia da computao semelhante aos conceitos de ponto, linha e plano,na geometria: todos eles so termos indefinidos sobre os quais podem serfeitas afirmaes, mas eles podem ser explicados em termos de conceitoselementares.1 20. 2 Estruturas de Dados Usando C Cap. 1Na geometria, possvel discutir sobre o tamanho de uma linhaindependentemente do fato de o conceito de uma linha ser ele mesmoindefinido. O tamanho de uma linha uma medida de quantidade. De modosemelhante, na cincia da computao, podemos avaliar quantidades deinformaes. A unidade bsica da informao o bit, cujo valor compreendeuma entre duas possibilidades mutuamente exclusivas. Por exemplo, se uminterruptor de luz pode estar em uma das duas posies, mas no em ambassimultaneamente, o fato de ele estar na posio de "ligado" ou na posio de"desligado" um bit de informao. Se um dispositivo pode estar em mais de doisestados possveis, o fato de ele estar em determinado estado representa mais deum bit de informao. Por exemplo, se um dial tem oito posies possveis, o fatode ele estar na posio 4 exclui sete outras possibilidades, enquanto o fato de uminterruptor estar ligado exclui somente outra possibilidade.Voc pode visualizar esse fenmeno sob outro prisma. Vamos suporque tivssemos chaves de duas alternativas, mas pudssemos usar quantasdelas precisssemos. Quantas chaves desse tipo seriam necessrias pararepresentar um dial com oito posies? Evidentemente, uma chave s poderepresentar duas posies (Figura 1.1.1a). Duas chaves podem representarquatro posies diferentes (Figura 1.1.1b) e so necessrias trs chaves pararepresentar oito posies diferentes (Figura 1.1.1c). Em geral, n chavespodem representar 2n possibilidades diferentes.Os dgitos binrios 0 e 1 so usados para representar os dois possveisestados de determinado bit (na realidade, a palavra "bit" uma contraodas palavras "binary digit"). Dados n bits, uma string de n ls e 0s usadapara representar seus valores. Por exemplo, a string 101011 representa seischaves, estando a primeira delas "ativada" (1), a segunda "desativada" (0),a terceira ativada, a quarta desativada, a quinta e a sexta ativadas.Verificamos que so suficientes trs bits para representar oitopossibilidades. As oito possveis configuraes desses trs bits (000, 001, 010,011, 100, 101, 110 e 111) podem ser usadas para representar os inteiros de0 a 7. Entretanto, no h nada nas definies desses bits que impliqueintrinsecamente que determinada definio representa determinado inteiro.Qualquer atribuio de valores inteiros s definies de bits vlida desdeque no sejam atribudos dois inteiros mesma definio de bits. Assim queocorrer uma atribuio desse tipo, determinada definio de bit poder serinterpretada com ambigidade como um inteiro especfico. Examinemosvrios mtodos amplamente usados para interpretar definies de bits comointeiros. 21. Cap. 1 Introduo s estruturas de dados 3Desligado DesligadoDesligadoLigado(c) Trs chaves (oito possibilidades).Figura 1.1.1Chave 1DesligadoLigado(a) Uma chave (duas possibilidades).Chave 1 Chave 2Desligado DesligadoDesligado LigadoLigado DesligadoDesligado Ligado(b) Duas chaves (quatro possibilidades).Chave 1 Chave 2 Chave 3Desligado Desligado DesligadoDesligado Desligado LigadoDesligadoDesligadoLigadoUgadoLigadoLigado LigadoLigadoDesligadoLigadoLigadoLigadoDesligadoUgado 22. 4 Estruturas de Dados Usando C Cap. 1INTEIROS BINRIOS E DECIMAISO mtodo mais amplamente usado para interpretar definies de bits comointeiros no-negativos o sistema de numerao binrio. Nesse sistema,cada posio de bit representa uma potncia de 2. A posio da extremadireita representa 2o que equivale a 1, a prxima posio esquerdarepresenta 21 que 2, a prxima posio de bit representa 22, que equivalea 4, e assim por diante. Um inteiro representado por uma soma de potnciasde 2. Uma string toda de Os representa o nmero 0. Se aparecer um 1 emdeterminada posio de bit, a potncia de 2 representada por essa posiode bit ser includa na soma; mas, se aparecer um 0, essa potncia de 2 noser includa na soma. Por exemplo, o grupo de bits 00100110 apresenta lsnas posies 1, 2 e 5 (contando da direita para a esquerda com a posio daextrema direita considerada posio 0). Sendo assim, 00100110 representao inteiro 21 + 22 + 25 = 2 + 4 + 32 = 38. Sob esse prisma, toda string de bitsde tamanho n representa um inteiro no-negativo nico, entre 0 e 2n-1, e todointeiro no-negativo entre 0 e 2a"1 pode ser representado por uma nicastring de bits de tamanho n.Existem dois mtodos amplamente usados para representar nme-rosbinrios negativos. No primeiro mtodo, chamado notao de comple-mentode um, um nmero negativo representado mudando cada bit emseu valor absoluto para a definio do bit oposto. Por exemplo, como 00100110representa 38, 11011001 usado para representar -38. Isso significa que obit da extrema esquerda de um nmero no mais usado para representaruma potncia de 2, mas reservado para o sinal do nmero. Uma string debits comeando com um 0 representa um nmero positivo, enquanto umastring de bits comeando com um 1 representa um nmero negativo. Emfuno de n bits, a faixa de nmeros que pode ser representada -2( n - l ) + 1(um 1 seguido por n - 1 zeros) a 2(n-1) - 1 (um 0 seguido por n - 1 uns).Observe que, com essa representao, existem duas representaes para onmero 0: um 0 "positivo" consistindo em todos os Os, e um zero "negativo"consistindo em todos os ls.O segundo mtodo que representa nmeros binrios negativos chamado notao de complemento de dois. Nessa notao, 1 somado representao de complemento de um de um nmero negativo. Por exemplo,como 11011001 representa -38 na notao de complemento um, 11011010 usado para representar -38 na notao de complemento de dois. Dados nbits, a faixa de nmeros que pode ser representada 2(n-1) (um 1 seguido por 23. Cap. 1 Introduo s estruturas de dados 5n - 1 zeros) a 2(n-1) -1 (um 0 seguido por n - 1 uns). Observe que -2(n-1) podeser representado em notao de complemento de dois, mas no em notaode complemento de um. Entretanto, seu valor absoluto, 2(n-1), no pode serrepresentado em ambas as notaes, usando n bits. Alm disso, observe queexiste apenas uma representao para o nmero 0 usando n bits na notaode complemento de dois. Para constatar isso, considere o 0 usando oito bits:00000000. O complemento de um 11111111, que o 0 negativo nessanotao. Somar 1 para produzir a forma de complemento de 2 resulta em100000000, que tem nove bits. Como somente oito bits so permitidos, o bitda extrema esquerda (ou a "sobra") descartado, deixando 00000000 comomenos 0.O sistema de numerao binrio definitivamente no o nicomtodo pelo qual os bits podem ser usados para representar inteiros. Porexemplo, uma string de bits pode ser usada para representar inteiros nosistema numrico decimal, da seguinte forma: quatro bits podem ser usadospara representar um dgito decimal entre 0 e 9 na notao binria descritaanteriormente. Uma string de bits de qualquer tamanho pode ser divididaem conjuntos consecutivos de quatro bits, com cada conjunto representandoum dgito decimal. Dessa forma, a string representa o nmero formado poresses dgitos decimais na notao decimal convencional. Por exemplo, nessesistema, a string de bits 00100110 separada em duas strings de quatro bitscada: 0010 e 0110. A primeira string representa o dgito decimal 2 e asegunda, o dgito decimal 6, de modo que a string inteira representa o inteiro26. Essa representao chamada decimal codificado em binrio.Uma caracterstica importante da representao de decimal codifi-cadoem binrio de inteiros no-negativos que nem todas as strings de bitsso representaes vlidas de um inteiro decimal. Quatro bits podem serusados para representar um dentre 16 possibilidades diferentes, uma vezque existem 16 estados possveis para um conjunto de quatro bits. Entretan-to,na representao de inteiro decimal codificado em binrio, somente dezdessas 16 possibilidades so usadas. Ou seja, cdigos como 1010 e 1100, cujosvalores binrios so 10 ou acima, no so vlidos em nmeros decimaiscodificados em binrio. 24. 6 Estruturas de Dados Usando C Cap. 1NMEROS REAISO mtodo comum usado pelos computadores para representar nmeros reais a notao de ponto flutuante. Existem vrios tipos de notao de pontoflutuante e cada um tem caractersticas prprias. O conceito-chave que umnmero real representado por um nmero, chamado mantissa, vezes umabase elevada a uma potncia de inteiro, chamada expoente. Em geral, abase fixa, e a mantissa e o expoente variam de modo a representar nmerosreais diferentes. Por exemplo, se a base for fixada com 10, o nmero 387,53poderia ser representado como 38753 x 10-2. (Lembre-se de que 10-2 0,01.)A mantissa 38753 e o expoente -2. Outras possveis representaes so0,38753 x 103 e 387,53 x 10. Optamos pela representao na qual a mantissa um inteiro sem Os finais.Na notao de ponto flutuante que descrevemos (que no necessa-riamenteimplementada em nenhuma mquina particular exatamente comodescrito), um nmero real representado por uma string de 32 bits consis-tindoem uma mantissa de 24 bits seguida por um expoente de 8 bits. A base fixada em 10. Tanto a mantissa como o expoente so inteiros binrios decomplemento de dois. Por exemplo, a representao binria de 24 bits de38753 000000001001011101100001, e a representao binria de comple-mentode dois de oito bits de -2 11111110; a representao de 387,53 00000000100101110110000111111110. Voc encontrar a seguir outros n-merosreais e suas representaes de ponto flutuante:0 00000000000000000000000000000000100 000000000000000000000001000000100,5 000000000000000000000101111111110,000005 0000000000000000000001011111101012.000 00000000000000000000110000000011-387,53 11111111011010001001111111111110-12.000 11111111111111111111010000000011 25. Cap. 1 Introduo s estruturas de dados 7A vantagem da notao de ponto flutuante que ela pode ser usadapara representar nmeros com valores absolutos muito grandes ou muitopequenos. Por exemplo, na notao apresentada anteriormente, o maiornmero que pode ser representado (223-1) x 10127, que, na realidade, umnmero muito grande. O menor nmero positivo que pode ser representado 10-128, que muito pequeno. O fator limitante na exatido com a qual osnmeros podem ser representados em determinada mquina o nmero dedgitos binrios significativos na mantissa. Nem todo nmero entre o maiore o menor pode ser representado. Nossa representao s permite 23 bitssignificativos. Dessa forma, um nmero como 10 milhes e 1, que exige 24dgitos binrios na mantissa, precisaria ser aproximado para 10 milhes (1x 107), que s exige um dgito significativo.STRINGS DE CARACTERESComo sabemos, nem sempre a informao interpretada em termos num-ricos.Itens como nomes, ttulos de cargos e endereos precisam tambm serrepresentados de alguma maneira dentro de um computador. Para permitira representao desses objetos no-numricos, necessrio outro mtodo deinterpretao de strings de bits. Geralmente, tais informaes so represen-tadasna forma de strings de caracteres. Por exemplo, em alguns computa-dores,os oito bits 00100110 so usados para representar o caractere '&'. Umpadro de oito bits diferente usado para representar o caractere 'A', outropara representar o 'B', outro ainda para representar o 'C', e mais um paracada caractere que tenha uma representao em determinada mquina. Umamquina russa usa padres de bits para representar caracteres russos,enquanto uma mquina israelense usa padres de bits para representarcaracteres do hebraico. (Na realidade, os caracteres usados ficam transpa-rentespara a mquina; o conjunto de caracteres pode ser alterado usando-seuma cadeia de impresso diferente na impressora.)Se so usados oito bits para representar um caractere, podem serrepresentados at 256 caracteres diferentes, uma vez que existem 256padres de bits diferentes. Se a string 11000000 usada para representar ocaractere 'A' e 11000001 usada para representar o caractere 'B', a stringde caracteres 'AB' seria representada pela string de bits 1100000011000001. 26. 8 Estruturas de Dados Usando C Cap. 1Em geral, uma string de caracteres (STR) representada pela concatenaodas strings de bits que representam os caracteres individuais da string.Como acontece no caso dos inteiros, no h nada em determinadastring de bits que a torne intrinsecamente adequada para representar umcaractere especfico. A atribuio de strings de bits a caracteres pode sertotalmente aleatria, mas precisa ser adotada com coerncia. possvel quealguma regra conveniente seja usada ao atribuir strings de bits a caracteres.Por exemplo, duas strings de bits podem ser atribudas a duas letras, demodo que uma delas com o valor binrio menor seja atribuda letra quevem antes no alfabeto. Entretanto, essa regra apenas uma convenincia;ela no ditada por nenhuma relao intrnseca entre caracteres e stringsde bits. Na verdade, os prprios computadores variam o nmero de bitsusados para representar um caractere. Alguns computadores usam sete bits(e, portanto, s permitem at 128 caracteres possveis), alguns usam oito (at256 caracteres) e outros usam dez (at 1.024 caracteres possveis). O nmerode bits necessrio para representar um caractere em determinado computa-dor chamado tamanho do byte e um grupo de bits com esse nmero chamado byte.Observe que usar oito bits para representar um caractere significaque podem ser representados 256 caracteres. No se encontra freqentemen-teum computador que use tantos caracteres diferentes (embora se concebaque um computador inclua letras maisculas e minsculas, caracteresespeciais, itlicos, negritos e outros tipos de caracteres), de modo que muitoscdigos de oito bits no so usados para representar caracteres.Sendo assim, verificamos que a prpria informao no tem signifi-cado.Qualquer significado por ser atribudo a determinado padro de bits,desde que seja feito com coerncia. a interpretao de um padro de bitsque d significado. Por exemplo, a string de bits 00100110 pode ser inter-pretadacomo o nmero 38 (binrio), o nmero 26 (decimal codificado embinrio) ou o caractere '&'. Um mtodo de interpretar um padro de bits freqentemente chamado tipo de dado. Apresentamos vrios tipos de dados:inteiros binrios, inteiros no-negativos decimais codificados em binrios,nmeros reais e strings de caracteres. Da surgem estas perguntas: comodeterminar que tipos de dados estejam disponveis para interpretar padresde bits e que tipos de dados possam ser usados para interpretar determinadopadro de bits? 27. Cap. 1 Introduo s estruturas de dados 9HARDWARE & SOFTWAREA memria (conhecida tambm como armazenamento ou ncleo) de umcomputador apenas um grupo de bits (chaves). Em qualquer momento daoperao de um computador, determinado bit na memria 0 ou 1 (desati-vadoou ativado). A definio de um bit chamada seu valor ou seucontedo.Os bits na memria de um computador so agrupados em unidadesmaiores, como bytes. Em alguns computadores, vrios bytes so agrupadosem unidades chamadas palavras. Cada unidade desse tipo (byte ou palavra,dependendo da mquina) recebe a atribuio de um endereo, isto , umnome que identifica determinada unidade entre todas as unidades namemria. Em geral, esse endereo numrico, de modo que podemos falardo byte 746 ou da palavra 937. Um endereo freqentemente chamadoposio, e o contedo de uma posio so os valores dos bits que formam aunidade nessa posio.Todo computador tem um conjunto de tipos de dados "nativos". Issosignifica que ele construdo com um mecanismo para manipular padresde bits coerentes com os objetos que eles representam. Por exemplo, vamossupor que um computador contenha uma instruo para somar dois inteirosbinrios e introduzir sua soma em determinada posio na memria parauso posterior. Sendo assim, deve existir um mecanismo incorporado nocomputador para:1. extrair os padres de bits dos operandos de duas posies deter-minadas;2. produzir um terceiro padro de bits representando o inteirobinrio que seja a soma dos dois inteiros binrios representadospelos dois operandos; e3. armazenar o padro de bits resultante em determinada posio.O computador "sabe" interpretar os padres de bits nas posiesespecficas como inteiros binrios porque o hardware que executa a instruofoi projetado para fazer isso. Essa operao parecida com uma lmpadaque "sabe" que est acesa quando o interruptor est em determinada posio. 28. 10 Estruturas de Dados Usando C Cap. 1Se a mesma mquina tiver tambm uma instruo para somar doisnmeros reais, dever existir um mecanismo embutido separado para inter-pretaroperandos como nmeros reais. So necessrias duas instruesdistintas para as duas operaes, e cada instruo carrega em si mesma umaidentificao implcita dos tipos de seus operandos, alm de suas posiesexplcitas. Portanto, cabe ao programador saber que tipo de dado est contidoem cada posio usada, e escolher entre usar uma instruo de soma deinteiros ou reais para obter a soma de dois nmeros.Uma linguagem de programao de alto nvel ajuda consideravel-mentenessa tarefa. Por exemplo, se um programador C declarar:int x, y;float a, b;ser reservado espao em quatro posies para quatro nmeros diferentes.Essas quatro posies podem ser referenciadas pelos identificadores x, y,a e b. Um identificador usado no lugar de um endereo numrico para citardeterminada posio de memria porque conveniente para o programador.O contedo das posies reservadas para x e y ser interpretado comointeiros, enquanto o contedo de a e 6 ser interpretado como nmeros deponto flutuante. O compilador responsvel pela converso de programas Cem linguagem de mquina traduzir o "+" contido na instruox = x + y;em soma de inteiros, e traduzir o "+" contido na instruoa = a + b;em soma de pontos flutuantes. Na verdade, um operador como o "+" um operadorgenrico porque tem vrios significados diferentes dependo de seu contexto. Ocompilador evita a necessidade de o programador especificar o tipo de soma quedeve ser efetuada, examinando o contexto e usando a verso adequada. importante reconhecer o papel-chave desempenhado pelas decla-raesnuma linguagem de alto nvel. por meio das declaraes que oprogramador especifica como o contedo da memria do computador deve serinterpretado pelo programa. Ao fazer isso, uma declarao determina aquantidade de memria necessria para certa entidade, como o contedodessa memria deve ser interpretado, e outros detalhes fundamentais. Asdeclaraes especificam tambm para o computador o significado dos smbo-losdas operaes que sero posteriormente usados. 29. Cap. 1 Introduo s estruturas de dados 11O CONCEITO DE IMPLEMENTAOAt agora, discutimos os tipos de dados como um mtodo de interpretaodo contedo da memria de um computador. O conjunto de tipos de dadosnativos que um computador pode suportar determinado pelas funesincorporadas em seu hardware. Entretanto, podemos visualizar o conceitode "tipo de dado" sob uma perspectiva totalmente diferente; no em termosdo que um computador pode fazer, mas em funo do que o usurio querfazer. Por exemplo, se algum quiser obter a soma de dois inteiros, esseusurio no se importar muito com o mecanismo detalhado pelo qual essasoma ser obtida. O usurio est interessado em manipular o conceitomatemtico de "inteiro", no em manipular bits do hardware. O hardwaredo computador pode ser usado para representar um inteiro e s ser tilpara esse propsito se a representao tiver sucesso.Quando o conceito de "tipo de dado" dissociado dos recursos dohardware do computador, um nmero ilimitado de tipos de dados pode serconsiderado. Um tipo de dado um conceito abstrato, definido por umconjunto de propriedades lgicas. Assim que um tipo de dado abstrato definido e as operaes vlidas envolvendo esse tipo so especificadas,podemos implementar esse tipo de dado (ou uma aproximao). Umaimplementao pode ser uma implementao de hardware, na qual ocircuito para efetuar as operaes necessrias elaborado e construdo comoparte de um computador; ou pode ser uma implementao de software,na qual um programa consistindo em instrues de hardware j existentes criado para interpretar strings de bits na forma desejada e efetuar asoperaes necessrias. Dessa maneira, a implementao de software incluiuma especificao de como um objeto do novo tipo de dado representadopor objetos dos tipos de dados j existentes, alm de uma especificao decomo esse objeto ser manipulado em conformidade com as operaes defi-nidaspara ele. No restante deste livro, o termo "implementao" ser usadono sentido de "implementao de software". 30. 12 Estruturas de Dados Usando C Cap. 1UM EXEMPLOIlustraremos esses conceitos com um exemplo. Vamos supor que o hardwarede um computador contenha uma instruo:MOVE (origem, dest, compr)que copia uma string de caracteres de bytes com o tamanho representadopor compr a partir de um endereo especificado por origem para um endereoespecificado por dest. (Apresentamos instrues do hardware com letrasmaisculas. O tamanho deve ser especificado por um inteiro e, por essa razo,ns o indicamos com letras minsculas, origem e dest podem ser especificadospor identificadores que representam posies de armazenamento.) Um exem-plodessa instruo MOVE(a,b,3), que copia os trs bytes comeando naposio a para os trs bytes comeando na posio 6.Observe os papis distintos desempenhados pelos identificadores ae b nessa operao. O primeiro operando da instruo MOVE o contedoda posio especificada pelo identificador a. O segundo operando, entretanto,no o contedo da posio b, uma vez que esse contedo irrelevante paraa execuo da instruo. Em substituio, a prpria posio o operandoporque ela especifica o destino da string de caracteres. Embora um identifi-cadorsempre represente uma posio, comum o uso de um identificadorcomo referncia ao contedo dessa posio. Sempre ficar evidente pelocontexto se um identificador est referenciando uma posio ou seu contedo.O identificador que aparece como primeiro operando de uma instruoMOVE refere-se ao contedo de memria, enquanto o identificador queaparece como segundo operando indica uma posio.Alm disso, partimos da premissa de que o hardware do computadorcontm as usuais instrues aritmticas e de desvio, que indicamos usandoa notao ao estilo C. Por exemplo, a instruo:z = x + y;interpreta o contedo dos bytes nas posies x e y como inteiros binrios,soma-os e insere a representao binria de sua soma no byte na posio z.(No operamos sobre inteiros maiores que um byte e ignoramos a possibilidadede sobrecarga.) Nesse caso, mais uma vez x ey so usados como referncias acontedos de memria, enquanto z usado como referncia a uma posio dememria, mas a interpretao correta evidenciada pelo contexto. 31. Cap. 1 Introduo s estruturas de dados 13Ocasionalmente, necessrio acrescentar uma quantidade numendereo para obter outro endereo. Por exemplo, se a uma posio namemria, possvel referenciar a posio quatro bytes frente de a. Nopodemos referir-nos a essa posio como a + 4, uma vez que essa notao reservada ao contedo inteiro da posio a + 4. Sendo assim, introduzimosa notao a[4] como uma referncia a essa posio. Apresentamos tambma notao a[x] para referenciar o endereo dado pela soma do contedo dosinteiros binrios do byte em x com o endereo a.A instruo MOVE exige que o programador especifique o tamanhoda string a ser copiada. Dessa forma, seu operador uma string de caracteresde tamanho fixo (isto , o tamanho da string deve ser conhecido). Uma stringde tamanho fixo e um inteiro binrio com tamanho em bytes podem serconsiderados tipos de dados nativos dessa mquina particular.Vamos supor que precisemos implementar strings de caracteres detamanhos variveis nessa mquina. Ou seja, permitiremos que os programa-doresusem uma instruo:MOVEVAR(origem, dest)para deslocar uma string de caracteres da posio especificada por origempara a posio representada por dest, sem precisar determinar qualquertamanho.Para implementar esse novo tipo de dado, devemos primeiro deter-minarcomo ele ser representado na memria da mquina e, em seguida,indicar como essa representao ser manipulada. Evidentemente, neces-srioconhecer a quantidade de bytes que deve ser deslocada para executaressa instruo. Como a operao MOVEVAR no especifica esse nmero, eleprecisa estar contido dentro da representao da prpria string de caracteres.Uma string de caracteres de tamanho varivel, com o tamanho l, pode serrepresentada por um conjunto contguo de / + 1 bytes (l < 256). O primeirobyte contm a representao binria do tamanho / e os bytes restantescontm a representao dos caracteres na string. As representaes de trsstrings como essas aparecem ilustradas na Figura 1.1.2. (Observe que osdgitos 5 e 9 nessa figura no substituem os padres de bits que representamos caracteres '5' e '9', mas os padres 00000101 e 00001001 [presumindo-seoito bits para um byte], que representam os inteiros cinco e nove. De modosemelhante, o 14 na Figura 1.1.2c substitui o padro de bits 00001110. Notetambm que esta representao muito diferente do modo como as stringsde caracteres so realmente implementadas em C.) 32. 14 Estruturas de Dados Usando C Cap. 1O programa para implementar a operao de MOVEVAR pode serescrito como segue (i uma posio de memria auxiliar):MOVE(origem, d e s t , 1 ) ;f o r ( i = l ; i < d e s t ; i++)MOVE(origem[i], d e s t [ i ] , 1 ) ;De maneira semelhante, podemos implementar uma operaoCONCATVAR(cl, c2, c3) para concatenar duas strings de caracteres detamanho varivel nas posies cl e c2, e colocar o resultado em c3. A Figura1.1.2c ilustra a concatenao das duas strings das Figuras 1.1.2a e b:(a)(b)(c)Figura 1.1.2 Strings de caracteres de tamanho varivel./* move o comprimento */z = c l + c 2 ;MOVE(z, c 3 , 1 ) ;/* move a primeira string */for (i = 1; i info(p); p = next(p))q = P;/* neste ponto, um noh contendo x deve ser inserido */if (g == null) /* insere x no inicio da lista */push(list, x);elseinsafter(q, x);Essa uma operao muito comum e ser indicada por place(list, x).Examinemos a eficincia da operao place. Quantos ns so aces-sadosem mdia, ao inserir um novo elemento numa lista ordenada? Vamossupor que uma lista contenha n ns. Assim, x pode ser colocado em uma dasn + 1 posies, isto , ele pode ser considerado menor que o primeiro elemento 258. 240 Estruturas de Dados Usando C Cap. 4da lista, entre o primeiro e o segundo, ... entre o elemento (n - 1) e o ensimoelemento, e pode ser maior que o ensimo elemento. Se x for menor que oprimeiro, place s acessar o primeiro n da lista (alm do novo n contendox); isto , ela determinar imediatamente que x < info{list) e inserir um ncontendo x, usando push. Se x estiver entre o elemento k e o elemento (k +1), place acessar os primeiros k ns; somente aps considerar x menor queo contedo do n (k + 1), x ser inserido usando insafter. Se x for maior queo ensimo elemento, todos os n ns sero acessados.Agora, suponha ser igualmente provvel que x seja inserido emqualquer uma das n + 1 possveis posies. (Se isso for verdadeiro, dizemosque a insero aleatria.) Assim, a probabilidade de inserir em qualquerposio determinada l/(n + 1). Se o elemento for inserido entre a posiok e a posio (k + 1), o nmero de acessos ser k + 1. Se o elemento for inseridodepois do ensimo elemento, o nmero de acessos ser n. O nmero mdiode ns acessados, A, equivale soma, sobre todas as possveis posies deinsero, dos produtos da probabilidade de inserir numa determinada posi-oe o nmero de acessos necessrios para inserir um elemento nessaposio. Sendo assim:Agora, 1 + 2 + ... + n = n * (n + l)/2. (Isso pode ser facilmenteverificado por induo matemtica.) Portanto:Quando n grande, n/(n + 1) fica muito prximo de 1, de modo que A aproximadamente n/2 + 1 ou (n + 2)/2. Para n grande, A fica suficientementeprximo de n/2 para podermos afirmar com freqncia que a operao deinsero aleatria de um elemento numa lista ordenada requer aproximada-menten/2 acessos de ns, em mdia.ou 259. Cap. 4 Filas e listas 241IMPLEMENTAO EM LISTA DE FILAS DE PRIORIDADEUma lista ordenada pode ser usada para representar uma fila de prioridade.Para uma fila de prioridade ascendente, a insero (pqinsert) implementadapela operao place, que mantm a lista ordenada, e a eliminao do elementomenor (pqmindelete) implementada pela operao pop, que remove o primeiroelemento da lista. Uma fila de prioridade descendente pode ser implementadamantendo-se a lista em ordem descendente, em vez de ascendente, e usandoremove para implementar pqmaxdelete. Uma fila de prioridade implementadacomo uma lista ligada ordenada requer o exame de uma mdia de aproxima-damenten/2 ns para insero, mas apenas um n para eliminao.Uma lista desordenada pode ser tambm usada como uma fila deprioridade. Essa lista requer o exame de somente um n para a insero(implementando pqinsert usando push ou insert), mas exige sempre o examede n elementos para a eliminao (atravessa a lista inteira para encontraro mnimo ou mximo e, em seguida, elimina esse n). Sendo assim, uma listaordenada um pouco mais eficiente do que uma lista desordenada aoimplementar uma fila de prioridade.A vantagem de uma lista sobre um vetor para implementar uma filade prioridade reside no fato de que no necessrio nenhum deslocamentode elementos ou intervalos numa lista. Um item pode ser inserido numa listasem deslocar nenhum dos outros itens, enquanto isso impossvel num vetor,a menos que um espao adicional fique vazio. Examinaremos outras imple-mentaesmais eficientes da fila de prioridade nas Sees 6.3 e 7.3.NS DE CABEALHOOcasionalmente, desejvel manter um n adicional no incio de uma lista.Esse n no representa um item na lista e chamado n de cabealho oucabealho de lista. A parte info desse n de cabealho poderia ficar semuso, conforme ilustrado na Figura 4.2.6a. Mais freqentemente, a parte infodeste n poderia ser usada para manter informaes globais sobre a listainteira. A Figura 4.2.6b ilustra uma lista na qual a parte info do n decabealho contm o nmero de ns (no incluindo o cabealho) na lista. Nessaestrutura de dados so necessrias mais etapas para incluir ou eliminar um 260. 242 Estruturas de Dados Usando C Cap. 4item da lista porque a contagem no n de cabealho precisa ser acertada.Entretanto, o nmero de itens na lista pode ser obtido diretamente a partirdo n de cabealho, sem atravessar a lista inteira.Figura 4.2.6 Listas com ns de cabealho.(a)(b)(c)(d)(e) 261. Cap. 4 Filas e listas 243Outro exemplo do uso de ns de cabealho o seguinte. Suponha queuma fbrica monte mquinas a partir de unidades menores. Uma determi-nadamquina (nmero de inventrio A746) poderia ser formada por umavariedade de partes diferentes (nmeros 5841, K321, A087, J492, G593).Essa montagem poderia ser representada por uma lista, como a apresentadana Figura 4.2.6c, em que cada item representa um componente e o n decabealho representa a montagem inteira.A lista vazia no seria mais representada por um ponteiro nulo, maspor uma lista com um nico n de cabealho, como na Figura 4.2.6d.Evidentemente, os algoritmos para operaes, como empty, push,pop, inseri e remove precisam ser reescritos de modo a considerar a presenade um n de cabealho. A maioria das rotinas fica um pouco mais complexa,mas algumas, como insert, tornam-se mais simples, uma vez que um ponteirode lista externa nunca nulo. Deixaremos a readaptao das rotinas comoexerccio para o leitor. As rotinas insafter e delafter no precisam seralteradas. Na realidade, quando um n de cabealho usado, insafter edelafter podem ser utilizadas em substituio a push e pop porque o primeiroitem nesta lista aparece no n seguinte ao n de cabealho, em vez de noprimeiro n na lista.Se a parte info de um n pode conter um ponteiro, surgem possibi-lidadesadicionais para o uso de um n de cabealho. Por exemplo, a parteinfo de um cabealho de lista poderia conter um ponteiro para o ltimo nalista, como na Figura 4.2.6e. Essa implementao simplifica a representaode uma fila. At agora, foram necessrios dois ponteiros externos, front erear, para uma lista representar uma fila. Entretanto, agora s necessrioum nico ponteiro externo, q, para o n de cabealho da lista, next(q) apontapara o incio da fila, e info(q) para seu final.Outra possibilidade para o uso da parte info de um cabealho de lista como um ponteiro para um n "atual" na lista durante um processo depercurso. Isso eliminaria a necessidade de um ponteiro externo durante opercurso. 262. 244 Estruturas de Dados Usando C Cap. 4EXERCCIOS4.2.1. Escreva um conjunto de rotinas para implementar vrias pilhas e filasdentro de um nico vetor.4.2.2. Quais as vantagens e desvantagens de representar um grupo de itenscomo um vetor versus uma lista ligada linear?4.2.3. Escreva um algoritmo para executar cada uma das seguintes operaes:a. Incluir um elemento no final de uma lista.b. Concatenar duas listas.c. Liberar todos os ns numa lista.d. Inverter uma lista de modo que o ltimo elemento se torne oprimeiro, e assim por diante.e. Eliminar o ltimo elemento de uma lista.f. Eliminar o ensimo elemento de uma lista.g. Combinar duas listas ordenadas numa nica lista ordenada.h. Formar uma lista contendo a unio dos elementos de duas listas.i. Formar uma lista contendo a interseco dos elementos de duaslistas.j. Inserir um elemento depois do ensimo elemento de uma lista.k. Eliminar cada segundo elemento de uma lista.I. Colocar os elementos de uma lista em ordem ascendente.m. Retornar a soma dos inteiros numa lista.n. Retornar o nmero de elementos numa lista.o. Deslocar node(p) n posies frente numa lista.p. Criar uma segunda cpia de uma lista. 263. Cap. 4 Filas e listas 2454.2.4. Escreva algoritmos para executar cada uma das operaes do exerccioanterior sobre um grupo de elementos em posies contguas de umvetor.4.2.5. Qual o nmero mdio de ns acessados ao procurar determinadoelemento numa lista desordenada? E numa lista ordenada? E numvetor desordenado? E num vetor ordenado?4.2.6. Escreva algoritmos para pqinsert e pqmindelete para uma fila deprioridade ascendente implementada como uma lista ordenada e comouma lista desordenada.4.2.7. Escreva algoritmos para executar cada uma das operaes do Exerccio4.2.3, pressupondo que cada lista contenha um n de cabealho com onmero de elementos na lista.4.2.8. Escreva um algoritmo que retorne um ponteiro para um n contendoo elemento x numa lista com um n de cabealho. O campo info docabealho dever conter o ponteiro que atravessa a lista.4.3. LISTAS EM CIMPLEMENTAO DE LISTAS EM VETORComo as listas lineares podem ser representadas em C? Como uma lista apenas um conjunto de ns, um vetor de ns uma idia imediata. Entre-tanto,os ns no podem ser ordenados pelos ndices do vetor; cada um deveconter em si mesmo um ponteiro para seu sucessor. Sendo assim, um grupode 500 ns poderia ser declarado como um vetor node, como segue:#define NUMNODES 500struct nodetype {int info, next;};struct nodetype node[NUMNODES]; 264. 246 Estruturas de Dados Usando C Cap. 4Nesse esquema, um ponteiro para um n representado por umndice do vetor. Ou seja, um ponteiro um inteiro entre 0 e NUMNODES -1, que referencia determinado elemento do vetor node. O ponteiro nulo representado pelo inteiro -1. Nessa implementao, a expresso C node[p] usada para referenciar node(p), info(p) referenciada por node[p].info enext(p) referenciada por nodep.next. null representado por -1.Por exemplo, suponha que a varivel list represente um ponteiropara uma lista. Se list tiver o valor 7, node[7] ser o primeiro n na lista enode[7].info ser o primeiro item de dado na lista. O segundo n da lista serdado por node[7].next. Suponha que node[7].next seja igual a 385. Assim,node[385].info ser o segundo item de dado na lista e node[385].next apontarpara o terceiro n.Os ns de uma lista podem ser distribudos pelo vetor node emqualquer ordem arbitrria. Cada n carrega dentro de si mesmo a posiode seu sucessor at o ltimo n na lista, cujo campo next contm -1, que oponteiro nulo. No existe relao entre o contedo de um n e o ponteirovoltado para ele. O ponteiro p para um n especifica apenas qual elementodo vetor node est sendo referenciado; node[p].info que representa ainformao contida dentro desse n.A Figura 4.3.1 ilustra uma parte do vetor node que contm quatrolistas ligadas. A lista list1 comea em node[16] e contm os inteiros 3, 7, 14,6, 5, 37, 12. Os ns que contm esses inteiros em seus campos info estoespalhados pelo vetor. O campo next de cada n contm o ndice dentro dovetor do n contendo o prximo elemento da lista. O ltimo n na lista node[23], que contm o inteiro 12 em seu campo info e o ponteiro nulo (-1)em seu campo next, para indicar que ele o ltimo na lista.De modo semelhante, list2 comea em node[4] e contm os inteiros17 e 23, list3 comea em node[ll] e contm os inteiros 31, 19 e 32, e listAcomea em node[3] e contm os inteiros 1, 18, 13, 11, 4 e 15. As variveislistl, list2, list3 e list4 so inteiros representando ponteiros externos paraas quatro listas. Dessa forma, o fato de que a varivel list2 tem o valor 4representa o fato de que a lista para a qual ela aponta comea em node[4].Inicialmente, todos os ns esto sem uso porque nenhuma lista foiformada. Portanto, todos eles devem ser colocados na lista de ns livres. Sea varivel global avail usada para apontar para essa lista, podemosorganizar de incio essa lista como segue: 265. Cap. 4 Filas e listas 247lista 4lista 2lista 3lista 1012= 3= 45678910= 1112131415= 1617181920212223242526info next26 -111 95 151 2417 013 1191814 124 2131 76 2373232032 -1715_12188-1-15Figura 4.3.1 Um vetor de ns contendo quatro listas ligadas.avail = 0;for (i = 0; i < NUMNODES-1; i++)node[i].next = i + 1;node[NUMNODES-1].next = - 1 ;Os 500 ns so associados inicialmente em sua ordem natural, demodo que node[i] aponta para node[i + 1]. node[0] o primeiro n na listadisponvel, node[l] o segundo e assim por diante. node[499] o ltimo nna lista, uma vez que node[499].next igual a -1. No existe outra razo, ano ser a convenincia, para ordenar inicialmente os ns dessa maneira.Poderamos apenas ter definido node[0].next com 499, node[499].next com 1,node[l].next com 498 e assim por diante, at que node[249].next fosse definidocom 250 e node[250].next com -1. A questo importante que a ordenao explcita dentro dos prprios ns e no causada por outra estrutura bsica. 266. 248 Estruturas de Dados Usando C Cap. 4Para as funes restantes nesta seo, presumiremos que as vari-veisnode e avail so globais e podem, portanto, ser usadas por quaisquerrotinas.Quando um n necessrio para uso numa determinada lista, ele obtido da lista de ns disponveis. De modo semelhante, quando um n no mais necessrio, ele retorna a essa lista. Estas duas operaes so implemen-tadaspelas rotinas em C, getnode e freenode. getnode uma funo que removeum n da lista de ns disponveis e retorna um ponteiro para ele.getnode(){int p;if (avail == -1) {printf("estouron");exit(l);}p = avail;avail = node[avail].next;return(p);} /* fim getnode */Se avail for igual a -1 quando essa funo for chamada, no existiro nsdisponveis. Isso significa que as estruturas de listas de um determinadoprograma excederam o espao disponvel.A funo freenode aceita um ponteiro para um n e retorna esse npara a lista livre:freenode(p)int p;{node[p].next = avail;avail = p;return;} /* fim freenode */As operaes primitivas de listas so verses simples em C dos algoritmoscorrespondentes. A rotina insafter aceita um ponteiro p para um n e umitem x como parmetros. Primeiro, ela assegura que p no nulo e, emseguida, insere x no n seguinte ao apontado por p:insafter(p, x)int p, x;{ 267. Cap. 4 Filas e listas 249int q;if (p == -1) {printf("insercao nulan");return;}q = getnode();node[q].info = x;node[q].next = node[p].next;node[p].next = q;return;} /* fim insafter */A rotina delafter(p, px), chamada pela instruo delafter(p, &x),elimina o n seguinte a node(p) e armazena seu contedo em x:delafter(p, px)int p, *px;{int q;if ((p == -1) || (node[p].next == -1)) {printf("remocao nulan");return;}q = node[p].next;*pq = node[q].info;node[p].next = node[q].next;freenode(q);return;} /* fim delafter */Antes de chamar insafter, precisamos assegurar que p no seja nulo.Antes de chamar delafter, precisamos garantir que p e node[p].next no sejamnulos.LIMITAES DA IMPLEMENTAO EM VETORConforme verificamos na Seo 4.2, a noo de um ponteiro permite-nosformar e manipular listas ligadas de vrios tipos. O conceito de um ponteirointroduz a possibilidade de montar um conjunto de blocos de construo,chamados ns, em estruturas flexveis. Alterando os valores dos ponteiros, 268. 250 Estruturas de Dados Usando C Cap. 4os ns podem ser ligados, desligados e remontados em padres que aumentame diminuem com o progresso da execuo de um programa.Na implementao em vetor, um conjunto fixo de ns representadopor um vetor estabelecido no incio da execuo. Um ponteiro para um n representado pela posio relativa do n dentro do vetor. A desvantagemdessa proposta dupla. Primeiro, o nmero de ns necessrios no pode serfreqentemente previsto quando um programa escrito. Em geral, os dadoscom os quais o programa executado determinam o nmero de ns necess-rio.Sendo assim, independentemente da quantidade de elementos que umvetor de ns contenha, existir sempre a possibilidade de que o programaseja executado com uma entrada que exija um nmero maior.A segunda desvantagem da proposta em vetor que a quantidadede ns declarada precisa permanecer alocada para o programa durante suaexecuo. Por exemplo, se 500 ns de determinado tipo forem declarados, aquantidade de armazenamento necessria para esses 500 ns ficar reser-vadaa esse propsito. Se o programa s usar 100 ou at mesmo 10 ns emsua execuo, os ns adicionais ainda permanecero reservados e seu arma-zenamentono poder ser usado para nenhum outro propsito.A soluo para esse problema permitir ns dinmicos, em vez deestticos. Ou seja, quando um n for necessrio, o armazenamento ficarreservado para ele e, quando no for mais necessrio, o armazenamento serliberado. Dessa forma, o armazenamento para ns no mais em uso ficardisponvel para outro propsito. Alm disso, no estabelecido um limitepredefinido sobre o nmero de ns. Enquanto houver armazenamentosuficiente disponvel para o programa como um todo, parte desse armazena-mentopoder ser reservada para uso como um n.ALOCANDO E LIBERANDO VARIVEIS DINMICASNas Sees 1.1, 1.2 e 1.3, examinamos os ponteiros na linguagem C. Se x um objeto qualquer, &x um ponteiro para x. Se p um ponteiro em C, *p o objeto para o qual p aponta. Podemos usar os ponteiros em C para ajudara implementar listas ligadas dinmicas. Entretanto, discutiremos em pri-meirolugar como o armazenamento pode ser alocado e liberado dinamica-mentee como o armazenamento dinmico acessado em C. 269. Cap. 4 Filas e listas 251Em C, uma varivel ponteiro para um inteiro pode ser criada peladeclarao:int *p;Assim que uma varivel p for declarada como um ponteiro para um tipo deobjeto especfico, ser possvel criar dinamicamente um objeto desse tipoespecfico e atribuir seu endereo a p.Isso pode ser feito em C chamando a funo da biblioteca padro,malloc(size). malloc aloca dinamicamente uma parte da memria, de tama-nhosize, e retorna um ponteiro para um item de tipo char. Examine asdeclaraes:extern char *malloc();int *pi;float *pr;Os comandos:pi = (int *) malloc(sizeof (int));pr = (float *) malloc(sizeof (float));criam dinamicamente a varivel inteira *pi e a varivel flutuante *pr. Essasvariveis so chamadas variveis dinmicas. Ao executar esses comandos,o operador sizeof retorna o tamanho, em bytes, de seu operando. Isso usadopara manter a independncia da mquina, malloc poder, ento, criar umobjeto desse tamanho. Assim, malloc(sizeof(int)) aloca armazenamento paraum inteiro, enquanto malloc(sizeof(float)) aloca armazenamento para umnmero de ponto flutuante, malloc retorna tambm um ponteiro para oarmazenamento que ela aloca. Esse ponteiro serve para o primeiro byte (porexemplo, caractere) desse armazenamento e do tipo char *. Para foraresse ponteiro a apontar para um inteiro ou real, usamos o operador deconverso (int *) ou (float *).(O operador sizeof retorna um valor do tipo int, enquanto a funomalloc espera um parmetro de tipo unsigned. Para que o programa nogere mensagens com o "lint", podemos escrever:pi = ( i n t *) malloc ((unsigned) ( s i z e o f ( i n t ) ) ) ;Entretanto, a converso sobre operador sizeof freqentemente omitida.) 270. 252 Estruturas de Dados Usando C Cap. 4Como exemplo do uso de ponteiros e da funo malloc, examine osseguintes comandos:1 int *p, *q;2 int x;3 p = (int *) malloc(sizeof (int));4 *p = 3;5 q = p;6 printf ("%d %dn", *p, *q);7 x = 7;8 *q = x;9 printf("%d %dn", *p, *q);10 p = (int *) malloc (sizeof (int));11 *p = 5;12 printf(%d %dn", *p, *q);Na linha 3, uma varivel inteira criada e seu endereo colocadoem p. A linha 4 define o valor dessa varivel como 3. A linha 5 define q como valor dessa varivel. O comando de atribuio na linha 5 perfeitamentevlido porque uma varivel ponteiro (q) est recebendo a atribuio do valorde outro (p). A Figura 4.3.2a ilustra a situao depois da linha 5. Observeque, nesse ponto, *p e *q referem-se mesma varivel. A linha 6, portanto,imprime o contedo dessa varivel (que 3) duas vezes.A linha 7 define o valor de uma varivel de inteiro, x, com 7. A linha8 muda o valor de *q para o valor de x. Entretanto, como p e q apontamambos para a mesma varivel, *p e *q tm o valor 7. Isso ilustrado naFigura 4.3.2b. A linha 9, portanto, imprime o nmero 7 duas vezes.A linha 10 cria uma nova varivel inteira e coloca seu endereo emp. Os resultados aparecem ilustrados na Figura 4.3.2c. Agora, *p refere-se varivel inteira recm-criada que ainda no recebeu um valor, q no foialterado; portanto, o valor de *q continua 7. Observe que *p no se refere auma nica varivel especfica. Seu valor muda em funo do valor de p. Alinha 11 define o valor dessa varivel recm-criada com 5, conforme ilustradona Figura 4.3.2d, e a linha 12 imprime os valores 5 e 7. 271. Cap. 4 Filas e listas 2533(a)x7 7(b)X7 7qq(c)x5 7 7Figura 4.3.2PqPqpp(d)A funo free usada em C para liberar o armazenamento de umavarivel alocada dinamicamente. A instruo:free(p);invalida quaisquer referncias futuras a *p (a menos, evidentemente, queum novo valor seja atribudo a p por um comando de atribuio ou por umachamada a malloc). Chamar free(p) torna o armazenamento ocupado por *pdisponvel para reutilizao, se necessrio.(Nota: A funo free espera um parmetro ponteiro do tipo char*.Para que o comando fique "limpo", devemos escrever:f r e e ( ( c h a r *) p ) ;Entretanto, na prtica, a converso do parmetro freqentemente omitida.)Para ilustrar o uso da funo free, examine as seguintes instrues: 272. 254 Estruturas de Dados Usando C Cap. 4123456789p = (int *) malloc (sizeof ( i n t ) ) ;*P = 5;q = (int *) malloc (sizeof ( i n t ) ) ;*q = 8;f r e e ( p ) ;p = q;q = (int *) malloc (sizeof ( i n t ) ) ;*q = 6;printf("%d %dn", *p, *q);Os valores 8 e 6 so impressos. A Figura 4.3.3a ilustra a situaodepois da linha 4, onde *p e *q foram alocados e receberam a atribuio devalores. A Figura 4.3.3b ilustra o efeito da linha 5, na qual a varivel paraa qual p aponta foi liberada. A Figura 4.3.3c ilustra a linha 6, na qual o valorde p alterado de modo a apontar para a varivel *q. Nas linhas 7 e 8, ovalor de q alterado de modo a apontar para uma varivel recm-criada querecebe a atribuio do valor 6 na linha 8 (Figura 4.3.3d).Observe que, se malloc for chamada duas vezes sucessivas e se seuvalor for atribudo mesma varivel, como em:p = (i n t *) malloc ( s i z e o f ( i n t ) ) ;*P = 3;p = ( i n t *) malloc ( s i z e o f ( i n t ) ) ;*P = 7;a primeira cpia de *p perdida porque seu endereo no foi salvo. 0 espaoalocado para variveis dinmicas s pode ser acessado por meio de umponteiro. A menos que o ponteiro para a primeira varivel seja salvo emoutro ponteiro, essa varivel ser perdida. Na realidade, seu armazenamentono poder sequer ser liberado porque no existe um meio de referenci-lanuma chamada free. Esse um exemplo de armazenamento alocado queno pode ser referenciado.0 valor 0 (zero) pode ser usado num programa C como ponteiro nulo.Qualquer varivel ponteiro pode ser definida com esse valor. Geralmente,um cabealho padro para um programa C inclui a definio#deine NULL 0para permitir que o valor de ponteiro zero seja escrito como NULL. Essevalor de ponteiro NULL no referencia um local de armazenamento, masindica um ponteiro que no aponta para nada. 0 valor NULL (zero) pode seratribudo a qualquer varivel ponteiro p, aps o que uma referncia a *p serinvlida. 273. p 5 8886 8pq(a)q(b)Pq(c)P(d)qFigura 4.3.3Cap. 4 Filas e listas 255Observamos que uma chamada a free(p) invalida uma refernciasubseqente a *p. Entretanto, os verdadeiros efeitos de uma chamada freeno so definidos pela linguagem C cada implementao de C podedesenvolver sua prpria verso dessa funo. Na maioria das implementa-esde C, o armazenamento para *p liberado, mas o valor de p ficainalterado. Isso significa que, embora uma referncia a *p se torne invlida,talvez no exista um meio de detectar a invalidao. O valor de p umendereo vlido e o objeto nesse endereo, do tipo correto, pode ser usadocomo valor de *p. p chamado ponteiro perdido. de responsabilidade doprogramador jamais usar esse ponteiro num programa. Convm definirexplicitamente p com NULL depois de executar free(p).Precisamos citar ainda outro recurso perigoso associado aos pontei-ros.Se q e p so ponteiros com o mesmo valor, as variveis *q e *p soidnticas. *p e *q referem-se ao mesmo objeto. Sendo assim, uma atribuioa *p muda o valor de q, independentemente do fato de que nem q nem *qestejam explicitamente mencionados na instruo de atribuio a *p. O 274. 256 Estruturas de Dados Usando C Cap. 4programador responsvel pelo rastreamento de "quais ponteiros estoapontando para onde" e pelo reconhecimento da ocorrncia de tais resultadosimplcitos.LISTAS LIGADAS USANDO VARIVEIS DINMICASAgora que dispomos do recurso de alocar e liberar dinamicamente umavarivel, verifiquemos como as variveis dinmicas podem ser usadas paraimplementar listas ligadas. Lembre-se de que uma lista ligada consiste numconjunto de ns, cada um dos quais com dois campos: um campo de informa-oe um ponteiro para o prximo n na lista. Alm disso, um ponteiro externoaponta para o primeiro n na lista. Usamos variveis de ponteiro paraimplementar ponteiros de lista. Dessa forma, definimos o tipo de um ponteirode um n por:struct node {int info;struct node *next;} ;typedef struct node *NODEPTR;Um n desse tipo idntico aos ns da implementao em vetor,exceto pelo fato de que o campo next um ponteiro (contendo o endereo doprximo n na lista) em vez de um inteiro (contendo o ndice dentro de umvetor no qual mantido o prximo n na lista).Empreguemos os recursos de alocao dinmica para implementarlistas ligadas. Em vez de declarar um vetor para representar um conjuntoagregado de ns, os ns so alocados e liberados, conforme a necessidade.Elimina-se a necessidade de declarar um conjunto de ns.Se declararmosNODEPTR p;a execuo do comandop = getnode();dever colocar o endereo de um n disponvel em p. Apresentamos a funogetnode: 275. Cap. 4 Filas e listas 257NODEPTR getnode(){NODEPTR p;p = (NODEPTR) malloc(sizeof(struct node));return(p);}Observe que sizeof aplicado a um tipo de estrutura e retorna o nmero debytes necessrio para a estrutura inteira.A execuo do comandofreenode(p);deve retornar o n cujo endereo est em p para o armazenamento disponvel.Apresentamos a rotina freenode:freenode(p)NODEPTR p;{free(p);}O programador no precisa preocupar-se com o gerenciamento doarmazenamento disponvel. No h mais necessidade do ponteiro avail(apontando para o primeiro n disponvel), uma vez que o sistema controlaa alocao e a liberao de ns e rastreia o primeiro n disponvel. Observetambm que no existe um teste em getnode para determinar a ocorrnciade estouro. Isso acontece porque tal condio ser detectada durante aexecuo da funo malloc e depende do sistema.Como as rotinas getnode e freenode so muito simples sob essa imple-mentao,elas so freqentemente substitudas pelos comandos em linha:p = (NODEPTR) malloc(sizeof (struct node));efree(p);Os procedimentos insafter(p,x) e delafter(p, px) so apresentados aseguir usando a implementao dinmica de uma lista ligada. Pressuponhaque list seja uma varivel ponteiro que aponte para o primeiro n de umalista (se existir alguma) e seja igual a NULL, no caso de uma lista vazia:insafter(p, x) 276. 258 Estruturas de Dados Usando C Cap. 4NODEPTR p;int x;{NODEPTR q;if (p == NULL) {printf("insersao nulan");exit(l);}q = getnode();q -> info = x;q -> next = p -> next;p = -> next = q;} /* fim insafter */delafter(p, px)NODEPTR p;int *px;{NODEPTR q;if ((p == NULL) || (p -> next == NULL)) {printf("remocao nulan");exit(l);}q = p ->next;*px = q -> info;p -> next = q -> next;freenode(q);} /* fim delafter */Observe a semelhana surpreendente entre as rotinas anteriores eas da implementao em vetor apresentadas previamente nesta seo.Ambas so implementaes dos algoritmos da Seo 4.2. Na verdade, a nicadiferena entre as duas verses reside no modo pelo qual os ns soreferenciados.FILAS COMO LISTAS EM CComo ilustrao adicional do uso das implementaes de listas em C,apresentamos rotinas em C para manipular uma fila representada como umalista linear. Deixamos as rotinas para manipular uma pilha e uma fila de 277. Cap. 4 Filas e listas 259prioridade como exerccios para o leitor. A ttulo de comparao, apresenta-remosa implementao em vetor e a dinmica. Presumimos que struct nodee NODEPTR tenham sido declarados como anteriormente. Uma fila representada como uma estrutura:Implementao em Vetorstruct queue {int front, rear;};struct queue q;Implementao Dinmicastruct queue {NODEPTR front, rear;};struct queue q;front e rear so ponteiros para o primeiro e o ltimo n de uma filarepresentada como uma lista. A fila vazia representada por front e rear,ambos equivalendo ao ponteiro nulo. A funo empty s precisa verificar umdesses ponteiros porque, numa fila no-vazia, nem front nem rear seroNULL.empty(pq)struct queue *pq;{return ((pq->front ==-1) ? TRUE: FALSE);} /* fim empty */empty(pq)struct queue *pq;{return ((pq->front ==NULL) ? TRUE: FALSE);} /* fim empty */A rotina para inserir um elemento numa fila pode ser escrita assim:insert(pq, x)struct queue *pq;int x;{int p;p = getnode();node[p].info = x;node[p].next = - 1 ;if (pq->rear == -1)pq->front = p;elsenode[pq->rear].next = p;pq->rear = p;} /* fim insert */insert(pq, x)struct queue *pq;int x;{NODEPTR p;p = getnode();p -> info = x;p->next = NULL;if (pq->rear == NULL)pq->front = p;else(pq->rear)-> next = p;pq->rear = p;} /* fim insert */A funo remove elimina o primeiro elemento de uma fila e retornaseu valor: 278. 260 Estruturas de Dados Usando C Cav. 4remove(pq)struct gueue *pq;{int p, x;if (empty(pq)) {printf ("underflow na filan");exit(1);}p = pq->front;x= node[p].info;pq ->front = node[p].next;i (pq->front == -1)pq->rear = -1;freenode(p);return(x);} /* fim remove */remove(pq)struct queue *pq;{NODEPTR p;int x;if (empty(pq)) {printf ("underflow nafilan");exit(l);}p = pq->front;x = p->info;pq->front = p->next;if (pq->front == NULL)pq->rear = NULL;freenode(p);return(x);} /* fim remove */EXEMPLOS DE OPERAES DE LISTAS EM CExaminemos algumas operaes de lista um pouco mais complexas imple-mentadasem C. Verificamos que a implementao dinmica freqentementesuperior implementao em vetor. Por essa razo, a maioria dos programa-doresem C usa a implementao dinmica para implementar listas. A partirde agora, ns nos restringiremos implementao dinmica de listas ligadas,embora possamos citar a implementao em vetor quando apropriado.Definimos anteriormente a operao place(list, x), onde list apontapara uma lista linear classificada e x um elemento a ser inserido em suaposio correta dentro da lista. Lembre-se de que essa operao usada paraimplementar a operao pqinsert de modo a inserir numa fila de prioridade.Presumimos que j implementamos a operao de pilha push. Veja a seguiro cdigo para implementar a operao place:place(plist, x)NODEPTR *plist;int x;{NODEPTR p, q; 279. Cap. 4 Filas e listas 261q = NULL;for (p = *plist; p != NULL && x > p->info; p = p->next)q = p;if (q == NULL) /* insere x no inicio da lista */push(plist, x ) ;elseinsafter(q, x ) ;} /* fim place */Note que plist deve ser declarada como um ponteiro para o ponteiro da lista,uma vez que o valor do ponteiro de lista externo ser alterado se x for inseridona incio da lista usando a rotina push. A rotina anterior seria chamada pelainstruo place(&list,x).Como segundo exemplo, escrevemos uma funo insend(plist,x) parainserir o elemento x no final de uma lista list:insend(plist, x)NODEPTR *plist;int x;{NODEPTR p ,q;p = getnode();p->info = x;p->next = NULL;if (*plist == NULL)*plist = p;else {/* procura o ultimo noh */for (q = *plist; q->next != NULL; q = q->next)rq->next = p;} /* fim if */} I* fim insend */Apresentamos a seguir uma funo search(list, x) que retorna um ponteiropara a primeira ocorrncia de x dentro da lista list e o ponteiro NULL se xno ocorrer na lista:NODEPTR search(list, x)NODEPTR list;int x;{NODEPTR p;for (p = list; p != NULL; p = p->next) 280. 262 Estruturas de Dados Usando C Cap. 4if (p->info == x)return (p);/* x nao estah na lista */return (NULL);} /* fim search */A prxima rotina elimina todos os ns cujo campo info contm o valor de x:remvx(plist, x)NODEPTR *plist;int x;{NODEPTR p, q;int y;q = NULL;p = *plist;while (p != NULL)if (p -> info == x) {p = p->next;if (q == NULL) {/* remove o primeiro noh da lista */freenode(*plist);*plist = p;}elsedelafter(q, &y);}else {/* avanca para o proximo noh da lista */q = p;p = p->next;} /* fim if */} /* fim remvx */LISTAS NAO-INTEIRAS E NAO-HOMOGENEASEvidentemente, um n numa lista no precisa representar um inteiro. Porexemplo, para representar uma pilha de strings de caracteres por uma listaligada, so necessrios ns contendo as strings de caracteres em seus campos 281. Cap. 4 Filas e listas 263info. Usando a implementao de alocao dinmica, tais ns poderiam serdeclarados por:struct node {char info[100];struct node *next;}; possvel que determinada aplicao exija ns contendo mais de umitem de informao. Por exemplo, todo n de estudante numa lista deestudantes pode conter as seguintes informaes: nome do estudante, nme-rode identificao da faculdade, endereo, ndice de pontos de graduao erea de especializao. Os ns para tal implementao podem ser declaradosassim:struct node {char name[30];char id[9];char address[100];float gpindex;char major[20];struct node *next;} ;Um conjunto separado de rotinas em C deve ser escrito para manipular aslistas contendo cada tipo de n.Para representar listas no-homogneas (as que contm ns dediversos tipos), pode ser usada uma unio. Por exemplo:#deine INTGR 1#define FLT 2#define STRING 3struct node {int etype /* etype equivale a INTGR, FLT ou STRING *//* dependendo do tipo do *//* elemento correspondente. */union {int ival;float fval;char *pval; /* ponteiro para uma string */} element;struct node *next;}; 282. 264 Estruturas de Dados Usando C Cap. 4define um n cujos itens podem ser inteiros, nmeros de ponto flutuante oustrings, dependendo do valor do etype correspondente. Como uma unio sempre suficientemente grande para armazenar seu maior componente, asfunes sizeof e malloc podem ser usadas para alocar armazenamento parao n. Dessa forma, as funes getnode e freenode permanecem inalteradas.Evidentemente, fica sob a responsabilidade do programador usar os compo-nentesde um n, conforme for apropriado. Para simplificar, no restante destaseo presumiremos que uma lista ligada declarada como tendo somenteelementos homogneos (para que as unies no sejam necessrias). Exami-naremosas listas no-homogneas, incluindo as que podem conter outraslistas e listas recursivas, na Seo 9.1.COMPARANDO A IMPLEMENTAO EM VETOR EA DINMICA DE USTASCompensa examinar as vantagens e desvantagens da implementao din-micae da implementao em vetor de listas ligadas. A principal desvantagemda implementao dinmica que ela pode consumir mais tempo na prepa-raodo sistema para alocar e liberar armazenamento do que na manipula-ode uma lista disponvel gerenciada pelo programador. Sua maior vantagem que um conjunto de ns no reservado antecipadamente para uso por umdeterminado grupo de listas.Por exemplo, suponha que um programa use dois tipos de listas:listas de inteiros e listas de caracteres. Sob a representao em vetor, doisvetores de tamanho fixo seriam imediatamente alocados. Se um grupo delistas sobrecarregar seu vetor, o programa no poder continuar. Sob arepresentao dinmica, dois tipos de ns so definidos no incio, masnenhum armazenamento alocado para as variveis, a menos que sejanecessrio. Quando os ns forem necessrios, o sistema ser chamado parafornec-los. Todo armazenamento no-utilizado para um tipo de n pode serusado para outro. Dessa forma, se existir armazenamento suficiente para osns realmente presentes nas listas, no ocorrer um estouro.Outra vantagem da implementao dinmica que uma refernciaa *p no requer o clculo do endereo necessrio ao calcular o endereo denode[p]. Para computar o endereo de node[p], o contedo de p precisa serincludo no endereo base do vetor node, enquanto o endereo de *p dadodiretamente pelo contedo de p. 283. Cap. 4 Filas e listas 265IMPLEMENTANDO NS DE CABEALHONo final da seo anterior, apresentamos o conceito de ns de cabealho quepodem conter informaes globais sobre uma lista, como seu tamanho ou umponteiro para o n atual ou ltimo n na lista. Quando o tipo de dado do contedodo cabealho idntico ao tipo do contedo de n de lista, o cabealho pode sersimplesmente implementado como qualquer outro n, no incio da lista. possvel tambm declarar ns de cabealho como variveis sepa-radasdo conjunto de ns de lista. Isto particularmente til quando ocabealho contm informaes de um tipo diferente dos dados dos ns delista. Por exemplo, examine o seguinte conjunto de declaraes:struct node {char info;struct node *next;};struct charstr {int length;struct node *firstchar;};struct charstr s1, s2;As variveis s1 e s2 de tipo charstr so ns de cabealho para uma lista decaracteres. O cabealho contm o nmero de caracteres na lista (length) eum ponteiro para a lista (firstchar). Sendo assim, s1 e s2 representam stringsde caracteres de tamanho varivel. Como exerccio, podemos escrever rotinaspara concatenar duas strings de caracteres como essas, ou para extrair umasubstring desse tipo de string.EXERCCIOS4.3.1. Implemente as rotinas empty, push, pop e popandtest usando as imple-mentaesde armazenamento em vetor e dinmica de uma pilha ligada.4.3.2. Implemente as rotinas empty, inseri e remove usando uma implemen-taodinmica de armazenamento de uma fila ligada. 284. 266 Estruturas de Dados Usando C Cap. 44.3.3. Implemente as rotinas empty, pqinsert e pqmindelete usando uma imple-mentaodinmica de armazenamento de uma fila de prioridade ligada.4.3.4. Escreva rotinas em C usando ambas as implementaes em vetor e devariveis dinmicas de uma lista ligada, para implementar as opera-esdo Exerccio 4.2.3.4.3.5. Escreva uma rotina em C para intercambiar os elementos m e n deuma lista.4.3.6. Escreva uma rotina, inssub(l1, i1, 12, i2, len) para inserir os elementosda lista 12, comeando no elemento i2 e continuando por len elementos,na lista Zl, comeando na posio i1. Nenhum elemento da lista Zldever ser removido ou substitudo. Se il > length(l1) + 1 (ondelengthdl) indica o nmero de ns na lista Zl), ou se i2 + len - 1 >length(l2), ou se il < 1, ou se i2 < 1, imprima uma mensagem de erro.A lista l2 deve permanecer inalterada.4.3.7. Escreva uma funo em C, search(l, x), que aceite um ponteiro l parauma lista de inteiros e um inteiro x, e retorne um ponteiro para umn contendo x, se existir, e o ponteiro nulo, caso contrrio. Escrevaoutra funo, srchinsert(l, x), que inclua x em l se ele no for encon-trado,e retorne sempre um ponteiro para um n contendo x.4.3.8. Escreva um programa em C para ler um grupo de linhas de entrada,cada uma contendo uma palavra. Imprima cada palavra que aparecerna entrada e o nmero de vezes que ela aparece.4.3.9. Suponha que uma string de caracteres seja representada por uma listade caracteres individuais. Escreva um conjunto de rotinas para mani-pularestas listas como segue (l1, l2 e list so ponteiros para um n decabealho de uma lista representando uma string de caracteres, str um vetor de caracteres, e il e i2 so inteiros):a. strcnvcl(str) para converter a string de caracteres, str, numa lista.Essa funo retorna um ponteiro para um n de cabealho.b. strcnvlc(list, str) para converter uma lista em uma string de caracteres.c. strpsl(l1, 12) para executar a funo strpos da Seo 1.2 sobre duasstrings de caracteres representadas por listas. Essa funo retornaum inteiro. 285. Cap. 4 Filas e listas 267d. strvrfyl(l1, 12) para determinar a primeira posio da string repre-sentadapor l1 que no esteja contida na string representada por l2.Essa funo retorna um inteiro.e. strsbstr(l1, il, i2) para executar a funo substr da Seo 1.2 sobreuma string de caracteres, representada pela lista l1 e pelos inteirosi1 e i2. Essa funo retorna um ponteiro para o n de cabealho deuma lista representando uma string de caracteres, que a substringdesejada. A lista 11 permanece inalterada.f. strpsblill, il, i2, 12) para fazer a atribuio de uma pseudo-substrpara a lista l1. Os elementos da lista l2 devem substituir os i2elementos da lista l1 a partir da posio i l . A lista l2 deve perma-necerinalterada.g. strcmpl(l1, l2) para comparar duas strings de caracteres, represen-tadaspor listas. Essa funo retorna -1 se a string de caracteresrepresentada por l1 menor que a string representada por l2; 0 seso iguais, e 1 se a string representada por l1 maior.4.3.10. Escreva uma funo, binsrch que aceite dois parmetros, um vetor deponteiros para um grupo de nmeros classificados e um nico nmero.A funo deve usar uma busca binria (ver Seo 3.1) para retornarum ponteiro ao nmero isolado se ele estiver no grupo. Se o nmerono estiver no grupo, ela retornar o valor NULL.4.3.11. Suponha que queiramos formar N listas, onde N uma constante.Declare um vetor list de ponteiros com:#definestruct};typedefNODEPTRN . . .node {int info;struct node *next;struct node *NODEPTR;list [N];Leia dois nmeros de cada linha de entrada, sendo o primeironmero o ndice da lista na qual o segundo nmero deve ser colocado' emordem ascendente. Quando no existirem mais linhas de entrada, imprimatodas as listas. 286. 268 Estruturas de Dados Usando C Cap. 44.4. UM EXEMPLO: SIMULAO USANDO LISTAS LIGADASUma das aplicaes mais teis de filas, filas de prioridade e listas ligadasreside na simulao. Um programa de simulao tenta modelar umasituao do mundo real para aprender algo sobre essa situao. Todo objetoe toda ao na situao real tm sua contrapartida no programa. Se asimulao for exata ou seja, se o programa espalha com xito o mundoreal , o resultado do programa dever espelhar o resultado das aes sendosimuladas. Dessa maneira, possvel compreender o que acontece na situa-odo mundo real sem realmente observar sua ocorrncia.Examinemos um exemplo. Imaginemos um banco com quatro caixas(atendentes). Um cliente entra no banco numa hora especfica (t1), querendofazer uma transao com algum caixa. Espera-se que a transao demoredeterminado intervalo de tempo (2) antes de ser finalizada. Se um caixaestiver disponvel, ele poder processar imediatamente a transao docliente, e o cliente sair do banco assim que a transao terminar, na horat1 + t2. O tempo total que o cliente demorou dentro do banco exatamenteigual durao da transao (t2).Entretanto, possvel que nenhum dos caixas esteja livre; talveztodos eles estejam atendendo clientes que chegaram anteriormente. Nessecaso, existir uma fila de espera diante de cada caixa. A fila de determinadocaixa talvez possa consistir em uma nica pessoa a que estiver fazendouma transao com o caixa no momento ou pode ser uma fila muito longa.O cliente encaminha-se para o final da fila mais curta e espera at que todosos clientes anteriores finalizem suas transaes e saiam do banco. Nessemomento, o cliente poder fazer seu negcio. O cliente sair do banco em t2unidades de tempo, depois de alcanar o incio da fila de um caixa. Nessecaso, o tempo gasto no banco t2 mais o tempo decorrido na fila de espera.Em funo desse sistema, gostaramos de calcular o tempo mdiopassado por um cliente no banco. Uma maneira de fazer isso ficar paradona porta do banco, perguntar aos clientes que saem a hora em que chegarame marcar a hora de sua sada, subtrair a primeira da segunda para cadacliente e calcular a mdia de todos os clientes. Entretanto, isso no seriamuito prtico. Seria difcil assegurar que nenhum cliente fosse esquecidoquando sasse do banco. Alm disso, duvidamos que a maioria dos clientesconsiga lembrar a hora exata de sua chegada. 287. Cap. 4 Filas e listas 269Em substituio, podemos escrever um programa para simular asaes dos clientes. Cada parte da situao do mundo real ter um anlogono programa. A ao no mundo real de um cliente chegando ser modeladapor entrada de dados. Quando cada cliente chega, dois fatos so conhecidos:a hora da chegada e a durao da transao (uma vez que, presumivelmente,quando um cliente chega, ele sabe o que foi fazer no banco). Dessa forma, osdados de entrada de cada cliente consistem em um par de nmeros: a hora(em minutos, a partir da abertura do banco) da chegada do cliente e ointervalo de tempo (mais uma vez em minutos) necessrio para a transao.Os pares de dados so classificados pela hora de chegada crescente.