2. 公司里的那点事儿(10分)

港控/mmm° 2022-04-02 08:44 154阅读 0赞

### 描述 ###

对于一间公司来说，它成立之时所做的第一件事恐怕就是任命CEO了。之后，CEO就会开始雇用员工，也会有员工离职去别的公司。假设公司中的每一个员工（包括 CEO在内）都可以直接雇用新的员工，而公司中的所有员工（包括CEO）也都可能会跳槽离开，则某公司在成立一段时间之后的的组织结构如图1：

![图1][1]

图1

VonNeumann是公司的CEO，他直接雇用了两个人，分别是Tanenbaum和Dijkstra。在公司中，某员工的几个直接下属，他们的职位是由员工们的工龄决定的，在图中即表现为从从左至右职位越来越低，譬如Tanenbaum的职位就比Dijkstra要高。

当一个员工雇用了新的下属时，该下属在该员工雇佣的所有下属中，职位是最低的。假设VonNeumann又雇用了Shannon，则VonNeumann的三名下属职位从高到低分别是Tanenbaum、Dijkstra和Shannon。

当公司中的员工离职，则有两种情况。若他没有雇用任何下属，则他会被从公司的组织结构中拿掉。若他有直接的下属，则他的直接下属中职位较高的人，会升职并补上缺位。而该下属若也有下属，则他的下属中职位最高的，会补上他升值后空出的位子。以此类推，直到某个尚未雇用下属的员工升职。

假设图1中的Tanenbaum跳槽离开了，则Stallings会补上它的位置，而Knuth会补上Stallings的位置。图2展示了变化后的结果：(1) VonNeumann雇用了Shannon，(2) Tanenbaum跳槽。

![图2][2]

图2

### 输入 ###

输入的第一行是 CEO 的姓名。题目中所有的人名的长度都在2-20之间，且由大小写字母、数字和短线（减号）组成。每个名字都包含至少一个大写和一个小写字母。

在第一行后会有很多行内容，他们由如下的规则构成：

*  \[老员工\] hires \[新员工\]
 *  fire \[老员工\]
 *  print

\[老员工\] 是已经在公司工作的人的名字，而\[新员工\]是即将被雇用的员工的名字。以上三种规则组成的内容可能会按照任何顺序出现。但公司中会至少有一名员工（CEO），且公司的规模最大不会超过 1000 人。

### 输出 ###

对于每一个打印命令，按照如下规则输出当前公司的结构信息：

*  每一行包含一个人名
 *  第一行是CEO的名字，从第一列开始
 *  图3形式的结果，
    
    ![图3][3]
    
    图3
    
    会输出为图4
    
    ![图4][4]
    
    图4
 *  在每次print之后，输出一行60个字符的减号，整个输出中没有任何空行。

<table> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th>测试输入<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" rel="nofollow"><img alt="关于“测试输入”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>期待的输出<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" rel="nofollow"><img alt="关于“期待的输出”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>时间限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" rel="nofollow"><img alt="关于“时间限制”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>内存限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" rel="nofollow"><img alt="关于“内存限制”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>额外进程<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" rel="nofollow"><img alt="关于“{$a} 个额外进程”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>测试用例 1</td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77931&amp;test=100749&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>VonNeumann↵</li> 
     <li>VonNeumann&nbsp;hires&nbsp;Tanenbaum↵</li> 
     <li>VonNeumann&nbsp;hires&nbsp;Dijkstra↵</li> 
     <li>Tanenbaum&nbsp;hires&nbsp;Stallings↵</li> 
     <li>Tanenbaum&nbsp;hires&nbsp;Silberschatz↵</li> 
     <li>Stallings&nbsp;hires&nbsp;Knuth↵</li> 
     <li>Stallings&nbsp;hires&nbsp;Hamming↵</li> 
     <li>Stallings&nbsp;hires&nbsp;Huffman↵</li> 
     <li>print↵</li> 
     <li>VonNeumann&nbsp;hires&nbsp;Shannon↵</li> 
     <li>fire&nbsp;Tanenbaum↵</li> 
     <li>print↵</li> 
     <li>fire&nbsp;Silberschatz↵</li> 
     <li>fire&nbsp;VonNeumann↵</li> 
     <li>print↵</li> 
    </ol></td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77931&amp;test=100749&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>VonNeumann↵</li> 
     <li>+Tanenbaum↵</li> 
     <li>++Stallings↵</li> 
     <li>+++Knuth↵</li> 
     <li>+++Hamming↵</li> 
     <li>+++Huffman↵</li> 
     <li>++Silberschatz↵</li> 
     <li>+Dijkstra↵</li> 
     <li>------------------------------------------------------------↵</li> 
     <li>VonNeumann↵</li> 
     <li>+Stallings↵</li> 
     <li>++Knuth↵</li> 
     <li>+++Hamming↵</li> 
     <li>+++Huffman↵</li> 
     <li>++Silberschatz↵</li> 
     <li>+Dijkstra↵</li> 
     <li>+Shannon↵</li> 
     <li>------------------------------------------------------------↵</li> 
     <li>Stallings↵</li> 
     <li>+Knuth↵</li> 
     <li>++Hamming↵</li> 
     <li>+++Huffman↵</li> 
     <li>+Dijkstra↵</li> 
     <li>+Shannon↵</li> 
     <li>------------------------------------------------------------↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

#include "stdio.h"
    #include "stdlib.h"
    #include "string.h"
    
    typedef struct node{
        char name[20];
        int rank;
        struct node *fchild;
        struct node *nextsibling;
    }NODE;
    NODE *CEO;
    
    typedef struct node2{
        int rank;
        struct node *position;
    }NODE2;
    NODE2 judge[100];
    
    int cmp(const void *a, const void *b)
    {
        return  (*(NODE2 *)b).rank - (*(NODE2 *)a).rank;
    }
    
    char employer[20], employee[20];
    
    void UpdateRank(NODE *p){
        if(p != NULL){
            p->rank++;
            UpdateRank(p->fchild);
            UpdateRank(p->nextsibling);
        }
        return;
    }
    
    int Hire(NODE *p){
        if(p != NULL){
            if(!strcmp(p->name, employer)){
                if(p->fchild == NULL){
                    p->fchild = (NODE*)malloc(sizeof(NODE));
                    p->fchild->rank = 0;
                    memset(p->fchild->name, '\0', 20);
                    strcpy(p->fchild->name, employee);
                    p->fchild->fchild = NULL;
                    p->fchild->nextsibling = NULL;
                    return 1;
                }
                else{
                    p = p->fchild;
                    while(p->nextsibling != NULL){
                        p = p->nextsibling;
                    }
                    p->nextsibling = (NODE*)malloc(sizeof(NODE));;
                    p->nextsibling->rank = 0;
                    memset(p->nextsibling->name, '\0', 20);
                    strcpy(p->nextsibling->name, employee);
                    p->nextsibling->fchild = NULL;
                    p->nextsibling->nextsibling = NULL;
                    return 1;
                }
            }
            else{
                if(Hire(p->nextsibling)) return 1;
                if(Hire(p->fchild)) return 1;
                return 0;
            }
        }
        else return 0;
        
    }
    
    NODE *boss, *fired;
    
    int Search(NODE *root){
        NODE *p = root->fchild;
        while(p != NULL){
            if(!strcmp(p->name, employee)){
                boss = root;
                fired = p;
                return 1;
            }
            else{
                p = p->nextsibling;
            }
        }
        p = root->fchild;
        while(p != NULL){
            if(Search(p)) return 1;
            p = p->nextsibling;
        }
        return 0;
    }
    
    void Pop(NODE *blank){
        if(blank->fchild->fchild == NULL){
            memset(blank->name, '\0', 20);
            strcpy(blank->name, blank->fchild->name);
            blank->fchild = blank->fchild->nextsibling;
            return ;
        }
        memset(blank->name, '\0', 20);
        strcpy(blank->name, blank->fchild->name);
        Pop(blank->fchild);
    }
    
    void Fire(NODE *p){
        if(fired->fchild == NULL){
            if(boss->fchild == fired){
                boss->fchild = boss->fchild->nextsibling;
                return;
            }
            else{
                NODE *p = boss->fchild;
                while(p->nextsibling != fired){
                    p = p->nextsibling;
                }
                p->nextsibling = p->nextsibling->nextsibling;
            }
        }
        else{
            Pop(fired);
    
        }
        
    }
    
    int count = 0;
    
    
    
    void Print(NODE *ptr,int dep)
    {
    	if(ptr!=NULL)
    	{
    		for(int i=0;i<dep;i++)
    			printf("+");
    		printf("%s\n",ptr->name);
    	}
    	if(ptr->fchild!=NULL)
    		Print(ptr->fchild,dep+1);
    	if(ptr->nextsibling!=NULL)
    		Print(ptr->nextsibling,dep);	
    }
    
    NODE *root;
    
    int main(int argc, char const *argv[])
    {
        char name[20], operate[20], print[20], fire[20];
        memset(fire, '\0', 20);
        memset(print, '\0', 20);
        strcpy(fire, "fire");
        strcpy(print, "print");
        //建立CEO
        CEO = (NODE*)malloc(sizeof(NODE));
        scanf("%s",name);
        memset(CEO->name, '\0', 20);
        strcpy(CEO->name, name);
        CEO->rank = 0;
        CEO->fchild = NULL;
        CEO->nextsibling = NULL;
        root = (NODE*)malloc(sizeof(NODE));
        root->fchild = CEO;
        root->nextsibling = NULL;
    
        //建立公司
        memset(operate, '\0', 20);
        while(scanf("%s",operate) != EOF){
            //print操作
            if(!strcmp(operate, print)){
                Print(root->fchild, 0);
                printf("------------------------------------------------------------\n");
                //Judge();
            }
            //fire操作
            else if(!strcmp(operate, fire)){
                memset(employer, '\0', 20);
                memset(employee, '\0', 20);
                scanf("%s", employee);
                Search(root);
                Fire(boss);
                //Judge();
                
            }
            //hire操作
            else{
                UpdateRank(CEO);
                memset(employer, '\0', 20);
                memset(employee, '\0', 20);
                strcpy(employer, operate);
                scanf("%s", operate);
                scanf("%s", employee);
                Hire(CEO);
            }
        }
    
    
        return 0;
    }

[1]: http://online.bit.edu.cn/moodle/pluginfile.php/185593/mod_programming/intro/%E5%85%AC%E5%8F%B8%E9%82%A3%E7%82%B9%E4%BA%8B1.JPG
[2]: http://online.bit.edu.cn/moodle/pluginfile.php/185593/mod_programming/intro/%E5%85%AC%E5%8F%B8%E9%82%A3%E7%82%B9%E4%BA%8B2.JPG
[3]: http://online.bit.edu.cn/moodle/pluginfile.php/185593/mod_programming/intro/%E5%85%AC%E5%8F%B8%E9%82%A3%E7%82%B9%E4%BA%8B3.JPG
[4]: http://online.bit.edu.cn/moodle/pluginfile.php/185593/mod_programming/intro/%E5%85%AC%E5%8F%B8%E9%82%A3%E7%82%B9%E4%BA%8B4.JPG