I have a data structure (Circular Doubly Linked List) of N integers. I have to modify it by minimising some quantity. In some cases of arrangements of numbers, I will have to check whether the quantity is minimised by checking the modified data structure in two or more cases. I would like to know if , my attempt is good enough and if any better algorithm is available for those cases. I am not explicitly stating the problem as I would like to solve it myself but for the sake of debugging, we have to take two adjacent elements of the list which have minimum sum and replace them with the sum. We have to calculate the sum of the sums in each stage. (N to 1)
I have created two functions 2 functions, : mod() and demod(), to modify and demodify the list. In those cases, I will mod() the structure for case 1 and store quantity1, demod() it, then mod() it for case 2, and store quantity2. Then, I will select the mod() for that case which has least quantity. index and temp are two pointers where I have to evaluate the quantities. The edited code is given below.
struct Node {
long long int data;
struct Node * prev;
struct Node * next;
};
void mod(struct Node * index, long long int val) {
struct Node * temp1 = index -> next;
index -> data = val;
index -> next = (index -> next) -> next;
((index -> next) -> next) -> prev = index;
//free(temp1);
}
void demod(struct Node * index ,long long int a){
long long int b = index->data - a;
index->data = a;
struct Node * new_Node = new Node;
new_Node->data = b;
new_Node -> next = index -> next;
index->next = new_Node;
new_Node->prev = index;
(new_Node->next)->prev = new_Node;
}
long long int value(struct Node * start, int length) {
long long int val;
struct Node * index = start->prev;
val = f(start -> prev);
struct Node * temp = start;
while (temp -> next != start) {
if (val > f(temp)) {
index = temp;
val = f(temp);
}
temp = temp -> next;
}
cout << "val : " << val << "--";
temp = start;
while (temp -> next != start) {
if (f(temp)==val && (index -> next == temp)) {
std::cout << "*##";
long long int init1 = index -> data;
//displayList(start);
// cout << init1 << " ";
mod(index, val, start);
cout << "start case 1\n ";
long long int temp1 = solve(start, length - 1);
cout << "end case 1\n ";
demod(index, init1);
displayList(start);
mod(temp, val, start);
displayList(start);
cout << "start case 2 \n";
long long int temp2 = solve(start, length - 1);
cout << "end case 2\n";
if (temp1 > temp2) {
mod(temp, val, start);
return val;
} else {
mod(index, val, start);
return val;
}
/*if ((index -> prev) -> data > ((temp -> next) -> next) -> data) {
std::cout << "*";
index = index -> next;
}*/
}
temp = temp -> next;
}
// cout << "index data " << index -> data << "\n";
mod(index, val, start);
return val;
}
... Full Code (162 lines) https://drive.google.com/open?id=1oD1pEr3_seX6kIzErpRG-Xu3s_95UVBj The code now has some corner cases that I have to correct and I have the basic problem of using the data structure again and again.
So I'm somewhat struggling to follow your question, but mod is supposed to change the value of index and remove the next node after index from the list?
If so then this is bugged
index->next = index->next->next;
index->next->next->prev = index;
What you're forgetting is that you change that value of index->next->next in the first statement, but then your second statement tries to use the old value.
It should be this (my preference)
index->next = index->next->next;
index->next->prev = index;
or this (switching the order of the two statements)
index->next->next->prev = index;
index->next = index->next->next;
I've little doubt there are more bugs in the rest of the code. This kind of pointer heavy code is extremely tricky to get right.
You also have commented out the bugged code free(temp1);. If you allocate memory with new it must be deallocated with delete. If you allocate memory with new[] it must be deallocated with delete[]. If you allocate memory with malloc it must be deallocated with free. Don't mix these up, they are not equivalent.