题目:1635 Directory Listing(列出目录)

    技术2022-05-13  34

    题目:1635 Directory Listing(列出目录)

           http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=635

            看描述好像是chenyue姐姐出的题目。这道题的大意是,给出一个UNIX文件系统的树,以及树节点的自身size,按要求列出它们,保持适当的缩进,并统计每个节点的总的size。输入的第一行代表根结点,每一个节点由name size或者*name size的形式组成(如果包含*表示这是一个文件夹,它包含的子节点将在下一行中列出,并用圆括号包含,size是一个表示节点自身属性的正整数)。在输出节点时,需要输出该节点自身size和所有子节点size的和。

           深度为d的节点前面应该有8d的前导(由空格或竖线组成);

     

    示范输入:

    */usr 1(*mark 1 *alex 1)(hw.c 3 *course 1) (hw.c 5)(aa.txt 12)

     

    示范输出:

    |_*/usr[24]        |_*mark[17]        |       |_hw.c[3]        |       |_*course[13]        |               |_aa.txt[12]        |_*alex[6]                |_hw.c[5]

            ---------------------------------------------------------------------------------------       题目属于按固定格式输出的题目,但本质上是属于对这种数据结构的考察。不难看出,在读取输入时,输入方式实际上是一种类似树的按层次遍历,即按照节点深度从小到大的顺序给出每一层次的节点,第k行即代表了该深度(depth=k)的所有节点。同时,如果节点不包含*,表示是叶子节点,如果包含*,则属于文件夹,因此一定会有下一行。如果某一行不包含任何*,则一棵树输入完毕。

           而对于输出,容易看出,输出实际上是对树的前序遍历。

           在我的此前的一篇博客中,已经详细讲解过如何通过栈来前序遍历树,以及如何通过队列来层次遍历树,因此这里不再详细介绍了。输出的时候完全是前序遍历,无须多做解释。唯一有点特别的是读取输入的过程就是组装这颗树的过程,组装过程中我们先把根结点(一定包含*)入列,然后依次读取下一行,下一行中假设包含n组子节点(即含有n组圆括号),则针对每一组子节点,从队列中出列一个节点作为这些子节点的父节点即可。直到队列为空,一棵树的读取和组装完毕。

           这里我们还要注意的第一个细节问题是,在组装过程中,我们还要把该节点的最终size统计出来。因此我们给每个树节点增加了一个父节点指针,这样每挂接一个子节点,从该节点向根结点追溯,对所有父辈节点累加该size。此外我们还需要一个属性记录该节点的所在深度,这个属性在后面的输出时被利用。因此,我们把节点定义如下:

     

    typedef struct tnode{      char text[11];/*节点名称*/      int depth; /*该节点所在层次*/      int size; /*该节点的当前值,最终值=自身值+所有子节点值*/      struct tnode *child[10]; /*根结点*/      struct tnode *parent; /*父节点,用于向根结点累加size*/} TNODE;

     

           下面我们即可给出读取并组装树的代码。值得注意的是,我们每次读取一行,而该行中包含的子节点组的个数n是未知的,因此我们需要对读取进来的这一行通过ParseLine函数进行解析,即根据'('')'字符,把圆括号内部的文本提取出来,再传递给AddChildNodes函数进行处理。

    Code_InputTreeTNODE *queue[100];/*队列,用于输入*/TNODE *stack[100];/*栈,用于输出*/int head, tail;        /*队列的全局指针*/int top;                    /*栈的全局指针*/TNODE* InputTree();void ParseLine(char*, int);void AddChildNodes(char*, int);void OutputTree(TNODE *head);/*读入并组装为一棵树,返回根结点指针*/TNODE* InputTree(){    int size, depth=0;/*队列的指针*/    char buf[11], line[1024];    TNODE *node=NULL, *root=NULL;    /*是否读到了文件尾部,如果读到空字符串也返回null*/    if(scanf("%s %d", buf, &size)==EOF || size<0)        return NULL;        head=tail=0;    /*申请首个节点空间,赋值,入列*/    root=(TNODE*)malloc(sizeof(TNODE));    memset(root, 0sizeof(TNODE));    root->size=size;    strcpy(root->text, buf);        queue[tail++]=root; /*首个节点入队列*/        /*循环读入后续的每一行*/    while(head!=tail)    {        gets(line);        ParseLine(line, depth++); /*解析这一行!实际就是装配树的过程!*/        /*如果这一行中没有星号,说明树已经输入完毕!*/    }    return root;    }/*解析当前输入的一行,depth为节点所在深度*/void ParseLine(char *line, int depth){    char *begin, *s;    int flag=0;    begin=s=line;    while(*s)    {        switch(*s)        {            case '(':                begin=s+1;                break;            case ')':                *s='/0';                AddChildNodes(begin, depth);                break;        }        s++;    }    }/*添加子节点, depth为节点所在深度*/void AddChildNodes(char *str, int depth){    TNODE *parent, *node, *temp;    char *token;    int i=0;/*子节点索引*/    token=strtok(str, " ");    /*出列一个节点!*/    parent=queue[head++];    while(token!=NULL)    {        node=(TNODE*)malloc(sizeof(TNODE));        memset(node, 0 ,sizeof(TNODE));        node->depth=depth;        strcpy(node->text, token);        /*看该节点是否应该入列,如果是文件夹,则入列!*/        if(token[0]=='*')            queue[tail++]=node;                /*读入size*/        token=strtok(NULL, " ");        node->size=atoi(token);                /*添加该子节点!*/        parent->child[i++]=node;        node->parent=parent;                /*累加父节点的size*/        temp=parent;        while(temp!=NULL)        {            temp->size+=node->size;            temp=temp->parent;        }        token=strtok(NULL, " ");    }}

     

           注意在上面的代码中,我们在AddChildNodes函数的最后面对节点的size进行向根结点方向的追踪累加,这样树组装完毕后,每个节点的size就是最终要输出的值。

           当树读取进来并且组装以后,我们只需要对这个树进行前序遍历,依次打印节点即可,这部分的内容比较简单。但显然在输出中存在很关键的打印技巧,即如何准确打印出树的形状,每一个节点前面的前导字符串是关键!每一行由下面的格式组成:

           [前缀字符串] |_ [节点名称] [size]

           这里唯一有难度和技巧性的是前缀字符串的确定,每一深度的缩进由8个空格组成,但有时第一个空格实际上是竖线。那么竖线是否出现的规律是什么呢?仔细观察我们可以发现,当该节点的父节点是祖父节点的最后一个子节点(即老幺)时,父节点下方将不包含竖线。否则这8个空格中的第一个被替换为'|'。这样我们就不难写出下面的代码,提供一个缓冲区,然后我们把它设置为正确的前缀字符串:

     

    Code_设置前缀字符串/*很关键的一个函数,设置某个节点的前导部分*/void SetPrefix(TNODE *node, char *buffer){    int i, depth=node->depth;    TNODE *temp, *parent=NULL;    if(node->depth>0)        memset(buffer, ' ', node->depth * 8);    buffer[node->depth * 8]='/0'/*结尾*/    /*从下向上去判断!注意depth=0时无需要判断,因为根结点是独子,注定是老幺”*/        temp=node->parent;    while(temp!=NULL && (temp->depth > 0))    {        parent=temp->parent;        /*从父节点的子节点集合中最后向前找,如果不是最后一个节点,则把空格改为竖线*/        for(i=9;i>=0;i--)        {            /*如果temp不是父节点的最后一个子节点(老幺)*/            if(parent->child[i]!=NULL && parent->child[i]!=temp)            {                buffer[temp->depth*8]='|';                break;            }            if(parent->child[i]==temp) /*是最后一个节点*/                break;        }        temp=parent;    }}

     

             最后我们就可以用常规的栈前序遍历输出结果:

     

    Code_用栈辅助来前序遍历输出/*借助栈的辅助,前序输出,并输出后释放相应节点!*/void OutputTree(TNODE *head){    TNODE *node;    char prefix[80];/*该节点的前导字符串*/    int i;        if(head==NULL)        return;    top=0/*栈顶指针*/        /*根结点入栈*/    stack[top++]=head;        /*当栈不为空时*/    while(top>0)    {        node=stack[--top]; /*pop a node*/        /*在这里我们设置节点的前导!非常关键的一个地方!!!*/        SetPrefix(node, prefix);                        /*打印该节点*/        printf("%s|_%s[%d]/n", prefix, node->text, node->size);                /*node的子节点从右到左入栈!*/        for(i=9;i>=0;i--)        {            if(node->child[i]!=NULL)                stack[top++]=node->child[i];        }            }}

     

             同时我们在输出完一棵树以后,在读取下一颗树之前,应当把当前的树说申请的内存还给系统。由于刚刚使用栈输出过这棵树,因此这棵树的所有节点实际上都位于辅助栈内。因此我们只需要把栈里所有节点释放即可:

    Code_释放树占用的内存/*此时应该是刚刚输出完毕树,只要清空堆栈里的所有节点即可*/void DeleteTree(){    int i=0;    for(i=0;i<100;i++)    {        if(stack[i]==NULL)            break;        free(stack[i]);        stack[i]=NULL;    }    }/*入口点*/int main(){    TNODE *tree;    while((tree=InputTree())!=NULL)    {        OutputTree(tree);        DeleteTree();/*释放栈中的所有节点!*/    }    return 0;}

             最后,我们再关注一下需要注意的事项:

             1)我们在输出所有节点以后,才统一的一次性释放所有节点。而不是每输出一个节点就当即释放一个节点。这样做的原因是我们需要用节点关系去推导前缀字符串,因此我们没有立即就释放已经遍历过的节点。 

           2)我们使用malloc申请了一个节点以后,请注意这样的内存是原始的,也就是未经过任何初始化的,因此如果里面包含指针(例如节点的父节点指针,所有子节点指针),则这些指针全部属于野指针状态。如果不对这些指针进行初始化,将会导致灾难性后果。所以每次申请到一个节点后我们必须要做的第一步是初始化它:即memset( node, 0, sizeof(TNODE)); 这一条语句将保证节点中所有指针被设置为NULL,切不可忘记!!!

            3)实际上由于输入和输出是完全顺序的操作,因此这里的辅助栈和辅助队列可以合并为一个,它是queue还是stack完全取决于我们如何使用它。但为了清晰起见,我们的代码还是保留为独立的queuestack空间。

            4)此题看似容易,但实际上包含了相当的技巧性,并不是很容易在短时间内写好,从它较低的AC率(24%)来看说明它也不是一道简单的送分题。我仔细调试和检查了代码,直到全部正确才提交,然后一次性AC了,运行时间和内存占用都和解排行榜上的数据一致。

     

     

     

     


    最新回复(0)