Linked list

copy constructor and destroy

Page 1 of 1

2 Replies - 1538 Views - Last Post: 08 November 2009 - 06:18 PM Rate Topic: -----

#1 brac589  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 33
  • Joined: 04-March 09

Linked list

Posted 07 November 2009 - 06:14 PM

Hi!!!
I think I am having trouble with my copy function......
--->The OLList::copy is a helper function for both copy constructor and the assignment operator. Its job is to generate a new chain of nodes with items identical to the items in the existing OLList object.
use new and manipulate pointer variables to create links.

--->Write a main program file to demonstrate successful copying of lists. Demonstrate:
copying of an empty list
copying of a list with only one item
copying of a list with many items.

we have to show that the copies are independent of each other (ie if 'a' and 'b' are OLList objects, and 'a' is a copy of 'b'. insertions to and removals from 'a' after the coying is done should not affect 'b'

--->The destroy function should remove dynamically allocated nodes of a linked list.


I think my destroy function is ok.

-->However, I cannot figure out how to stop the_list to not change after it its been copied to b.

Can someone help me out??

Also for the main.cpp( It is just a rough/test main....I wanted to check where I was going wrong)
I have done an empty list (ie OLList the_list)and a list with one item(ie OLList b and b=the_list)
--> first, does this sound right?
--> How do i do a list with many items??

// OLList.cpp

#include <iostream>
using namespace std;

#include <stdlib.h>
#include "OLList.h"

OLList::OLList()
  : headM(0)
{
}

OLList::OLList(const OLList& source)
{
  copy(source);
}

OLList& OLList::operator =(const OLList& rhs)
{
  if (this != &rhs)
 {
	destroy();
	copy(rhs);
  }
  return *this;
}

OLList::~OLList()
{
  destroy();
}

void OLList::print() const
{
  cout << '[';
  if (headM != 0) {
	cout << ' ' << headM->item;
	for (const Node *p = headM->next; p != 0; p = p->next)
	  cout << ", " << p->item; 
  }
  cout << " ]\n";
}

void OLList::insert(const ListItem& itemA)
{
  Node *new_node = new Node;
  new_node->item = itemA;

  if (headM == 0 || itemA <= headM->item) {
	new_node->next = headM;
	headM = new_node;
  }
  else {
	Node *before = headM;	  // will point to node in front of new node
	Node *after = headM->next; // will be 0 or point to node after new node
	while(after != 0 && itemA > after->item) {
	  before = after;
	  after = after->next;
	}
	new_node->next = after;
	before->next = new_node;
  }
}

void OLList::remove(const ListItem& itemA)
{
  if (headM == 0 || itemA < headM->item)
	return;

  Node *doomed_node = 0;
  if (itemA == headM->item) {
	doomed_node = headM;
	headM = headM->next;
  }
  else {
	Node *before = headM;
	Node *maybe_doomed = headM->next;
	while(maybe_doomed != 0 && itemA > maybe_doomed->item) {
	  before = maybe_doomed;
	  maybe_doomed = maybe_doomed->next;
	}

	// point one

	if (maybe_doomed != 0 && maybe_doomed->item == itemA) {
	  doomed_node = maybe_doomed;

	  // point two
	  
	  before->next = maybe_doomed->next;
	}	  
  }
  delete doomed_node;		   // Does nothing if doomed_node == 0.
}

void OLList::destroy()
{
 delete [] headM;
}
void OLList::copy(const OLList& source)
{
 Node *nnode = new Node;
 nnode = source.headM;

 nnode->item = source.headM->item;
 nnode->next = source.headM->next;

 /*destroy();*/
 headM = nnode;
}



//OLList.h
#ifndef OLLIST_H
#define OLLIST_H

typedef int ListItem;

struct Node {
  ListItem item;
  Node *next;
};

class OLList {
public:
  OLList(); // PROMISES: Creates empty list.
  OLList(const OLList& source);
  OLList& operator =(const OLList& rhs);
  ~OLList();

  void insert(const ListItem& itemA);
  // PROMISES:
  //	A node with a copy of itemA is added in 
  //	a way that preserves the nondecreasing 
  //	order of items in nodes.

  void remove(const ListItem& itemA);
  //  PROMISES:
  //	If no node has an item matching itemA, 
  //	list is unchanged.
  //	Otherwise exactly one node with 
  //	its item == itemA is removed.

  void print() const;
  // PROMISES:
  //   Prints items in list on a single line, with commas separating
  //   the items and square brackets marking the ends of the list.
  // NOTE:
  //   This is different from the print function presented in lectures.

private:
  Node *headM;
  void destroy(); 
  // Deallocate all nodes, set headM to zero.

  void copy(const OLList& source); 
  // List becomes copy of source.
};
#endif




 
//main.cpp

#include <iostream>
using namespace std;

#include "OLList.h"

int main()
{
  OLList the_list;

  cout << "List just after creation: ";
  the_list.print();
  
  the_list.insert(440);
  the_list.insert(330);
  the_list.insert(220);
  the_list.insert(110);
  cout << "List after some insertions: ";
  the_list.print();

  the_list.remove(550);
  the_list.remove(330);
  cout << "List after some removals: ";
  the_list.print();

  OLList b;
  b = the_list;
  the_list = the_list;
  cout << "b's list equals the_list: ";
  b.print();
  
b.remove(220);
b.insert(550);
cout<<"b,s modified list:";
b.print();
cout< "the_list is the same as before?";
the_list.print();
  return 0;
} 


My output --->
List just after creation: [ ]
List after some insertions: [ 110, 220, 330, 440 ]
List after some removals: [ 110, 220, 440 ]
b's list equals the_list: [ 110, 220, 440 ]
b,s modified list:[ 110, 440, 550 ]
the_list is the same as before?[ 110, 440, 550 ]


the_list should still be[110,220,440] i believe




Thank you for helping me out

This post has been edited by brac589: 07 November 2009 - 06:21 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Linked list

#2 brac589  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 33
  • Joined: 04-March 09

Re: Linked list

Posted 07 November 2009 - 09:57 PM

These two functions from OLList.cpp

   
void OLList::destroy()
{
delete [] headM;
}

void OLList::copy(const OLList& source)
{
Node *nnode = new Node;
nnode = source.headM;

nnode->item = source.headM->item;
nnode->next = source.headM->next;

/*destroy();*/
headM = nnode;
}


I have been working on this, and I was wondering can I use
OLList temp;
and set
temp = source.headM
and then when the function exits, temp dies???
and the_list doesnt change?

I have tried and the output of the_list always changes after b copies the_list :s

thanks

This post has been edited by brac589: 08 November 2009 - 05:36 PM

Was This Post Helpful? 0
  • +
  • -

#3 brac589  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 33
  • Joined: 04-March 09

Re: Linked list

Posted 08 November 2009 - 06:18 PM

in my new copy function,
 void OLList::copy(const OLList& source)
{
 Node *nnode = new Node;
 nnode = source.headM;
 /*nnode->item = source.headM->item;*/
 /*nnode->next = source.headM->next;*/

  while(nnode!=0)
   {
	nnode=nnode->next;
   }
}


List just after creation: [ ]
List after some insertions: [ 110, 220, 330, 440 ]
List after some removals: [ 110, 220, 440 ]
b's list equals the_list at the beginning: [ ]
b's list after insertions and removals: [ 550 ]
the_list should equal [ 110, 220, 440 ]:
[ 110, 220, 440 ]

in the above is right that b's list equals [ ] ???????
or should it equal [ 110, 440, 550 ] ?????

Thank you

This post has been edited by brac589: 08 November 2009 - 08:03 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1