Strange output from linked list

Strange output when traversing linked list of arays

Page 1 of 1

5 Replies - 2357 Views - Last Post: 15 May 2010 - 10:45 PM Rate Topic: -----

#1 jayd  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 13
  • Joined: 18-March 10

Strange output from linked list

Posted 15 May 2010 - 06:21 PM

Hi all,

I am currently working on a linked list that accepts numbers from a text file that can have an arbitrary number of fields. To achieve this I am using a linked list of arrays so I can store a number of values as the data of the node, where each node is a 'row' of the original input file (the rows have to be manipulated later.) While I think I've got the program accepting input and storing values just fine, whenever I try to traverse the list and get all the numbers I just input, I get weird jibberish numbers.

My output is typically:
5.72939e-313 0
5.72939e-313 0
5.72939e-313 0
5.72939e-313 0
5.72939e-313 0
5.72939e-313 0
5.72939e-313 0
5.72939e-313 0
5.72939e-313 0
5.72939e-313 0
5.72939e-313 0
5.72939e-313 0
5.72939e-313 0

When the output should be:
1 3
2 5
3 7
4 2
6 8
8 9
9 5
1 3
2 11
10 300
45 55
6 48
100 2

I'm completely stumped as to exactly what is wrong.

My main file is:
//Included libraries
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>

//Included user-defined files
#include "Node.h"
#include "LinkedList.h"

//Namespaces used
using namespace std;
using namespace node_class;
using namespace linked_list;

int main(int argc, char *argv[])
{
	//If there is an incorrect number of arguments (there should be two - the program execution and the input file)
	//An error is displayed and the progra exits
	if (argc > 3)
    {
       cout << "Incorrect execution - please enter two arguments next time you run the program. Program shall now exit.\n" << endl;
       return 0;
    }
    
    //Variables declared
    //At first it is assumed that there is no EOF line
    bool eofFound = false;
    LinkedList myList;
    Node* nodePtr = NULL;
    nodePtr = new Node;
    double num = 0;
    //The files that are input are declared and used throughout the program
    fstream fieldFile (argv[1]);
    fstream myFile (argv[1]);
	string line;
	string fieldLine;
	string tempString = "";

//	int sortField = 1;
	int fieldCount = 1;
	int maxField; 
	//If there is no file to be read (from the second argument)
	//an error message is displayed, and the program exits
	if(!myFile) 
	{
	    cout << "No file to be read. Please check the file locations. Program shall now exit.\n" << endl;
	    return 0;
  	}
	
	//The first line of the file is quickly scanned to know the number of fields we are working with
	getline (fieldFile,fieldLine);

	for (int i = 0; i < fieldLine.size(); i++)
	{
		if (fieldLine[i] == ' ') // look at each character and process it accordingly
		{
			fieldCount++;
		}
	}

	//The max number of fields is taken from the number o fields in the first line
	maxField = fieldCount;

	//Now each element from the files are added to the link list
	while (getline (myFile,line))
	{
			//If it's a valid line (not the EOF line, and assuming the input is valid as given in the assignment specifications)
			//then the data is converted to a double, and added to the list
			
			//An array is declared for each line
			Node::value_type fieldArray[maxField];
			if (line != "EOF")
			{	
				fieldCount = 0;
				tempString = "";		
				for (int i=0; i < line.size(); i++)
				{
					
					num = atof(tempString.c_str());
					if (line[i] == ' ') //We know there's a new field when there's a space
					{
						fieldArray[fieldCount] = num;
						tempString = "";
						fieldCount++;
					}
					else
					{
						tempString = tempString + line[i];
					}	
				}
				//The current number is input for the current index
				fieldArray[fieldCount] = num;
				//The number is input
				myList.tail_insert(nodePtr, num, fieldArray, maxField);	
			}

			//If the line is the EOF line, we know that it is the end of the files
			else if (line == "EOF")
			{
				//If there is an EOF line, the file is valid
				eofFound = true;
			}
	}

	if (!eofFound)
	{
		cout << "No EOF line in file - please check your input, and try again. Program shall now exit.\n";
		return 0;
	}
	//The file is closed
	myFile.close();
	
	
	cout << "List Input and Stored: " << endl;

	myList.traverse_list(nodePtr);
		
	//The program is complete, and hence exits
	return EXIT_SUCCESS;



}





My linked list implementation is:

//Imported libraries
#include <iostream>
#include <cstdlib>
#include <string>

//Included header files
#include "LinkedList.h"
#include "Node.h"

using namespace std;

//Namespace
namespace linked_list
{

	//Constructor - no default parameters or instantiation of memeber variables needed
	LinkedList::LinkedList()
	{
		fieldCount = 0;
	}

	//This function returns the size of the linked list, that is, the number of elements in the list
	size_t LinkedList::list_length(const Node* head_ptr)
	{
		const Node* current;
		size_t answer = 0;
		
		//This loop simply moves through the list, and increments the size for each element
		for (current = head_ptr; current != NULL;current = current->link())
		{
			//For each element, the size is incremented
			answer++;
		}
		
		//The size of the list is returned
		return answer;
	}

	//This function inserts an element at the head of the linked list
	void LinkedList::head_insert(Node*& head_ptr, const Node::value_type& dataEntry,Node::value_type fieldArrayEntry[], int fieldEntry)
	{
		//A new node is simply inserted at the head of the list
		head_ptr = new Node(dataEntry, head_ptr, fieldEntry);
	}

	//This function inserts an element at the tail of the linked list
	void LinkedList::tail_insert(Node*& node_ptr, const Node::value_type& dataEntry, Node::value_type fieldArrayEntry[], int fieldEntry)
	{
		//Two nodes are instantiated
		Node *temp = new Node;
		Node *tail_ptr;
		//The umber of fields is stored
		fieldCount = fieldEntry;
		//One node is set to be the last element in the list,
		//although it isn't an actual member of the list yet
		tail_ptr = new Node;
		//The array values are added to the list
		tail_ptr->setArray(fieldArrayEntry, fieldCount);
		//Data is set so I can make sure the program is working
		tail_ptr->setData(dataEntry);
		tail_ptr->setLink(NULL);

		//The other node is set to have the data from the node provided in the function parameters
		temp = node_ptr;

		//If the list is empty, then the node is already at the end, so it is simply placed in the list
		if (node_ptr == NULL)
		{
			node_ptr = tail_ptr;
		}
		else
		{
			//If there are elements in the list, this loop moves to the end of the list
			//where the new node will be inserted at the tail
			while (temp->link() != NULL)
			{  
				//The new link will be final link in the list
				temp = temp->link();
			}
			
			//The second node is added to the end of the list
			//by having it's link set to null (from the first node)
			temp->setLink(tail_ptr);
		}
	}

	//This function traverses the list and retrieves the data in eas array index in each node.
	void LinkedList::traverse_list(Node* head_ptr)
	{
		Node* current;
		
		for (current = head_ptr -> link(); current != NULL;current = current -> link())
		{
			for (int i = 0; i < fieldCount; i++)
			{
					cout << current->getArrayData(i) << " ";
					
			}
			
			cout << "\n";
		}

					
	}
}




The linked list header file is:
#include <iostream>
#include <cstdlib>
	
//Macroguard
#ifndef LINKED_LIST_H
#define LINKED_LIST_H

//Imported header files
#include "Node.h"

using namespace node_class;

//namespace	declaration
namespace linked_list
{
  class LinkedList
    {
    public:
    	
    	//Constructor
      	LinkedList();
      	
      	//Member functions for the linked list
        size_t list_length(const Node* head_ptr);
      	
      	void head_insert(Node*& head_ptr, const Node::value_type& dataEntry,Node::value_type fieldArrayEntry[], int fieldEntry);
      	
      	void tail_insert(Node*& tail_ptr, const Node::value_type& dataEntry,Node::value_type fieldArrayEntry[], int fieldEntry);
      	
      	void traverse_list(Node* head_ptr);
	
    private:
    	//Private member variables used
		size_t answer;	

		int fieldCount;

	};
	
}

#endif




And my node implementation is:
//Imported libraries
#include <iostream>
#include <cstdlib>

//Included header files
#include "Node.h"
using namespace std;
//Namespace
namespace node_class
{
	//Constructor
	Node::Node(const value_type& initialData, Node* initialLink, int fieldCount)
	{
		data = initialData;
		next = initialLink;
	}

	//Member functions to set data and link fields
	//Sets the data, that essentially isn't used
	void Node::setData(const value_type& newData)
	{
		data = newData;
	
	}
	
	//Sets the  array values
	void Node::setArray(value_type newArray[] , int fieldEntry)
	{
		for (int i = 0; i < fieldEntry; i++)
		{			
			fieldArray[i] = newArray[i];
		}
	}
	
	void Node::setLink(Node* newLink)
	{
		next = newLink;
	}

	//Member function to retrieve current data
	Node::value_type Node::getData()
	{
		return data;
	}
	
	Node::value_type Node::getArrayData(int index)
	{
		return fieldArray[index];
	}
	
	//Member functions to retrieve current link
	const Node* Node::link() const
	{
		return next;
	}

	Node* Node::link()
	{
		return next;
	}

}




The node header file is:
//Included libraries
#include <iostream>
#include <cstdlib>

//Macroguard
#ifndef NODE_H
#define NODE_H

//Namespace
namespace node_class
{
	class Node
	{
		
	public:
	
		typedef double value_type;
  		//Constructor
  		Node(const value_type& initialData = value_type(), Node* initialLink = NULL, int fieldCount = 0);
		
		//Functions to set data and link fields
		void setData(const value_type& newData);
			
		void setArray(value_type newArray[] , int fieldEntry);		
			
		void setLink(Node* newLink);
		
		//Functions to retrieve data	
		value_type getData();
		
		value_type getArrayData(int index);
		
		//Functions to retrieve current link
		const Node* link() const;

		Node* link();	

    private:
    
    	//private member variables
		value_type data;
		
		Node *next;

		int fieldCount;
		
		value_type fieldArray[];
	};

}

#endif




I think the problem is coming from these classes, but I don't know where. I'm attaching the sample text file that is read in.
I execute it by using a makefile, and run by using the command line; typing ./p8a numbers.txt to run the program. If anyone could help me out and see where I'm going wrong, I would be very grateful. Thanks in advance.

Attached File(s)



Is This A Good Question/Topic? 0
  • +

Replies To: Strange output from linked list

#2 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 378
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

Re: Strange output from linked list

Posted 15 May 2010 - 07:06 PM

That shouldn't compile. You are using some sort of compiler that has its own custom extensions that allows arrays to be declared with a non-constant value.

That is on line 73 of the main file.

I think something is getting corrupted somewhere though. The program prints out everything when I debug it but it fails at the end.

*EDIT*

While digging through this a little more to figure out what "value_type" is I find that you put a typedef
typedef double value_type;

DO NOT DO THAT! It makes debugging total hell. The point is to write clear, concise code. Not a jumble of typedefs that make it look like crap

*EDIT 2*
Now I see why you used the typedef but that isn't the correct way to do things. Look up 'templates'. That is the correct way to use different data types.

This post has been edited by eker676: 15 May 2010 - 07:19 PM

Was This Post Helpful? 1
  • +
  • -

#3 n8wxs  Icon User is offline

  • --... ...-- -.. . -. ---.. .-- -..- ...
  • member icon

Reputation: 971
  • View blog
  • Posts: 3,878
  • Joined: 07-January 08

Re: Strange output from linked list

Posted 15 May 2010 - 07:22 PM

This array

Node::value_type fieldArray[maxField];



has a size of zero. It is created at compile time. You need to dynamically allocate the array based on the value fieldCount
Was This Post Helpful? 0
  • +
  • -

#4 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 378
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

Re: Strange output from linked list

Posted 15 May 2010 - 07:26 PM

This code needs some serious working over before your going to get it to work. You need to simplify.
Was This Post Helpful? 0
  • +
  • -

#5 jayd  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 13
  • Joined: 18-March 10

Re: Strange output from linked list

Posted 15 May 2010 - 10:08 PM

Hi all, thanks for all the help - I got it working for now by declaring the array as
value_type fieldArray[100000]; 
in the Node header file - not the most elegant solution, but it'll do for the time being.
Was This Post Helpful? 0
  • +
  • -

#6 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 275
  • View blog
  • Posts: 1,764
  • Joined: 20-September 08

Re: Strange output from linked list

Posted 15 May 2010 - 10:45 PM

As already suggested above ... a dynamic array (class) (or just use the STL vector) to hold your data at each node

And you might also like to see a template class example ... (there are several here at DIC) ...

http://www.dreaminco...snippet2617.htm
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1