Multilistas
Definição: É um tipo de lista onde cada nó contém mais de um apontador.
Logo, um lista duplamente encadeada é um exemplo de multilista (lista com ligações múltiplas).
Outro exemplo é conhecido como matriz esparsa, na qual o nó será alocado quando a posição receber um valor. Uma das vantagens dessa estrutura é a economia de espaço quando o número de elementos da matriz preenchidos é bem menor que a da matriz esparsa.
Quando a matriz não é esparsa, perde-se bastante espaço pois é necessário armazenar para cada nó, além do valor em si:
Dada a matriz com valores 2 (2,2), 3 (2,3) -2 (3,1) e 8 (3,3), mostrada abaixo:
| 0 | 0 | 0 |
| 0 | 2 | 3 |
| -2 | 0 | 8 |
Teríamos graficamente a estrutura:
Para ver uma implementação de uma Matriz Esparsa, abra a unit MatEsp e para um programa que demonstra como usá-la, veja DMatEsp.
O procedimento Inicializar cria a linha 0 e a coluna 0 e ajusta os apontadores. Supondo que desejamos criar uma matriz esparsa com 3 linhas e 2 colunas, ao chamarmos Inicializar, teríamos a matriz abaixo:
A função ObterAcima retorna o apontador para o nó que está acima da linha e da coluna especificados. Da mesma forma, A função ObterEsquerda retorna o apontador para o nó que está à esquerda da linha e da coluna especificados. Em ambos os casos, quando o nó não existir, o apontador retornado é necessário para inserir o nó naquela posição.