Estrutura de Dados - Aula 03

Estrutura de Dados

Prof. Me. Stephany Mendes

TAD - Vetores e Listas Encadeadas

Um vetor (também conhecido como array) é uma estrutura de dados que armazena múltiplos elementos de mesmo tipo em um bloco contínuo de memória. Cada elemento pode ser acessado diretamente pelo seu índice, o que garante um acesso muito rápido e eficiente, já que o endereço de cada elemento pode ser calculado com base no índice.

Vetores

Entendo Vetores e Listas Encadeadas

• Acesso rápido: O acesso a um elemento em um vetor é feito diretamente através de seu índice, com complexidade O(1) (constante), já que não há necessidade de percorrer a estrutura.

• Memória contígua: Todos os elementos de um vetor são armazenados em posições adjacentes na memória.

Características de Vetores

Entendo Vetores e Listas Encadeadas

• Tamanho fixo: Em muitas linguagens (exceto em Python), os vetores têm um tamanho fixo, o que significa que não podem crescer ou diminuir dinamicamente.

• Desempenho para inserção/remoção: Inserir ou remover elementos no meio do vetor é ineficiente, pois pode ser necessário mover vários elementos para manter a continuidade da memória (complexidade O(n) para essas operações no pior caso).

Características de Vetores

Entendo Vetores e Listas Encadeadas

Em Python, os vetores são implementados como listas nativas, e sua sintaxe é muito simples. Embora as listas em Python possam armazenar elementos de tipos diferentes, o conceito de "vetor" normalmente implica que todos os elementos sejam do mesmo tipo (em linguagens fortemente tipadas).

1. Acesso a elementos: Através do índice.

2. Inserção no final: Usando o método append().

3. Remoção: Usando o método remove() ou pop() (removendo por índice).

4. Atribuição: Os valores de um vetor podem ser alterados acessando diretamente o índice.

Operações em Vetores

Entendo Vetores e Listas Encadeadas

Uma lista encadeada (ou linked list) é uma estrutura de dados dinâmica, onde cada elemento (chamado de nó) contém:

1. Um valor (ou dado).

2. Uma referência (ou ponteiro) para o próximo nó da lista.

Lista Encadeada

Entendo Vetores e Listas Encadeadas

• Acesso sequencial: Diferente de um vetor, onde podemos acessar qualquer elemento diretamente pelo índice, em uma lista encadeada precisamos começar a partir do primeiro nó e percorrer a lista até encontrar o elemento desejado. Isso torna o acesso mais lento (O(n) no pior caso).

Características da Lista Encadeada

Entendo Vetores e Listas Encadeadas

• Crescimento dinâmico: Uma lista encadeada pode crescer ou diminuir dinamicamente, pois não precisa de blocos contínuos de memória.

Características da Lista Encadeada

Entendo Vetores e Listas Encadeadas

• Inserção e remoção rápidas: A inserção e remoção de elementos, especialmente no início ou no meio da lista, é muito eficiente, pois não é necessário mover outros elementos na memória. No entanto, é preciso percorrer a lista até o ponto desejado.

Características da Lista Encadeada

Entendo Vetores e Listas Encadeadas

• Lista simplesmente encadeada: Cada nó tem uma referência para o próximo nó.

• Lista duplamente encadeada: Cada nó tem uma referência para o próximo nó e para o nó anterior.

• Lista circular: O último nó da lista aponta para o primeiro nó, formando um ciclo.

Tipos de Lista Encadeada

Entendo Vetores e Listas Encadeadas

1. Inserção no início: Adiciona um novo nó no começo da lista.

2. Inserção no final: Adiciona um novo nó no final da lista.

3. Remoção de um nó: Remove um nó específico, ajustando os ponteiros dos nós adjacentes.

4. Busca: Percorre a lista para encontrar um valor.

5. Exibição: Exibe todos os nós da lista sequencialmente.

Operações em Lista Encadeada

Entendo Vetores e Listas Encadeadas

Python não possui uma implementação nativa para listas encadeadas como em C ou Java, mas podemos implementar uma lista encadeada usando classes.

Implementação de Lista Encadeada

Entendo Vetores e Listas Encadeadas

TAD - Cadeia

No contexto de estruturas de dados, uma cadeia (também conhecida como string) é uma sequência de caracteres armazenados em uma ordem específica.

Cadeias

O Tipo Abstrato de Dados Cadeia define uma estrutura para manipular sequências de caracteres de forma eficiente. Cadeias podem ser vistas como uma coleção ordenada de caracteres de comprimento finito, com as seguintes propriedades:

• Cada caractere tem uma posição na sequência, numerada a partir de 0 (índice base 0) em muitas linguagens de programação.

• A cadeia pode ser de tamanho fixo ou variável, dependendo da implementação.
  

Cadeias

• Cadeias geralmente são imutáveis em muitas linguagens, o que significa que, uma vez criadas, não podem ser modificadas diretamente. No entanto, operações como concatenação ou substituição criam novas cadeias.
  

Cadeias - Implementação

Em um nível mais técnico, uma cadeia pode ser implementada de diversas maneiras, como:

• Vetores (ou arrays) de caracteres: Uma cadeia pode ser representada como um array unidimensional, onde cada posição armazena um caractere.

• Lista encadeada: Outra forma de implementar cadeias é usar listas encadeadas de caracteres, onde cada nó da lista armazena um caractere da cadeia.
  

Cadeias - Implementação : Cuidados a se tomar !

• Imutabilidade: Em muitas linguagens de programação, cadeias são imutáveis. Isso significa que, ao realizar operações como concatenação ou substituição, uma nova cadeia é criada ao invés de modificar a cadeia original. Isso pode ter implicações de desempenho, pois criar novas cadeias repetidamente pode consumir mais memória e tempo de execução.
  

Cadeias - Implementação : Cuidados a se tomar !

• Alocação de Memória: Em linguagens que permitem cadeias mutáveis, como C, a manipulação direta de memória é necessária, e o programador deve ter cuidado com o uso de ponteiros e a alocação/desalocação de memória para evitar vazamentos de memória.

Cadeias - Implementação : Cuidados a se tomar !

• Complexidade Computacional: Operações como a concatenação de cadeias podem ter custo proporcional ao tamanho das cadeias envolvidas. Por exemplo, concatenar duas cadeias de tamanhos m e n pode ter um custo O(m + n). Assim, ao manipular grandes cadeias, é necessário considerar o custo de tempo das operações.

Representação Teórica

Na matemática e na ciência da computação, cadeias (ou strings) são representadas por uma notação formal e padronizada que facilita a descrição de suas propriedades e operações.

​Representando a Cadeia : Alfabeto

O alfabeto de uma cadeia é o conjunto de símbolos ou caracteres que podem ser usados para formar cadeias. O alfabeto é representado geralmente por uma letra maiúscula grega, como:

Σ (Sigma) representa um conjunto finito de símbolos.

Exemplo: Se o alfabeto for Σ = {a, b}, então as cadeias podem ser formadas pelos caracteres a e b.

​Representando a Cadeia

Uma cadeia (ou string) é uma sequência finita de símbolos pertencentes ao alfabeto Σ. Se os símbolos de uma cadeia forem representados como elementos do alfabeto, podemos expressar uma cadeia como:

Uma cadeia w é uma sequência de símbolos w = w₁w₂w₃...wₙ, onde w₁, w₂, w₃,..., wₙ ∈ Σ.

Exemplo: Se Σ = {a, b}, então a cadeia w = abba é composta pelos símbolos de Σ.

​Representando a Cadeia : Comprimento da Cadeia

O comprimento de uma cadeia w, denotado por |w|, é o número de símbolos em w.

Exemplo:

• Se w = abba, então |w| = 4.

• Se w = ε (cadeia vazia), então |w| = 0.

​Representando a Cadeia : Cadeia Vazia

A cadeia vazia (ou string vazia) é uma cadeia que não contém nenhum símbolo. A cadeia vazia é geralmente denotada por:

ε (épsilon) ou às vezes apenas por um símbolo vazio λ.

A cadeia vazia tem comprimento 0, ou seja, |ε| = 0.

​Representando a Cadeia : Operações - Concatenação

A concatenação de duas cadeias u e v, representada como u · v ou simplesmente uv, é uma operação que combina as duas cadeias, anexando os símbolos de v ao final de u.

Exemplo:

• Se u = ab e v = ba, então uv = abba.

• A concatenação de qualquer cadeia w com a cadeia vazia ε resulta na própria cadeia: w · ε = ε · w = w.

​Representando a Cadeia : Operações - Potência

A potência de uma cadeia w, denotada por wⁿ, indica a concatenação da cadeia consigo mesma n vezes. Formalmente:

• w⁰ = ε (a cadeia elevada à potência 0 é a cadeia vazia);

• w¹ = w (a cadeia elevada à potência 1 é a própria cadeia);

• w² = w · w (a cadeia concatenada com ela mesma), e assim por diante.

Exemplo:

• Se w = ab e n = 3, então w³ = ababab.

​Representando a Cadeia : Operações - Reversão

A cadeia reversa ou inversa de uma cadeia w, denotada por wᴿ, é a cadeia obtida ao inverter a ordem dos símbolos em w.

Exemplo:

• Se w = abcd, então wᴿ = dcba.

​Representando a Cadeia : Operações - Subcadeia

Uma subcadeia (ou substring) de uma cadeia w é uma sequência de símbolos que aparece contiguamente em w. Se w = w₁w₂...wₙ, então a subcadeia de w que começa no índice i e termina no índice j (onde 1 ≤ i ≤ j ≤ n) é denotada por w[i:j].

Exemplo:

• Se w = abcd, então w[2:4] = bc.

​Representando a Cadeia : Conjunto de Todas as Cadeias Possíveis

O conjunto de todas as cadeias possíveis sobre um alfabeto Σ é denotado por Σ*. Esse conjunto inclui todas as cadeias de comprimento arbitrário, incluindo a cadeia vazia.

Formalmente:

• Σ* = {ε} ∪ Σ ∪ Σ² ∪ Σ³ ∪ ... (o conjunto de cadeias de comprimento 0, 1, 2, 3, etc.).

​Representando a Cadeia : Exemplo Completo

Dado o alfabeto Σ = {0, 1}, o conjunto Σ* inclui:

• ε (cadeia vazia),

• 0, 1 (cadeias de comprimento 1),

• 00, 01, 10, 11 (cadeias de comprimento 2),

• E assim por diante.

​Representando a Cadeia : Resumo das Notações

• Alfabeto (Σ): Conjunto de símbolos.

• Cadeia (w): Sequência de símbolos de Σ.

• Cadeia vazia (ε): Cadeia sem nenhum símbolo.

• Comprimento de uma cadeia (|w|): Número de símbolos em w.

• Concatenação (uv): Junção de duas cadeias.

• Potência (wⁿ): Cadeia concatenada n vezes.

• Subcadeia (w[i:j]): Subsequência de w entre os índices i e j.

• Cadeia reversa (wᴿ): Cadeia w na ordem inversa.

• Conjunto de todas as cadeias (Σ*): Todas as cadeias possíveis, incluindo a cadeia vazia.

Outras Notações - Notação Big-O

A notação O(n) faz parte de um conceito chamado análise de complexidade de algoritmos e é usada para descrever a eficiência de um algoritmo em termos de tempo de execução ou uso de memória, à medida que o tamanho da entrada cresce. Essa notação é conhecida como notação Big-O e permite classificar algoritmos de acordo com o comportamento de desempenho conforme a quantidade de dados de entrada aumenta.

Principais tipos de complexidade Big-O:

• O(1): Tempo constante — O tempo de execução não depende do tamanho da entrada.

• O(n): Tempo linear — O tempo de execução cresce linearmente à medida que o tamanho da entrada aumenta.

• O(n²): Tempo quadrático — O tempo de execução cresce proporcionalmente ao quadrado do tamanho da entrada.

• O(log n): Tempo logarítmico — O tempo de execução cresce de forma logarítmica em relação ao tamanho da entrada.

• O(n log n): Tempo linear-logarítmico — O tempo de execução cresce de forma proporcional a n log n.

O que significa O(n)?

A notação O(n), especificamente, significa que o tempo de execução ou o uso de memória do algoritmo cresce linearmente com o tamanho da entrada n. Em outras palavras, se o tamanho da entrada n aumentar, o tempo necessário para executar o algoritmo aumentará proporcionalmente.

Exemplo Intuitivo:

Suponha que você tenha uma lista de n números e deseja imprimir todos eles. O tempo que você levará para imprimir os números será proporcional ao tamanho da lista. Se a lista tiver 10 elementos, você fará 10 operações (imprimir cada elemento). Se a lista tiver 100 elementos, você fará 100 operações. Portanto, o tempo de execução desse algoritmo cresce linearmente com o tamanho da entrada, e sua complexidade é O(n).

• Busca Linear em uma Lista: Se você precisar procurar um determinado número em uma lista de n números, a complexidade é O(n), porque no pior caso, você pode precisar verificar todos os elementos da lista até encontrar o número.

• Somar Elementos de um Vetor: Para calcular a soma de todos os elementos de uma lista com n números, o tempo de execução é O(n), porque você precisa visitar cada elemento exatamente uma vez.

​Exemplo Prático

Exercícios Complementares

Dado o alfabeto Σ = {0, 1}, liste todas as cadeias de comprimento 3 que podem ser formadas a partir de Σ.

​Definição de Cadeias

Exercício 1

As cadeias de comprimento 3 são formadas combinando os símbolos de Σ em sequências de 3 símbolos. O número total de cadeias é dado por |Σ|³ = 2³ = 8. As cadeias possíveis são:

• 000, 001, 010, 011, 100, 101, 110, 111

​Definição de Cadeias - Resolução

Exercício 1

Sejam u e v cadeias sobre o alfabeto Σ. Explique que |u · v| = |u| + |v|, onde |u| representa o comprimento de u e |v| o comprimento de v.

Comprimento de Cadeia

Exercício 2

O comprimento de uma cadeia é o número de símbolos que ela contém. Quando concatenamos duas cadeias u e v, o comprimento da nova cadeia u · v será a soma dos comprimentos de u e v, já que estamos apenas unindo as duas sequências sem modificar o número de símbolos. Logo, |u · v| = |u| + |v|.

Comprimento de Cadeia - Resolução

Exercício 2

Seja w = a₁a₂...aₙ uma cadeia de comprimento n sobre o alfabeto Σ. Mostre que a inversa de w (denotada por wᴿ) é dada por wᴿ = aₙaₙ₋₁...a₁.

Inversão de Cadeia

Exercício 3

A inversa de uma cadeia w = a₁a₂...aₙ é obtida reorganizando os símbolos de w na ordem inversa, ou seja, começando do último símbolo aₙ até o primeiro símbolo a₁. Portanto, a cadeia reversa é wᴿ = aₙaₙ₋₁...a₁.

Inversão de Cadeia - Resolução

Exercício 3

Seja w = "abcdef". Determine as subcadeias w[2:5] e w[0:3] usando a notação matemática de fatiamento de cadeias.

Subcadeia

Exercício 4

• w[2:5]: A subcadeia começa no índice 2 e vai até o índice 4 (o índice final é excluído). Logo, a subcadeia é "cde".

• w[0:3]: A subcadeia começa no índice 0 e vai até o índice 2. Logo, a subcadeia é "abc".

Subcadeia - Resolução

Exercício 4