CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Threaded View

  1. #1
    Join Date
    Jun 2006
    Posts
    15

    Question Assigment HELP.. stuck & confused..

    I have everything able to compile, but I have to add a few things and I am not sure what to do. Any suggestions or ideas would be GREATLY appreciated cause i am pretty clueless at this point.
    THANKS!!
    Write a function that returns the info of the n'th element of the linked list. If no such element exists, terminate the program.

    Write a function that deletes the n'th element in the linked list. If no such element exists, output an appropriate message.





    Code:
    #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
    {
    	friend ostream& operator<<(ostream&, const linkedListType<Type>&);
    
    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. 
    
    	Type getKThElement(int k); 
    	
    	void deteteKthElement(int k);
    
        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. 
    
    protected:
        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 
    private:
        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
    Last edited by brokenbndgedoll; June 18th, 2006 at 02:11 PM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured