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

Thread: Multiple Problems

  1. #1
    Join Date
    Sep 2011
    Posts
    17

    Multiple Problems

    Hello,

    I am working on a final for my data structures class and the program is to read a file into memory then from there run various tasks (sorting, inserting, displaying). He have header files that are defined already but we need to implement pieces on our own that are not included. Even when I compile with the base headers I run into errors and the instructor had entered some if (true) statements so that it would compile but I don't think it actually solved the problem.

    Here is what I have so far and the errors I am getting.


    Code:
    #ifndef H_UnorderedLinkedList
    #define H_UnorderedLinkedList
    
    
    #include "linkedList.h"
     
    using namespace std;
    
    template <class Type>
    class unorderedLinkedList: public linkedListType<Type>
    {
    public:
           bool search(const Type& searchItem) const;
      
           void insertFirst(const Type& newItem);
    
           void insertLast(const Type& newItem);
    
           void deleteNode(const Type& deleteItem);
    
           void deleteAll(const Type& deleteItem);
    
           void deleteSmallest();
    
           void printListReverse() const;
    
           void mergeSort();
    
    private:
    	void reversePrint(nodeType<Type> *current) const;
    
    	void divideList(nodeType<Type>* first1, 
    					nodeType<Type>* &first2);
    
    	nodeType<Type>* mergeList(nodeType<Type>* first1, 
    							  nodeType<Type>* first2);
    
    	void recMergeSort(nodeType<Type>* &head);
    };
    
    template <class Type>
    bool unorderedLinkedList<Type>::
                       search(const Type& searchItem) const
    {
        nodeType<Type> *current; //pointer to traverse the list
        bool found = false;
        
        current = first; //set current to point to the first 
                         //node in the list
    
        while (current != NULL && !found)    //search the list
    		if(true)// jk       if (current->info == searchItem) //searchItem is found
                found = true;
            else
                current = current->link; //make current point to
                                         //the next node
        return found; 
    }//end search
    
    template <class Type>
    void unorderedLinkedList<Type>::insertFirst(const Type& newItem)
    {
        nodeType<Type> *newNode; //pointer to create the new node
    
        newNode = new nodeType<Type>; //create the new node
    
        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;
    }//end insertFirst
    
    template <class Type>
    void unorderedLinkedList<Type>::insertLast(const Type& newItem)
    {
        nodeType<Type> *newNode; //pointer to create the new node
    
        newNode = new nodeType<Type>; //create the new node
    
        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 in the list
            count++;        //increment count
        }
    }//end insertLast
    
    
    template <class Type>
    void unorderedLinkedList<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; the list is empty. 
            cout << "Cannot delete from an empty list."
                 << endl;
        else
        {
    	if(true)//jk  if (first->info == deleteItem) //Case 2 
            {
                current = first;
                first = first->link;
                count--;
                if (first == NULL)    //the list has 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 (current != NULL && !found)
                {
    			if(true)//                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 << "The item to be deleted is not in "
                         << "the list." << endl;
            }//end else
        }//end else
    }//end deleteNode
    
    
    template <class Type>
    void unorderedLinkedList<Type>::deleteAll(const Type& deleteItem)
    {
    	nodeType<Type> *current; //pointer to traverse the list
    	nodeType<Type> *trailCurrent; //pointer just before current
    
    	if (first == NULL)    //Case 1; list is empty. 
    		cout << "Can not delete from an empty list." << endl;
    	else
    	{
    		current = first;
    
    		while (current != NULL)
    		{
    		if(true)//jk  			if (current->info == deleteItem) 
    			{
    				if (current == first)
    				{
    					first = first->link;
    					delete current;
    					current = first;
    					if(first == NULL)
    						last = NULL;
    				}
    				else
    				{
    					trailCurrent->link = current->link;
    					
    					if(current == last)
    						last = trailCurrent;
    
    					delete current;
    
    					current = trailCurrent-> link;
    				}
    			}
    			else
    			{ 
    				trailCurrent = current;
    				current = current->link;
    			}
    		} // end while
    	}
    } //end deleteAll
    
    template <class Type>
    void unorderedLinkedList<Type>::deleteSmallest()
    {
    	nodeType<Type> *current; 
    	nodeType<Type> *trailCurrent; 
    
    	nodeType<Type> *small; 
    	nodeType<Type> *trailSmall;
    	
    	if (first == NULL)
    		cout << "Cannot delete from an empty list." << endl;
    	else
    		if (first->link == NULL)
    		{
    			first = NULL;
    			delete last;
    			last = NULL;
    		}
    		else
    		{
    			small = first;
    			trailCurrent = first;
    			current = first->link;
    
    			while (current != NULL)
    			{
    			if(true)//jk				if (small->info > current->info)
    				{
    					trailSmall = trailCurrent;
    					small = current;
    				}
    
    				trailCurrent = current;
    				current = current->link;
    			}
    
    			if (small == first)
    				first = first->link;
    			else
    			{
    				trailSmall->link = small->link;
    
    				if (small == last)
    					last = trailSmall;
    			}
    
    			delete small;
    		}
    }
    
    template<class Type>
    void unorderedLinkedList<Type>::mergeSort()
    {
    	recMergeSort(first);
    }
    
    template<class Type>
    void unorderedLinkedList<Type>::divideList(
    						nodeType<Type>* first1, 
    						nodeType<Type>* &first2)
    {
    	nodeType<Type>* middle;
    	nodeType<Type>* current;
    
    	if (first1 == NULL) // if (true)
    		first2 = NULL;
    	else if(first1->link == NULL)
    		first2 = NULL;
    		else
    		{
    			middle = first1;
    			current = first1->link;
    			if (current != NULL)
    				current = current->link;
    
    			while (current != NULL)
    			{
    				middle = middle->link;
    				current = current->link;
    				if (current != NULL)
    					current = current->link;
    			} //end while
    
    			first2 = middle->link;
    			middle->link = NULL;
    
    		} //end else
    } //end divideList
    
    
    
    template<class Type>
    nodeType<Type>* unorderedLinkedList<Type>::mergeList 
      	            (nodeType<Type>* first1, nodeType<Type>* first2)
    {
    	nodeType<Type> *lastSmall;
    	nodeType<Type> *newHead;
    
    	if (first1 == NULL)
    		return first2;
    	else
    		if (first2 == NULL)
    			return first1;
    		else
    		{
    			if (first1->info < first2->info)
    			{
    				newHead = first1;  
    				first1 = first1->link;
    				lastSmall = newHead;
    			}
    			else
    			{
    				newHead = first2;
    				first2 = first2->link;
    				lastSmall = newHead;
    			}
    	
    			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)
    				lastSmall->link = first2;
    			else
    				lastSmall->link = first1;
    
    	   return newHead;
    	}	
    } //end mergeList
    
    
    template<class elemType>
    void unorderedLinkedList<elemType>::recMergeSort(
      						nodeType<elemType>* &head)
    {
    	nodeType<elemType> *otherHead;
    
    	if (head != NULL)
    	   if( head->link != NULL)
    	   {
    			divideList(head, otherHead);
    			recMergeSort(head);
    			recMergeSort(otherHead);
    			head = mergeList(head, otherHead);
    	   }
    } //end recMergeSort
    
    template<class Type>
    void unorderedLinkedList<Type>::reversePrint
    							(nodeType<Type> *current) const
    {
    	if (current != NULL)
    	{
    		reversePrint(current->link);
    		cout << current->info << " ";
    	}
    }
    
    template<class Type>
    void unorderedLinkedList<Type>::printListReverse() const
    {
    	reversePrint(first);
    	cout << endl;
    }
    Code:
    #ifndef H_EmployeeType
    #define H_EmployeeType
    
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    class employeeType
    {
    	friend ostream& operator<< (ostream&, const employeeType&);
    
    public:
    	void setEmployeeInfo(int id, string employee);
    	bool checkEmployeeNumber(int id);
    	void printInfo() const;
    	employeeType(int id = 0, string employee = "");
    
    private:
    	int iEmpNum;
    	string sEmpName;
    };
    
    ostream& operator<< (ostream& osObject, const employeeType& list)
    {
    	osObject << endl;
    	osObject << "Employee Number: " << list.iEmpNum << endl;
    	osObject << "Employee Name  :" << list.sEmpName << endl;
    	osObject << "_________________________________" << endl;
    
    	return osObject;
    }
    
    void employeeType::setEmployeeInfo(int id, string employee)
    {
    	iEmpNum = id;
    	sEmpName = employee;
    }
    
    void employeeType::printInfo() const
    {
    	cout << "Employee Number: " << iEmpNum << endl;
    	cout << "Employee Name  :" << sEmpName << endl;
    }
    
    bool employeeType::checkEmployeeNumber(int id)
    {
    	return (iEmpNum == id);
    }
    
    employeeType::employeeType(int id, string employee)
    {
    	setEmployeeInfo(id, employee);
    }
    #endif
    Code:
    #ifndef H_EmployeeListType
    #define H_EmployeeListType
    
    #include <string>
    #include "unorderedLinkedList.h"
    #include "employeeType.h"
    
    using namespace std;
    
    class employeeListType:public unorderedLinkedList<employeeType>
    {
    public: 
    	bool employeeNumberSearch(int id) const;
    
    private:
    	void searchEmployeeList(int id, bool& found,
    							nodeType<employeeType>* &current) const;
    };
    
    void employeeListType::searchEmployeeList(int id, bool& found,
    										  nodeType<employeeType>* &current) const
    {
    	found = false;
    
    	current = first;
    
    	while (current != NULL && !found)	
    		if (current->info.checkEmployeeNumber(id))
    			found = true;
    		else
    			current = current->link;
    }
    
    bool employeeListType::employeeNumberSearch(int id) const
    {
    	bool found = false;
    	nodeType<employeeType> *location;
    
    	searchEmployeeList(id, found, location);
    
    	return found;
    }
    
    #endif
    Code:
    #include <iostream>
    #include <iomanip>
    #include <fstream>
    #include <string>
    #include "employeeType.h"
    #include "employeeListType.h"
    
    using namespace std;
    
    void createEmployeeList(ifstream& infile, employeeListType& empList);
    void displayMenu();
    
    int main()
    {
    	char cChoice;
    	int iEmpID;
    	string sEmpName;
    
    	employeeListType empList;
    
    	ifstream infile;
    
    	infile.open("employees.txt");
    
    	if (!infile)
    	{
    		cout << "The file does not exist. Program ending." << endl;
    		system("pause");
    		return 1;
    	}
    
    	createEmployeeList(infile, empList);
    	infile.close();
    
    	displayMenu();
    	cout << "Enter a choice: ";
    	cin >> cChoice;
    
    	while(cChoice != 'f')
    	{
    		switch (cChoice)
    		{
    			case 'a':
    				empList.print();
    				break;
    
    			case 'b':
    				empList.mergeSort();
    				break;
    				
    			case 'c':
    				//empList.printListReverse();
    				break;
    
    			case 'd':
    				cout << "Enter an Employee ID: ";
    				cin >> iEmpID;
    				cout << endl;
    
    				if (empList.employeeNumberSearch(iEmpID))
    					cout << "Is an employee.";
    				else
    					cout << "Is not an employee.";
    				break;
    
    			case 'e':
    				cout << "Enter the new Employee's number: ";
    				cin >> iEmpID;
    				empList.insertLast(iEmpID);
    				cout << endl;
    
    			//	cout << "Enter the new Employee's Name: ";
    			//	cin >> sEmpName;
    			//	empList.insertLast(sEmpName);
    			//	for (int i = 0; i < sEmpName.length(); i++)								 
    			//	empList.insertLast(sEmpName[i]);	
    				break;
    
    			default:
    				cout << "Invalid choice" << endl;
    		}
    	displayMenu();
    	cout << "Enter a choice: ";
    	cin >> cChoice;
    	}
    
    	cout << fixed << showpoint;
    	cout << setprecision(2);
    
    
    }
    
    void createEmployeeList(ifstream& infile,
    						employeeListType& empList)
    {
    	int id;
    	string employee;
    
    	employeeType newList;
    
    	infile >> id;
    	while (infile)
    	{
    		getline(infile, employee);
    		newList.setEmployeeInfo(id, employee);
    		empList.insertFirst(newList);
    
    		infile >> id;
    	}
    }
    
    void displayMenu()
    {
    	cout << "EMPLOYEE DATABASE" << endl << endl;
    	cout << "a) Display list" << endl;
    	cout << "b) Sort list by Employee Number (ascending)" << endl;
    	cout << "c) Sort list by Employee Number (descending)" << endl;
    	cout << "d) Search for an Employee Number" << endl;
    	cout << "e) Add another Employee" << endl;
    	cout << "f) Quit" << endl;
    }

    Any help that can get me going again is appreciated.


    Thank you,

    -Matthew

  2. #2
    Join Date
    Sep 2011
    Posts
    17

    Re: Multiple Problems

    Here are the errors I am getting:
    Code:
    1>------ Build started: Project: Final, Configuration: Debug Win32 ------
    1>Compiling...
    1>Final.cpp
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(341) : error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'employeeType'
    1>        c:\Program Files\Microsoft Visual Studio 9.0\VC\include\string(150) : see declaration of 'std::operator <'
    1>        c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(330) : while compiling class template member function 'nodeType<Type> *unorderedLinkedList<Type>::mergeList(nodeType<Type> *,nodeType<Type> *)'
    1>        with
    1>        [
    1>            Type=employeeType
    1>        ]
    1>        c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(383) : while compiling class template member function 'void unorderedLinkedList<Type>::recMergeSort(nodeType<Type> *&)'
    1>        with
    1>        [
    1>            Type=employeeType
    1>        ]
    1>        c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(70) : while compiling class template member function 'bool unorderedLinkedList<Type>::search(const Type &) const'
    1>        with
    1>        [
    1>            Type=employeeType
    1>        ]
    1>        c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\employeeListType.h(11) : see reference to class template instantiation 'unorderedLinkedList<Type>' being compiled
    1>        with
    1>        [
    1>            Type=employeeType
    1>        ]
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(341) : error C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const _Elem *' from 'employeeType'
    1>        c:\Program Files\Microsoft Visual Studio 9.0\VC\include\string(140) : see declaration of 'std::operator <'
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(341) : error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'employeeType'
    1>        c:\Program Files\Microsoft Visual Studio 9.0\VC\include\string(130) : see declaration of 'std::operator <'
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(341) : error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'employeeType'
    1>        c:\Program Files\Microsoft Visual Studio 9.0\VC\include\xutility(2262) : see declaration of 'std::operator <'
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(341) : error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'employeeType'
    1>        c:\Program Files\Microsoft Visual Studio 9.0\VC\include\xutility(2072) : see declaration of 'std::operator <'
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(341) : error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'employeeType'
    1>        c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility(99) : see declaration of 'std::operator <'
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(341) : error C2676: binary '<' : 'employeeType' does not define this operator or a conversion to a type acceptable to the predefined operator
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(356) : error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'employeeType'
    1>        c:\Program Files\Microsoft Visual Studio 9.0\VC\include\string(150) : see declaration of 'std::operator <'
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(356) : error C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const _Elem *' from 'employeeType'
    1>        c:\Program Files\Microsoft Visual Studio 9.0\VC\include\string(140) : see declaration of 'std::operator <'
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(356) : error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'employeeType'
    1>        c:\Program Files\Microsoft Visual Studio 9.0\VC\include\string(130) : see declaration of 'std::operator <'
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(356) : error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'employeeType'
    1>        c:\Program Files\Microsoft Visual Studio 9.0\VC\include\xutility(2262) : see declaration of 'std::operator <'
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(356) : error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'employeeType'
    1>        c:\Program Files\Microsoft Visual Studio 9.0\VC\include\xutility(2072) : see declaration of 'std::operator <'
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(356) : error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'employeeType'
    1>        c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility(99) : see declaration of 'std::operator <'
    1>c:\users\mparndsp.cccw\documents\visual studio 2008\projects\final\final\unorderedLinkedList.h(356) : error C2676: binary '<' : 'employeeType' does not define this operator or a conversion to a type acceptable to the predefined operator
    1>Build log was saved at "file://c:\Users\mparndsp.CCCW\Documents\Visual Studio 2008\Projects\Final\Final\Debug\BuildLog.htm"
    1>Final - 14 error(s), 0 warning(s)
    ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
    I was also unable to include the linkedlist.h. If that is needed to help please let me know and I can supply it.


    Thanks,

    Matthew

  3. #3
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Multiple Problems

    You should not put a "using" statement at unrestricted scope in a header file. It's bad form, but it isn't the cause of those errors.

    Can you point out which bits of the above code are on or around lines 341 and 356 of unorderedLinkedList.h?

  4. #4
    Join Date
    Sep 2011
    Posts
    17

    Re: Multiple Problems

    Code:
    template<class Type>
    nodeType<Type>* unorderedLinkedList<Type>::mergeList 
      	            (nodeType<Type>* first1, nodeType<Type>* first2)
    {
    	nodeType<Type> *lastSmall;
    	nodeType<Type> *newHead;
    
    	if (first1 == NULL)
    		return first2;
    	else
    		if (first2 == NULL)
    			return first1;
    		else
    		{
    			if (first1->info < first2->info)  // line 341
    			{
    				newHead = first1;  
    				first1 = first1->link;
    				lastSmall = newHead;
    			}
    			else
    			{
    				newHead = first2;
    				first2 = first2->link;
    				lastSmall = newHead;
    			}
    	
    			while (first1 != NULL && first2 != NULL)
    			{
    				if (first1->info < first2->info)  // line 356
    				{
    					lastSmall->link = first1;
    					lastSmall = lastSmall->link;
    					first1 = first1->link;
    				}
    				else
    				{
    					lastSmall->link = first2;
    					lastSmall = lastSmall->link;
    					first2 = first2->link;
    				}
    			} //end while
    
    			if (first1 == NULL)
    				lastSmall->link = first2;
    			else
    				lastSmall->link = first1;
    
    	   return newHead;
    	}	
    } //end mergeList

  5. #5
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Multiple Problems

    Quote Originally Posted by arndtmatt View Post
    Even when I compile with the base headers I run into errors and the instructor had entered some if (true) statements so that it would compile but I don't think it actually solved the problem.
    Code:
    nodeType
    What is "nodeType?

    As to the error, the error is obvious if you were a C++ programmer and knew template programming. It will be non-obvious if you are not a C++ programmer. That's the problem with learning data structures with such a language as C++. If you don't know C++ to (at the very least) intermediate level, writing data structures in such a language makes it even more difficult.

    Whatever nodeType is, you're calling the template function unorderedLinkedList<Type>::mergeList without specifying fully what the template arguments are. Without seeing nodeType, that is what the compiler is saying to you.
    Code:
    if( head->link != NULL)
    {
    	divideList(head, otherHead);
    	recMergeSort(head);
    	recMergeSort(otherHead);
    head = mergeList(head, otherHead);
    }
    This is not enough information for the compiler to figure out what "Type" is.
    Code:
    head = mergeList<elemType>(head, otherHead);
    But I have a question -- what purpose does the base class "linkedListType" and the header "linkedlist.h" serve? I see all of your code as if linkedListType does absolutely no work whatsoever, and you're reimplementing everything that a linked list does in the derived class. What does "linkedlist.h" do? According to your code, basically nothing as you coded the unordered list from scratch (that's what it seems like to me at first glance).

    For example:
    Code:
    template <class Type>
    void unorderedLinkedList<Type>::deleteNode(const Type& deleteItem)
    Why is this function so complex? Doesn't the base class have a "search" function and a "delete" function, and a "getItem" function? If so, then the code for this function is basically 3 lines not 30 lines.
    Code:
    template <class Type>
    void unorderedLinkedList<Type>::deleteNode(const Type& deleteItem)
    {
        Type* t = searchForMyItem( deleteItem );
        deleteMyItem( t );
    }
    Seriously, if the base class (which you didn't show us) has these functions, why are you not using them? Instead, you reimplemented everything a linked list should do in the derived classes, as if the base class is, well, basically useless.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; November 29th, 2011 at 11:26 AM.

  6. #6
    Join Date
    Sep 2011
    Posts
    17

    Re: Multiple Problems

    Here is linkedlist.h
    Code:
    #ifndef H_LinkedListType
    #define H_LinkedListType
     
    #include <iostream>
    #include <cassert>
    
    using namespace std;
    
    //Definition of the node
    
    template <class Type>
    struct nodeType
    {
    	Type info;
    	nodeType<Type> *link;
    };
    
    //***********************************************************
    // Author: D.S. Malik
    //
    // This class specifies the members to implement an iterator
    // to a linked list.
    //***********************************************************
    
    template <class Type>
    class linkedListIterator
    {
    public:
       linkedListIterator();
         //Default constructor
         //Postcondition: current = NULL;
    
       linkedListIterator(nodeType<Type> *ptr);
         //Constructor with a parameter.
         //Postcondition: current = ptr;
    
       Type operator*();
         //Function to overload the dereferencing operator *.
         //Postcondition: Returns the info contained in the node.
    
       linkedListIterator<Type> operator++();    
         //Overload the preincrement operator.
         //Postcondition: The iterator is advanced to the next 
         //               node.
    
       bool operator==(const linkedListIterator<Type>& right) const; 
         //Overload the equality operator.
         //Postcondition: Returns true if this iterator is equal to 
         //               the iterator specified by right, 
         //               otherwise it returns the value false.
    
       bool operator!=(const linkedListIterator<Type>& right) const; 
         //Overload the not equal to operator.
         //Postcondition: Returns true if this iterator is not  
         //               equal to the iterator specified by  
         //               right; otherwise it returns the value 
         //               false.
    
    private:
       nodeType<Type> *current; //pointer to point to the current 
                                //node in the linked list
    };
    
    template <class Type>
    linkedListIterator<Type>::linkedListIterator()
    {
        current = NULL;
    }
    
    template <class Type>
    linkedListIterator<Type>::
                      linkedListIterator(nodeType<Type> *ptr)
    {
        current = ptr;
    }
    
    template <class Type>
    Type linkedListIterator<Type>::operator*()
    {
        return current->info;
    }
    
    template <class Type>
    linkedListIterator<Type> linkedListIterator<Type>::operator++()   
    {
        current = current->link;
    
        return *this;
    }
    
    template <class Type>
    bool linkedListIterator<Type>::operator==
                   (const linkedListIterator<Type>& right) const
    {
        return (current == right.current);
    }
    
    template <class Type>
    bool linkedListIterator<Type>::operator!=
                     (const linkedListIterator<Type>& right) const
    {    return (current != right.current);
    }
    
    //***********************************************************
    // Author: D.S. Malik
    //
    // This class specifies the members to implement the basic
    // properties of a linked list. This is an abstract class.
    // We cannot instantiate an object of this class.
    //***********************************************************
    
    template <class Type>
    class linkedListType
    {
    public:
        const linkedListType<Type>& operator=
                             (const linkedListType<Type>&);
          //Overload the assignment operator.
    
        void initializeList(); 
          //Initialize the list to an empty state.
          //Postcondition: first = NULL, last = NULL, count = 0;
    
        bool isEmptyList() const;
          //Function to determine whether the list is empty. 
          //Postcondition: Returns true if the list is empty, otherwise
          //    it returns false.
    
        void print() const;
          //Function to output the data contained in each node.
          //Postcondition: none
    
        int length() const;
          //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() const; 
          //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, the program terminates;
          //    otherwise, the first element of the list is returned.
    
        Type back() const; 
          //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, the program
          //               terminates; otherwise, the last  
          //               element of the list is returned.
    
        virtual bool search(const Type& searchItem) const = 0;
          //Function to determine whether searchItem is in the list.
          //Postcondition: Returns true if searchItem is in the list,
          //    otherwise the value false is returned.
    
        virtual void insertFirst(const Type& newItem) = 0;
          //Function to insert newItem at the beginning of the list.
          //Postcondition: first points to the new list, newItem is
          //    inserted at the beginning of the list, last points to
          //    the last node in the list, and count is incremented by
          //    1.
    
        virtual void insertLast(const Type& newItem) = 0;
          //Function to insert newItem at the end of the list.
          //Postcondition: first points to the new list, newItem is
          //    inserted at the end of the list, last points to the
          //    last node in the list, and count is incremented by 1.
    
        virtual void deleteNode(const Type& deleteItem) = 0;
          //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,
          //    last points to the last node of the updated list, and
          //    count is decremented by 1.
    
        linkedListIterator<Type> begin();
          //Function to return an iterator at the beginning of the 
          //linked list.
          //Postcondition: Returns an iterator such that current is set
          //    to first.
    
        linkedListIterator<Type> end();
          //Function to return an iterator one element past the 
          //last element of the linked list. 
          //Postcondition: Returns an iterator such that current is set
          //    to NULL.
    
        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.  
    
    	//virtual void deleteAll(const Type& deleteItem) = 0;
    	   //Delete all occurences of a given element
    
    	//virtual void deleteSmallest() = 0;
    	   //Find and delete the node with the smallest info
    
    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() const
    {
        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 the 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>
    void linkedListType<Type>::print() const
    {
        nodeType<Type> *current; //pointer to traverse the list
    
        current = first;    //set current so that it points to 
                            //the first node
        while (current != NULL) //while more data to print
        {
            cout << current->info << " ";
            current = current->link;
        }
    }//end print
    
    template <class Type>
    int linkedListType<Type>::length() const
    {
        return count;
    }  //end length
    
    template <class Type>
    Type linkedListType<Type>::front() const
    {   
        assert(first != NULL);
    
        return first->info; //return the info of the first node	
    }//end front
    
    template <class Type>
    Type linkedListType<Type>::back() const
    {   
        assert(last != NULL);
    
        return last->info; //return the info of the last node	
    }//end back
    
    template <class Type>
    linkedListIterator<Type> linkedListType<Type>::begin()
    {
        linkedListIterator<Type> temp(first);
    
        return temp;
    }
    
    template <class Type>
    linkedListIterator<Type> linkedListType<Type>::end()
    {
        linkedListIterator<Type> temp(NULL);
    
        return temp;
    }
    
    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 the 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
    
            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
                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
    
    template <class Type>
    linkedListType<Type>::~linkedListType() //destructor
    {
       destroyList();
    }//end destructor
    
    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
    linkedList.h and unorderedLinkedList.h are files that were available for us to use. nodeType can be found defined at the top of linkedList.h. I believe unorderedLinkedList using linkedList for the iterators then uses its own functions to work with un ordered lists.

  7. #7
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Multiple Problems

    Quote Originally Posted by arndtmatt View Post
    Here is linkedlist.h
    My question is why the base class hasn't implemented search(), insertFirst(), insertLast(), etc.? Why are these left to the derived class to implement? There should be a base version of search(), insertFirst(), etc. as there is really no specialty to these functions for a linked list.

    Now what if I just want a simple linked list? I have to derive and implement what the base class was supposed to do? Does that make sense to you? That's like having the garbage truck pull up to your house, and you're the one picking up the garbage and throwing it into the truck instead of the garbage men.

    For example:
    Code:
    Node* cur = headNode;
    while (cur != tailNode)
    {
       if (cur->getData() == Data_I_Am_Looking_For )
           return cur;
       cur = cur->nextNode;
    }
    return NULL;
    That is the basic design of a linked list search function, and this should have been part of the base class implementation.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; November 29th, 2011 at 12:42 PM.

  8. #8
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Multiple Problems

    In addition, the copyList function does too much work. It is a two line loop to copy a list into another list.
    Code:
    template <class Type>
    void linkedListType<Type>::copyList
                       (const linkedListType<Type>& otherList) 
    {
        destroyListl();  // remove all nodes from this list
        linkedListIterator<Type> it = otherList.begin();
        while (it != otherList.end() )
       {
             insertLast(*it );  // add item to this list
             ++it;  // go to next item in otherList
       }
    }
    That is psuedo-code for how copyList should look like. All of this other stuff with checking for NULLs and a bunch of other things need not be done at all. All that needs to be done is go through otherlist, and keep adding nodes to this until there are no more nodes in otherlist.

    Does your teacher know what "code reuse" means?

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; November 29th, 2011 at 01:01 PM.

  9. #9
    Join Date
    Sep 2011
    Posts
    17

    Re: Multiple Problems

    I understand what you are saying about the base class not implementing the basic functions. These were header files included with the book "Data Structure using C++" so the instructor didn't write them himself. I do appreciate you giving suggestions on how to make the code length reduced. Honestly at this point I just need some help with the errors I am getting trying to sort the data in either ascending or descending order after it is read into memory. The mergeList piece seems to be causing me the problems. Any ideas on how I can adjust the code so I do not get the errors? I tried the earlier suggestion:
    Code:
    head = mergeList<elemType>(head, otherHead);
    It did not help but instead gave another error:
    unorderedLinkedList.h(392) : error C2275: 'Type' : illegal use of this type as an expression

    I also changed it from elemType to Type (that was a mistake on my part)

  10. #10
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Multiple Problems

    Quote Originally Posted by arndtmatt View Post
    I understand what you are saying about the base class not implementing the basic functions. These were header files included with the book "Data Structure using C++" so the instructor didn't write them himself.
    Maybe, but do you know we only care about the code given, and really, it makes no sense to me. Why is copyList implemented in the base class, and assumes how the nodes were linked together, if the responsibility to link the nodes together is in the derived class?? Looks like the author may know C++ syntax, but has no idea about program design.

    Secondly, even if what you say is true, why is your employeeListType class trying to do internal linked-list coding? Shouldn't it just call the search function for unorderedLinkedList (the parent class), or better yet, use the iterator? Your code should not be doing things like this:
    Code:
    while (current != NULL && !found)	
    		if (current->info.checkEmployeeNumber(id))
    			found = true;
    		else
    current = current->link;
    }
    That code in red should not be in the derived class, and to be blunt, not correct at all.

    All you know in the derived class should be the iterator, and it is the iterator you increment to the next item. How the iterator works is of no concern to the employeeListType class. The iterator should point to begin(), and iterate until end() is reached or the item has been found, and use operator* to get the data (not use "info").

    What if the base class changes the way to get the info (even change the variable name from "info" to "linked_info"), or changes the way to get to the next node? Your derived employeeListType class now is broken, and has to be changed to match what the base class is doing. That is not good design -- the derived classes shouldn't change, regardless of how the base class may change.

    In other words, the employeeListType shouldn't know or care how the nodes are put together, or the internals of the base class. It should defer all of this knowledge to the parent class, which knows how to search.
    Code:
    linkedListIterator<employeeType> startIt = this->begin();
    linkedListIterator<employeeType> endIt = this->end();
    while (startIt != endIt )
    {
       if ((*startIt).checkEmployeeNumber(id) )
           return true;
       ++startIt;
    }
    return false;
    Now, regardless of whether the linked list base class changes the way iterators increment internally, or whether the name is no longer "info", etc. this code will not break. As long as begin(), end(), operator*, and operator++ do what they're supposed to do, that's all there is to it.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; November 29th, 2011 at 05:35 PM.

  11. #11
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Multiple Problems

    Also, what compiler are you using? I see no issue with the code, as I was able to compile this with no problems:
    Code:
    #include <iostream>
    #include <cassert>
    
    //Definition of the node
    
    template <class Type>
    struct nodeType
    {
    	Type info;
    	nodeType<Type> *link;
    };
    
    template <class Type>
    class linkedListIterator
    {
    public:
       linkedListIterator();
       linkedListIterator(nodeType<Type> *ptr);
       Type operator*();
       linkedListIterator<Type> operator++();    
       bool operator==(const linkedListIterator<Type>& right) const; 
       bool operator!=(const linkedListIterator<Type>& right) const; 
    
    private:
       nodeType<Type> *current; //pointer to point to the current 
                                //node in the linked list
    };
    
    template <class Type>
    linkedListIterator<Type>::linkedListIterator()
    {
        current = NULL;
    }
    
    template <class Type>
    linkedListIterator<Type>::
                      linkedListIterator(nodeType<Type> *ptr)
    {
        current = ptr;
    }
    
    template <class Type>
    Type linkedListIterator<Type>::operator*()
    {
        return current->info;
    }
    
    template <class Type>
    linkedListIterator<Type> linkedListIterator<Type>::operator++()   
    {
        current = current->link;
    
        return *this;
    }
    
    template <class Type>
    bool linkedListIterator<Type>::operator==
                   (const linkedListIterator<Type>& right) const
    {
        return (current == right.current);
    }
    
    template <class Type>
    bool linkedListIterator<Type>::operator!=
                     (const linkedListIterator<Type>& right) const
    {    return (current != right.current);
    }
    
    template <class Type>
    class linkedListType
    {
    public:
        const linkedListType<Type>& operator=
                             (const linkedListType<Type>&);
          //Overload the assignment operator.
    
        void initializeList(); 
    
        bool isEmptyList() const;
    
        void print() const;
    
        int length() const;
          //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() const; 
    
        Type back() const; 
        virtual bool search(const Type& searchItem) const = 0;
        virtual void insertFirst(const Type& newItem) = 0;
        virtual void insertLast(const Type& newItem) = 0;
        virtual void deleteNode(const Type& deleteItem) = 0;
        linkedListIterator<Type> begin();
    
        linkedListIterator<Type> end();
        linkedListType(); 
        linkedListType(const linkedListType<Type>& otherList); 
          //copy constructor
    
        ~linkedListType();   
    
    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() const
    {
        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 the 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>
    void linkedListType<Type>::print() const
    {
        nodeType<Type> *current; //pointer to traverse the list
    
        current = first;    //set current so that it points to 
                            //the first node
        while (current != NULL) //while more data to print
        {
            cout << current->info << " ";
            current = current->link;
        }
    }//end print
    
    template <class Type>
    int linkedListType<Type>::length() const
    {
        return count;
    }  //end length
    
    template <class Type>
    Type linkedListType<Type>::front() const
    {   
        assert(first != NULL);
    
        return first->info; //return the info of the first node	
    }//end front
    
    template <class Type>
    Type linkedListType<Type>::back() const
    {   
        assert(last != NULL);
    
        return last->info; //return the info of the last node	
    }//end back
    
    template <class Type>
    linkedListIterator<Type> linkedListType<Type>::begin()
    {
        linkedListIterator<Type> temp(first);
    
        return temp;
    }
    
    template <class Type>
    linkedListIterator<Type> linkedListType<Type>::end()
    {
        linkedListIterator<Type> temp(NULL);
    
        return temp;
    }
    
    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 the 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
    
            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
                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
    
    template <class Type>
    linkedListType<Type>::~linkedListType() //destructor
    {
       destroyList();
    }//end destructor
    
    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; 
    }
    
    template <class Type>
    class unorderedLinkedList: public linkedListType<Type>
    {
    public:
    	bool search(const Type& searchItem) const;
    
    	void insertFirst(const Type& newItem);
    
    	void insertLast(const Type& newItem);
    
    	void deleteNode(const Type& deleteItem);
    
    	void deleteAll(const Type& deleteItem);
    
    	void deleteSmallest();
    
    	void printListReverse() const;
    
    	void mergeSort();
    
    private:
    	void reversePrint(nodeType<Type> *current) const;
    
    	void divideList(nodeType<Type>* first1, 
    		nodeType<Type>* &first2);
    
    	nodeType<Type>* mergeList(nodeType<Type>* first1, 
    		nodeType<Type>* first2);
    
    	void recMergeSort(nodeType<Type>* &head);
    };
    
    template <class Type>
    bool unorderedLinkedList<Type>::
    search(const Type& searchItem) const
    {
    	nodeType<Type> *current; //pointer to traverse the list
    	bool found = false;
    
    	current = first; //set current to point to the first 
    	//node in the list
    
    	while (current != NULL && !found)    //search the list
    		if(true)// jk       if (current->info == searchItem) //searchItem is found
    			found = true;
    		else
    			current = current->link; //make current point to
    	//the next node
    	return found; 
    }//end search
    
    template <class Type>
    void unorderedLinkedList<Type>::insertFirst(const Type& newItem)
    {
    	nodeType<Type> *newNode; //pointer to create the new node
    
    	newNode = new nodeType<Type>; //create the new node
    
    	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;
    }//end insertFirst
    
    template <class Type>
    void unorderedLinkedList<Type>::insertLast(const Type& newItem)
    {
    	nodeType<Type> *newNode; //pointer to create the new node
    
    	newNode = new nodeType<Type>; //create the new node
    
    	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 in the list
    		count++;        //increment count
    	}
    }//end insertLast
    
    
    template <class Type>
    void unorderedLinkedList<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; the list is empty. 
    		std::cout << "Cannot delete from an empty list."
    		<< std::endl;
    	else
    	{
    		if(true)//jk  if (first->info == deleteItem) //Case 2 
    		{
    			current = first;
    			first = first->link;
    			count--;
    			if (first == NULL)    //the list has 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 (current != NULL && !found)
    			{
    				if(true)//                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
    				std::cout << "The item to be deleted is not in "
    				<< "the list." << std::endl;
    		}//end else
    	}//end else
    }//end deleteNode
    
    
    template <class Type>
    void unorderedLinkedList<Type>::deleteAll(const Type& deleteItem)
    {
    	nodeType<Type> *current; //pointer to traverse the list
    	nodeType<Type> *trailCurrent; //pointer just before current
    
    	if (first == NULL)    //Case 1; list is empty. 
    		std::cout << "Can not delete from an empty list." << std::endl;
    	else
    	{
    		current = first;
    
    		while (current != NULL)
    		{
    			if(true)//jk  			if (current->info == deleteItem) 
    			{
    				if (current == first)
    				{
    					first = first->link;
    					delete current;
    					current = first;
    					if(first == NULL)
    						last = NULL;
    				}
    				else
    				{
    					trailCurrent->link = current->link;
    
    					if(current == last)
    						last = trailCurrent;
    
    					delete current;
    
    					current = trailCurrent-> link;
    				}
    			}
    			else
    			{ 
    				trailCurrent = current;
    				current = current->link;
    			}
    		} // end while
    	}
    } //end deleteAll
    
    template <class Type>
    void unorderedLinkedList<Type>::deleteSmallest()
    {
    	nodeType<Type> *current; 
    	nodeType<Type> *trailCurrent; 
    
    	nodeType<Type> *small; 
    	nodeType<Type> *trailSmall;
    
    	if (first == NULL)
    		cout << "Cannot delete from an empty list." << endl;
    	else
    		if (first->link == NULL)
    		{
    			first = NULL;
    			delete last;
    			last = NULL;
    		}
    		else
    		{
    			small = first;
    			trailCurrent = first;
    			current = first->link;
    
    			while (current != NULL)
    			{
    				if(true)//jk				if (small->info > current->info)
    				{
    					trailSmall = trailCurrent;
    					small = current;
    				}
    
    				trailCurrent = current;
    				current = current->link;
    			}
    
    			if (small == first)
    				first = first->link;
    			else
    			{
    				trailSmall->link = small->link;
    
    				if (small == last)
    					last = trailSmall;
    			}
    
    			delete small;
    		}
    }
    
    template<class Type>
    void unorderedLinkedList<Type>::mergeSort()
    {
    	recMergeSort(first);
    }
    
    template<class Type>
    void unorderedLinkedList<Type>::divideList(
    	nodeType<Type>* first1, 
    	nodeType<Type>* &first2)
    {
    	nodeType<Type>* middle;
    	nodeType<Type>* current;
    
    	if (first1 == NULL) // if (true)
    		first2 = NULL;
    	else if(first1->link == NULL)
    		first2 = NULL;
    	else
    	{
    		middle = first1;
    		current = first1->link;
    		if (current != NULL)
    			current = current->link;
    
    		while (current != NULL)
    		{
    			middle = middle->link;
    			current = current->link;
    			if (current != NULL)
    				current = current->link;
    		} //end while
    
    		first2 = middle->link;
    		middle->link = NULL;
    
    	} //end else
    } //end divideList
    
    
    
    template<class Type>
    nodeType<Type>* unorderedLinkedList<Type>::mergeList 
    (nodeType<Type>* first1, nodeType<Type>* first2)
    {
    	nodeType<Type> *lastSmall;
    	nodeType<Type> *newHead;
    
    	if (first1 == NULL)
    		return first2;
    	else
    		if (first2 == NULL)
    			return first1;
    		else
    		{
    			if (first1->info < first2->info)
    			{
    				newHead = first1;  
    				first1 = first1->link;
    				lastSmall = newHead;
    			}
    			else
    			{
    				newHead = first2;
    				first2 = first2->link;
    				lastSmall = newHead;
    			}
    
    			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)
    				lastSmall->link = first2;
    			else
    				lastSmall->link = first1;
    
    			return newHead;
    		}	
    } //end mergeList
    
    
    template<class elemType>
    void unorderedLinkedList<elemType>::recMergeSort(
    	nodeType<elemType>* &head)
    {
    	nodeType<elemType> *otherHead;
    
    	if (head != NULL)
    		if( head->link != NULL)
    		{
    			divideList(head, otherHead);
    			recMergeSort(head);
    			recMergeSort(otherHead);
    			head = mergeList(head, otherHead);
    		}
    } //end recMergeSort
    
    template<class Type>
    void unorderedLinkedList<Type>::reversePrint
    (nodeType<Type> *current) const
    {
    	if (current != NULL)
    	{
    		reversePrint(current->link);
    		std::cout << current->info << " ";
    	}
    }
    
    template<class Type>
    void unorderedLinkedList<Type>::printListReverse() const
    {
    	reversePrint(first);
    	std::cout << endl;
    }
    
    int main()
    {
    	unorderedLinkedList<int> ul;
    	ul.deleteAll(1);
    	ul.mergeSort();
    }
    This instantiates the template and calls mergeSort(). There are no errors when compiling with VS 2008.

    Regards,

    Paul McKenzie

  12. #12
    Join Date
    Sep 2011
    Posts
    17

    Re: Multiple Problems

    I'm using VS C++ 2008 express

  13. #13
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Multiple Problems

    Quote Originally Posted by arndtmatt View Post
    I'm using VS C++ 2008 express
    Take the code I posted and compile it. Does it compile?

    Regards,

    Paul McKenzie

  14. #14
    Join Date
    Sep 2011
    Posts
    17

    Re: Multiple Problems

    Yes it did. I worked through some of the problems I had and can now get every function to work but adding a new employee. I'm working on the function to overload the extraction operator but am having problems accessing the private variables.

Posting Permissions

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


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)