Why is my program crashing/segmentation faulting?

[vaultDweller]

So for an assignment, we're making Huffman trees, and I'm trying to write a function that finds the two smallest frequencies in a list then removes them then makes them the children of a new treeNode and inserts it into the list again (in the style of traditional Huffman trees), although my program seems to be crashing around the line just after the second call to the remove function, can anyone help me find out why is would crash and why my solution for making a Huffman tree isn't working? Thanks! :)

typedef TreeNode* Element;
typedef Frequency* TreeElement;

struct TreeNode {

  TreeElement data; //stores a pointer to the data in this tree node
  TreeNode *left; //reference to the left child tree
  TreeNode *right; //reference to the right child tree

};

struct ListNode {
  Element data;  // stores a pointer to data in node
  ListNode *next; // reference to next node in list
};

struct List {
  ListNode *head;  // reference to the first node in the list
  int numElements; // the number of nodes in the list
};

struct HuffmanTree {
  TreeNode *root;
};

struct FrequencyList {
  List *freqs;
};

struct Frequency {
  char data; // the character being represented
  int count; // the number of occurrences of the character
};

  HuffmanTree *createHuffmanTree(FrequencyList *frequencies) {
  
	List * newList = new List;
	newList = frequencies->freqs;
	
	TreeNode * newTree1 = new TreeNode;
	TreeNode * newTree2 = new TreeNode;
	TreeNode * root = new TreeNode;
	
	
		while (frequencies != NULL) {
	
			newTree1 = remove_smallest(frequencies); // removes and returns smallest treeNode from list
			newTree2 = remove_smallest(frequencies);
			root->data->count = newTree1->data->count + newTree2->data->count; 
			root->left = newTree1;
			root->right = newTree2;
			root->data->data = 'D';
			insert(newList, root);	// inserts back into list
	
		}
		
		HuffmanTree * newHuffmanTree = new HuffmanTree;
		newHuffmanTree->root = root;
  
  	return newHuffmanTree;

}

[Moschops]

A TreeNode object, newly created, contains a TreeElement object.

A TreeElement object is actually a pointer-to-Frequency.

So when you create a TreeNode object, that pointer-to-Frequency will point at some random memory somewhere until you create a Frequency object and make the pointer point at it. If you don't do this, and you try to dereference that pointer (which is pointing at random memory somewhere) you'll get a segFault.

Did you create a Frequency object somewhere and make this pointer-to-Frequency object (named data) point at it?

[vaultDweller]

@Moschops hmm.. I'm not really sure. I thought that because I set remove_smallest to equal the new TreeNode that it solved that part? What should I do to make sure that frequency object is pointing to the right place?

[Moschops]

Also, what is line 41 and 42 for, given that lines 48 and 49 reassign those pointers anyway? Looks like a memory leak; the TreeNode objects created on line 41 and 42 never get used and never get deleted.

What should I do to make sure that frequency object is pointing to the right place?

No idea. I have no idea what your remove_smallest function does. When do you actually assign data to the TreeNode?

[vaultDweller]

@Moschops Line 41 and 42 create two new treeNodes then on line 48 and 49 it sets those two new tree nodes to equal the remove_smallest function which will return the smallest treeNode in the Frequency List, then create a new node called root that combines them.

[Moschops]

then on line 48 and 49 it sets those two new tree nodes to equal the remove_smallest function

No it doesn't. It throws away those two new Treenodes and instead points at whatever remove_smallest tell it to point to. You should replace lines 41 and 42 with this:

	TreeNode * newTree1;
	TreeNode * newTree2;

[vaultDweller]

Ok, I see. I changed that and I'm still getting a "segmentation fault 11".

[vaultDweller]

It seems to crash right after the "root->data->count = newTree1->data->count + newTree2->data->count;".

[Moschops]

Yes, that won't have fixed it. That's something else entirely.

Does it crash AFTER that, or DURING that? Have you tried using a debugger? It's really very easy. You're almost certainly dereferencing a pointer that's pointing at random memory because you're making pointers and not pointing them at anything.

http://www.cplusplus.com/articles/iwTbqMoL/ (This article more or less assumes you're using a *nix)

[vaultDweller]

Ok Ill try that. It would appear that it crashes during that.