Members Online
Total Online: 36 Web Spiders: 17
Guests Online: 33
Members Online: 3
Registered Members: 70170 Newest Member: bahmx
|
View Thread
| Author |
C - Double Linked List Ordering |
chess_rock
Member
Posts: 243
Location:
Joined: 20.02.08
Rank: God |
|
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.
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:
temp = LST_reorder( temp ) ;
The list work's fine, yet, unordered |
|
| Author |
RE: C - Double Linked List Ordering |
COM
Banned
Posts: 800
Location:
Joined: 31.08.07
Rank: God |
|
Change
while( element->amount >= runner->amount && runner != NULL )
to
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.
K'aem'nhi kh'rn, K'aem'nhi kh'r, K'aem'nhi kh'rmnu.
I'a Y'gs-Othoth! |
|
|
| Author |
RE: C - Double Linked List Ordering |
chess_rock
Member
Posts: 243
Location:
Joined: 20.02.08
Rank: God |
|
COM wrote:
Change
while( element->amount >= runner->amount && runner != NULL )
to
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):
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 |
COM
Banned
Posts: 800
Location:
Joined: 31.08.07
Rank: God |
|
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.
K'aem'nhi kh'rn, K'aem'nhi kh'r, K'aem'nhi kh'rmnu.
I'a Y'gs-Othoth! |
|
|
| Author |
RE: C - Double Linked List Ordering |
chess_rock
Member
Posts: 243
Location:
Joined: 20.02.08
Rank: God |
|
|
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 |
|
|
|
|
|
Main:
