468,457 Members | 1,643 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,457 developers. It's quick & easy.

LinkedList with Nodes

Hi,

i am currently working on creating a LinkedList, for that I using a
predefined Node-class which offers a LinkedList Toolkit to manipulate
the Linked List (http://www.cs.colorado.edu/~main/chapter5/node1.h). I
develop a Squence-Class which should store a sequence of numbers in a
LinkedList.

My header file of sequence looks like this, respectively the methods
and variables:
Expand|Select|Wrap|Line Numbers
  1. public:
  2. // TYPEDEFS and MEMBER CONSTANTS
  3. typedef double value_type;
  4. typedef std::size_t size_type;
  5. // CONSTRUCTORS and DESTRUCTOR
  6. sequence( );
  7. sequence(const sequence& source);
  8. ~sequence( );
  9. // MODIFICATION MEMBER FUNCTIONS
  10. void start( );
  11. void advance( );
  12. void insert(const value_type& entry);
  13. void attach(const value_type& entry);
  14. void operator =(const sequence& source);
  15. void remove_current( );
  16. // CONSTANT MEMBER FUNCTIONS
  17. size_type size( ) const { return many_nodes; }
  18. bool is_item( ) const { return (cursor != NULL); }
  19. value_type current( ) const;
  20. private:
  21. node *head_ptr;
  22. node *tail_ptr;
  23. node *cursor;
  24. node *precursor;
  25. size_type many_nodes;
  26.  
I already implemented the two constructors, the desctructor, the
advance and start-method.
Expand|Select|Wrap|Line Numbers
  1. sequence::sequence()
  2. {
  3. head_ptr = NULL;
  4. tail_ptr = NULL;
  5. many_nodes = 0;
  6. }
  7.  
  8. sequence::sequence(const sequence& source)
  9. {
  10. node *tail_ptr;
  11. list_copy(source.head_ptr, head_ptr, tail_ptr);
  12. many_nodes = source.many_nodes;
  13. }
  14.  
  15. sequence::~sequence()
  16. {
  17. list_clear(head_ptr);
  18. many_nodes = 0;
  19. }
  20.  
  21. void sequence::start()
  22. {
  23. cursor = head_ptr;
  24. }
  25.  
  26. void sequence::advance()
  27. {
  28. cursor = cursor->link();
  29. }
  30.  
I hope they are right defined.
Unfortunately I really have problems with the insert-function.
According to the specification the insert function should insert a node
before the node which the current cursor points to. So therefore I have
to point with the precursor to the node before the node the cursor
points to, but I do not understand how i can find out this
position...:((

Does anybody know here how this insert-method could be efficient
defined?

matti

Oct 18 '06 #1
15 4226
On 18 Oct 2006 08:30:36 -0700 in comp.lang.c++, ma****@gmx.at wrote,
>According to the specification the insert function should insert a node
before the node which the current cursor points to. So therefore I have
to point with the precursor to the node before the node the cursor
points to, but I do not understand how i can find out this
position...:((
You get it from the "precursor" of the existing node that you are
inserting before (before clobbering that value with the pointer to
the inserted node!)

Oct 18 '06 #2

Yes I have to let the precursor point to the previous node before the
one to which the cursor pointer points to.

but how can I set the precursor pointer to the previous node - the node
before the node to which the cursor points to?

matti

PS: sorry but I don't understand what do you mean with clobbering,
unfortunately i am not an english native speaker and my dictionary gave
me some strange translations for that word..:-/

Oct 18 '06 #3
On 18 Oct 2006 09:20:09 -0700 in comp.lang.c++, ma****@gmx.at wrote,
>
Yes I have to let the precursor point to the previous node before the
one to which the cursor pointer points to.

but how can I set the precursor pointer to the previous node - the node
before the node to which the cursor points to?
The precursor pointer of the node the cursor points to is what you
need.

The precursor pointers in the nodes of the existing list form a back
pointing chain, that you can follow backwards as far as you need to.
>PS: sorry but I don't understand what do you mean with clobbering,
unfortunately i am not an english native speaker and my dictionary gave
me some strange translations for that word..:-/
Sorry. By that I mean, when you insert the node, you will change
the precursor pointer of the existing node to point to the new node,
but you need to save the old value of the pointer before you change
it. That old value is the one you need to find the previous node.

Yes, it's a strange word. I could not define it myself.

Oct 18 '06 #4


thanks for the explanation...but now I am a little bit confused, every
node in my class has only data field and a pointer to the next node
(regarding the definition and implementation of my node-class i use).

so not every node object has an precursor pointer but only a data field
and a link to the next node....maybe there is some kind of
misunderstanding...?
David Harmon wrote:
On 18 Oct 2006 09:20:09 -0700 in comp.lang.c++, ma****@gmx.at wrote,

Yes I have to let the precursor point to the previous node before the
one to which the cursor pointer points to.

but how can I set the precursor pointer to the previous node - the node
before the node to which the cursor points to?

The precursor pointer of the node the cursor points to is what you
need.

The precursor pointers in the nodes of the existing list form a back
pointing chain, that you can follow backwards as far as you need to.
PS: sorry but I don't understand what do you mean with clobbering,
unfortunately i am not an english native speaker and my dictionary gave
me some strange translations for that word..:-/

Sorry. By that I mean, when you insert the node, you will change
the precursor pointer of the existing node to point to the new node,
but you need to save the old value of the pointer before you change
it. That old value is the one you need to find the previous node.

Yes, it's a strange word. I could not define it myself.
Oct 18 '06 #5
On 18 Oct 2006 09:57:34 -0700 in comp.lang.c++, ma****@gmx.at wrote,
>
thanks for the explanation...but now I am a little bit confused, every
node in my class has only data field and a pointer to the next node
(regarding the definition and implementation of my node-class i use).

so not every node object has an precursor pointer but only a data field
and a link to the next node....maybe there is some kind of
misunderstanding...?
Yes, my misunderstanding. I was thinking that you had a
double-linked list, but really you have a single linked list.

In that case, it would be the precursor field of the list head.
Make sure that you keep the condition that the precursor always
points to the node before the cursor.

Oct 18 '06 #6
ah okay, so i think i have to set the precursor also in the start and
advance method. but i still do not know exactly how i should set the
several pointers when i insert a new node (cursor, precursor, tail_ptr,
head_ptr)

Expand|Select|Wrap|Line Numbers
  1. void sequence::start()
  2. {
  3. cursor = head_ptr;
  4. precursor = head_ptr;
  5. }
  6.  
  7. void sequence::advance()
  8. {
  9. cursor = cursor->link();
  10. precursor = precursor->link();
  11. }
  12.  
  13. void sequence::insert(const value_type& entry)
  14. {
  15. list_head_insert(precursor, entry);
  16.  
  17. precursor->set_link
  18.  
  19. ++many_nodes;
  20. }
  21.  
I hope start and advance is right, i tried it in insert that he should
insert a new node and the precursor points than to this new node but
actually the cursor should then point to the new node. I simple don't
get really through it...? :((

matti

Oct 18 '06 #7
On 18 Oct 2006 11:11:55 -0700 in comp.lang.c++, ma****@gmx.at wrote,
>[code]
void sequence::start()
{
cursor = head_ptr;
precursor = head_ptr;
}
Do not expect the following examples to be exactly right, but
something generally like the way I would go.

void sequence::start()
{
cursor = head_ptr;
precursor = 0;
}
>void sequence::advance()
{
cursor = cursor->link();
precursor = precursor->link();
}
void sequence::advance()
{
precursor = cursor;
cursor = cursor->link();
}
>void sequence::insert(const value_type& entry)
{
list_head_insert(precursor, entry);

precursor->set_link

++many_nodes;
}
void sequence::insert(const value_type& entry)
{
entry.link = cursor;
if (precursor)
precursor->link = &entry;
else
head_ptr = tail_ptr = &entry;

cursor = &entry;
++many_nodes;
}

Write a function that goes through the list and prints all the link
values. Call it after every operation to help see what is actually
happening.

Oct 18 '06 #8

Unfortunately i got a lot of error because of the code lines in the
insert-method. entry is of type double so i cannot call entry.link and
errorso occur for the following lines...:

error C2228: left of '.link' must have class/struct/union
sequenceimpl.cpp(48) : error C2659: '=' : function as left operand
sequenceimpl.cpp(50) : error C2440: '=' : cannot convert from 'const
main_savitch_5::sequence::value_type *__w64 ' to 'main_savitch_5::node
*'
Types pointed to are unrelated; conversion requires
reinterpret_cast, C-style cast or function-style cast
sequenceimpl.cpp(52) : error C2440: '=' : cannot convert from 'const
main_savitch_5::sequence::value_type *__w64 ' to 'main_savitch_5::node
*'
Types pointed to are unrelated; conversion requires
reinterpret_cast, C-style cast or function-style cast

maybe you know why these problems occur...?

matti

Oct 18 '06 #9
On 18 Oct 2006 13:20:18 -0700 in comp.lang.c++, ma****@gmx.at wrote,
>
Unfortunately i got a lot of error because of the code lines in the
insert-method. entry is of type double so i cannot call entry.link and
errorso occur for the following lines...:
Well, I did say you would have to fix it up into actual code.
Instead of entry.link, set the link field of the new node you are
inserting, whatever it is called.

Oct 18 '06 #10

yes that is my real problem...i don't know how to use the certain node,
because I call test.insert(getNumber());

and then I am in within the insert-method with the corresponding
parameter, so how i do not really know how i can assign the pointer to
the real node...? :(

Oct 18 '06 #11
hi,

I implemented insert and attach now and gernally the two functions
work:

Expand|Select|Wrap|Line Numbers
  1. void sequence::start()
  2. {
  3. cursor = head_ptr;
  4. precursor = 0;
  5.  
  6. }
  7.  
  8. void sequence::advance()
  9. {
  10. precursor = cursor;
  11. cursor = cursor->link();
  12.  
  13. }
  14.  
  15. void sequence::insert(const value_type& entry)
  16. {
  17. if(precursor == NULL)
  18. {
  19. list_head_insert(head_ptr, entry);
  20. cursor = head_ptr;
  21. tail_ptr = head_ptr;
  22. }
  23. else
  24. {
  25. list_insert(precursor, entry);
  26. cursor = precursor->link();
  27. }
  28.  
  29. ++many_nodes;
  30. }
  31.  
  32. void sequence::attach(const value_type& entry)
  33. {
  34. if(cursor == NULL)
  35. {
  36. list_head_insert(head_ptr, entry);
  37. cursor = head_ptr;
  38. tail_ptr = head_ptr;
  39. }
  40. else
  41. {
  42. list_insert(cursor, entry);
  43. cursor = cursor->link();
  44. }
  45.  
  46. ++many_nodes;
  47.  
  48. }
  49.  
However there are still errors when I use the testprogram which tests
the boundaries. Does anybody eventually know what is still wrong at
these functions? :(

matti

Oct 19 '06 #12
* ma****@gmx.at:
hi,

I implemented insert and attach now and gernally the two functions
work:

Expand|Select|Wrap|Line Numbers
  1. void sequence::start()
  2. {
  3.         cursor = head_ptr;
  4.         precursor = 0;
  5. }
  6. void sequence::advance()
  7. {
  8.         precursor = cursor;
  9.         cursor = cursor->link();
  10. }
  11. void sequence::insert(const value_type& entry)
  12. {
  13.     if(precursor == NULL)
  14.     {
  15.         list_head_insert(head_ptr, entry);
  16.         cursor = head_ptr;
  17.         tail_ptr = head_ptr;
  18.     }
  19.     else
  20.     {
  21.         list_insert(precursor, entry);
  22.         cursor = precursor->link();
  23.     }
  24.     ++many_nodes;
  25. }
  26. void sequence::attach(const value_type& entry)
  27. {
  28.     if(cursor == NULL)
  29.     {
  30.         list_head_insert(head_ptr, entry);
  31.         cursor = head_ptr;
  32.         tail_ptr = head_ptr;
  33.     }
  34.     else
  35.     {
  36.         list_insert(cursor, entry);
  37.         cursor = cursor->link();
  38.     }
  39.     ++many_nodes;
  40. }
  41.  

However there are still errors when I use the testprogram which tests
the boundaries. Does anybody eventually know what is still wrong at
these functions? :(
Without having looked at earlier code, it seems that you have two member
variables 'tail_ptr' and 'precursor' that are being confused.

I'd drop one of them.

When you get this to work (which is recommended if you haven't done this
before), you'll be amazed at the simplicifation a circular list brings.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Oct 19 '06 #13
hi,

I did this all and my methods now look like this:

Expand|Select|Wrap|Line Numbers
  1. void sequence::start()
  2. {
  3. cursor = head_ptr;
  4. precursor = 0;
  5.  
  6. }
  7.  
  8. void sequence::advance()
  9. {
  10. if(is_item())
  11. {
  12. precursor = cursor;
  13. cursor = cursor->link();
  14. }
  15.  
  16. }
  17.  
  18. void sequence::insert(const value_type& entry)
  19. {
  20. if(!(is_item()))
  21. cursor = head_ptr;
  22.  
  23. if(precursor == NULL)
  24. {
  25. list_head_insert(head_ptr, entry);
  26. cursor = head_ptr;
  27. tail_ptr = head_ptr;
  28. }
  29. else
  30. {
  31. list_insert(precursor, entry);
  32. cursor = precursor->link();
  33. }
  34.  
  35. ++many_nodes;
  36.  
  37. node* cursor1;
  38. node * precursor1;
  39. for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
  40. {
  41. precursor1 = cursor1;
  42. }
  43. tail_ptr = precursor1;
  44. }
  45.  
  46. void sequence::attach(const value_type& entry)
  47. {
  48. if(cursor == NULL)
  49. {
  50. list_head_insert(head_ptr, entry);
  51. cursor = head_ptr;
  52. tail_ptr = head_ptr;
  53. }
  54. else
  55. {
  56. list_insert(cursor, entry);
  57. cursor = cursor->link();
  58. precursor = cursor;
  59. }
  60.  
  61. ++many_nodes;
  62.  
  63. node* cursor1;
  64. node* precursor1;
  65. for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
  66. {
  67. precursor1 = cursor1;
  68. }
  69. tail_ptr = precursor1;
  70. }
  71. void sequence::operator =(const sequence& source)
  72. {
  73. if(this == &source)
  74. return;
  75.  
  76. list_clear(head_ptr);
  77. many_nodes=0;
  78. list_copy(source.head_ptr, head_ptr, tail_ptr);
  79. many_nodes = source.many_nodes;
  80. }
  81.  
If have added a for-loop in the insert and attach-method so that the
tail_ptr points definitely everytime to the last node, when i test this
function interactiv it works without problems but when i use this
testprogramm:

Expand|Select|Wrap|Line Numbers
  1. int test1( )
  2. {
  3. sequence empty;                            // An empty sequence
  4. sequence test;                             // A sequence to add
  5. items to
  6. double items1[4] = { 5, 10, 20, 30 };  // These 4 items are put in
  7. a sequence
  8. double items2[4] = { 10, 15, 20, 30 }; // These are put in another
  9. sequence
  10.  
  11. // Test that the empty sequence is really empty
  12. cout << "Starting with an empty sequence." << endl;
  13. if (!correct(empty, 0, 0, items1)) return 0;
  14.  
  15. // Test the attach function to add something to an empty sequence
  16. cout << "I am now using attach to put 10 into an empty sequence."
  17. << endl;
  18. test.attach(10);
  19. if (!correct(test, 1, 0, items2)) return 0;
  20.  
  21. // Test the insert function to add something to an empty sequence
  22. cout << "I am now using insert to put 10 into an empty sequence."
  23. << endl;
  24. test = empty;
  25.  
  26. test.insert(10);
  27.  
  28. if (!correct(test, 1, 0, items2)) return 0;
  29.  
  30. // Test the insert function to add an item at the front of a
  31. sequence
  32. cout << "I am now using attach to put 10,20,30 in an empty
  33. sequence.\n";
  34. cout << "Then I move the cursor to the start and insert 5." <<
  35. endl;
  36. test = empty;
  37. test.attach(10);
  38. test.attach(20);
  39. test.attach(30);
  40. test.start( );
  41. test.insert(5);
  42. if (!correct(test, 4, 0, items1)) return 0;
  43.  
  44. // Test the insert function to add an item in the middle of a
  45. sequence
  46. cout << "I am now using attach to put 10,20,30 in an empty
  47. sequence.\n";
  48. cout << "Then I move the cursor to the start, advance once, ";
  49. cout << "and insert 15." << endl;
  50. test = empty;
  51. test.attach(10);
  52. test.attach(20);
  53. test.attach(30);
  54. test.start( );
  55. test.advance( );
  56. test.insert(15);
  57. if (!correct(test, 4, 1, items2)) return 0;
  58.  
  59. // Test the attach function to add an item in the middle of a
  60. sequence
  61. cout << "I am now using attach to put 10,20,30 in an empty
  62. sequence.\n";
  63. cout << "Then I move the cursor to the start and attach 15 ";
  64. cout << "after the 10." << endl;
  65. test = empty;
  66. test.attach(10);
  67. test.attach(20);
  68. test.attach(30);
  69. test.start( );
  70. test.attach(15);
  71. if (!correct(test, 4, 1, items2)) return 0;
  72.  
  73. // All tests have been passed
  74. cout << "All tests of this first function have been passed." <<
  75. endl;
  76. }
  77.  
the programm stops the line test.insert(10); in the section "I am now
using insert to put 10 in an empty sequence". A popup-window opens and
it shows a message that the program has detected an error and has to be
closed. I also tried to debug the program, but i didn't find the
error....? :(

matti

Oct 19 '06 #14
hi,

I did this all and my methods now look like this:

Expand|Select|Wrap|Line Numbers
  1. void sequence::start()
  2. {
  3. cursor = head_ptr;
  4. precursor = 0;
  5.  
  6. }
  7.  
  8. void sequence::advance()
  9. {
  10. if(is_item())
  11. {
  12. precursor = cursor;
  13. cursor = cursor->link();
  14. }
  15.  
  16. }
  17.  
  18. void sequence::insert(const value_type& entry)
  19. {
  20. if(!(is_item()))
  21. cursor = head_ptr;
  22.  
  23. if(precursor == NULL)
  24. {
  25. list_head_insert(head_ptr, entry);
  26. cursor = head_ptr;
  27. tail_ptr = head_ptr;
  28. }
  29. else
  30. {
  31. list_insert(precursor, entry);
  32. cursor = precursor->link();
  33. }
  34.  
  35. ++many_nodes;
  36.  
  37. node* cursor1;
  38. node * precursor1;
  39. for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
  40. {
  41. precursor1 = cursor1;
  42. }
  43. tail_ptr = precursor1;
  44. }
  45.  
  46. void sequence::attach(const value_type& entry)
  47. {
  48. if(cursor == NULL)
  49. {
  50. list_head_insert(head_ptr, entry);
  51. cursor = head_ptr;
  52. tail_ptr = head_ptr;
  53. }
  54. else
  55. {
  56. list_insert(cursor, entry);
  57. cursor = cursor->link();
  58. precursor = cursor;
  59. }
  60.  
  61. ++many_nodes;
  62.  
  63. node* cursor1;
  64. node* precursor1;
  65. for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
  66. {
  67. precursor1 = cursor1;
  68. }
  69. tail_ptr = precursor1;
  70. }
  71. void sequence::operator =(const sequence& source)
  72. {
  73. if(this == &source)
  74. return;
  75.  
  76. list_clear(head_ptr);
  77. many_nodes=0;
  78. list_copy(source.head_ptr, head_ptr, tail_ptr);
  79. many_nodes = source.many_nodes;
  80. }
  81.  
If have added a for-loop in the insert and attach-method so that the
tail_ptr points definitely everytime to the last node, when i test this
function interactiv it works without problems but when i use this
testprogramm:

Expand|Select|Wrap|Line Numbers
  1. int test1( )
  2. {
  3. sequence empty;                            // An empty sequence
  4. sequence test;                             // A sequence to add
  5. items to
  6. double items1[4] = { 5, 10, 20, 30 };  // These 4 items are put in
  7. a sequence
  8. double items2[4] = { 10, 15, 20, 30 }; // These are put in another
  9. sequence
  10.  
  11. // Test that the empty sequence is really empty
  12. cout << "Starting with an empty sequence." << endl;
  13. if (!correct(empty, 0, 0, items1)) return 0;
  14.  
  15. // Test the attach function to add something to an empty sequence
  16. cout << "I am now using attach to put 10 into an empty sequence."
  17. << endl;
  18. test.attach(10);
  19. if (!correct(test, 1, 0, items2)) return 0;
  20.  
  21. // Test the insert function to add something to an empty sequence
  22. cout << "I am now using insert to put 10 into an empty sequence."
  23. << endl;
  24. test = empty;
  25.  
  26. test.insert(10);
  27.  
  28. if (!correct(test, 1, 0, items2)) return 0;
  29.  
  30. // Test the insert function to add an item at the front of a
  31. sequence
  32. cout << "I am now using attach to put 10,20,30 in an empty
  33. sequence.\n";
  34. cout << "Then I move the cursor to the start and insert 5." <<
  35. endl;
  36. test = empty;
  37. test.attach(10);
  38. test.attach(20);
  39. test.attach(30);
  40. test.start( );
  41. test.insert(5);
  42. if (!correct(test, 4, 0, items1)) return 0;
  43.  
  44. // Test the insert function to add an item in the middle of a
  45. sequence
  46. cout << "I am now using attach to put 10,20,30 in an empty
  47. sequence.\n";
  48. cout << "Then I move the cursor to the start, advance once, ";
  49. cout << "and insert 15." << endl;
  50. test = empty;
  51. test.attach(10);
  52. test.attach(20);
  53. test.attach(30);
  54. test.start( );
  55. test.advance( );
  56. test.insert(15);
  57. if (!correct(test, 4, 1, items2)) return 0;
  58.  
  59. // Test the attach function to add an item in the middle of a
  60. sequence
  61. cout << "I am now using attach to put 10,20,30 in an empty
  62. sequence.\n";
  63. cout << "Then I move the cursor to the start and attach 15 ";
  64. cout << "after the 10." << endl;
  65. test = empty;
  66. test.attach(10);
  67. test.attach(20);
  68. test.attach(30);
  69. test.start( );
  70. test.attach(15);
  71. if (!correct(test, 4, 1, items2)) return 0;
  72.  
  73. // All tests have been passed
  74. cout << "All tests of this first function have been passed." <<
  75. endl;
  76. }
  77.  
the programm stops the line test.insert(10); in the section "I am now
using insert to put 10 in an empty sequence". A popup-window opens and
it shows a message that the program has detected an error and has to be
closed. I also tried to debug the program, but i didn't find the
error....? :(

matti

Oct 19 '06 #15
* ma****@gmx.at:
hi,

I did this all and
[...]
>
the programm stops the line test.insert(10); in the section "I am now
using insert to put 10 in an empty sequence". A popup-window opens and
it shows a message that the program has detected an error and has to be
closed. I also tried to debug the program, but i didn't find the
error....? :(
Sorry, perhaps I gave bad advice.

Good advice: start /as simple as possible/. Test all the way. Add a
little bit of functionality at a time and test thoroughly.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Oct 19 '06 #16

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by J Peterman | last post: by
10 posts views Thread by cody | last post: by
2 posts views Thread by Justin Crites | last post: by
2 posts views Thread by Steve | last post: by
20 posts views Thread by martin-g | last post: by
1 post views Thread by CaseySimplified | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.