1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#include <stdlib.h>
#include "dfs.h"
#include "structs.h"
#include "common.h"
struct front_item * dfs(struct data * data) {
struct front_item * front = new_front_item(0, 0, NULL, NULL);
struct front_item * front_last = front;
struct tree_item * tree = new_tree_item(0, 0, 0, 0, NULL, NULL);
/* Iterative dfs */
do {
/* Check if tree is leaf. If true:
* Add item to front_item;
* Update tree to tree->next;
* Free leaf;
* Continue;
*/
if(tree->depth == data->N) {
front_last->next = new_front_item(tree->values.p, tree->values.w, front_last, NULL);
front_last = front_last->next;
struct tree_item * old = tree;
tree = tree->next;
if(tree != NULL) {
tree->prev = old->prev;
}
free(old);
continue;
}
/* Make left node (select item) */
struct tree_item * left = new_tree_item(
tree->depth + 1,
tree->itemi + 1,
tree->values.w + data->items[tree->itemi].w,
tree->values.p + data->items[tree->itemi].p,
tree->prev,
tree
);
/* Make right node (do not select item) */
struct tree_item * right = new_tree_item(
tree->depth + 1,
tree->itemi + 1,
tree->values.w,
tree->values.p,
left,
tree->next
);
/* Update left next */
left->next = right;
/* Update tree to left node and free old node */
struct tree_item * old = tree;
tree = left;
free(old);
} while(tree != NULL);
/* Remove first item from front (only a placeholder) */
front=front->next;
free(front->prev);
front->prev = NULL;
return front;
}
|
