Jump to content
  • Advertisement
Sign in to follow this  
yoMama

circular doubly linked list

This topic is 4232 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hey :) im trying to make code for a doubly linked list that will 1) insert nodes im order in it 2) print that list forward 3) print it backward 4) merge it n another one into a whole new, special ,being lol..yeh, im tired:D this seems like it shud be relatively easy...but i keep gettin ridiculous errors :( (besides the two pointers, each node just holds one int) heres my implementation file: //***************************************** //Implementation File (list.cpp) //***************************************** #include <iostream> #include <fstream> #include "cdll.h" using namespace std; List::List() { head = '\0'; } void List::insertNode(int num) { Node *newNode; Node *nodePtr; Node *previous = '\0'; newNode = new Node; newNode->data = num; if(!head) { head = newNode; newNode->next = '\0'; } else { nodePtr = head; previous = '\0'; while(nodePtr!='\0' && (nodePtr->data < num)) { previous = nodePtr; nodePtr = nodePtr->next; } if(previous == '\0') { head = newNode; nodePtr->prev = newNode; newNode->next = nodePtr; newNode->prev = head; } else { newNode->next = nodePtr; previous->next = newNode; newNode->prev = previous; } } nodePtr = head; while(nodePtr!='\0') nodePtr = nodePtr->next; nodePtr = head; head->prev = nodePtr; } void List::printForward(fstream &out)const { Node *p; //to move through the list p = head->next; //position p pointer at head of list while(p!=head) { out << p->data << endl; p = p->next; } } void List::printBackward(fstream &out)const { Node *q; q = head; q = q->prev; while(q!=head) { out << q->data << endl; q = q->prev; } out << endl; } void List::deleteNode(int num) { Node *nodePtr; Node *prevNode; if(head=='\0') return; if(head->data == num) { nodePtr = head->next; delete head; head = nodePtr; } else { nodePtr = head; while(nodePtr!='\0' && (nodePtr->data!=num)) { prevNode = nodePtr; nodePtr = nodePtr->next; } if(nodePtr) { prevNode->next = nodePtr->next; delete nodePtr; } } } void List::merge(List list1, List list2) { Node *ptr1; Node *ptr2; ptr1 = list1.head; while(ptr1!='\0') { insertNode(ptr1->data); ptr1 = ptr1->next; } ptr2 = list2.head; while(ptr2!='\0') { insertNode(ptr2->data); ptr2 = ptr2->next; } } any help wud be very much appreciated...thank you :)

Share this post


Link to post
Share on other sites
Advertisement
Hello,
Help us read your code (use [ source ] [ / source ] tags without spaces, an someone will help you understand it.

Cheers

Share this post


Link to post
Share on other sites
mmkay...i dun really kn owhat u mean, but i'll just try to clear it up abit :)

#include <iostream>
#include <fstream>
#include "cdll.h" [specification file]
using namespace std;

List::List() [constructor:creates list]
{
head = '\0';
}


void List::insertNode(int num) [inserts a node]
{
Node *newNode;
Node *nodePtr;
Node *previous = '\0';
newNode = new Node;
newNode->data = num;

if(!head) [if theres no nodes yet, make the first one]
{
head = newNode;
newNode->next = '\0';
}
else
{
nodePtr = head;
previous = '\0';
while(nodePtr!='\0' && (nodePtr->data < num))
{
previous = nodePtr;
nodePtr = nodePtr->next;
}
if(previous == '\0') [in case it comes right after the head pointer]
{
head = newNode;
nodePtr->prev = newNode;
newNode->next = nodePtr;
newNode->prev = head;
}
else [insert anywhere else in the list lol]
{
newNode->next = nodePtr;
previous->next = newNode;
newNode->prev = previous;
}
}
nodePtr = head;
while(nodePtr!='\0') [um...this is supposed to make it circular]
nodePtr = nodePtr->next;
nodePtr = head;
head->prev = nodePtr;
}

void List::printForward(fstream &out)const
{
Node *p; //to move through the list
p = head->next; //position p pointer at head of list
while(p!=head)
{
out << p->data << endl; [trying to print forward..havent really progressed..
p = p->next; ..from here, program keeps gettin stuck]
}
}

void List::printBackward(fstream &out)const [im guesssing thisll have the..
{ ..same problem when i get to it:P]
Node *q;
q = head;
q = q->prev;
while(q!=head)
{
out << q->data << endl;
q = q->prev;
}
out << endl;
}


void List::deleteNode(int num) [supposed to find and delete a node w/
{ specific value]
Node *nodePtr;
Node *prevNode;

if(head=='\0')
return;
if(head->data == num)
{
nodePtr = head->next;
delete head;
head = nodePtr;
}
else
{
nodePtr = head;
while(nodePtr!='\0' && (nodePtr->data!=num))
{
prevNode = nodePtr;
nodePtr = nodePtr->next;
}
if(nodePtr)
{
prevNode->next = nodePtr->next;
delete nodePtr;
}
}
}

void List::merge(List list1, List list2) [merges 2 lists into one]
{
Node *ptr1;
Node *ptr2;
ptr1 = list1.head;
while(ptr1!='\0')
{
insertNode(ptr1->data);
ptr1 = ptr1->next;
}
ptr2 = list2.head;
while(ptr2!='\0')
{
insertNode(ptr2->data);
ptr2 = ptr2->next;
}
}
hope that helps... :)

Share this post


Link to post
Share on other sites
he means use the [ source ] tags to make your code more readable

e.g here is a copy of your code with [ source ] and [/ source ] (without the spaces)


#include <iostream>
#include <fstream>
#include "cdll.h" [specification file]
using namespace std;

List::List() [constructor:creates list]
{
head = '\0';
}


void List::insertNode(int num) [inserts a node]
{
Node *newNode;
Node *nodePtr;
Node *previous = '\0';
newNode = new Node;
newNode->data = num;

if(!head) [if theres no nodes yet, make the first one]
{
head = newNode;
newNode->next = '\0';
}
else
{
nodePtr = head;
previous = '\0';
while(nodePtr!='\0' && (nodePtr->data < num))
{
previous = nodePtr;
nodePtr = nodePtr->next;
}
if(previous == '\0') [in case it comes right after the head pointer]
{
head = newNode;
nodePtr->prev = newNode;
newNode->next = nodePtr;
newNode->prev = head;
}
else [insert anywhere else in the list lol]
{
newNode->next = nodePtr;
previous->next = newNode;
newNode->prev = previous;
}
}
nodePtr = head;
while(nodePtr!='\0') [um...this is supposed to make it circular]
nodePtr = nodePtr->next;
nodePtr = head;
head->prev = nodePtr;
}

void List::printForward(fstream &out)const
{
Node *p; //to move through the list
p = head->next; //position p pointer at head of list
while(p!=head)
{
out << p->data << endl; [trying to print forward..havent really progressed..
p = p->next; ..from here, program keeps gettin stuck]
}
}

void List::printBackward(fstream &out)const [im guesssing thisll have the..
{ ..same problem when i get to it:P]
Node *q;
q = head;
q = q->prev;
while(q!=head)
{
out << q->data << endl;
q = q->prev;
}
out << endl;
}


void List::deleteNode(int num) [supposed to find and delete a node w/
{ specific value]
Node *nodePtr;
Node *prevNode;

if(head=='\0')
return;
if(head->data == num)
{
nodePtr = head->next;
delete head;
head = nodePtr;
}
else
{
nodePtr = head;
while(nodePtr!='\0' && (nodePtr->data!=num))
{
prevNode = nodePtr;
nodePtr = nodePtr->next;
}
if(nodePtr)
{
prevNode->next = nodePtr->next;
delete nodePtr;
}
}
}

void List::merge(List list1, List list2) [merges 2 lists into one]
{
Node *ptr1;
Node *ptr2;
ptr1 = list1.head;
while(ptr1!='\0')
{
insertNode(ptr1->data);
ptr1 = ptr1->next;
}
ptr2 = list2.head;
while(ptr2!='\0')
{
insertNode(ptr2->data);
ptr2 = ptr2->next;
}
}


Share this post


Link to post
Share on other sites
um..ok..still dunno how to do that tho...but neway....u got it up for me so ty :)
now, about t he programming problem.... lol :D ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by yoMama
now, about t he programming problem.... lol :D ;)


What is the programming problem? What "ridiculous errors" are you getting?

Share this post


Link to post
Share on other sites
its not even an error really...this is waht it says:
Unhandled exception at 0x00420760 in CDLL.exe: 0xC0000005: Access violation reading location 0x00000000.

Share this post


Link to post
Share on other sites
Quote:
Original post by yoMama
its not even an error really...this is waht it says:
Unhandled exception at 0x00420760 in CDLL.exe: 0xC0000005: Access violation reading location 0x00000000.


0xC0000005 means you're tying to do read from memory you don't own, in this case at address 0x00000000. Basically, you're trying to access a NULL pointer.

Step through you're code in a debugger and see where this is happening. If you don't know how to use a debugger, nows as good a time to learn as any. Here is an article which you may also find usefull.

Share this post


Link to post
Share on other sites
Quote:
Original post by yoMama
um..ok..still dunno how to do that tho...but neway....u got it up for me so ty :)
now, about t he programming problem.... lol :D ;)


0) Proper spelling, grammar, and overall command of the English language are important. Sorry. This is not a chat room.

1) He pretty much told you what to do, but if you really need another hint, select "edit" on my or his post to see what stuff is typed in. (The board will, of course, not let you save any edits to our posts.)

If that's still not enough, then FFS, read the Forum FAQ. It's linked at the top of the page, with the inner-tube-and-magic-wand icon. There's really no excuse for ignorance of how to use the board. Reading FAQs is expected.

2) For Beginners is at the top of the forum list for a reason.

3) In For Beginners, we would tell you not to do this yourself, because proper use of the language includes proper use of the standard library. To wit:

Quote:

hey :)
im trying to make code for a doubly linked list that will



#include <list>
#include <iterator> // will be used later
#include <algorithm> // will be used later
#include <iostream> // will be used later

std::list<int> numbers; // or std::list<whatever other type>


Quote:

1) insert nodes im order in it


numbers.push_back(42);

Quote:

2) print that list forward



std::copy(numbers.begin(), numbers.end(),
std::ostream_iterator<int>(std::cout, ", "));


Quote:

3) print it backward



std::copy(numbers.rbegin(), numbers.rend(),
std::ostream_iterator<int>(std::cout, ", "));


Quote:

4) merge it n another one into a whole new, special ,being lol..yeh, im tired:D



std::list<int> other, result;
// put stuff into 'other'
// Now we make 'result' as the merge of 'numbers' and 'other':
result.splice(result.end(), numbers);
result.splice(result.end(), other);
// The nodes have all been moved into 'result', so 'numbers' and 'other' are
// now empty.

Share this post


Link to post
Share on other sites
ok zahlman, not everyone likes to use STL. I normally like to write my own classes because STL has a weird way of doing things (I do use STL if Im in a hurry but if Im writing a big project I like to write my own). Also, the most likely scenario here is that this is a homework assignment or something that this guy has to do, in which case he couldnt just use the template list class.

as to the question, Im tired and only took a brief look at the code but in the section:

while(nodePtr!='\0' && (nodePtr->data < num))
{
previous = nodePtr;
nodePtr = nodePtr->next;
}
if(previous == '\0') [in case it comes right after the head pointer]
{
head = newNode;
nodePtr->prev = newNode;
newNode->next = nodePtr;
newNode->prev = head;
}

the first loop exits when nodePtr == 0. in the next if statement tho, nodePtr->prev is call which would cause your error. Im not entirely sure that this scenario is possible, and there may be other cases like this later in the program. You should step through your program to check for any case where a null pointer is dereferenced.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!