Code:
// SparseMatrix.cpp
#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
typedef int Elem;
typedef struct cell Cell;
typedef Cell * Matrix;
struct cell {
int row;
int col;
Cell * right;
Cell * down;
Elem value;
};
Matrix newSparseMatrix();
void freeSparseMatrix( Matrix m );
void setElem( Matrix m, int row, int col, Elem value );
Elem getElem( Matrix m, int row, int col );
void showByRows( Matrix m );
void showByCols( Matrix m );
Matrix readSparseMatrix();
Matrix transpose( Matrix m );
Matrix addMatrix( Matrix m, Matrix other );
bool rowExists(Matrix m, int nRow);
bool colExists(Matrix m, int nCol);
Matrix findRow(Matrix m,int nRow, int nCol);
Matrix findCol(Matrix m, int nRow, int nCol);
void deleteCell(Matrix m, int nRow, int nCol);
void createNewCell(Matrix m,int nRow, int nCol, Elem Value);
void main()
{
Matrix A;
A = newSparseMatrix();
A = readSparseMatrix();
system("pause");
}
Matrix newSparseMatrix()
{
Matrix M = (Matrix)calloc(1,sizeof(Cell));
//printf("%d\n",M->col);
return M;
}//Matrix newSparseMatrix()
void freeSparseMatrix(Matrix m)
{
Cell *NextValue;
while(m->down)
{
m = m->right;
while(m->right)
{
NextValue = m->right;
free(m);
m = NextValue;
}
m = m->down;
}
free(m);
}//free matrix
void setElem(Matrix m, int nRow, int nCol, Elem Value)
{
if(Value == 0)
{
deleteCell(m,nRow,nCol);
}
else
{
createNewCell(m,nRow,nCol,Value);
}
}
Elem getElem(Matrix m, int nRow, int nCol)
{
Cell *Value;
if(rowExists(m,nRow) && colExists(m,nCol))
{
Value = findRow(m,nRow,nCol);
Value = Value->right;
return Value->value;
}
return 0;
}//get elem
void showByRows(Matrix m)
{
Cell *CurrRow = m;
Cell *NextRow = m;
Cell *CurrCol = m;
Cell *NextCol = m;
while(CurrRow)
{
while(CurrCol)
{
printf("(%d,%d) = %d\n",CurrCol->row,CurrCol->col,CurrCol->value);
NextCol = CurrCol->right;
CurrCol = NextCol;
}
NextRow = CurrRow->down;
CurrRow = NextRow;
}
}
void showByCols(Matrix m)
{
Cell *CurrRow = m;
Cell *NextRow = m;
Cell *CurrCol = m;
Cell *NextCol = m;
while(CurrCol)
{
while(CurrRow)
{
printf("(%d,%d) = %d\n",CurrRow->row,CurrRow->col,CurrRow->value);
NextRow = CurrRow->down;
CurrRow = NextRow;
}
NextCol = CurrCol->right;
CurrCol = NextCol;
}
}//show by cols
Matrix readSparseMatrix()
{
Matrix M = newSparseMatrix();
Cell *NewCol = newSparseMatrix();
Cell *NewRow = newSparseMatrix();
int nRow;
int nCol;
int nValue;
printf("Enter the row number:\n");
scanf("%d",&nRow);
printf("Enter the col number:\n");
scanf("%d",&nCol);
printf("Enter the value of the cell:\n");
scanf("%d",&nValue);
if(nValue!=0&&nRow!=0&&nCol!=0)
{
NewCol->col = nCol;
NewCol->row = 0;
M->right = NewCol;
NewCol->right = NULL;
NewCol->down = NULL;
NewRow->row = nRow;
NewRow->col = 0;
M->down = NewRow;
NewRow->right = NULL;
NewRow->down = NULL;
}
while(nRow>0 && nCol>0)
{
setElem(M,nRow,nCol,nValue);
printf("Enter the row number:\n",nRow);
scanf("%d",&nRow);
printf("Enter the col number:\n",nCol);
scanf("%d",&nCol);
printf("Enter the value of the cell:\n",nValue);
scanf("%d",&nValue);
}
return M;
}//read sparse matrix
/*
Matrix transpose( Matrix m ) {
}//matrix transpose
Matrix addMatrix( Matrix m, Matrix other ) {
}//add matrix
*/
bool rowExists(Matrix m, int nRow)
{
Cell *NextRow;
Cell *CurrRow;
bool bRowFound = false;
CurrRow = m;
NextRow = m->down;
while(NextRow&&!bRowFound)
{
if(CurrRow->row == nRow)
{
return true;
}
NextRow = CurrRow->down;
CurrRow = NextRow;
}
return false;
}
bool colExists(Matrix m, int nCol)
{
Cell *NextCol;
Cell *CurrCol;
bool bColFound = false;
CurrCol = m;
NextCol = m->right;
while(NextCol&&!bColFound)
{
if(CurrCol->col == nCol)
{
return true;
}
NextCol = CurrCol->right;
CurrCol = NextCol;
}
return false;
}
Matrix findRow(Matrix m,int nRow, int nCol)
{
Cell *CurrRow = m;
Cell *NextRow = m;
Cell *CurrCol;
Cell *NextCol;
while(CurrRow->row != nRow)
{
NextRow = CurrRow->down;
CurrRow = NextRow;
}
CurrCol = CurrRow;
NextCol = CurrCol->right;
while(NextCol->col != nCol)
{
NextCol = CurrCol->right;
CurrCol = NextCol;
}
return CurrCol;
}
Matrix findCol(Matrix m, int nRow, int nCol)
{
Cell *CurrCol = m;
Cell *NextCol = m;
Cell *CurrRow;
Cell *NextRow;
while(CurrCol->col != nCol)
{
NextCol = CurrCol->right;
CurrCol = NextCol;
}
CurrRow = CurrCol;
while(NextRow->row != nRow)
{
NextRow = CurrRow->right;
CurrRow = NextRow;
}
return CurrRow;
}
void deleteCell(Matrix m, int nRow, int nCol)
{
Cell *LeftCell;
Cell *AboveCell;
Cell *CurrCell;
Cell *AboveIndex;
Cell *LeftIndex;
if(rowExists(m,nRow))
{
LeftCell = findRow(m,nRow,nCol);
AboveCell = findCol(m,nRow,nCol);
CurrCell = LeftCell->right;
LeftCell->right = CurrCell->right;
AboveCell->down = CurrCell->down;
free(CurrCell);
if(LeftCell->row == 0 && LeftCell->right == NULL)
{
AboveIndex = findCol(m,LeftCell->row,LeftCell->col);
AboveIndex->down = LeftCell->down;
free(LeftCell);
}
if(AboveCell->col == 0 && AboveCell->down == NULL)
{
LeftIndex = findRow(m,AboveCell->row,AboveCell->col);
LeftIndex->right = AboveCell->right;
free(AboveCell);
}
}
}
void createNewCell(Matrix m,int nRow, int nCol, Elem Value)
{
Cell *NewCell = newSparseMatrix();
Cell *NewRow = newSparseMatrix();
Cell *NewCol = newSparseMatrix();
Cell *Left = m;
Cell *Above = m;
NewCell->col = nCol;
NewCell->row = nRow;
NewCell->value = Value;
if(rowExists(m,nRow))
{
Left = findRow(m,nRow,nCol);
NewCell->right = Left->right;
Left->right = NewCell;
}
if(!colExists(m,nCol))
{
NewCol->col = nCol;
Left = findRow(m,0,nCol);
NewCol = Left->right;
Left->right = NewCol;
NewCol->right = NewCell;
}
if(colExists(m,nCol))
{
Above = findCol(m,nRow,nCol);
NewCell->down = Above->down;
Above->down = NewCell;
}
if(!rowExists(m,nRow))
{
NewRow->row = nRow;
Above = findCol(m,nRow,0);
NewRow = Above->down;
Above->down = NewRow;
NewRow->down = NewCell;
}
}