Thread: Linked list with two class types within template.

  1. #1
    Registered User
    Join Date
    Dec 2001
    Posts
    38

    Linked list with two class types within template.

    I'm having a problem getting a program to run for class. We are using a specific list class our Professor rearranged himself. We have to use it. It is of template type with two classes imbedded such as template<class TYPE,class KTYPE>. I have enclose my main and the header file for the list class. If someone could tell me why my compiler won't build I would be forever grateful. Here is the main and header:

    #include <iostream.h>
    #include "list.h"

    void main()
    {
    List<int,int> s;
    int i;
    for (i=1;i<=9;i++)
    s.addNode(i);
    s.traverse();
    }

    By the way, I've only named the list and tried to build it and print it with this. I narrowed it down to the bare essentials to try to figure out the error.

    Here is the list class.


    #include <iostream.h>

    // ************************************************** ******************
    // Declaration of a node
    // ************************************************** ******************
    template <class TYPE>
    struct NODE
    {
    TYPE data;
    NODE *link;
    };

    // ************************************************** *******************
    // Declaration of list class
    // ************************************************** *******************

    template <class TYPE, class KTYPE>
    class List
    {
    private:
    NODE<TYPE> *head; // pointer to the first node
    NODE<TYPE> *pos; // pointer to the current node
    NODE<TYPE> *rear; // pointer to the last node
    int count; // the number of nodes
    bool _insert(NODE<TYPE> *pPre, const TYPE &dataIn);
    // insert a new node after node *pPre
    void _delete(NODE<TYPE> *pPre, NODE<TYPE> *&pLoc, TYPE &dataOut);
    // delete node *pLoc, dataOut = pLoc->data
    bool _search(NODE<TYPE> *&pPre, NODE<TYPE> *&pLoc, const KTYPE &key);
    // search for the node containing a value
    // equal to key
    public:
    List(void); // Constructor for creating an empty list
    ~List(void); // Destructor
    int addNode(const TYPE &dataIn);
    // insert a new node
    bool removeNode(const KTYPE &key, TYPE &dataOut);
    // remove the node storing key with data of
    // the node returned through dataOut
    bool retrieveNode(const KTYPE &key, TYPE &dataOut);
    // retrieve the data at the node having key
    bool getNext (int fromWhere, TYPE &dataOut);
    // return the data from the next node
    bool emptyList(void){ return ( count == 0 ); }
    // test if the list is empty
    bool fullList(void); // test to see if the list is full; that is,
    // no more memory to add an additional node
    int listCount(void) { return count; }
    // return the number of nodes
    void traverse(void); // traverse list displaying keys
    };

    // ************************************************** *****************
    // The following are private member function definitions.
    // ************************************************** *****************

    template <class TYPE, class KTYPE>
    bool List<TYPE, KTYPE>::_insert(NODE<TYPE> *pPre, const TYPE &dataIn)
    // -------------------------------------------------------------------
    // Purpose: This function inserts a new node either at the beginning
    // or after the node *pPre.
    // -------------------------------------------------------------------
    {
    // Create a new node with pNew pointing to the object.
    NODE<TYPE> *pNew;
    if (!(pNew = new NODE<TYPE>))
    return false;

    pNew->data = dataIn;

    if (pPre == NULL) // empty list
    {
    pNew->link = head;
    head = pNew;
    }
    else // non-empty list
    {
    pNew->link = pPre->link;
    pPre->link = pNew;
    }

    if (pNew->link == NULL)
    rear = pNew;

    ++count;
    return true;
    }

    template <class TYPE, class KTYPE>
    void List<TYPE, KTYPE>::_delete(NODE<TYPE> *pPre, NODE<TYPE> *&pLoc, TYPE &dataOut)
    // -------------------------------------------------------------------
    // Purpose: This function deletes node *pLoc
    // -------------------------------------------------------------------
    {
    // Return the data value of the node to be deleted.
    dataOut = pLoc->data;
    if (pPre == NULL) // delete the first node
    head = pLoc->link;
    else
    pPre->link = pLoc->link;

    if (pLoc->link == NULL)
    rear = pPre;

    delete pLoc;
    --count;
    return;
    }

    template <class TYPE, class KTYPE>
    bool List<TYPE, KTYPE>::_search (NODE<TYPE> *&pPre, NODE<TYPE> *&pLoc, const KTYPE &key )
    // ------------------------------------------------------------------
    // Purpose: Search for the existence of a node containing a value
    // equal to key.
    // ------------------------------------------------------------------
    {


    // Initialize pointers pPre and pLoc.
    pPre = NULL;
    pLoc = head;
    if (count == 0)
    return false;
    // Continue to loop until a target either matches key, the target is less
    // than key, or the end of the list is encountered.
    if (key > rear->data.key)
    {
    pPre = rear;
    return false;
    }

    while (key > pLoc->data.key)
    {
    pPre = pLoc;
    pLoc = pLoc->link;
    }

    if (key == pLoc->data.key)
    return true;
    return false;
    }

    // ************************************************** *****************
    // The following are public member function definitions.
    // ************************************************** *****************

    template <class TYPE, class KTYPE>
    List<TYPE, KTYPE>::List(void)
    // -------------------------------------------------------------------
    // Purpose: This constructor initializes the member variables
    // head, pos and count.
    // -------------------------------------------------------------------
    {
    head = NULL;
    pos = NULL;
    rear = NULL;
    count = 0;
    }

    template <class TYPE, class KTYPE>
    List<TYPE, KTYPE>::~List(void)
    // -------------------------------------------------------------------
    // Purpose: This destructor removes all unwanted storage of nodes
    // before the object of class List ceases to exist.
    // -------------------------------------------------------------------
    {
    NODE<TYPE> *deletePtr; // local pointer
    while( head != NULL ) // Continue to delete nodes until the list is empty
    {
    deletePtr = head;
    head = head->link;
    delete deletePtr;
    }
    count = 0;
    }

    template <class TYPE, class KTYPE>
    int List<TYPE, KTYPE>::addNode(const TYPE &dataIn)
    // ----------------------------------------------------------------
    // Purpose: Public function for inserting a new node.
    // ----------------------------------------------------------------
    {
    bool found;
    bool success;
    NODE<TYPE> *pPre;
    NODE<TYPE> *pLoc;

    // Search the position where a new node is to be inserted.
    found = _search(pPre, pLoc, dataIn.key);
    if(found) // Duplicate key exist.
    return (+1);

    // attempt to insert a new node within the linked list.
    success = _insert(pPre, dataIn);
    if (!success)
    return (-1);
    return (0);
    }

    template <class TYPE, class KTYPE>
    bool List<TYPE, KTYPE>::removeNode(const KTYPE &key, TYPE &dataOut)
    // ------------------------------------------------------------------
    // Purpose: Public function for removing a node from within a
    // linked list with data of the node returned through
    // dataOut.
    // ------------------------------------------------------------------
    {
    bool found;
    NODE<TYPE> *pPre;
    NODE<TYPE> *pLoc;

    // Search for a node containing the value of key.
    found = _search(pPre, pLoc, key);

    if(found)
    _delete(pPre, pLoc, dataOut);
    return found;
    }

    template <class TYPE, class KTYPE>
    bool List<TYPE, KTYPE>::retrieveNode(const KTYPE &key, TYPE &dataOut)
    // ------------------------------------------------------------------
    // Purpose: This function retrieves the data at a node having key
    // ------------------------------------------------------------------
    {
    bool found;
    NODE<TYPE> *pPre;
    NODE<TYPE> *pLoc;

    found = _search(pPre, pLoc, key);

    if (found)
    dataOut = pLoc->data;
    return found;
    }

    template <class TYPE, class KTYPE>
    bool List<TYPE, KTYPE>::getNext (int fromWhere, TYPE &dataOut)
    // --------------------------------------------------------------------
    // Purpose: This public function returns the data from the next node
    // in the linked list.
    // --------------------------------------------------------------------
    {
    // Test if fromWhere is at the beginning of the linked list.
    if(fromWhere == 0)
    {
    if(count == 0)
    return false;
    else
    {
    pos = head;
    dataOut = pos->data;
    return true;
    }
    }
    else // Continue from the current position
    {
    if(pos->link == NULL)
    return false;
    else
    {
    pos = pos->link;
    dataOut = pos->data;
    return true;
    }
    }
    }

    template <class TYPE, class KTYPE>
    bool List<TYPE, KTYPE>::fullList()
    // ------------------------------------------------------------------
    // Purpose: Provides a test to see if the list is full; that is,
    // no further memory exist to add an additional node.
    // ------------------------------------------------------------------

    {
    NODE<TYPE>* pNew;
    if (pNew = new NODE<TYPE>) // successful memory allocation
    {
    delete pNew;
    return false;
    }
    return true;
    }

    template <class TYPE, class KTYPE>
    void List<TYPE, KTYPE>::traverse(void)
    // -----------------------------------------------------------------
    // Purpose: Traverses the linked list displaying the value of
    // the key from each node.
    // -----------------------------------------------------------------
    {
    NODE<TYPE> *pNext = head;

    // Display the keys from each node of the linked list.
    while(pNext)
    {
    cout << pNext->data.key << " | ";
    pNext = pNext->link;
    }
    cout << endl;
    }


    Thanks for any help.
    SilasP

  2. #2
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    I don't know whether it's due to the formatting of the board, but

    // **************************************************
    ******************

    is a one line comment and a meaningless line.

    Also, where does it state that your TYPE has a key member. Doing a quick scan of your code, it appears that you're trying to instantiate a list of ints, int's won't have any members.

  3. #3
    Registered User
    Join Date
    Dec 2001
    Posts
    38
    The comment line is due to pasting. I'm not sure what you mean about instantiating. The only thing I'm trying to do is make an integer list from 1-9 and output the list so far. The key would be the second int type and used for searching the list. Does this help clarify anything? I hope it might help.
    SilasP

  4. #4
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    what errors are you getting

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Function template has already been defined
    By Elysia in forum C++ Programming
    Replies: 19
    Last Post: 04-14-2009, 10:17 AM
  2. Default class template problem
    By Elysia in forum C++ Programming
    Replies: 5
    Last Post: 07-11-2008, 08:44 AM
  3. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  4. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  5. error: template with C linkage
    By michaels-r in forum C++ Programming
    Replies: 3
    Last Post: 05-17-2006, 08:11 AM