C - Double Linked List Ordering

Hey there HBH,

I've been struggling with this code for a long time now. I'm creating a file compressor using Huffman Algorithm. First of all, i need to read the file and count the number of times each character appears. Everytime i find a character that has not been counted, it goes to my double linked list with a value of one. Everytime i read a character that has already been counted, i sum 1 to the value of the count and reorder the element (Ascendent). I need to order those values but i'm having a trouble with my ordering function. Below it's an example of how the linked list should look like, step by step:

ABCA -> text file

A - 1

A - 1 B - 1

A - 1 B - 1 C - 1

B - 1 C - 1 A - 2 (the two is reordered when read with fscanf)

There is a mistake in my function LST_reorder( List * temp ), but i'm not finding it :S Can you help me out? I'm fighting against this for two days now.

  char letter ;
  int amount ;
  struct list * before ;
  struct list * next ;
} List;

List * LST_get( List * first , char caption )
{
  List * runner ;
  
  if( first == NULL )
    return NULL ;
  
  for( runner = first ; runner != NULL ; runner = runner->next )
  {
    if( runner->letter == caption )
    {
      return runner ;
    }
  }
  
  return NULL ;
}


List * LST_reorder( List * element )
{
  List * runner ;
  
  if( element == NULL || element->next == NULL )
  {
    return element ;
  }
  else
  {
    runner = element->next ;
    while( element->amount >= runner->amount && runner != NULL )
    {
      element->next = runner->next ;
      runner->before = element->before ;
      element->before = runner ;
      runner->next = element ;
      runner = element->next ;
    }
    return element ;
  }
}

List * LST_insert( List * first , char caption )
{
  List * temp ;
  
  temp = LST_get( first , caption ) ;
  
  if( temp != NULL )
  {
    temp->amount += 1 ;
    temp = LST_reorder( temp ) ;
  }
  else
  {
    temp = ( List * )malloc( sizeof( List ) ) ;
  
    temp->letter = caption ;
    temp->amount = 1 ; // Because it was found once
    if( first == NULL )
    {
      temp->next = NULL ;
      temp->before = NULL ;
    }
    else
    {
      first->before = temp ;
      temp->next = first ;
      temp->before = NULL ;
    }
  }
  
  return temp ;  
}

PS: When i remove the line: markuptemp = LST_reorder( temp ) ; The list work's fine, yet, unordered

Change markupwhile( element->amount >= runner->amount && runner != NULL ) to markupwhile( runner != NULL && element->amount > runner->amount ) Things are evaluated in order, when you hit the NULL, you'll try to step into it for comparison, which in turn gives a NULL pointer exception. Furthermore, if you're only rearranging for larger than, it's just wasting time to switch places for when they are the same.

COM wrote: Change markupwhile( element->amount >= runner->amount && runner != NULL ) to markupwhile( runner != NULL && element->amount > runner->amount ) Things are evaluated in order, when you hit the NULL, you'll try to step into it for comparison, which in turn gives a NULL pointer exception. Furthermore, if you're only rearranging for larger than, it's just wasting time to switch places for when they are the same.

That worked! I'm amazed. It does not display all characters now, but i guess it will be easier to solve this one. Thank you a lot COM!

PS: Fixed it! It's is working nice. For those willing to study this case, here i post the function finished (Again, thanks COM):

{
  List * runner ;
  List temp ;
  
  if( element == NULL )
  {
    return element ;
  }
  else
  {
    runner = element->next ;
    while( runner != NULL && element->amount > runner->amount )
    {
      temp.amount = element->amount ;
      temp.letter = element->letter ;
      element->amount = runner->amount ;
      element->letter = runner->letter ;
      runner->amount = temp.amount ;
      runner->letter = temp.letter ;
      element = runner ;
      runner = element->next ;
    }
    return element ;
  }
}```

No worries, basic stuff. I hope you've figured out why exactly the second problem appeared and not just managed to solve it, because to be frank, considering the nature of linked lists, I find that an ugly solution.

COM wrote: No worries, basic stuff. I hope you've figured out why exactly the second problem appeared and not just managed to solve it, because to be frank, considering the nature of linked lists, I find that an ugly solution.

Well, the idea first is to make it work. I need to hand in this Huffman thing on thursday. But when i finish i'll certainly optimize the code because it is looking terrible. At least it's modular, so it'll be easy to modify.