unexpected output trying to generate an ordered linked list

Question

I am trying to write a program that generate an ordered random linked list. The problem is that the output sometimes is only 4 numbers and sometimes is an infinite sequence of numbers. I think the problem is in the gen function, how can i fix it?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 5

struct node{
    int v;
    struct node *nextPtr;
};

typedef struct node Node;
typedef Node *NodePtr;

void gen(NodePtr *startPtr);
void print(NodePtr start);

int main()
{
    NodePtr startPtr;
    startPtr = NULL;
    gen(&startPtr);
    print(startPtr);
    return 0;
}

void gen(NodePtr *startPtr)
{
    NodePtr currPtr, lastPtr, newPtr;
    int r;
    lastPtr = NULL;
    srand(time(NULL));


    for(int i = 0; i < N; i++){
        currPtr = *startPtr;
        r = rand()%101;
        while(currPtr != NULL && r > currPtr->v){
            lastPtr = currPtr;
            currPtr = currPtr->nextPtr;
        }
        newPtr = malloc(sizeof(Node));
        newPtr->v = r;
        newPtr->nextPtr = NULL;
        if(lastPtr == NULL){
            *startPtr = newPtr;
        }
        else{
            lastPtr->nextPtr = newPtr;
            newPtr->nextPtr = currPtr;
        }
    }
}

void print(NodePtr start)
{
    while(start != NULL){
        printf("%d ", start->v);
        start = start->nextPtr;
    }
}

Paul Ogilvie · Accepted Answer · 2019-01-22 16:31:21Z

3

lastPtr must be initialized to null in the for-loop.

Consider && r > currPtr->v being false on a 2nd (3rd...) iteration of the for loop. Consider that on a previous iteration the while loop was executed one or more times, so lastPtr has a value.

Then on this iteration where && r > currPtr->v is false the old value of lastPtr is used in the else part where it should have been null.

So:

    for(int i = 0; i < N; i++){
        lastPtr = NULL;
        currPtr = *startPtr;

...and then I ran it in the debugger and found also:

    newPtr = malloc(sizeof(Node));
    newPtr->v = r;
    newPtr->nextPtr = currPtr;     // set it here
    if(lastPtr == NULL){
        *startPtr = newPtr;        // because here it is needed too
    }
    else{
        lastPtr->nextPtr = newPtr; // and no lomger needed here
    }

The case I found was when rand() returned zero and the new node had to be inserted at the front.

edited Jan 22, 2019 at 16:31

answered Jan 22, 2019 at 16:17

Paul Ogilvie

25.4k4 gold badges26 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Alex Over a year ago

Ok, now works better but there Is still a problem, sometimes It not generate the correct number of random value("N")

Alex Over a year ago

Yes thanks. But why the first node can not just be NULL? It should not point to anything

Paul Ogilvie Over a year ago

@Alex, think what happens when you insert a node at the front: currPtr is the old *startPtr. Becasue the while loop has not executed, lastPtr is still null and so *starPtr= newPtr is executed. But the old *startPtr will be lost if you don't assign it as newPtr->nextPtr .

Alex Over a year ago

I still not understand. If the while loop is not executed currPtr = NULL. So newPtr->nextPtr = NULL should be the same as newPtr->nextPtr = currPtr.

Paul Ogilvie Over a year ago

If the while loop has not executed then currPtr = *startPtr; and this may not be null if there is an element in the list. If r is smaller than the first element it must be inserted at the front.

Ian Abbott · Accepted Answer · 2019-01-22 16:30:47Z

0

There are two problems.

When lastPtr == NULL, you forgot to set newPtr->nextPtr to currPtr. You need to set newPtr->nextPtr = currPtr unconditionally.
The lastPtr variable needs to be reinitialized to NULL each time around the loop.

Original code:

    for(int i = 0; i < N; i++){
        currPtr = *startPtr;
        r = rand()%101;
        while(currPtr != NULL && r > currPtr->v){
            lastPtr = currPtr;
            currPtr = currPtr->nextPtr;
        }
        newPtr = malloc(sizeof(Node));
        newPtr->v = r;
        newPtr->nextPtr = NULL;
        if(lastPtr == NULL){
            *startPtr = newPtr;
        }
        else{
            lastPtr->nextPtr = newPtr;
            newPtr->nextPtr = currPtr;
        }
    }

New code:

    for(int i = 0; i < N; i++){
        currPtr = *startPtr;
        lastPtr = NULL; // <-- (re-)initialize lastPtr
        r = rand()%101;
        while(currPtr != NULL && r > currPtr->v){
            lastPtr = currPtr;
            currPtr = currPtr->nextPtr;
        }
        newPtr = malloc(sizeof(Node));
        newPtr->v = r;
        if(lastPtr == NULL){
            *startPtr = newPtr;
        }
        else{
            lastPtr->nextPtr = newPtr;
        }
        newPtr->nextPtr = currPtr; // <<-- set newPtr->nextPtr unconditionally
    }

A more robust solution should also check the result of malloc.

edited Jan 22, 2019 at 16:30

answered Jan 22, 2019 at 16:11

Ian Abbott

18.1k1 gold badge22 silver badges39 bronze badges

3 Comments

Ian Abbott Over a year ago

I've reinitialized lastPtr in the loop. Try it now, it works for me!

Ian Abbott Over a year ago

@PaulOgilvie It didn't properly insert the new node when inserting at the beginning of the list, as you found out in your answer! I think we came up with the full solution between us. :)

Paul Ogilvie Over a year ago

Ian, yes, we have :-)

Alain Merigot · Accepted Answer · 2019-01-22 16:39:51Z

-1

Your code is uselessly complex. Instead of traversing the list at every iteration, use an head and tail pointer. If sorting is required, the value array can be initially sorted.

int comp( const void* a, const void* b)
{
     int a_int = * ( (int*) a );
     int b_int = * ( (int*) b );   
     if ( a_int == b_int ) return 0;
     else if ( a_int < b_int ) return -1;
     else return 1;
}

void gen(NodePtr *startPtr)
{
    NodePtr head, tail;
    int a[N] ;
    for(int i = 1; i < N; i++)
      a[i]=rand()%101;
    qsort(a,N,sizeof(N),comp);

    int i=0;
    // first node
    head = malloc(sizeof(Node));
    head->nextPtr=NULL;
    head->v=a[i];
    tail=head;        
    for(i = 1; i < N; i++){
      tail->nextPtr= malloc(sizeof(Node));
      tail=tail->nextPtr;
      tail->v=a[i];
      tail->nextPtr=NULL;
    }
    *startPtr=head;
}

edited Jan 22, 2019 at 16:39

answered Jan 22, 2019 at 16:20

Alain Merigot

11.7k3 gold badges22 silver badges33 bronze badges

4 Comments

Paul Ogilvie Over a year ago

Your code does not insert the new node in a sorted fashion, which is what he wants.

Alain Merigot Over a year ago

Right, I missed that.

Alex Over a year ago

Ok but It should be ordered.

Alain Merigot Over a year ago

Updated the answer with an initial sort. That's somehow cheating, but for a large number of values, it should much more efficient.

Collectives™ on Stack Overflow

unexpected output trying to generate an ordered linked list

3 Answers 3

5 Comments

3 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

3 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related