minheap vs minleftisttree.rar

  • ac0665
    了解作者
  • Visual C++
    开发工具
  • 2KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 16
    下载次数
  • 2005-09-14 09:21
    上传日期
这是一个用C++编写的代码,实现了最小堆和最小左偏树在插入删除元素性能方面进行比较.
minheap vs minleftisttree.rar
  • www.pudn.com.txt
    218B
  • 实验2.cpp
    4.4KB
内容介绍
#include<iostream.h> #include<stdlib.h> #include<time.h> int m=100000;//number of sequence const long r[7]={100,500,1000,2000,3000,4000,5000}; enum Boolean{FALSE,TRUE}; class MinHeap { public: Boolean HeapIsFull(); Boolean HeapIsEmpty(); void HeapInsert(const int &x); int*HeapDelete(int &x); MinHeap(int sz=32000) { int MaxSize=32000; cs=0; heap=new int[MaxSize+1];//heap[0] is not used } private: int*heap; int cs;//current size of heap int Maxsize; }; Boolean MinHeap::HeapIsFull() { if(cs==32000) return TRUE; else return FALSE; } Boolean MinHeap::HeapIsEmpty() { if(cs==0) return TRUE; else return FALSE; } void MinHeap::HeapInsert(const int &x) { if(cs==32000) {HeapIsFull();return;} cs++; for(int i=cs;1;) { if(i==1) break;//at root if(x>=heap[i/2]) break;//unneed to adjust heap[i]=heap[i/2]; i/=2; } heap[i]=x; } int* MinHeap::HeapDelete(int &x) { if(!cs) {HeapIsEmpty();return 0;} x=heap[1]; int k=heap[cs]; cs--; for(int i=1,j=2;j<=cs;) { if(j<cs) if(heap[j]>heap[j+1]) j++; //j points to the smaller child if(k<=heap[j]) break; heap[i]=heap[j];//move child up i=j; j*=2;//move i and j down } heap[i]=k; return &x; } class LeftistNode { friend class MinLeftistTree; public: LeftistNode(int d=0,LeftistNode*l=0,LeftistNode*r=0) { data=d; LeftChild=l; RightChild=r; } private: int data; LeftistNode*LeftChild; LeftistNode*RightChild; int shortest;//最短路径的值 }; class MinLeftistTree { public: MinLeftistTree(LeftistNode*root=0){}; Boolean TreeIsEmpty(); int*TreeDeleteMin(int &); void TreeMinCombine(LeftistNode*); LeftistNode *TreeMinUnion(LeftistNode*,LeftistNode*); LeftistNode *root; }; Boolean MinLeftistTree::TreeIsEmpty() { if(!root) return TRUE; else return FALSE; } void MinLeftistTree::TreeMinCombine(LeftistNode*b) { if(!root) root=b; else if(b) root=TreeMinUnion(root,b); } LeftistNode* MinLeftistTree::TreeMinUnion(LeftistNode*a,LeftistNode*b) //combine two nonempty min leftist trees { //set a to be min leftist tree with smaller root if((a->data)>(b->data)) {LeftistNode*t=a;a=b;b=t;} //creat binary tree such that the smallest key in each subtree is in the root if(!a->RightChild) a->RightChild=b; else a->RightChild=TreeMinUnion(a->RightChild,b); //leftist tree property if(!a->LeftChild) { //interchange subtrees a->LeftChild=a->RightChild; a->RightChild=0; } else if((a->LeftChild->shortest)<(a->RightChild->shortest)) { //interchange subtrees LeftistNode*t=a->LeftChild; a->LeftChild=a->RightChild; a->RightChild=t; } //set shortest data number if(!a->RightChild) a->shortest=1; else a->shortest=a->RightChild->shortest+1; return a; } int* MinLeftistTree::TreeDeleteMin(int &x) { if(!root) return 0; x=root->data; if(!root->RightChild) root=root->LeftChild; else root=TreeMinUnion(root->LeftChild,root->RightChild); return &x; } void tryheap() { srand((unsigned)time(NULL)); clock_t hstart,hend; int min; for(int n=0;n<7;n++) { MinHeap h; for (int i=1;i<r[n]+1;i++) h.HeapInsert(rand()%5000); hstart=clock(); for(int j=0;j<m;j++) { if((rand()%2)==0) { if(h.HeapIsEmpty()); else h.HeapDelete(min); } else { if(h.HeapIsFull()); else { int temp=rand()%5000; h.HeapInsert(temp); } } } hend=clock(); cout<<"n="<<r[n]<<" "<<"average time (min heap) is:"<<" " <<(hend-hstart)/(double)m<<endl; } cout<<endl; } void trytree() { srand((unsigned)time(NULL)); long start,end; for(int p=0;p<7;p++) { int min; MinLeftistTree z; LeftistNode tt(rand()%5000); z.root=&tt; for(int t=1;t<r[p];t++) { int min=rand()%5000; LeftistNode*element=new LeftistNode(min);//初始化liftisttree; z.TreeMinCombine(element); } start=clock(); for(int j=0;j<m;j++) { if((rand()%2)==0)//0代表删除元素 { if(z.TreeIsEmpty()) ; else z.TreeDeleteMin(min); } else //1代表插入元素 { int pmet=rand()%5000; LeftistNode*temp=new LeftistNode(pmet); z.TreeMinCombine(temp); } } end=clock(); cout<<"n="<<r[p]<<" "<<"average time (leftist tree) is:"<<" " <<(end-start)/(double)m<<endl; } } void main() { tryheap(); trytree(); }
评论
    相关推荐
    • 数据库课程设计
      一个数据库课程设计,access管理工具实现,用的是窗体!
    • 数据库课程设计
      数据库课程设计十分完整有需要的请下载啊谢谢
    • 数据库课程设计
      广东工业大学数据库课程设计,可视化界面连接数据库,delphi7
    • 数据库课程设计
      数据库课程设计实验及其描述 数据库课程设计实验及其描述 数据库课程设计实验及其描述 数据库课程设计实验及其描述 数据库课程设计实验及其描述 数据库课程设计实验及其描述
    • 数据库课程设计
      数据库课程设计》由周爱武、汪海威、肖云编著,遵循数据库课程设计的具体要求,独立于具体的数据库教材,从实际应用系统的需求着手,引导读者逐步完成数据库设计全过程,重点讲解数据库系统的需求分析、概念设计、...
    • 数据库课程设计
      数据库课程设计人事管理系统 数据库课程设计人事管理系统数据库课程设计人事管理系统数据库课程设计人事管理系统数据库课程设计人事管理系统数据库课程设计人事管理系统数据库课程设计人事管理系统数据库课程设计...
    • 数据库课程设计
      数据库课程设计,基于visual basic自助银行管理系统,界面很清爽,实用。同学都说好,所以就上传了!!!
    • 数据库课程设计
      数据库课程设计 里面有详细的文档资料 包含数据库一切的图 以及生成的数据库表文件 期末得分为优秀
    • 数据库课程设计
      可以作为数据库课程设计,也可以作为Java的课程设计,内容全面。本资源转载的,非本人原创。用于交流学习,特此申明!
    • 数据库课程设计
      数据库课程设计蓝天大学学生管理系统 2.商店信息管理系统 3.实验室机房收费管理系统 4.图书馆资料检索系统 5.企业库存管理系统 6.仓库管理系统 7.工程项目管理系统 8.教材管理系统 9.企业人事管理系统 10.企业财务...