how to remove this segmentation fault

author_unknown · 01-20-2009, 07:59 AM

hi guyz .. i have written this program ascll.list that forms a linked list in ascending order...... the programs works fine on turboc 3 on windows bt gives segmentation fault on gcc4.3.1 on fedora 9

PHP Code:



#include<stdio.h> 
#include<stdlib.h> 
struct node 
{ 
int data; 
struct node *link; 
}; 
void add(struct node **,int); 
void display(struct node *); 
void count(struct node *); 
 
main() 
{ 
struct node *p; 
p=NULL; 
 
count(p); 
add(&p,6); 
add(&p,1); 
add(&p,3); 
add(&p,16); 
display(p); 
count(p); 
return 0; 
} 
 
void add(struct node **q,int num) 
{ 
struct node *temp,*r; 
temp=*q; 
r=malloc(sizeof(struct node)); 
r->data=num; 
 
if(*q==NULL||(*q)->data>num) 
{ 
*q=r; 
(*q)->link=temp; 
} 
else 
{ 
while(temp!=NULL) 
{ 
if(temp->data<=num && ((temp->link)->data>num || temp->link==NULL)) 
{ 
r->link=temp->link; 
temp->link=r; 
return; 
} 
temp=temp->link; 
} 
} 
} 
 
void display(struct node *q) 
{ 
printf("\n"); 
while(q!=NULL) 
{ 
printf("%d",q->data); 
q=q->link; 
} 
} 
 
void count(struct node *q) 
{ 
int c=0; 
printf("\n"); 
while(q!=NULL) 
{ 
c++; 
q=q->link; 
} 
printf("The no. of elemnts in linked list are %d",c); 
}

PHP Code:



[vikas@localhost ~]$ gcc -g ascll.c -o ascll 
[vikas@localhost ~]$ ./ascll  
 
Segmentation fault

SciYro · 01-20-2009, 09:03 AM

Why dont you run it thru a debugger like gdb yourself and find out why its happening. You havent even shown where in your program the segfault occurs.

author_unknown · 01-20-2009, 09:08 AM

i did it man.... its the if condition in the while loop.... in add function... but the logic seems 2 b correct...as program works fyn on windows

trouble is in

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

johnsfine · 01-20-2009, 09:27 AM

Quote:

Originally Posted by author_unknown

((temp->link)->data>num || temp->link==NULL)

Think about what the above expression means.

What happens when temp->link==NULL ??

Quote:

Originally Posted by author_unknown

the programs works fine on turboc 3 on windows

I forget which version turboc 3 is. There is some version of turboc in which you can compile real mode DOS programs and run them in v86 mode in Windows. Your program would work in DOS or in Windows DOS emulation. It would not work as a native Windows program.

dwhitney67 · 01-20-2009, 09:52 AM

I would recommend that you augment this code in add():

Code:

struct node *temp,*r; 
temp=*q; 
r=malloc(sizeof(struct node)); 
r->data=num;
...

to include this statement:

Code:

r->link = NULL;

As you have already indicated, the error is in this line:

Code:

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

Consider this approach (note that code is written in ISO C 1999):

Code:

void add(struct Node** head, int num)
{
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = num;
  newNode->link = 0;

  if (*head == 0)
  {
    // virgin list
    *head = newNode;
  }
  else
  {
    if ((*head)->data > num)
    {
      // insert new node at the head of the list
      newNode->link = *head;
      *head = newNode;
    }
    else
    {
      // search list for appropriate insert position
      struct Node* node = *head;
      struct Node* prev = 0;

      while (node && node->data <= num)
      {
        prev = node;
        node = node->link;
      }

      if (node == 0)
      {
        // insert new node at the end of the list
        prev->link = newNode;
      }
      else
      {
        // insert new node in the "middle" of the list
        newNode->link = prev->link;
        prev->link = newNode;
      }
    }
  }
}

johnsfine · 01-20-2009, 10:12 AM

I'm confident my earlier post is the answer author_unknown should look at. I hope the subsequent discussion doesn't hide that.

Quote:

Originally Posted by dwhitney67

r->link = NULL;

That was my first thought as well when looking at the code. But on inspection I saw that was not required.

Maybe it is good practice to initialize such pointers immediately when allocated, even when that initialization is reliably over written by subsequent code. Certainly that practice would avoid a lot of beginner mistakes.

Personally, I hate adding wasted steps to code. I often leave out such initialization and usually put in a comment explaining why I'm sure it is safe to leave out a particular initialization.

Quote:

Consider this approach

It's always tempting to respond to an ugly beginner example (of what should be simple code) with a complete clean rewrite.

I don't think that is a good idea. (oops, I failed to resist this time).

I think it is better to explain the specific issues in the code given. In this case, I just explained the bug that caused the segment fault. I could explain why many other details in the code are bad practice. But for the question asked in this thread, I guessed it would be best to just explain the bug itself.

But, while we're on the subject of clean rewrites, one problem in the original and just as bad in your version is too many possible paths. For a problem this simple, you shouldn't need all the exception cases coded that way. They make it too hard to desk check the logic and see that all paths are valid.

It is better to write the main path with enough generality that it covers all cases. The key to that in the add function is a Node** that is always valid and becomes the place you put the pointer to the new node and whose successor becomes the successor to the new node.

Code:

void add(struct Node** head, int num)
{
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = num;
  while ( *head && (*head)->data<=num )
  {
    head = &((*head)->link);
  }
  newNode->link = *head;
  *head = newNode;
}

If you also care about performance (and don't trust the optimizer) you might prefer:

Code:

void add(struct Node** head, int num)
{
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = num;
  struct Node* node;
  while ( (node=*head)!=NULL && node->data<=num )
  {
    head = &(node->link);
  }
  newNode->link = node;
  *head = newNode;
}