Tipo de dados abstratos

Da Wikipédia, a enciclopédia livre
Ir para navegação Pular para pesquisar

Na ciência da computação , um tipo abstrato de dados ( ADT ) é um modelo matemático para tipos de dados . Um tipo de dado abstrato é definido por seu comportamento ( semântica ) do ponto de vista de um usuário , dos dados, especificamente em termos de valores possíveis, operações possíveis em dados desse tipo e o comportamento dessas operações. Este modelo matemático contrasta com as estruturas de dados , que são representações concretas de dados e são o ponto de vista de um implementador, não de um usuário.

Formalmente, um TAD pode ser definido como uma "classe de objetos cujo comportamento lógico é definido por um conjunto de valores e um conjunto de operações"; [1] isso é análogo a uma estrutura algébrica em matemática. O que se entende por "comportamento" varia de acordo com o autor, com os dois principais tipos de especificações formais para comportamento sendo a especificação axiomática (algébrica) e um modelo abstrato; [2] estes correspondem à semântica axiomática e semântica operacional de uma máquina abstrata , respectivamente. Alguns autores também incluem a complexidade computacional("custo"), tanto em termos de tempo (para operações de computação) quanto de espaço (para representação de valores). Na prática, muitos tipos de dados comuns não são ADTs, pois a abstração não é perfeita e os usuários devem estar cientes de problemas como estouro aritmético que são devidos à representação. Por exemplo, os inteiros são freqüentemente armazenados como valores de largura fixa (números binários de 32 ou 64 bits) e, portanto, sofrem um estouro de inteiros se o valor máximo for excedido.

ADTs são um conceito teórico, em ciência da computação, usado no projeto e análise de algoritmos , estruturas de dados e sistemas de software, e não correspondem a recursos específicos de linguagens de computador - as linguagens de computador principais não suportam diretamente ADTs formalmente especificados. No entanto, vários recursos de linguagem correspondem a certos aspectos dos ADTs e são facilmente confundidos com os ADTs propriamente ditos; isso inclui tipos abstratos , tipos de dados opacos , protocolos e projeto por contrato . Os ADTs foram propostos pela primeira vez por Barbara Liskov e Stephen N. Zilles em 1974, como parte do desenvolvimento da linguagem CLU . [3]

Exemplos

Por exemplo, inteiros são um ADT, definidos como os valores ..., −2, −1, 0, 1, 2, ..., e pelas operações de adição, subtração, multiplicação e divisão, junto com maior que , menor que, etc., que se comportam de acordo com a matemática familiar (com cuidado para a divisão de inteiros ), independentemente de como os inteiros são representados pelo computador. [a] Explicitamente, "comportamento" inclui obedecer a vários axiomas (associatividade e comutatividade de adição, etc.) e pré-condições nas operações (não pode ser dividido por zero). Normalmente, os inteiros são representados em uma estrutura de dados como números binários , na maioria das vezes como complemento de dois , mas podem ser decimais com codificação binária ou emum complemento , mas o usuário é abstraído da escolha concreta de representação e pode simplesmente usar os dados como tipos de dados.

Um ADT consiste não apenas em operações, mas também em valores dos dados subjacentes e em restrições nas operações. Uma "interface" normalmente se refere apenas às operações e talvez algumas das restrições nas operações, notavelmente pré-condições e pós-condições, mas não outras restrições, como relações entre as operações.

Por exemplo, uma pilha abstrata , que é uma estrutura last-in-first-out, poderia ser definida por três operações push:, que insere um item de dados na pilha; pop, que remove um item de dados dele; e peekou top, que acessa um item de dados no topo da pilha sem remoção. Uma fila abstrata , que é uma estrutura first-in-first-out, também teria três operações enqueue:, que insere um item de dados na fila; dequeue, que remove o primeiro item de dados dele; efront, que acessa e fornece o primeiro item de dados na fila. Não haveria maneira de diferenciar esses dois tipos de dados, a menos que uma restrição matemática fosse introduzida para que uma pilha especifique que cada pop sempre retorna o item empurrado mais recentemente que ainda não foi exibido. Ao analisar a eficiência de algoritmos que usam pilhas, pode-se também especificar que todas as operações levam o mesmo tempo, não importa quantos itens de dados foram colocados na pilha, e que a pilha usa uma quantidade constante de armazenamento para cada elemento.

Introdução

Tipos de dados abstratos são entidades puramente teóricas, usadas (entre outras coisas) para simplificar a descrição de algoritmos abstratos, para classificar e avaliar estruturas de dados e para descrever formalmente os sistemas de tipo de linguagens de programação. No entanto, um ADT pode ser implementado por tipos de dados ou estruturas de dados específicos , de muitas maneiras e em muitas linguagens de programação; ou descrito em uma linguagem de especificação formal . ADTs são frequentemente implementados como módulos : a interface do módulo declara procedimentos que correspondem às operações de ADT, às vezes com comentários que descrevem as restrições. Esta informação escondidaA estratégia permite que a implementação do módulo seja alterada sem perturbar os programas do cliente .

O termo tipo de dados abstratos também pode ser considerado uma abordagem generalizada de várias estruturas algébricas , como reticulados, grupos e anéis. [4] A noção de tipos de dados abstratos está relacionada ao conceito de abstração de dados , importante na programação orientada a objetos e design por meio de metodologias de contrato para desenvolvimento de software . [5]

A definição de um tipo de dado abstrato

Um tipo de dados abstrato é definido como um modelo matemático dos objetos de dados que constituem um tipo de dados, bem como as funções que operam nesses objetos. Não há convenções padrão para defini-los. Uma ampla divisão pode ser traçada entre os estilos de definição "imperativo" e "funcional".

Definição de estilo imperativo

Na filosofia das linguagens de programação imperativas , uma estrutura de dados abstrata é concebida como uma entidade que é mutável - o que significa que pode estar em estados diferentes em momentos diferentes. Algumas operações podem alterar o estado do ADT; portanto, a ordem em que as operações são avaliadas é importante, e a mesma operação nas mesmas entidades pode ter efeitos diferentes se executada em momentos diferentes - exatamente como as instruções de um computador ou os comandos e procedimentos de uma linguagem imperativa. Para enfatizar essa visão, é costume dizer que as operações são executadas ou aplicadas , ao invés de avaliadas. O estilo imperativo é freqüentemente usado ao descrever algoritmos abstratos. (Veja The Art of Computer Programming de Donald Knuth para mais detalhes)

Variável abstrata

As definições de estilo imperativo de ADT freqüentemente dependem do conceito de uma variável abstrata , que pode ser considerada como a ADT não trivial mais simples. Uma variável abstrata V é uma entidade mutável que admite duas operações:

  • store( V , x ) onde x é um valor de natureza não especificada;
  • fetch( V ), que produz um valor,

com a restrição de que

  • fetch( V ) sempre devolve o valor de x usado na mais recente store( V , x ) operação na mesma variável V .

Como em muitas linguagens de programação, a operação store( V , x ) é freqüentemente escrita Vx (ou alguma notação semelhante), e fetch( V ) está implícita sempre que uma variável V é usada em um contexto onde um valor é necessário. Assim, por exemplo, VV + 1 é comumente entendido como uma abreviação para store( V , fetch( V ) + 1).

Nesta definição, assume-se implicitamente que o armazenamento de um valor para uma variável L tem qualquer efeito sobre o estado de uma variável distinta V . Para tornar esta suposição explícita, pode-se adicionar a restrição de que

  • se U e V são variáveis ​​distintas, a sequência { store( U , x ); store( V , y )} é equivalente a { store( V , y ); store( U , x )}.

De forma mais geral, as definições de ADT muitas vezes assumem que qualquer operação que altera o estado de uma instância de ADT não tem efeito sobre o estado de qualquer outra instância (incluindo outras instâncias do mesmo ADT) - a menos que os axiomas de ADT impliquem que as duas instâncias estão conectadas ( alias ) nesse sentido. Por exemplo, quando se estende a definição de uma variável de sumário para incluir sumário registos , a operação que selecciona um campo de uma variável ficha R deve produzir uma variável V que é alias a que parte de R .

A definição de uma variável resumo V pode também restringir os valores armazenados x para os membros de um conjunto específico X , chamado o gama ou tipo de V . Como nas linguagens de programação, tais restrições podem simplificar a descrição e análise de algoritmos e melhorar sua legibilidade.

Note-se que esta definição não implica nada sobre o resultado da avaliação fetch( V ) quando V é un-inicializado , isto é, antes de realizar qualquer storeoperação em V . Um algoritmo que faz isso geralmente é considerado inválido porque seu efeito não está definido. (No entanto, existem alguns algoritmos importantes cuja eficiência depende fortemente da suposição de que tal fetché legal e retorna algum valor arbitrário no intervalo da variável. [ Carece de fontes ? ] )

A criação da instância

Alguns algoritmos precisam criar novas instâncias de alguns ADT (como novas variáveis ​​ou novas pilhas). Para descrever tais algoritmos, geralmente inclui-se na definição de ADT uma createoperação () que produz uma instância de ADT, geralmente com axiomas equivalentes a

  • o resultado de create() é diferente de qualquer instância em uso pelo algoritmo.

Este axioma pode ser reforçado para excluir também aliasing parcial com outras instâncias. Por outro lado, esse axioma ainda permite implementações de create() para gerar uma instância criada anteriormente que se tornou inacessível para o programa.

Exemplo: Pilha abstrata (imperativo)

Como outro exemplo, uma definição de estilo imperativo de uma pilha abstrata poderia especificar que o estado de uma pilha S pode ser modificado apenas pelas operações

  • push( S , x ), onde x é algum valor de natureza não especificada;
  • pop( S ), que produz um valor como resultado,

com a restrição de que

  • Para qualquer valor x e qualquer variável abstrata V , a seqüência de operações { push( S , x ); Vpop( S )} é equivalente a Vx .

Como a atribuição Vx , por definição, não pode alterar o estado de S , essa condição implica que Vpop( S ) restaura S ao estado que tinha antes de push( S , x ). A partir desta condição e das propriedades das variáveis ​​abstratas, segue-se, por exemplo, que a sequência

{ push( S , x ); push( S , y ); Upop( S ); push( S , z ); Vpop( S ); Wpop( S )}

onde x , y e z são quaisquer valores, e U , V , W são variáveis ​​distintas entre pares, é equivalente a

{ Uy ; Vz ; Wx }

Aqui, é implicitamente assumido que as operações em uma instância de pilha não modificam o estado de nenhuma outra instância de ADT, incluindo outras pilhas; isso é,

  • Para quaisquer valores x , y e quaisquer pilhas distintas S e T , a sequência { push( S , x ); push( T , y )} é equivalente a { push( T , y ); push( S , x )}.

Uma definição de pilha abstrata geralmente inclui também uma função com valor booleanoempty ( S ) e uma createoperação () que retorna uma instância de pilha, com axiomas equivalentes a

  • create() ≠ S para qualquer pilha anterior S (uma pilha recém-criada é diferente de todas as pilhas anteriores);
  • empty( create()) (uma pilha recém-criada está vazia);
  • not empty( push( S , x )) (colocar algo em uma pilha a torna não vazia).

Estilo de instância única

Às vezes, um ADT é definido como se apenas uma instância dele existisse durante a execução do algoritmo e todas as operações fossem aplicadas a essa instância, o que não é explicitamente notado. Por exemplo, a pilha resumo acima poderia ter sido definida com as operações de push( x ) e pop(), que operam sobre a pilha única existente. As definições de ADT neste estilo podem ser facilmente reescritas para admitir várias instâncias coexistentes do ADT, adicionando um parâmetro de instância explícita (como S no exemplo anterior) para cada operação que usa ou modifica a instância implícita.

Por outro lado, alguns ADTs não podem ser definidos de forma significativa sem assumir várias instâncias. Esse é o caso quando uma única operação leva duas instâncias distintas do ADT como parâmetros. Por exemplo, considere aumentar a definição da pilha abstrata com uma operação compare( S , T ) que verifica se as pilhas S e T contêm os mesmos itens na mesma ordem.

Definição de estilo funcional

Outra forma de definir um ADT, mais próxima do espírito da programação funcional , é considerar cada estado da estrutura como uma entidade separada. Nessa visão, qualquer operação que modifique o ADT é modelada como uma função matemática que pega o antigo estado como um argumento e retorna o novo estado como parte do resultado. Ao contrário das operações imperativas, essas funções não têm efeitos colaterais . Portanto, a ordem em que são avaliados é irrelevante e a mesma operação aplicada aos mesmos argumentos (incluindo os mesmos estados de entrada) sempre retornará os mesmos resultados (e estados de saída).

Na visão funcional, em particular, não há maneira (ou necessidade) de definir uma "variável abstrata" com a semântica das variáveis ​​imperativas (a saber, com operações fetche store). Em vez de armazenar valores em variáveis, eles são passados ​​como argumentos para funções.

Exemplo: pilha sumário (funcional)

Por exemplo, uma definição completa de estilo funcional de uma pilha abstrata pode usar as três operações:

  • push: recebe um estado de pilha e um valor arbitrário, retorna um estado de pilha;
  • top: assume um estado de pilha, retorna um valor;
  • pop: assume um estado de pilha, retorna um estado de pilha.

Em uma definição de estilo funcional, não há necessidade de uma createoperação. Na verdade, não há noção de "instância de pilha". Os estados de pilha podem ser considerados estados potenciais de uma única estrutura de pilha, e os estados de duas pilhas que contêm os mesmos valores na mesma ordem são considerados estados idênticos. Na verdade, essa visualização reflete o comportamento de algumas implementações concretas, como listas vinculadas com hash cons .

Em vez de create(), uma definição de estilo funcional de uma pilha abstrata pode assumir a existência de um estado de pilha especial, a pilha vazia , designada por um símbolo especial como Λ ou "()"; ou defina uma bottomoperação () que não aceita argumentos e retorna este estado de pilha especial. Observe que os axiomas implicam que

  • push(Λ, x ) ≠ Λ.

Em uma definição de estilo funcional de uma pilha, não é necessário um emptypredicado: em vez disso, pode-se testar se uma pilha está vazia testando se ela é igual a Λ.

Observe que esses axiomas não definem o efeito de top( s ) ou pop( s ), a menos que s seja um estado de pilha retornado por a push. Uma vez que pushdeixa a pilha não vazia, essas duas operações são indefinidas (portanto, inválidas) quando s = Λ. Por outro lado, os axiomas (e a ausência de efeitos colaterais) implica que push( s , x ) = push( t , y ) se e só se x = y e s = t .

Como em alguns outros ramos da matemática, é costume assumir também que os estados da pilha são apenas aqueles cuja existência pode ser provada a partir dos axiomas em um número finito de etapas. No exemplo de pilha abstrata acima, essa regra significa que toda pilha é uma sequência finita de valores, que se torna a pilha vazia (Λ) após um número finito de pops. Por si só, os axiomas acima não excluem a existência de pilhas infinitas (que podem ser popeditadas para sempre, cada vez produzindo um estado diferente) ou pilhas circulares (que retornam ao mesmo estado após um número finito de pops). Em particular, eles não excluem estados s tais que pop( s ) = s ou push( s ,x ) = s para algum x . No entanto, uma vez que não é possível obter tais estados de pilha com as operações fornecidas, eles são considerados "não existentes".

Se deseja incluir complexidade

Além do comportamento em termos de axiomas, também é possível incluir, na definição de uma operação ADT, sua complexidade algorítmica . Alexander Stepanov , designer da C ++ Standard Template Library , incluiu garantias de complexidade na especificação STL, argumentando:

A razão para introduzir a noção de tipos de dados abstratos foi permitir módulos de software intercambiáveis. Você não pode ter módulos intercambiáveis, a menos que esses módulos compartilhem um comportamento de complexidade semelhante. Se eu substituir um módulo por outro módulo com o mesmo comportamento funcional, mas com diferentes compensações de complexidade, o usuário deste código ficará desagradavelmente surpreso. Eu poderia dizer a ele o que quiser sobre abstração de dados, e ele ainda não gostaria de usar o código. Asserções de complexidade devem fazer parte da interface.

-  Alexander Stepanov [6]

Vantagens de digitação de dados abstrato

Encapsulamento

A abstração fornece uma promessa de que qualquer implementação do ADT possui certas propriedades e habilidades; saber disso é tudo o que é necessário para usar um objeto ADT.

Localização de mudança

O código que usa um objeto ADT não precisará ser editado se a implementação do ADT for alterada. Uma vez que quaisquer alterações na implementação ainda devem estar em conformidade com a interface, e como o código que usa um objeto ADT pode se referir apenas a propriedades e habilidades especificadas na interface, as alterações podem ser feitas na implementação sem exigir quaisquer alterações no código onde o ADT é usado .

Flexibilidade

Implementações diferentes do ADT, tendo todas as mesmas propriedades e habilidades, são equivalentes e podem ser usadas de forma intercambiável no código que usa o ADT. Isso oferece uma grande flexibilidade ao usar objetos ADT em diferentes situações. Por exemplo, diferentes implementações do ADT podem ser mais eficientes em diferentes situações; é possível usar cada um na situação em que são preferíveis, aumentando assim a eficiência geral.

Operações típicas

Algumas operações que são frequentemente especificadas para ADTs (possivelmente com outros nomes) são

  • compare( s , t ), que testa se os estados de duas instâncias são equivalentes em algum sentido;
  • hash( s ), que calcula alguma função hash padrão do estado da instância;
  • print( s ) ou show( s ), que produz uma representação legível do estado da instância.

Nas definições de ADT de estilo imperativo, muitas vezes também se encontra

  • create(), que resulta em uma nova instância do ADT;
  • initialize( s ), que prepara uma instância recém-criada s para operações adicionais ou a redefine para algum "estado inicial";
  • copy( s , t ), que coloca a instância s em um estado equivalente ao de t ;
  • clone( t ), que executa screate(), copy( s , t ), e retorna s ;
  • free( s ) ou destroy( s ), que recupera a memória e outros recursos usados ​​por s .

A freeoperação normalmente não é relevante ou significativa, uma vez que ADTs são entidades teóricas que não "usam memória". No entanto, pode ser necessário quando se precisa analisar o armazenamento usado por um algoritmo que usa o ADT. Nesse caso, são necessários axiomas adicionais que especificam quanta memória cada instância de ADT usa, em função de seu estado, e por quanto é retornado ao pool free.

Exemplos

Alguns ADTs comuns, que se mostraram úteis em uma grande variedade de aplicações, são

Cada um desses ADTs pode ser definido de muitas maneiras e variantes, não necessariamente equivalentes. Por exemplo, uma pilha abstrata pode ou não ter uma countoperação que informa quantos itens foram empurrados e ainda não removidos. Essa escolha faz a diferença não só para seus clientes, mas também para a implementação.

Tipo de dados gráficos abstratos

Uma extensão do ADT para computação gráfica foi proposta em 1979: [7] um tipo abstrato de dados gráficos (AGDT). Foi apresentado por Nadia Magnenat Thalmann e Daniel Thalmann . Os AGDTs fornecem as vantagens dos ADTs com recursos para construir objetos gráficos de forma estruturada.

Implementação

Implementar um ADT significa fornecer um procedimento ou função para cada operação abstrata. As instâncias do ADT são representadas por alguma estrutura de dados concreta que é manipulada por esses procedimentos, de acordo com as especificações do ADT.

Normalmente, existem muitas maneiras de implementar o mesmo ADT, usando várias estruturas de dados concretas diferentes. Assim, por exemplo, uma pilha abstrata pode ser implementada por uma lista encadeada ou por um array .

Para evitar que os clientes dependam da implementação, um ADT é frequentemente empacotado como um tipo de dados opaco em um ou mais módulos , cuja interface contém apenas a assinatura (número e tipos dos parâmetros e resultados) das operações. A implementação do módulo - ou seja, os corpos dos procedimentos e a estrutura de dados concreta usada - pode então ser ocultada da maioria dos clientes do módulo. Isso permite alterar a implementação sem afetar os clientes. Se a implementação for exposta, ela será conhecida como um tipo de dados transparente.

Ao implementar um ADT, cada instância (em definições de estilo imperativo) ou cada estado (em definições de estilo funcional) é geralmente representado por um identificador de algum tipo. [8]

Linguagens orientadas a objetos modernas, como C ++ e Java , suportam uma forma de tipos de dados abstratos. Quando uma classe é usada como um tipo, é um tipo abstrato que se refere a uma representação oculta. Nesse modelo, um ADT é geralmente implementado como uma classe , e cada instância do ADT é geralmente um objeto dessa classe. A interface do módulo normalmente declara os construtores como procedimentos comuns e a maioria das outras operações ADT como métodosdessa classe. No entanto, essa abordagem não encapsula facilmente várias variantes representacionais encontradas em um ADT. Também pode prejudicar a extensibilidade dos programas orientados a objetos. Em um programa puramente orientado a objetos que usa interfaces como tipos, os tipos referem-se a comportamentos, não a representações.

Exemplo: implementação da pilha abstrato

Como exemplo, aqui é uma implementação da pilha abstrato acima na linguagem de programação C .

-Estilo imperativo de interface

Uma interface de estilo imperativo pode ser:

typedef struct stack_Rep stack_Rep ; // tipo: representação da instância da pilha (registro opaco) typedef stack_Rep * stack_T ; // tipo: manipula para uma instância de pilha (ponteiro opaco) typedef void * stack_Item ; // tipo: valor armazenado na instância da pilha (endereço arbitrário)          
                 
                   

stack_T stack_create ( vazio ); // cria uma nova instância de pilha vazia void stack_push ( stack_T s , stack_Item x ); // adiciona um item no topo da pilha stack_Item stack_pop ( stack_T s ); // remove o item do topo da pilha e o retorna bool stack_empty ( stack_T s ); // verifica se a pilha está vazia                
     
            
                

Essa interface pode ser usada da seguinte maneira:

#include <stack.h>           // inclui a interface de pilha 

stack_T s = stack_create (); // cria uma nova instância de pilha vazia int x = 17 ;    
   
stack_push ( s , & x ); // adiciona o endereço de x no topo da pilha void * y = stack_pop ( s ); // remove o endereço de x da pilha e o retorna se ( stack_empty ( s )) { } // faz algo se a pilha estiver vazia           
        
        

Essa interface pode ser implementada de várias maneiras. A implementação pode ser arbitrariamente ineficiente, uma vez que a definição formal do ADT, acima, não especifica quanto espaço a pilha pode ocupar, nem quanto tempo cada operação deve ocupar. Também não especifica se o estado da pilha s continua a existir após uma chamada xpop( s ).

Na prática, a definição formal deve especificar que o espaço é proporcional ao número de itens empurrados e ainda não pop; e que cada uma das operações acima deve terminar em um período de tempo constante, independentemente desse número. Para cumprir essas especificações adicionais, a implementação pode usar uma lista vinculada ou uma matriz (com redimensionamento dinâmico) junto com dois inteiros (uma contagem de itens e o tamanho da matriz).

-Estilo funcional de interface

As definições de ADT de estilo funcional são mais apropriadas para linguagens de programação funcional e vice-versa. No entanto, pode-se fornecer uma interface de estilo funcional, mesmo em uma linguagem imperativa como C. Por exemplo:

typedef struct stack_Rep stack_Rep ; // tipo: representação do estado da pilha (registro opaco) typedef stack_Rep * stack_T ; // tipo: manipula para um estado de pilha (ponteiro opaco) typedef void * stack_Item ; // tipo: valor de um estado de pilha (endereço arbitrário)             
                    
                      

stack_T stack_empty ( vazio ); // retorna o estado da pilha vazia stack_T stack_push ( stack_T s , stack_Item x ); // adiciona um item no topo do estado da pilha e retorna o estado da pilha resultante stack_T stack_pop ( stack_T s ); // remove o item superior do estado da pilha e retorna o estado da pilha resultante stack_Item stack_top ( stack_T s ); // retorna o item superior do estado da pilha                    
     
                  
               

Bibliotecas ADT

Muitas linguagens de programação modernas, como C ++ e Java, vêm com bibliotecas padrão que implementam vários ADTs comuns, como os listados acima.

Built-in tipos de dados abstratos

A especificação de algumas linguagens de programação é intencionalmente vaga sobre a representação de certos tipos de dados embutidos, definindo apenas as operações que podem ser feitas neles. Portanto, esses tipos podem ser vistos como "ADTs integrados". Os exemplos são os arrays em muitas linguagens de script, como Awk , Lua e Perl , que podem ser considerados como uma implementação da lista abstrata.

Veja também

Notas

  1. ^ Compare com a caracterização de inteiros em álgebra abstrata.

Citations

  1. ^ Dale & Walker 1996 , p. 3
  2. ^ Dale & Walker 1996 , p. 4
  3. ^ Liskov & Zilles 1974 .
  4. ^ Rudolf Lidl (2004). Álgebra abstrata . Springer. ISBN 978-81-8128-149-4., Capítulo 7, seção 40.
  5. ^ "O que é programação orientada a objetos?" . Contratação | Upwork . 05-05-2015 . Página visitada em 2016-10-28 .
  6. ^ Stevens, Al (março de 1995). "Entrevistas de Al Stevens com Alex Stepanov" . Diário do Dr. Dobb . Retirado em 31 de janeiro de 2015 .
  7. ^ D. Thalmann, N. Magnenat Thalmann (1979). Projeto e implementação de tipos de dados gráficos abstratos . IEEE. doi : 10.1109 / CMPSAC.1979.762551 ., Proc. 3ª Conferência Internacional de Software e Aplicativos de Computador (COMPSAC'79), IEEE, Chicago, EUA, pp.519-524
  8. ^ Robert Sedgewick (1998). Algoritmos em C . Addison / Wesley. ISBN 978-0-201-31452-6., definição 4.4.

Referências

Outras leituras

Ligações externas