Monday, December 3, 2018

recursion - function with return type node* in conjunction with OOP in c++

I need to write a program that takes an instance of a linear linked list and removes all of the items in the list except for the last two items. I'm doing this in c++ using classes, so I'll have 3 files: main.cpp, list.h, and list.cpp. There can be no loops: I can use multiple functions but the traversal part has to be recursive.



I thought about it and what I concluded is this: I'll have to have one public function that I can call from main which will take no arguments, called void lastTwo(). I'll have another private function called node* lastTwo(node *& current, node *& tail) which will be called by lastTwo(), and it will traverse the list recursively and delete the nodes it touches until it reaches the second to last node in the list, and then it will return the address of that node.



Then, when it returns the address of the second to last node in the list, the public function lastTwo() will catch that address and set head equal to it.




The problem I'm having is that I need to do this in vi and compile and run from the command line, and I'm getting a segmentation fault even though I drew a pointer diagram and can't find a problem with my code.



I'm working on this on the student server at my university, and all of the implementation of the data structure except for these two functions have been written by my instructors, so they're all solid. Also, every time you run the a.out file, they've written it to generate a new, random, non-empty linked list, of at least 5 nodes.



I think the problem is related to the function having the return type "node*" , because I tried doing this in visual studio as well and it wouldn't let me have functions of type node*. But, I know that when you don't use classes and just put everything in one file, functions of type node* work.



Here is my list.h:



#include


struct node
{
int data;
node* next;
};

class list
{
public:
// these functions were already written by the school and included in the .o file

list();
~list();
void build();
void display();

// my functions
void lastTwo();

private:
node* head;

node* tail;
node* lastTwo(node *& current, node *& tail);
}


And list.cpp:



void list::lastTwo(){
node* current = head;
node * newHead = lastTwo(current, tail);

head = newHead;
delete newHead;
head->next = tail;
}

node* lastTwo(node *& current, node *& tail){
if(current->next == tail){
return current;
}
else if(current->next != tail){

node* temp = current;
current = current->next;
temp->next = NULL;
delete temp;
lastTwo(current, tail);
}
return NULL;
}



Any ideas on what might be the problem, and what the correct way to do this is, would be really appreciated! Thank you

No comments:

Post a Comment

plot explanation - Why did Peaches' mom hang on the tree? - Movies & TV

In the middle of the movie Ice Age: Continental Drift Peaches' mom asked Peaches to go to sleep. Then, she hung on the tree. This parti...