• Listas Cruzadas

  • INFO:
  • Linha :
  • Coluna :

  • HUB

  • 1/1

  • Linhas:

  • Colunas:

Informações da Estrutura
Estrutura de Dados

NoLista

{

  valor : String;

  abaixo : NoLista;

  direita : NoLista;

  linha : inteiro;

  coluna : inteiro;

}

EstruturaListaCruzada

{

  Colunas : vetor de NoLista;

  Linhas : vetor de NoLista;

}

Constantes

N_LINHAS : inteiro;

N_COLUNAS : inteiro;

Descrição
Matrizes Esparsas possuem uma grande quantidade elementos nulos ou repetidos, nos quais ocupam quantidade desnecessária de memória. A estrutura em lista cruzada é uma das soluções para este problema. A Matriz é representada por várias listas que se entrelaçam, onde cada elemento na estrutura é um elemento não-nulo que está ligado com o próximo elemento na coluna, ou na linha, também não-nulo. A informação dentro do nó não afeta o fluxo de execução do algoritmo, apenas a posição da linha e da coluna.

Mais informações
Implementação: Realizada por meio de dois vetores de tamanho fixo onde cada uma possui listas encadeadas que se entrelaçam.

Regras: Cada elemento na estrutura é um elemento não-nulo que está ligado com o próximo elemento na coluna, ou na linha, também não-nulo.

Aplicação: Armazenamento, Grafos, entre outros.

Requisitos para aplicação: Geralmente a aplicação requer que os dados permaneçam intactos, caso contrário, utiliza-se compreensão de dados.

Vantagem: Armazena somente o número necessário de elementos.

Desvantagem: Maior complexidade no algoritmo e custo pode aumentar devido aos ponteiros não utilizados.
FUNÇÃO
Insere(INFO,Linha,Coluna)

leitorColuna,leitorLinha : NoLista;

anteriorColuna,anteriorLinha : NoLista;

i,j : inteiro;

 

novo : NoLista;

novo := alocar();

novo.linha := Linha;

novo.coluna := Coluna;

novo.info := INFO;

 

leitorColuna := Colunas[Coluna];

leitorLinha := Linhas[Linha];

 

Se leitorColuna != nulo então

INICIO

i := Colunas[Coluna].linha;

 

Enquanto leitorColuna.abaixo != nulo e i < Linha faça

INICIO

anteriorColuna := leitorColuna;

leitorColuna := leitorColuna.abaixo;

i := leitorColuna.linha;

FIM

 

Se i == Linha então

INICIO

leitorColuna.info := INFO;

Retornar;

FIM

 

Se leitorColuna.abaixo != nulo então

INICIO

Se anteriorColuna == nulo então

INICIO

novo.abaixo := leitorColuna;

Colunas[Coluna] := novo;

FIM

Senão

INICIO

novo.abaixo := leitorColuna;

anteriorColuna.abaixo := novo;

FIM

FIM

Senão

INICIO

novo.abaixo := nulo;

anteriorColuna.abaixo := novo;

FIM

FIM

Senão

INICIO

Colunas[Coluna] := novo;

novo.abaixo := nulo;

FIM

 

Se leitorLinha != nulo então

INICIO

j := Linhas[Linha].coluna;

 

Enquanto leitorLinha.direita != nulo e j < Coluna faça

INICIO

anteriorLinha := leitorLinha;

leitorLinha := leitorLinha.direita;

j := leitorLinha.coluna;

FIM

 

Se leitorLinha.direita != nulo então

INICIO

Se anteriorLinha == nulo então

INICIO

novo.direita := leitorLinha;

Linhas[Linha] := novo;

FIM

Senão

INICIO

novo.direita := leitorLinha;

anteriorLinha.direita := novo;

FIM

FIM

Senão

INICIO

novo.direita := nulo;

anteriorLinha.direita := novo;

FIM

FIM

Senão

INICIO

Linhas[Linha] := novo;

novo.direita := nulo;

FIM

FUNÇÃO
Remove(Linha,Coluna)

leitorLinha,anteriorLinha : NoLista;

leitorColuna,anteriorColuna : NoLista;

 

leitorLinha := Linhas[Linha];

 

Enquanto leitorLinha != nulo e leitorLinha.coluna != Coluna faça

INICIO

anteriorLinha := leitorLinha;

leitorLinha := leitorLinha.direita;

FIM

 

Se leitorLinha != nulo então

INICIO

leitorColuna := Colunas[Coluna];

 

Enquanto leitorColuna != leitorLinha faça

INICIO

anteriorColuna := leitorColuna;

leitorColuna := leitorColuna.abaixo;

FIM

 

Se anteriorLinha != nulo então

anteriorLinha.direita := leitorLinha.direita;

Senão

Linhas[Linha] := leitorLinha.direita;

 

Se anteriorColuna != nulo então

anteriorColuna.abaixo := leitorColuna.abaixo;

Senão

Colunas[Coluna] := leitorColuna.abaixo;

FIM

FUNÇÃO
Busca(Linha,Coluna)
RETORNA
O valor linha i e coluna j

leitor : NoLista;

leitor := Linhas[Linha];

 

Enquanto leitor != nulo então

INICIO

Se leitor.coluna == Coluna então

Retornar leitor.info;

leitor := leitor.direita;

FIM

Retornar nulo;

Última animação

Nenhuma animação disponível para revisar!

Executando animação ...

Aguarde encerrar !

Última animação que foi executada:

# Descrição
Entradas Programadas

Configurações

Entradas

Limpar entrada ao final da animação

Chance de gerar número negativo na entrada aleatória:

50%

Estrutura

Ocultar Ponteiros Nulos

Impedir inserção de valores repetidos

Mostrar Descritores

Cor do componente primário

Cor do componente secundário

Código

Usar delimitador em chaves

Contar linhas brancas

Configurações serão salvas para este navegador
Histórico
    • #
    • INFO
    • Vazio
Principal
Menu das Estruturas

  • Pseudo-código

  • Informações da Estrutura

  • Entradas Programadas

  • Rever Passos

  • Histórico

Listas Cruzadas

  • Vazio
Logo

Estruturas

Listas

Sem ordenação

Simples

Dupla

Com ordenação

Simples

Dupla

Estática

Cruzada

Filas

Estáticas

Simples

Circular

Dinâmicas

Normal

Com Prioridade

Circular

Pilhas

Estáticas

Simples

Múltipla

Dinâmicas

Simples

Hashing

Sem Tratamento

Simples

Com Tratamento

Listas Encadeadas

Área de Overflow

Árvores

Balanceadas

AVL

Rubro-Negra

B

Não Balanceadas

Binária

Trie

Patricia
Histórico

Lista Ordenada Simples

Lista Ordenada Estática

Lista Ordenada Dupla

Lista Sem Ordenação Simples

Lista Sem Ordeneção Dupla

Lista Cruzada

Fila Estática

Fila Estática Circular

Fila com Prioridade

Fila Dinâmica

Fila Circular

Pilha Estática

Pilha Múltipla

Pilha Dinâmica

Hash sem Tratamento

Hash com Tratamento

Hash com Overflow

Árvore AVL

Árvore B

Árvore RubroNegra

Árvore Binária

Árvore Trie

Árvore Patricia

Estrutura não encontrada