网站开发框架 c,网站建设 技术 哪些内容,个人申请营业执照流程,提供建立网站服务的公司templateclass T void HeapT::PercolateUp() //为了向上调整为堆#xff0c;我们需要比较当前节点和其父节点的值#xff0c;如果父节点的值比当前节点大#xff0c;则交换它们的值。 { int p size - 1, c (p - 1) / 2;//c表示当前节点的父节点#xff0… templateclass T void HeapT::PercolateUp() //为了向上调整为堆我们需要比较当前节点和其父节点的值如果父节点的值比当前节点大则交换它们的值。 { int p size - 1, c (p - 1) / 2;//c表示当前节点的父节点p表示当前节点。 T temp vec[p]; while (p 0) //为什么不是c0 //在while循环中我们判断当前节点是否已经到达根节点如果是根节点则停止循环。所以条件应该是p 0而不是c 0。 { if (vec[c] temp) break; else { vec[p] vec[c]; p c; c (p - 1) / 2; } } vec[p] temp; //写在while 里面还是外面 目前结点最后会空出来 } templateclass T void HeapT::PercolateDown(int h)// 向下调整为堆如果父亲节点目前结点比孩子结点(较小值大交换 { int p h, c 2 * p 1;// c为p的左孩子 T temp vec[h]; //不定类型 不用写成int while (c size) //怎么修改 { if (c 1 size vec[c 1] vec[c]) //左孩子的下标小于size-1最后一个叶子结点找到左右孩子的最小值 //c size表示当前节点有左孩子而c 1 size表示当前节点有右孩子。根据堆的性质选择较小的孩子进行交换。 { c; } if (temp vec[c]) break; else { vec[p] vec[c]; p c; c 2 * p 1; } } vec[p] temp; } #includeiostream
#includevector
#includequeue
using namespace std;templateclass T
struct BTNode
{T data;BTNode* left, * right;BTNode(const T item T(), BTNode* lptr NULL, BTNode* rptr NULL) :data(item), left(lptr), right(rptr) {}
};void Gotoxy(int x, int y)
{static int level 0, indent 0;if (y 0){indent 0;level 0;}if (level ! y){cout endl;indent 0;level;}cout.width(x - indent);indent x;
}templateclass T
BTNodeT* GetBTNode(const T item, BTNodeT* lp NULL, BTNodeT* rp NULL)
{BTNodeT* p;p new BTNodeT(item, lp, rp);if (p NULL){cout error! endl;}return p;
}struct Location
{int xindent, ylevel;
};templateclass T
void PrintBTree(const BTNodeT* t, int screenwidth)
{if (t NULL){return;}int level 0, offset screenwidth / 2;Location floc, cloc;queueconst BTNodeT* Q;queueLocation LQ;floc.xindent offset;floc.ylevel level;Q.push(t);LQ.push(floc);while (!Q.empty()){t Q.front();floc LQ.front();Q.pop();LQ.pop();Gotoxy(floc.xindent, floc.ylevel);cout t-data;if (floc.ylevel ! level){level;offset offset / 2;}if (t-left){Q.push(t-left);cloc.ylevel floc.ylevel 1;cloc.xindent floc.xindent - offset / 2;LQ.push(cloc);}if (t-right){Q.push(t-right);cloc.ylevel floc.ylevel 1;cloc.xindent floc.xindent offset / 2;LQ.push(cloc);}}cout endl;}templateclass T
class Heap //小根堆 根-叶子 小到大
{vectorT vec;int size;void BuildHeap(void);void PercolateUp();void PercolateDown(int h);
public:Heap(int max 100) : vec(max), size(0) {}Heap(const vectorT vt);int Size(){return size;}void Insert(const T item);void DeleteMin(void);void DeleteMin(T item);
};templateclass T
void HeapT::PercolateUp() //为了向上调整为堆我们需要比较当前节点和其父节点的值如果父节点的值比当前节点大则交换它们的值。
{int p size - 1, c (p - 1) / 2;//c表示当前节点的父节点p表示当前节点。T temp vec[p];while (p 0) //为什么不是c0//在while循环中我们判断当前节点是否已经到达根节点如果是根节点则停止循环。所以条件应该是p 0而不是c 0。{if (vec[c] temp)break;else{vec[p] vec[c];p c;c (p - 1) / 2;}}vec[p] temp; //写在while 里面还是外面 目前结点最后会空出来
}templateclass T
void HeapT::PercolateDown(int h)// 向下调整为堆如果父亲节点目前结点比孩子结点(较小值大交换
{int p h, c 2 * p 1;// c为p的左孩子T temp vec[h];while (c size) //怎么修改{if (c 1 size vec[c 1] vec[c]) //左孩子的下标小于size-1最后一个叶子结点找到左右孩子的最小值{c;}if (temp vec[c])break;else{vec[p] vec[c];p c;c 2 * p 1;}}vec[p] temp;
}templateclass T
void HeapT::Insert(const T item)
{if (size vec.size()){vec.resize(vec.size() *2);}vec[size] item;size;PercolateUp();}templateclass T
void HeapT::BuildHeap(void) //从最后一个非叶子结点a)开始size-1是最后一个叶子结点,a是它的parent
{for (int i size / 2 - 1; i 0; i--){PercolateDown(i);//为该结点的子树调整成堆}
}templateclass T
void HeapT::DeleteMin()
{if (size 0){return;}vec[0] vec[size - 1];size--;PercolateDown(0);
}templateclass T
void HeapT::DeleteMin(T item)
{if (size 0) //删除最小值需要判断堆是否为空{return;}item vec[0];vec[0] vec[size - 1];size--;PercolateDown(0);
}templateclass T
HeapT::Heap(const vectorT vt) : vec(vt.size() 10), size(vt.size())
{for (int i 0; i size; i){vec[i] vt[i];}BuildHeap();
}templateclass T
struct HuffmanNode
{BTNodeT* t;int operator(const HuffmanNode h)//穿入参数是哈夫曼节点 bool类型{return (t-data h.t-data);}int operator(const HuffmanNode h)//穿入参数是哈夫曼节点{return (t-data h.t-data);}
};templateclass T
BTNodeT* MakeHuffman(T* pa, int n)
{BTNodeT* t, * right, * left;HuffmanNodeT hf;HeapHuffmanNodeT HF(n);//第一个循环将数组里的元素插入到哈夫曼堆for (int i 0; i n; i){t GetBTNodeint(pa[i]);hf.t t;HF.Insert(hf);}//第二个循环找到最小的两个数生成根节点后删除for (int i 1; i n; i){HF.DeleteMin(hf);left hf.t;HF.DeleteMin(hf);right hf.t;t GetBTNode(left-data right-data, left, right);//t的左孩子是left,右孩子是righthf.t t;HF.Insert(hf);}HF.DeleteMin(hf);//是一个对象调用函数t hf.t;return t;
};int main()
{int a[] { 7,5,2,4 };BTNodeint* root;root MakeHuffman(a, 4);PrintBTree(root, 40);cout endl;return 0;
}
