fork download 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include <cstring>
  6. using namespace std;
  7.  
  8. struct Node
  9. {
  10. 	char data;
  11. 	unsigned freq;
  12. 	Node *left, *right;
  13.  
  14. 	Node(char data=' ', unsigned freq=0)
  15. 	{
  16. 		left = right = NULL;
  17. 		this->data = data;
  18. 		this->freq = freq;
  19. 	}
  20. 	bool operator<(Node x)
  21. 	{
  22. 		return freq < x.freq;
  23. 	}
  24. 	bool operator>(Node x)
  25. 	{
  26. 		return freq > x.freq;
  27. 	}
  28. };
  29. void print_node(Node x)
  30. {
  31. 	printf("%c: %d\n",x.data,x.freq);
  32. 	if(x.left)
  33. 		printf("left:: %c: %d\n",x.left->data,x.left->freq);
  34. 	if(x.right)
  35. 		printf("right:: %c: %d\n",x.right->data,x.right->freq);
  36. 	cout<<endl;
  37. }
  38. void swap(Node *x,Node *y)
  39. {
  40. 	//printf("xf: %d xd: %c yf: %d % yd: %c\n",x->freq,x->data,y->freq,y->data);
  41. 	int temp = x->freq;
  42. 	x->freq = y->freq;
  43. 	y->freq = temp;
  44. 	char t = x->data;
  45. 	x->data = y->data;
  46. 	y->data = t;
  47. }
  48. void min_heapify(Node *A, int n, int i)
  49. {
  50. 	int l = 2*(i+1)-1; int r = 2*(i+1);
  51. 	int smallest;
  52. 	if (l < n && A[l] < A[i])
  53. 		smallest = l;
  54. 	else
  55. 		smallest = i;
  56. 	if (r < n && A[r] < A[smallest])
  57. 		smallest = r;
  58. 	if (smallest != i)
  59. 	{
  60. 		swap(&A[i],&A[smallest]);
  61. 		min_heapify(A,n,smallest);
  62. 	}
  63. }
  64. void build_min_heap(Node *A, int n)
  65. {
  66. 	for(int i = n/2-1; i >= 0; i--)
  67. 	{
  68. 		min_heapify(A,n,i);
  69. 	}
  70. }
  71. Node extract_min(Node *A, int &n)
  72. {
  73. 	Node min = A[0];
  74. 	A[0] = A[n-1];
  75. 	n--;
  76. 	min_heapify(A,n,0);
  77. 	return min;
  78. }
  79. void insert(Node *A, int &n, Node key)
  80. {
  81. 	n++;
  82. 	int i = n-1;
  83. 	while(i > 0 && A[i/2] > key)
  84. 	{
  85. 		A[i] = A[i/2];
  86. 		i = i/2;
  87. 	}
  88. 	A[i] = key;
  89. }
  90. //ERROR IS IN THIS FUNCTION
  91. //I need to make a new node z and have it's left and right children
  92. //point the the smallest two nodes in heap. When I assign the address
  93. //of the x and y nodes to z.left and z.right it's fine. But then when 
  94. //I loop around again and reinitialize x, y, and z those address locations
  95. //are destroyed and the left and right children no longer exist.
  96. Node Huffman(Node *Q, int n)
  97. {
  98.  
  99. 	while(n>1)
  100. 	{
  101. 		//ERROR IS THIS ASSIGNMENT OF VARIABLES		
  102. 		Node x,y,z;
  103. 		x = extract_min(Q,n);
  104. 		y = extract_min(Q,n);
  105. 		z.left = &x;
  106. 		z.right = &y;
  107. 		z.freq = x.freq + y.freq;
  108. 		insert(Q, n, z);
  109. 	}
  110. 	Node root = extract_min(Q,n);
  111. 	print_node(root);
  112. 	print_node(*root.left);
  113. 	return root;
  114. }
  115. void traverse(Node x)
  116. {	
  117.  
  118. 	print_node(x);
  119. 	if(x.left)
  120. 		traverse(*x.left);
  121.  
  122. 	if(x.right)
  123. 		traverse(*x.right);
  124. }
  125. int main(int argc, char *argv[])
  126. {	
  127. 	Node B[] = {{'c',6},{'d',5},{'e',7},{'z',15}};
  128. 	int n = 4;
  129. 	build_min_heap(B,n);
  130. 	Node C[4] = B;
  131. 	int n_C = n;
  132. 	cout<<"What it should print like\n";
  133. 	//loop1
  134. 	Node z1;
  135. 	Node x1 = extract_min(B,n);
  136. 	Node y1 = extract_min(B,n);
  137. 	z1.left = &x1;
  138. 	z1.right = &y1;
  139. 	z1.freq = x1.freq+y1.freq;
  140. 	insert(B,n,z1);
  141. 	//loop2
  142. 	Node z2;
  143. 	Node x2 = extract_min(B,n);
  144. 	Node y2 = extract_min(B,n);
  145. 	z2.left = &x2;
  146. 	z2.right = &y2;
  147. 	z2.freq = x2.freq+y2.freq;
  148. 	insert(B,n,z2);
  149. 	//loop3
  150. 	Node z3;
  151. 	Node x3 = extract_min(B,n);
  152. 	Node y3 = extract_min(B,n);
  153. 	z3.left = &x3;
  154. 	z3.right = &y3;
  155. 	z3.freq = x3.freq+y3.freq;
  156. 	insert(B,n,z3);
  157. 	/*//loop4
  158. 	Node z4;
  159. 	Node x4 = extract_min(B,n);
  160. 	Node y4 = extract_min(B,n);
  161. 	z4.left = &x4;
  162. 	z4.right = &y4;
  163. 	z4.freq = x4.freq+y4.freq;
  164. 	insert(B,n,z4);*/
  165. 	Node root = extract_min(B,n);
  166. 	traverse(root);
  167.  
  168. 	cout<<"What actually happens\n";
  169. 	root = Huffman(C,n_C);
  170.  
  171. 	//print_node(root);
  172.  
  173.  
  174. 	return 0;
  175.  
  176. }
Success #stdin #stdout 0s 3416KB
comments (?)
stdin 
Standard input is empty
stdout 
What it should print like
 : 33
left:: z: 15
right::  : 18

z: 15
left:: d: 5
right:: c: 6

d: 5

c: 6

 : 18
left:: e: 7
right::  : 11

e: 7

 : 11

What actually happens
 : 33
left:: z: 15
right::  : 18

z: 15
left:: z: 15
right::  : 18
https://ideone.com/2g8ELi
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!