• Sparse array

Sparse array application scenario:
    When array size is large and space utilization is low, sparse array should be used for storage
    
The following implementation of sparse array 0, row 0 and column are not used to store data. They are reserved for row size and other data. A sparse array is composed of multiple row lists and a row list is composed of multiple nodes

Python is implemented as follows:

# Node class
class ArrayEntry:
    def __init__(self, columnNumber=0, nextEntry=None, entry=0):
        # Number of columns
        self.columnNumber = columnNumber
        # Next node
        self.nextEntry = nextEntry
        # Data domain
        self.entry = entry


# Row linked list class
class ArrayRow:
    def __init__(self, rowNumber=0, rowSentinel=ArrayEntry(), nextRow=None):
        # Row of sparse array
        self.rowNumber = rowNumber
        # next row
        self.nextRow = nextRow
        # Current line's sentry, head pointer
        self.rowSentinel = rowSentinel

        self.columnSize = 0


# Sparse array class
class SparseArray:
    def __init__(self, sentinel=ArrayRow(), rowSize=0, columnSize=0):
        # Header pointer to sentinel row
        self.sentinel = sentinel
        # Rows of sparse array
        self.rowSize = rowSize
        # Columns of sparse array
        self.columnSize = columnSize

Define actions:

1. Find the previous line

# Find the previous row of rowNum and return to the previous row of rowNum
    def findRowBefore(self, rowNum) -> ArrayRow:
        array_row = self.sentinel
        while array_row.nextRow and array_row.nextRow.rowNumber < rowNum:
            array_row = array_row.nextRow
        return array_row

2. Find the precursor node of a node in a row

 # Find row's columnNum's previous column
    def findColumnBefore(self, row, columnNum) -> ArrayEntry or str:
        if row is None:
            return "row Can not be empty"
        row_sentinel = row.rowSentinel
        while row_sentinel.nextEntry and row_sentinel.nextEntry.columnNumber < columnNum:
            row_sentinel = row_sentinel.nextEntry
        return row_sentinel

3. Get value

    # Get (rowNum, columnNum) value
    def getEntry(self, rowNum, columnNum) -> int or str:
        row = self.findRowBefore(rowNum)
        if row.nextRow is None or row.nextRow.rowNumber > rowNum:
            return "No rows found." + str(rowNum)
        row_sentinel = self.findColumnBefore(row, columnNum)
        if row_sentinel.nextEntry is None or row_sentinel.nextEntry.columnNumber > columnNum:
            return "No columns found" + str(columnNum)
        return row_sentinel.nextEntry.entry

4. Set value

# Set entry. If no row is found, a new row will be created. If no column is found, a new column will be created
    def setEntry(self, rowNum, columnNum, entry) -> bool:
        # Find rows
        row = self.findRowBefore(rowNum)
        if row.nextRow is None or row.nextRow.rowNumber > rowNum:
            new_row = ArrayRow(row.rowNumber + 1)
            new_row.nextRow = row.nextRow
            row.nextRow = new_row
            row = row.nextRow

        # Find column
        row_sentinel = self.findColumnBefore(row, columnNum)
        if type(row_sentinel) == str:
            return False
        elif row_sentinel.nextEntry is None or row_sentinel.nextEntry.columnNumber > columnNum:
            new_column = ArrayEntry(columnNumber=row_sentinel.columnNumber + 1, entry=entry)
            new_column.nextEntry = row_sentinel.nextEntry
            row_sentinel.nextEntry = new_column
        else:
            row_sentinel.nextEntry.entry = entry
        return True

5. Delete node

def deleteEntry(self, rowNum, columnNum):
    He found the line.
    row = self.findRowBefore(rowNum)
    if row.nextRow is None or row.nextRow.rowNumber > rowNum:
        return False

    Find the list
    row_sentinel = self.findColumnBefore(row.nextRow, columnNum)
    if type(row_sentinel) == str:
        return False
    elif row_sentinel.nextEntry is None or row_sentinel.nextEntry.columnNumber > columnNum:
        return False
    else:
        delete = row_sentinel.nextEntry
        after_delete = row_sentinel.nextEntry.nextEntry
        row_sentinel.nextEntry = after_delete
        #If there is no column in the row after the column is deleted, delete the row
        if after_delete is None and row_sentinel.columnNumber == 0:
            row.nextRow = None
        del delete
        gc.collect()
        return True

6. Matrix addition

Sparse matrix addition (pseudo code):
    //Traversing two matrix rows,
    while arr1 and arr2:
        if arr1.rowNum>arr2.rowNum : add arr2 to result,arr2=arr2.nextRow
        elif arr1.rowNum<arr2.rowNum : add arr1 to result,arr1 = arr1.nextRow
        else add arr1[rowNum] + arr2[rowNum] to result,arr1 = arr1.nextRow,arr2=arr2.nextRow
    
    add arr1 remaining to result
    add arr2 remaining to result

7. Matrix multiplication

Sparse matrix multiplication:
    For and matrix arr1*arr2, each column of arr2 is traversed by and, and the column cannot be iterated,
    We can transpose arr2. A row of matrix arr2 after transposing is the column before transposing,
    If the default value of entry is zero, similar to addition, multiplication can be calculated as follows:
        Traversal of arr1, transposition of arr2,
            If for Arr1. rowNum! = arr2 transpose. rowNum, the point (arr1.rowNum, arr2 transpose. rowNum) is 0
            If for arr1.rowNum == arr2 transpose. rowNum, then the point (arr1.rowNum, arr2 transpose. rowNum) is the sum of the product of the corresponding terms

• Triangular matrix

Application scenario: in the face of a large array, and when the array has good symmetry, you can use triangular matrix, such as the adjacency matrix of undirected graph, etc.
Features: one dimensional matrix represents two-dimensional matrix, [I, J] = ((i-1) * * 2 + i-1) / 2 + J (the table below the array starts from 1), [I, J] = = (I * * 2 + I) / 2 + J (the table below the array starts from 0)

Python implementation:

import time

from pymysql import Date

"""
    //Application scenario: array symmetry
"""


class TriangleArray:
    def __init__(self):
        self.data = []
        self.size = 0

    def get(self, row, column):
        index = int((row ** 2 + row) / 2 + column)
        if index <= self.size - 1:
            return self.data[index]
        else:
            return None

    def append_(self, value):
        self.data.append(value)
        self.size += 1

    def set(self, row, column, value):
        index = int((row ** 2 + row) / 2 + column)
        if index <= self.size - 1:
            self.data[index] = value
            return True
        else:
            return False


if __name__ == "__main__":
    tri = TriangleArray()
    tri.append_(1)
    tri.append_("rlyslata")
    tri.append_("CSDN")
    tri.append_("New pneumonia coronavirus")
    tri.append_(str(time.localtime()))

    print(tri.get(0, 0))
    print(tri.get(1, 0))
    print(tri.get(1, 1))
    print(tri.get(2, 0))
    print(tri.get(2, 1))

PS: Code clone address: git@github.com:Rlyslata/DataStauct-And-Algorithm.git

Path: About algorithm of linked list / SparseArray about algorithm of linked list / TriangleArray