Matriz Esparsa

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

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)

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

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.

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

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

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

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

Na verdade é assim:

List<List><Integer>> matrizEsparsa = new LinkedList<LinkedList><Integer>>();

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

ViniGodoy:

Na verdade é assim:

List<List><Integer>> matrizEsparsa = new LinkedList<LinkedList><Integer>>();

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

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.

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

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