山东大学数据结构实验报告六

发布时间 : 2024/5/20 4:11:35 星期一 文章山东大学数据结构实验报告六更新完毕开始阅读

else{ root = new BinaryTreeNode(x); last=p_last=root; state++;} return *this; } void MaxHeap::Adjust(BinaryTreeNode *u) { if (!u->LeftChild && !u->RightChild) return; else if(u->LeftChild && u->RightChild){ if (u->LeftChild->data > u->RightChild->data) { if (u->data < u->LeftChild->data) { swap(u->data, u->LeftChild->data); Adjust(u->LeftChild); } } else { if (u->data < u->RightChild->data) { swap(u->data, u->RightChild->data); Adjust(u->RightChild); } } }} MaxHeap& MaxHeap::DeleteMax(int& x) { if (!root) exit(1) ; else if(!last) {x=root->data; state=0;root=0;} else{ x = root->data; root->data = last->data; int k = (int)(log((double)(state))/log((double)(2)))+ 1; int index = state - (int)(pow(2.0, k - 1) - 1); Adjust(root); if(index%2) p_last->LeftChild=0; else p_last->RightChild=0; delete last; state--; k = (int)(log((double)(state-1))/log((double)(2)))+ 1; index = state - 1 - (int)(pow(2.0, k - 1) - 1); int p_index = index / 2 + 1; if (index == (int) (pow(2.0, k - 1))){ p_index=1; p_last=LocateLast(root,k,p_index); } else p_last=LocateLast(root,k-1,p_index); if(!p_last->RightChild) last=p_last->LeftChild; else last=p_last->RightChild;} return *this; } MaxHeap& MaxHeap::Initialize(int a[], int n) { MaxHeap LMaxHeap,RMaxHeap; MakeHeap(a[0],LMaxHeap,RMaxHeap); for(int i=1;i=0;i--) { maxHeap.DeleteMax(x); // cout<<\// Travel(root);cout<HT[j].weight) { s1=j;//s1为权重小的 s2=i; } else { s1=i; s2=j; } i=j+1; while(i<=n) { if(HT[i].parent!=0) i++; else if(HT[i].weightweight=w[i-1]; p->lchild=0; p->rchild=0; p->parent=0; } int s1,s2; for(;i<=m;++i) { Select(HT,i-1,s1,s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].parent=0; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } HC=new char* [n]; cd=new char[n]; cd[n-1]='\\0';