I wrote a post on a similar topic yesterday about my destructor for my Huffman tree class program. I have since isolated an issue with how my tree is being built that has me pretty baffled at the moment. I'll share the code below, along with what exactly the program is spitting out into memory.
It's my current theory concerning my weird memory location issue (which is discussed further below), that there is something funky going on with the list I'm using. Memory locations are being swapped around. For instance, when a parent node is created, this parent node should show up again when it's popped out of the list, but it's coming out with a different memory location. Could this be the source of my issue? But why is it doing that?
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
|
Huffman :: Huffman (list <BTree> nodes)
{
nodes.sort(); //Get it into ascending order
BTree *one, *two, *temp;
while (nodes.size() > 1)
{
one = &nodes.front();
nodes.pop_front();
two = &nodes.front();
nodes.pop_front();
temp = insert(one, two);
nodes.push_back(*temp);
nodes.sort();
//reset(temp);
//reset(one);
//reset(two);
}
root = temp;
//createCodes();
nodes.pop_front();
}
BTree* Huffman :: reset(BTree *in)
{
in->setData(0);
in->setLeft(0);
in->setRight(0);
return in;
}
BTree* Huffman :: insert(BTree *lower, BTree *higher)
{
BTree *tree = new BTree;
tree->setLeft(lower);
tree->setRight(higher);
tree->setData(lower->getData() + higher->getData());
return tree;
}
|
Oh, and here is the main which is putting the nodes onto the list:
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
|
int main()
{
ifstream fin("assign15.in");
list <BTree> nodes;
int frequency;
char letter;
if (fin.fail())
{
cout << "Error opening 'assign15.in'... Terminating...\n";
exit(1);
}
for (int i = 0; i < 26; i++)
{
fin >> frequency;
letter = 'a' + i;
BTree *temp = new BTree;
temp->setData(frequency);
temp->setLetter(letter);
nodes.push_front(*temp);
}
fin.close();
Huffman tree(nodes);
return 0;
}
|
Below is the detailed step by step function. The loop loads two nodes from the linked list onto the temp variables 'one' and 'two'. The addresses to each of these nodes is given. Then, a new temp node is created with 'one' and 'two' as children. The temp node is then pushed onto the list.
Notes: The address of all the 'temp' nodes are unique. However, it doesn't seem like this address is being saved to the list.
Notes: Many addresses are recurring within the output, showing the issues, but why is it doing this?
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
One set to 9(0xdb7650) Two set to 10(0xdb7a50)
pushing parent node with values:
(0xdb6a40)P: 19 - L: 9 - R: 10
One set to 19(0xdb7a50) Two set to 20(0xdb76d0)
pushing parent node with values:
(0xdb6a70)P: 39 - L: 19 - R: 20
One set to 20(0xdb7890) Two set to 39(0xdb76d0)
pushing parent node with values:
(0xdb6aa0)P: 59 - L: 20 - R: 39
One set to 52(0xdb7a10) Two set to 59(0xdb76d0)
pushing parent node with values:
(0xdb6ad0)P: 111 - L: 52 - R: 59
One set to 93(0xdb7750) Two set to 111(0xdb76d0)
pushing parent node with values:
(0xdb6b00)P: 204 - L: 93 - R: 111
One set to 161(0xdb7b10) Two set to 162(0xdb7c50)
pushing parent node with values:
(0xdb6b30)P: 323 - L: 161 - R: 162
One set to 188(0xdb7690) Two set to 203(0xdb7710)
pushing parent node with values:
(0xdb6b60)P: 391 - L: 188 - R: 203
One set to 204(0xdb76d0) Two set to 225(0xdb7990)
pushing parent node with values:
(0xdb6b90)P: 429 - L: 204 - R: 225
One set to 228(0xdb7b50) Two set to 229(0xdb78d0)
pushing parent node with values:
(0xdb6bc0)P: 457 - L: 228 - R: 229
One set to 310(0xdb7790) Two set to 320(0xdb7c10)
pushing parent node with values:
(0xdb6bf0)P: 630 - L: 310 - R: 320
One set to 323(0xdb7c50) Two set to 365(0xdb7bd0)
pushing parent node with values:
(0xdb6c20)P: 688 - L: 323 - R: 365
One set to 391(0xdb7710) Two set to 403(0xdb79d0)
pushing parent node with values:
(0xdb6c50)P: 794 - L: 391 - R: 403
One set to 429(0xdb7990) Two set to 457(0xdb78d0)
pushing parent node with values:
(0xdb6c80)P: 886 - L: 429 - R: 457
One set to 514(0xdb7ad0) Two set to 603(0xdb7850)
pushing parent node with values:
(0xdb6cb0)P: 1117 - L: 514 - R: 603
One set to 630(0xdb7c10) Two set to 659(0xdb7810)
pushing parent node with values:
(0xdb6ce0)P: 1289 - L: 630 - R: 659
One set to 688(0xdb7bd0) Two set to 718(0xdb7a90)
pushing parent node with values:
(0xdb6d10)P: 1406 - L: 688 - R: 718
One set to 719(0xdb7950) Two set to 794(0xdb79d0)
pushing parent node with values:
(0xdb6d40)P: 1513 - L: 719 - R: 794
One set to 794(0xdb7910) Two set to 805(0xdb7c90)
pushing parent node with values:
(0xdb6d70)P: 1599 - L: 794 - R: 805
One set to 886(0xdb78d0) Two set to 959(0xdb77d0)
pushing parent node with values:
(0xdb6da0)P: 1845 - L: 886 - R: 959
One set to 1117(0xdb7850) Two set to 1231(0xdb7b90)
pushing parent node with values:
(0xdb6dd0)P: 2348 - L: 1117 - R: 1231
One set to 1289(0xdb7810) Two set to 1406(0xdb7a90)
pushing parent node with values:
(0xdb6e00)P: 2695 - L: 1289 - R: 1406
One set to 1513(0xdb79d0) Two set to 1599(0xdb7c90)
pushing parent node with values:
(0xdb6e30)P: 3112 - L: 1513 - R: 1599
One set to 1845(0xdb77d0) Two set to 2348(0xdb7b90)
pushing parent node with values:
(0xdb6e60)P: 4193 - L: 1845 - R: 2348
One set to 2695(0xdb7a90) Two set to 3112(0xdb7c90)
pushing parent node with values:
(0xdb6e90)P: 5807 - L: 2695 - R: 3112
One set to 4193(0xdb7b90) Two set to 5807(0xdb7c90)
pushing parent node with values:
(0xdb6ec0)P: 10000 - L: 4193 - R: 5807
|
