Capítulo 2 Princípios de estruturas de dados - DCA-Wikicalhau.dca.fee.unicamp.br/wiki/images/5/5b/Cap2.pdf · 33 Princípios de estruturas de dados ocupada na coleção (Figura

Capítulo 2

Princípios de estruturas de dados

Em diversos contextos, disciplinas associadas à programação recebem a denomi-nação de “processamento de dados”. Esta denominação não é gratuita — de fato,embora seja possível criar procedimentos que não manipulem nenhum dado, taisprocedimentos seriam de pouco valor prático.

Uma vez que procedimentos são, efetivamente, processadores de dados, a efi-ciência de um procedimento está muito associada à forma como seus dados sãoorganizados. Estrutura de dados é o ramo da computação que estuda os diver-sos mecanismos de organização de dados para atender aos diferentes requisitos deprocessamento.

Neste capítulo são apresentadas algumas estruturas de dados, com ênfase naque-las que são utilizadas posteriormente no decorrer do texto. Assim, algumas estruturasde importância para outros tipos de aplicações — como a representação de matrizesesparsas, fundamental para a área de computação científica — não estão descritasaqui.

As estruturas de dados definem a organização, métodos de acesso e opções deprocessamento para coleções de itens de informação manipulados pelo programa.Dois tipos de coleções são apresentados. Estruturas lineares são aquelas que man-tém os seus itens de forma independente de seus conteúdos, ou seja, na qual qualquertipo de interpretação dos dados que são armazenados é irrelevante para a manuten-ção da estrutura. Estruturas associativas são aquelas que levam em consideração ainterpretação do valor (ou de parte dele) para a manutenção dos itens na estrutura.

Apresenta-se inicialmente uma visão conceitual de cada tipo de estrutura, comilustrações que utilizam estruturas pré-definidas na biblioteca padrão de gabaritos(STL) da linguagem C++. O conjunto de classes e algoritmos dessa biblioteca de-finem recursos de uso genérico para permitir que o programador trabalhe com es-truturas de dados usuais. Esses recursos estão agrupados em três grandes categorias(containers, iteradores, algoritmos) e utilizam o mecanismo de definições parame-trizadas (templates) para poder trabalhar com qualquer tipo de conteúdo. Essencial-mente, apresenta-se o tipo de estrutura e um conjunto básico de procedimentos paraa sua manipulação, ou API (Application Programming Interface). É esta API quedefine o tipo de estrutura, ou seja, o que se pode fazer com uma estrutura desse tipo,

31

2.1. Estruturas lineares 32

e é a única informação relevante para um programador que vá utilizar uma estruturade dados pré-definida.

Ao final, apresentam-se aspectos da organização interna de uma estrutura de da-dos. Tais aspectos são relevantes para o projeto e implementação de uma nova es-trutura de dados e normalmente não são manipulados por um programador que sim-plesmente utiliza estruturas já existentes na linguagem. Entretanto, é importante queo usuário detenha tal conhecimento por dois motivos. O primeiro é simplesmente terparâmetros para poder selecionar qual a implementação mais adequada, se houvermais de uma disponível, para a sua aplicação. O segundo motivo é ter conhecimentopara, se for necessário por não haver nenhuma implementação disponível, desenvol-ver a sua própria implementação de uma estrutura adequada às suas necessidades.

2.1 Estruturas linearesEstruturas lineares são aquelas que mantêm os seus itens de informação de forma

independente de seus valores. A única informação utilizada pela estrutura é a posiçãodo item; qualquer manipulação relativa ao conteúdo ou valor desse item é atribuiçãoda aplicação.

Estruturas lineares são, ao menos conceitualmente, naturais para programadores.Os arranjos, presentes nas linguagens de programação de alto nível, oferecem umaforma básica de definir um agregado de dados linear e com acesso indexado. Noentanto, são estruturas estáticas, ou seja, não há como modificar a dimensão de umarranjo após sua criação. Ademais, mesmo para uma estratégia de organização sim-ples como a estrutura linear, há operações que não ocorrem eficientemente em umarranjo, como por exemplo a inserção de novo conteúdo em posição intermediáriade um arranjo parcialmente preenchido.

A STL de C++ oferece um elenco de classes que definem estruturas lineares.Como mencionado, a STL utiliza o recurso de classes parametrizadas de C++ parapermitir a manipulação de qualquer tipo de conteúdo na estrutura. Para o progra-mador, o uso de uma classe parametrizada é simples; requer que ele especifique, nomomento da criação do objeto, qual é o tipo que deve ser utilizado internamente pelaclasse. Essa especificação dá-se através da indicação do tipo entre os símbolos demenor e maior. Por exemplo, seja cp uma classe parametrizada que requer a espe-cificação de um tipo. Se for criado um objeto c1 onde esse tipo seja int, então aexpressão correspondente seria

cp<int> c1;

As estruturas lineares básicas da STL de C++ são vector, deque e list.

2.1.1 vectorUma coleção do tipo vetor é essencialmente um arranjo cuja capacidade pode

variar dinamicamente. Internamente, é mantida informação sobre a última posição

33 Princípios de estruturas de dados

ocupada na coleção (Figura 2.1). Se o espaço reservado for totalmente ocupado eespaço adicional for necessário, este será alocado automaticamente.

Figura 2.1 Estrutura do tipo vetor

Para criar uma coleção desse tipo, é preciso incluir no programa o arquivo decabeçalho vector. Por exemplo, para criar um vetor de strings (ver Seção 2.3.1),seria necessário incluir os arquivos de cabeçalho vector e string:

#include <vector>#include <string>

Para a criação de uma instância dessa estrutura, seria utilizado o mecanismo da defi-nição parametrizada associado à declaração de um objeto desse tipo.

vector<string> umaLista;

É possível descobrir a quantidade de elementos em um vetor através da aplicaçãodo método size. Para verificar se a coleção está vazia, o método empty (queretorna um valor booleano) é mais eficiente.

Para a manipulação dos elementos que estão armazenados no vetor, é possívelutilizar o método insert para incluir e erase para eliminar um conteúdo emuma posição arbitrária. Alternativamente, o operador sobrecarregado [] pode serutilizado para ter acesso a qualquer posição.

Deve-se observar que, internamente, o vetor utiliza para o armazenamento dosdados um arranjo. Assim, inserções e remoções de elementos em uma posição inter-mediária não são eficientes, pois têm complexidade linear.

Para manipular a útlima posição do vetor, os métodos push_back (inserir) epop_back (retirar) são eficientes, pois realizam a operação em um tempo que inde-pende da quantidade de elementos armazenados no vetor, ou seja, têm complexidadetemporal constante.

Sempre que uma coleção dinâmica for necessária, o programador deve consideraro vetor como uma opção, pois é o tipo de estrutura mais simples e com menor sobre-carga de memória para o seu armazenamento. Se as características de manipulaçãode elementos definidas pelo vetor forem no entanto inadequadas para a aplicação,então as outras opções de estruturas devem ser avaliadas.

2.1. Estruturas lineares 34

2.1.2 dequeO deque é uma estrutura linear similar a um vetor, mas com informação mantida

internamente sobre a posição das suas duas extremidades, inicial e final (Figura 2.2).Como no vetor, manipulações em posições intermediárias da estrutura, com os

métodos insert, erase e o operador [] não são eficientes. No entanto, o dequepermite operar eficientemente com ambas as extremidades da coleção. Além dosmétodos push_back e pop_back, que manipulam a extremidade final, o dequetem implementações eficientes para os métodos push_front e pop_front, quemanipulam a extremidade inicial da estrutura.

Figura 2.2 Estrutura do tipo deque

Como para qualquer estrutura seqüencial de C++, os métodos size e emptyretornam informação sobre a ocupação da coleção. A definição do deque requer ainclusão do cabeçalho correspondente:

#include <deque>

A criação da estrutura precisa da definição do tipo de conteúdo. Por exemplo,para um deque de inteiros:

deque<int> fila;

2.1.3 listUma estrutura linear do tipo list é uma implementação de uma lista ligada. Em

uma estrutura deste tipo, os itens armazenados na coleção não estão necessariamenteem posições contíguas. Assim, junto a cada item armazenado é preciso armazenara informação sobre a localização do próximo item. A estrutura list implementa,na verdade, uma lista duplamente ligada, na qual informação sobre a localização doitem anterior também é armazenada junto a cada elemento (Figura 2.3).

Pela sua característica, a lista executa eficientemente inserções e remoções deelementos em posições intermediárias, usando os métodos erase e insert, comcomplexidade temporal constante. Em contrapartida, o acesso direto a elementosarmazenados no interior da lista não é eficiente. Por este motivo, o operador [] nãoé sobrecarregado para este tipo de estrutura.

Para usar essa estrutura, é preciso incluir o arquivo de cabeçalho list e, nadefinição, especificar o tipo de conteúdo:


Figura 2.3 Estrutura do tipo lista

#include <list>#include <string>...list<string> compras;

2.2 Estruturas associativasEstruturas associativas são aquelas que permitem o acesso a seus elementos de

forma independente de sua posição, com base apenas no seu valor. Em alguns casos,não é o valor do elemento completo que é utilizado, mas apenas uma parte dele; nestecaso, essa parte é conhecida como chave.

Este tipo de estrutura é a base conceitual para a construção de tabelas, peça defundamental importância para o desenvolvimento de software de sistema. Um deseus usos principais é na construção de tabelas de símbolos, amplamente utiliza-das em compiladores e montadores. Tabelas são também amplamente utilizadas emsistemas operacionais para a manutenção de informação de apoio à execução de pro-gramas, como as tabelas de processos e as tabelas de arquivos.

2.2.1 ConjuntosUm conjunto é uma estrutura associativa que mantém seus elementos ordenados

pelo valor (completo), sem que possam existir dois elementos de mesmo valor.Na biblioteca STL, conjunto é implementado pela classe set:

#include <set>...set<int> dados;

Se o tipo de conteúdo do conjunto for uma classe definida pelo usuário, então épreciso informar um segundo parâmetro na declaração do conjunto, que é a funçãode comparação. Entretanto, se a classe já tiver uma definição para o operador menorque (<), então ele será utilizado se o segundo parãmetro for omitido.

2.2. Estruturas associativas 36

Os métodos básicos que podem ser utilizados com os elementos de um con-junto são essencialmente os mesmos que podem ser usados por uma estrutura linear:insert, size, empty, begin, end. Além desses, há outros métodos que sãoespecíficos para operações com conjuntos, tais como includes, set_union eset_intersection. Para descobrir se um objeto faz ou não parte da coleção, ométodo find é utilizado.

Além de conjuntos implementados com set, STL oferece uma outra estrutura,multiset, que tem as mesmas operações mas permite a duplicação de elementoscom mesmo valor.

2.2.2 MapasUm mapa é uma estrutura associativa na qual os elementos armazenados estão

organizados na forma de pares (chave, valor), de tal forma que é possível ter acessoa valor (que pode eventualmente ser uma estrutura complexa) a partir da chave (Fi-gura 2.4). Assim, deve ser possível obter o valor def a partir da especificação dachave β, ou o valor xyz a partir de ζ .

Figura 2.4 Visão conceitual de uma tabela.

Uma tabela de símbolos, utilizada em compiladores para manter a informação so-bre cada variável de um programa, é um exemplo de uma possível aplicação de umaestrutura do tipo mapa. Neste caso, a chave é usualmente o nome de uma variável eo valor é o conjunto de informações sobre a variável, tais como o seu tipo, endereçode memória e local de definição. Já em uma tabela de arquivos, uma estrutura utili-zada pelo sistema operacional para manter a informação sobre cada um dos arquivosassociados a um processo, a chave pode ser um identificador inteiro (por exemplo, oterceiro arquivo aberto pelo processo) e o valor o conjunto de informações sobre oarquivo, tais como a posição corrente no arquivo.

Em C++, a STL implementa mapas com a classe map, que é declarada com doisparâmetros, o primeiro para o tipo da chave e o segundo para o tipo do valor:

#include <map>#include <string>...map<string,int> compras;


Neste exemplo, a chave é uma string e o valor associado é um inteiro.Para operar com os elementos de um mapa, o operador [] é sobrecarregado. Por

exemplo, para associar o valor 6 à chave vinho, basta utilizar a expressão:

compras["vinho"] = 6;

Do mesmo modo, para obter o valor associado a uma chave, o mesmo operadorpode ser utilizado:

int quantidade = compras["vinho"];

Além da sobrecarga desse operador, os métodos básicos presentes nos outrostipos de estrutura (como empty e size) também estão disponíveis para mapas.

A estrutura map não admite duplicação de chaves; STL oferece também umaimplementação multimap, na qual as chaves podem ser repetidas.

2.3 Alocação dos elementosA fim de poder escolher a melhor estrutura para uma determinada aplicação,

ou mesmo para fazer uma implementação alternativa caso nenhuma implementaçãodisponível atenda às suas demandas, é importante entender como essas estruturas sãoimplementadas. São considerados aqui dois aspectos de implementação. O primeiroconsidera como os dados são mantidos em memória, que é um aspecto essencial paraqualquer tipo de estrutura. O outro aspecto está associado às estruturas associativase aborda como um valor é localizado em uma coleção.

2.3.1 Alocação contíguaPara armazenar vários dados de um determinado tipo na memória, há duas pos-

sibilidades básicas. A primeira é ter um espaço contíguo para todos os elementos,de forma que apenas o endereço inicial precise ser preservado. A outra possibilidadeé ter um espaço independente para cada elemento, o que aumenta a flexibilidade dealocação mas demanda a manutenção de informação adicional para a localização decada elemento.

As linguagens de programação normalmente oferecem facilidades para construiragregados contíguos e uniformes, ou seja, nos quais todos os elementos são de ummesmo tipo e estão armazenados em uma área contígua de memória. São os ar-ranjos; seus elementos podem ser acessados através de um índice representando aposição desejada.

Em C++, arranjos são definidos e acessados através do operador de indexação[], como em:

int elem[5];...elem[0] = 1;

2.3. Alocação dos elementos 38

Neste exemplo, um arranjo de nome elem é definido. Este arranjo tem espaçopara armazenar cinco valores inteiros, que serão referenciados no programa comoelem[0], elem[1], elem[2], elem[3] e elem[4]. Observe através desseexemplo que o primeiro elemento de um arranjo em C++ é sempre o elemento deíndice 0 (elem[0]). Conseqüentemente, para um arranjo com N elementos o últimoelemento é o de índice N-1 (elem[4], no exemplo).

A implementação de arranjos está intimamente ligada ao conceito de ponteiros.Quando se cria, como acima, um arranjo com cinco inteiros, reserva-se o espaço namemória para armazená-los e atribui-se um nome para o endereço inicial dessa área— em outras palavras, um ponteiro. O acesso ao valor i-ésimo elemento do arranjoelem, elem[i], equivale à expressão

*(elem + i)

As duas formas de indicar o elemento acessado podem ser usadas indistintamente.Entretanto, enquanto o valor de uma variável ponteiro que não seja const pode seralterado, o valor base de um arranjo não pode.

É fundamental entender em que região da memória os dados de um arranjo serãoarmazenados. Todo processo mantém uma área de dados na memória e tambémuma área de pilha, que é utilizada na passagem de parâmetros entre funções e parao armazenamento de valores temporários, como as variáveis locais de uma função.Se um arranjo é declarado como uma variável local de alguma função, ela só terávalidade enquanto a função estiver “ativa”, ou seja, enquanto ela ainda não tiverconcluído seu escopo. Quando a função retorna, ela libera o espaço que ocupava napilha e suas variáveis locais são descartadas.

Caso seja necessário que a informação seja mantida além do tempo de execuçãode uma função, ela deve estar alocada à área de dados. Em C e C++, há duas maneirasbásicas de fazer isto. A primeira é ter a variável declarada fora do escopo de umafunção. A outra forma é declarar a variável no escopo da função mas acrescentar nadeclaração a palavra-chave static, uma indicação de que a variável não deve serarmazenada na pilha como o padrão para variáveis locais.

Strings em C++

Em C++, a definição da classe string torna transparente a forma de armazena-mento da seqüência de caracteres e sua manipulação. Assim, o programador podeabstrair-se de detalhes como terminadores de seqüência ou tamanho do arranjo.

Para utilizar strings em C++, o programador deve incluir em seu programa oarquivo de cabeçalho string. Com essa inclusão, ele pode criar objetos dessetipo de forma similar à declaração de variáveis de tipos primitivos. Por exemplo, nosegmento de código

#include <string>...string estouVazia;


um objeto string estouVazia é criado, neste caso sem nenhum conteúdo inicial.Outras formas possíveis de criação de objetos desse tipo são:

string socorro("Alguem me ajude!");string sos(socorro);string toAqui = "Ta me ouvindo?";

No primeiro caso, é utilizada a forma de inicialização de objetos, passando um ar-gumento entre parênteses — no caso, uma string constante. O segundo exemploé similar, mas usa para inicialização um objeto já existente ao invés da constante.No terceiro caso, é usada uma forma que combina a declaração do objeto e umaatribuição.

Métodos são semelhantes a funções, com a diferença que devem ser aplicados aum objeto. A forma de aplicação de um método dá-se através do operador . (ponto)após o objeto. Por exemplo, para obter o tamanho da seqüência armazenado noobjeto sos, utiliza-se o método size através de uma expressão como a seguinte:

int tamanho = sos.size();

Há duas formas de obter os elementos individuais de uma seqüência. Uma utilizao método at, que recebe um argumento inteiro que indica a posição desejada, sendoque 0 é a primeira posição. Por exemplo,

char c = sos.at(2);

teria como resultado o caráter ’g’. A outra forma utiliza o conceito de sobrecargade operadores da linguagem C++, que permite associar um novo comportamentoaos operadores da linguagem quando aplicados a objetos de uma classe. No caso daclasse string, um novo comportamento foi definido para o operador de indexação,[]. Assim, a expressão acima poderia ter sido representada como

char c = sos[2];

Outros operadores sobrecarregados para objetos da classe string incluem ooperador de soma, +, para a concatenação de seqüências; e os operadores de compa-ração (==, !=, >, <, <= e <=), modificados para avaliar o conteúdo das seqüênciase não seus endereços de memória.

2.3.2 Alocação não-contígua

Na estratégia de alocação não-contígua, o espaço para cada elemento é requisi-tado independentemente. Desse modo, não é necessário prever com antecedênciaqual deve ser a capacidade máxima da estrutura, pois à medida que se necessita doespaço para o elemento adicional, esse espaço é requisitado e o elemento incorpo-rado à estrutura.


Ao contrário das estratégias baseadas em alocação contígua, que podem fazer usode uma alocação prévia na área de dados estática, nas estratégias de alocação não-contígua é necessário buscar o espaço para o armazenamento durante a execução doprograma. O recurso oferecido para tal fim é a alocação dinâmica de memória. Amemória alocada com esse recurso não faz parte nem da área estática de dados e nemda pilha, mas são incorporadas ao espaço de dados do programa como uma terceiraregião de dados (o heap.

Em C++, a alocação dinâmica é suportada pelo operador new.A área que é alocada dinamicamente deve ser liberada depois que seu uso foi

concluído, caso contrário a execução do programa pode levar o sistema a um estadode instabilidade por falta de espaço. O operador delete de C++ oferece essa facilidadepara liberar espaço alocado dinamicamente;

Nesse tipo de alocação, o uso de ponteiros ou referências é intenso, pois é precisomanter a informação sobre o endereço de cada elemento da coleção. Há basicamentedois tipos de estruturas de implementação baseadas nessa abordagem, listas ligadase árvores.

Listas ligadas

Uma lista ligada é uma estrutura que corresponde a uma seqüência lógica deentradas ou nós. Tipicamente, em uma lista ligada há um ou dois pontos conhecidosde acesso — normalmente o topo da lista (seu primeiro elemento) e eventualmenteo fim da lista (seu último elemento). Cada nó armazena também a localização dopróximo elemento na seqüência, ou seja, de seu nó sucessor. Desse modo, o arma-zenamento de uma lista não requer uma área contígua de memória. A Figura 2.5representa graficamente uma estrutura de lista ligada.

Figura 2.5 Representação de uma lista ligada.

Como pode-se observar nessa figura, toda a informação em um nó pode ser abs-traída para dois campos de interesse: info, o conteúdo do nó, e next, uma referênciapara o próximo nó da lista. A entrada que determina o topo da lista deve ser regis-trada à parte da lista. Essa informação é tipicamente mantida em um nó descritorda lista. A entrada que marca o fim da lista não precisa de indicação especial —tipicamente, o ponteiro nulo como valor de next marca o final da lista.

O tipo de lista apresentado na Figura 2.5 é denominado lista simplesmente ligada.Ela é eficiente quando a varredura dos elementos da lista se faz no sentido do iníciopara o final, mas não no sentido inverso. Se os elementos da lista precisam servarridos nos dois sentidos, uma lista duplamente ligada deve ser utilizada. Neste


caso, além de info e next, um outro campo de interesse, prev, mantém a referênciapara o nó antecessor da lista.

Para fins de descrição dos procedimentos de uma lista ligada, considera-se aquique o nó de uma lista é um registro com a seguinte estrutura:

NODE |= info : ENTRY

next : NODE

Como listas são estruturas dinâmicas, normalmente são definidos procedimentosque permitem criar e remover nós na memória. Neste texto, a criação e remoção deum nó estarão associadas respectivamente aos procedimentos:

CREATENODE(ENTRY e). Aloca recursos (área de memória) para guardar a infor-mação especificada nos argumentos. Retorna uma referência para o nó criado,do tipo NODE; e

DELETENODE(NODE n). Libera os recursos usados pelo nó.

Estabelecer a conexão entre dois nós é uma operação simples e freqüente namanipulação de listas. Para estabelecer a ligação entre um nó já pertencente a umalista e um novo nó, basta fazer com que o novo nó referencie no campo next o nó queanteriormente era referenciado pelo nó original — mesmo que esse campo tenha ovalor nulo. Para concluir a conexão, o nó original deve ter atualizado o campo nextpara referenciar o novo nó. O efeito dessa conexão é ilustrado na Figura 2.6.

Figura 2.6 Efeito da aplicação do procedimento LINKNODE.

(a) Antes da ligação (b) Após a ligação

O procedimento LINKNODE, apresentado no Algoritmo 2.1, descreve como es-tabelecer essa ligação entre os dois nós que são passados como argumento.

Algoritmo 2.1 Ligação de dois nós.LINKNODE(NODE n1, NODE n2)1 n2.next← n1.next2 n1.next← n2

A informação sobre a estrutura de uma lista ligada está distribuída ao longo deseus nós. Assim, a única informação adicional requerida para manter a lista é aespecificação de seu nó descritor:


LIST |= top : NODE

Na criação de uma lista, o nó descritor está inicialmente vazio, de forma queseu campo next tem o valor nulo. Assim, um procedimento para verificar se a listaestá vazia deve verificar o valor desse campo. Esse procedimento está descrito noAlgoritmo 2.2.

Algoritmo 2.2 Verificação se a lista ligada está vazia.ISEMPTY(LIST l)1 if l.top.next = NIL

2 then return true3 else return false

Para a inserção de um novo nó em uma lista há duas possibilidades que podemser consideradas, dependendo da opção de se inserir o novo nó no início (antes doprimeiro elemento) ou no final (após o último elemento) da lista.

A primeira dessas possibilidades está representada através do procedimento IN-SERT, que recebe como argumentos as referências para a lista e para o nó a serinserido. O Algoritmo 2.3 apresenta esse procedimento.

Algoritmo 2.3 Inserção de nó no topo da lista ligada.INSERT(LIST l, NODE n)1 LINKNODE(l.top, n)

O procedimento que acrescenta um nó ao final da lista necessita varrer a listacompletamente em busca do último nó, aquele cujo campo next tem o valor nulo.Para tanto, requer a utilização de uma variável interna que indica qual o nó estáatualmente sendo analisado. No momento em que o campo next desse nó tiver ovalor nulo, então sabe-se que o último nó da lista foi localizado. Esse procedimento,APPEND, está descrito no Algoritmo 2.4.

Algoritmo 2.4 Inserção de nó no final da lista ligada.APPEND(LIST l, NODE n)1 declare curr : NODE

2 curr ← l.top3 while curr.next 6= NIL

4 do curr ← curr.next5 LINKNODE(curr, n)

De forma similar, o procedimento para retirar um nó do início da lista é maissimples que aquele para retirar um nó do fim da lista, pois este requer a varredura


completa da lista. Nos dois casos, o valor de retorno é uma referência ao nó retirado;a partir dessa referência, a aplicação pode determinar o que deseja fazer com o nó,se manipular a informação nele contida ou simplesmente liberar os recursos com oprocedimento DELETENODE. Um valor de retorno nulo indica que a operação foiespecificada sobre uma lista vazia.

O procedimento que retira o primeiro nó da lista é apresentado no Algoritmo 2.5.Embora a linha 5 desse algoritmo não seja absolutamente necessária, ela garanteque não há meios de acesso aos nós da lista exceto pelos procedimentos definidos.Se ela não estivesse presente, seria possível que a aplicação, ao obter o nó com ainformação de endereço do seu antigo sucessor, tivesse acesso a um nó da lista deforma direta.

Algoritmo 2.5 Retirada do primeiro nó da lista ligada.REMOVEFIRST(LIST l)1 declare first : NODE

2 first← l.top.next3 if first 6= NIL

4 then LINKNODE(l.top, first.next)5 first.next← NIL

6 return first

O procedimento para a retirada de um nó do fim da lista é descrito no Algo-ritmo 2.6. Da mesma forma que no procedimento de remoção do primeiro elementoda lista, a situação de manipulação de uma lista vazia deve receber tratamento es-pecial. Como no procedimento de inserção, uma varredura de toda a lista é feitamantendo-se uma referência para o nó sob análise; adicionalmente, mantém-se umareferência para o nó anterior a este de forma a permitir a atualização da indicação dofim da lista.

Algoritmo 2.6 Retirada do último nó da lista ligada.REMOVELAST(LIST l)1 declare pred, curr : NODE

2 pred← l.top3 curr ← l.top.next4 if curr 6= NIL

5 then while curr.next 6= NIL

6 do pred← curr7 curr ← curr.next8 pred.next← NIL

9 return curr

Outro procedimento usual na manipulação de uma lista ligada é aquele que per-


mite procurar o nó que satisfaz um determinado critério de busca — por exemplo,cuja chave em seu campo de informação seja igual a um argumento fornecido. Esseprocedimento de busca é apresentado através do Algoritmo 2.7, que retorna uma re-ferência para o campo de informação do nó encontrado ou o valor nulo se não forencontrado nenhum nó que satisfaça a condição de busca.

Algoritmo 2.7 Busca de nó com chave especificada em lista ligada.FIND(LIST l, KEY k)1 declare curr : Node2 curr ← l.top.next3 while curr 6= NIL

4 do if curr.info.c = k5 then return curr.info6 else curr ← curr.next7 return NIL

Como se observa nesse caso, a varredura de uma lista em busca de uma dadachave é um procedimento seqüencial, similar em conceito à busca linear. Essa é acontra-partida à flexibilidade de manipulação de uma lista — não há como realizaruma busca binária, por exemplo, nesse tipo de estrutura. Assim, o procedimentodeve analisar a lista nó a nó até encontrar o elemento procurado.

Dependendo da aplicação, outros procedimentos podem ser associados à mani-pulação de uma lista ligada, tais como obter o número de nós na lista, SIZE(); con-catenar ou combinar duas listas, CONCAT(); inserir elemento em posição específicada lista, INSERTAT(); ou remover elemento em posição específica, REMOVEAT().

Filas e pilhas

Filas e pilhas são estruturas usualmente lineares, implementadas através de ar-ranjos ou listas, que têm restrições à política de manipulação dos elementos da lista.

Uma fila (queue) tipicamente estabelece uma política FIFO — first in, first out— de acesso aos dados. Em outras palavras, a ordem estabelecida na lista é a ordemde inserção. No momento de retirar um nó da lista, o nó mais antigo (o primeiro queentrou) é o primeiro a ser retirado.

Como as políticas de inserção e remoção são pré-definidas, para esse tipo deestrutura as operações são descritas de forma genérica, INSERT e REMOVE. Há duaspossibilidades para implementar as operações de uma fila usando os procedimentosdescritos para listas:

1. restringir a inserção ao procedimento INSERT e a remoção ao procedimentoREMOVELAST, ou

2. restringir a inserção ao procedimento APPEND e a remoção ao procedimentoREMOVEFIRST.


Uma estrutura de pilha (stack), por outro lado, estabelece uma política LIFO —last in, fisrt out. Uma estrutura de pilha também oferece basicamente duas operaçõesde manipulação, PUSH, para inserção no topo da pilha, e POP, para retirada do topoda pilha.

Embora também fosse possível implementar uma pilha através de lista usando osprocedimentos que acrescentam e removem os nós no final da lista, por razões óbviasde desempenho uma pilha é usualmente implementada usando os procedimentos IN-SERT e REMOVEFIRST, que não requerem a varredura da lista para estabelecer essapolítica de manipulação de dados.

Árvores

A estratégia de lista ligada é adequada para a implementação de estruturas line-ares, pois a cada nó temos associado apenas a referência para um nó vizinho. Outrotipo de estratégia de implementação não-contígua extensivamente utilizada na pro-gramação de sistemas é a árvore, que esquematicamente pode ser visualizada comouma extensão de uma lista ligada na qual um nó pode ter mais de um sucessor (Fi-gura 2.7). A representação esquemática de árvores usualmente coloca a raiz no topo,com a árvore crescendo para baixo.

Figura 2.7 Representação esquemática de uma estrutura de árvore.

Uma árvore é uma estrutura que contém um conjunto finito de um ou mais nós,sendo que um dos nós é especialmente designado como o nó raiz e os demais nóssão particionados em 0 ou mais conjuntos disjuntos onde cada um desses conjuntosé em si uma árvore, que recebe o nome de sub-árvore.

A Figura 2.7 ilustra um exemplo de uma árvore T , que tem o nó raiz n3 e as sub-árvores T1, T2 e T3. A sub-árvore T1 tem o nó raiz n1 e não contém sub-árvores; sub-árvore T2 tem o nó raiz n4 e sub-árvores T4 e T5; e a sub-árvore T3 tem o nó raiz n6e sub-árvore T6. No próximo nível, as sub-árvores T4, T5 e T6 têm respectivamenteos nós raízes n2, n5 e n7 e não têm sub-árvores.


O número de sub-árvores de um nó é o grau do nó. No exemplo, o nó n3 temgrau 3; n4, 2; e n5, 0. O grau da árvore é o maior valor de grau de nó entre todos osnós da árvore; no exemplo, a árvore T tem grau 3. Um nó que não tem sub-árvores,ou seja, cujo grau é 0, é normalmente denominado nó folha da árvore. No exemplo,a árvore T tem folhas n1, n2, n5 e n7. Os nós raízes das sub-árvores de um nó sãousualmente chamados de nós filhos desse nó, que recebe também o nome de nó paidaqueles nós. Em uma estrutura de árvore, cada nó tem apenas um nó pai.

Um tipo especial de árvore é a árvore binária. Uma árvore binária tem umnó raiz e no máximo duas sub-árvores, uma sub-árvore esquerda e uma sub-árvoredireita. Em decorrência dessa definição, o grau de uma árvore binária é limitado adois. A Figura 2.8 ilustra alguns exemplos de árvores binárias.

Figura 2.8 Árvores binárias

Observe na figura que T1 e T2 são árvores binárias distintas pois, ao contrário dadefinição genérica de árvores, há diferença de tratamento para a árvore binária entre asub-árvore direita e a sub-árvore esquerda. Outra diferença de definição para árvoresbinárias é que elas podem eventualmente ser vazias, algo que a definição de árvoregenérica não permite. T3 é uma árvore binária degradada (equivalente a uma listalinear), enquanto T4 é uma árvore binária completa e balanceada (com sub-árvoresde igual tamanho).

Uma das principais aplicações de árvores binárias é a manutenção de estruturasnas quais a ordem é importante. Para manter a ordem dos nós de uma árvore binária,três estratégias podem ser utilizadas:

Pré-ordem é a estratégia de varredura de uma árvore binária na qual o primeiro nóé o nó raiz, seguido pela sub-árvore esquerda em pré-ordem e finalmente pelasub-árvore direita em pré-ordem;

Intra-ordem é a estratégia de varredura de árvore binária na qual lê-se primeiro asub-árvore esquerda em intra-ordem, seguido pelo nó raiz e finalmente pelasub-árvore direita em intra-ordem;


Pós-ordem é a estratégia de varredura na qual primeiro lê-se os nós da sub-árvoreesquerda em pós-ordem, depois os nós da sub-árvore direita em pós-ordem efinalmente o nó raiz.

Aplicando essas estratégias à árvore T4 (Figura 2.8), com pré-ordem a seqüênciade nós da árvore seria A, B, D, E, C, F, G; com intra-ordem, D, B, E, A, F, C, G; ecom a pós-ordem, D, E, B, F, G, C, A.

A estratégia intra-ordem é usualmente utilizada para a manutenção de coleçõesordenadas por valores. Todos os valores na sub-árvore esquerda de um nó precedemo valor armazenado nesta raiz; similarmente, todos os valores na sub-árvore direitasão maiores que esse valor. Deste modo, a busca por um valor na árvore inicia-sepelo nó raiz. Se o valor armazenado for igual ao buscado, encerra-se a busca. Caso ovalor buscado seja menor que a raiz, a busca é repetida na sub-árvore esquerda; casoseja mair, na sub-árvore direita.

Para inserir um novo valor na árvore binária, estratégia similar é utilizada. Se aárvore estiver vazia, o elemento é inserido na raiz. Caso a raiz exista, o elemento éinserido na sub-árvore esquerda, se seu valor for menor ou igual àquela armazenadona raiz, ou na sub-árvore direita, caso contrário.

2.3.3 Hashing

Na apresentação da estrutura de containers, a busca por uma chave ocorre sem-pre através de comparações. Uma alternativa de busca em coleções dá-se através docálculo da posição que uma chave ocupa numa tabela através de uma função. Essetipo de função que mapeia um símbolo ou uma string de símbolos para valores intei-ros é denominado função hash e o tipo de estrutura manipulada dessa forma é umatabela hash.

A tabela hash combina aspectos da alocação contígua com a alocação não-contí-gua. Por um lado, o espaço total da tabela hash é alocado previamente e ocupa umaárea contígua. Por outro lado, a ocupação da tabela não é contígua, pois a posição decada nó depende da aplicação da função hash.

Idealmente, cada chave processada por uma função hash gera uma posição dife-rente na tabela, um vetor com capacidade pré-definida. No entanto, na prática exis-tem sinônimos — chaves distintas que resultam em um mesmo valor de hashing.Quando duas ou mais chaves sinônimas são mapeadas para a mesma posição da ta-bela, diz-se que ocorre uma colisão.

Uma boa função hash deve apresentar duas propriedades básicas: seu cálculodeve ser rápido e deve gerar poucas colisões. Além disso, é desejável que ela leve auma ocupação uniforme da tabela para conjuntos de chaves quaisquer. Duas funçõeshash usuais são descritas a seguir:

Meio do quadrado. Nesse tipo de função, a chave é interpretada como um valornumérico que é elevado ao quadrado. Os r bits no meio do valor resultante sãoutilizados como o endereço em uma tabela com 2r posições.


Divisão. Nesse tipo de função, a chave é interpretada como um valor numérico queé dividido por um valor M . O resto dessa divisão inteira, um valor entre 0 eM − 1, é considerado o endereço em uma tabela de M posições. Para reduzircolisões, é recomendável que M seja um número primo.

Como nem sempre a chave é um valor inteiro que possa ser diretamente utilizado,a técnica de folding pode ser utilizada para reduzir uma chave a um valor inteiro.Nessa técnica, a chave é dividida em segmentos de igual tamanho (exceto pelo últimodeles, eventualmente) e cada segmento é considerado um valor inteiro. A soma detodos os valores assim obtidos será a entrada para a função hash.

O processamento de tabelas hash demanda a existência de algum mecanismopara o tratamento de colisões. As formas mais usuais de tratamento de colisão sãopor endereçamento aberto ou por encadeamento.

Na técnica de tratamento de colisão por endereçamento aberto, a estratégia é uti-lizar o próprio espaço da tabela que ainda não foi ocupado para armazenar a chaveque gerou a colisão. Quando a função hash gera para uma chave uma posição quejá está ocupada, o procedimento de armazenamento verifica se a posição seguintetambém está ocupada; se estiver ocupada, verifica a posição seguinte e assim pordiante, até encontrar uma posição livre. (Nesse tipo de tratamento, considera-se a ta-bela como uma estrutura circular, onde a primeira posição sucede a última posição.)A entrada é então armazenada nessa posição. Se a busca termina na posição inici-almente determinada pela função hash, então a capacidade da tabela está esgotada euma mensagem de erro é gerada.

No momento da busca, essa varredura da tabela pode ser novamente necessária.Se a chave buscada não está na posição indicada pela função hash e aquela posiçãoestá ocupada, a chave pode eventualmente estar em outra posição na tabela. Assim,é necessário verificar se a chave não está na posição seguinte. Se, por sua vez, essaposição estiver ocupada com outra chave, a busca continua na posição seguinte eassim por diante, até que se encontre a chave buscada ou uma posição sem nenhumsímbolo armazenado.

Na técnica de tratamento de colisão por encadeamento, para cada posição ondeocorre colisão cria-se uma área de armazenamento auxiliar, externa à área inicial databela hash. Normalmente essa área é organizada como uma lista ligada que contémtodas as chaves que foram mapeadas para a mesma posição da tabela. No momentoda busca, se a posição correspondente à chave na tabela estiver ocupada por outrachave, é preciso percorrer apenas a lista ligada correspondente àquela posição atéencontrar a chave ou alcançar o final da lista.

Hashing é uma técnica simples e amplamente utilizada na programação de sis-temas. Quando a tabela hash tem tamanho adequado ao número de chaves que iráarmazenar e a função hash utilizada apresenta boa qualidade, a estratégia de mani-pulação por hashing é bastante eficiente.


2.4 OrdenaçãoEstruturas lineares, embora simples, apresentam um inconveniente para deter-

minar se um dado valor está ou não presente na coleção. É preciso percorrer cadaelemento até encontrar o valor ou até chegar ao final da lista, para decidir que elenão está presente. Uma melhoria simples à abordagem de representação de uma es-trutura, com o objetivo de obter uma busca mais eficiente, é a manutenção dos seuselementos em ordem. Deste modo, é possível utilizar no momento da busca umaestratégia análoga àquela utilizada ao procurar uma palavra no dicionário:

1. Faz-se uma estimativa da posição aproximada da palavra e abre-se na páginaestimada.

2. Se a palavra não foi encontrada nessa página, pelo menos sabe-se em quedireção buscar, se mais adiante ou mais atrás no dicionário. O processo deestimar a nova página de busca repete-se na parte do dicionário que pode contera palavra.

Esse mecanismo de busca só é possível porque existe uma ordenação possíveldas palavras com base na precedência das letras no alfabeto (a chamada ordem lexi-cográfica) e esta ordenação é utilizada no dicionário. Se o dicionário mantivesse aspalavras sem nenhuma ordem, esse tipo de busca não seria possível. Com base nessemesmo princípio, a busca em um vetor pode ser melhorada se seu conteúdo puderser ordenado.

O algoritmo de busca binária utiliza esse princípio. No caso, a estimativa queé feita para a posição a ser buscada é a posição mediana do restante do vetor queainda precisa ser analisado. No início, este “restante” é o vetor completo; assim, asua posição central é a primeira a ser analisada. Se seu conteúdo não for a entradabuscada, analisa-se a metade que resta, ou a inferior (se a chave encontrada tem valormaior que a procurada) ou a superior (em caso contrário). O procedimento assim serepete, até que se encontre a entrada desejada ou que a busca se esgote sem que estaseja encontrada.

O Algoritmo 2.8 descreve essa forma de busca. Os dois argumentos são o vetorT e o elemento que será utilizado como chave de busca c, cujo tipo é genericamenteaqui denotado como ELEMENT. O retorno é uma indicação se o elemento está pre-sente ou não nesta coleção. As variáveis bot, mid e top referem-se a posições novetor — respectivamente o início, o meio e o fim da área ainda por ser pesquisada.A notação bxc denota o maior inteiro cujo valor é menor ou igual a x.

A manutenção da ordem em um vetor dá-se através de procedimentos auxiliaresde ordenação, uma das áreas relevantes de estudos em estruturas de dados. Porsimplicidade, é assumido nessa apresentação que os conteúdos que serão ordenadosestão sempre contidos em memória. Os algoritmos de ordenação que trabalham comessa restrição são denominados algoritmos de ordenação interna. Algoritmos deordenação externa manipulam conjuntos de valores que podem estar contidos emarquivos maiores, armazenados em discos ou outros dispositivos de armazenamento

2.4. Ordenação 50

Algoritmo 2.8 Busca binária em um vetor.BINARYSEARCH(VECTOR T, ELEMENT c)

1 declare bot, mid, top : INTEGER

2 bot← 03 top← T.size()− 14 while bot ≤ top5 do mid← b(bot + top)/2c6 if c > T [mid]7 then bot← mid + 18 else if c < T [mid]9 then top← mid− 1

10 else return true11 return false

externos à memória principal. Os algoritmos de ordenação interna (em memória) sãoconvencionalmente baseados em estratégias de comparação (quicksort, heapsort) ouem estratégias de contagem (radixsort).

Um algoritmo básico de ordenação é o algoritmo de ordenação pelo menorvalor, que pode ser sucintamente descrito como a seguir. Inicialmente, procure aentrada que apresenta o menor valor de todo o vetor. Uma vez que seja definido queposição contém esse valor, troque seu conteúdo com aquele da primeira posição dovetor; desta forma, o menor valor estará na posição correta. Repita então o proce-dimento para o restante do vetor, excluindo os elementos que já estão na posiçãocorreta.

Esse procedimento é descrito no Algoritmo 2.9, que recebe como argumento ovetor a ser ordenado. No procedimento, pos1 e pos2 são as posições sob análise. Avariável min corresponde à posição onde foi encontrado o menor valor até o mo-mento, mantido na variável sml.

Algoritmo 2.9 Ordenação de vetor pela busca do menor valor.MINENTRYSORT(VECTOR T )1 declare min, pos1, pos2 : INTEGER

2 declare sml : ELEMENT

3 for pos1← 0 to T.size()− 24 do sml← +∞5 for pos2← pos1 to T.size()− 16 do if T [pos2] < sml7 then sml← T [pos2]8 min← pos29 T.swap(pos1, min)


Neste algoritmo, o laço de iteração mais externo indica o primeiro elemento novetor não ordenado a ser analisado — no início, esse é o seu primeiro elemento. Aslinhas de 4 a 8 são responsáveis por procurar, no restante do vetor, o elemento commenor valor. Na linha 9, o método swap troca o conteúdo das duas entradas nasposições especificadas.

Este tipo de algoritmo de ordenação é razoável para manipular coleções com umpequeno número de elementos, mas à medida que esse tamanho cresce o desempe-nho torna seu uso inviável — sua complexidade temporal é O(n2), conseqüência doduplo laço de iteração que varre o vetor até o final. Felizmente, há outros algorit-mos de ordenação com melhor comportamento de desempenho em situações onde aquantidade de elementos cresce.

Quicksort é baseado no princípio de “dividir para conquistar:” o conjunto deelementos a ser ordenado é dividido em dois subconjuntos (partições), que sendomenores irão requerer menor tempo total de processamento que o conjunto total,uma vez que o tempo de processamento para a ordenação não é linear com a quan-tidade de elementos. Em cada partição criada, o procedimento pode ser aplicadorecursivamente, até um ponto onde o tamanho da partição seja pequeno o suficientepara que a ordenação seja realizada de forma direta por outro algoritmo.

Nesta descrição do procedimento QUICKSORT (Algoritmo 2.10), os seus argu-mentos determinam as posições inicial e final do segmento do vetor a ser ordenado,init e end, respectivamente.

Algoritmo 2.10 Ordenação de vetor por quicksort.QUICKSORT(VECTOR T, INTEGER init, INTEGER end)

1 declare pos1, pos2, part : INTEGER

2 if init < end3 then pos1← init + 14 pos2← end5 while true6 do while T [pos1] < T [init]7 do pos1← pos1 + 18 while T [pos2] > T [init]9 do pos2← pos2− 1

10 if pos1 < pos211 then part← pos112 T.swap(pos1, pos2)13 else part← pos214 break15 T.swap(init, part)16 QUICKSORT(T, init, part− 1)17 QUICKSORT(T, part + 1, end)

2.4. Ordenação 52

O ponto crítico deste algoritmo está na forma de realizar a partição — um ele-mento é escolhido como pivô, ou separador de partições. No Algoritmo 2.10, aposição desse pivô é mantida na variável part. Todos os elementos em uma partiçãotêm valores menores que o valor do pivô, enquanto todos os elementos de outra par-tição têm valores maiores que o valor do pivô. Os dois laços internos (iniciando naslinhas 6 e 8) fazem a busca pelo pivô tomando como ponto de partida o valor inicial.Um melhor desempenho poderia ser obtido obtendo-se o valor médio de três amos-tras como ponto de partida para o pivô — por exemplo, entre os valores no início,meio e fim da partição sob análise. Dessa forma, haveria melhores chances de ob-ter como resultado partições de tamanhos mais balanceados, característica essencialpara atingir um bom desempenho para esse algoritmo.

Quicksort é um algoritmo rápido em boa parte dos casos onde aplicado, comcomplexidade temporal média O(n log n). Entretanto, no pior caso essa comple-xidade pode degradar para O(n2). Mesmo assim, implementações genéricas dessealgoritmo são usualmente suportadas em muitos sistemas — por exemplo, pela rotinaqsort da biblioteca padrão da linguagem C.

Entre os principais atrativos de quicksort destacam-se o fato de que na maiorparte dos casos sua execução é rápida e de que é possível implementar a rotina semnecessidade de espaço de memória adicional. Uma desvantagem de quicksort é quetodos os elementos devem estar presentes na memória para poder iniciar o processode ordenação. Isto inviabiliza seu uso para situações de ordenação on the fly, ou seja,onde o processo de ordenação ocorre à medida que elementos são obtidos.

Outra classe de algoritmos de ordenação é aquela na qual a definição da posiçãoordenada de um elemento se dá pela contagem do número de elementos com cadavalor. O princípio básico é simples. Considere por exemplo uma coleção de elemen-tos a ordenar onde as chaves podem assumir N valores diferentes. Cria-se então umatabela com N contadores e varre-se a coleção do início ao fim, incrementando-se ocontador correspondente à chave i cada vez que esse valor for encontrado. Ao finaldessa varredura conhece-se exatamente quantas posições serão necessárias para cadavalor; os elementos são transferidos para as posições corretas na nova coleção, agoraordenada.

Claramente, a aplicação desse princípio básico de contagem a domínios commuitos valores torna-se inviável. Por exemplo, se os elementos são inteiros de 32bits, o algoritmo de contagem básico precisaria de uma tabela com cerca de quatrobilhões (232) de contadores.

Radix sort é um algoritmo baseado neste conceito de ordenação por contagemque contorna este problema ao aplicar o princípio da ordenação por contagem a umaparte da representação do elemento, a raiz. O procedimento é repetido para a raizseguinte até que toda a representação dos elementos tenha sido analisada. Por exem-plo, a ordenação de chaves inteiras com 32 bits pode ser realizada em quatro passosusando uma raiz de oito bits, sendo que a tabela de contadores requer apenas 256(28) entradas.


O procedimento para execução de radix sort é descrito no Algoritmo 2.11. Paraessa descrição, assumiu-se que elementos do vetor são inteiros positivos, que serãoanalisados em blocos de R bits a cada passo. As variáveis internas ao procedimentosão pass, que controla o número de passos executados e também qual parte do ele-mento está sob análise, iniciando pelos R bits menos significativos; pos, que indicaqual posição do vetor está sob análise; radixV alue, o valor da parte do elemento(entre 0 e 2R − 1) no passo atual; count, a tabela de contadores; e Taux, uma cópiado vetor ordenado segundo a raiz sob análise ao final de cada passo. A notação dxedenota o menor inteiro cujo valor é maior ou igual a x.

Algoritmo 2.11 Ordenação de vetor por radixsort.RADIXSORT(VECTOR T, INTEGER R)

1 declare pass, pos, radixV alue : INTEGER

2 declare count : array[2R] of INTEGER

3 declare Taux : VECTOR

4 for pass← 1 to dSIZEOFBITS(INTEGER)/Re5 do for radixV alue← 0 to 2R − 16 do count[radixV alue]← 07 for pos← 0 to T.size()− 18 do radixV alue← (T [pos] >> (R× (pass− 1))) & (2R − 1)9 count[radixV alue]← count[radixV alue] + 1

10 for radixV alue← 1 to 2R − 111 do count[radixV alue]← count[radixV alue] + count[radixV alue− 1]12 for pos← T.size()− 1 to 013 do radixV alue← (T [pos] >> (R× (pass− 1))) & (2R − 1)14 Taux[count[radixV alue]]← T [pos]15 count[radixV alue]← count[radixV alue]− 116 T ← Taux

O laço mais externo do algoritmo RADIXSORT (linhas 4 a 16) é repetido tantasvezes quantas forem necessárias para que a chave toda seja analisada em blocos detamanho R bits. Utiliza-se na linha 4 um operador SIZEOFBITS para determinaro tamanho do elemento em bits. Em C ou C++, este seria implementado com ooperador sizeof, que retorna o tamanho do tipo em bytes, e a informação sobrequantos bits há em um byte.

O primeiro laço interno do algoritmo (linhas 5 e 6) simplesmente inicializa oarranjo de contadores, pois este será reutilizado em todos os demais passos do laço.No laço seguinte (linhas 7 a 9), o vetor é percorrido para avaliar o valor da raiz emcada posição (linha 8, usando os operadores binários SHIFT, >> e AND, &) e assimatualizar a contagem de valores (linha 9).

Na seqüência (linhas 10 e 11), gera-se a soma acumulada de contadores, o quepermite avaliar quantas chaves com raiz de valor menor que o indicado existem. Essainformação permitirá que, no próximo laço (linhas 12 a 15), o vetor auxiliar Taux seja

2.5. Comparação das estruturas 54

preenchido colocando cada entrada do vetor T na nova posição que lhe correspondesegundo esse valor de raiz; cada vez que uma entrada é colocada na tabela, o valordo contador associado deve ser decrementado (linha 15) para que o elemento coma próxima raiz de mesmo valor seja colocada na posição correta, anterior à últimaocupada.

Finalmente, o vetor T recebe a tabela ordenada segundo a raiz e o procedimentoé repetido para o bloco de bits seguinte da chave. Após a varredura do último bloco(o mais significativo), o vetor estará completamente ordenada.

Este algoritmo requer, para seu correto funcionamento, que a ordenação utilizadaem cada etapa intermediária seja estável, ou seja, que dois elementos com mesmovalor mantenham suas posições relativas na nova seqüência ordenada. Radix sort éum algoritmo rápido, mas apresenta como principal desvantagem a necessidade deespaço adicional de memória — uma área do mesmo tamanho ocupado pelo conjuntode elementos sendo ordenado é necessária para receber os dados re-ordenados apóscada contagem. Quando o espaço de memória não é um recurso limitante, radix sorté um algoritmo atrativo, com complexidade temporal linear O(n).

2.5 Comparação das estruturasAs estratégias de implementação apresentadas nesta seção são amplamente utili-

zadas em estruturas de dados e a STL as aplica na construção das suas classes queimplementam as coleções.

Arranjos são utilizados na implementação de vector e deque. O espaço ocu-pado por essas estruturas é mantido internamente pela estrutura; se a inserção deum elemento excede a capacidade de armazenamento reservado, um novo arranjo éalocado e o conteúdo do arranjo antigo é transferido para o novo. Se o programadortem uma noção da dimensão máxima de uma dessas estruturas, ele pode utilizar ométodo allocate para reservar espaço suficiente.

A classe list implementa uma lista duplamente ligada. Se o custo de manter ainformação adicional para permitir a varredura da lista no sentido do fim para o iníciofor supérfluo, ou seja, se esse tipo de varredura não for necessário na aplicação, entãoa classe slist, que implementa uma lista simplesmente ligada, deve ser utilizada.

Árvores são utilizadas na implementação das classes que implementam estruturasassociativas, set e map, e em suas versões que permitem repetições, multiset emultimap. No entanto, para cada uma dessas classes existe uma versão que ofereceexatamente o mesmo conjunto de operações mas que utiliza hashing para a imple-mentação: hash_set, hash_map, hash_multiset e hash_multimap.

A grande vantagem na utilização da tabela hash está no desempenho — enquantoa busca linear tem complexidade temporal O(N) e a busca binária tem complexidadeO(log N), o tempo de busca na tabela hash é praticamente independente do númerode chaves armazenadas na tabela, ou seja, tem complexidade temporal O(1). Apli-cando a função hash no momento de armazenar e no momento de buscar a chave,a busca pode se restringir diretamente àquela posição da tabela gerada pela função.


Outro aspecto importante é que as estratégias mais eficientes baseadas em compa-ração, com vetores ordenados ou árvores binárias, demandam que o conjunto devalores assumido pelas chaves seja ordenável, algo que não é necessário em hashing.No entanto, o desempenho de hashing pode degradar sensivelmente em situações nasquais um grande número de colisões pode ocorrer.

Documents

Capítulo 2 Princípios de estruturas de dados - DCA-Wikicalhau.dca.fee.unicamp.br/wiki/images/5/5b/Cap2.pdf · 33 Princípios de estruturas de dados ocupada na coleção (Figura