469,923 Members | 1,512 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,923 developers. It's quick & easy.

Help with linked list

61
Hi I am having some problems with the annoying segmentation error when I try to run a program that creates a linked list of numbers that are passed on to it.

All I am trying to do is to create a link list which takes number that may not possibly be in order. For example, I try to read a file which says,

101
102
105
104
103
101 <-------- Duplication
It should create a linked list with ascending order. I wrote a but it gives me a segmentation fault and after spending many hours deskchecking the code, I couldnt find the bug. Can anyone help me out?

CODE BELOW
NB: this is just part of the code, but the error lies in the function addBlock().

Expand|Select|Wrap|Line Numbers
  1. struct block
  2. {
  3.    struct block *down;
  4.    int number;   
  5. };
  6. typedef struct block block;
  7.  
  8. void addBlock(block **start, int number);
  9.  
  10. int main(int argc, char *argv[])
  11. {
  12.    block *head = NULL;
  13.    /* Codes to read every line of a file and obtain the number and store in number variable below, goes through a loop
  14.       to do this and loop goes on until the end of file is reach */
  15.  
  16.  
  17.    int number = some Function that Reads Number Into It ;
  18.    add(Block(&head, nuumber);
  19.  
  20. }
  21.  
  22. void addBlock(block **start, int number)
  23. {
  24.  
  25.    /*
  26.         There are 4 possibilities here: 
  27.         1) temp is the first block
  28.         2) temp can fit between 2 blocks,
  29.         3) A block with same number already exists
  30.         4) None of the above, set temp to the end of list         
  31.    */
  32.  
  33.    block *temp = newBlock(number);
  34.    block *curr = NULL;   /*curr scans every element in the link list*/ 
  35.  
  36.    if(*start == NULL)   /*First block*/
  37.    {
  38.       *start = temp;
  39.    }
  40.    else if ((*start)->down == NULL)      /*Second block*/
  41.    {
  42.        /*Check whether temp can go as first block*/
  43.        if(temp->number < (*start)->number)
  44.        {
  45.            temp->down = *start;
  46.           *start = temp;
  47.        }
  48.         else      /*Put it to the end of the list, as second element*/
  49.            (*start)->down = temp;
  50.    }
  51.    else      /*If there is more than 2 blocks*/
  52.    {
  53.       /*Scan down the list*/
  54.         for(curr = *start; curr->down != NULL; curr = curr->down)
  55.         {
  56.          /*Check if temp can fit in betwen any blocks*/            
  57.             if(curr->number < temp->number && 
  58.                                                     curr->down->number > temp->number)
  59.             {
  60.                 temp->down = curr->down;
  61.                 curr->down = temp;
  62.                 break;
  63.             }        
  64.         }
  65.    }
  66.    /*Checks if the new block has been added or not, if not 
  67.      it will be added to the end of the list */
  68.    if(temp->down == NULL)
  69.        curr->down = temp;    
  70. }
  71.  
  72.  
Oct 30 '07 #1
3 1244
weaknessforcats
9,208 Expert Mod 8TB
block *temp = newBlock(number); <<<???
block *curr = NULL; /*curr scans every element in the link list*/

if(*start == NULL) /*First block*/
{
*start = temp;
First: Does newBlock create the block on the heap??
Second: Does newBlock set the down pointer to 0?

Third: The add logic seems overly complicated. I would expect the check for *start to be NULL. After that, I don't see why the concern about 2 blocks. That is to say, is *start is not NULL you compare numbers until you reach the insertion point.

This code:
/*Scan down the list*/
for(curr = *start; curr->down != NULL; curr = curr->down)
{
/*Check if temp can fit in betwen any blocks*/
if(curr->number < temp->number &&
curr->down->number > temp->number)
{
temp->down = curr->down;
curr->down = temp;
break;
}
}
assumes that curr->down is not zero. That's a bad assumption. curr->down will be zero when curr is the end of the list.

What you have to do is save the value of curr so that on each cycle of the loop the save value is the address of the previous block. Then when your
temp->number is greater than curr->number, you insert after the save, that is, before the current node. Of course, if you run off the end of the list you insert there. And always, be sure your curr->down is not zero before using it.

My guess is that a lot of the code in the add block funciton can be deleted.
Oct 30 '07 #2
Alien
61
Thank you weakness for looking into it.

New block just creates a new block (dunno on heap or not) the code for it below is:

Expand|Select|Wrap|Line Numbers
  1. block* newblock(int number)
  2. {
  3.    /* dynamicaly allocate memory for an intNode
  4.       make sure it is initialised correctly
  5.    */
  6.  
  7.    block *temp;
  8.  
  9.    temp = (block *) malloc(sizeof(block));
  10.  
  11.    if (temp == NULL)   /*checks whether allocation was success or not*/
  12.    {
  13.       printf("WARNING - Memory allocation error\n");
  14.       exit(EXIT_FAILURE);
  15.    }
  16.    else
  17.    {
  18.       temp->number = number;
  19.       temp->next = NULL;
  20.       temp->down = NULL;
  21.    } 
  22.    return temp;   
  23. }
  24.  
It just uses malloc and returns a pointer to the block created. AddBlock function merely adds it.

So by complicated, are you suggesting that this functions is doing too much and should be split it's task into smaller functions? Something like,

NewBlock = mallocs and creates a new block.
AddBlock = adds it to the list and returns a pointer to the block added

and perhaps create another function say, orderBlocks which will order them in ascending order of the number?

Thank you for your help.

Regards.
Oct 31 '07 #3
weaknessforcats
9,208 Expert Mod 8TB
So by complicated, are you suggesting that this functions is doing too much and should be split it's task into smaller functions? Something like,

NewBlock = mallocs and creates a new block.
AddBlock = adds it to the list and returns a pointer to the block added
It looked like the add function was larger than it needed to be. So I reworked it:
Expand|Select|Wrap|Line Numbers
  1. void addBlock(block **start, int number)
  2. {
  3.  
  4.    block *temp = newBlock(number);
  5.    block *curr = NULL;   /*curr scans every element in the link list*/ 
  6.    block* prev = NULL;  /* used to save address of block before curr */
  7.  
  8.    if(*start == NULL)   /*First block*/
  9.    {
  10.       *start = temp;
  11.       return;                   /*you are done */
  12.    }
  13.    /*Scan down the list*/
  14.         prev = 0;
  15.         for(curr = *start; curr != NULL; curr = curr->down)
  16.         {
  17.             /*Check if temp can fit in betwen any blocks*/      
  18.             if(temp->number < curr->number )
  19.             {
  20.                 if (prev)
  21.                 {
  22.                       prev->down = temp;
  23.                       temp->down = curr;
  24.                 }
  25.                 else
  26.                 {
  27.                        temp->down = curr;
  28.                        *start = temp;
  29.                  }   
  30.                prev = curr;    
  31. }
  32.  
I didn't debug this, but what I did was try to simplify the logic and keep the list sorted.

So, if the start is NULL then temp is your new start.
Otherwise, you scan the list comparing numbers as long as the temp->number ius greater than the curr->number. When temp->number is less (or equal) to curr->number, then you have gone one block too far. So you insert the new block after the previous block. Conveniently, you have saved the address of the previous block.

Again, I apologize for any errors as I am trying to communicate the logic flow.
Oct 31 '07 #4

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

5 posts views Thread by jhon02148 | last post: by
1 post views Thread by jhon02148 | last post: by
6 posts views Thread by Steve Lambert | last post: by
13 posts views Thread by XXXXXX.working.in.my.blood | last post: by
1 post views Thread by drewy2k12 | last post: by
6 posts views Thread by Rylios | last post: by
4 posts views Thread by teddarr | last post: by
reply views Thread by Atos | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.