Well, I'm still stuck here. I thought that I would be able to create a copy of my values vector of Huff pointers, and start on them as a method of going from the leaves of this budding Huffman tree up to it's root. I did not use delete in the deletePtr function because I thought it would interfere with the pointer in the traverse function recognizing the tree structure that I have created in main before calling it. Well, after I call it, I have traced the fact that the while loop:
never executes. Furthermore, I can't figure out why parent is always NULL. I expected it to be recognized, but clearly I am mistaken. Any ideas why this attempted traversal of the Huffman algorithm I have dreamed up has not gotten off the launching pad? I may have to wind up doing a pre-order traversal. If so, could someone give me some pointers about that? Thanks, SteveCode:void traverse(vector<Huff*> v) // took out ampersand { int i; Huff* p; stack<int> s; //cout<<v[0]->parent<<endl; for(i=0; i<v.size(); i++) { p=v[i]; cout<<p->parent<<endl; /***************************here************/ while(p->parent != NULL) { cout<<"Debug"<<endl; p=p->parent; if(p->left->ch == v[i]->ch) { s.push(0); } else { s.push(1); } } //cout<<v[i]->ch<<" "; while(!s.empty()) { cout<<"Debug"; cout<<s.top(); s.pop(); } } cout<<endl; return; }
Code:#include<iostream> #include<vector> #include<fstream> #include<stack> using namespace std; struct Huff; void deletePtr(vector<Huff*>& v, Huff* m); Huff* findMinimum(vector<Huff*>& v); void traverse(vector<Huff*> v); // took out ampersand struct Huff { Huff(); int count; char ch; Huff* left; Huff* right; Huff* parent; }; int main(int argc, char* argv[]) { if(argc<2) { cout<<"Not enough arguments were provided."<<endl; return -1; } ifstream myFile(argv[1], ios::in); if(!myFile.is_open()) { cout<<"Unknown file specified."<<endl; return -1; } char cz; int i; vector<Huff*> values; while(myFile.get(cz)) { if(cz < 'a' || cz > 'z') continue; for(i=0; i<values.size(); i++) { if(values[i]->ch == cz) { values[i]->count++; break; } } if(values.size()==i) { Huff* h = new Huff; h->ch=cz; h->count=1; values.push_back(h); } } if(values.size() == 0) { cout<<"File is empty.\n"; return 0; } if(values.size() == 1) { cout<<values[0]->ch<<"1"<<endl; } vector<Huff*> copy; for(i=0; i<values.size(); i++) { copy.push_back(values[i]); } Huff* min; Huff* min2; while(values.size() > 1) { min=findMinimum(values); deletePtr(values, min); min2=findMinimum(values); deletePtr(values, min2); Huff* p=new Huff; p->left=min; p->right=min2; p->count=min->count+min2->count; values.push_back(p); } traverse(copy); return 0; } Huff::Huff() : ch(0), count(0), left(NULL), right(NULL), parent(NULL) { } Huff* findMinimum(vector<Huff*>& v) { int i, minCo=v[0]->count; char minCh=v[0]->ch; Huff* h3=v[0]; for(i=1; i<v.size(); i++) { if(v[i]->count < minCo) { minCo=v[i]->count; minCh=v[i]->ch; h3=v[i]; } } return h3; } void deletePtr(vector<Huff*>& v, Huff* m) { int i; i=0; while(i < v.size() && v[i]->ch != m->ch) { i++; } for( ; i<v.size()-1; i++) { v[i]=v[i+1]; } v.pop_back(); // decided not to delete m } void traverse(vector<Huff*> v) // took out ampersand { int i; Huff* p; stack<int> s; //cout<<v[0]->parent<<endl; for(i=0; i<v.size(); i++) { p=v[i]; cout<<p->parent<<endl; // always "0" while(p->parent != NULL) { cout<<"Debug"<<endl; // never executes p=p->parent; if(p->left->ch == v[i]->ch) { s.push(0); } else { s.push(1); } } cout<<v[i]->ch<<" "; while(!s.empty()) { cout<<"Debug"; cout<<s.top(); s.pop(); } } cout<<endl; return; }
That's just a wild guess, by the way. But I don't really see why you need to have all your pointers in a vector; all you really need, usually, is the root pointer and a few good recursive functions that do the traversing from there. I'm pretty sure Sang-drax posted a nice implementation of that for a contest a while back (though it had a minor bug). I wrote a similar implementation later, which you can find at my website (see my signature) if you're interested.
