Estruturas de Dados: Aula 13 Tipos abstratos de dados e listas

E aí [Música] [Música] o Olá pessoal sejam bem-vindos a mais uma aula da disciplina estrutura de dados hoje nós vamos falar sobre estruturas de dados lineares ou seja vamos começar o conteúdo é um conteúdo é extenso Tem vários tipos de isso de estrutura de dados lineares dessas estruturas a gente vai ver um pedacinho das listas hoje é basicamente O que que é uma lista como que ela funciona quais são os as vantagens mas antes disso nós vamos tratar sobre o tipo abstrato de dados que são tipos de dados que nós implementamos conforme as nossas necessidades

que agrupam tanto é a parte dos dados quanto as funcionalidades para manipular esses dados e vamos algumas definições né O que que é o tipo de dado que a gente sempre fala né o tipo de dado inteiro o tipo de dado flor te dando estrincha é um conjunto de valores ou seja o domínio que uma variável pode assumir se eu defino por exemplo que uma variável do tipo inteiro ela tem uma faixa de valores específicas que ela pode pode ser é atribuída Então se uma variável é do tipo inteiro eu não posso colocar qualquer valor

eu preciso olhar para o tipo dela que é o inteiro e ter ciência de qual que é o conjunto de valores ou seja qual que é o domínio né que àquela variável pode receber como valor se simplesmente o tipo inteiro eu posso colocar números negativos e positivos dentro de uma faixa de valores pré-determinada O que é um tipo inteiro sem sinal eu posso colocar é do zero em diante né zero e números positivos um tablet para ele Ocupa um tamanho diferente na memória Ou seja quando eu alloco uma variável do tipo inteiro ela vai ocupar

Aquela quantidade de Bart né o bits também que o sistema operacional trabalho então esse é o tipo de dado é o conjunto de valores que uma variável pode assumir não seja o domínio dela e o que que são estruturas de dados que nos já vimos antes né são estruturas que permitem um relacionamento lógico entre diversos tipos de dados por exemplo no Street Nós aprendemos a criar truques e na linguagem C + + E essas stricts não eram compostas por apenas um dado ou um tipo de dado eram vários tipos de dados que possui um relacionamento

lógico são Campos diferentes mais que os campos eles criavam uma entidade eles tinham um relacionamento lógico entre eles o que que é esse nome conceito né de tipo abstrato de dados são estruturas de dados como Street né mas que incluem operações pré-definidas para manipulação desses dados na instruct nós temos vários Campos de diversos tipos e esses campos tinham um relacionamento lógico aqui na estrutura é de tipo abstrato de dados além de ter esse relacionamento lógico entre os dados eu tenho funções operações pré-definidas que manipulam esses dados como criar essa estrutura inclui um novo o valor

excluir acessar enfim e isso é um conceito novo para gente não quando a gente trabalhou com arquivos nessa disciplina a gente tava usando no fundo um tipo abstrato de dados um exemplo é um fire on fire É um tipo abstrato de dados que além de permitir a manipulação de arquivos né que são os dados ele também tinha um conjunto de funções de manipulação desses arquivos para diversas ocasiões estão tinha função para abrir para escrever para ler para fechar é para verificar se a leitura do arquivo chegou até no final dele Enfim então além de permitir

abrir arquivos tinha outras funções também tudo encapsulada dentro do tipo Fairy e eu não consegui acessar um arquivo é acessar o conteúdo de um arquivo de forma direta sem passar pela função f we por exemplo a função f Weed é uma operação pré-definida do tipo abstrato de dados Fire E é isso que a gente vai aprender a fazer criar os nossos próprios tipos de dados é o tipo abstrato de dados na verdade ele é uma metodologia de programação é uma forma diferente de você programar e a proposta é reduzir a informação necessária para programação de

um algoritmo Claro a partir do momento que o tipo abstrato de dados está pronto não vou retornar O slide aqui eu não preciso saber como que o tipo abstrato de dados Fire ele foi implementado eu sei que existem Essas funções e cada função aqui vai permitir executar uma operação diferente então quando eu creio os meus tipos abstratos de dados ele vai reduzir a complexidade então eu vou abstrair todas as variáveis que estão envolvidas tudo em uma única entidade e o que eu preciso saber são só Quais são as operações que tem suporte né que são

próprias a natureza daquele tipo abstrato e vamos a um exemplo prático né antes da gente saber que existe o tipo a tipo abstrato de dados a gente tava é representando por exemplo né dentro de um contexto de aplicação de um sistema para controle escolar a gente tava visualizando o estudante com uma série né uma conte um conjunto de variáveis soltas Então tinha nome do Estudante idade a matrícula tudo de forma separada sem uma ligação lógica agora que a gente conhece o tipo abstrato de dados nesse contexto a gente projeta ele de maneira que não existe

o nome do Estudante a idade ou a matrícula mas simplesmente o tipo estudante e esse tipo estudante ele traz todas essas informações relacionadas de forma lógica e também traz operações pré-definidas que eu não acesso por exemplo a matrícula de forma direta mas eu tenho uma função por exemplo que chama validar a matrícula ou o teu tenho uma outra função uma outra operação pré-definida que permite o verificar a idade desse estudante tudo isso encapsulado entre uma estrutura só e quais são as vantagens de se utilizar o tipo de se implementar nesse utilizar o tipo abstrato de

dados primeiro encapsulamento segurança o programador que tá usando esse tipo abstrato de dados no que você implementou ou é você mesmo que tá utilizando ele não tem acesso direto a manipulação dos dados eu não vou acessar de forma direta o nome do Estudante a idade dele a a matrícula eu vou é manipular esses dados por meio de operações pré-definidas é como se fosse mais ou menos orientação a objetos mas é diferente aqui porque aqui a gente não tá usando o paradigma da orientação a objetos a gente tá usando o paradigma do tipo abstrato de dados

E aí a segunda vantagem flexibilidade e reutilização depois que eu tenho esse tipo abstrato de dados um alimentado eu tenho implementado validado eu posso usar ele qualquer programa e existem diversos fé diversas formas de 51 implementar essa essa metodologia só que vai depender do programador e da aplicação a gente vai ver uma forma de fazer isso dentro dessa disciplina e a lista pessoal ela é um exemplo disso ela é um tipo de estrutura de dados formada por uma sequência de elementos do mesmo tipo a gente já conhece lista Aí de outras ocasiões por exemplos vetores

é uma forma de lista também mas vetor no caso ele é uma estrutura de dados 1 é permite eu manipular esses dados de forma direta os elementos de uma lista ela possui eles e possui uma estrutura interna abstraída Ou seja eu não sei é isso também não me interessa como esses dados estão organizados dentro me interessa que quando eu faço referência a essa lista eu consigo acessar de forma sequencial os elementos do game são conhecidos também como nosso a complexidade das listas ela arbitrária e não afeta o seu funcionamento Ou seja eu não preciso saber

como ela foi implementado não preciso saber complexidade dela eu simplesmente uso o tipo lista e pra mim isso já basta então aqui eu tenho um exemplo de lista de elementos inteiros não eu tenho uma lista com seis elementos do tipo inteiro e essa lista um por todas essas características que a gente tá falando né como não é um tipo de dados simples ela possui algumas operações básicas e também possui algumas características uma lista ela pode possui n elementos ou seja não tem limite o limite vai ser a quantidade de memória disponível no computador para poder

armazenar essa lista e esse N pode ser maior ou igual a zero se n = 0 a gente diz que a lista está vazia mas ela pode também ter alguns elementos ou estar cheia start é E se ela for uma lista estática que não permite relocar mais espaço para ela e tem uma lista do tipo genérico né é a gente pode realizar algumas operações básicas quais são essas criar destruir a lista inserir e excluir e acessar um elemento e também retornar informações dessa lista E é isso que a gente vai aprender a fazer bom quando

a gente tiver implementando o tipo lista a essas operações elas variam conforme o tipo dessa lista se essa lista é uma lista estática ou se é uma lista dinâmica ou seja conforme o tipo de alocação de memória a gente diz que é uma lista tá cheia quando não cabe mais elementos nela Muito provavelmente essa lista é uma lista estática Porque ela foi definida com o conjunto é com um número fixo de posições e esse número ele não é alterado em tempo de execução e já uma lista dinâmica ela vai se tornar cheia quando não houver

mais espaço em memória no computador para gente alocar e adicionar novos elementos vamos ver essas duas diferenças né as listas criadas com alocação de estática e com alocação dinâmica quando eu crio uma lista é de forma estática o espaço de memória alocado para essa lista ela é ele é feito no momento da compilação Ou seja quando eu escrevo programa E e compilo esse código para ele se transformar um arquivo executável um binário ou naquele momento é um de Finnick a minha lista tem tamanho 50 ela vai ter tamanho 50 para o resto da vida enquanto

aquele programa tiver funcionando a não ser que eu abro o código desse programa altere de 50 sei lá para 70 e com o Pine de novo Gere um novo executável essa e é alocado de forma estática ela exige a definição de número máximo de elementos é 50 70 100 enfim mil acesso sequencial com n elementos consecutivos você já é um vetor quando eu digo que esse acesso é sequencial quer dizer que todos os dados são armazenados na memória ou seja todas as posições dessa lista estão na memória de forma sequencial então se eu tenho uma

lista com cinco elementos os cinco estão na posição continuar de memória é uma lista é estática sequencial ela é composta de duas partes tá um vetor e uma variável esse vetor é onde a gente guarda os nossos elementos nessa lista e nessa variável ela aponta para próxima posição vaga da lista indicando a quantidade de elementos também porque porque em C + + os nossos vetores começam com índice zero nesse caso aqui eu tenho um exemplo de uma lista é que não importa para mim a quantidade final de posições dela mas nesse caso aqui ela tem

seis posições e dessas 63 já estão preenchidas com número 33 23:16 essa variável quantidade aqui ela indica a próxima posição de memória que está vazia que que no caso é a posição com índice três e também indica quantos elementos estão já armazenados nesta lista e quando a gente cria uma lista dinâmica aí já é diferente porque o espaço de memória ele alocado em tempo de execução e quando eu abri o meu programa que vai manipular listas é o meu programa ele vai precisar de um espaço aí memória mas a minha lista ela inicia vazia ela

iniciou sem ocupar espaço nenhum e ela vai crescendo à medida que eu vou adicionando novos elementos Então ela cresce à medida que os elementos são armazenados na memória e diminui à medida que são removidos por isso que é diferente da estática que Independente de Quantos elementos eu tenho na lista a minha lista cheia ou vazia ocupa a mesma quantidade em memória o processo dessa lista também é diferente da lista estática porque lá na lista é estática o acesso é sequencial Ou seja todos os números estão é um após o outro aqui o acesso é em

cadeado cada elemento pode estar na posição distinta da memória então se eu tiver uma lista com cinco elementos eu posso ter o primeiro elemento na posição da memória o segundo elemento lá na posição 6 o terceiro elemento na posição 200 o quarto elemento na posição é três então eu eles não são sequenciais mas eu tenho uma forma de é é saber qual que é sequência de cada um deles é em cadeado o acesso Eles não estão sequenciais na a memória mas eu consigo controlar Qual que é o próximo elemento a partir de cada um para

gente acessar um elemento dessa lista a gente precisa percorrer todos os seus antecessores da lista eu sei onde a lista começa mas eu não sei aonde que termina se eu quero acessar o quarta quarto elemento dessa lista eu tenho que partir do primeiro e para o segundo do segunda vou para o terceiro do terceiro eu vou para o quarto não preciso começar a dormir isso essa lista ela possui dois conjuntos de campo o dado a eo ponteiro que aponta para o próximo da lista a gente vai aprender a implementar essas miçangas aqui na prática mas

por enquanto é só overview das listas né Para que que serve e quais são os tipos no caso da lista dinâmica Eu tenho um ponteiro inicial eu sei que nesse exemplo aqui está apontando para posição sem da memória lá na posição sem eu tenho o número 33 vinculado a esse número 33 da minha lista eu tenho uma posição de memória 24 o que que eu tenho nessa posição de memória 24 o próximo elemento da lista O que é o 23 por sua vez 23 também vinculado a ele eu tenho outro endereço de memória que a

Andressa 45 O que que tem no endereço de memória 45 o número 16 o número 16 é o último elemento dessa lista então o ponteiro que tá É próximo né que tá vinculado a ele indicando o próximo elemento da lista ele não tem endereço nenhum por isso ele é no ele aponta para posição nenhuma da memória Olá pessoal é isso é as listas é de forma geral podem ser divididas em status aí dinâmica mas existem tipos especiais de listas como listas circulares como pilhas como filas que são os tipos que nós vamos ver nas próximas

aulas até lá saiba mais sobre o Instituto Federal goiâno as SF goiano.edu.br e os procure também manter de sociais Instituto Federal Goiano a educação transforma você transforma o mundo