Nov 8, 2011 at 5:06pm UTC
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
#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;
}
Last edited on Nov 8, 2011 at 5:07pm UTC
Nov 8, 2011 at 7:38pm UTC
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
Nov 8, 2011 at 8:20pm UTC
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 :))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
#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 :))
Last edited on Nov 8, 2011 at 8:22pm UTC
Nov 8, 2011 at 8:28pm UTC
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. =)
Nov 8, 2011 at 9:09pm UTC
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.
Last edited on Nov 8, 2011 at 9:51pm UTC
Nov 8, 2011 at 9:36pm UTC
I think the answer is in insertAfter too, but I cant make the connection.Is it a mistake that the Position class is public?
Nov 8, 2011 at 10:00pm UTC
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?
Last edited on Nov 8, 2011 at 10:03pm UTC
Nov 8, 2011 at 10:06pm UTC
There is, the trailer is the next node.Yes, we can talk about it tomorrow.Thank you again for the help so far :)
Nov 9, 2011 at 7:32am UTC
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. =)
Nov 9, 2011 at 1:58pm UTC
It should be subclassed, I think .
Nov 9, 2011 at 4:20pm UTC
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 :))
Nov 9, 2011 at 4:46pm UTC
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 dacster13@yahoo.com.
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
Nov 9, 2011 at 5:11pm UTC
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. =)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
#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;
}
Last edited on Nov 9, 2011 at 5:30pm UTC
Nov 9, 2011 at 5:23pm UTC
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:))
Nov 9, 2011 at 5:35pm UTC
you're welcome, I'm glad I could help. ^_^