-
C - access violation
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;
}
}
This is my code where I try to implement a sparse matrix.
When I enter some random values and the function readSparseMatrix() reads them I get a Memory access violation error pointing to this line: while(NextCol->col != nCol)
in the function findRow.
findRow and findCol are used to find the cell that points from left and above respectively at the cell needed.
I have figured out that when the matrix is empty and I try to create a cell, there is nothing that can point at this cell. So I need to create cells in row number 0 and column number 0 (the cells in those indexes have no values, only pointers right and down).
So I have added this piece of code to the function readSparseMatrix():
Code:
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;
}
This is supposed to create a row cell and column cell, that the cell in 0,0 (empty matrix) will point at them. But I still get the same error in the same location.
Please disregard all the non-standard things I did in this code, I'll deal with that later.
I really need to get this to work.
Thanks in advance.
-
Code:
void main()
{
Matrix A;
A = newSparseMatrix();
You don't use the first result anyway, it just leaks memory.
Also, main returns int, not void.
> Matrix M = newSparseMatrix();
> Cell *NewCol = newSparseMatrix();
> Cell *NewRow = newSparseMatrix();
Why the mixed types?
Do you have a working diagram of what your sparse matrix is supposed to look like?
Because your free() function paints a VERY odd picture of what it looks like. Using just one variable for traversing both right AND down just seems wrong to me.
-
In looking at this, are you sure you are calling setElem() correctly. You see to be calling this prior to actually assigning your values. So you are now deleting them since their values are 0.
Code:
while(nRow>0 && nCol>0)
{
setElem(M,nRow,nCol,nValue); /*Is this your intent!!! */
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);
}