¿Qué es una matriz dispersa?
Hay muchos ceros en la matriz, de los cuales los elementos distintos de cero solo representan una pequeña parte, y la mayoría de ellos son ceros. se llama matriz dispersa.
El concepto de matriz dispersa no está estrictamente definido y el número de 0 / porcentaje del número total de elementos de la matriz no está estrictamente definido. Es un concepto basado en el sentimiento.
En la versión estricta de la definición de la estructura de datos, cero aquí puede ser la constante c.
Si c es cero o no es una diferencia conceptual.
Representación triplete
La primera línea (subíndice 0): generalmente no almacena ningún elemento
La primera representa el número de elementos distintos de cero, el el segundo representa el número de filas y el tercero representa el número de columnas
Los elementos de la matriz se almacenan a partir del subíndice 1 y generalmente se almacenan con prioridad de fila.
Por supuesto, puede usar la prioridad de columna o almacenarla en cualquier ubicación. Simplemente almacene todos los elementos que contiene.
Notación de lista de adyacencia
Define una matriz unidimensional, el subíndice de la matriz corresponde al índice de fila de la matriz a almacenar
Los elementos de la matriz son punteros. Cada puntero apunta a una lista vinculada y los nodos de la lista vinculada almacenan la información del elemento distinto de cero en la matriz.
La primera información es el valor del elemento distinto de cero
La segunda información es el índice de la columna del elemento distinto de cero
La fila. índice de cada lista vinculada Guarda la información de la etiqueta de fila de todos los elementos en esta lista vinculada.
Los nodos en cada lista vinculada almacenan el valor y la información de la etiqueta de la columna del elemento.
Cada lista entrecruzada tiene un nodo principal, que tiene cinco campos.
La primera fila: el primer campo: el número de filas, el segundo campo: el número de columnas. tercer campo: número de elementos distintos de cero
Segunda línea: dos campos conducen a dos punteros, apuntando a dos matrices
Cuarto campo: matriz de columnas, el quinto campo: matriz de filas.
Las dos matrices almacenan algunos punteros que apuntan a elementos distintos de cero en la tabla.
Solicite un nodo para cada elemento distinto de cero en la tabla
El tipo de nodo del elemento de la tabla es el mismo que el tipo de nodo principal de la tabla, pero la información se guarda es diferente.
Nodo de elemento
El primer componente almacena: número de fila
El segundo componente almacena: número de columna
Los tres componentes almacenan: elemento valores
Los componentes cuarto y quinto almacenan: punteros
La construcción de una lista cruzada es similar a una matriz bidimensional.
Simplemente asigna espacio de almacenamiento únicamente a elementos distintos de cero.
Los punteros entre nodos en la dirección de la fila se derivan del quinto campo del nodo.
Los punteros entre nodos en la dirección de la columna se derivan del cuarto campo del nodo.