0315-5269188

工作时间

09:00 - 17:00

数字生态·驱动未来 企业数字化管理解决方案
当前位置:首页 > 技术文档

博弈树的建立以及节点删除出现的错误

描述

对于一间公司来说,它成立之时所做的第一件事恐怕就是任命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之间,且由大小写字母、数字和短线(减号)组成。每个名字都包含至少一个大写和一个小写字母。

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

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

输出

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

\

 

学长代码链接:1. 点击打开链接

                        2. 点击打开链接

这个题我花了很长时间,其实错误对我而言确实是不明显:

我的正确代码如下:


  1.  
    #include<stdio.h>
  2.  
    #include<stdlib.h>
  3.  
    #include<string.h>
  4.  
     
  5.  
    typedef struct node{
  6.  
    char name[20];
  7.  
    struct node * left;
  8.  
    struct node * right;
  9.  
    }NODE;
  10.  
     
  11.  
    NODE **Father=NULL;
  12.  
    NODE **Delete=NULL;
  13.  
    NODE *CEO=NULL;
  14.  
    void print(NODE *ptr,int dep)
  15.  
    {
  16.  
    if(ptr!=NULL)
  17.  
    {
  18.  
    for(int i=0;i<dep;i++)
  19.  
    printf("+");
  20.  
    printf("%s\n",ptr->name);
  21.  
    }
  22.  
    if(ptr->left!=NULL)
  23.  
    print(ptr->left,dep+1);
  24.  
    if(ptr->right!=NULL)
  25.  
    print(ptr->right,dep);
  26.  
    }
  27.  
     
  28.  
    void Build(NODE **ptr,char *s)
  29.  
    {
  30.  
    while((*ptr)!=NULL)
  31.  
    ptr=&((*ptr)->right);
  32.  
    (*ptr)=(NODE*)malloc(sizeof(NODE));
  33.  
    strcpy((*ptr)->name,s);
  34.  
    (*ptr)->right=NULL;
  35.  
    (*ptr)->left=NULL;
  36.  
    }
  37.  
    int Hire(NODE **ptr,char *p,char *q)
  38.  
    {
  39.  
    if(*ptr==NULL) return 0;
  40.  
    if(strcmp(p,(*ptr)->name)==0)
  41.  
    {
  42.  
    if((*ptr)->left==NULL)
  43.  
    {
  44.  
    (*ptr)->left=(NODE*)malloc(sizeof(NODE));
  45.  
    (*ptr)->left->left=NULL;
  46.  
    (*ptr)->left->right=NULL;
  47.  
    strcpy((*ptr)->left->name,q);
  48.  
    }
  49.  
    else
  50.  
    {
  51.  
    Build(&((*ptr)->left),q);
  52.  
    }
  53.  
    return 1;
  54.  
    }
  55.  
    else
  56.  
    {
  57.  
    if((*ptr)->left!=NULL)
  58.  
    Hire(&((*ptr)->left),p,q);
  59.  
     
  60.  
    if((*ptr)->right!=NULL)
  61.  
    Hire(&((*ptr)->right),p,q);
  62.  
    }
  63.  
    return 0;
  64.  
    }
  65.  
     
  66.  
    void Search(NODE **ptr, char *s)
  67.  
    {
  68.  
    if((*ptr)==NULL) return;
  69.  
    if((*ptr)->left!=NULL&&strcmp((*ptr)->left->name,s)==0)
  70.  
    {
  71.  
    Father=ptr;
  72.  
    Delete=&((*ptr)->left);
  73.  
    return;
  74.  
    }
  75.  
    if((*ptr)->right!=NULL&&strcmp((*ptr)->right->name,s)==0)
  76.  
    {
  77.  
    Father=ptr;
  78.  
    Delete=&((*ptr)->right);
  79.  
    return;
  80.  
    }
  81.  
    if((*ptr)->left!=NULL)
  82.  
    Search(&((*ptr)->left),s);
  83.  
    if((*ptr)->right!=NULL)
  84.  
    Search(&((*ptr)->right),s);
  85.  
    return;
  86.  
    }
  87.  
     
  88.  
    void Fire(char *s)
  89.  
    {
  90.  
     
  91.  
     
  92.  
    if(strcmp(s,CEO->name)==0 && CEO->left!=NULL)
  93.  
    {
  94.  
    char str[20];
  95.  
    strcpy(str,CEO->name);
  96.  
    strcpy(CEO->name,CEO->left->name);
  97.  
    strcpy(CEO->left->name,str);
  98.  
    }
  99.  
    else if(strcmp(s,CEO->name)==0 && CEO->right!=NULL)
  100.  
    {
  101.  
    char str[20];
  102.  
    strcpy(str,CEO->name);
  103.  
    strcpy(CEO->name,CEO->right->name);
  104.  
    strcpy(CEO->right->name,str);
  105.  
    }
  106.  
    else;
  107.  
    Father=NULL; Delete=NULL;
  108.  
    Search(&CEO,s);
  109.  
    if(Father==NULL)
  110.  
    {
  111.  
    return;
  112.  
    }
  113.  
    else
  114.  
    {
  115.  
    if((*Father)->left== *Delete)
  116.  
    {
  117.  
    if((*Delete)->left==NULL)
  118.  
    {
  119.  
    (*Father)->left=(*Delete)->right;
  120.  
    return;
  121.  
    }
  122.  
    else
  123.  
    {
  124.  
    char str[20];
  125.  
    strcpy(str,(*Delete)->name);
  126.  
    strcpy((*Delete)->name,(*Delete)->left->name);
  127.  
    strcpy((*Delete)->left->name,str);
  128.  
    Fire(s);
  129.  
    }
  130.  
    }
  131.  
    else if((*Father)->right== *Delete)
  132.  
    {
  133.  
    if((*Delete)->left==NULL)
  134.  
    {
  135.  
    (*Father)->right=(*Delete)->right;
  136.  
    return;
  137.  
    }
  138.  
     
  139.  
    else if((*Delete)->right==NULL)
  140.  
    {
  141.  
    (*Father)->right=(*Delete)->left;
  142.  
    return;
  143.  
    }
  144.  
    else
  145.  
    {
  146.  
    char str[20];
  147.  
    strcpy(str,(*Delete)->name);
  148.  
    strcpy((*Delete)->name,(*Delete)->left->name);
  149.  
    strcpy((*Delete)->left->name,str);
  150.  
    Fire(s);
  151.  
    }
  152.  
    }
  153.  
    else;
  154.  
    }
  155.  
     
  156.  
    }
  157.  
    int main()
  158.  
    {
  159.  
    CEO=(NODE*)malloc(sizeof(NODE));
  160.  
    CEO->left=NULL;
  161.  
    CEO->right=NULL;
  162.  
    int input;
  163.  
    char inputs[100],prase1[20],prase2[20],prase3[20];
  164.  
    scanf("%s",CEO->name);
  165.  
    while(gets(inputs)!=NULL)
  166.  
    {
  167.  
    input=sscanf(inputs,"%[^ ] %[^ ] %[^ ]",prase1,prase2,prase3);
  168.  
    if(input==1)
  169.  
    {
  170.  
    print(CEO,0);
  171.  
    printf("------------------------------------------------------------\n");
  172.  
    }
  173.  
    else if(input==2)
  174.  
    Fire(prase2);
  175.  
    else if(input==3)
  176.  
    Hire(&CEO,prase1,prase3);
  177.  
    }
  178.  
    return 0;
  179.  
    }

错误的地方是Fire函数,错误代码如下:


  1.  
    void Fire(char *s)
  2.  
    {
  3.  
    if(strcmp(s,CEO->name)==0 && CEO->left!=NULL)
  4.  
    {
  5.  
    char str[20];
  6.  
    strcpy(str,CEO->name);
  7.  
    strcpy(CEO->name,CEO->left->name);
  8.  
    strcpy(CEO->left->name,str);
  9.  
    }
  10.  
    else if(strcmp(s,CEO->name)==0 && CEO->right!=NULL)
  11.  
    {
  12.  
    char str[20];
  13.  
    strcpy(str,CEO->name);
  14.  
    strcpy(CEO->name,CEO->right->name);
  15.  
    strcpy(CEO->right->name,str);
  16.  
    }
  17.  
    else;
  18.  
    Father=NULL; Delete=NULL;
  19.  
    Search(&CEO,s);
  20.  
    if(Father==NULL)
  21.  
    {
  22.  
    return;
  23.  
    }
  24.  
    else
  25.  
    {
  26.  
    if((*Father)->left== *Delete) // *1*
  27.  
    {
  28.  
    if((*Delete)->left==NULL)
  29.  
    {
  30.  
    (*Father)->left=(*Delete)->right;
  31.  
    return;
  32.  
    }
  33.  
    else
  34.  
    {
  35.  
    char str[20];
  36.  
    strcpy(str,(*Delete)->name);
  37.  
    strcpy((*Delete)->name,(*Delete)->left->name);
  38.  
    strcpy((*Delete)->left->name,str);
  39.  
    Fire(s);
  40.  
    }
  41.  
    }
  42.  
    if((*Father)->right== *Delete) //错误的地方
  43.  
    {
  44.  
    if((*Delete)->left==NULL)
  45.  
    {
  46.  
    (*Father)->right=(*Delete)->right;
  47.  
    return;
  48.  
    }
  49.  
     
  50.  
    else if((*Delete)->right==NULL)
  51.  
    {
  52.  
    (*Father)->right=(*Delete)->left;
  53.  
    return;
  54.  
    }
  55.  
    else
  56.  
    {
  57.  
    char str[20];
  58.  
    strcpy(str,(*Delete)->name);
  59.  
    strcpy((*Delete)->name,(*Delete)->left->name);
  60.  
    strcpy((*Delete)->left->name,str);
  61.  
    Fire(s);
  62.  
    }
  63.  
    }
  64.  
    }
  65.  
    }
 

错误之处在于程序进入*1*处的  if语句块中,将节点已经删除,但是程序依旧进行 *2* 处条件判断,但此时Delete指针所指的区域已经被删除,所以程序会提示内存访问冲突。

这件事提示我如果已经删除了一个节点,就不能再对它进行判断或者操作,否则会有内存访问冲突的错误。

地址:唐山市新华西道大洋商厦4层

电话:0315-5269188

电话:18633118288

邮箱:52731887@qq.com

为您提供专业的 唐山网页设计 唐山网站建设 唐山网站制作 等优质的唐山网络布线服务

欢迎国内外/唐山网站建设,唐山网络布线,唐山网站制作,网站设计服务公司同行与我们建立友情链接

版权所有

  • 唐山赫鸣科技有限公司 冀ICP备11004205号-1