Estruturas de dados

Prévia do material em texto

3ºSemestre
Estruturas de dados lineares
Professor Edeilson Ferreira da Silva
· Estruturas de Dados Estáticas
Os algoritmos são elaborados de modo que possam receber os dados de entrada de um problema e, por meio de uma sequência de instruções, transformar a entrada em uma saída pretendida
O computador armazena os dados que serão manipulados pelos programas em uma memória principal. Veja que um programa de computador é a implementação de um algoritmo, em uma linguagem de programação específica.
A maioria das linguagens de programação dispõe de um conjunto de tipos de dados, os quais são denominados de tipos de dados primitivos. Cada tipo de dado primitivo demanda uma quantidade específica de bits para o seu armazenamento.
· A memória
O armazenamento de dados em um computador pode considerar diferentes tipos de dispositivos.
utilizam a RAM como memória principal ou primária. Assim, os dados que serão processados estarão armazenados, de maneira temporária, na memória RAM, visto que se trata de uma memória volátil. A RAM é um dispositivo de armazenamento eletrônico de dados que suporta as operações de leitura e escrita de dados. Podemos considerar a RAM, daqui em diante referida somente como memória principal, como uma grade bidimensional, na qual cada interseção entre linha e coluna contém uma unidade de armazenamento.
A memória principal trata-se de uma memória de acesso rápido, e cujo acesso é feito por meio de um endereçamento direto de cada unidade de armazenamento.
As unidades de armazenamento podem ser disponibilizadas para uso individualmente ou em conjunto. Quando um programa de computador precisa de um espaço de memória para o armazenamento de dados, ele faz uma alocação de memória.
Existem duas formas de se fazer a alocação de memória, as alocações estática e dinâmica
A alocação estática é feita de maneira prévia, antes do tempo de execução. Desse modo, a alocação estática reserva um espaço de memória contíguo (sequencial) com tamanho previamente definido. Isso implica uma estrutura mais simples de ser gerenciada.
A alocação dinâmica de memória é feito em tempo de execução. Assim, à medida que o processo demanda mais espaço na memória, a alocação de um bloco de memória pré-determinado1 é feita, de modo a atender especificamente a essa demanda.
· Vetores
Um vetor ou array é uma estrutura de dados que armazena, podemos ter um vetor de vetores, o que caracterizaria um vetor bidimensional (matriz). Nesse sentido, podemos ter vetores de muitas dimensões (multidimensionais)
A alocação de um vetor é feita a partir da definição do tipo específico de dado que será armazenado, bem como da quantidade de elementos a ser armazenada. Assim, seráreservada uma quantidade específica de bits contíguos na memória principal. O acesso aos elementos no vetor é facilitado por conta de sua organização sequencial na memória.
As operações sobre um vetor podem ser feitas com a utilização do seu nome e do indexador objetivo.
o acesso às posições de um vetor sempre será feito a partir do seu respectivo nome, associado ao indexador que queremos (o indexador será declarado entre colchetes).
· Fila estática
O vetor, como uma estrutura de dados estática, pode ser utilizado para a implementação de outras estruturas similares. Nesse sentido, a fila é uma dessas estruturas e considera um vetor estático e uma determinada regra de acesso. Uma regra de acesso define a forma pela qual podemos realizar manipulações sobre a estrutura.
*FIFO (First In First Out) a regra que diz: o primeiro que entra é o primeiro que sai. Desse modo, como em uma fila de banco, o primeiro elemento a entrar na fila será o primeiro a sair dela.
Um ponto de acesso é a cabeça da fila, o qual denominaremos de head, e é a partir desse ponto que os elementos são retirados da fila. Outro ponto de acesso é o final da fila, o qual denominaremos de tail, onde os elementos entram na fila.
· Algoritmo 1 – Função para verificar se uma fila v está cheia
O Algoritmo 1 descreve os passos para verificar se a fila está cheia
· Algoritmo 2 – Procedimento para inserir o valor x na fila v
O Algoritmo 2. O procedimento Enqueue() recebe, como parâmetros, o vetor V e um valor x que será inserido na fila. A operação de remoção de um elemento da fila é denominada dequeue
· Algoritmo 3 – Função para verificar se uma fila v está vazia
O Algoritmo 3, descreve os passos para que possamos verificar se uma fila está vazia.
· Algoritmo 4 – Função para remover um elemento da fila
A remoção de um elemento na fila é feita na posição indicada pelo ponteiro head. O Algoritmo 4 descreve os passos que compõem a função Dequeue (). Após verificar se a fila não está vazia, o elemento na posição head é atribuído a uma variável auxiliar.
*Quando tentamos inserir um novo elemento em um fila cheia, temos um erro de overflow. Por outro lado, quanto tentamos remover um elemento de uma fila vazia, temos um erro de underflow.
· Fila estática circular
A fila circular resolve o problema das posições ociosas, sem que seja necessário realizar movimentações adicionais na fila. Assim, o limite de armazenamento será igual ao tamanho do vetor considerado para a implementação da fila.
· Pilha estática
A pilha é uma estrutura de dados na qual as operações são realizadas em um único ponto. As operações básicas que podem ser realizadas sobre uma pilha são a inserção e a remoção de elementos, denominaremos essas operações de push e pop, respectivamente. A regra de acesso a uma pilha descreve que os elementos serão retirados na ordem inversa em que foram inseridos. Essa regra é denominada LIFO (Last In First Out) e significa que o último que entra será o primeiro a sair.
ponto de acesso à pilha é denominado topo, onde todas as operações são realizadas. Assim, os elementos serão inseridos no topo da pilha e a remoção só será possível sobre o elemento que, também, está posicionado no topo.
· Algoritmo 5 – Função para verificar se uma pilha está cheia
A operação push, responsável pela inserção de elementos, deve ser realizada somente se houver espaço para o armazenamento. o Algoritmo 5 descreve os passos para a implementação da função IsFull () no contexto de uma pilha, implementada sobre um vetor de inteiros.
· Algoritmo 6 – Procedimento para inserir o valor x na pilha
Após a verificação da ocupação da pilha, a operação Push () pode ser executa para a inserção de elementos nessa estrutura. Essa operação recebe um elemento a ser inserido na pilha, na posição estabelecida pelo valor da variável topo, atualizando, em seguida, essa variável. O Algoritmo 6 descreve os passos que compõem essa operação, lembrando que estamos considerando a variável topo como global.
· Algoritmo 7 – Função para verificar se uma pilha está vazia
é preciso verificar se a pilha está vazia antes de proceder com a retirada de elementos. A função que é responsável por essa verificação é descrita no Algoritmo 7.
· Algoritmo 8 – Função para remover o valor posicionado no topo da pilha v
A operação de remoção, aqui denominada pop, retira da pilha o elemento que está armazenado na posição indicada pela variável topo, após a verificação da existência de elementos na pilha, a qual é feita pela função IsEmpty. Assim, o Algoritmo 8 descreve os passos que compõem a função Pop.
A operação de remoção, aqui denominada pop, retira da pilha o elemento que está armazenado na posição indicada pela variável topo, após a verificação da existência de elementos na pilha, a qual é feita pela função IsEmpty. Assim, o Algoritmo 8 descreve os passos que compõem a função Pop.
se no topo está o símbolo [ e o próximo símbolo lido é ], então, como eles são simétricos, o algoritmo retira o símbolo do topo e realiza a leitura de um novo símbolo.
Se ao final da entrada a pilha estiver vazia, o algoritmo aceita a entrada, decidindo que a sequência de símbolos é bem formulada, ou a rejeita, caso contrário.
· Algoritmos de Classificação e Pesquisa I
o problema de ordenação consiste em transformar uma entrada em uma saída, ambas bem especificadas. Desse modo, o algoritmo que resolveesse problema deve descrever os passos necessários para que a entrada seja transformada na saída que pretendemos. Assim, Cormen (2009) define a entrada e a saída para um problema de ordenação da seguinte forma:
• Entrada: uma sequência de n números 
• Saída: uma permutação da entrada 
Veja que as descrições da entrada e da saída são genéricas, onde cada x representa um valor na sequência. Especificamente para a saída, um valor anterior deve ser menor ou igual ao valor posterior.
· Ordenação pelo Método de Bolhas (Bubble Sort)
O algoritmo de ordenação pelo método de bolhas, popularmente conhecido como Bubble Sort, é de simples aplicação e entendimento, porém ineficiente. Ele considera a troca repetitiva de elementos vizinhos que estão fora de ordem
· Algoritmo 1 – Ordenação pelo método de bolhas (Bubble Sort)
Existem diferentes versões para o algoritmo Bubble Sort, algumas localizam o maior valor e o levam até o final do vetor, o que é o inverso do que a nossa versão faz. Note que, independentemente da versão, o Bubble Sort percorre todo o vetor, identifica o menor ou o maior valor, segrega esse valor em uma das extremidades e reduz o tamanho do vetor.
O algoritmo Bubble Sort compara todos os valores de sua entrada aos pares, trocando os valores que estão fora de ordem. Essa comparação pode ser feita do final para o início do vetor, como fizemos aqui, ou do início para o final, como é mais comumente feito. Independentemente do sentido da execução, não há diferença sobre a eficiência de ambas as versões. Ambas são ineficientes.
· Ordenação por Inserção (Insertion Sort)
O algoritmo Insertion Sort é o mais eficiente dos algoritmos de ordenação que gastam tempo proporcional a uma função quadrática, para instâncias pequenas.
· Algoritmo 2 – Ordenação por inserção (Insertion Sort)
os algoritmos de ordenação selecionados têm em comum o fato de considerarem uma abordagem iterativa em suas definições, em vez de uma abordagem recursiva.
Outra característica comum a esses algoritmos é que todos são ineficientes para grandes instâncias de entrada, ou seja, quando precisamos ordenar muitos elementos, esse algoritmos não são nossa melhor escolha.
 A comparação entre diferentes algoritmos de ordenação possibilita a compreensão de estratégias distintas, que certamente serão úteis em aprimorar nossa capacidade de desenvolver nossas próprias soluções.
· Ordenação por Seleção (Selection Sort)
O algoritmo Selection Sort é um dos mais eficientes para a ordenação de pequenos conjuntos de elementos. Outra característica importante é o fato de o Selection Sort não utilizar uma estrutura auxiliar para o armazenamento dos dados do vetor e, dessa forma, consome pouca memória em seu processo de execução. O Algoritmo 3 descreve os passos pertinentes ao Selection Sort.
· Algoritmo 3 – Ordenação por seleção (Selection Sort)
Quando analisamos os algoritmos Bubble Sort, Insertion Sort e Selection Sort, vemos que eles consideram diferentes estratégias e que cada uma delas pode ter mais ou menos operações. As operações, também, consomem tempos diferentes para serem realizadas.
e podemos ter algoritmos que realizam a mesma tarefa, como é o caso dos algoritmos de ordenação, mas fazem isso de maneiras diferentes. Essas diferenças entre as estratégias, consideradas pelos algoritmos, impactam no tempo que será necessário para a execução da tarefa.
O primeiro caso considera um vetor em ordem crescente, isso é o que chamamos de melhor caso. Para o melhor caso não serão realizadas trocas, em nenhum dos algoritmos, visto que os valores já estão em suas posições corretas, de acordo com o objetivo do algoritmo. Há somente a realização de comparações que verificam as respectivas posições dos valores no vetor. Quando o vetor tem seus valores organizados em ordem decrescente, dizemos que temos o pior caso. Nesse contexto, o pior caso é quando todos os valores serão reposicionados, considerando um vetor com um número par de elementos. O último caso, conhecido como caso médio, é quando os valores estão posicionados de forma aleatória no vetor. Esse é o caso mais comum de ser observado.
os algoritmos que realizam uma mesma tarefa podem ter desempenhos diferentes, o que, para grandes instâncias de entrada, pode inviabilizar seu uso.
· Pesquisa Sequencial
processo de pesquisa ou busca de um determinado valor em uma lista é uma operação cotidiana, no âmbito da computação. Existem, basicamente, duas formas de se realizar uma pesquisa.
A pesquisa sequencial considera um valor x a ser procurado e uma lista de valores V onde será realizada a pesquisa.
O Algoritmo 4 descreve a função Busca(), que retorna um valor lógico (verdadeiro ou falso), indicando a existência ou não do valor no respectivo vetor. A função recebe como parâmetros de entrada o valor a ser pesquisado e o vetor de elementos.
· Algoritmo 4 – Algoritmo para pesquisa sequencial
A função Busca() tem um único laço que é responsável por percorrer todo o vetor, considerando a ordem em que os valores estão armazenados. Para cada elemento no vetor, a função faz uma comparação entre o valor objetivo (x) e o elemento correspondente.
· Algoritmo 5 – Algoritmo para pesquisa sequencial com a utilização de sentinela
A função BuscaComSentinela() adiciona o valor procurado x na posição final do vetor, lembrando que devemos prever essa posição adicional no vetor.
Uma alternativa à busca sequencial é a busca binária. Na busca binária, o número de comparações realizadas é muito menor, tornando o processo de pesquisa muito mais eficiente. Porém é necessário que o vetor esteja ordenado previamente para se executar a busca binária. Veremos nas próximas unidades os detalhes referentes a esse tipo de busca
Os algoritmos iterativos são aqueles que repetem um conjunto de instruções diversas vezes.
Outro ponto em comum entre os algoritmos Bubble Sort, Selection Sort e Insertion Sort são as respectivas eficiências computacionais. Por eficiência computacional considere o tempo que o algoritmo demora em produzir a saída correspondente. Esses algoritmos são úteis quando temos poucos elementos a serem ordenados. Outra possibilidade é a utilização de algum desses algoritmos associados a outros algoritmos mais eficientes.
· Algoritmos de Classificação e Pesquisa II
A iteração, no contexto da programação de computadores, se refere à repetição de uma ou mais instruções.
A recursão é uma abordagem na qual a execução de um determinado procedimento prevê uma nova execução do mesmo procedimento.
Os algoritmos recursivos possuem uma chamada interna a si mesmo. Assim, uma nova execução do algoritmo se inicia, ficando a primeira execução aguardando a finalização da segunda. Esse processo pode ser repetido diversas vezes até que um determinado caso base ocorra. A recursividade é utilizada em algoritmos que utilizam uma estratégia denominada divisão e conquista. Essa estratégia consiste em dividir um problema, sucessivas vezes, até que ele seja pequeno o suficiente e possa ser resolvido de forma direta
· Recursividade
A recursividade é a capacidade que uma função apresenta de chamar a si mesma. A ideia fundamental por trás de um algoritmo recursivo é a transformação do problema (instância) original em outro menor ou mais simples, de modo que seu tamanho ou sua simplicidade permita uma solução direta, sem que haja a necessidade de recorrer novamente ao algoritmo.
 A condição de parada de um algoritmo recursivo é denominada de caso base. Quando, no processo recursivo, atinge-se o caso base, o algoritmo interrompe as chamadas recursivas e retorna a solução direta, para esse caso, à instância que realizou a chamada, até que a solução para o problema original seja obtida. Todo algoritmo recursivo terá uma versão iterativa para executar a mesma tarefa. Quando comparamos as duas abordagens, observamos que os algoritmos recursivos são mais simples de compreender e apresentam um número menor de instruções. Além disso, existem tipos de problema que apresentam características recursivas, o que sugere uma solução na mesma abordagem.
· Algoritmo1 – Algoritmo recursivo para o cálculo do fatorial de um número
Um algoritmo recursivo, para o cálculo do fatorial de um número, poderia ter suas instruções descritas como no Algoritmo 1
A sequência, ou série, de Fibonacci tem os valores iniciais 0 e 1, o que se caracteriza como o caso base da recursão. Os demais valores são obtidos a partir da soma dos dois anteriores, essa é a regra de formação. A recursividade, para esse caso, pode ser evidenciada na representação formal do problema, a qual define uma função que recebe a posição desejada e retorna o valor da posição.
Cada chamada gera um novo “ramo” de computação, que é resultado da nova chamada à função. Nesse contexto, a execução que contém a chamada fica aguardando a finalização da execução de todas as chamadas que foram derivadas dela. Assim, a execução chamadora será finalizada a partir dos resultados retornados pelas chamadas derivadas.
Uma característica importante dos algoritmos recursivos é que eles podem realizar várias chamadas para uma mesma instância.
· Algoritmo 2 – Algoritmo recursivo para o cálculo do -ésimo valor da série de Fibonacci
O algoritmo recursivo que retorna o valor da n-ésima posição da série de Fibonacci
*Quick Sort. Esse algoritmo considera a abordagem recursiva para ordenar um vetor. A estratégia do Quick Sort resulta em um desempenho, em termos de tempo de execução, muito melhor do que os desempenhos dos algoritmos de ordenação
· Ordenação pelo Método Rápido (Quick Sort)
O Quick Sort é, possivelmente, o algoritmo de ordenação mais utilizado no mundo e apresenta um desempenho muito bom em termos de tempo de execução. Esse algoritmo utiliza o paradigma da divisão e conquista para ordenar um vetor típico 
A implementação do Quick Sort considera dois procedimentos. O primeiro procedimento, aqui denominado Quicksort(), reorganiza o vetor V em dois subvetores. O segundo procedimento, denominado Partition(), é a chave para que o procedimento Quicksort() possa reorganizar o vetor.
· Algoritmo 3 – Algoritmo Quick Sort
O Algoritmo 3 descreve as instruções que compõem o procedimento Quicksort().
· Algoritmo 4 – Procedimento Partition
O procedimento Partition() recebe como parâmetros de entrada o vetor V e os indexadores p e r, que representam a primeira e a última posições no vetor, respectivamente. O valor da última posição no vetor é reservado por meio de sua atribuição à variável x
O algoritmo de ordenação pelo método rápido é, muitas vezes, a melhor opção para ordenação de arranjos. Isso se deve ao seu ótimo desempenho médio, fazendo com que o Quick Sort seja o algoritmo mais considerado entre aqueles pertencentes à classe dos algoritmos de ordenação.
· Ordenação por Mistura (Merge Sort)
O algoritmo de ordenação por mistura ou intercalação, mais conhecido como Merge Sort, também considera a abordagem da divisão e conquista, assim como o seu correlato Quick Sort. O princípio fundamental do Merge Sort está relacionado com a combinação de dois subvetores ordenados em um único vetor ordenado.
· Algoritmo 5 – Algoritmo de ordenação pelo método de intercalação (Merge Sort), esse procedimento é parte do algoritmo completo
O Algoritmo 5 descreve as instruções para o procedimento Merge(), que realiza a combinação de vetores previamente ordenados. Esse procedimento considera como parâmetros de entrada um vetor V, no qual os valores à esquerda da posição q estão ordenados e os valores à direita de q também estão ordenados. As variáveis p e r contêm as posições inicial e final do vetor, respectivamente.
A combinação dos subvetores é feita a partir da seleção do menor valor entre aqueles que estão em suas posições iniciais, de modo que sempre o menor valor será inserido primeiro no vetor. Veja que, como os subvetores estão ordenados, um valor nas posições iniciais dos subvetores é sempre menor ou igual aos valores subsequentes.
O processo de seleção do menor valor e substituição do valor inicial de cada subvetor é repetido até que todos os valores sejam selecionados. Quando se atinge o valor ∞, em um dos subvetores, a opção será sempre pela seleção dos valores no outro subvetor; veja que o valor selecionado é sempre o menor entre os subvetores e, desse modo, qualquer valor será sempre menor que ∞.
O procedimento Merge() é funcional somente quando os subvetores estejam ordenados. Essa premissa não parece ser muito útil, visto que se espera que o algoritmo faça a ordenação, mas, nesse caso, a ordenação é um pré-requisito. Nesse contexto, precisamos de um procedimento complementar que resolva a questão da pré-ordenação.
· Algoritmo 6 – Algoritmo de ordenação pelo método de intercalação (Merge Sort), esse procedimento é parte do algoritmo completo
O procedimento Mergesort(), descrito no Algoritmo 6, realiza a divisão do vetor de entrada V, de forma recursiva, até que cada subvetor tenha somente um elemento.
Podemos dizer que o algoritmo Mergesort() desmembra o vetor em subvetores ordenados e com uma única posição. Assim, o procedimento Merge() pode ser considerado sobre os subvetores, pois eles são ordenados. A recomposição do vetor a partir do procedimento Merge() resultará em sua ordenação.
Quick Sort, o Merge Sort apresenta um desempenho melhor que os algoritmos de ordenação discutidos na unidade anterior. A estratégia da divisão e conquista, baseada na recursão, possibilita esse desempenho superior, em termos de tempo de execução.
· Pesquisa Binária
A pesquisa sequencial compara o elemento, para o qual queremos verificar a pertinência, com todos os elementos existentes no vetor de busca.
A busca binária é realizada sobre um vetor previamente ordenado, essa é a premissa básica para que possamos melhorar a eficiência da nossa busca.
a base da pesquisa ou busca binária. A premissa é que se realize a busca sobre um vetor previamente ordenado, de modo que, a cada passo, possamos desconsiderar metade do vetor. Esse procedimento reduz substancialmente o número de comparações que serão realizadas até que se encontre o valor procurado.
· Algoritmo 7 – Algoritmo para busca binária
O Algoritmo 7 descreve as instruções que compõem o algoritmo de busca binária. Os parâmetros de entrada do BuscaBinaria( ) são: o valor a ser procurado (x), um vetor (V) previamente ordenado, as posições inicial (p) e final (r) do vetor.
O processo de busca se repetirá até que a posição que contém o valor procurado seja identificada e retornada como resposta.
· Estruturas de Dados Dinâmicas
estruturas de dados que resultado de alocação dinâmica de memória.
• na alocação estática, os bytes são alocados de forma contígua (sequencial) na memória; na alocação dinâmica, os bytes são distribuídos pela memória;
• na alocação estática, a quantidade de objetos que serão armazenados é conhecida previamente; na alocação dinâmica, não é necessária essa informação prévia;
• a alocação estática é feita em tempo de compilação, enquanto a alocação dinâmica é feita em tempo de execução.
Os objetos que são alocados dinamicamente são compostos pelos valores que queremos armazenar e, pelo menos, um membro adicional que armazenará um endereço de memória
· Listas Ligadas
A lista ligada é uma estrutura dinâmica de dados cujo objetivo é armazenar elementos de forma sequencial. Nesse contexto, o elemento da lista é armazenado em conjunto com o endereço para o próximo elemento. Esse conjunto é denominado célula.
As operações de consulta são aquelas que retornam informações a respeito do conjunto, tais como: (i) busca por um determinado elemento, identificar o (ii) menor ou (iii) maior valor no conjunto e retornar o (iv) sucessor ou o (v) predecessor de um determinado elemento. As operações modificadoras são aquelas que alteram a composição do conjunto. Essas operações se referem à (i) inserção ou (ii) remoção de um determinado elemento do conjunto.
· Algoritmo 1 – Algoritmo para busca em uma lista ligada
operação de busca em uma lista ligada tem suas instruções descritas pelo Algoritmo 1. A operação de inserção em uma lista ligada é feita de maneira simples, primeiro se deve alocar uma novacélula (nova). O elemento que será inserido na fila é atribuído ao membro nova.valor e o membro nova.ponteiro deverá conter o endereço da primeira posição atual da lista. Por fim, o endereço da nova célula será a “cabeça” da lista ligada.
· Algoritmo 2 – Algoritmo para inserção no início em uma lista ligada
O procedimento InserirLigada( ), que tem suas instruções descritas no Algoritmo 2, recebe como parâmetros de entrada o endereço da lista ligada (L) e um elemento que deverá ser inserido (k). Inicialmente, é feita a alocação de memória para uma nova célula , cujo endereço é armazenado na variável nova. Essa nova célula receberá o elemento a ser inserido no membro nova.valor e o membro nova.ponteiro receberá o endereço do início da lista ligada atual, ou seja, antes da inserção ser realizada
· Algoritmo 3 – Algoritmo para remoção em uma lista ligada
Os passos do algoritmo RemoverLigada( ) são descritos no Algoritmo 3. Nesse caso, os parâmetros de entrada são o endereço da lista ligada (L) e o valor que se quer remover (k). O endereço do primeiro elemento na lista é copiado para a variável p e o endereço do segundo elemento, que é descrito pelo membro L.ponteiro, é copiado para a variável q . Desse modo se tem os endereços de memória do elemento atual e de seu sucessor.
para obter o sucessor, basta retornar o endereço armazenado no membro ponteiro do elemento identificado. Para o caso da operação predecessor, devemos manter o endereço do elemento atual e do próximo elemento. Assim, utilizaremos o valor do próximo elemento para a busca pelo elemento objetivo e, quando identificado, retorna o endereço do elemento atual.
**Na alocação estática de memória, os elementos em um arranjo estão, de fato, organizados de forma sequencial. Na alocação dinâmica, o sequenciamento é feito por meio dos ponteiros.
· Listas Duplamente Ligadas
As s lista
s duplamente ligadas consideram, para a composição de uma célula, no mínimo, três membros. Um dos membros é utilizado para o armazenamento do elemento na lista, os outros dois são utilizados para armazenar os endereços do elemento anterior e posterior. A configuração de uma lista duplamente ligada apresenta como vantagem melhor acessibilidade aos elementos na lista. Porém é preciso considerar que será utilizado o dobro de ponteiros e isso acarreta maior quantidade de trabalho para a sua manutenção.
· Algoritmo 4 – Algoritmo para inserção em uma lista duplamente ligada
O Algoritmo 4 descreve as instruções que compõem o procedimento InserirDLigada( ). A operação de remoção em uma lista duplamente ligada é feita a partir da identificação do endereço de memória da célula que se quer remover. Desse modo, a remoção segue de forma distinta daquela apresentada para uma lista ligada simples.
A operação de remoção consiste em “conectar” as células apontadas por q.anterior e q.posterior, de modo que a célula apontada por q seja removida da lista.
· Algoritmo 5 – Algoritmo para remoção em uma lista duplamente ligada
O primeiro passo para a operação de remoção é criar um ponteiro p e atribuir a ele o endereço do membro q.anterior, esse passo é descrito na linha 5 no Algoritmo 5
Podemos ter uma lista ligada circular, na qual o membro “ponteiro” da última célula contém o endereço da primeira. Além disso, podemos implementar uma lista duplamente ligada circular, a qual apresenta as mesmas características da lista ligada circular simples com a utilização de um segundo ponteiro para a célula anterior.
· Fila dinâmica
Uma fila armazena elementos de acordo com uma regra de acesso específica. A sigla FIFO (First In First Out) define a regra de acesso para uma fila como o primeiro elemento que entra será o primeiro a sair da fila. Como em outras estruturas de dados, a fila suporta algumas operações para a manipulação de seus elementos.
**As regras de acesso para estruturas como a fila ou a pilha são as mesmas, independentemente de considerarem um arranjo estático ou uma lista dinâmica. A diferença está na forma de manipular as estruturas.
. Em uma estrutura estática, o limite de armazenamento é dado pelo tamanho da fila, o qual foi definido previamente. A fila dinâmica não apresenta essa limitação, visto que sempre será possível alocar mais espaço de memória, em tempo de execução, para o armazenamento de um novo elemento. De fato, o limite para a fila dinâmica está restrito à disponibilidade de memória.
· Algoritmo 6 – Algoritmo para inserção em uma fila dinâmica
icialmente, é alocada uma nova célula e seu endereço é atribuído à variável ponteiro nova. Os membros “valor” e “ponteiro”, na nova célula, recebem os valores a serem inseridos na fila e Null, essas atribuições são descritas no Algoritmo 6.
A operação de remoção de um elemento em uma fila dinâmica considera a célula indicada pelo ponteiro head. Isso está de acordo com a regra de acesso às filas, que diz que as remoções devem ser feitas no início da fila.
A remoção somente poderá ser realizada mediante a existência de elementos na fila; assim, esta verificação é a primeira instrução do algoritmo (linha 1). Caso haja elementos na fila, o valor desse elemento é reservado, por meio da sua atribuição à variável x (linha 2).
· Algoritmo 7 – Algoritmo para remoção em uma fi la dinâmica
A instrução seguinte se refere à atualização do início da fila. O novo endereço de início da fila é aquele armazenado no membro “ponteiro” da célula que será removida.
· Pilha Dinâmica
a fila, a pilha é uma estrutura de dados que apresenta uma regra de acesso específica. A sigla LIFO (Last In First Out) descreve a regra de acesso à pilha como o último elemento que entra é o primeiro que sai.
· Algoritmo 8 – Procedimento para inserir o valor na pilha dinâmica P
O membro nova.ponteiro recebe o valor armazenado no membro P.ponteiro, que, no caso, é igual a Null, por se tratar do primeiro elemento inserido. A atualização dos ponteiros é finalizada com a atribuição do endereço da célula nova ao membro P.ponteiro, de modo a “conectar” a “cabeça” da pilha ao primeiro elemento inserido.
A operação de desempilhar (Pop( )) somente deve ser realizada a partir da existência de elementos na pilha. A função IsEmpty( ) realiza a verificação da existência de elementos na pilha por meio do retorno do valor lógico da expressão P.ponteiro = Null.
· Algoritmo 9 – Função para remover o valor posicionado no da pilha V
Após a reserva do valor desempilhado, o ponteiro para o topo da pilha (P.ponteiro) é atualizado, passando a apontar para o segundo valor, indicando o novo topo
· Algoritmos de Classificação em Estruturas Dinâmicas
A ideia fundamental, por trás da versão dinâmica do Insertion Sort, é a remoção de um elemento da lista dinâmica inicial e inseri-lo em uma nova lista em sua posição correta.
· Algoritmo 10 – Algoritmo Insertion Sort para ordenar uma lista dinâmica
O procedimento Inserir( ) cria dois novos ponteiros, p e q, que indicarão a posição inicial da nova lista e a posição de inserção do elemento x, respectivamente
· Algoritmo 11 – Procedimento auxiliar para inserção ordenada em uma lista dinâmica
somente os ponteiros em cada célula são atualizados de modo a sequenciar os elementos corretamente.
O algoritmo InsertionSort( ) finaliza quando todos os elementos são retirados da lista inicial e inseridos, na posição correta, na nova lista.
· Pesquisa em Estruturas Dinâmicas
A pesquisa sequencial é realizada percorrendo todo o arranjo e comparando cada elemento com aquele que é procurado. 
Realizar a pesquisa sequencial em uma estrutura dinâmica, O Algoritmo 1 descreve os passos para a realização de busca em uma lista ligada. Veja que não há grandes diferenças ao compararmos com a busca sobre um arranjo
a pesquisa binária. Vimos que esse tipo de pesquisa requer um arranjo ordenado.
A busca binária realizada sobre uma lista ligada é mais problemática comparada àquela realizada sobre um arranjo estático. a identificação do ponto médio em uma lista ligada depende da realização do percurso por todos os elementos na lista.
· Algoritmos de Classificação em Tempo LinearO Bubble Sort, por exemplo, percorre todo o arranjo comparando pares contíguos de elementos de modo a isolar o maior ou menor elemento, dependendo da versão do algoritmo, em uma das extremidades do arranjo.
o algoritmo Insertion Sort seleciona um elemento no arranjo, de modo a dividi-lo em dois subarranjos: um ordenado à esquerda e outro não ordenado à direita. O elemento selecionado é comparado com todos os elementos no subarranjo à esquerda, buscando por sua posição ordenada nesse segmento.
Os algoritmos de classificação em tempo linear são aqueles que não realizam comparações entre todos os elementos no arranjo. Assim, o número de instruções que são realizadas é proporcional à quantidade de elementos pertinentes ao arranjo. 
· Ordenação por Contagem (Counting Sort)
O algoritmo de ordenação por contagem, ou Counting Sort, executa um número de instruções proporcional a n. A premissa para esse algoritmo é que a entrada seja um arranjo de inteiros maiores ou iguais a 0 e menores ou iguais a k. Nesse sentido, é preciso que se conheça previamente o maior valor no arranjo.
O algoritmo Counting Sort ordena um arranjo de entrada em tempo linear, porém não se pode ignorar as premissas que possibilitam esse desempenho. O arranjo de entrada deve ser composto por valores inteiros na faixa de 0 até k. Essa premissa pode inviabilizar a utilização do algoritmo em determinados contextos. 
Uma aplicação particular do algoritmo Counting Sort é quando temos que ordenar números compostos por vários dígitos. Essa estratégia era utilizada para a ordenação de cartões perfurados nos primórdios da computação. A estratégia consiste em ordenar cada dígito do número individualmente, iniciando pelo dígito menos representativo.
 A ordenação digital considera algum algoritmo de ordenação estável para ordenar cada digito. Desse modo, quando a ordenação for feita sobre o próximo dígito mais representativo e esses forem iguais, a ordenação sobre o dígito anterior garante que os elementos ocupem as posições corretas.
*Um algoritmo de ordenação é estável quando a ordem original de elementos de mesmo valor é mantida após a execução do algoritmo. O algoritmo Counting Sort é estável.
Apesar de, aparentemente, o algoritmo Counting Sort ser adequado para a ordenação digital, seu processo de execução prevê a ordenação em outro arranjo, isso pode ser uma característica desfavorável à sua aplicação. Há de se considerar diferentes aspectos associados ao contexto da implementação para a escolha do algoritmo de ordenação ideal.
· Ordenação por Balde (Bucket Sort)
Assim como ocorre no algoritmo de ordenação por contagem, ou Counting Sort, o algoritmo de ordenação por balde, ou Bucket Sort, também considera ou assume algo sobre a entrada.
· Algoritmo 2: Algoritmo Bucket Sort
Os algoritmos de ordenação em tempo linear ao tamanho da entrada, como o Counting Sort e o Bucket Sort, são sensíveis às premissas sobre a entrada e não oferecem o mesmo desempenho quando as premissas não são observadas.
No caso do Bucket Sort a principal premissa é a distribuição uniforme dos elementos no arranjo de entrada.
· Fundamentos de Análise de Complexidade de Algoritmos
A base da análise dos algoritmos está na contagem do número de instruções que são executadas por eles. Cada instrução demora certo tempo para ser realizada, assim, quanto maior for o número de instruções, tanto maior será o tempo de execução.
O crescimento do número de instruções é dependente da variável n, sempre que n cresce T(n) também cresce de forma linear. Assim, podemos dizer que o crescimento do número de instruções executadas no laço é definido por T(n) = n, ou seja, o coeficiente que multiplica n e a unidade adicional, Os algoritmos Counting Sort e Bucket Sort são algoritmos de ordenação em tempo linear, ou seja, o número de instruções executadas é proporcional a T(n) = n. Isso significa que o tempo de execução aumenta linearmente com o número de elementos a serem ordenados. Algoritmos lineares são muito bons, do ponto de vista da eficiência computacional
Os algoritmos de tempo quadrático são menos eficientes que os algoritmos de tempo linear. Os algoritmos Bubble Sort e Insertion Sort são algoritmos de tempo quadrático, portanto, são menos eficientes que os algoritmos Counting Sort e Insertion Sort.
tempo que um algoritmo demora em terminar sua execução está ligado ao tamanho de sua entrada. A ligação entre o tamanho da entrada e o tempo para execução é definida por uma função que descreve a forma como o tempo de execução cresce de acordo com o aumento do tamanho da entrada.
a análise de complexidade de algoritmos é a área que estuda o tempo que os algoritmos demoram em finalizar sua execução. Nesse contexto, a análise de complexidade não está interessada em apresentar o número de instruções executadas ou o tempo que isso vai demorar. O objetivo da análise de complexidade é fornecer uma função que descreva o padrão de crescimento do tempo de execução dado o tamanho da instância de entrada. Existem diferentes funções que descrevem os tempos de execução mais comuns observados para algoritmos.
A contagem de instruções executadas em cada linha do algoritmo é uma tarefa que permite calcular de maneira precisa o número de instruções que são executadas por um algoritmo. Na maior parte das vezes, estamos interessados em tamanhos de entrada grandes e, para esses casos, não importa a precisão do número de instruções, mas, sim, o padrão de crescimento desse número. Por conta disso, as constantes multiplicativas e os termos de ordem mais baixa são desconsiderados quando tratamos com entradas grandes cujo número de instruções executadas será dominado pelo termo de ordem mais alta.
Denominamos eficiência assintótica a análise do tempo de execução dos algoritmos, quando o tamanho da instância de entrada é suficientemente grande, de modo que apenas a ordem de crescimento do tempo de execução seja relevante.
_______________________________