[SOLVED] Erroneous pointer monograph?

atlantis43 · 10-31-2014, 10:13 AM

In a popular on-line C-programming monograph on pointers (Nick Parlante, “Linked List Problems”, Stanford U.), I’m running into the following dilemma with a suggested solution in the text, which I cannot make compile.
Though I have produced a satisfactory working solution, I’m wondering if anyone can identify if I’ve made a coding error while trying to employ the suggested solution, or is the suggested solution erroneous.

[I note that I still had to rem the last two code lines of AlternateSplit() to accomplish compiling-------don’t understand why those code lines were even included in the original]

The Problem, as stated, is:
Write a function AlternatingSplit() that takes one list and divides up its nodes to make two smaller lists. The sublists should be made from alternating elements in the original list. So if the original list is {a, b, a, b, a}, then one sublist should be {a, a, a} and the other should be {b, b}. You may want to use MoveNode() as a helper. The elements in the new lists may be in any order.
/*
Given the source list, split its nodes into two shorter lists.
If we number the elements 0, 1, 2, ... then all the even elements
should go in the first list, and all the odd elements in the second.
The elements in the new lists may be in any order.
*/

Code:

void AlternatingSplit(struct node* source,
struct node** aRef, struct node** bRef) {
// Your code

The Recommended Solution in the monograph is as follows:

Code:

void AlternatingSplit(struct node* source,
struct node** aRef, struct node** bRef) {
struct node* a = NULL; // Split the nodes to these 'a' and 'b' lists
struct node* b = NULL;
struct node* current = source;
while (current != NULL) {
MoveNode(&a, &current); // Move a node to 'a'
if (current != NULL) {
MoveNode(&b, &current); // Move a node to 'b'
}
}
*aRef = a;
*bRef = b;
}

This (my) version compiles and functions:

Code:

#include <stdio.h>
#include <stdlib.h>
struct node
{
int i;
struct node* next;
};
//prototypes
void AlternatingSplit(struct node* source,struct node** aRef,struct node** bRef);
void MoveNode(struct node** destRef,struct node** sourceRef);
void Push(struct node** headref,int i);

int main(void)
{

int i;
struct node* head=NULL;
struct node* a=NULL;
struct node* b=NULL;
struct node* tail;
    Push(&head,0);  //build list
    tail=head;
    for(i=1;i<9;i++)
    {
    Push(&(tail->next),i);
    tail=tail->next;
    }
    AlternatingSplit(head,&a,&b); //split into lists a and b
}

void AlternatingSplit(struct node* source,struct node** aRef,struct node** bRef)
{
//struct node* a = NULL;
//struct node* b = NULL;
    while (source != NULL) 
    {
    MoveNode(aRef, &source); // Move node from source to 'a'
    if (source != NULL) 
        {
        MoveNode(bRef, &source); // Move node from source to 'b'
        }
    }
//*aRef = a;
//*bRef = b;
}

void MoveNode(struct node** destRef,struct node** sourceRef)
{
struct node* current;
current = *sourceRef;
*sourceRef = current->next;
current->next = *destRef;
*destRef = current;
}

void Push(struct node** headref,int i)
{
struct node* temp=malloc(sizeof(struct node));
temp->i = i;
temp->next = *headref;
*headref = temp;
}

However, this version, which is a suggested solution in the text, does not compile;

Code:

#include <stdio.h>
#include <stdlib.h>
struct node
{
int i;
struct node* next;
};
//prototypes
void AlternatingSplit(struct node* source,struct node** aRef,struct node** bRef);
void MoveNode(struct node** destRef,struct node** sourceRef);
void Push(struct node** headref,int i);

int main(void)
{

int i;
struct node* head=NULL;
struct node* tail;
    Push(&head,0);  //build list
    tail=head;
    for(i=1;i<9;i++)
    {
    Push(&(tail->next),i);
    tail=tail->next;
    }
    AlternatingSplit(head,&a,&b); //split into lists a and b
}

void AlternatingSplit(struct node* source,struct node** aRef,struct node** bRef)
{
struct node* a = NULL;
struct node* b = NULL;
    while (source != NULL) 
    {
    MoveNode(aRef, &source); // Move node from source to 'a'
    if (source != NULL) 
        {
        MoveNode(bRef, &source); // Move node from source to 'b'
        }
    }
 //*aRef = a;
//*bRef = b;
}

void MoveNode(struct node** destRef,struct node** sourceRef)
{
struct node* current;
current = *sourceRef;
*sourceRef = current->next;
current->next = *destRef;
*destRef = current;
}

void Push(struct node** headref,int i)
{
struct node* temp=malloc(sizeof(struct node));
temp->i = i;
temp->next = *headref;
*headref = temp;
}

NevemTeve · 10-31-2014, 12:51 PM

It's quite easy too fix, eg:

Code:

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int i;
    struct node* next;
};

void AlternatingSplit(struct node* source,struct node** aRef,struct node** bRef);
void MoveNode(struct node** destRef,struct node** sourceRef);
void Push(struct node** headref,int i);

int main(void)
{
int i;
struct node* head=NULL;
struct node* tail;
struct node *a, *b;

    Push(&head,0);  //build list
    tail=head;
    for(i=1;i<9;i++)
    {
    Push(&(tail->next),i);
    tail=tail->next;
    }
    AlternatingSplit(head,&a,&b); //split into lists a and b
}

void AlternatingSplit(struct node* source,struct node** aRef,struct node** bRef)
{
    struct node* a = NULL;
    struct node* b = NULL;

    while (source != NULL) 
    {
    MoveNode(aRef, &source); // Move node from source to 'a'
    if (source != NULL) 
        {
        MoveNode(bRef, &source); // Move node from source to 'b'
        }
    }
    *aRef = a;
    *bRef = b;
}

void MoveNode(struct node** destRef,struct node** sourceRef)
{
    struct node* current;

    current = *sourceRef;
    *sourceRef = current->next;
    current->next = *destRef;
    *destRef = current;
}

void Push(struct node** headref,int i)
{
    struct node* temp=malloc(sizeof(struct node));

    temp->i = i;
    temp->next = *headref;
    *headref = temp;
}

atlantis43 · 10-31-2014, 04:55 PM

Thanks (again) so much. Hard to believe that such errors in scholarly monographs are never corrected by the authors.

atlantis43 · 11-06-2014, 03:12 PM

Quote:

Originally Posted by NevemTeve

It's quite easy too fix, eg:

Code:

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int i;
    struct node* next;
};

void AlternatingSplit(struct node* source,struct node** aRef,struct node** bRef);
void MoveNode(struct node** destRef,struct node** sourceRef);
void Push(struct node** headref,int i);

int main(void)
{
int i;
struct node* head=NULL;
struct node* tail;
struct node *a, *b;

    Push(&head,0);  //build list
    tail=head;
    for(i=1;i<9;i++)
    {
    Push(&(tail->next),i);
    tail=tail->next;
    }
    AlternatingSplit(head,&a,&b); //split into lists a and b
}

void AlternatingSplit(struct node* source,struct node** aRef,struct node** bRef)
{
    struct node* a = NULL;
    struct node* b = NULL;

    while (source != NULL) 
    {
    MoveNode(aRef, &source); // Move node from source to 'a'
    if (source != NULL) 
        {
        MoveNode(bRef, &source); // Move node from source to 'b'
        }
    }
    *aRef = a;
    *bRef = b;
}

void MoveNode(struct node** destRef,struct node** sourceRef)
{
    struct node* current;

    current = *sourceRef;
    *sourceRef = current->next;
    current->next = *destRef;
    *destRef = current;
}

void Push(struct node** headref,int i)
{
    struct node* temp=malloc(sizeof(struct node));

    temp->i = i;
    temp->next = *headref;
    *headref = temp;
}

Thought the above correction (which compiled) was suitable, but I find that it leaves "a" and "b" empty. Is it valid to pass uninitialized pointers *a and *b in main() as arguments to AlternatingSplit() ?
I remain uncertain as to the whole "solution" listed by the author of the monograph.

johnsfine · 11-06-2014, 03:35 PM

Quote:

Originally Posted by atlantis43

Thought the above correction (which compiled) was suitable, but I find that it leaves "a" and "b" empty. Is it valid to pass uninitialized pointers *a and *b in main() as arguments to AlternatingSplit() ?
I remain uncertain as to the whole "solution" listed by the author of the monograph.

I don't see why NevemTeve uncommented the lines

Code:

 //*aRef = a; 
 //*bRef = b;

I think those lines were correctly commented out in the original.

Adding the missing declaration of a and b in main was obviously needed. Beyond that, I didn't test and didn't desk check carefully.

Anyway, in answer to your question, it is perfectly valid to pass the addresses of uninitialized pointers. Something needs to initialize those before use, but that can be (probably should be) inside the function, rather than outside, such as:

Code:

void AlternatingSplit(struct node* source,struct node** aRef,struct node** bRef)
{
    *aRef = NULL;
    *bRef = NULL;
    while (source != NULL) 
    {
    MoveNode(aRef, &source); // Move node from source to 'a'
    if (source != NULL) 
        {
        MoveNode(bRef, &source); // Move node from source to 'b'
        }
    }
}

atlantis43 · 11-06-2014, 04:28 PM

Johnsfine:
Thanks for your info regarding passing uninitialized variables.
No, I was the one who commented out the lines

Code:

*aRef = a; 
*bRef = b;

as there was no need for a return value in my working solution: in fact, my version would not compile properly with those return values present, and I would get following errmsg on compilation:

Quote:

prob12.c:68:9: error: use of undeclared identifier 'a'
*aRef = a;
^
prob12.c:69:9: error: use of undeclared identifier 'b'
*bRef = b;

With NevemTeve's code, if I try using the following function to evaluate what is contained in a and b lists:

Code:

void Length_Vals(struct node* head)
{
struct node* current = head;
int count = 0;
while(current!=NULL)
    {
    count++;

    printf("%3d",current->i);
    current = current->next;
    }
printf("\n# of nodes in list is %d\n",count);
}

I get the following terminal output:

Quote:

0 1 2 3 4 5 6 7 8 9
# of nodes in [original] list is 10

# of nodes in list [a] is 0

# of nodes in list [b] is 0

I remain completely befuddled by the "suggested" solution.

norobro · 11-06-2014, 07:17 PM

I believe NevemTeve has a typo in his AlternatingSplit():

Code:

    while (source != NULL) 
    {
    MoveNode(aRef, &source); // Move node from source to 'a'
    if (source != NULL) 
        {
        MoveNode(bRef, &source); // Move node from source to 'b'
        }
    }

Should be &a and &b respectively.

atlantis43 · 11-06-2014, 09:40 PM

Quote:

Originally Posted by norobro

I believe NevemTeve has a typo in his AlternatingSplit():

Code:

    while (source != NULL) 
    {
    MoveNode(aRef, &source); // Move node from source to 'a'
    if (source != NULL) 
        {
        MoveNode(bRef, &source); // Move node from source to 'b'
        }
    }

Should be &a and &b respectively.

Yes!!!, problem solved. Thanks to all.