Matriz Esparsa

Programação Java
#1

gente to precisando urgente de ajuda pra um projeto da facul, como eu faço pra implementar uma Matriz Esparsa em uma LinkedList?
abraço

#2

[quote=nipo_style]gente to precisando urgente de ajuda pra um projeto da facul, como eu faço pra implementar uma Matriz Esparsa em uma LinkedList?
abraço[/quote]

Uma implementação simples seria criar uma classe Elemento que possui um valor (o número diferente de zero em uma dada posição Xij) e o índice j (coluna) deste número em sua respectiva linha. Você pode criar um array de listas encadeadas, sendo que estas listas guardam objetos da classe Elemento.

Assim, a seguinte matriz esparsa

! 0 0 0 5 6 0 3 !
! 0 7 0 0 0 0 0 !
! 0 0 0 4 0 0 0 !
! 0 3 0 0 6 0 3 !

Poderia ser representada como

array      listas encadeadas
0 ===> (valor = 5, coluna = 3), (valor = 6, coluna = 4), (valor = 3, coluna = 6)
1 ===> (valor = 7, coluna = 1)
2 ===> (valor = 4, coluna = 3)
3 ===> (valor = 3, coluna = 2), (valor = 6, coluna = 4), (valor = 3, coluna = 6)
#3

[quote=nipo_style]gente to precisando urgente de ajuda pra um projeto da facul, como eu faço pra implementar uma Matriz Esparsa em uma LinkedList?
abraço[/quote]

Use duas linked lists. Uma com as linhas, que aponta para outra com as colunas:

List<List> matrixEsparsa = new LinkedList<LinkedList>();

Agora é só encapsular isso numa classe e criar métodos para facilitar a manipulação.

#4

PS: Eu não deveria estar postando isso aqui… mas acho que você vai gostar de ler esse tópico.

#5

cara ainda n entendi direito isso, ainda to começando a entender lista, vc poderia dar um exemplo?
eu consigo fazer uma class que usa a linkedlist, mas pra resolver o problema da matrizespersa n consigo :frowning:

#6

Você visitou o tópico que eu passei o link? Tem uma matriz esparsa implementada lá!

#7

eu vi, mas pelo q vi la ele tava usando map, hashmap, e eu ainda n vi isso, e eu n entedi essa parte que ele declara uma “linkedlist” dentro de outra, como se fosse —> LinkedList<Integer, LinkedList> lista;
sera que existe uma solução pra isso usando somente uma linkedlist?? @_@
vlw abraço

#8

Na verdade é assim:

List&lt;List&gt;&lt;Integer&gt;&gt; matrizEsparsa = new LinkedList&lt;LinkedList&gt;&lt;Integer&gt;&gt;();

Uma lista, onde cada elemento é uma outra lista, para um inteiro.

#9

[quote=ViniGodoy]Na verdade é assim:

List&lt;List&gt;&lt;Integer&gt;&gt; matrizEsparsa = new LinkedList&lt;LinkedList&gt;&lt;Integer&gt;&gt;();

Uma lista, onde cada elemento é uma outra lista, para um inteiro.[/quote]

Não seria mais eficiente uma única lista com o esquema de calculo de posição equivalente ?
Se a matriz é esparsa criar uma linked list só para conter o ultimo item parece pesado.

#10

Também dá. Acho que é melhor mesmo. Principalmente se for um mapa.

#11

eh akela função que transforma as posições de matriz em posição de vetor??
eu tentei mas se n me engano deu um erro com o addLast, eu vou tentar denovo
obrigado a todos! abraço

#12