Trouble modifing my program from templates to link lists

This is a discussion on Trouble modifing my program from templates to link lists within the C++ Programming forums, part of the General Programming Boards category; I have to modify this program which uses templates to use only linked lists and I am having a world ...

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    1

    Trouble modifing my program from templates to link lists

    I have to modify this program which uses templates to use only linked lists and I am having a world of trouble trying to figure out how to start. I am quite horrible with linked lists and would appreciate any kind of help. It is n implementation file that recieves any kind of data and then sorts it. And I can't figure out how I would make a linked list do that. Or what kind of code I would write to make it do that. I have read a couple of chapters in my C++ book and they are anything but helpful. I have spent a couple of days working on it and this is my last resort. Thanks.

    Code:
    #include <iostream>
    
    using namespace std;
    
    template<class ItemType>
    GLista<ItemType>::GList()  //Constructor
    {
     length = 0;
     sorted = false;
    }
    
    template<class ItemType>
    bool GLista<ItemType>::IsEmpty() const
    {
     return(length == 0);
    }
    
    template<class ItemType>
    bool GLista<ItemType>::IsFull() const
    {
     return(length == MAX_LENGTH);
    }
    
    template<class ItemType>
    int GLista<ItemType>::Length() const
    {
     return length;
    }
    
    template<class ItemType>
    void GLista<ItemType>::Insert(/* in */ ItemType item)
    {
     data[length] = item;
     length++;
     sorted = true;
    }
    
    template<class ItemType>
    void GLista<ItemType>::Delete(/* in */ ItemType item)
    {
     int index = 0;
    
     while(index < length && item != data[index])
      index++;
    
     if(index < length)
     {
      if(sorted)
      {
       while(index <= length - 2)
       {
        data[index] = data[index + 1];
        index++;
       }
      }
      else
       data[index] = data[length - 1];
    
      length--;
     }
    }
    
    template<class ItemType>
    bool GLista<ItemType>::IsPresent(/* in */ ItemType item) const
    {
     int index = 0;
    
     while(index < length && item != data[index])
     index++;
    
     return(index < length);
    }
    
    template<class ItemType>
    void GLista<ItemType>::SelSort()
    {
     ItemType temp;
     int passCount;
     int searchIndex;
     int minIndex;
    
     for(passCount = 0; passCount < length - 1; passCount++)
     {
      minIndex = passCount;
      for(searchIndex = passCount + 1; searchIndex < length; searchIndex++)
       if(data[searchIndex] < data[minIndex])
        minIndex = searchIndex;
    
      temp = data[minIndex];
      data[minIndex] = data[passCount];
      data[passCount]= temp;
     }
     sorted = true;
    }
    
    template<class ItemType>
    void GLista<ItemType>::Print() const
    {
     int index;
    
     for(index = 0; index < length; index++)
      cout << data[index] << endl;
    }

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,803
    Code:
    template<class ItemType>
    GLista<ItemType>::GList()  //Constructor
    {
     length = 0;
     sorted = false;
    }
    Constructors must have the same name as the class. So, either the name of the class must be GList or the constructor must be GLista.

    Well, it looks like you started off with an array based container implementation and now wish to move to a list based container correct? Well, for starters, lists and arrays are two very different things. You can't just slap a "list" label on an array implementation and have it work like a list should work. You are going to need to start from scratch. It would also be helpful to have a complete class declaration to look at and not just the function themselves, one for a basic double-linked list might look something like:

    Code:
    template <class T> struct node
    {
        T data;
        node *next;
        node *previous;
        node(const T& item)
        {
            next = previous = NULL;
            data = item;
        }
        node()
        {
            next = previous = NULL;
        }
    };
    
    template <class T>
    class GList
    {
        node<T> *head;
        node<T> *tail;
    public:
        GList()
        {
            head = tail = NULL;
        }
        ~GList()
        {
            node<T> *current = head;
            node<T> *temp;
            while( current != NULL )
            {
                temp = current;
                current = current->next;
                delete temp;
            }
        }
        void push_back(const T& data)
        {
            node<T> *pNew = new node<T>(data);
            if( pNew )
            {
                if( head == NULL )
                {
                    // This is the first node added to list, set head/tail pointers
                    head = tail = pNew;
                }
                else
                {
                    // Previous nodes have been added, add this node to end of list
                    tail->next = pNew;
                    pNew->previous = tail;
                    tail = pNew;
                }
            }
            else
            {
                // There was an error allocating memory, display error message
                cerr << "GList::push_back - Memory allocation error!" << endl;
            }
        }
    };
    You'll need to convert all your necessary functions from array based implementations into a linked list implementation. I was nice and demonstrated a "push_back" function that adds a new node to the end of the list, you'll need to do the rest. Since you are using templates, all that probably needs to go in a header file of some kind. You'll need to decide what to keep from your old array implementation and what to throw out. Obviously, a list can keep growing (until no more memory is available) so a function like IsFull really doesn't make sense with a list unless you wish to place an arbitrary restriction on its size. When it comes time to use your GList class, you can start out using it like this:

    Code:
    GList<int> intList;
    
    intList.push_back(10);  // Add element to linked list
    intList.push_back(20);  // Add element to linked list
    intList.push_back(30);  // Add element to linked list
    intList.push_back(40);  // Add element to linked list
    Last edited by hk_mp5kpdw; 03-26-2005 at 09:13 PM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 04-12-2009, 04:21 AM
  2. Recursion program trouble... ?
    By Beachblue in forum C Programming
    Replies: 7
    Last Post: 06-19-2008, 01:43 PM
  3. trouble with file i/o program.
    By Pyroteh in forum C++ Programming
    Replies: 7
    Last Post: 01-09-2007, 09:29 PM
  4. Link lists as datastructure
    By stseitli in forum C Programming
    Replies: 13
    Last Post: 07-09-2002, 07:34 AM
  5. double link lists
    By rumi_red in forum C++ Programming
    Replies: 3
    Last Post: 10-30-2001, 09:13 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21