Find-depth_success.rar_Success_算法设计与分析

//Program Find_depth_liangfeng #include<iostream.h> int i,j; class tree //tree是一个类，用来记录各节点的属性值 { public: int p; //对应的父节点 int count; //对应的子树中节点的个数 int weight; //节点对应的weight值 int w; //对应原父节点的新weight值 } t[10]; //建立10个tree类型的节点，本程序只用到其中的1-9节点 void find1() //由于本程序中的find(i)不进行weight值得计算，而只是返回它的w值，该子程序用来补充计算weight值 { for (i=1;i<=9;i++) { t[i].weight+=t[i].w;t[i].w=0;} } //*************************************** int find(int i) //查找节点i对应的根节，修改t[i].w的值 { if (i==t[i].p) t[i].w=0; else if(t[i].p!=i) {if (t[i].p==t[t[i].p].p) t[i].w=0; else { t[i].w=t[t[i].p].w+t[t[i].p].weight; t[i].p=find(t[i].p); } } return t[i].p; } //**************************************** int find_depth(int v,int v1)//用来求某个节点的深度，形参V1用来记录没有进行Link前v的根节点 { int root,depth; //此处没有按照书上所介绍的直接求节点v的深度，而是间接的利用 root=find(v1); //v的深度=根节点v1的深度+v到v1路经的权和 find1(); depth=t[v1].weight+t[v1].w; while(v1!=v) {depth=depth+t[v].weight;v=t[v].p;}//v的深度=根节点v1的深度+v到v1路经的权和 return depth; } //**************************************** void link(int v,int r) //用来连接两个节点 { int v1=find(v); int r1=find(r); if (v1==r1) {cout<<"两个节点已经在同一棵树下";return;} if (t[r1].count<=t[v1].count) //若r1的子节点数小于v1的子节点数，执行 { t[r1].p=v1; t[r1].weight=find_depth(v,v1)+1-t[v1].weight+t[r1].weight; t[v1].count+=t[r1].count; find(v); find1(); } else if(t[r1].count>t[v1].count) //若r1的子节点数大于v1的子节点数，执行 { t[v1].p=r1; t[r1].weight=find_depth(v,v1)+1+t[r1].weight; t[v1].weight=t[v1].weight-t[r1].weight; t[r1].count+=t[v1].count; find(v); find1(); } } //**************************************** void main() { bool a; int c,v1; a=0; for (i=0;i<=9;i++) //初始化 {t[i].p=i; t[i].weight=0; t[i].count=1; } while (a!=1) { cout<<"请选择执行动作 1: 执行 Link(i,j); "; cout<<"2: 执行find_depth(i)"<<endl; cin>>c; if(c==1) //用来标示选择要进行的动作 选择1执行Link(i,j); { cout<<"请输入要执行link的两个节点i,j"<<endl; cin>>i>>j; link(i,j); } else if(c==2) // 选择2执行 find_depth(i) { cout<<"请输入要执行find_depth节点"<<endl; cin>>i; v1=find(i); find_depth(i,v1); } cout<<"ID "<<" p "<<"weight"<<" count"<<endl; for (i=1;i<=9;i++) //输出节点的属性值 { cout<<i<<" "; cout<<t[i].p<<" "; cout<<t[i].weight<<" "; cout<<t[i].count<<" "<<endl; } } }