Como implementar uma lista de ligação no Visual Basic

A lista ligada, o que é uma estrutura de dados clássica com executarão Aplicabilidade em C++, também pode ser implementada no Visual Basic com a utilização de classes.

Uma lista ligada é um conjunto de itens organizados sequencialmente, tal como uma matriz. Numa matriz, a organização sequencial é fornecida implicitamente (pela posição da matriz); numa lista ligada, utilize uma disposição explícita em que cada item é parte de um "nó" que também contém uma "ligação" para o nó seguinte.

A vantagem principal de listas ligadas através de matrizes é que listas ligadas podem aumentar e diminuir tamanho durante as respectivas durações. Em particular, seu tamanho máximo necessário não ser conhecido antecipadamente. Uma vantagem secundária é que fornecem flexibilidade de permitir que os produtos a ser reorganizadas eficientemente sem realmente mover quaisquer dados contidos na lista.

Uma desvantagem de uma lista ligada é que operações como referenciar um elemento específico na lista requerem a deslocar-se a lista completa de cabeça à cauda. Numa matriz, pode simplesmente fazê-lo a aceder a uma (n). Outra operação que não funciona com uma lista ligada está a localizar um item antes de um determinado item. Para contornar estas limitações, pode criar uma lista doubly ligadas em que duas ligações para cada nó são mantidas, uma para o item antes de e para o item depois. O custo de fornecer esta capacidade adicional é duplicando o número de manipulações de ligação por operação básica. Este artigo só vai demonstrar uma simples lista ligada, não uma lista ligada doubly.

Programas de exemplo

O exemplo seguinte cria uma lista ligada de 20 nós e inverte-lo utilizando uma função denominada ReverseList. Cada nó na lista é realmente uma instância de uma classe do Visual Basic criado com a nova palavra-chave.

1. Inicie um novo projecto no Visual Basic e escolha "EXE padrão." É criado o Form1 por predefinição.
2. No menu ' projecto ', escolha ' Adicionar módulo de classe, Aula1 é criado por predefinição. Na janela Propriedades do novo módulo de classe, altere o nome do Aula1 para "Nó" e, em seguida, colar o código seguinte na secção General Declarations do nó:

         Public key As Integer          'var to hold some data
         Public pnext As node           'pointer to next node in list
   
   						

3. Adicione um botão de comando Command1, ao Form1.
4. Cole o código seguinte na secção General Declarations do Form1:

         Dim head As node               'object pointer to head of list
         Private Sub Form_Load()
           Dim curr As node             'object pointer to current pos in
           Dim i As Integer             'list used in For loop
   
           'CREATE LIST
           Set head = New node          'object pointer to new node
           head.Key = 0                 'dummy head
           Set curr = head              'keep head pointer here
           For i = 1 To 20              'iterate n times to fill list
             Set curr.pnext = New node  'insert new node after current
             Set curr = curr.pnext      'set current one = new node
             curr.Key = i               'set new node key value
           Next i
           Set curr.pnext = New node    'dummy tail
           Set curr = curr.pnext        'move current to dummy tail
           curr.Key = 0                 'set value of dummy tail
           Set curr.pnext = curr        'points to itself to identify end
   
           Debug.Print "before: " & DumpList(head) 'print list
         End Sub
   
         Private Sub Command1_click()
           'RERVERSE LIST
           ReverseList head             'pass in head to ReverseList
           Debug.Print "after: " & DumpList(head)  'print reversed list
         End Sub
   
         Private Sub ReverseList(ByRef head As node)
           'reverse entire list including dummy head and tail
           'Note: head becomes tail, tail becomes head
           Dim curr As node             'object pointer to current node
           Dim nexx As node             'object pointer to next node
           Set curr = head.pnext        'current to node after head
           Set head.pnext = head        'turn head into tail
           While Not curr.pnext Is curr 'walk entire list
             Set nexx = curr.pnext      'pointer to node after current
             Set curr.pnext = head      'current points back to head
             Set head = curr            'move head to current
             Set curr = nexx            'set current = next node
           Wend
           Set curr.pnext = head        'point new head to first node
           Set head = curr              'return head to first position
         End Sub
   
         Private Function DumpList(ByRef head As node) As String
           'walk list and dump to debug window
           Dim strOut As String         'temp var to hold string
           Dim curr As node             'object pointer to current node
           Set curr = head.pnext        'skip dummy head
           While Not curr.pnext Is curr 'walk rest of list to end
             strOut = strOut & " " & CStr(curr.Key)
             Set curr = curr.pnext      'current pointer to next node
           Wend
           DumpList = strOut            'return string
         End Function
   
   						

5. Iniciar o programa ou prima a tecla F5. Será criada uma lista de 20 nós ligada.
6. Clique no botão Command1 para inverter a lista e imprimir os resultados para a janela de depuração.

Algoriths no C++, Robert Sedegwick, ISBN 0-201-51059-6

(c) 1997 Microsoft Corporation, todos os direitos reservados. Contribuições de João Fowler, Microsoft Corporation