Error while running...

[gaurav_13191]

Hi, I have the following code which compiles absolutely fine..

using namespace std;

#include<iostream>
#include<stdio.h>
#include<conio.h>

struct node
{
  int data;
  struct node *link;
};

void add(struct node **,int);
void display(struct node*);
int count(struct node *);

int main(void)
{
    struct node *p;
    p=NULL;
    
    add(&p,5);
    add(&p,1);
    add(&p,6);
    add(&p,4);
    add(&p,7);
    
    display(p);
    cout<<"\nNo of elements in linked list:"<<count(p);
    getch();
    return 0;
}

void add(struct node **q,int num)
{
     struct node *r,*temp;
     r=*q;
     if(num<=r->data||r==NULL)
     {
      struct node *s;
      s= new struct node;
      s->link=*q;
      s->data=num;
      *q=s;
     }
     else
     {
     temp=new struct node;
     temp->data=num;
     while(r!=NULL)
     {
      if(r->data<=num&&(r->link->data>num||r->link==NULL))
      {
        temp->link=r->link;
        r->link=temp;
        return;
      }
      r=r->link;
     }
     }
}  

void display(struct node *q)
{
 struct node *temp;
 temp=q;
 while(temp!=NULL)
 {
 cout<<temp->data;
 cout<<"\n";
 temp=temp->link;
 }
}

int count(struct node *q)
{
    struct node *e;
    int n=0;
    while(q!=NULL)
    {
     n++;
     q=q->link;
    }
    return n;
}

However when I run the code, I get an error (LinkedList2.exe(name of my file) has encountered a problem and needs to close.. and there is no output..)

Please suggest some solution to this..I am using dev C++ as compiler

[arkoenig]

The first statements you execute in your main program are

p = NULL;
add(&p,5);

The first statements you execute in add are

r=*q;
if(num<=r->data||r==NULL)
// ...

Here, q is the first parameter of add, which means that the value of q is &p as computed in main. Therefore, *q is the same value as p in main, or NULL.

When you try to access r->data when r is NULL, the result is a run-time error.

I will leave it to you to figure out (a) what the problem is, (b) how to fix it, and (c) whether there are any other problems.

[gaurav_13191]

As you pointed out I changed the statement to

if((r==NULL)||r->data>num)

Now,as r=NULL the first condition should be satisfied and the program should then go into the block defined within if and now there should be no problem.. But the result is still the same.. Help!!

[arkoenig]

If the result is still the same, that suggests that there are similar problems elsewhere in the program. Perhaps you should look for them.

[gaurav_13191]

I tried but could not find any other mistake which could have caused runtime error.. Can you please help!!

[Stefano Mtangoo]

I tried but could not find any other mistake which could have caused runtime error.. Can you please help!!

Use debugger to step through your code and you will find errornous line which will be easy to fix.

Also get yourself Update IDE. I think DevCPP died many years ago!
get CodeLite, CodeBlocks, VC++ Express or Active version of DevCPP called wxDevC++

[xavier666]

#include<conio.h>

This code hurts :O

I tried but could not find any other mistake which could have caused runtime error.. Can you please help!!

We here will not directly give you the answer. Check again. You'll find the error...
Give us the new corrected code...

[JasonHippy]

OK, well arkoenig hit the nail on the head with his description of the problem.
This thread is becoming a little painful to read now, so I think I'll put you out of your misery. But I'll explain things as I go, that way I'm not just spoon-feeding code. Also, that way, you'll at least be able to understand what's going on!

Before we go into that, here's a quick note on the AND (&&) and OR (||) operators:
With the boolean logical comparisons, expressions are evaluated from left to right.
With an AND, if the left-hand expression evaluates to false, the AND returns false without bothering to evaluate the right-hand expression.
However, OR's will only return after evaluating the expressions on both sides.

Bearing that in mind, let's get onto your problem:
First up, the first 'if' statement in your add function:

if(num<=r->data||r==NULL)

Simply moving the 'r==NULL' comparison to the left does not solve the problem:

if(r==NULL || num<=r->data)

This is because the OR evaluates both sides of the expression before returning a value. So in cases where r is NULL, the left hand side of the expression will evaluate to true, but due to the nature of the OR it will also attempt to evaluate the right hand expression.
But because r is NULL, the attempt to read r->data in the right hand expression will cause a crash. So you need to include an additional test in the right hand side of the OR to ensure that r is not null before attempting to access r->data.
So you'll need to put an additional AND in there like this:

if(r==NULL || (r!=NULL && num<r->data))

// or more succinctly:
if(!r || (r && num<r->data))

With this change to the code, if r is NULL, before the right hand side of the OR is evaluated, the bracketed AND gets evaluated.
Because r is NULL, the left hand part of the AND statement will evaluate to false, thus the AND returns false. The right hand part of the AND does not get evaluated.
This way we avoid a memory access violation and a crash!

Likewise, the second 'if' statement has a similar problem:

if(r->data<=num&&(r->link->data>num||r->link==NULL))

The left hand part of the AND is OK, but what about the bracketed OR statement on it's right?
You are attempting to access r->link->data without testing whether r->link is valid. Again this could result in a crash if r->link was NULL.
Once more we put an additional AND in there to ensure that r->link is not NULL:

if( r->data<=num && ((r->link!=NULL && r->link->data>num) || r->link==NULL) )

// or more succinctly:
if( r->data<=num && ((r->link && r->link->data>num) || !r->link) )

Other than those two logical errors in your 'if' statements the rest of your code should be fine!

Also I mentioned this in your thread from the other day, but there is some unneccesary duplicate code in your add function which makes the logic look more convoluted than it actually needs to be.

In both of the 'if' statements, you were creating a new node and assigning its data member the value of num. You can factor this common code outside of the 'if' statements. All the 'if' statements need to do is determine what to do with the link member variable of the new node.
In other words, you can refactor the code like this:

void add(struct node **q, int num)
{
	struct node *temp = new struct node;
	temp->data = num;

	if(!*q || (*q && num<*q->data))
	{
		temp->link=*q;
		*q=temp;
	}
	else
	{
		struct node *r=*q;
		while(r)
		{
			if( r->data<=num && ((r->link && r->link->data>num) || !r->link) )
			{
				temp->link=r->link;
				r->link=temp;
				return;
			}
			r=r->link;
		}
	}
}

Which makes the code a lot cleaner and it's now a little easier to read and understand.
The only thing you could perhaps do with are a few comments in your code!
e.g.

/////////////////////////////////////////////////////////////
/// add - add a node to the linked list
/////////////////////////////////////////////////////////////
/// \param<q> pointer to the head node of the linked list (struct node**)
/// \param<num> data for new node (int)
/////////////////////////////////////////////////////////////
void add(struct node **q, int num)
{
	// create a new node and assign it the passed-in value
	struct node *temp = new struct node;
	temp->data = num;

	// if head of list is empty, or the new node's data is lower than the head node's data
	if(!*q || (*q && num<(*q)->data))
	{
		// the new node becomes the head node
		temp->link=*q;
		*q=temp;
	}
	else
	{
		// traverse the list
		struct node *r=*q;
		while(r)
		{
			// If new node's data is: 
			// Greater than the previous node AND less than the next node
			// OR if we've reached the end of the list
			if( r->data<=num && ((r->link && r->link->data>num) || !r->link) )
			{
				// Insert the new node into the list at the current position and return
				temp->link=r->link;
				r->link=temp;
				return;
			}

			// move to the next node
			r=r->link;
		}
	}
}

That way others reading your code will have a better understanding of your intentions and can more easily pick up on logical errors in the code.
I hope this is of some help to you.

Cheers for now,
Jas.

BTW: As also mentioned in your other thread, I still think this linked list could be better implemented as a class, but maybe that's just me!

[gaurav_13191]

Thanks JasonHippy and others for their suggestions.. but the problem is that I am following a book so I am adopting their way of programming(That is why I didn't use a class).. I am new to linked lists and when I would feel a little comfortable with them, I would surely use a class and would try to optimize the code.. Right now I am not upto that level that I can code linked lists myself.. but would certainly keep all these suggestions in mind the next time I program.. Thanks again..

[arkoenig]

First up, the first 'if' statement in your add function:

if(num<=r->data||r==NULL)

Simply moving the 'r==NULL' comparison to the left does not solve the problem:

if(r==NULL || num<=r->data)

This is because the OR evaluates both sides of the expression before returning a value. So in cases where r is NULL, the left hand side of the expression will evaluate to true, but due to the nature of the OR it will also attempt to evaluate the right hand expression.

I am sorry to have say that you are completely mistaken about this description.
The definition of || is that it evaluates its left operand first; if that operand yields true, then the result of || is true and the right operand is not evaluated.

Similarly, && evaluates its left operand first; if that operand yields false, then the result of && is false and the right operand is not evaluated.

[JasonHippy]

I am sorry to have say that you are completely mistaken about this description.
The definition of || is that it evaluates its left operand first; if that operand yields true, then the result of || is true and the right operand is not evaluated.

Similarly, && evaluates its left operand first; if that operand yields false, then the result of && is false and the right operand is not evaluated.

Oops, yeah you're right! Of course it is! {face-palm} What the hell was I thinking?? I definitely dropped the ball there! {ashamed}

Hang on... Just for the sake of my own sanity... {firing up compiler}
I'm gonna try copying the OPs code and then making my suggested changes and compiling and running (didn't do that earlier, just used notepad to type my solution and then cut/pasted into my post! heh heh!)....

OK, that works...

Now lets get rid of the extraneous ANDs that I've put into the if's and shift the checks against null to the left of the OR's..
Now compile and....Yup that works... Hmmm, now I feel really stupid!!
Thanks for correcting me there arkoenig!

So the conditions of the two if statements in the add function should be:

if(!*q || num<(*q)->data)

and

if( r->data<=num && (!r->link || r->link->data>num) )

For want of a better word, I really am a twit* sometimes! (*substitute the 'i' for an 'a' is more like it!)
I use this stuff every day without thinking about it, but when it comes to explaining it to somebody else, I do tend to get things slightly wrong from time to time!

Thanks again for the correction Arkoenig, it really is appreciated and sorry to the OP for my schoolboy error!

Cheers for now,
Jas.

[arkoenig]

Thanks again for the correction Arkoenig, it really is appreciated and sorry to the OP for my schoolboy error!

Hey, don't worry about it, and thanks for being a good sport!

Heck, I make elementary blunders sometimes too, and I've been programming in C++ for more than 25 years.