/* 只需要看一處。在標(biāo)2.的注釋處，newNode是parent的引用。經(jīng)過這一條語句， 等號右面的值被改變，其右兒子的值從2變?yōu)?。很不理解。 標(biāo)1.的注釋是進(jìn)入注釋2.的語句 編譯能通過，不過運(yùn)行出錯。我知道出錯的原因，只不理解值被改變的原因。 */ #include<iostream> #include<stack> using?namespace?std; //19.10 template<class?T> class?MinHeap{ private: int?CurrentSize,?MaxSize; T*heapMin; public: T&RemoveMin(T*&rt); void?Insert(T&newNode); MinHeap(int?num); virtual?~MinHeap(){?if?(MaxSize?>?0)delete[]heapMin;?}; public: void?swap(int?pos_x,?int?pos_y); void?siftDown(int?pos); void?siftUp(int?pos); int?getlson(int?pos){ return?pos?*?2?+?1; } int?getrson(int?pos){ return?pos?*?2?+?2; } int?getparent(int?pos){ return?(pos?-?1)?/?2; } }; template<class?T> MinHeap<T>::MinHeap(int?num){ if?(num?<=?0)return; MaxSize?=?num*3; CurrentSize?=?0; heapMin?=?new?T[num]; } template<class?T> void?MinHeap<T>::swap(int?pos_x,?int?pos_y){ T?temp?=?heapMin[pos_x]; heapMin[pos_x]?=?heapMin[pos_y]; heapMin[pos_y]?=?temp; } template<class?T> void?MinHeap<T>::siftDown(int?pos){ int?pos_min?=?getlson(pos); T?temp?=?heapMin[pos]; while?(pos?<?CurrentSize){ if?(pos_min+1<CurrentSize&&heapMin[pos_min]>heapMin[pos_min?+?1])pos_min++; if?(pos_min<CurrentSize&&heapMin[pos]>heapMin[pos_min]){ swap(pos,?pos_min); pos?=?pos_min; } else?break; } } template<class?T> void?MinHeap<T>::siftUp(int?pos){ int?par?=?getparent(pos); while?(par?>=?0?&&?heapMin[par]?>?heapMin[pos]){ swap(par,?pos); pos?=?par; } } template<class?T> void?MinHeap<T>::Insert(T&newNode){ if?(CurrentSize?==?MaxSize){ T*temp?=?new?T[++MaxSize]; for?(int?i?=?0;?i?<?CurrentSize;?i++){ temp[i]?=?heapMin[i]; } temp[CurrentSize]?=?newNode; delete[]heapMin; heapMin?=?new?T[MaxSize]; for?(int?i?=?0;?i?<?MaxSize;?i++){ heapMin[i]?=?temp[i]; } delete[]temp; temp?=?NULL; return; } else{ heapMin[CurrentSize]?=?newNode;??//斷點(diǎn)進(jìn)入這里，在剛進(jìn)入函數(shù)時newNode值是被傳進(jìn)來的值，經(jīng)過這一行后，newNode值被改變 CurrentSize++; siftUp(CurrentSize?-?1); } } template<class?T> T&MinHeap<T>::RemoveMin(T*&rt){ swap(0,?--CurrentSize); siftDown(0); rt?=?&heapMin[CurrentSize]; return?heapMin[CurrentSize]; } template<class?T>class?HuffmanTree; template<class?T> class?HuffmanTreeNode{ friend?class?HuffmanTree<T>; private: HuffmanTreeNode<T>*leftchild,?*rightchild,?*parent; T?data; public: HuffmanTreeNode<T>*getLChild(); HuffmanTreeNode<T>*getRChild(); HuffmanTreeNode<T>*getParent(); bool?operator?<?(HuffmanTreeNode<T>&t){?return?data?<?t.data;?} bool?operator?>?(HuffmanTreeNode<T>&t){?return?data>t.data;?} HuffmanTreeNode(); T?getData(){ return?data; } }; template<class?T> HuffmanTreeNode<T>::HuffmanTreeNode(){ leftchild?=?rightchild?=?parent?=?NULL; } template<class?T> HuffmanTreeNode<T>*?HuffmanTreeNode<T>::getLChild(){ return?leftchild; } template<class?T> HuffmanTreeNode<T>*?HuffmanTreeNode<T>::getRChild(){ return?rightchild; } template<class?T> HuffmanTreeNode<T>*HuffmanTreeNode<T>::getParent(){ return?parent; } template<class?T> class?HuffmanTree{ private: HuffmanTreeNode<T>*root; void?mergeTree(HuffmanTreeNode<T>*&left,?HuffmanTreeNode<T>*&right,?HuffmanTreeNode<T>*&parent); void?deleteTree(HuffmanTreeNode<T>*rt); public: virtual?~HuffmanTree(){?deleteTree(root);?} HuffmanTree(T?*weight,?int?num); void?preOrder(HuffmanTreeNode<T>*rt){ if?(rt?==?NULL)return; cout?<<?rt->data?<<?"?"; preOrder(rt->leftchild); preOrder(rt->rightchild); } HuffmanTreeNode<T>*getRoot(){ return?root; } }; template<class?T> HuffmanTree<T>::HuffmanTree(T?*weight,?int?num){ root?=?NULL; MinHeap<HuffmanTreeNode<T>?>heap(num); HuffmanTreeNode<T>*nodelist?=?new?HuffmanTreeNode<T>[num*3]; for?(int?i?=?0;?i?<?num;?i++){ nodelist[i].data?=?weight[i]; nodelist[i].rightchild?=?nodelist[i].leftchild?=?nodelist[i].parent?=?NULL; heap.Insert(nodelist[i]); } HuffmanTreeNode<T>*temp; for?(int?i?=?0;?i?<?num?-?1;?i++){ HuffmanTreeNode<T>*left?=?new?HuffmanTreeNode<T>; HuffmanTreeNode<T>*right?=?new?HuffmanTreeNode<T>; HuffmanTreeNode<T>*parent?=?new?HuffmanTreeNode<T>; heap.RemoveMin(left); heap.RemoveMin(right); mergeTree(left,?right,?parent); heap.Insert(*parent);??//1.斷點(diǎn)進(jìn)入這里 root?=?parent; } root; delete[]nodelist; } template<class?T> void?HuffmanTree<T>::deleteTree(HuffmanTreeNode<T>*rt){ if?(rt?==?NULL)return; deleteTree(rt->rightchild); deleteTree(rt->leftchild); delete?rt; } template<class?T> void?HuffmanTree<T>::mergeTree(HuffmanTreeNode<T>*&left,?HuffmanTreeNode<T>*&right,?HuffmanTreeNode<T>*&parent){ parent->parent?=?NULL; parent->leftchild?=?left; parent->rightchild?=?right; parent->data?=?left->data?+?right->data; (left->parent?)=?(right->parent)?=?parent; } int?main() { int?weight[3]?=?{?4,?2?}; HuffmanTree<int>heap(weight,?2); }