Programming Forums > Application Development > C++

Jessehk · Oct 1st, 2005, 11:36 PM

I figure knowing how to program a linked-list using a class would be a good exercise, so I attempted to code one with the following code:

(Toggle Plain Text)

//numbers.cpp -- implementing a linked-list with classes

#include <iostream>

using namespace std;

class Numbers
{
	private:
		struct Node
		{
			int value;
			Node *nexts;
		};
		Node *firsts, *currents, *news;
	public:
		Numbers();
		bool appendNumber(int);
		//bool insertNumber(int, int);
		bool showNumber(int);
};

Numbers::Numbers()
{
	firsts = currents = news = 0;
}

bool Numbers::appendNumber(int x)
{
	if(firsts == 0) {
		firsts = new Node;
		firsts->value = x;
		firsts->nexts = 0;
	
		return true;
	}

	else {
			currents = firsts;
		do {
			currents = currents->nexts;
		}while(currents->nexts != 0);

		news = new Node;
		
		currents->nexts = news;
		news = currents;
		currents->value = x;
		currents->nexts = 0;
	}

	return true;
}

bool Numbers::showNumber(int x)
{
	if(firsts == 0)
		return false;

	currents = firsts;

	for(int i = 0; i < x; i++)
		currents = currents->nexts;

	cout << currents->value;

	return true;
}

int main()
{
	Numbers numbs1;
	
	numbs1.appendNumber(4);
	numbs1.appendNumber(5);

	numbs1.showNumber(1);
	numbs1.showNumber(2);

	return 0;
}

the only output I get is

Quote:

Segmentation fault

I have checked over this quite a bit and I can't figure out where I have gone wrong.

Any help would be appreciated; Thanks

EDIT: I just ran it through gdb (which I have very little expirience using), and apparently, line 42:

(Toggle Plain Text)

}while(currents->nexts != 0);

is a problem.

Looks fine to me

...

L7Sqr · Oct 2nd, 2005, 12:13 AM

Quote:

do {
currents = currents->nexts;
}while(currents->nexts != 0);

Consider this for a moment...
You are telling the computer to move to the next node (regardless of it validity) and then (without checking the validity) dereference that node.
When that node is NULL, you will have trouble.
My suggestion to you is to try to implement error checking in your code.
I would prefer to write this as

(Toggle Plain Text)

if (currents) {
   while (currents->next) 
      currents = currents->next;
} else {
   //handle the NULL case
}

new can fail, and should be checked accordingly.
Any time a pointer is dereferenced, it should have been checked for NULL be fore the dereference.

(Toggle Plain Text)

for(int i = 0; i < x; i++)
		currents = currents->nexts;

Lines like that will creep up on you. You may only ever expect to pass a value that is in the correct range, but what happens if you forget the range, or pass an invalid range?

Jessehk · Oct 2nd, 2005, 12:16 AM

Quote:

Originally Posted by L7Sqr

Consider this for a moment...
You are telling the computer to move to the next node (regardless of it validity) and then (without checking the validity) dereference that node.
When that node is NULL, you will have trouble.
My suggestion to you is to try to implement error checking in your code.
I would prefer to write this as

(Toggle Plain Text)

if (currents) {
   while (currents->next) 
      currents = currents->next;
} else {
   //handle the NULL case
}

new can fail, and should be checked accordingly.
Any time a pointer is dereferenced, it should have been checked for NULL be fore the dereference.

(Toggle Plain Text)

for(int i = 0; i < x; i++)
		currents = currents->nexts;

Lines like that will creep up on you. You may only ever expect to pass a value that is in the correct range, but what happens if you forget the range, or pass an invalid range?

Thanks for the reply

I don't know if this is good practise, but often I will code a very simple, check-free version of a program to test the basic theory behind it. Once that is confirmed working, I add in bounds-checking ( correct term? ), and all the "padding".

I will add the changes you mentioned

Jessehk · Oct 2nd, 2005, 12:24 AM

I added in a few changes:

(Toggle Plain Text)

//numbers.cpp -- implementing a linked-list with classes

#include <iostream>

using namespace std;

class Numbers
{
	private:
		struct Node
		{
			int value;
			Node *nexts;
		};
		Node *firsts, *currents, *news;
	public:
		Numbers();
		bool appendNumber(int);
		//bool insertNumber(int, int);
		bool showNumber(int);
		void show();
};

Numbers::Numbers()
{
	firsts = currents = news = 0;
}

bool Numbers::appendNumber(int x)
{
	if(firsts == 0) {
		firsts = new Node;
		firsts->value = x;
		firsts->nexts = 0;
	
		return true;
	}

	else {
			currents = firsts;
		while(currents->nexts)
			currents = currents->nexts;

		news = new Node;
		
		currents->nexts = news;
		news = currents;
		currents->value = x;
		currents->nexts = 0;
	}

	return true;
}

/*bool Numbers::showNumber(int x)
{
	if(firsts == 0)
		return false;

	currents = firsts;

	for(int i = 0; i < x - 2; i++)
		currents = currents->nexts;

	cout << currents->value;

	return true;
}*/

void Numbers::show()
{
	currents = firsts;
	while(currents->nexts != 0) {
		cout << currents->value << endl;
		currents = currents->nexts;
	}
}

int main()
{
	Numbers numbs1;
	
	numbs1.appendNumber(4);
	numbs1.appendNumber(5);

	//numbs1.showNumber(1);
	cout << endl;
	//numbs1.showNumber(2);
	numbs1.show();

	return 0;
}

this time, I don't get a segmentation fault, but I just get 2 lines of blank output.

I don't understand why this is occuring.

InfoGeek · Oct 2nd, 2005, 12:32 AM

Also use NULL instead of 0 in case you want a NULL pointer.
here 's a recent discussion. and i believe Scorpions4ever is right there.

InfoGeek · Oct 2nd, 2005, 12:39 AM

Quote:

(Toggle Plain Text)

              while(currents->nexts)
			currents = currents->nexts;

		news = new Node;
		
		currents->nexts = news;

after your while loop finishes, the current pointer points to NULL. and then in the next line you are trying to use currents->nexts. I think you're unlucky this time as you didn't get a seg fault.

Edit: you need to use another pointer that stays a step back to the currents pointer, that way when your while loop finishes, that pointer points to the last element in your list.

(Toggle Plain Text)

currents=start;
while(currents->nexts)
{
    save=currents;
    currents = currents->nexts;
}

L7Sqr · Oct 2nd, 2005, 12:50 AM

Quote:

Originally Posted by InfoGeek

after your while loop finishes, the current pointer point to NULL

No. currents->nexts points to NULL, that is the terminating case.

@JessehK
Your print statement is never being reached.
You are doing some funky stuff in your appendnumber function...
You are always checking currents->nexts after assigning it to firsts, whos nexts is assigned null right before. So currents is always pointing to firsts.
You update the value by assigning news to currents->nexts and assign the news to the head, and then the currents->nexts to 0 (What happened to news??)

Now in your show function, you assign currents to firsts whos next is already determined to be NULL and check for currents->nexts to be non-null. This will always fail. Try putting a cout statement right before you test for while (currents->nexts != 0)...I bet you get output. If you put cout statements after the while loop, you will also get output.

Look into these problems and see where you get.

InfoGeek · Oct 2nd, 2005, 12:55 AM

Quote:

Originally Posted by L7Sqr

No. currents->nexts points to NULL, that is the terminating case.

sorry, didn't see it carefully. thought it was while(current)

Jessehk · Oct 2nd, 2005, 1:00 AM

I fixed it after changing a few of the do-while loops.

Works perfectly, now I just need to add in the bulk that you were refering to L7sqr

.

here is the code

(Toggle Plain Text)

//numbers.cpp -- implementing a linked-list with classes

#include <iostream>

using namespace std;

class Numbers
{
	private:
		struct Node
		{
			int value;
			Node *nexts;
		};
		Node *firsts, *temps, *news, *currents;
	public:
		Numbers();
		bool appendNumber(int);
		void insertNumber(int, int);
		void showNumber(int);
		void show();
};

Numbers::Numbers()
{
	firsts = /*lasts =*/ news = currents = NULL;
}

bool Numbers::appendNumber(int x)
{

	news = new Node;
	news->value = x;
	
	if(firsts == NULL) {
		firsts = news;
		firsts->nexts = NULL;
		
		return true;
	}


	else {
		currents = firsts;
		while(currents->nexts != NULL) {
			currents = currents->nexts;
		}

		currents->nexts = news;
		currents = news;
		currents->nexts = NULL;
	}

	return true;
}

void Numbers::showNumber(int x)
{
	//if(firsts == 0)
		//return false;

	currents = firsts;

	for(int i = 0; i < x - 1 ; i++)
		currents = currents->nexts;

	cout << currents->value;

}

void Numbers::insertNumber(int x, int y)
{
	currents = firsts;
	news = new Node;
	news->value = x;

	for(int i = 0; i < y - 2; i++) {
		currents = currents->nexts;
	}

	temps = currents->nexts;
	currents->nexts = news;
	news->nexts = temps;
}

void Numbers::show()
{
	currents = firsts;
	do {
		cout << currents->value << endl;
	}while((currents = currents->nexts) != NULL);
}

int main()
{
	Numbers numbs1;
	
	numbs1.appendNumber(1);
	numbs1.appendNumber(3);
	numbs1.appendNumber(5);
	numbs1.appendNumber(7);

	
	cout << endl;
	cout << endl;
	
	numbs1.show();
	numbs1.insertNumber(6, 4);
	cout << endl;
	numbs1.show();
	cout << endl;
	cout << "4th Node = ";
	numbs1.showNumber(4);
	cout << endl;
	
	return 0;
}

and the output:

Quote:

1
3
5
7

1
3
5
6
7

4th Node = 6

Thanks again for all the advice

L7Sqr · Oct 2nd, 2005, 1:08 AM

Quote:

Originally Posted by InfoGeek

sorry, didn't see it carefully

No need for appology.
To tell you the truth, with all the currents', nexts', firsts' and lasts' I was kinds spinning myself. It's hard to pluralise items in a sentence that contains singular items with plural spellings.
Rereading my post, I'm not sure how any of that helped

Oct 2nd, 2005, 12:24 AM	#4
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 648 Rep Power: 4	I added in a few changes: (Toggle Plain Text) //numbers.cpp -- implementing a linked-list with classes #include <iostream> using namespace std; class Numbers { private: struct Node { int value; Node nexts; }; Node firsts, currents, news; public: Numbers(); bool appendNumber(int); //bool insertNumber(int, int); bool showNumber(int); void show(); }; Numbers::Numbers() { firsts = currents = news = 0; } bool Numbers::appendNumber(int x) { if(firsts == 0) { firsts = new Node; firsts->value = x; firsts->nexts = 0; return true; } else { currents = firsts; while(currents->nexts) currents = currents->nexts; news = new Node; currents->nexts = news; news = currents; currents->value = x; currents->nexts = 0; } return true; } /bool Numbers::showNumber(int x) { if(firsts == 0) return false; currents = firsts; for(int i = 0; i < x - 2; i++) currents = currents->nexts; cout << currents->value; return true; }/ void Numbers::show() { currents = firsts; while(currents->nexts != 0) { cout << currents->value << endl; currents = currents->nexts; } } int main() { Numbers numbs1; numbs1.appendNumber(4); numbs1.appendNumber(5); //numbs1.showNumber(1); cout << endl; //numbs1.showNumber(2); numbs1.show(); return 0; } //numbers.cpp -- implementing a linked-list with classes #include <iostream> using namespace std; class Numbers { private: struct Node { int value; Node nexts; }; Node firsts, currents, news; public: Numbers(); bool appendNumber(int); //bool insertNumber(int, int); bool showNumber(int); void show(); }; Numbers::Numbers() { firsts = currents = news = 0; } bool Numbers::appendNumber(int x) { if(firsts == 0) { firsts = new Node; firsts->value = x; firsts->nexts = 0; return true; } else { currents = firsts; while(currents->nexts) currents = currents->nexts; news = new Node; currents->nexts = news; news = currents; currents->value = x; currents->nexts = 0; } return true; } /bool Numbers::showNumber(int x) { if(firsts == 0) return false; currents = firsts; for(int i = 0; i < x - 2; i++) currents = currents->nexts; cout << currents->value; return true; }/ void Numbers::show() { currents = firsts; while(currents->nexts != 0) { cout << currents->value << endl; currents = currents->nexts; } } int main() { Numbers numbs1; numbs1.appendNumber(4); numbs1.appendNumber(5); //numbs1.showNumber(1); cout << endl; //numbs1.showNumber(2); numbs1.show(); return 0; } this time, I don't get a segmentation fault, but I just get 2 lines of blank output. I don't understand why this is occuring. __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Oct 2nd, 2005, 12:32 AM	#5
InfoGeek Professional Programmer Join Date: Jun 2005 Location: India, The great. Posts: 435 Rep Power: 4	Also use NULL instead of 0 in case you want a NULL pointer. here 's a recent discussion. and i believe Scorpions4ever is right there. __________________ PFO - My daily dose of technology.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

Getting a seg. fault with a simple linked-list