Archived

This topic is now archived and is closed to further replies.

bower12345

Linked List Help

Recommended Posts

Hoping for a little help. Working on a Huffman encoding / decoding application, yet I cannot find my logic error. No matter how large of a file I load into my application, my list will never get larger than 2 elements. Here''s the code if anyone can help me out...
#include <stdio.h>
#include <iostream.h>

class CList
{
public:
	CList( char );
	bool Search_And_Insert( char Temp );
	void Add_New_Node( char Temp );
	void Sort_List();
	struct Node
	{
		int nAppearances;
		char szItemName;
		Node *Next, *Previous;
		Node( char Name )
		{
			Next = NULL;
			szItemName = Name;
			nAppearances = 1;
		}
	};
	struct Tree
	{
		int nValue;
		Node *Next, *Left, *Right;
	};
	Node *Head, *Tail, *Current;
};

CList::CList( char Temp )
{
	Head = new Node( Temp );
	Current = Tail = Head;
}

bool CList::Search_And_Insert( char Temp )
{
	Current = Head;
	bool bRun_Loop = true;
	while( bRun_Loop && Current -> Next != NULL )
	{
		if( Current -> szItemName == Temp )
		{
			bRun_Loop = false;
			Current -> nAppearances++;
			return true;
		}
		else
		{
			Current = Current -> Next;
		}
	}
	return false;
}

void CList::Add_New_Node( char Temp )
{
	Tail -> Next = new Node( Temp );
	Tail = Tail -> Next;
}

void CList::Sort_List()
{
}

void main(int argc, char *argv[])
{
	unsigned char Temp;
	if( argc != 2 )
	{
		printf( "Huffman Encoding Application Alpha" );
		printf( "\nHuffman encoding application use is as follows: \n\t\t\"executable name <file to encode>\"" );
		return;
	}
	FILE *File_Handle;
	File_Handle = fopen( argv[1], "rb" );
	Temp = ( unsigned char )fgetc( File_Handle );
	CList List( Temp );
	while( Temp = fgetc( File_Handle ) != EOF )
	{
		if( !List.Search_And_Insert( Temp ) )
			List.Add_New_Node( Temp );
	}
	List.Current = List.Head;
	while( List.Current != List.Tail )
	{
		cout << "\n" << List.Current -> szItemName << "   " << List.Current -> nAppearances;
		List.Current = List.Current -> Next;
	}
	return;
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Ah Ha, I think I found your problem...

the line:

while( Temp = fgetc( File_Handle ) != EOF )

should be:

while( (Temp = fgetc( File_Handle )) != EOF )

The line was changing the returned char Temp to !EOF. Therefore, the search and add code was inreasing the count for one node. The reason you only had 2 nodes was that the first call you made added one node (during the construction) and following node was added during the first loop, and the rest being added to the second node. Hope this helps...

Oh, and BTW... It seems to me like the line in Search_And_Insert:
while( bRun_Loop && Current -> Next != NULL )

has this problem: The loop will terminate early if the next node is null. Well, what is only one node has been added? The next added one may still be a duplcate. I believe you should check for that right after you increment. Such as:

if( !(Current = Current -> Next))
break;

Share this post


Link to post
Share on other sites
Another suggestion:
In my humble opinion, it's best to code a templatized linked list, which is a little more difficult to write, but will allow you to never write a linked list again, since it can be applied everywhere with every type of variable.

eg:

CLinkedList<int> intList;
intList.Add(0);
intList.Add(1);

CLinkedList<float> floatList;
floatList.Add(0.0f);
floatList.Add(1.0f);


"My basic needs in life are food, love and a C++ compiler"
[Project AlterNova] [Novanet]


[edited by - Vich on November 18, 2003 5:34:49 AM]

Share this post


Link to post
Share on other sites