| bl00dninja |
Sep 5th, 2006 12:45 AM |
linked list problems
when i try to destroy the last (not tail, but the last remaining element) i get a run-time error. here's the code for those brave enough...
:
// dataDefinition.h
#ifndef DATADEFINITION_H
#define DATADEFINITION_H
typedef int elementDataType;
#endif
:
// list.h
#ifndef list_H
#define list_H
#include "dataDefinition.h"
struct node
{
elementDataType nodeData;
node * next; // self referential
};
class list { // singly linked list class
public:
list(); // constructor
~list(); // destructor
list(const list&); // copy constructor
void deleteElement(); // deletes the current element
void addElementAfterCurrent(elementDataType); // adds an element AFTER the current element
void addElementAsHead(elementDataType); // adds an element at the list head
void addElementAsTail(elementDataType); // adds an element at the list tail
elementDataType getCurrentElementValue(); // gets data value of current element
void moveForward(); // move forward one node in list
bool isFirstElement(); // returns true if current element is list head
bool isLastElement(); // returns true if current element is head tail
bool isEmpty(); // returns true if list is empty
int size(); // returns the size of the list
void moveTolistHead(); // moves current node to the list head
void showlist(); // shows list contents
private:
node * head; // list head
node * current; // current node being processed
int currentSize;
};
#endif
:
#include "list.h"
#include "dataDefinition.h"
#include <iostream>
using namespace std;
//constructor**********************************************************
list::list()
{
//set head to null
head = 0;
//set current to head
current = head;
//set size = 0
currentSize = 0;
}
//destructor*************************************************************
list::~list()
{
//taken care of by deleteElement()
}
//copy constructor********************************************************
list::list(const list& nextObject)
{
current = head = 0;
currentSize = nextObject.currentSize;
node * pNext = nextObject.head;
while(pNext->next != 0)
{
node * temp = new node;
temp->nodeData = pNext->nodeData;
temp->next = pNext->next;
pNext = pNext->next;
}
}
//delete the current element*****************************************************
void list::deleteElement()
{
//do nothing if no elements
if(head == 0) cout<<"\nempty list.\n"<<endl;
//if 1 element
else if(head->next == 0)
{
//drop first element
head = 0;
//dump that node
delete current;
//set current to head
current = head;
//adjust list size
currentSize--;
}
//if >1 element && current = head
else if(current == head && current->next != 0)
{
//drop first element
head = head->next;
//dump that node
delete current;
//set current to head
current = head;
//adjust list size
currentSize--;
}
//if in middle of list...
else if (current != head && current->next != 0)
{
//temp node*
node * temp = head;
//find the place right before current
while(temp->next != current)
{
temp = temp->next;
}
//connect THAT place with the next place
temp->next = current->next;
//get rid of current node
delete current;
//set current to old place
current = temp;
//adjust list size
currentSize--;
}
//we're pointing at tail...
else if(current != head && current->next == 0)
{
//set temp to head
node * temp = head;
//find node before current
while(temp->next != current)
{
temp = temp->next;
}
//set temp's next to null
temp->next = 0;
//dump this node
delete current;
//reset current
current = temp;
}
}
//add after current*************************************************************
void list::addElementAfterCurrent(elementDataType input)
{
//if nothing, add as head
if(head == 0) addElementAsHead(input);
//if at end, add as tail
else if (current ->next == 0) addElementAsTail(input);
//otherwise...
else
{
//temp node
node * temp = new node;
//hold current position
temp->next = current->next;
//back current up some
current->next = temp;
//insert data
temp->nodeData = input;
//set current to new item
current = current->next;
//adjust list size
currentSize++;
}
}
//add as head******************************************************************
void list::addElementAsHead(elementDataType input)
{
//if no elements, set head to new one
if (head == 0)
{
head = new node;
head->nodeData = input;
head->next = 0;
current = head;
}
//otherwise...
else if(head != 0)
{
//new node
node * temp = new node;
//new node's data = paramater
temp->nodeData = input;
//push the old head back a bit
temp->next = head;
//reset head to new stuff
head = temp;
//set current to new element
current = temp;
}
//adjust list size
currentSize++;
}
//add to tail****************************************************************
void list::addElementAsTail(elementDataType input)
{
//if no elements, we just repeat the crap above...
if (head == 0)
{
head = new node;
current = head;
head->nodeData = input;
head->next = 0;
}
//otherwise...
else
{
//new node
node * temp = new node;
//set start
current = head;
//find end of list
while(current->next != 0)
{
current = current->next;
}
//set temp at end
current->next = temp;
//set tail pointer to null
temp->next = 0;
//insert data
temp->nodeData = input;
//set current to new crap
current = temp;
}
//adjust list size
currentSize++;
}
//return current's value*******************************************************
elementDataType list::getCurrentElementValue()
{
//duh...
return current->nodeData;
}
//move current to next element*************************************************
void list::moveForward()
{
//if empty list, chide user
if (head == 0) cout<<"empty list, try again buddy."<<endl;
//if we're at the end, make sure the user understands the implications
// of moving forward (we go back to the start)
else if (current->next == 0)
{
cout<<"\nwarning: end of list, want to wrap to head? (y or n)"<<endl;
char choice = 'n';
//get choice
cin>>choice;
//move current to start of list
if(choice == 'y') current = head;
//do nothing if they want to stay at the end
else if (choice == 'n') cout<<"ok, you're gonna stay at the end"<<endl;
//WTF!?!..the user is retarded, exit program and suggest
// they stay away from computers
else
{
cout<<"invalid parameter, bye."<<endl;
exit(1);
}
}
//or we can just move to the next element
else current = current->next;
}
//is current the head?**********************************************************
bool list::isFirstElement()
{
//if no elements, remind user that they suck
if (head == 0)
{
cout<<"\nempty list\n"<<endl;
return 0;
}
//return if they are pointing to the start
else
{
return (current == head);
}
}
//is current the last element?***************************************************
bool list::isLastElement()
{
//duh...there's nothing there
if (head == 0)
{
cout<<"\nempty list\n"<<endl;
return 0;
}
//return if the user is pointing to the tail node
else
{
return (current->next == 0);
}
}
//are there elements?**************************************************************
bool list::isEmpty()
{
//if head's not pointing to something real, there's nothing there
return (head == 0);
}
//return # of elements*************************************************************
int list::size()
{
return currentSize;
}
//move current element to the start of the list************************************
void list::moveTolistHead()
{
//do nothing if already at head
if(current == head) cout<<"\n\nalready at head\n\n"<<endl;
else
{
//temp node
node * temp = current;
//add that crap to the start (with correct paramater)
addElementAsHead(temp->nodeData);
//point current to old stuff (so we can trash it)
current = temp;
//get rid of the old crap
deleteElement();
//reset current to new stuff
current = head;
}
}
//print out list contents, and vars, etc.********************************************
void list::showlist()
{
cout<<"\n\n********************************************************"<<endl;
cout<<"size:\t"<<currentSize<<"\n"<<endl;
cout<<"current val:\t"<<current->nodeData<<"\n"<<endl;
cout<<"current->next:\t"<<current->next<<"\n"<<endl;
int i = 1;
for(node * temp = head; temp != 0; temp = temp->next)
{
//display that info
cout<<"element "<<i<<"\t"<<temp->nodeData<<endl;
i++;
}
cout<<"\n\n********************************************************@"<<endl;
}
//****************************************************************************************8
:
#include <iostream>
#include "list.h"
#include "dataDefinition.h"
using namespace std;
int main()
{
list x;
bool b =true;
while(b)
{
int choice;
cout<<"\n\nselect from the following:\n\n"<<endl;
cout<<"1:\tadd as head\t\t2:\tadd as tail"<<endl;
cout<<"3:\tadd after this node\t4:\tmove to next element"<<endl;
cout<<"5:\tis first element?\t6:\tis last element?"<<endl;
cout<<"7:\tis the list empty?\t8:\tmove current node to head"<<endl;
cout<<"9:\tdelete current element\t10:\tquit\n\n"<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
elementDataType in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x.addElementAsHead(in);
x.showlist();
break;
}
case 2:
{
elementDataType in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x.addElementAsTail(in);
x.showlist();
break;
}
case 3:
{
elementDataType in;
cout<<"\n\nvalue?"<<endl;
cin>>in;
x.addElementAfterCurrent(in);
x.showlist();
break;
}
case 4:
{
x.moveForward();
x.showlist();
break;
}
case 5:
{
if(x.isFirstElement() ) cout<<"\n\nyes"<<endl;
else cout<<"\n\nno"<<endl;
x.showlist();
break;
}
case 6:
{
if(x.isLastElement() ) cout<<"\n\nyes"<<endl;
else cout<<"\n\nno"<<endl;
x.showlist();
break;
}
case 7:
{
if(x.isEmpty() ) cout<<"\n\nyes"<<endl;
else cout<<"\n\nno"<<endl;
x.showlist();
break;
}
case 8:
{
x.moveTolistHead();
x.showlist();
cout<<"copy"<<endl;
list y(x);
y.showlist();
break;
}
case 9:
{
x.deleteElement();
x.showlist();
break;
}
case 10:
{
exit(0);
break;
}
default:
{
cout<<"invalid input"<<endl;
break;
}
}//end switch
}//end while
system("PAUSE");
return 0;
}
am i mis-using the destructor?
the copy constructor is essentially untested.
but the big problem is in the case of deleteElement() here:
case of one element in list to destroy.
:
//if 1 element
else if(head->next == 0)
{
//drop first element
head = 0;
//dump that node
delete current;
//set current to head
current = head;
//adjust list size
currentSize--;
}
also, how do i transfer a struct to a template? the 2nd problem, i have the syntax for everything else, yes i googled. |
