C

uber · 07-08-2009, 09:12 AM

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.

**Salem** · 07-08-2009, 10:16 AM

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.

slingerland3g · 07-08-2009, 01:30 PM

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);
    }

07-08-2009, 10:16 AM	#2
Salem and the hat of vanishing Join Date: Aug 2001 Location: The edge of the known universe Posts: 21,214	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. __________________ If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut. Up to 8Mb PlusNet broadband from only £5.99 a month!
Salem is offline

07-08-2009, 01:30 PM	#3
slingerland3g Registered User Join Date: Jan 2008 Location: Seattle Posts: 476	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); }
slingerland3g is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Istream::Release access violation? [C++]	A10	Windows Programming	10	01-13-2009 10:56 PM
Access violation... can't figure it out...	Raigne	C++ Programming	7	10-11-2007 10:52 AM
FtpFileFind access violation with MS VC++ 6.0	earth_angel	C++ Programming	3	09-22-2005 07:02 PM
Strange access violation	jimmy_anttila	Windows Programming	2	04-11-2004 03:10 AM
0xC0000005: Access Violation	Strider	Windows Programming	3	11-07-2001 02:46 PM