Thread: Splitting a Matrix of Linked Lists

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    46

    Splitting a Matrix of Linked Lists

    So I have a square matrix composed of several linked lists, all containing random integers.
    The data diagram looks like this so far:
    Splitting a Matrix of Linked Lists-15c-000123103291042913021-png

    Here's all the source code for now:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <math.h>
    #include <crtdbg.h> 
    
    typedef struct node{
        int          data;
        struct node *link;
    } NODE;
    
    typedef struct{
        int rows;
        int cols;
        NODE **m;
    }MATRIX;
    
    
    MATRIX *createMatrix(int rows, int cols);
    MATRIX *buildRandomMatrix( int rows, int cols );
    void   printMatrix( MATRIX *matrix );
    
    NODE   *buildRandomList( int n );
    void   printList( NODE *pList );
    
    void split( MATRIX *matrix ); // must be changed
    
    int main( void )
    {
    //  Local Definitions 
        MATRIX *matrix;
    
    //  Statements 
        matrix = buildRandomMatrix( 6, 6 );
        //matrix = buildRandomMatrix( 3, 3 );
        //matrix = buildRandomMatrix( 2, 2 );
        //matrix = buildRandomMatrix( 1, 1 );
        //matrix = buildRandomMatrix( 0, 0 );
        //matrix = buildRandomMatrix( -10, -10 );
        //matrix = buildRandomMatrix( 5, 6 );
    
        if( !matrix )
            printf("Invalid sizes!\n");
        else
        {
            printf("ORIGINAL MATRIX:\n\n");
            printMatrix( matrix );
    
            split(matrix); // must be changed
            printf("NEW LISTS:\n\n");
    
            //printf( _CrtDumpMemoryLeaks() ? "Memory Leak\n" : "No Memory Leak\n");
        }
    
        system("pause");
    
        return 0;
    }
    
    /* ======================================================= 
       This function ...
         PRE:  matrix
         POST: ...
    */
    void split( MATRIX *matrix ) // must be changed
    {
    
        return;
    }
    
    // print up to here!
    /* ********************************************************** */
    /* ********************************************************** */
    /* ********************************************************** */
    
    /* ======================================================= 
       This function allocates a header structure for a MATRIX
       and a list of row NODE pointers
         PRE:  rows - the number of linked lists
               cols - the number of elements in each linked list
         POST: returns a pointer to the structure, all fields 
               initialized, OR NULL if not enough memory
    */
    MATRIX *createMatrix(int rows, int cols)
    {
        MATRIX *matrix;
    
        matrix = (MATRIX *) malloc(sizeof(MATRIX));
        if( matrix )
        {
            matrix->rows = rows;
            matrix->cols = cols;
            matrix->m    = (NODE **) calloc( rows, sizeof(NODE *));
            if( !matrix->m ) // not enough memory
            {
                free(matrix);
                matrix = NULL;
            }
        }
        return matrix;
    }
    
    /* ====================================================== 
       This function builds a matrix of rows linked lists, 
       each containing cols random numbers
         PRE: rows - the number of linked lists
              cols - the number of elements in each linked list
         
         POST: returns a pointer to MATRIX header structure
    */
    MATRIX* buildRandomMatrix( int rows, int cols )
    {
    //  Local Definitions 
        MATRIX *matrix = NULL;
        int    r;
    
    //  Statements 
        srand( time(NULL) );
    
        if ( rows > 0 && rows == cols )
        {
            matrix = createMatrix (rows, cols);
            for( r = 0; r < rows; r++ )
                matrix->m[r] = buildRandomList(cols);
        }// if
        return matrix;
    }
    
    
    /* ====================================================== 
       This function prints a matrix of rows linked lists,
       each containing cols random numbers
         PRE:  matrix - a pointer to the header structure of
                        a matrix
         POST: matrix printed
    */
    void printMatrix( MATRIX *matrix )
    {
    //  Local Definitions 
        int r;
    
    //  Statements 
        for( r = 0; r < matrix->rows; r++ )
        {
            printf( "Row #%d: ", r + 1 );
            printList(matrix->m[r]);
        }
        printf("\n\n\n");
    
        return;
    }
    
    /* ====================================================== 
       This function builds a linked list of n random numbers
         PRE:  n - number of nodes
         POST: returns a pointer to the first node 
    */
    NODE *buildRandomList( int n )
    {
    //  Local Definitions 
        NODE * pList;
        NODE * pNew;
        NODE * pPre;
        int    i;
    
    //  Statements 
        pList = NULL; //empty list
        if ( n > 0 )
        {
            // create the first node in the list
            pList = (NODE *) malloc(sizeof(NODE));
            if( pList == NULL )
            {
                printf( "Not enough memory\n" );
                exit(100);
            }
            pList->data = 1 + rand() % 99;
            // create the rest of the nodes        
            pPre = pList;
            for( i = 1; i < n; i++ )
            {
                pNew = (NODE *) malloc(sizeof(NODE));
                if( pNew == NULL )
                {
                    printf( "Not enough memory\n" );
                    exit(100);
                }
                pNew->data = 1 + rand() % 99;
                pPre->link = pNew;
                pPre = pNew;
            }
            pPre->link = NULL; // set the last node's link to NULL
        }
        return pList;
    }
    
    
    /* ====================================================== 
       This function prints a linked list
         PRE:  pList - pointer to the first node in the list
         POST: list printed
    */
    void printList( NODE *pList )
    {
       NODE *pCurr;
      
       pCurr = pList;
       while( pCurr != NULL )
       {
          printf( "%4d", pCurr->data );
          pCurr = pCurr->link;
       }
       printf("\n");
    
       return;
    }
    I need to get it to look like this:
    Splitting a Matrix of Linked Lists-15c-00324234209r53204923402-png

    I'm not entirely sure how to start codewise....
    I know that I must rearrange the nodes in the lists but I am not sure how to do it.

    Any and all feedback is appreciated

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    As for the code you've posted, the comments "// Local Definitions" and "// Statements" are ridiculous. When you write comments, you should assume that the person reading your program actually knows the language!

    As for your question, it's hard to understand how you've written this code but can't do the relatively simple task of splitting the matrix. At any rate, you need to make an attempt. So give the split function a try and post just that function.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    46
    I've managed to successfully split the top half
    Code:
    void split( MATRIX *matrix ) // must be changed
    {
        int r, s;
        NODE* pPre, *pNext, *pPre2, *pNext2;
        
        //split top half into list_1
        for(r = 0; r < matrix->rows - 1; r++)
        {
            s = r + 2;
            pPre = findNthNode(matrix->m[r], 0);
            //printf("pPre : %d\t", pPre->data);
            pNext = findNthNode(matrix->m[r + 1], matrix->rows - s);
            //printf("pNew : %d\n", pNext->data);
            pPre->link = pNext;
        }
    
        return;
    }
    /* ======================================================= 
        This function finds the nth node from the end of the 
        linked list and returns its address
    
    */
    NODE *findNthNode (NODE *pList, int n)
    {
        NODE* pPre, *pCurr;
        int i;
    
        if(!pList)
            return NULL;
        pPre = pList;
        pCurr = pList;
    
        for(i = 0; i < n; i++)
        {
            if(!pCurr)
                return NULL;
            else
                pCurr = pCurr->link;
        }
    
        while(pCurr->link)
        {
            pCurr = pCurr->link;
            pPre = pPre->link;
        }
    
        return pPre;
    }

  4. #4
    Registered User
    Join Date
    Jan 2012
    Posts
    1
    Thank you very much.
    And can you upload the whole program after you finished ?

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I've managed to successfully split the top half
    Excellent! Keep going.

    As for the original code, it occurs to me that it was given to you by your teacher. I didn't realize that at first. (I suppose that explains the bizzaro-world comments like "//Statements" etc.)

    Anyway, you will need to change the declaration of split to something like the following in order to pass the lists back:
    Code:
    void split(MATRIX *matrix, NODE **list1, NODE **list2)
    {
        // split lists
        // ...
    
        // assign them to list1 and list2
        *list1 = first node of first list
        *list2 = first node of second list
    }
    I haven't looked at your code in detail yet but will probably do so after dinner.

  6. #6
    Registered User
    Join Date
    Nov 2011
    Posts
    46
    Thank you!

    I managed to eventually split the bottom half...
    the only catch being that if I do so, the top half won't split properly.

    I know I have to use new header nodes, but I figured I would save that for the end once I had all the kinks figured out.

    This is the code I got to successfully split the bottom
    Code:
    for(r = 1; r < matrix->rows - 1; r++)
            {
                pPre = findNthNode(matrix->m[r], matrix->rows - r);
                printf("pPre : %d\t", pPre->data);
                pNext = findNthNode(matrix->m[r + 1], matrix->rows - 1);
                printf("pNext : %d\n", pNext->data);
                pPre->link = pNext;
            }
            pPre = findNthNode(matrix->m[1], 1);
            pPre->link = NULL;
        }
    I just need it to work in conjunction with the top now..

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Tko View Post
    Thank you very much.
    And can you upload the whole program after you finished ?
    Someone needs to TKO you.


    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    The two parts do seem to work individually. Unfortunately, the first part modifies the lists of matrix in such a way that the second part won't work afterwards. You need to try to combine them into one pass, all in the same loop.

  9. #9
    Registered User
    Join Date
    Nov 2011
    Posts
    46
    Quote Originally Posted by oogabooga View Post
    The two parts do seem to work individually. Unfortunately, the first part modifies the lists of matrix in such a way that the second part won't work afterwards. You need to try to combine them into one pass, all in the same loop.
    I've had a few days to dabble in this and unfortunately procrastination got the best of me. I tried combining the two bits in the same loop but all to no avail..

    Can you give me some hints as to the logic involved?

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    So you want to turn a matrix into two linked lists?
    Code:
    A0 A1 A2 A3
    B0 A4 A5 A6
    B1 B2 A7 A8
    B3 B4 B5 A9
    B6 B7 B8 B9
    Something like that? So all you need to do is keep track of what row and what column you are on, and based on that, append that node to the correct list. If the current column is greater than or equal to the row counter, put this node on list 1. Otherwise put it on list 2.

    Something like that anyway.


    Quzah.
    Last edited by quzah; 01-16-2012 at 07:31 PM.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    Nov 2011
    Posts
    46
    Quote Originally Posted by quzah View Post
    So you want to turn a matrix into two linked lists?
    Code:
    A0 A1 A2 A3
    B0 A4 A5 A6
    B1 B2 A7 A8
    B3 B4 B5 A9
    B6 B7 B8 B9
    Something like that? So all you need to do is keep track of what row and what column you are on, and based on that, append that node to the correct list. If the current column is greater than or equal to the row counter, put this node on list 1. Otherwise put it on list 2.

    Something like that anyway.


    Quzah.
    Oh I see.. so maybe something like
    Code:
    void split( MATRIX *matrix , NODE **list_1, NODE **list_2)
    {
        int r;
        
        for(r = 0; r < matrix->rows; r++)
        {
            if(node_column >= r)
                add to list_1;
            else
                add to list_2;
        }
        
        return;
        }

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Where are you going through columns there?


    Quzah.
    Last edited by quzah; 01-16-2012 at 09:45 PM.
    Hope is the first step on the road to disappointment.

  13. #13
    Registered User
    Join Date
    Nov 2011
    Posts
    46
    Code:
    void split( MATRIX *matrix , NODE **list_1, NODE **list_2)
    {
        int r, count;
        
        count = 0;
        for(r = 0; r < matrix->rows; r++)
        {
            if(count >= r)
                add to list_1;
            else
                add to list_2;
                
            matrix->m[r] = matrix->m[r].link;
            
            if(count == (matrix->rows - 1))
                count = 0;
            else
                count++;
            
        }
        
        return;
        }
    Last edited by jeanermand; 01-16-2012 at 10:08 PM.

  14. #14
    Registered User
    Join Date
    Nov 2011
    Posts
    46
    Or maybe something like this...
    Code:
    void split( MATRIX *matrix , NODE **list_1, NODE **list_2)
    {
        int r;
        
        
        for(r = 0; r < matrix->rows; r++)
        {
            AddToList(matrix->m[r], list_1, list_2, r);
            
        }
        
        return;
        }
        
    void AddToList (NODE *pList, NODE **list_1, NODE **list_2, int n)
    {
        int count;
        NODE *pWalk;
            
        count = 0;
        pWalk = pList;
        while(pWalk != NULL)
        {
            if(n <= count)
                add to list_1;
            else
                add to list_2;
            
            pWalk = pWalk->next;
            count++;
        }
            
        return;
    }
    Last edited by jeanermand; 01-16-2012 at 10:50 PM.

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I'm not going to do it for you. Give it a shot.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sparse matrix as linked lists
    By ioan1ioan in forum C Programming
    Replies: 13
    Last Post: 07-30-2011, 12:46 PM
  2. Replies: 4
    Last Post: 05-15-2011, 10:36 AM
  3. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  4. splitting linked list recursive vs. iterative
    By Micko in forum C Programming
    Replies: 7
    Last Post: 03-17-2005, 05:51 PM
  5. question on linked lists(stack with linked lists)
    By dionys in forum C Programming
    Replies: 1
    Last Post: 06-02-2004, 11:08 AM

Tags for this Thread