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):

http://cboard.cprogramming.com/showthread.php?t=91981

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

Quote:

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.

Quote:

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.

Quote:

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

Quote:

Originally Posted by Stunner

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:

Yes, you're going past the end of the string when you're incrementing "n++" after the for-loop in the main. So if you find a nul-character in the string, you go past it, and continue until the next nul, which may be overflowing all sorts of other buffers and cause bad thing to happen. See one of my previous posts.

--
Mats

Matsp, I took both of your suggestions and the first one made it respond nearly exactly the same as Swoopy's version. The second part however made it crash worse than originally.
n should be incremented no matter what so that it skips over a space if there is one ( there will be one besides NULL).

But you are right the n++ needs to be moved to after the if else statement. Here is my entire 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] = {'\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')//I dont understand what these if elses are checking for... { stringFlag = 1; //n++; }//if else stringFlag = 0; n++; 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 = 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

Also another thing, while making modifications, I noticed the if else statement:

Code:

if(string[n] != '\0')//I dont understand what these if elses are checking for... { stringFlag = 1; //n++; }//if else stringFlag = 0;

And it is not making any sense to me whatsoever(yeah I know its sad, I wrote it, need better comments), supposedly it is supposed to detect if it is a number or an operator. If anyone can save me from my stupidity, that would be great.

I think that if else statement is the problem, working on it...

HAH! That WAS the problem! I'm so dumb, when I converted it, I did it wrong which caused the problems... sorry guys. Matsp, good call n the n++ counter fixed a problem and now it runs like its supposed to:

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] = {'\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 if(string[n] != '\0') n++; if(flag == 0) { stringFlag = 1; }//if else stringFlag = 0; 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 = 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; }//if }//if else { if(stringFlag == 0) { temp->opr = part[0]; temp->type = 'O'; temp->next = head; } }//else return temp; }//tempArray

Thanks for all your help guys, you guys are awesome. Sorry bout that stupid error.

>Thanks for all your help guys, you guys are awesome. Sorry bout that stupid error.
Whew, glad you got it working. :)

Code:

if(flag == 0) { stringFlag = 1; }//if else stringFlag = 0;

This code snippet is EXACTLY the same as "stringFlag = !flag". So why not simplify your tempArray function to only use the one flag - not using two different ones that are always the opposite of each other.

--
Mats

Quote:

Originally Posted by matsp

Code:

if(flag == 0) { stringFlag = 1; }//if else stringFlag = 0;

This code snippet is EXACTLY the same as "stringFlag = !flag". So why not simplify your tempArray function to only use the one flag - not using two different ones that are always the opposite of each other.

--
Mats

Haha, true, thanks for mentioning that. Long day, not planning on working on it anymore for now. Thanks for all the help.