Follow us on Twitter!
One mans freedom fighter, another's terrorist.
Thursday, April 24, 2014
Navigation
Home
HellBoundHackers Main:
HellBoundHackers Find:
HellBoundHackers Information:
Learn
Communicate
Submit
Shop
Challenges
HellBoundHackers Exploit:
HellBoundHackers Programming:
HellBoundHackers Think:
HellBoundHackers Track:
HellBoundHackers Patch:
HellBoundHackers Other:
HellBoundHackers Need Help?
Other
Members Online
Total Online: 23
Guests Online: 21
Members Online: 2

Registered Members: 82903
Newest Member: Piriformis
Latest Articles
View Thread

HellBound Hackers | Computer General | Programming

Author

C - Double Linked List Ordering

chess_rock
Member



Posts: 244
Location:
Joined: 20.02.08
Rank:
Apprentice
Posted on 11-10-10 21:41
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

1)
A - 1

2)
A - 1
B - 1

3)
A - 1
B - 1
C - 1

4)
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.

Code
typedef struct list{
  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:
Code
temp = LST_reorder( temp ) ;



The list work's fine, yet, unordered
Author

RE: C - Double Linked List Ordering


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 11-10-10 22:51
Change
Code
while( element->amount >= runner->amount && runner != NULL )



to
Code
while( 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.


Author

RE: C - Double Linked List Ordering

chess_rock
Member



Posts: 244
Location:
Joined: 20.02.08
Rank:
Apprentice
Posted on 11-10-10 23:08
COM wrote:
Change
Code
while( element->amount >= runner->amount && runner != NULL )



to
Code
while( 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):

Code
List * LST_reorder( List * element )
{
  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 ;
  }
}




Edited by chess_rock on 11-10-10 23:19
Author

RE: C - Double Linked List Ordering


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 12-10-10 00:00
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.


Author

RE: C - Double Linked List Ordering

chess_rock
Member



Posts: 244
Location:
Joined: 20.02.08
Rank:
Apprentice
Posted on 12-10-10 00:20
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.

Edited by chess_rock on 12-10-10 16:44