3 Replies - 1498 Views - Last Post: 11 October 2012 - 07:13 AM Rate Topic: -----

#1 purplesmiles  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 02-October 12

Merging lists

Posted 10 October 2012 - 09:52 PM

#include <iostream>
#include "C:\Documents and Settings\Administrator\Desktop\hw3_files\Ch5_ProgExercise6\orderedLinkedList.h"

using namespace std;


int main()

{
	orderedLinkedListType<int> newList, list1, list2;

	int num;

	cout<<"Enter numbers, for list1, ending with -999"<<endl;
	cin>>num;

	while(num != -999)
	{
		list1.insertNode(num);
		cin>>num;
	}

	cout<<"list1: "<<list1<<endl;
	cout<<"Length of list1: "<<list1.length()<<endl;


	cout<<"Enter numbers, for list2, ending with -999"<<endl;
	cin>>num;

	while(num != -999)
	{
		list2.insertNode(num);
		cin>>num;
	}

	cout<<endl;

	cout<<"list2: "<<list2<<endl;
	cout<<"Length of list2: "<<list2.length()<<endl;

	newList.mergeLists(list1, list2);

	cout<<"newList after merging lis1 and list2"<<endl;
	cout<<newList<<endl;
	cout<<"Length of the newList: "<<newList.length()<<endl;

	cout<<"*************************"<<endl;

	return 0;
}




#ifndef H_orderedLinkedListType
#define H_orderedLinkedListType

#include <iostream>
#include <cassert>

#include "C:\Documents and Settings\Administrator\Desktop\hw3_files\Ch5_ProgExercise6\linkedList.h"

using namespace std;

template<class Type>
class orderedLinkedListType: public linkedListType<Type>
{
public:
    bool search(const Type& searchItem);
		//Function to determine if item is in the list
 		//Postcondition: Outputs "Item is found in the list"
 		//              if searchItem is in the list;
		//         otherwise, outputs "Item is not in the list"

    void insertNode(const Type& newItem);
		//Function to insert newItem in the list
		//Postcondition: first points to the new list and
		//        newItem is inserted at the proper place in the list

    void deleteNode(const Type& deleteItem);
		//Function to delete deleteItem from the list
		//Postcondition: If found, then the node containing the
		//                 deleteItem is deleted from the list;
		//                 first points to the first node of
		//                 the new list
		//               If deleteItem is not in the list,
		//                  an appropriate message is printed

	void mergeLists(orderedLinkedListType<Type> &list1,
				    orderedLinkedListType<Type> &list2);
		//This operation creates a new list by merging the elements
     	//of list1 and list2.
        //Pre condition: Both lists list1 and list2 are ordered.
        //Post condition: first points to the merged list.
		// 			  list1 and list2 are empty.

};

template<class Type>
bool orderedLinkedListType<Type>::search(const Type& searchItem)
{
    bool found;
    nodeType<Type> *current; //pointer to traverse the list
	nodeType<Type> *first;

    found = false;    //initialize found to false
    current = first;  //start the search at the first node

    while(current != NULL && !found)
       if(current->info >= searchItem)
          found = true;
       else
          current = current->link;

      if(found)
         found = (current->info == searchItem); //test for equality

    return found;
}//end search

template<class Type>
void orderedLinkedListType<Type>::insertNode(const Type& newItem)
{
	nodeType<Type> *current; //pointer to traverse the list
	nodeType<Type> *trailCurrent; //pointer just before current
	nodeType<Type> *newNode; //pointer to create a node
	nodeType<Type> *first;
	

	bool  found;

	newNode = new nodeType<Type>; //create the node
 	assert(newNode != NULL);

	newNode->info = newItem;   //store newItem in the node
	newNode->link = NULL;      //set the link field of the node
                                 //to NULL

	if(first == NULL)  //Case 1
	{
	   first = newNode;
	   count++;
 	}
	else
	{
	   current = first;
	   found = false;

	   while(current != NULL && !found) //search the list
	     if(current->info >= newItem)
		   found = true;
     	 else
	     {
	         trailCurrent = current;
	         current = current->link;
	     }

	   if(current == first)  	//Case 2
	   {
			newNode->link = first;
			first = newNode;
 			count++;
	   }
	   else				//Case 3
	   {
			trailCurrent->link = newNode;
			newNode->link = current;
 			count++;
	   }
	}//end else
}//end insertNode

template<class Type>
void orderedLinkedListType<Type>::deleteNode(const Type& deleteItem)
{
	nodeType<Type> *current; //pointer to traverse the list
	nodeType<Type> *trailCurrent; //pointer just before current
	nodeType<Type> *first;
	nodeType<Type> *last;

	bool found;

	if(first == NULL) //Case 1
		cerr<<"Cannot delete from an empty list."<<endl;
	else
	{
		current = first;
		found = false;

		while(current != NULL && !found)  //search the list
			if(current->info >= deleteItem)
				found = true;
			else
			{
				trailCurrent = current;
				current = current->link;
			}

		if(current == NULL)   //Case 4
			cout<<"Item to be deleted is not in the list."<<endl;
		else
 			if(current->info == deleteItem) //item to be deleted is
											//in the list
			{
  				if(first == current) 		//Case 2
				{
					first = first->link;

					delete current;
				}
				else     				//Case 3
				{
					trailCurrent->link = current->link;
					delete current;
				}
 				count--;
			}
			else  					//Case 4
				cout<<"Item to be deleted is not in the list."<<endl;
	}
} //end deleteNode


template<class Type>
void orderedLinkedListType<Type>::mergeLists(orderedLinkedListType<Type> &list1,
				                       orderedLinkedListType<Type> &list2)
{
	nodeType<Type> *lastSmall;	//pointer to the last node of
  									// the merged list.
    nodeType<Type> *first;
	nodeType<Type> *first1 = list1.first;
	nodeType<Type> *first2 = list2.first;

	count = list1.count + list2.count;

	if (list1.first == NULL)   //first sublist is empty
	{
		first = list2.first;
		list2.first = NULL;
	}
	else
		if (list2.first == NULL)   // second sublist is empty
		{
			first = list1.first;
			list1.first = NULL;
		}
		else
		{
			if (first1->info < first2->info) //Compare first nodes
			{
				first = first1;
				first1 = first1->link;
				lastSmall = first;
			}
			else
			{
				first = first2;
				first2 = first2->link;
				lastSmall = first;
			}

			while (first1 != NULL && first2 != NULL)
			{
				if (first1->info < first2->info)
				{
					lastSmall->link = first1;
					lastSmall = lastSmall->link;
					first1 = first1->link;
				}
				else
				{
					lastSmall->link = first2;
					lastSmall = lastSmall->link;
					first2 = first2->link;
				}
			} //end while

			if (first1 == NULL)  			//first sublist exhausted first
				lastSmall->link = first2;
			else							//second sublist exhausted first
				lastSmall->link = first1;

			list1.first = NULL;
			list1.count = 0;
			list2.first = NULL;
			list2.count = 0;
	}
}//end mergeList


#endif


#ifndef H_LinkedListType
#define H_LinkedListType

#include <iostream>
#include <cassert>
using namespace std;

template <class Type>
struct nodeType
{
	Type info;
	nodeType<Type> *link;
};

template<class Type>
class linkedListType
{


public:
    const linkedListType<Type>& operator=
          			      (const linkedListType<Type>&);
		//Overload the assignment operator.
    void initializeList();
 		//Initializes the list to an empty state.
	    //Postcondition: first = NULL, last = NULL,
		//                count = 0
    bool isEmptyList();
 		//Function to determine whether the list is empty.
		//Postcondition: Returns true if the list is empty;
		//               otherwise, returns false.

	int length();
		//Function to return the number of nodes in the
		//list.
		//Postcondition: The value of count is returned.
    void destroyList();
 		//Function to delete all the nodes from the list.
  		//Postcondition: first = NULL, last = NULL,
		//               count = 0
    Type front();
 		//Function to return the first element of the list.
 		//Precondition: The list must exist and must not be
		//empty.
  		//Postcondition: If the list is empty, then the
 		//               program terminates; otherwise,
	    //               the first element of the list is
		//               returned.
    Type back();
       //Function to return the last element of the
       //list.
		//Precondition: The list must exist and must not
		//be empty.
		//Postcondition: If the list is empty, then the
		//               program terminates; otherwise,
		//               the last element of the list is
		//               returned.

   bool search(const Type& searchItem);
		//Function to determine whether searchItem is in
		//the list.
		//Postcondition: Returns true if searchItem is found
		//               in the list; otherwise, it returns
		//               false.

    void insertFirst(const Type& newItem);
		//Function to insert newItem in the list.
		//Postcondition: first points to the new list
		//                and newItem is inserted at the
		//                beginning of the list.

    void insertLast(const Type& newItem);
		//Function to return newItem at the end of the
		//list.
	    //Postcondition: first points to the new list,
		//                newItem is inserted at the end
		//                of the list, and last points to
		//                the last node in the list.

    void deleteNode(const Type& deleteItem);
  		//Function to delete deleteItem from the list.
 		//Postcondition: If found, the node containing
   		//               deleteItem is deleted from the
		//                list, first points to the first
		//                node, and last points to the last
		//                node of the updated list.

    linkedListType();
   		//default constructor
 		//Initializes the list to an empty state.
 		//Postcondition: first = NULL, last = NULL,
		//               count = 0

    linkedListType(const linkedListType<Type>& otherList);
         //copy constructor

    ~linkedListType();
    	//destructor
   		//Deletes all the nodes from the list.
    	//Postcondition: The list object is destroyed.


    int count;		//variable to store the number of
 					//elements in the list
    nodeType<Type> *first; //pointer to the first node of
                           //the list
    nodeType<Type> *last;  //pointer to the last node of
                           //the list

    void copyList(const linkedListType<Type>& otherList);
		//Function to make a copy of otherList.
		//Postcondition: A copy of otherList is created
		//               and assigned to this list.
};

template<class Type>
bool linkedListType<Type>::isEmptyList()
{
	return(first == NULL);
}

template<class Type>
linkedListType<Type>::linkedListType() // default constructor
{
	first = NULL;
	last = NULL;
	count = 0;
}

template<class Type>
void linkedListType<Type>::destroyList()
{
	nodeType<Type> *temp;   //pointer to deallocate the memory
							//occupied by the node
	while(first != NULL)    //while there are nodes in the list
	{
	   temp = first;        //set temp to the current node
	   first = first->link; //advance first to the next node
	   delete temp;         //deallocate memory occupied by temp
	}

	last = NULL;	//initialize last to NULL; first has already
                   //been set to NULL by the while loop
 	count = 0;
}


template<class Type>
void linkedListType<Type>::initializeList()
{
	destroyList(); //if the list has any nodes, delete them
}

template<class Type>
int linkedListType<Type>::length()
{
 	return count;
}  // end length

template<class Type>
Type linkedListType<Type>::front()
{
    assert(first != NULL);
   	return first->info; //return the info of the first node
}//end front


template<class Type>
Type linkedListType<Type>::back()
{
	 assert(last != NULL);
   	 return last->info; //return the info of the first node
}//end back

template<class Type>
bool linkedListType<Type>::search(const Type& searchItem)
{
    nodeType<Type> *current; //pointer to traverse the list
    bool found;

    current = first; //set current to point to the
                     //first node in the list
    found = false;   //set found to false

    while(current != NULL && !found)		//search the list
        if(current->info == searchItem)     //item is found
           found = true;
        else
           current = current->link; //make current point
                                    //to the next node

     return found;
}//end search

template<class Type>
void linkedListType<Type>::insertFirst(const Type& newItem)
{
	nodeType<Type> *newNode; //pointer to create the new node

	newNode = new nodeType<Type>; //create the new node

	assert(newNode != NULL);	//If unable to allocate memory,
 								//terminate the program

	newNode->info = newItem; 	   //store the new item in the node
	newNode->link = first;        //insert newNode before first
	first = newNode;              //make first point to the
                                 //actual first node
	count++; 			   //increment count

	if(last == NULL)   //if the list was empty, newNode is also
                      //the last node in the list
		last = newNode;
}

template<class Type>
void linkedListType<Type>::insertLast(const Type& newItem)
{
	nodeType<Type> *newNode; //pointer to create the new node

	newNode = new nodeType<Type>; //create the new node

	assert(newNode != NULL);	//If unable to allocate memory,
 							//terminate the program

	newNode->info = newItem;      //store the new item in the node
	newNode->link = NULL;         //set the link field of newNode
         						//to NULL

	if(first == NULL)	//if the list is empty, newNode is
     					//both the first and last node
	{
		first = newNode;
		last = newNode;
		count++;		//increment count
	}
	else			//the list is not empty, insert newNode after last
	{
		last->link = newNode; //insert newNode after last
		last = newNode;   //make last point to the actual last node
		count++;		//increment count
	}
}//end insertLast

template<class Type>
void linkedListType<Type>::deleteNode(const Type& deleteItem)
{
	nodeType<Type> *current; //pointer to traverse the list
	nodeType<Type> *trailCurrent; //pointer just before current
	bool found;

	if(first == NULL)    //Case 1; list is empty.
		cerr<<"Can not delete from an empty list.\n";
	else
	{
		if(first->info == deleteItem) //Case 2
		{
			current = first;
			first = first->link;
			count--;
			if(first == NULL)    //list had only one node
				last = NULL;
			delete current;
		}
		else  //search the list for the node with the given info
		{
			found = false;
			trailCurrent = first;   //set trailCurrent to point to
                                 //the first node
			current = first->link;  //set current to point to the
    			   //second node

			while((!found) && (current != NULL))
			{
  				if(current->info != deleteItem)
				{
					trailCurrent = current;
					current = current-> link;
				}
				else
					found = true;
			} // end while

			if(found) //Case 3; if found, delete the node
			{
				trailCurrent->link = current->link;
				count--;

				if(last == current)      //node to be deleted was
                                     //the last node
					last = trailCurrent;  //update the value of last
				delete current;  //delete the node from the list
			}
			else
				cout<<"Item to be deleted is not in the list."<<endl;
		} //end else
	} //end else
} //end deleteNode


	//Overloading the stream insertion operator
template<class Type>
ostream& operator<<(ostream& osObject, const linkedListType<Type>& list)
{
	nodeType<Type> *current; //pointer to traverse the list

	current = list.first;   //set current so that it points to
					   //the first node
	while(current != NULL) //while more data to print
	{
	   osObject<<current->info<<" ";
	   current = current->link;
	}

	return osObject;
}

template<class Type>
linkedListType<Type>::~linkedListType() // destructor
{
	destroyList();
}//end destructor


template<class Type>
void linkedListType<Type>::copyList
            	      (const linkedListType<Type>& otherList)
{
   nodeType<Type> *newNode; //pointer to create a node
   nodeType<Type> *current; //pointer to traverse the list

   if(first != NULL)	//if list is nonempty, make it empty
	  destroyList();

   if(otherList.first == NULL) //otherList is empty
   {
		first = NULL;
		last = NULL;
 		count = 0;
   }
   else
   {
		current = otherList.first;  //current points to the
									//list to be copied
		count = otherList.count;

			//copy the first node
		first = new nodeType<Type>;  //create the node

 		assert(first != NULL);

		first->info = current->info; //copy the info
		first->link = NULL;  	     //set the link field of
									 //the node to NULL
		last = first;    		     //make last point to the
            						 //first node
		current = current->link;     //make current point to the
           							 //next node

			//copy the remaining list
		while(current != NULL)
		{
			newNode = new nodeType<Type>;  //create a node

			assert(newNode!= NULL);

			newNode->info = current->info;	//copy the info
			newNode->link = NULL;   	    //set the link of
                                        //newNode to NULL
			last->link = newNode; 		//attach newNode after last
			last = newNode;   			//make last point to
										//the actual last node
			current = current->link;	//make current point to
       									//the next node
		}//end while
	}//end else
}//end copyList


	//copy constructor
template<class Type>
linkedListType<Type>::linkedListType
            	      (const linkedListType<Type>& otherList)
{
	first = NULL;

	copyList(otherList);

}//end copy constructor

	//overload the assignment operator
template<class Type>
const linkedListType<Type>& linkedListType<Type>::operator=
   	 	 		(const linkedListType<Type>& otherList)
{

	if(this != &otherList) //avoid self-copy
	{
		copyList(otherList);
	}//end else

	return *this;
}

#endif




Here is the problem. I keep getting random errors. I can cut and paste the code back in just as it was and I will get different errors. Right now, the errors are showing that a lot of the items in the first section of the code (the first set of code in tags) is undeclared. However, these errors weren't there before and best I can tell they are declared. I'm relatively new to all this so any help with this is greatly appreciated.

Is This A Good Question/Topic? 0
  • +

Replies To: Merging lists

#2 purplesmiles  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 02-October 12

Re: Merging lists

Posted 10 October 2012 - 10:05 PM

Now all the errors are for No post increment operator for type for the last set of codes (the bottom set of code tags)
Was This Post Helpful? 0
  • +
  • -

#3 purplesmiles  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 9
  • Joined: 02-October 12

Re: Merging lists

Posted 11 October 2012 - 12:14 AM

Finally got them to compile. However, now the lists do not merge. In fact, nothing comes up at all. The lists i put in doesn't even come back up. Any help is greatly appreciated.
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3572
  • View blog
  • Posts: 11,107
  • Joined: 05-May 12

Re: Merging lists

Posted 11 October 2012 - 07:13 AM

Have you tried stepping through your code with a debugger? If you don't know how to use a debugger, I highly recommend picking up the skill soon because it will pay off dividends in the long run.

If you don't want to learn how to use a debugger, you can go old school and put strategically place statements to print out to the console so that you can monitor what your program is doing.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1