1. ## 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;
} 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 = pNew;
}
}
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 );
}
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

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

return;
}
/* =======================================================
This function finds the nth node from the end of the

*/
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
}

{
}

return pPre;
}

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

5. 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. 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 = findNthNode(matrix->m[1], 1);
}
I just need it to work in conjunction with the top now..

7. Originally Posted by Tko
Thank you very much.
And can you upload the whole program after you finished ?
Someone needs to TKO you.

Quzah.

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

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

11. 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)
else
}

return;
}

12. Where are you going through columns there?

Quzah.

13. 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)
else

if(count == (matrix->rows - 1))
count = 0;
else
count++;

}

return;
}

14. 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++)
{

}

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)
else

pWalk = pWalk->next;
count++;
}

return;
}

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

Quzah.