Problem Creating Linked List in Function

Hey guys, I am currently trying to get my program to implement a linked list by invoking a function, but garbage is always thrown out whenever I execute it. Here is a link describing more of my programming project (scroll down a bit):

Setting String equal to char array?

I have tried debugging, to no avail, I cannot figure out why it is feeding me garbage. I made a similar program which inserted and deleted nodes via functions and it had no problem. I have copied that method and for some reason this program messes up.

Here is my code:

Code:

#include <iostream>

using namespace std;

struct node
{
float num;
char opr;
char type;
node* next;
};

void printList(const node*);
//entry* insert(int n, node* h);
//entry* deleteNode(int n, node* h);
//entry* PQInit(entry* h, entry* PQh);
float arrayToFloat(char part[]);
node* tempArray(node* head, char string[], char part[], int flag, int stringFlag);

int main()
{
node *temp = 0, *head = 0;//starts out empty
node *PQt = 0, *PQh = 0;//Polish queue
//float fltval;
int j, n = 0, flag, count = 0, stringFlag = 0;
char string[80];

	cout << "Enter an algebraic equation in reverse polish notation: \n";
	cin.getline(string, 80);

	cout << "Output from func arrayToFloat:\n";
	while(string[n] != '\0')
	{
	char part[15] = {'O'};

		for(j = 0, flag = 0; (string[n] != ' ') && (string[n] != '\0'); j++, n++) 
		{
			part[j] = string[n];
			if(!isdigit(part[j]))//if character
			{
				flag = 1;
			}//if
		}//for
		n++;

		if(string[n] != '\0')
			stringFlag = 1;
		else
			stringFlag = 0;


		head = new node;
		head = tempArray(head, string, part, flag, stringFlag);


	}//while

	//PQh = PQInit(head, PQh);
	cout << "Output from linked list:\n";
	printList(head);

	//creating PQ stack from initial array
	while(head != 0)
	{
		PQh = new node;
		if(head->type == 'N')
		{
			PQh->num = head->num;
			PQh->type = 'N';
			PQh->next = PQt;
			PQt = PQh;
		}//if
		else
		{
			PQh->opr = head->opr;
			PQh->type = 'O';
			PQh->next = PQt;
			PQt = PQh;
		}//else

		head = head->next;
	}//while

	cout << "Output from PQ: \n";

	printList(PQh);

	return 0;
}//main

/***************************************/
//Prints list of Nodes

void printList(const node* pointer)
{
	while(pointer != 0)
	{
		if(pointer->type == 'N')
			cout << pointer->num << " ";
		else
			cout << pointer->opr << " ";

		pointer = pointer->next;
	}//while
	cout << endl;

}//printList

/****************************************/
//Converts an array of ints to a float value

float arrayToFloat(char part[])
{
int L = 0, i, j;
float val = 0, value[15] = {0};
float valtab[5] = {1, 10, 100, 1000, 10000};
//                 1   2   3     4     5

	for(i = 0; part[i]; i++)
	{
		value[i] = part[i] - '0';//converting to int from char	
	}//for
	
	L = strlen(part);
	for(i = 0, j = L - 1; i < L; i++, j--)
	{
		val = val + (value[i] * valtab[j]);
	}//for

	return val;
}//arrayToFloat

/******************************************/
//Initializes PQ

node* tempArray(node* head, char string[], char part[], int flag, int stringFlag)
{
float fltval;
node* temp = 0;
node* h = head;

		if(flag == 0)//if part consists of int
		{
			if(stringFlag == 1)
			{
				fltval = arrayToFloat(part);//converting array based number to float
				cout << fltval << endl;

				//h = new node;
				h->num = fltval;
				h->type = 'N';
				h->next = temp;
				temp = h;
			}//if
		}//if
		else
		{
			if(stringFlag == 0)
			{
				//h = new node;
				h->opr = part[0];
				h->type = 'O';
				h->next = temp;
				temp = h;
			}//if
		}//else

		return h;
	
}//tempArray

Thanks in advance for any help!

I'm not sure what your problem with the linked list is, but here's a little function that does string_to_float a bit better than your function:

Code:

float str_to_float(char *s)
{
  float f = 0.0f;
  int dot = 0;
  float mul = 0.1f;
  float neg = 1.0f;
  if (*s == '-') {
    neg = -1.0f;
    s++;
  }
  for(;;) {
    // Check for end of string first. 
    // Sorry, no error checking, empty string => 0.0
    if (!*s) 
      return f * neg;

    if (*s == '.') {
      s++;
      dot = 1;
    } else {
      // Should check if the "digit" is really a digit!
      int c = *s - '0';
      s++;
      if (!dot) {
	f *= 10.0f;
	f += c;
      } else {
	f += c * mul;
	mul /= 10.0f;
      }
    }
  }
}

It doesn't take "e{+,-}number" format, so you can't write 1.14e-3, you'd have to write 0.00114. And there's no checking if the number is actually "a number", so 3B41 would make some "intersting" value. I'll leave that for you to do.

[I just wrote this, and I've only given it some testing, but I think it's OK]

--
Mats

> head = new node;
> head = tempArray(head, string, part, flag, stringFlag);
After the first line above head no longer points to the start of the list. It looks like you're trying to add a node to the front of the list, so in tempArray() you'd need to create a new node, then point its next member to either (1) null if head is null or (2) head if head is not null. Then simply return the new node, and it would become head.

> char part[15] = {'O'};
This should be:

Code:

	char part[15] = {'\0'};

This letter O does not equal zero (0).

Originally Posted by swoopy

> head = new node;
> head = tempArray(head, string, part, flag, stringFlag);
After the first line above head no longer points to the start of the list. It looks like you're trying to add a node to the front of the list, so in tempArray() you'd need to create a new node, then point its next member to either (1) null if head is null or (2) head if head is not null. Then simply return the new node, and it would become head.

> char part[15] = {'O'};
This should be:

Code:

	char part[15] = {'\0'};

This letter O does not equal zero (0).

Haha, yeah I just wanted to initialize the string to something at first, not necessarily NULL. I modified the code a bit in order to see if it would get fixed, I should have left it like this:

Code:

...
		else
			stringFlag = 0;


		
		head = tempArray(head, string, part, flag, stringFlag);


	}//while...

And in the function:

Code:

node* tempArray(node* head, char string[], char part[], int flag, int stringFlag)
{
float fltval;
node* temp = 0;
node* h = head;

		if(flag == 0)//if part consists of int
		{
			if(stringFlag == 1)
			{
				fltval = arrayToFloat(part);//converting array based number to float
				cout << fltval << endl;

				h = new node;
				h->num = fltval;
				h->type = 'N';
				h->next = temp;
				temp = h;
			}//if
		}//if
		else
		{
			if(stringFlag == 0)
			{
				h = new node;
				h->opr = part[0];
				h->type = 'O';
				h->next = temp;
				temp = h;
			}//if
		}//else

		return h;
	
}//tempArray

This is what you were telling me to do right? Sorry if I misunderstood you, but doing it this way still doesn't work. Thanks for the help guys.

This code looks "wrong" to me:

Code:

node* tempArray(node* head, char string[], char part[], int flag, int stringFlag)
{
  float fltval;
  node* temp = 0;

This sets temp to 0 every time you enter the function - is that really what you want?

Code:

  node* h = head;

h points to the same as head - that's fine, but why not just type the extra three letters in each place you use h below? - or call "head" h in the function header, perhaps?

Code:

  if(flag == 0)//if part consists of int
    {
      if(stringFlag == 1)
	{
	  fltval = arrayToFloat(part);//converting array based number to float
	  cout << fltval << endl;

	  //h = new node;
	  h->num = fltval;
	  h->type = 'N';
	  h->next = temp;
	  temp = h;
	}//if
    }//if
  else
    {
      if(stringFlag == 0)
	{
	  //h = new node;
	  h->opr = part[0];
	  h->type = 'O';
	  h->next = temp;
	  temp = h;
	}//if
    }//else

  return h;
	
}//tempArray

This doesn't explain why your code isn't working, but I'm pretty sure it's not what you wanted to do... I'll keep looking.

--
Mats

Wow dude, thanks for pointing that out. I didn't notice that temp resets, that is part of the problem for sure. I set head to h because I was initially designing the function by looking off of another function which had me do it. I did it this way so that if I needed to "cheat" the system by changing the list w/o changing the head pointer, I could.

>> [I just wrote this, and I've only given it some testing, but I think it's OK]

Stringstreams, lexical_cast, or some other standard method is what should be used unless it is being done as a learning exercise. Either way, there's no reason to use somebody else's handwritten version, especially when it hasn't been thoroughly tested and debugged.

Here is an update of my code:

Code:

#include <iostream>

using namespace std;

struct node
{
float num;
char opr;
char type;
node* next;
};

void printList(const node*);
//entry* insert(int n, node* h);
//entry* deleteNode(int n, node* h);
//entry* PQInit(entry* h, entry* PQh);
float arrayToFloat(char part[]);
node* tempArray(node* head, node* temp, char string[], char part[], int flag, int stringFlag);

int main()
{
node *temp = 0, *head = 0;//starts out empty
node *PQt = 0, *PQh = 0;//Polish queue
//float fltval;
int j, n = 0, flag, count = 0, stringFlag = 0;
char string[80];

	cout << "Enter an algebraic equation in reverse polish notation: \n";
	cin.getline(string, 80);

	cout << "Output from func arrayToFloat:\n";
	while(string[n] != '\0')
	{
	char part[15] = {'\0'};

		for(j = 0, flag = 0; (string[n] != ' ') && (string[n] != '\0'); j++, n++) 
		{
			part[j] = string[n];
			if(!isdigit(part[j]))//if character
			{
				flag = 1;
			}//if
		}//for
		n++;

		if(string[n] != '\0')
			stringFlag = 1;
		else
			stringFlag = 0;


		
		head = tempArray(head, temp, string, part, flag, stringFlag);


	}//while

	//PQh = PQInit(head, PQh);
	cout << "Output from linked list:\n";
	printList(head);

	//creating PQ stack from initial array
	while(head != 0)
	{
		PQh = new node;
		if(head->type == 'N')
		{
			PQh->num = head->num;
			PQh->type = 'N';
			PQh->next = PQt;
			PQt = PQh;
		}//if
		else
		{
			PQh->opr = head->opr;
			PQh->type = 'O';
			PQh->next = PQt;
			PQt = PQh;
		}//else

		head = head->next;
	}//while

	cout << "Output from PQ: \n";

	printList(PQh);

	return 0;
}//main

/***************************************/
//Prints list of Nodes

void printList(const node* pointer)
{
	while(pointer != 0)
	{
		if(pointer->type == 'N')
			cout << pointer->num << " ";
		else
			cout << pointer->opr << " ";

		pointer = pointer->next;
	}//while
	cout << endl;

}//printList

/****************************************/
//Converts an array of ints to a float value

float arrayToFloat(char part[])
{
int L = 0, i, j;
float val = 0, value[15] = {0};
float valtab[5] = {1, 10, 100, 1000, 10000};
//                 1   2   3     4     5

	for(i = 0; part[i]; i++)
	{
		value[i] = part[i] - '0';//converting to int from char	
	}//for
	
	L = strlen(part);
	for(i = 0, j = L - 1; i < L; i++, j--)
	{
		val = val + (value[i] * valtab[j]);
	}//for

	return val;
}//arrayToFloat

/******************************************/
//Initializes PQ

node* tempArray(node* head, node* temp, char string[], char part[], int flag, int stringFlag)
{
float fltval;
node* h = head;

		if(flag == 0)//if part consists of int
		{
			if(stringFlag == 1)
			{
				fltval = arrayToFloat(part);//converting array based number to float
				cout << fltval << endl;

				h = new node;
				h->num = fltval;
				h->type = 'N';
				h->next = temp;
				temp = h;
			}//if
		}//if
		else
		{
			if(stringFlag == 0)
			{
				h = new node;
				h->opr = part[0];
				h->type = 'O';
				h->next = temp;
				temp = h;
			}//if
		}//else

		return h;
	
}//tempArray

It still has the problems from before... But I solved the issue matsp pointed out. Thanks for the input.

Originally Posted by Daved

>> [I just wrote this, and I've only given it some testing, but I think it's OK]

Stringstreams, lexical_cast, or some other standard method is what should be used unless it is being done as a learning exercise. Either way, there's no reason to use somebody else's handwritten version, especially when it hasn't been thoroughly tested and debugged.

Don't worry I am going to stick to my way for now, it is good enough for my program's needs. Yeah, I am writing this all out for practice and to get a better knowledge of how all this good stuff works. Thanks for the concern.

>Haha, yeah I just wanted to initialize the string to something at first, not necessarily NULL.
Yeah, I later realized you might actually mean O. Change it back if you prefer.

>node* tempArray(node* head, node* temp, char string[], char part[], int flag, int stringFlag)
I would take out temp, it's not needed.

>node* h = head;
Just make this:

Code:

node* h;

> h->next = temp;
Make both instances of this:

Code:

				h->next = head;

> temp = h;
Take both instances of this line out.

Swoopy I did as you said:

Code:

/******************************************/
//Initializes PQ

node* tempArray(node* head, node* temp, char string[], char part[], int flag, int stringFlag)
{
float fltval;
node* h = head;
node* ptr = NULL;

		if(flag == 0)//if part consists of int
		{
			if(stringFlag == 1)
			{
				fltval = arrayToFloat(part);//converting array based number to float
				cout << fltval << endl;

				h = new node;
				h->num = fltval;
				h->type = 'N';
				h->next = temp;
				temp = h;
			}//if
		}//if
		else
		{
			if(stringFlag == 0)
			{
				h = new node;
				h->opr = part[0];
				h->type = 'O';
				h->next = temp;
				temp = h;
			}//if
		}//else

		if(h == NULL)
			ptr->next = NULL;
		else if(h != NULL)
			ptr->next = h;

		return ptr;
	
}//tempArray

I didn't notice until I wrote it, that it makes the problem worse. Because the new ptr only has a next value and when other functions access it, they look for a value in it, which is garbage, so the program crashes. I think you noticed this too since you deleted your post just recently... haha. All good man, I am likely to do the same thing. Nonetheless thanks for the comments and responses .

I agree, if a "standard function" works, use it. I was just showing that it can be done "better" than using a lot of tables - the original code doesn't even ALMOST do what it says it does (yes, it's a float, but it doesn't handle decimal points, negative numbers, large numbers [beyond 90000], etc, etc).

I also DID point out that the code wasn't perfect - I should of course have pointed out some of the other methods to do the same thing in a standardized way.

However, I have now "hacked" the temparray code so that it does SOMETHING sensible, it also assumes the following change at the point of call:

don't do "head = new node"

Code:

node* tempArray(node* head, char string[], char part[], int flag, int stringFlag)
{
  float fltval;
  node *temp = new node;

  if(flag == 0) //if part consists of int
    {
      if(stringFlag == 1)
	{
	  fltval = arrayToFloat(part);//converting array based number to float
	  cout << fltval << endl;

	  temp->num = fltval;
	  temp->type = 'N';
	  temp->next = head;
	}
    }
  else
    {
      if(stringFlag == 0)
	{
	  temp->opr = part[0];
	  temp->type = 'O';
	  temp->next = head;
	}
    }

  return temp;
	
}//tempArray

Note that this doesn't take into account passing temp in as a parameter - nor should it need to.

You may find that this list is "backwards" compared to what you want - since I don't know what you want to do further down the line, I can't say for sure.

--
Mats

You may also want to move your "n++" so that it is only done when you haven't found the end of the string - I found by running your code that it goes on past the end of the string and picks up all sorts of garbage:

Code:

      for(j = 0, flag = 0; (string[n] != ' ') && (string[n] != '\0'); j++, n++) 
	{
	  part[j] = string[n];
	  if(!isdigit(part[j]))//if character
	    {
	      flag = 1;
	    }//if
	}//for
// don't do n++ here
      if(string[n] != '\0') {
	stringFlag = 1;
	n++;   // do it here instead
      } else
	stringFlag = 0;

--
Mats

>I think you noticed this too since you deleted your post just recently... haha.
Yeah, I realized that regardless of whether head was null or not, setting the new node's next member to head would be the same thing. So all you would need is:

Code:

h->next = head;
.
.
return h;

h being whatever you which to call the newly created node.

Originally Posted by swoopy

>Haha, yeah I just wanted to initialize the string to something at first, not necessarily NULL.
Yeah, I later realized you might actually mean O. Change it back if you prefer.

>node* tempArray(node* head, node* temp, char string[], char part[], int flag, int stringFlag)
I would take out temp, it's not needed.

>node* h = head;
Just make this:

Code:

node* h;

> h->next = temp;
Make both instances of this:

Code:

				h->next = head;

> temp = h;
Take both instances of this line out.

Nice man, that makes my code work better, but now I get garbage on the end. It is able to print out only one node and then garbage on the end. If I insert more than one entry I get a fatal error. What you said did improve it. Here is the update:

Code:

/******************************************/
//Initializes PQ

node* tempArray(node* head, char string[], char part[], int flag, int stringFlag)
{
float fltval;
node* h;


		if(flag == 0)//if part consists of int
		{
			if(stringFlag == 1)
			{
				fltval = arrayToFloat(part);//converting array based number to float
				cout << fltval << endl;

				h = new node;
				h->num = fltval;
				h->type = 'N';
				h->next = head;
				
			}//if
		}//if
		else
		{
			if(stringFlag == 0)
			{
				h = new node;
				h->opr = part[0];
				h->type = 'O';
				h->next = head;
				
			}//if
		}//else

	
		return h;
	
}//tempArray