一、要解決的問題
給出某一個操作系統(tǒng)下目錄和文件信息，輸入的數(shù)據(jù)第一行為根目錄節(jié)點。若是目錄節(jié)點，那么它的孩子節(jié)點將在第二行中被列出，同時用一對圓括號“（）”界定。同樣，如果這些孩子節(jié)點中某一個也是目錄的話，那么這個目錄所包含的內(nèi)容將在隨后的一行中列出，由一對圓括號“（）”界定。目錄的輸入輸入格式為：*name size，文件的輸入輸入格式為：name size。Name為一串不超過10個字符組成，并且字符串中不能有‘（’，‘）’，‘[‘,’]’和’*’。Size是該文件/目錄的大小，文件的size輸入值為該文件的大小，目錄的size輸入值都為1。樹結(jié)構(gòu)最多10層，每一層最多2個文件/目錄。
要求編程實現(xiàn)將其排列成一棵有一定縮進(jìn)的樹，輸出要求：第d層的文件/目錄名前面需要縮進(jìn)8*d個空格，兄弟節(jié)點要在同一列上。并計算每一個目錄大小，目錄大小為所包含的所有子目錄和文件大小以及自身大小的總和。
例如輸入：
*/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[3]
二、算法基本思想描述：
采用孩子兄弟雙親鏈表的數(shù)據(jù)存儲結(jié)構(gòu)建立二叉樹，再先序遍歷該二叉樹輸出所有節(jié)點。輸出時，通過parent節(jié)點的第一個孩子是否有兄弟節(jié)點控制縮進(jìn)輸出” | ”或” ”；目錄的大小為該目錄左子樹（以其第一個孩子為根的樹）所有節(jié)點的size和加上它本身大小。
三、設(shè)計
1. 數(shù)據(jù)結(jié)構(gòu)的設(shè)計和說明
在一開始設(shè)計要采用的數(shù)據(jù)結(jié)構(gòu)時，雖然課題只要求“樹結(jié)構(gòu)最多10層（樹的深度），每一層最多2個文件/目錄”，考慮到問題的實際意義，我決定把它優(yōu)化消除這一限制，于是采用孩子兄弟的數(shù)據(jù)結(jié)構(gòu)，后來由于縮進(jìn)輸出的需要又增加了parent域。
2. 關(guān)鍵算法的設(shè)計
（1）輸入處理：從外部文件每讀入一行處理一行，數(shù)據(jù)結(jié)構(gòu)的構(gòu)造與讀入同時進(jìn)行，提取節(jié)點的name[]域和size域建立該行所有節(jié)點。其間，利用隊列設(shè)立parentArray[]用來記錄所有的目錄節(jié)點地址，設(shè)置兩個虛擬指針rear和head，每增加一個目錄rear+1，head標(biāo)記可作為當(dāng)前節(jié)點parent域的目錄，每遇到一個‘）’ head+1處理下一個目錄包含的節(jié)點。當(dāng)輸入文件結(jié)束時所采用的孩子兄弟雙親鏈表二叉樹也就建立完成。
(2)輸出處理：先序遍歷所建立的二叉樹，每個節(jié)點輸出一行，都是先通過其parent節(jié)點的第一個孩子是否有兄弟節(jié)點標(biāo)記flag[0]~flag[i]，然后從flag[i]~flag[0]控制輸出縮進(jìn)符” | ”或” ”后再輸出該節(jié)點信息。
3． 數(shù)據(jù)結(jié)構(gòu)圖：
四、源程序清單（Win7系統(tǒng)WinTC環(huán)境下編譯運(yùn)行通過）：
/*
========================================================
課題：文件目錄結(jié)構(gòu)的顯示
Author:Estrong. All Rights Reserved.
指導(dǎo)老師：LinFang
2011年1月7日寫于福建工程學(xué)院.
========================================================
*/
#include "stdio.h"
#include "string.h"
#define Null 0
#define MAX 200
/*輸入文件每行應(yīng)不超過MAX個字符*/
typedef struct node /*采用孩子兄弟雙親鏈表的存儲結(jié)構(gòu)*/
{
char name[12];
unsigned int size;
struct node *parent,*first_child,*next_sibling;
}BinTNode,*BinTree;
/* 添加新節(jié)點 */
BinTree New_BinTNode(char str[],int *I,BinTree parentArray[],int *head,int *rear)
{ int i=0;
BinTree bt;
bt=(BinTNode *)malloc(sizeof(BinTNode));
bt->parent=parentArray[*head]; /*鏈接雙親結(jié)點確定歸屬目錄*/
bt->first_child=Null;
bt->next_sibling=Null;
if(str[*I]=='*')
{(*rear)++; parentArray[*rear]=bt;}
while(str[*I]!=' ')
{
bt->name[i]=str[*I];
(*I)++;i++;
}
bt->name[i]='\0';(*I)++;
bt->size=str[*I]-'0';(*I)++;
while ((str[*I]!=' ')&&(str[*I]!=')')&&((*I)<strlen(str)-1)) /*條件(*I)<strlen(str)-1)是考慮到根節(jié)點沒有‘ ’和')'*/
{
bt->size=bt->size*10+(str[*I]-'0');
(*I)++;
}
return bt;
}
/* 創(chuàng)建數(shù)據(jù)（將輸入數(shù)據(jù)轉(zhuǎn)化為所采用的樹結(jié)構(gòu)) */
BinTree Create_BinTree(FILE *input)
{ int I=0,rear=0,head=1; /*parentArray[head]用來記錄當(dāng)前節(jié)點應(yīng)指向的parent目錄節(jié)點*/
/*parentArray[rear]用來記錄最后一個目錄節(jié)點*/
BinTree parentArray[MAX];/*parentArray[]用來記錄所有的目錄節(jié)點地址*/
BinTree root,bt,pbt;
char str[MAX];
fgets(str,MAX,input);
root=New_BinTNode(str,&I,parentArray,&head,&rear);
root->parent=Null; /* 在創(chuàng)建根節(jié)點時其parent的賦值是隨機(jī)的，這里給它賦回空 */
while(!feof(input))
{I=1; /*I是輸入文件每行字符串中的下標(biāo)，貫穿該行字符處理始末*/
fgets(str,MAX,input);
while(I<=(strlen(str)-1))
{
if(str[I]!=')')
{
bt=New_BinTNode(str,&I,parentArray,&head,&rear);
parentArray[head]->first_child=bt;
pbt=bt;
do /*創(chuàng)建并鏈接一對括號里的所有兄弟節(jié)點*/
{
if(str[I]==' ')
{
I++;
pbt->next_sibling=New_BinTNode(str,&I,parentArray,&head,&rear); /*創(chuàng)建兄弟節(jié)點*/
pbt=pbt->next_sibling;
}
}while(str[I]!=')') ;
head++; I=I+3; /* 此時遇到右括號head+1處理下一個目錄；I+3跳過") (" */
}
else
{head++ ; I=I+3;} /* 此時也遇到右括號 */
}
}
return root;
}
/* 求目錄大小 */
int SIZE(BinTree bt) /*返回當(dāng)前目錄左子樹的大?。ㄎ醇由显夸洿笮。?/
{ int size;
if(bt)
size=bt->size+SIZE(bt->first_child)+SIZE(bt->next_sibling);
else size=0;
return size;
}
/* 輸出單個節(jié)點 */
void out(BinTree bt,FILE *output)
{ char size_str[10];
BinTree pbt=bt->parent;
int i=-1,j=0,k;
int flag[11]; /*flag[i]用來控制縮進(jìn)，子目錄深度可以設(shè)置，目前設(shè)為11*/
for(k=0;k<11;k++) flag[k]=0;
if(bt->name[0]=='*') bt->size=bt->size+SIZE(bt->first_child);
/*目錄的大小為該目錄本身大小及其左子樹（以其第一個孩子為根的樹）所有節(jié)點的size和*/
while(pbt!=Null)
{
i++;
if(pbt->next_sibling) flag[j]=1; /*輸出時flag[i]=1縮進(jìn)"| " */
else flag[j]=0; /*輸出時flag[i]=0縮進(jìn)" " */
pbt=pbt->parent;
j++;
}
while(i>=0)
{
if(flag[i]) {printf("| ");fprintf(output,"| ");}
else {printf(" ");fprintf(output," ");}
i--;
}
printf("|_%s[%d]\n",bt->name,bt->size);
fprintf(output,"|_%s[%d]\n",bt->name,bt->size);
}
/* 先序遍歷輸出整棵樹 */
void OUTPUT(BinTree bt,FILE *output)
{
if(bt)
{
out(bt,output);
OUTPUT(bt->first_child,output);
OUTPUT(bt->next_sibling,output);
}
}
/* 主函數(shù) */
main()
{ FILE *input,*output;
BinTree root;
if((input=fopen("input.txt","r"))==NULL)
{
printf("Cannot find the file! Strike any key to exit!");
getch();
exit(1);
}
output=fopen("output.txt","w");
root=Create_BinTree(input);
OUTPUT(root,output);
getch();
fclose(input);fclose(output);
}
五、測試數(shù)據(jù)及測試結(jié)果：
（注：以下測試數(shù)據(jù)置于外部文件input.txt里）
*/kqss 1
(*mark 1 *alex 1 *course 1 aa.txt 12 hw.c 5 hjh.c 4 gffg.c 5)
() (kkhw.c 3 *course 1) (ghw.c 5 *test 1 abcd.exe 13 *fdg 1 hw.c 5 hjh.c 4)
(aa.txt 2 kqss.c 100 hgfgsdf.h 35 ghgjh.mp3 7) () (arfe.txt 12 kqss.c 100 fdfs.h 35)
