7
Capítulo 1Tipos Abstratos de Dados
Seus objetivos neste capítulo• EntenderoconceitodeTiposAbstratosdeDadoseomododeutilizá-lo
nodesenvolvimentodeprogramas.
• PerceberqueousodeTiposAbstratosdeDadosdáaosoftwaremaiorportabilidade,
maiorpotencialparareutilização,reduzcustosdedesenvolvimentoedemanutenção.
• Conscientizar-sequantoàimportânciadeadotarumaestratégiaqueagregue
portabilidadeereusabilidadeaosjogosquevocêdesenvolverá.
1.1 Queremos desenvolver um jogo. E agora?Suponhaquevocêemaisdoisamigostenhamdecididodesenvolverumjogonomundovirtual—umsoftware.Eagora?Qualoprimeiropasso?
Quandoqueremosdesenvolverumsoftware,oprimeiropassoédecidiro quedesen-volver.Ociclodevidatradicionaldodesenvolvimentodesoftwareenvolveasfasesdeanálise,projeto,implementação,testeemanutenção(Figura1.1).Nafasedeanálise,determinamoso queosoftwareprecisafazer,quaisproblemasdeveráresolverequaisinformaçõesdeverámanipular.
8
Capítulo 1 Tipos Abstratos de Dados
Nafasedeprojeto,oobjetivoédefinircomoosoftwareserádesenvolvido.Estamosfalandodeumadefiniçãogeral,nãodetalhada.Nafasedeprojeto,escolhemosaarquiteturadosoftware,definimosquaisserãoosprincipaismódulose,comisso,podemosdividirotrabalhoentreosdesenvolvedores—cadamembrodaequipeficaresponsávelpelaimplementaçãodeumdosmódulos.
Asoutrasfasesreferem-seàimplementação(codificaçãoemumalinguagemdepro-gramação),teste(paragarantirqueosoftwarefuncionesegundooesperado)emanu-tenção(ajusteouevoluçãonasfuncionalidadesdosoftware,aolongodeseuperíododeutilização).Paraumaleituracomplementarsobreociclodevidatradicionaldodesenvolvimentodesoftware,consulteSommerville(2003)ePressman(1995).
VamossuporquevocêeseusdoisamigosaceitaramoDesafio1dolivroEstruturas de dados com jogosedecidiramdesenvolverumjogocomooFreeCell.Jásabemo quedesenvolvereestãoagoranafasedeprojeto,definindocomodesenvolver.Evocêsestãodecididosaescolheramelhorestratégiaparadesenvolveressejogo.Éprecisamentenessecontexto,nafasedeprojetodosoftware,embuscadamelhorestratégia,quevocêprecisaconhecereutilizaroconceitodeTiposAbstratosdeDados.
1.2 Definição de Tipos Abstratos de DadosUmTipoAbstratodeDadoséformadoporumacoleçãodeDadosaseremarmazenadoseumconjuntodeOperaçõesouaindaOperadoresquepodemseraplicadosparama-nipulaçãodessesDados(Langsam,AugensteineTenembaum,1996;Celes,CerqueiraeRangel,2004).TodamanipulaçãodesseconjuntodeDados,parafinsdearmazenamentoerecuperação,deveserrealizadaexclusivamenteatravésdosOperadores.
Figura 1.2 DefiniçãodeTipoAbstratodeDados.
Figura 1.1 Fasesdodesenvolvimentodesoftware.
Estruturas de Dados com Jogos
9
EmquemomentodevemseridentificadoseprojetadososTiposAbstratosdeDados?Nafasedeprojetodosoftware,ouseja,nomomentoemquedefinimosumavisãogeral,nãodetalhada,decomoosoftwareserádesenvolvido.
1.3 Exemplo: FreeCellComooconceitodeTiposAbstratosdeDadospodeserutilizadonoprojetodoFreeCell,ojogodoDesafio1quequeremosdesenvolver?TemosnoFreeCellalgumconjuntodeDadosaseremarmazenados?Sim!Temos,porexemplo,osvaloreseosnaipesdascartasetambémasequênciadessascartasnasPilhas Intermediárias.
UmdosOperadoresparamanipulaçãodessesDadostemporobjetivoretiraracartaqueestánotopodapilha.UmsegundoOperadorpoderiasercolocarumacartanotopodapilha,casoovalordacartaestivernasequênciacorreta.NessasPilhas Intermediárias,sóépossívelinserircartasnotopodapilhaemordemdecrescenteeemcoresalternadas—pretassobrevermelhasevermelhassobrepretas.
ApartirdadefiniçãodoTADPilhaIntermediáriadoFreeCell,oaplicativoFreeCellcomoumtododeverealizaroarmazenamentodascartasnasPilhas Intermediáriasdemodoabstrato,ouseja,semsepreocuparcomosdetalhesdecomoessesdadossãoefetivamentearmazenados.Arecuperaçãodosdadostambémdeveocorrerdemodoabstrato.FuncionariacomoseasPilhas Intermediáriasfossemcaixas-pretas,comumaoperaçãopararetiraracartaqueestánotopodapilhaeoutraparacolocarumacartanotopodapilha,casoasequênciaestivercorreta.Osdemaismódulosdoprogramasimplesmentepediriam“Retireacartaqueestánotopodestapilha”ou“Coloqueestacartanotopodaquelapilha”,eacaixa-pretaquecuidadissodariaumjeitodeatenderassolicitações.
Figura 1.3 ExemplodeTADPilhaIntermediáriadoFreeCell.
10
Capítulo 1 Tipos Abstratos de Dados
Suponhaque,nafasedeprojeto,tenhasidodefinidooTADPilhaIntermediáriadoFree-CellesuasoperaçõesdetalhadasconformemostraaFigura1.4.
Suponhatambémqueoutroprojetistadesoftwaretenhaficadoencarregadodeim-plementaroTADPilhaIntermediáriadoFreeCell.CoubeavocêdesenvolveraoperaçãoparatransferirumacartaentreduasPilhas Intermediárias,casoaCartaretiradadaPilha de OrigemestivernasequênciacorretanaPilha de Destino,conformeasregrasdoFreeCell.ComovocêdesenvolveriaessaoperaçãosemteramenorideiaquantoaosdetalhesdaimplementaçãodaPilhaIntermediária?
Exercício 1.1 Transfere Carta
DesenvolvaumaoperaçãoparatransferirumaCartaentreduasPilhas IntermediáriasdoFreeCell.AtransferênciasópoderáserrealizadaseaCartaretiradadaPilhaOrigemestivernasequênciacorretanaPilhaDestino,conformeasregrasdefuncionamentodoFreeCell.SeaCartanãoforefetivamentetransferida,deveretornaràPilhaOrigem.EssaoperaçãodeveserimplementadacomousodosoperadoresdoTADPilhaIntermediáriadoFree-Cell,conformeespecificadonaFigura1.4.
AFigura1.5apresentaumalgoritmoconceitualparaaoperação,quetransfereumacartaentreduasPilhas Intermediárias.NotequeamanipulaçãodosDadosarmazenadosnasPilhas IntermediáriaséfeitaexclusivamenteatravésdosOperadoresdefinidosnaespecificaçãodoTAD(Figura1.4).Devidoaisso,paradesenvolveressasoluçãonãofoi
Figura 1.4 OperaçõesdoTADPilhaIntermediária.
Estruturas de Dados com Jogos
11
precisoconhecerdetalhessobreaimplementaçãodasPilhasIntermediárias.Nãoélegalprogramarassim?
AsOperaçõesdoTADPilhaIntermediária,conformeconstamnaFigura1.4,eoalgoritmoconceitualdaFigura1.5têmporobjetivoapenasexemplificaroconceitodeTiposAbs-tratosdeDados.AconcepçãodasOperaçõesdeumaPilhadeveráseraprimoradaapartirdaapresentaçãodenovosconceitosnoCapítulo2.
1.4 Qual a melhor maneira de aumentar o volume da televisão?Temosduasestratégiasalternativasparaaumentarovolumedeumatelevisão.Primeiraalternativa:podemosaumentarovolumedatelevisãoacionandoobotãodovolume,nocontroleremotoounaprópriatelevisão.Nasegundaalternativa,pegamosumachavedefenda,abrimosatelevisão,mexemoscomachavedefendaemumcomponenteeletrônicoeaumentamosovolume“namarra”.Qualalternativavocêachamaisinteres-sante:botãodevolumeouchavedefenda?
Emumaanalogia,podemosconsiderarumTipoAbstratodeDadoscomoumatelevisão.Podemosdesenvolverprogramasaumentandoovolumeatravésdobotãodatelevisãooupodemosdesenvolverprogramasaumentandoovolumecomumachavedefenda.AumentarovolumepelobotãodatelevisãosignificaidentificarTiposAbstratosdeDados,definirDadosaseremarmazenados,definirOperadoresaplicáveisaessesDadose,apartirdeentão,sómexernessesDadosatravésdosOperadoresdoTAD.OsOperadoresdoTAD,emnossaanalogia,equivalemaosbotõesdatelevisão(Figura1.6).
QualopapeldeumTADnoprojetodesoftware?UmTipoAbstratodeDadoséummodelo abstratodoarmazenamentoemanipulaçãodedeterminadoconjuntodeDados
Figura 1.5 Algoritmoconceitual—TransfereCarta.
12
Capítulo 1 Tipos Abstratos de Dados
deumprograma.UmTADéumacaixa-preta.Oqueévisívelexternamenteaessacaixa-pretaéasuafuncionalidade,ouseja,asOperaçõesdefinidasparaoTAD.Osdeta-lhesdeimplementaçãoficamescondidos.
Oprincipalpropósitodessemodelo abstratochamadoTipoAbstratodeDadosésim-plificar.Porexemplo,umavezdefinidooTADPilhadeCartas,aoconstruiralógicadaaplicaçãodevemosabstrair,nosdespreocuparousimplesmenteesquecercomooarmazenamentodascartaséefetivamenteimplementado.DevemossimplesmenteacionarasoperaçõesdaPilhadeCartas,ouos“botõesdatelevisão”,paraconstruiralógicadaaplicação.Émaissimplesprogramarassim,nãoé?
ÉpossívelalterarosdadosdeumaPilhadeCartassemserporintermédiodeumaoperaçãodefinidanaespecificaçãodoTADPilhadeCartas?Sim,épossível.Mas,fazendoisso,estamosoptandopelaestratégiadachavedefenda,ouseja,estamosabrindoatelevisãocomumachavedefendaparaaumentarovolume.Utilizarobotãodevolumeéumaestratégiamelhor!
1.5 O que é um bom programa?Não,umbomprogramanãoésimplesmenteumprogramaquefunciona.Naverdade,umprogramaquenãofuncionaaindanãoéumprograma.Vamosdetalharapergunta:temosdoisprogramaseosdoisfuncionam.Umdeleséumprogramabomeooutroéumprogramaruim.Quaissãoaspossíveiscaracterísticasdoprogramaqueébom?
Vocêsabeoquesignificaportabilidadedecódigo?Resumidamente,portabilidadeéacapacidadedeumcódigo(trechodeprograma)executaremdiferentesplataformasdehardwareesoftware.Assimcomopodemoscarregarumcomputadorportátildeumlugarparaooutro,podemoscarregarumsoftwareportátildeumaplataformaparaoutra,eessesoftwarecontinuaráfuncionando.Pense,porexemplo,emumeditordetexto.Comoeleconsegueexecutaraoperaçãodeimprimir,mesmosevocêtrocarasuaimpressora?Portabilidadedesoftware:capacidadedeexecutaremdiferentesplataformas.
Figura 1.6 Analogia:OperadoresdoTADebotõesdatelevisão.
Estruturas de Dados com Jogos
13
Eotermoreusabilidade,vocêsabeoquesignifica?Reusabilidadedecódigoousoftwaresignificareutilizarumsoftwarejádesenvolvido,emumasegundasituação.Ouseja,vocêdesenvolveosoftwareparaumanecessidadeeoaproveita(reutiliza)parasatisfazerumasegundanecessidade.
Outrocritérioquepodeserutilizadoparadiferenciarprogramasbonsdeprogramasruinséaeficiência—umprogramaqueexecutamaisrápidoouutilizamenosmemória.Sevocêtivessequeescolherentreumcódigocommaiorportabilidadeereusabilidade,eumcódigoqueexecutemilésimosdesegundomaisrápido,oqueescolheria?
Existemcircunstânciasespecíficasnasquaiscertamenteénecessáriopriorizaraeficiência.Porexemplo,quandoprecisamosgarantirqueotempoderespostadeumsoftwaresatisfaçacritériosmuitorígidos,paraquenãoocorramgrandesdesastres.Mas,namaiorpartedascircunstâncias,asopçõesdeprojetodevempriorizaroqueresultaemcustomaisbaixonodesenvolvimentoenamanutençãodesoftware.
Portabilidadeereusabilidadesãocaracterísticasdeumsoftwarequeresultamemcustomaisbaixodedesenvolvimentoemanutenção.
1.6 Vantagens da utilização de Tipos Abstratos de DadosPodemosapontarasseguintesvantagensdautilizaçãodoconceitodeTiposAbstratosdeDados:
● É mais fácil programar, sem se preocupar com detalhes de implantação.Porexemplo,nomomentodetransferirdadosdeumaPilha de Cartasparaoutra,vocênãoprecisasepreocuparemsabercomoaPilhaéefetivamenteimplementada.VocêprecisaapenassaberutilizarasoperaçõesquecolocamouretiramcartasemumaPilha.
● É mais fácil preservar a integridade dos dados.ApenasasoperaçõesdoTipoAbstratodeDadosalteramosdadosarmazenados.SuponhaqueasoperaçõesdoTADPilha de Cartasestejamcorretas,nãocorrompendoosdadosnemocasionan-doperdadedados.SevocêalterarosDadospelosOperadoresdoTAD,osDadoscertamenteserãopreservados.Mas,sevocênãoconhecemuitobemaimplemen-taçãodoTADPilhadeCartasedecidealterarosDadoscom a chave de fenda(ouseja,semusarosbotõesdatelevisão),épossívelquefaçaalgumabesteiraeacabecorrompendoosdados.
● Maior independência e portabilidade de código.AlteraçõesnaimplementaçãodeumTADnãoimplicamemalteraçõesnasaplicaçõesqueoutilizam.Vamossuporque
Figura 1.7 Portabilidadeereusabilidadedesoftware.
14
Capítulo 1 Tipos Abstratos de Dados
implementamosumTADPilha de Cartasutilizandodeterminadatécnicadeimplemen-tação,masdepoisdecidimosmudaratécnicadeimplementação.SeumaaplicaçãoqueusaoTADtiversidoimplementadaexclusivamenteatravésdosOperadoresdoTAD,essaaplicaçãocontinuaráfuncionando,aindaqueaimplementaçãodoTADPilha de Cartassejacompletamentealterada.OquemudoufoiaimplementaçãodoTAD,masseusOperadorescontinuamosmesmos!Logo,aaplicaçãocontinuaráfuncionando.
● Maior potencial de reutilização de código.Pode-sealteraralógicadeumprogramasemnecessidadedereconstruirasestruturasdearmazenamento.UmmesmoTADPilha de CartaspodeserutilizadonodesenvolvimentodoFreeCell,nodesenvolvimentodevariaçõesdoFreeCelletambémnodesenvolvimentodeoutrasaplicaçõesqueutilizampilhasdecartas.
SeadotarmosumaestratégiadedesenvolvimentocomousodeTiposAbstratosdeDados,ouseja,aumentandoovolumedatelevisãosemprepelosbotõesenuncacomachavedefenda,odesenvolvimentoserámaisfácil,osdadosestarãomaisseguros,ocódigoteráumpotencialmaiorparaexecutaremdiferentesplataformaseparaserreutilizadoemoutrasaplicações.Comoconsequência,teremoscustomenordedesen-volvimentoemanutenção.Softwarebom,bonitoebarato!
VamosadotarTiposAbstratosdeDadosnodesenvolvimentodenossosjogos?
Software bom, bonito e barato
OusodoconceitodeTiposAbstratosdeDadosaumentaaportabilidadeeopotencialdereutilizaçãodosoftware.Emconsequênciadisso,ocustodedesenvolvimentoemanutençãoéreduzido.
Consulte no Banco de Jogos AdaptaçõesdoFreeCell
Exercícios de fixaçãoExercício 1.2OqueéumTipoAbstratodeDados(TAD)?ComoosdadosarmazenadosemumTADdevemsermanipulados?EmquemomentoumTADdeveseridentificadoedefinido?
Exercício 1.3ComoépossíveldesenvolverumprogramautilizandoumTADPilhadeCartas,porexemplo,semconhecerdetalhesdesuaimplementação?
Exercício 1.4Oqueéportabilidadedecódigo?Oqueéreusabilidadedecódigo?
http://www.elsevier.com.br/edcomjogos
Estruturas de Dados com Jogos
15
Exercício 1.5Façaumapesquisasobreportabilidadeereusabilidadedesoftware.Con-versecomoscolegassobreoquevocêconsideraimportantesobreisso.Vocêconcordaqueportabilidadeereusabilidadesão,namaioriadassituações,característicasmaisimportantesparaumprogramadoqueexecutarmilésimosdesegundomaisrápido?
Exercício 1.6QuaisasvantagensdeprogramarutilizandooconceitodeTAD?Expliquecomexemplos.
Exercício 1.7Consulteemumdicionárioosignificadodotermo“abstrato”.Consulteaspalavras“abstrato”,“abstrair”e“abstração”.
Referências e leitura adicionalCeles,W.;Cerqueira,R.;RangelF.L.Introdução a estruturas de dados.RiodeJaneiro,Elsevier;2004.p.126.Langsam,Y.;Augenstein,M.J.;Tenenbaum,A.M.Data Structures Using C and C++.2nded.UpperSaddle
River.NewJersey:PrenticeHall,1996.p.13.Pressman,R.Engenharia de software.3.ed.SãoPaulo:MakronBooks,1995.p.32-35.SommervilleR.I.Engenharia de software.6.ed.SãoPaulo:AddisonWesley,2003.p.35-38.