题解 | #路径打印#

#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXCHAR 4 //单个文件名长度
#define MAXPATHLEN 512 //文件路径总长度
#define MAXFILECOUNT 32 //同级文件夹上限
using namespace std;

typedef struct BiTNode {
    char Name[MAXCHAR];
    BiTNode* firstChild;
    BiTNode* nextSibling;
} BiTree, BiTNode;

typedef struct SortTable { //写完才发现要排序QAQ
    char fc; //憨批测试案例反正就一位
    BiTNode* address;
    bool operator< (SortTable st) const {
        if (fc == st.fc) {
            return true;
        } else {
            return fc < st.fc;
        }
    }
} SortTable;

BiTNode* genNode(char* name) {
    BiTNode* node = new BiTNode;
    node->firstChild = nullptr;
    node->nextSibling = nullptr;
    memcpy(node->Name, name, MAXCHAR);
    return node;
}

BiTNode* hasSameFile(char* s, BiTNode* node, bool& hasSame) {

    BiTNode* prev = node;
    BiTNode* current = node->firstChild;
    while (current) {
        //printf("current:%s, target:%s\n",current->Name,s);
        if (strcmp(s, current->Name) == 0) {
            hasSame = true;
            return current;
        } else {
            prev = current;
            current = current->nextSibling;
        }
    }
    hasSame = false;
    return prev; //返回最后停止的结点
}

void pathToNode(char* path, BiTNode* root) {
    char fileName[MAXCHAR];
    int nameLen = 0;
    BiTNode* current = root; //当前文件夹
    if (path[strlen(path) - 1] == '\\') {
        path[strlen(path) - 1] = path[strlen(path)]; //剥去末尾符号
    }
    for (int i = 0; i <= strlen(path); i++) {
        if (path[i] != '\\' && i != strlen(path)) {
            //如果不是\也不是最后一个字符
            fileName[nameLen++] = path[i];
        } else {
            fileName[nameLen] = '\0', nameLen = 0;
            if (current->firstChild == nullptr) { //空文件夹
                current->firstChild = genNode(fileName);//新建文件夹
                current = current->firstChild;//打开新建文件夹
            } else { //文件夹不空
                bool hasSame;
                //检查是否有文件名相同的,有则返回文件夹指针，否则停留在末尾
                BiTNode* t = hasSameFile(fileName, current, hasSame);
                if (hasSame) {
                    current = t;
                } else {
                    t->nextSibling = genNode(fileName);//新建文件夹
                    current = t->nextSibling;
                }
            }
        }
    }
}

void freeTree(BiTNode *root) {
  if (root == NULL) return;

  freeTree(root->firstChild);
  freeTree(root->nextSibling);
  free(root);
}


void printer(BiTNode* node, int level) {
    //先把同级的文件夹都翻出来
    BiTNode* t = node;
    if (!t) { //到末尾了
        return;
    }
    int i = 0;
    while (t) {
        t = t->nextSibling;
        i++;
    }
    t = node;
    SortTable* st = new SortTable[i]();
    memset(st, 0, sizeof(st));
    for (int j = i; j > 0; j--) {
        st[j - 1].address = t;
        st[j - 1].fc = t->Name[0];
        t = t->nextSibling;
    }
    sort(st, st + i);
    for (int j = 0; j < i; j++) {
        for (int k = 0; k < level; k++) cout<<"  ";
        cout<<st[j].address->Name<<endl;
        // printf("%s\n", );
        printer(st[j].address->firstChild, level + 1);
    }

}

int main() {
    int len;
    char rootc[] = "\\\0";
    char path[MAXPATHLEN];

    while(scanf("%d", &len)==1){
        BiTree* T = genNode(rootc); //文件系统根节点
        while (len--) {
            scanf("%s", &path);
            pathToNode(path, T);
        }
        printer(T->firstChild, 0);
        printf("\n");
        freeTree(T);
    }
        return 0;

    
}