POJ 2003 Hire and Fire (Tree)-白红宇

POJ 2003 Hire and Fire (Tree)

阅读量：5076 次

发布时间：2019-06-12

本文共 1783 字，大约阅读时间需要 5 分钟。

　　题目：Hire and Fire

　　题目翻译成数据结构就是：建树，加结点，删除结点，打印结点。只有删除结点稍微复杂点，因为删除设计掉树的调整。

　　首先要考虑树怎么存储才能使解题更顺手。

　　1.我们要存储每个结点的孩子，父亲和名字。存储孩子是因为第一个孩子可能会“升级”，存储父亲是因为要打印，名字肯定也是要打印的；

　　2.我们要知道每个结点的子树，删除结点会涉及调整；

　　3.我们要知道根节点，存放CEO。

　　所以我们的结点出来了，如下：

struct Tman {      string name;      Tman *father;      list
     
       sons; };

　思路都在注释里。

　　代码如下：

#include
     
      #include
      #include
       
        #include
        
         using namespace std;//存储名字，父亲，孩子就行struct Tman{    string name;    Tman *father;    list
         
           sons;};//key是结点名字，value是名字的子树map
          
            hash;//根结点，指向CEO，打印是要用Tman *root;void print(long dep, Tman *now){ if(now == NULL) return; for(long i = 1; i <= dep; ++i) cout<<"+"; cout<
           
            name<
            
             ::iterator j = now->sons.begin(); j != now->sons.end(); ++j) print(dep + 1, *j);}void hires(string n1, string n2) { Tman *boss = hash[n1];//父亲的子树指针 Tman *employee = new Tman();//新建一个Tman结构体，用于存储新加入的结点 employee->name = n2;//新加入结点的名字 employee->father = boss;//n1是n2的父亲 boss->sons.push_back(employee);//把n2放入n1的孩子list中 hash[n2] = employee;//新加入的结点也要有子树}void fire(string n1){ Tman *p = hash[n1];//指向n1结点的指针 hash.erase(n1); while(p->sons.size() > 0)//如果要删的结点有孩子 { p->name = p->sons.front()->name;//第一个孩子取代父亲的地位 hash[p->name] = p;//父亲的子树交给第一个孩子 p = p->sons.front();//p往下移动，始终指向孩子队列的第一个 } p->father->sons.remove(p);//最后一个没有孩子的结点“删除”，实际上是上移了 delete p;//防止野指针}void solve(){ string str1,str2; long i; cin>>str1; root = new Tman(); hash[str1] = root; root->name = str1; while(cin>>str1) { if(str1 == "print") { print(0,root); cout<<"------------------------------------------------------------"<
             
              >str2; fire(str2); } else { cin>>str2; cin>>str2; hires(str1, str2); } }}int main(){ solve(); return 0;}

转载于:https://www.cnblogs.com/HpuAcmer/p/4170441.html

你可能感兴趣的文章

创建本地yum软件源，为本地Package安装Cloudera Manager、Cloudera Hadoop及Impala做准备...