1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Seg fault in Sparse Matrix Code (due in 2.5 hours)

  1. Mar 2, 2009 #1
    i just ran it using a debugger and this is what it had:

    Code (Text):

    #0  0x0804939e in SparseNode::getColID (this=0x0) at sparsematrix.h:130
    #1  0x08048a2d in SparseMatrix::insertElement (this=0xbfe5ef10, row=1, col=2, elem=2) at sparsematrix.cpp:72
    #2  0x080491f3 in main () at sparsematrix.cpp:378
     
    these are the files I have:

    sparsematrix.h
    Code (Text):

    #ifndef SPARSEMATRIX_H
    #define SPARSEMATRIX_H


    class SparseNode;


    class SparseMatrix
    {
        private:
            int numRows;  // number of rows
            int numCols;  // number of columns
            int numElements;  // number of elements stored in the matrix
            SparseNode** rows;  // pointer to the array of row-list heads
            SparseNode** cols;  // pointer to the array of column-list heads

        public:
            // get/set functions for the private variables
            int getNumRows() { return numRows; };
            int getNumCols() { return numCols; };
            int getNumElements() { return numElements; };
            SparseNode* getRowPtr(int rowID)  { return rows[rowID]; };
            SparseNode* getColPtr(int colID)  { return cols[colID]; };
            SparseNode* setRowPtr(int rowID, SparseNode* node)  { rows[rowID] = node; };
            SparseNode* setColPtr(int colID, SparseNode* node)  { cols[colID] = node; };

            // ============= FUNCTIONS TO BE IMPLEMENTED =============
            // constructor and destructor

            /* Function: Creates a Sparse Matrix by allocating memory for rows/columns
               Return Value: none
               Parameters: number of rows (int nr),  number of cols (int nc)
               Pre-conditions: No matrix
               Post-conditions: Each row/column is the head node for a single linked list
            */
            SparseMatrix(int nr, int nc);

            /* Function: Deletes all linked lists and memory allocated for matrix
               Return Value: none
               Parameters: none
               Pre-conditions: No bin
               Post-conditions: Memory for sparse matrix is deleted
            */
            ~SparseMatrix();

            // functions for inserting/removing/accessing elements

            /* Function: Inserts a new node in linked list
               Return Value: 1 if succesful, 0 if not
               Parameters: row/column index(int row, int col), data(float elem)
               Pre-conditions: A sparse matrix with existing nodes
               Post-conditions: New node with data inserted at specified indices
            */
            int insertElement(int row, int col, float elem);

            /* Function: Removes a node in linked list
               Return Value: 1 if succesful, 0 if not
               Parameters: row/column index(int row, int col)
               Pre-conditions: A sparse matrix with existing nodes
               Post-conditions: Previous node will point to node after deleted node
            */
            int removeElement(int row, int col);

            /* Function: Gets data from a node
               Return Value: 1 if succesful, 0 if not
               Parameters: row/column index(int row, col), data array(float* pelem)
               Pre-conditions: No data
               Post-conditions: Data from specified node stored in array
            */
            int getElement(int row, int col, float* pelem);

            // some extra operations on the sparse matrix

            /* Function: Computes average of data stored in nodes along row
               Return Value: number of elements in row
               Parameters: row index (int row),  data array (float* avg)
               Pre-conditions: none
               Post-conditions: avg points to row average
            */
            int computeRowAverage(int row, float* avg);

            /* Function: Computes average of data stored in nodes along column
               Return Value: number of elements in column
               Parameters: col index (int row),  data array (float* avg)
               Pre-conditions: none
               Post-conditions: avg points to column average
            */
            int computeColAverage(int col, float* avg);

            /* Function: Finds indices of common nonempty columns between two rows
               Return Value: none
               Parameters: 2 row indices (int row1, row2), array for storing
                           indices (int** intersectCols), and # of common columns
                           (int* numIntersect)
               Pre-conditions: No bin
               Post-conditions: column indices stored in array, counts # of columns
            */
            void intersectTwoRows(int row1, int row2, int** intersectCols, int* numIntersect);

            /* Function: Finds indices of common nonempty rows between two columns
               Return Value: none
               Parameters: 2 column indices (int col1, col2), array for storing
                           indices (int** intersectRows), and # of common rows
                           (int* numIntersect)
               Pre-conditions: No bin
               Post-conditions: row indices stored in array, counts # of rows
            */
            void intersectTwoCols(int col1, int col2, int** intersectRows, int* numIntersect);
            // ========================================================
    };


    class SparseNode  {
        private:
            float data;  // data stored in the node
            int rowID;  // row number of the node in a sparse matrix
            int colID;  // column number of the node in a sparse matrix
            SparseNode* right;  // pointer to the right node in a sparse matrix
            SparseNode* down;  // pointer to the node below in a sparse matrix

        public:
            // get/set functions for the private variables
            int getRowID() { return rowID; };
            int getColID() { return colID; };
            float getData() { return data; };
            SparseNode* getRight() { return right; };
            SparseNode* getDown() { return down; };
            float* getDataPtr()  { return &data; };

            void setRowID(int rowID) { this->rowID = rowID; };
            void setColID(int colID) { this->colID = colID; };                 //LINE 130!
            void setData(float data) { this->data = data; };
            void setRight(SparseNode* right) { this->right = right; };
            void setDown(SparseNode* down) { this->down = down; };
    };
     
    sparsematrix.cpp
    Code (Text):

    /* sparsematrix.cpp
     *
     * Contains SparseMatrix class constructor, destructor, functions to insert,
     * remove, and get an element, functions to compute the average of a row or
     * column, and functions that find the common intersecting rows between two
     * columns and vice versa.
     */

    #include <iostream>
    #include "sparsematrix.h"

    SparseMatrix::SparseMatrix(int nr, int nc)
    {
        numRows = nr;
        numCols = nc;
        numElements = 0;

        //allocate memory for each row
        //set each row (head node) to NULL
        rows = new SparseNode* [nr];
        for(int i=0; i<nr; i++)
        {
            rows[i] = NULL;
        }

        //allocate memory for each col
        //set each col (head node) to NULL
        cols = new SparseNode* [nc];
        for(int i=0; i<nc; i++)
        {
            cols[i] = NULL;
        }

    }

    SparseMatrix::~SparseMatrix()
    {
        int numRows = getNumRows();
        int numCols = getNumCols();
        SparseNode* tempPtr;
        SparseNode* currentNode;

        for(int i=0; i<numRows; i++)
        {

            currentNode = getRowPtr(i);
            while(currentNode != NULL)
            {
                //deletes currentNode while using tempPtr to keep track of position
                tempPtr = currentNode;
                currentNode = currentNode->getRight();
                delete[] tempPtr;
                tempPtr = currentNode;
            }
        }
    }

    int SparseMatrix::insertElement(int row, int col, float elem)
    {
        int rowNum = row;
        int colNum = col;

        SparseNode newNode;
        newNode.setRowID(rowNum);
        newNode.setColID(colNum);
        newNode.setData(elem);

        if(getRowPtr(rowNum) != NULL)
        {
            SparseNode* tempPtr = getRowPtr(rowNum);
            //traverse tempPtr along row until right before the specified index
            while(tempPtr->getRight()->getColID() < colNum)                        //LINE 72
            {
                tempPtr = tempPtr->getRight();
            }
            //inserts newNode between tempPtr and the next element
            newNode.setRight(tempPtr->getRight());
            tempPtr->setRight(&newNode);

            return 1;
        }
        //else if the specified row is empty and within bounds
        else if(rowNum < getNumRows())
        {
            setRowPtr(rowNum, &newNode);
            newNode.setRight(NULL);
            return 1;
        }
        else //else invalid row
            return 0;

        if(getColPtr(colNum) != NULL)
        {
            SparseNode* tempPtr = getColPtr(colNum);
            //traverse tempPtr along column until right before the specified index
            while(tempPtr->getDown()->getColID() < colNum)
            {
                tempPtr = tempPtr->getDown();
            }
            //inserts newNode between tempPtr and the next element
            newNode.setDown(tempPtr->getDown());
            tempPtr->setDown(&newNode);

            return 1;
        }
        //else if the specified column is empty and within bounds
        else if(colNum < getNumCols())
        {
            setColPtr(colNum, &newNode);
            newNode.setDown(NULL);

            return 1;
        }
        else //else invalid column
            return 0;

    }

    int SparseMatrix::removeElement(int row, int col)
    {
        int rowNum = row;
        int colNum = col;

        if(getRowPtr(rowNum) != NULL)
        {
            SparseNode* tempPtr = getRowPtr(rowNum);
            //traverse tempPtr along row
            while(tempPtr->getRight()->getColID() < colNum)
            {
                tempPtr = tempPtr->getRight();
            }
            if(tempPtr->getRight()->getColID() == colNum)
            {
                // valid indices, tempPtr points to next next node
                tempPtr->setRight(tempPtr->getRight()->getRight());
                delete[] tempPtr->getRight(); //deallocate memory

                return 1;
            }
            else // invalid indices
                return 0;
        }
        else // row is empty
            return 0;

        if(getColPtr(colNum) != NULL)
        {
            SparseNode* tempPtr = getColPtr(colNum);
            //traverse tempPtr along column
            while(tempPtr->getDown()->getRowID() < rowNum)
            {
                tempPtr = tempPtr->getDown();
            }
            if(tempPtr->getDown()->getRowID() == rowNum)
            {
                // valid indices, tempPtr points to next next node
                tempPtr->setDown(tempPtr->getDown()->getDown());
                delete[] tempPtr->getDown(); //deallocate memory

                return 1;
            }
            else // invalid indices
                return 0;
        }
        else // column is empty
            return 0;

    }

    int SparseMatrix::getElement(int row, int col, float* pelem)
    {

        int rowNum = row;
        int colNum = col;

        if(getRowPtr(rowNum) != NULL)
        {
            SparseNode* tempPtr = getRowPtr(rowNum);
            while(tempPtr->getColID() < colNum)
            {
                tempPtr = tempPtr->getRight();
            }
            if(tempPtr->getColID() == colNum)
            {
                //valid indices, get data
                pelem = tempPtr->getDataPtr();
                return 1;
            }
            else //invalid indices
                return 0;
        }
        else //empty row
                return 0;

    }

    int SparseMatrix::computeRowAverage(int row, float* avg)
    {
        float sum = 0;
        int count = 0; // number of elements along row
        float average = 0;
        int rowNum = row;

        SparseNode* tempPtr = getRowPtr(rowNum);

        while(tempPtr != NULL)
        {
            sum += tempPtr->getData(); //tempPtr traverse along row
            count++;
            tempPtr = tempPtr->getRight();
        }
        average = sum/count;
        *avg = average;

        return count;

    }

    int SparseMatrix::computeColAverage(int col, float* avg)
    {
        float sum = 0;
        int count = 0; // number of elements along column
        float average = 0;
        int colNum = col;

        SparseNode* tempPtr = getColPtr(colNum);

        while(tempPtr != NULL)
        {
            sum += tempPtr->getData(); //tempPtr traverse along column
            count++;
            tempPtr = tempPtr->getDown();
        }
        average = sum/count;
        *avg = average;

        return count;

    }

    void SparseMatrix::intersectTwoRows(int row1, int row2, int** intersectCols, int* numIntersect)
    {
        int rowNum1 = row1;
        int rowNum2 = row2;
        SparseNode* ptrRow1; //pointer to row 1
        SparseNode* ptrRow2; //pointer to row 2
        int colCount = 0; //number of common columns between row 1 and row 2
        int* array = NULL;
        int index = 0;

        //if either row is empty, # of common cols = zero, intersectCols = NULL
        if((ptrRow1 = getRowPtr(rowNum1)) == NULL
           || (ptrRow2 = getRowPtr(rowNum2)) == NULL)
        {
            intersectCols = NULL;
            *numIntersect = 0;
            return;
        }

        //rows are non-empty
        while((ptrRow1 = getRowPtr(rowNum1)) != NULL
               && (ptrRow2 = getRowPtr(rowNum2)) != NULL)
        {
            if(ptrRow1->getColID() == ptrRow2->getColID())
            {
                index = ptrRow1->getColID();
                colCount++;
                int* tempArray = NULL;
                //newArray[] is one larger than array[]
                int* newArray = new int [sizeof(array)+1];
                for(int i=0; i<sizeof(array); i++)
                {
                    //copy array[] into newArray[]
                    newArray[i] = array[i];
                }
                newArray[sizeof(array)] = index;

                //set array[] to point to newArray[], and deallocate the old one
                tempArray = array;
                array = newArray;
                delete[] tempArray;
            }
            //keep traversing pointers until both are at same column
            else if(ptrRow1->getColID() > ptrRow2->getColID())
            {
                ptrRow2 = ptrRow2->getRight();
            }
            //keep traversing pointers until both are at same column
            else
            {
                ptrRow1 = ptrRow1->getRight();
            }
        }

        *intersectCols = new int [sizeof(array)];
        for(int i=0; i<sizeof(array); i++)
        {
            //store common column indices of both rows in *intersectCols array
            *intersectCols[i] = array[i];
        }
        *numIntersect = colCount; //number of common columns

    }

    void SparseMatrix::intersectTwoCols(int col1, int col2, int** intersectRows, int* numIntersect)
    {
        int colNum1 = col1;
        int colNum2 = col2;
        SparseNode* ptrCol1; //pointer to column 1
        SparseNode* ptrCol2; //pointer to column 1
        int rowCount = 0; //number of common columns between row 1 and row 2
        int* array = NULL;
        int index = 0;

        //if either column is empty, # of common rows = zero, intersectRows = NULL
        if((ptrCol1 = getColPtr(colNum1)) == NULL
           || (ptrCol2 = getColPtr(colNum2)) == NULL)
        {
            intersectRows = NULL;
            *numIntersect = 0;
            return;
        }

        //columns are non-empty
        while((ptrCol1 = getColPtr(colNum1)) == NULL || (ptrCol2 = getColPtr(colNum2)) != NULL)
        {
            if(ptrCol1->getRowID() == ptrCol2->getRowID())
            {
                index = ptrCol1->getRowID();
                rowCount++;
                int* tempArray = NULL;
                //newArray[] is one larger than array[]
                int* newArray = new int [sizeof(array)+1];
                for(int i=0; i<sizeof(array); i++)
                {
                    //copy array[] into newArray[]
                    newArray[i] = array[i];
                }
                newArray[sizeof(array)] = index;

                //set array[] to point to newArray[], and deallocate the old one
                tempArray = array;
                array = newArray;
                delete[] tempArray;
            }
            //keep traversing pointers until both are at same row
            else if(ptrCol1->getRowID() > ptrCol2->getRowID())
            {
                ptrCol2 = ptrCol2->getDown();
            }
            //keep traversing pointers until both are at same row
            else
            {
                ptrCol1 = ptrCol1->getDown();
            }
        }

        *intersectRows = new int [sizeof(array)];
        for(int i=0; i<sizeof(array); i++)
        {
            //store common row indices of both rows in *intersectRows array
            *intersectRows[i] = array[i];
        }
        *numIntersect = rowCount; //number of common rows

    }

    int main()
    {
        float* a;
        float* avg;
        int** b;
        int* c;

        SparseMatrix s(3,4);
        s.insertElement(1,1,1);
        s.insertElement(0,2,3);
        s.insertElement(1,2,2);                      //LINE 378
        s.getElement(1,2, a);
        s.computeRowAverage(1, avg);
        s.computeColAverage(2, avg);
        s.intersectTwoRows(0,1, b, c);
        s.intersectTwoCols(1,2, b, c);
        s.removeElement(1,1);
        s.~SparseMatrix();

    }
     
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?



Similar Discussions: Seg fault in Sparse Matrix Code (due in 2.5 hours)
Loading...