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.