Implementing a specific type of singly linked list
void insert(int number){
Node* temp0 = NULL;
Node* temp1 = head;
Node* temp = new Node();
int sum = 0;
while(temp1!= NULL && sum>=number){
sum+=temp1->content;
temp0=temp1;
temp1=temp1->next;
}
if(temp0 == NULL){
temp->content = number;
temp->next = head;
if(head!=NULL){
head->content -= temp->content;
}
head = temp;
}
else{
temp0->next = temp;
temp->content = number - sum;
temp1->content -= temp->content;
temp->next = temp1;
}// end of else
}// end of void insert
I ran into a problem, which i described in one of my previous questions,
but still, i'm looking to implement the solution on my own. In short, i
want to make a "relative" list: for example, for elements 1 5 7 2 4 6 the
list would look like 1 1 2 1 1 1
I would make a priority queue list 1 2 4 5 7 6, and then i would change
elements relative to the previous one:first element would stay 1,second
would be 2-1 = 1, third would be 4-2 = 2, fourth 5-4 = 1 and so on. When i
form a priority queue, i would replace the current element with the
difference of it's value and the value of the previous element. I'm having
problems implementing the insert feature. The code is given at the top of
the question.
The idea is, i go through the list, adding the "difference" (which is the
content field of my Node* structure) to a counter variable. When the sum
counter becomes greater or equal to the element i need to insert, i found
the position where to insert it.
If temp0 is null, i insert the element on the first position. If it's not
the only element, i update the content of the next element - head, which
was the previous first element.
If the number needs to be inserted somewhere in the middle of the list (or
at the end), i update the content as sum - number, which would be a number
>= 0, which is okay. Also, i update the content of the new's next element
(temp1) as temp->content - temp->content.
For some reason, this does not work. When i insert 4 2 8, instead of 2 2
4, i'm getting 8 -6 2 as the result list.
No comments:
Post a Comment