ADT list

[RachelAnderson]

Hi guys, I am trying to implement an ADT list, but when I compile it, it freezes and the following message appears:

"xxx.exe has encountered a problem and needs to close. We are sorry for the inconvenience."
At the moment I am using Dev-C++ 4.9.8.0, and I am not sure if the compiler is responsible for this error.I know its not the best choice, but I dont have another at this computer at the moment.

Here is the code:

#include<iostream>
#include<stdlib.h>
#include<ctype.h>
using namespace std;
template<class Item>
class LIST
 {
    private:
    struct node
    {
     Item item;
     node *next;
     node(Item x, node* t)
      {
       item=x;
       next=t;
      }
    };
    typedef node *list;
    list head;
    
    Item read_element()
    {
     Item x;
     x=cin.get();
     while(isspace(x))
     x=cin.get();
     return (x);
    }
    void deleteLISTcontent()
    {
      for(list t= head; t!=0; head=t)
      {
        t=head->next;
        delete head;
      }
    };
   public:
    LIST()
    {
    head=0;
    }
    LIST(const LIST& rhs)
    {
      head=0;
      *this=rhs;
    }
    
    LIST& operator=(const LIST& rhs)
    {
     if(this==&rhs)
      return *this;
     deleteLISTcontent();
     list t=rhs.head,p,q;
     if(t!=0)
      {
       head=new node(t->item,0);
       t=t->next;
       p=head;
       while(t!=0)
         {
         q=new node(t->item,0);
         p->next=q;
         p=q;
         t=t->next;
        }
       }
     return *this;
    }
    
    ~LIST()
    {
        deleteLISTcontent();
    }
     int null()
    {
    return head==0;
    }
    
 void read()
    {
    int i=0, j;Item x;  list p;
    Item a[80];
    x=read_element();
    
       while((x=read_element()) != '0')
        a[i++]=x;
   
    if(i>0)
     p=new node(a[--i],p);
     while(i>0)
      p=new node(a[--i],p);
    head=p;
    }
 void print()
        {
         cout<<"(";
         for(list t=head; t!=0;t=t->next)
          cout<<t->item;
         cout<<")"<<endl;
        }
};
int main()
{
    LIST<char> L,M;
    
    cout<<"enter list ";
    L.read();
   
    cout<<"entered list is"<<" ";
    L.print();
    cout<<"second object is";
   
    system ("pause");
    return 0;
    
}

[Dacster13]

tried it on Dev-C++ 4.9.9.2 and I'm not getting that error message. It crashes after printing though, and the first character prints out wrong too. I hope that helps. :P

[RachelAnderson]

I get the same error.It prints several characters and then freezes.I am trying to understand the concept of List ADT.Here is another code, but I don't know how to fill that list.I will be very thankful if you help me, because, apparently, I cant do it by myself, and it drives me crazy :))

#include <iostream>
#include <string>
 #include <stdexcept>
 #include <vector>
using namespace std;
class RuntimeException {		// generic run-time exception
private:
  string errorMsg;
public:
  RuntimeException(const string& err) { errorMsg = err; }
  string getMessage() const { return errorMsg; }
};

class InvalidPositionException : public RuntimeException {  
public:
  InvalidPositionException(const string& err) : RuntimeException(err) {}
};

class BoundaryViolationException : public RuntimeException {  
public:
  BoundaryViolationException(const string& err) : RuntimeException(err) {}
};

class EmptyContainerException : public RuntimeException {  
public:
  EmptyContainerException(const string& err) : RuntimeException(err) {}
};

template <typename Object>

class NodeList {
protected:    
 struct Node {	      
  Object  element;					// element   
    Node*   prev;					// previous node
    Node*   next;					// next node
    Node(const Object& e = Object(), Node* p = NULL, Node* n = NULL)
        : element(e), prev(p), next(n) { }      	// constructor
  };
  typedef Node* NodePtr;				// pointer to a Node 
public:
  class Position {					// position in NodeList
  private:
    NodePtr node;					// pointer to the node
  public:
    Position(NodePtr n = NULL)				// constructor
      { node = n; }
    Object& element() const 				// return element
         throw(InvalidPositionException) {
      if (node == NULL) throw InvalidPositionException("Null position");
      return node->element;
    }
    bool isNull() const 				// a null position?
      { return node == NULL; }
    friend class NodeList<Object>;			// allow access
  };
protected:                          // utility to convert Position to node pointer
  NodePtr nodePtr(const Position& p) const throw(InvalidPositionException) {
    if (p.node == NULL)
      throw InvalidPositionException("Attempt to use null position");
    else return p.node;
  }
protected: 						// data members
  int       sz;        					// number of items
  NodePtr   header;					// head of list sentinel
  NodePtr   trailer;					// tail of list sentinel
public:
  NodeList() {						// default constructor
    sz = 0;
    header   = new Node;				// create sentinels
    trailer  = new Node;
    header->next   = trailer;				// head points to trailer
    trailer->prev  = header;				// trailer points to head
  }
  int size() const 					// list size
    { return sz; }
  bool isEmpty() const 					// is the list empty?
    { return (sz == 0); }
  bool isFirst(const Position& p) const 		// is this the first?
      throw(InvalidPositionException) {
    NodePtr v = nodePtr(p);
    return v->prev == header;
  }
  bool isLast(const Position& p) const 			// is this the last?
      throw(InvalidPositionException) {
    NodePtr v = nodePtr(p);
    return v->next == trailer;
  }
  
  Position first() const 				// return first element
      throw(EmptyContainerException) {
    if (isEmpty()) throw EmptyContainerException("List is empty");
    return Position(header->next);
  }
  Position before(const Position& p) const 		// return item before p
      throw(BoundaryViolationException, InvalidPositionException) {
    NodePtr v = nodePtr(p);
    NodePtr prev = v->prev;
    if (prev == header)
      throw BoundaryViolationException("Advance past beginning of list");
    return Position(prev);
  }
  Position insertAfter(const Position& p, const Object& element)
      throw(InvalidPositionException) {			// insert after p
    NodePtr v = nodePtr(p);
    sz++;
    NodePtr newNode  = new Node(element, v, v->next);
    v->next->prev    = newNode;				// link node into list
    v->next	     = newNode;
    return Position(newNode);
  }
  void remove(const Position& p)			// remove a given node
      throw(InvalidPositionException) {
    sz--;
    NodePtr v = nodePtr(p);
    v->prev->next    = v->next;				// unlink from the list
    v->next->prev    = v->prev;
    delete v;
  }
  void replaceElement(const Position& p, const Object& element)
      throw(InvalidPositionException) {			// replace element
    NodePtr v  = nodePtr(p);
    v->element = element;
  }
  
};

int main ()
{



system ("pause");
return 0;
}

Thats the code.So can you tell me how can I fill the list with integers?
I will be very very thankful :))

[Dacster13]

well when the program crashes it usually is because of pointers. Most likely trying to access a bad pointer. Your code is quite long so I'll have to take a good look at it first. =)

[RachelAnderson]

Thank you :))

[Dacster13]

well, I think the insertAfter method is what you need to use to insert nodes into the list.

However i don't quite see how to get the first position to insert to which is a parameter in the insertAfter method. Even though there is a first and before method that returns a position, since the list will start out empty it just ends up throwing an exception. Did you make the NodeList class?

Just noticed the Position class is public lol.

[RachelAnderson]

I think the answer is in insertAfter too, but I cant make the connection.Is it a mistake that the Position class is public?

[Dacster13]

I still can't quite figure it out, maybe I need to get some sleep first it's 5:48 am here in my timezone. I'll try again when I wake up though.

Nope it's not really a mistake that the Position class is public, I thought it was protected or private though because normally public members break encapsulation. I still can't figure it out at the moment though, I haven't been programming in C++ for a while so I'm a bit rusty on the syntax and such. :P

I also noticed in that class it has a method to get the previous node, but not the next node on the list. Does that mean the list should be traversed backwards?

[RachelAnderson]

There is, the trailer is the next node.Yes, we can talk about it tomorrow.Thank you again for the help so far :)

[Dacster13]

I'm back, I figured out how to access the Position class but trying to construct a Position object just gives a null NodePtr though, and you can't pass in a NodePtr object cause the Node structure is protected. Maybe this class was meant to be subclassed?

Still confused how to get the head NodePtr Position so we can start inserting nodes, but I'm still working on it. =)

[RachelAnderson]

It should be subclassed, I think .

[RachelAnderson]

By the way, what about insertFirst function used for lists, I read somewhere something about it a few months ago, but I am not sure if I can implement it, but I am pretty sure that we should use it.I will search for more info in uncle google :))

[Dacster13]

lolz i find it a lot easier making lists from scratch actually. Trying to figure out what someone was trying to do is sometimes more difficult in my opinion. I think the easy way to make it work would be to add an accessor method so we can get access to the head node of the list and pass it to the Position constructor to create a valid position. Once we have a valid Position object we can just use the insertAfter method to insert nodes into the list.

Anyways you can always email me if you find anything interesting about the insertFirst function. My email is [e-mail].

I'll try adding an accessor method and post what I have here, or I could email it to you which would be probably easier. :P

[Dacster13]

Anyways here's the result, it's actually very simple once you have access to the head node pointer. I really wanted to understand how the person who created the class want us to use his class instead of introducing a method which bypasses the actual design. It's most likely done through inheritance I think, but I haven't been programming in C++ for a while so I'll need to review and get some practice on that again I think. =)

#include <iostream>
#include <string>
#include <stdexcept>
#include <vector>

using namespace std;

class RuntimeException {        // generic run-time exception
    private:
        string errorMsg;
    public:
        RuntimeException(const string& err) { errorMsg = err; }
        string getMessage() const { return errorMsg; }
};

class InvalidPositionException : public RuntimeException {  
    public:
        InvalidPositionException(const string& err) : RuntimeException(err) {}
};

class BoundaryViolationException : public RuntimeException {  
    public:
        BoundaryViolationException(const string& err) : RuntimeException(err) {}
};

class EmptyContainerException : public RuntimeException {  
    public:
        EmptyContainerException(const string& err) : RuntimeException(err) {}
};

template <typename Object>

class NodeList {
    protected:    
        struct Node {	      
            Object  element;					// element   
            Node*   prev;					// previous node
            Node*   next;					// next node
            Node(const Object& e = Object(), Node* p = NULL, Node* n = NULL)
                : element(e), prev(p), next(n) { }      	// constructor
        };
        
        typedef Node* NodePtr;				// pointer to a Node 
    public:
        class Position {					// position in NodeList
            private:
                NodePtr node;					// pointer to the node
            public:
                Position(NodePtr n = NULL)				// constructor
                { node = n; }
                Object& element() const 				// return element
                    throw(InvalidPositionException) {
                    if (node == NULL) throw InvalidPositionException("Null position");
                        return node->element;
                }
                bool isNull() const 				// a null position?
                { return node == NULL; }
                friend class NodeList<Object>;			// allow access
        };
    protected:                          // utility to convert Position to node pointer
        NodePtr nodePtr(const Position& p) const throw(InvalidPositionException) {
            if (p.node == NULL)
                throw InvalidPositionException("Attempt to use null position");
            else return p.node;
        }
    protected: 						                    // data members
        int       sz;        					        // number of items
        NodePtr   header;					            // head of list sentinel
        NodePtr   trailer;					            // tail of list sentinel
    public:
        NodeList() {						            // default constructor
            sz = 0;
            header   = new Node;				        // create sentinels
            trailer  = new Node;
            header->next   = trailer;				    // head points to trailer
            trailer->prev  = header;				    // trailer points to head
        }
        
        int size() const 					            // list size
        { return sz; }
        
        bool isEmpty() const 					        // is the list empty?
        { return (sz == 0); }
        
        bool isFirst(const Position& p) const 		    // is this the first?
        throw(InvalidPositionException) {
            NodePtr v = nodePtr(p);
            return v->prev == header;
        }
        
        bool isLast(const Position& p) const 			// is this the last?
        throw(InvalidPositionException) {
            NodePtr v = nodePtr(p);
            return v->next == trailer;
        }
        
        Position first() const                          // return first element
        throw(EmptyContainerException) {
            if (isEmpty()) throw EmptyContainerException("List is empty");
            return Position(header->next);
        }
        
        Position before(const Position& p) const 		// return item before p
        throw(BoundaryViolationException, InvalidPositionException) {
            NodePtr v = nodePtr(p);
            NodePtr prev = v->prev;
            if (prev == header)
                throw BoundaryViolationException("Advance past beginning of list");
            return Position(prev);
        }
        
        Position insertAfter(const Position& p, const Object& element)
        throw(InvalidPositionException) {               // insert after p
            NodePtr v = nodePtr(p);
            sz++;
            NodePtr newNode  = new Node(element, v, v->next);
            v->next->prev    = newNode;				    // link node into list
            v->next	     = newNode;
            return Position(newNode);
        }
        
        void remove(const Position& p)			        // remove a given node
        throw(InvalidPositionException) {
            sz--;
            NodePtr v = nodePtr(p);
            v->prev->next    = v->next;				    // unlink from the list
            v->next->prev    = v->prev;
            delete v;
        }
        
        void replaceElement(const Position& p, const Object& element)
        throw(InvalidPositionException) {			    // replace element
            NodePtr v  = nodePtr(p);
            v->element = element;
        }
    public:
           NodePtr getHeadNode() const { return this->header; }    // added accessor method to access the head node.
};

int main ()
{
    try
    {
        NodeList<int> *list = new NodeList<int>();            // create a list of integers
        NodeList<int>::Position pos(list->getHeadNode());     // create a position referring to the head node of the list
        
        // insert 10 elements into the list
        for(int i = 0; i < 10; ++i)
        {
              list->insertAfter(pos, i);
        }

        // remove and print out the contents of the list
        while(!list->isEmpty())
        {
             NodeList<int>::Position cur = list->first();
             cout << cur.element() << endl;
             list->remove(list->first());
        }
    }
    catch(InvalidPositionException ipexc)
    {
         cout << "invalid position exception" << endl;
    }
    catch(BoundaryViolationException bvexc)
    {
         cout << "boundary violation exception" << endl;
    }
    catch(EmptyContainerException ecexc)
    {
         cout << "empty container exception" << endl;
    }
    catch(RuntimeException rexc)
    {
         cout << "runtime exception" << endl;
    }
    cin.get();
    return 0;
}

[RachelAnderson]

Lol thats great =], now, when the code is complete I will spend some time on it, to understand the concept, Many many thanks Dacster 13:))

[Dacster13]

you're welcome, I'm glad I could help. ^_^