Join 136,324 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 2,782 people online right now. Registration is fast and FREE... Join Now!
Hello, I was wondering if someone could help me with a copy constructor function for this linked list program. It's pretty generic and just processes a name and age value.
Also, how would you invoke the copy constructor once it's defined?
Any help with this would be great. Thanks for your time.
Here's the class definition:
CODE
class LL { protected: struct Node { char * Name; int Age; Node * Next; Node * Prev; }; int Length; Node * Head; Node * Tail;
Note, I don't really trust the Length attribute. I'd rather just have it as a method and count the list.
If your Insert method is working properly, this should be fine. Think of it as just starting with an empty list and adding nodes in sequence, which is just what we're doing.
cpp
// this bit looks fine LL::LL() { Length = 0; Head = NULL; Tail = NULL; }
LL::LL(const LL & obj) { // start with blank, just like in the empty constructor Length = 0; Head = NULL; Tail = NULL;
// Now you should just be able to use // your list's methods Node *p = obj.Head; while(p!=NULL) { Insert(p->Name, p->Age); p = p->Next; } }
The copy constructor is easy, it's the Insert and InsertNode that's the challenge. Also, since you're using C++, you might consider the string class if you're allowed.
Hope this helps.
This post has been edited by baavgai: 3 Sep, 2008 - 11:48 AM
Baavgai, Thanks so much for your response! Your explanation made perfect sense. I tested it out and worked great.
I managed to come up with this other one while waiting to see if anyone would reply from the first post. I contrasted the two of them below:
Here's what I tried on my second attempt. It was kind of like fusing the Insert() function and the copy constructor into one. The new one you described is much more slick and makes use of the already defined Insert() function.
Thanks again!
Contrasted this...
CODE
LL::LL(const LL & obj) { Node * o = obj.Head;
if (obj.Head == NULL) { cout << "List is empty...\n"; Head = NULL; } else { Head = new Node; assert(Head != NULL); Head->Name = new char[strlen(o->Name) + 1]; strcpy(Head->Name, o->Name); Head->Age = o->Age;
( Um, I didn't test this code. It's perfect, in theory only. )
Most Linked List implementations only need a Next pointer in the node to do their thing. Your class need only hold the top. For a doubly linked list, like this one, there's usually a reason. A search requirement, most likely.
Hi Baavgai, Thanks again for looking at my code. I've been trying to compile a set of data structure programs and have been more or less reusing the LL class for the circular, doubly linked, stack, and queue structures. I added functions for inserting at the front and at the end using your suggestions.
I've been getting a seg fault on my Delete function and would like to clean it up a bit and make it as slick as the insertion functions. This is pretty pretty ugly but what could I do to clean this function up? The seg fault is occurring at the end.
You are assuming that curr is not null. That's not a valid assumption, if you didn't find the node, it could be null.
If you did find it, you have a prev and a next in the node itself, you really shouldn't need any other pointers to delete it. You have a search function? void Search(char *Name, int Age); What does it do, exactly? Make a useful one, like Node* Search(char *Name, int Age);.
Also, you're doing a lot of mucking about data in your nodes. You might do well have have the data be class:
Hi Baavgai, Thanks for your further suggestions and I totally revamped the whole linked list program/class. I'm still having trouble with the Delete function though. I'm trying to figure out how to clean up the pointers when the deletion is made and I keep getting seg faults. Can you suggest anything?
I'm going to need to revamp all the other programs as well. Is this class definition type the best way to implement a linked list or binary search tree? Does the ItemType class need to have more operator overloading?
Here's my new class definition:
CODE
#include <iostream> #include <cstring> using namespace std;
class ItemType { public: friend class LL;
char * Name; int Age;
ItemType(char *Name, int Age){ this->Name = new char[strlen(Name) + 1]; strcpy(this->Name, Name); this->Age = Age; } ~ItemType(){ delete this->Name; }
if(curr == NULL) { cout << "Didn't find the info to delete from the list.\n"; } else { if (curr->Next = NULL) { cout << "node to delete was at the end of the list.\n"; curr->Prev->Next = NULL; Tail = curr->Prev;
} else { cout << "node to delete was in the middle of the list somewhere.\n"; curr->Prev->Next = curr->Next; curr->Next->Prev = curr->Prev;
Hi Baavgai, Thanks again for all your help with this. I've been working on this project all day for the most part and it seems close to being completed. I was able to get the Delete function working with the help of the Search function and it is now much shorter. It still looks a bit busy though.
I'm now having some interesting errors that I can't quite pinpoint. To add some completenes to the program I tried to add file I/O capability. Now, when the program is run and I read in data to the list from a file and try to use one of the sort ascending or descending functions, the program seg faults.
If I don't read in anything from the file to initialize the list and just input the list node information manually, the sort functions work fine. Client information can be added and then sorted without problems (so it seems).
There may be something wrong with my SaveList or OpenFile functions.
Is there any apparent code problems with the sort functions?
Thanks again for all your help. I included the entire program files if it helps any.
void LL::SortList_Ascend() { Node * temp; Node * curr, * save; curr = save = Head; if (Head == NULL) { cout << "Linked list is empty\n"; return; } else { for (curr = Head; (curr != NULL); curr = curr->Next) { for (save = curr->Next; (save != NULL); save = save->Next) { if (strcmp(curr->Item->Name, save->Item->Name) > 0) { temp = new Node; temp->Item = new ItemType(save->Item->Name, save->Item->Age); strcpy(save->Item->Name, curr->Item->Name); save->Item->Age = curr->Item->Age; strcpy(curr->Item->Name, temp->Item->Name); curr->Item->Age = temp->Item->Age; } } } cout << "The linked list is now sorted in ascending order!\n"; } }
/*--------------------------------------------------------------------------*/ void LL::SortList_Descend() { Node * temp; Node * curr, * save; curr = save = Head; if (Head == NULL) { cout << "Linked list is empty\n"; return; } else { for (curr = Head; (curr != NULL); curr = curr->Next) { for (save = curr->Next; (save != NULL); save = save->Next) { if (strcmp(curr->Item->Name, save->Item->Name) < 0) { temp = new Node; temp->Item = new ItemType(save->Item->Name, save->Item->Age); strcpy(save->Item->Name, curr->Item->Name); save->Item->Age = curr->Item->Age; strcpy(curr->Item->Name, temp->Item->Name); curr->Item->Age = temp->Item->Age; } } } cout << "The linked list is now sorted in descending order!\n"; } }
Attached File(s) LL2_h.txt ( 1.23k )
Number of downloads: 2 LL2_cpp.txt ( 6.46k )
Number of downloads: 2 main_cpp.txt ( 2.8k )
Number of downloads: 3 list.txt ( 129bytes )
Number of downloads: 1
You need to write a functional swap method. Once it works, call that from each of your sorts.
You should not be doing this:
CODE
strcpy(save->Item->Name, curr->Item->Name);
Because you define the name like this:
CODE
this->Name = new char[strlen(Name) + 1];
Doing what you're doing, if one name "Fred" and the other is "Alexander" you will crash when you try to stuff a nine character name into a four character hole.
There's a really, really easy way to do this. Because your node simply holds a pointer to it's payload, why don't you just swap those pointers? There is no need for new anything.
Hi Baavgai, It took me awhile to figure out how to implement what you were talking about but I think I managed to make it work. I shifted gears to look at a circular doubly linked list implementation this afternoon and tried to modify the doubly linked list from before to avoid rewriting.
I've been struggling with the Delete function with this as well. I'm having trouble with the special cases: inserting at front, inserting in middle, and at the end. Can you see any immediate flaws? The code is somewhat messy but I'm striving for really understanding the concepts and getting the functionality down. Thanks again for everything!
I'm not sure if this was correct but here's the Swap function I tried coding:
if(curr == NULL) { cout << "Didn't find the info in the list.\n"; return; } else { if(curr == Head) { cout << "Node info to delete was in the Head node.\n"; Head = Head->Next; delete curr->Item->Name; delete curr; } else if(curr->Next == NULL) { cout << "Node info to delete was in the last node in the list.\n"; curr->Prev->Next = Head; Head->Prev = curr->Prev; delete curr->Item->Name; delete curr; } else { cout << "Node info to delete was in the middle of the list.\n"; curr->Prev->Next = curr->Next; curr->Next->Prev = curr->Prev; delete curr->Item->Name; delete curr; } } }
The Search function looks like this:
CODE
LL::Node * LL::SearchNode(Node * srchNode) { Node * curr; if(Head == NULL) { cout << "The list is empty\n"; } else { cout << "head is not NULL...searching...\n"; curr = Head; while(curr != NULL) { if((strcmp(curr->Item->Name, srchNode->Item->Name)==0) && (curr->Item->Age == srchNode->Item->Age)) { cout << "Found the info in the list...\n"; break; } curr = curr->Next; if(curr == Head) { cout << "Circular.\n"; break; } }
if(curr != NULL) { return curr; } else { cout << "Info not in the list.\n"; return NULL; } } }
Did you say "circular doubly linked list"? If so, none of your node pointers should ever be NULL. Before you could ignore one side if you added at top or bottom, now you can't.
Inserting a node is the same, no matter where you do it. You just need to know who you're next to. I'll give you this one.
cpp
void LL::InsertNodePrior(Node * newNode, Node * nextNode) { if (priorNode == NULL) { newNode->Prev = newNode; newNode->Next = newNode; } else { newNode->Prev = nextNode->Prev; newNode->Next = nextNode; // note, you'll always be doing this little attach dance // tell the neighbors to point to you newNode->Prev->Next = newNode; newNode->Next->Prev = newNode; } }
void LL::InsertNodeAtEnd(Node * newNode) { InsertNodeAtFront(newNode); // think about it. }
I'm just going to have to give the swap, you're not seeing it. You are swaping pointers! It's just like swapping ints. This is the point of having an ItemType, it can be anything and your code needn't worry about it.
Now, since you're doing a circular list, go back and make sure nothing has "!=NULL" as a stopper. Otherwise, you'll spin a long time. Remember, your logic is this:
CODE
Head==NULL // empty list Head==Head->Next // list has one value Node *node = Head; while(node!=Head) // oops, this doesn't work. You'll have to figure it out.
3 Sep, 2008 - 10:52 AM
