# Splitting a Matrix of Linked Lists

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 01-12-2012
jeanermand
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:
Attachment 11335

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:
Attachment 11336

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 :)
• 01-12-2012
oogabooga
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.
• 01-12-2012
jeanermand
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; }```
• 01-12-2012
Tko
Thank you very much.
And can you upload the whole program after you finished ?
• 01-12-2012
oogabooga
Quote:

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.
• 01-12-2012
jeanermand
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..
• 01-12-2012
quzah
Quote:

Originally Posted by Tko
Thank you very much.
And can you upload the whole program after you finished ?

Someone needs to TKO you.

Quzah.
• 01-12-2012
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.
• 01-16-2012
jeanermand
Quote:

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?
• 01-16-2012
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.
• 01-16-2012
jeanermand
Quote:

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;     }```
• 01-16-2012
quzah
Where are you going through columns there?

Quzah.
• 01-16-2012
jeanermand
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;     }```
• 01-16-2012
jeanermand
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; }```
• 01-16-2012
quzah
I'm not going to do it for you. Give it a shot.

Quzah.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last