描述
对于一间公司来说,它成立之时所做的第一件事恐怕就是任命CEO了。之后,CEO就会开始雇用员工,也会有员工离职去别的公司。假设公司中的每一个员工(包括 CEO在内)都可以直接雇用新的员工,而公司中的所有员工(包括CEO)也都可能会跳槽离开,则某公司在成立一段时间之后的的组织结构如图1
VonNeumann是公司的CEO,他直接雇用了两个人,分别是Tanenbaum和Dijkstra。在公司中,某员工的几个直接下属,他们的职位是由员工们的工龄决定的,在图中即表现为从从左至右职位越来越低,譬如Tanenbaum的职位就比Dijkstra要高。
当一个员工雇用了新的下属时,该下属在该员工雇佣的所有下属中,职位是最低的。假设VonNeumann又雇用了Shannon,则VonNeumann的三名下属职位从高到低分别是Tanenbaum、Dijkstra和Shannon。
当公司中的员工离职,则有两种情况。若他没有雇用任何下属,则他会被从公司的组织结构中拿掉。若他有直接的下属,则他的直接下属中职位较高的人,会升职并补上缺位。而该下属若也有下属,则他的下属中职位最高的,会补上他升值后空出的位子。以此类推,直到某个尚未雇用下属的员工升职。
假设图1中的Tanenbaum跳槽离开了,则Stallings会补上它的位置,而Knuth会补上Stallings的位置。图2图3分别展示了基于图1的两种的操作的结果。图2: VonNeumann雇用了Shannon。图3: Tanenbaum跳槽。
输入
输入的第一行是 CEO 的姓名。题目中所有的人名的长度都在2-20之间,且由大小写字母、数字和短线(减号)组成。每个名字都包含至少一个大写和一个小写字母。
在第一行后会有很多行内容,他们由如下的规则构成:
- [老员工] hires [新员工]
- fire [老员工]
- print
[老员工] 是已经在公司工作的人的名字,而[新员工]是即将被雇用的员工的名字。以上三种规则组成的内容可能会按照任何顺序出现。但公司中会至少有一名员工(CEO),且公司的规模最大不会超过 1000 人。
输出
对于每一个打印命令,按照如下规则输出当前公司的结构信息:
- 每一行包含一个人名
- 第一行是CEO的名字,从第一列开始
- 对于图4形式的树
学长代码链接:1. 点击打开链接
2. 点击打开链接
这个题我花了很长时间,其实错误对我而言确实是不明显:
我的正确代码如下:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
void print(NODE *ptr,int dep)
-
-
-
-
-
-
printf("%s\n",ptr->name);
-
-
-
-
-
-
-
-
void Build(NODE **ptr,char *s)
-
-
-
-
(*ptr)=(NODE*)malloc(sizeof(NODE));
-
-
-
-
-
int Hire(NODE **ptr,char *p,char *q)
-
-
-
if(strcmp(p,(*ptr)->name)==0)
-
-
-
-
(*ptr)->left=(NODE*)malloc(sizeof(NODE));
-
-
(*ptr)->left->right=NULL;
-
strcpy((*ptr)->left->name,q);
-
-
-
-
Build(&((*ptr)->left),q);
-
-
-
-
-
-
-
Hire(&((*ptr)->left),p,q);
-
-
-
Hire(&((*ptr)->right),p,q);
-
-
-
-
-
void Search(NODE **ptr, char *s)
-
-
-
if((*ptr)->left!=NULL&&strcmp((*ptr)->left->name,s)==0)
-
-
-
-
-
-
if((*ptr)->right!=NULL&&strcmp((*ptr)->right->name,s)==0)
-
-
-
-
-
-
-
Search(&((*ptr)->left),s);
-
-
Search(&((*ptr)->right),s);
-
-
-
-
-
-
-
-
if(strcmp(s,CEO->name)==0 && CEO->left!=NULL)
-
-
-
-
strcpy(CEO->name,CEO->left->name);
-
strcpy(CEO->left->name,str);
-
-
else if(strcmp(s,CEO->name)==0 && CEO->right!=NULL)
-
-
-
-
strcpy(CEO->name,CEO->right->name);
-
strcpy(CEO->right->name,str);
-
-
-
Father=NULL; Delete=NULL;
-
-
-
-
-
-
-
-
if((*Father)->left== *Delete)
-
-
if((*Delete)->left==NULL)
-
-
(*Father)->left=(*Delete)->right;
-
-
-
-
-
-
strcpy(str,(*Delete)->name);
-
strcpy((*Delete)->name,(*Delete)->left->name);
-
strcpy((*Delete)->left->name,str);
-
-
-
-
else if((*Father)->right== *Delete)
-
-
if((*Delete)->left==NULL)
-
-
(*Father)->right=(*Delete)->right;
-
-
-
-
else if((*Delete)->right==NULL)
-
-
(*Father)->right=(*Delete)->left;
-
-
-
-
-
-
strcpy(str,(*Delete)->name);
-
strcpy((*Delete)->name,(*Delete)->left->name);
-
strcpy((*Delete)->left->name,str);
-
-
-
-
-
-
-
-
-
-
CEO=(NODE*)malloc(sizeof(NODE));
-
-
-
-
char inputs[100],prase1[20],prase2[20],prase3[20];
-
-
while(gets(inputs)!=NULL)
-
-
input=sscanf(inputs,"%[^ ] %[^ ] %[^ ]",prase1,prase2,prase3);
-
-
-
-
printf("------------------------------------------------------------\n");
-
-
-
-
-
Hire(&CEO,prase1,prase3);
-
-
-
错误的地方是Fire函数,错误代码如下:
-
-
-
if(strcmp(s,CEO->name)==0 && CEO->left!=NULL)
-
-
-
-
strcpy(CEO->name,CEO->left->name);
-
strcpy(CEO->left->name,str);
-
-
else if(strcmp(s,CEO->name)==0 && CEO->right!=NULL)
-
-
-
-
strcpy(CEO->name,CEO->right->name);
-
strcpy(CEO->right->name,str);
-
-
-
Father=NULL; Delete=NULL;
-
-
-
-
-
-
-
-
if((*Father)->left== *Delete)
-
-
if((*Delete)->left==NULL)
-
-
(*Father)->left=(*Delete)->right;
-
-
-
-
-
-
strcpy(str,(*Delete)->name);
-
strcpy((*Delete)->name,(*Delete)->left->name);
-
strcpy((*Delete)->left->name,str);
-
-
-
-
if((*Father)->right== *Delete)
-
-
if((*Delete)->left==NULL)
-
-
(*Father)->right=(*Delete)->right;
-
-
-
-
else if((*Delete)->right==NULL)
-
-
(*Father)->right=(*Delete)->left;
-
-
-
-
-
-
strcpy(str,(*Delete)->name);
-
strcpy((*Delete)->name,(*Delete)->left->name);
-
strcpy((*Delete)->left->name,str);
-
-
-
-
-
错误之处在于程序进入*1*处的 if语句块中,将节点已经删除,但是程序依旧进行 *2* 处条件判断,但此时Delete指针所指的区域已经被删除,所以程序会提示内存访问冲突。
这件事提示我如果已经删除了一个节点,就不能再对它进行判断或者操作,否则会有内存访问冲突的错误。