Tipos Tipos

Abstratos Abstratos de de

Dadose Dadose

Listas Listas

Lineares Lineares

EstruturasdeDados EstruturasdeDados

Prof.AlexSandro alexscunha@yahoo.com.br

Introdução

TiposdeDados

Conjuntodevaloresqueumavariávelpode assumir+operaçõesquepoderãoserefetuadas

GruposdeTiposdeDados:

Primitivos Estáticos(Linguagenstipadas) Dinâmicos

Abstração Oquesignifica?

“Nomundodaprogramação,pararesolverumproblema énecessárioconstruirumaabstraçãodarealidadee depoisencontrarumaformaderepresentá-laemuma linguagemdeprogramação”.

Introdução

TiposAbstratosdeDados(T.A.D.)

Conceito:modeloidealizadopararepresentar umaabstração

Tiposcomplexosdefinidospelousuário

ImplementarumTAD:representara abstraçãoemlinguagemdeprogramaçãoe definirumaestruturadedadospara representá-la

Definição:

Modelopararepresentaçãodeumaabstração, constituídopordadoseoperaçõessobreseus elementos.

EstruturadeDados

“Asestruturasdedadosdiferemumadasoutraspela disposiçãooumanipulaçãodeseusdados”(Markenzon, 1994).

“Programarébasicamenteestruturardadoseconstruir algoritmos”(Wirth,1976).

EstruturadeDados

MétodoparticulardeseimplementarTAD Filas,Pilhas,Listas,Árvores,etc.

Constituídoportiposprimitivosoucompostos

Obs:EmC,aimplementaçãodeestruturasde dadosenvolveconceitossobreponteirose estruturas( struct).

EstruturadeDados

EstruturadeDados

ImplementaçãodeumTAD

Qualaidéia? Encapsulamento

Técnicafundamental: modularização

Programaédivididoemmódulos Facilitaamanutençãoereutilizaçãodecódigo

OperaçõesefetuadasemumTAD

1.Criação

2.Inclusão

3.Remoção

4.Percurso 5.Busca

TiposAbstratosdeDados

Exemplo:oTADponto

/* ponto.h (protótipo e def. estrutura) */ typedef struct { int x, int y; }ponto; ponto* criaPonto(int x, int y); void liberaPonto(ponto* p); void acessaPonto(ponto* p, int *x, int *y); void atribuiPonto(ponto* p, int x, int y); float distanciaPonto(ponto *p1, ponto *p2);

/* ponto.c : implementação do tipo abstrato de dados “ponto” */ #include “ponto.h”

#include<bibliotecas de C> /* Aqui voce coloca o corpo das funcoes, inclusive com sua assinatura */

/* main.c */ #include “ponto.h” #include<bibli otecas de C> main() { /* declare o(s) ponto(s) e use suas operacoes */

ListasLineares

Definição:

“Estruturadinâmica/estáticacaracterizadapor umasequênciaordenadadeelementos”. (VILLASetal,1993)

CompostaporNós.

Exemplos:

ListaTelefônica,listadeclientesdeumaagência bancária,listadesetoresdeumdisco,etc.

Representação:

ListasLineares

Propriedades

Existemnelementosnasequência;

E1éoprimeiroelementodasequência;

Enéoúltimoelementodasequência;

Paratodoi,jentre1en,sei<j,entãoo elementoEiantecedeoelementoEj;

Operaçõesrealizadascomlistas

Criarumalistavazia;

Verificarseumalistaestávazia;

Obterotamanhodeumalista;

Obter/modificarovalordoelementoemuma determinadaposiçãonalista;

ListasLineares

Operaçõesrealizadascomlistas(cont.)

Obteraposiçãodoelementocujovalorédado;

Inserirumnovoelementoapós(antes)deuma determinadaposiçãonalista;

Removerumelementoemumadeterminada posição.

Exibiroselementosdeumalista; Concatenarduaslistas.

FormasdeRepresentaçãodelistas(Overview):

a) Sequencial b) Encadeada

ListaSequencial

Exploraasequencialidadedamemóriado computador.

Utilizaestruturasestáticas

ListasLineares

paulo joao ana eu LISTA

ListaEncadeada

Sequenciadeelementosencadeadospor ponteiros

ListasLineares casa carro cama mesa

ListaSequencial

Listaarmazenadaemmemórianaforma sequencial.

Aimplementaçãodeoperaçõespodeserfeita utilizandoarray,associandooelementoa(i) comoíndicei(mapeamentosequencial)

Características

Elementossãoarmazenadosfisicamenteem posiçõesconsecutivas

Ainserçãodeumelementonaposiçãoa(i) causaodeslocamentoadireitadoelemento a(i)aoúltimo

Aremoçãodoelementoa(i)requero deslocamentoàesquerdadoelementoa(i+1) aoúltimo

ListaSequencial

Oquedevemossabersobreaslistas?

Seestávazia

Seestácheia

Númerodeelementosexistentes

Qualelementoocupaumadeterminada posição

Inserireremoverelementos;

Comorealizarbuscaepercorrerseus elementos

Obs:Asquatroprimeirasoperaçõesocorrem constantemente.Asdemaisrequeremcuidados

ListaSequencial

Vantagens

Acessodiretoindexadoaqualquerelementoda lista;

Tempoconstanteparaacessaroelementoi (dependeapenasdoíndice).

Desvantagens

Movimentaçãoquandoeliminado/inseridoum elemento;

Tamanhomáximopré-estimado;

Quandousar?

Listaspequenas;

Inserção/Remoçãonofimdalista; Quandootamanhomáximoébemdefinido.

Operaçõesbásicassobaslistas

CódigofonteemC:

DefiniçãodaED; Criaçãodeumalistavazia Verificarsealistaestávazia Verificarseumalistaestácheia ObteroI-ésimoelementodeumalista Pesquisarumdadoelemento,retornandoumaposição Inserirumelementoemumadeterminadaposição Removerumelementoemumadeterminadaposição

ListaSequencial

Bibliografia

IntroduçãoaEstruturasdeDados.Riode Janeiro:Campus,2004.

ZIVIANI,N.:Projetodealgoritmoscom implementaçõesemPascaleC.SãoPaulo: Thomsoneditora,2aedicao,2004.

G.;MIRANDA,C.;BOCKMAN,C.,L.Estruturas deDados.RiodeJaneiro:Campus,1993.

M.:EstruturadeDadosUsandoC.SãoPaulo: MakronBooks,1995.

Comentários