|
/*只需要看一处。在标2.的注释处，newNode是parent的引用。经过这一条语句，等号右面的值被改变，其右儿子的值从2变为3。很不理解。标1.的注释是进入注释2.的语句编译能通过，不过运行出错。我知道出错的原因，只不理解值被改变的原因。*/#include#includeusing namespace std;//19.10templateclass 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; }};templateMinHeap::MinHeap(int num){ if (num = 0 && heapMin[par] > heapMin[pos]){ swap(par, pos); pos = par; }}templatevoid MinHeap::Insert(T&newNode){ if (CurrentSize == MaxSize){ T*temp = new T[++MaxSize]; for (int i = 0; i < CurrentSize; i++){ temp = heapMin; } temp[CurrentSize] = newNode; delete[]heapMin; heapMin = new T[MaxSize]; for (int i = 0; i < MaxSize; i++){ heapMin = temp; } delete[]temp; temp = NULL; return; } else{ heapMin[CurrentSize] = newNode; //断点进入这里，在刚进入函数时newNode值是被传进来的值，经过这一行后，newNode值被改变 CurrentSize++; siftUp(CurrentSize - 1); }}templateT&MinHeap::RemoveMin(T*&rt){ swap(0, --CurrentSize); siftDown(0); rt = &heapMin[CurrentSize]; return heapMin[CurrentSize];}templateclass HuffmanTree;templateclass HuffmanTreeNode{ friend class HuffmanTree;private: HuffmanTreeNode*leftchild, *rightchild, *parent; T data;public: HuffmanTreeNode*getLChild(); HuffmanTreeNode*getRChild(); HuffmanTreeNode*getParent(); bool operator < (HuffmanTreeNode&t){ return data < t.data; } bool operator > (HuffmanTreeNode&t){ return data>t.data; } HuffmanTreeNode(); T getData(){ return data; }};templateHuffmanTreeNode::HuffmanTreeNode(){ leftchild = rightchild = parent = NULL;}templateHuffmanTreeNode* HuffmanTreeNode::getLChild(){ return leftchild;}templateHuffmanTreeNode* HuffmanTreeNode::getRChild(){ return rightchild;}templateHuffmanTreeNode*HuffmanTreeNode::getParent(){ return parent;}templateclass HuffmanTree{private: HuffmanTreeNode*root; void mergeTree(HuffmanTreeNode*&left, HuffmanTreeNode*&right, HuffmanTreeNode*&parent); void deleteTree(HuffmanTreeNode*rt);public: virtual ~HuffmanTree(){ deleteTree(root); } HuffmanTree(T *weight, int num); void preOrder(HuffmanTreeNode*rt){ if (rt == NULL)return; cout data leftchild); preOrder(rt->rightchild); } HuffmanTreeNode*getRoot(){ return root; }};templateHuffmanTree::HuffmanTree(T *weight, int num){ root = NULL; MinHeapheap(num); HuffmanTreeNode*nodelist = new HuffmanTreeNode[num*3]; for (int i = 0; i < num; i++){ nodelist.data = weight; nodelist.rightchild = nodelist.leftchild = nodelist.parent = NULL; heap.Insert(nodelist); } HuffmanTreeNode*temp; for (int i = 0; i < num - 1; i++){ HuffmanTreeNode*left = new HuffmanTreeNode; HuffmanTreeNode*right = new HuffmanTreeNode; HuffmanTreeNode*parent = new HuffmanTreeNode; heap.RemoveMin(left); heap.RemoveMin(right); mergeTree(left, right, parent); heap.Insert(*parent); //1.断点进入这里 root = parent; } root; delete[]nodelist;}templatevoid HuffmanTree::deleteTree(HuffmanTreeNode*rt){ if (rt == NULL)return; deleteTree(rt->rightchild); deleteTree(rt->leftchild); delete rt;}templatevoid HuffmanTree::mergeTree(HuffmanTreeNode*&left, HuffmanTreeNode*&right, HuffmanTreeNode*&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 }; HuffmanTreeheap(weight, 2);} |
天盟APP下载
