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:


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:


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

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.

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

Thank you very much.
And can you upload the whole program after you finished ?

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.

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..

Originally Posted by Tko

Thank you very much.
And can you upload the whole program after you finished ?

Someone needs to TKO you.


Quzah.

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.

Originally Posted by oogabooga

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?

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.

Originally Posted by quzah

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

Where are you going through columns there?


Quzah.

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

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

I'm not going to do it for you. Give it a shot.


Quzah.