Requisito previo: array dispersa y sus representaciones Conjunto 1 (Uso de arrays y listas enlazadas)
En esta publicación se analizan otros dos métodos de representación de array dispersa.
- Lista de listas
- Diccionario
Lista de listas (LIL)
Una de las posibles representaciones de la array dispersa es la Lista de listas (LIL). Donde se usa una lista para representar las filas y cada fila contiene la lista de triples: índice de columna, valor (elemento distinto de cero) y campo de dirección, para elementos distintos de cero. Para obtener el mejor rendimiento, ambas listas deben almacenarse en orden de claves ascendentes.
Implementación:
C++
// C++ program for Sparse Matrix Representation
// using List Of Lists
#include<bits/stdc++.h>
using namespace std;
#define R 4
#define C 5
// Node to represent row - list
struct row_list
{
int row_number;
struct row_list *link_down;
struct value_list *link_right;
};
// Node to represent triples
struct value_list
{
int column_index;
int value;
struct value_list *next;
};
// Function to create node for non - zero elements
void create_value_node(int data, int j, struct row_list **z)
{
struct value_list *temp, *d;
// Create new node dynamically
temp = new value_list();
temp->column_index = j+1;
temp->value = data;
temp->next = NULL;
// Connect with row list
if ((*z)->link_right==NULL)
(*z)->link_right = temp;
else
{
// d points to data list node
d = (*z)->link_right;
while(d->next != NULL)
d = d->next;
d->next = temp;
}
}
// Function to create row list
void create_row_list(struct row_list **start, int row,
int column, int Sparse_Matrix[R][C])
{
// For every row, node is created
for (int i = 0; i < row; i++)
{
struct row_list *z, *r;
// Create new node dynamically
z = new row_list();
z->row_number = i+1;
z->link_down = NULL;
z->link_right = NULL;
if (i==0)
*start = z;
else
{
r = *start;
while (r->link_down != NULL)
r = r->link_down;
r->link_down = z;
}
// Firstiy node for row is created,
// and then traversing is done in that row
for (int j = 0; j < 5; j++)
{
if (Sparse_Matrix[i][j] != 0)
{
create_value_node(Sparse_Matrix[i][j], j, &z);
}
}
}
}
//Function display data of LIL
void print_LIL(struct row_list *start)
{
struct row_list *r;
struct value_list *z;
r = start;
// Traversing row list
while (r != NULL)
{
if (r->link_right != NULL)
{
cout<<"row="<<r->row_number<<endl;
z = r->link_right;
// Traversing data list
while (z != NULL)
{
cout<<"column="<<z->column_index<<" value="<<z->value<<endl;
z = z->next;
}
}
r = r->link_down;
}
}
//Driver of the program
int main()
{
// Assume 4x5 sparse matrix
int Sparse_Matrix[R][C] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};
// Start with the empty List of lists
struct row_list* start = NULL;
//Function creating List of Lists
create_row_list(&start, R, C, Sparse_Matrix);
// Display data of List of lists
print_LIL(start);
return 0;
}
// This code is contributed by rutvik_56.
C
// C program for Sparse Matrix Representation
// using List Of Lists
#include<stdio.h>
#include<stdlib.h>
#define R 4
#define C 5
// Node to represent row - list
struct row_list
{
int row_number;
struct row_list *link_down;
struct value_list *link_right;
};
// Node to represent triples
struct value_list
{
int column_index;
int value;
struct value_list *next;
};
// Function to create node for non - zero elements
void create_value_node(int data, int j, struct row_list **z)
{
struct value_list *temp, *d;
// Create new node dynamically
temp = (struct value_list*)malloc(sizeof(struct value_list));
temp->column_index = j+1;
temp->value = data;
temp->next = NULL;
// Connect with row list
if ((*z)->link_right==NULL)
(*z)->link_right = temp;
else
{
// d points to data list node
d = (*z)->link_right;
while(d->next != NULL)
d = d->next;
d->next = temp;
}
}
// Function to create row list
void create_row_list(struct row_list **start, int row,
int column, int Sparse_Matrix[R][C])
{
// For every row, node is created
for (int i = 0; i < row; i++)
{
struct row_list *z, *r;
// Create new node dynamically
z = (struct row_list*)malloc(sizeof(struct row_list));
z->row_number = i+1;
z->link_down = NULL;
z->link_right = NULL;
if (i==0)
*start = z;
else
{
r = *start;
while (r->link_down != NULL)
r = r->link_down;
r->link_down = z;
}
// Firstiy node for row is created,
// and then traversing is done in that row
for (int j = 0; j < 5; j++)
{
if (Sparse_Matrix[i][j] != 0)
{
create_value_node(Sparse_Matrix[i][j], j, &z);
}
}
}
}
//Function display data of LIL
void print_LIL(struct row_list *start)
{
struct row_list *r;
struct value_list *z;
r = start;
// Traversing row list
while (r != NULL)
{
if (r->link_right != NULL)
{
printf("row=%d \n", r->row_number);
z = r->link_right;
// Traversing data list
while (z != NULL)
{
printf("column=%d value=%d \n",
z->column_index, z->value);
z = z->next;
}
}
r = r->link_down;
}
}
//Driver of the program
int main()
{
// Assume 4x5 sparse matrix
int Sparse_Matrix[R][C] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};
// Start with the empty List of lists
struct row_list* start = NULL;
//Function creating List of Lists
create_row_list(&start, R, C, Sparse_Matrix);
// Display data of List of lists
print_LIL(start);
return 0;
}
Producción
row=1 column=3 value=3 column=5 value=4 row=2 column=3 value=5 column=4 value=7 row=4 column=2 value=2 column=3 value=6
Diccionario de llaves
Una representación alternativa de array dispersa es Diccionario. Para el campo clave del diccionario, se utiliza un par de índices de fila y columna que se asignan con el elemento distinto de cero de la array. Este método ahorra espacio pero el acceso secuencial de elementos es costoso.
En C++, el diccionario se define como una clase de mapa de STL (Biblioteca de plantillas estándar). Para saber más sobre el mapa, haga clic en el siguiente enlace:
Conceptos básicos del mapa
Implementación:
CPP
// C++ program for Sparse Matrix Representation
// using Dictionary
#include<bits/stdc++.h>
using namespace std;
#define R 4
#define C 5
// Driver of the program
int main()
{
// Assume 4x5 sparse matrix
int Sparse_Matrix[R][C] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};
/* Declaration of map where first field(pair of
row and column) represent key and second
field represent value */
map< pair<int,int>, int > new_matrix;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if (Sparse_Matrix[i][j] != 0)
new_matrix[make_pair(i+1,j+1)] =
Sparse_Matrix[i][j] ;
int c = 0;
// Iteration over map
for (auto i = new_matrix.begin(); i != new_matrix.end(); i++ )
{
if (c != i->first.first)
{
cout << "row = " << i->first.first << endl ;
c = i->first.first;
}
cout << "column = " << i->first.second <<" ";
cout << "value = " << i->second << endl;
}
return 0;
}
Python3
# Python program for Sparse Matrix Representation
# using Dictionary
R = 4
C = 5
# Driver of the program
# Assume 4x5 sparse matrix
Sparse_Matrix=[[0 , 0 , 3 , 0 , 4] ,
[0 , 0 , 5 , 7 , 0] ,
[0 , 0 , 0 , 0 , 0] ,
[0 , 2 , 6 , 0 , 0]]
''' Declaration of map where first field(pair of
row and column) represent key and second
field represent value '''
new_matrix = {}
for i in range(R):
for j in range(C):
if (Sparse_Matrix[i][j] != 0):
new_matrix[(i + 1, j + 1)] = Sparse_Matrix[i][j]
c = 0
# Iteration over map
for i in new_matrix:
if (c != i[0]):
print("row =", i[0])
c = i[0]
print("column =", i[1], end = " ")
print("value =", new_matrix[i])
# This code is contributed by Shubham Singh
Producción
row = 1 column = 3 value = 3 column = 5 value = 4 row = 2 column = 3 value = 5 column = 4 value = 7 row = 4 column = 2 value = 2 column = 3 value = 6
Este artículo es una contribución de Akash Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA