# Coursework_DiskusageAnalyser

**Repository Path**: Celesteria/coursework_-diskusage-analyser

## Basic Information

- **Project Name**: Coursework_DiskusageAnalyser
- **Description**: 南开大学2023春，高级语言程序设计二大作业
- **Primary Language**: C++
- **License**: GPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2023-05-06
- **Last Updated**: 2023-10-27

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Coursework_DiskusageAnalyser

#### 介绍
南开大学2023春，高级语言程序设计二大作业，一个模仿WizTree做的磁盘空间分析工具，由于看不懂MTF索引怎么使用于是采取了最原始的深度优先搜索，导致速度远远慢于WizTree。实现了搜素功能，但因为不会其它索引方式，只好建了一颗庞大的字典树作为索引（由于似乎好像不能直接获取文件夹占用的空间，因此我在多叉树建立完之后，从底层文件一个个累加上来获得每个文件夹占用的空间，因此字典树只好在累加结束只好再遍历多叉树得到。另外，如果想实现通过中间内容查找，我采用添加文件名所有后缀到字典树来实现，这导致扫描与树的建立过程更慢了，且字典树也更肥了）。

#### 程序运行原理
1.  用户选择扫描的根目录。
2.  从根目录开始，采用深度优先搜素方法，遍历根目录下的所有文件/文件夹，并将它们存入一多叉树与一字典树中。
  2.1  多叉树的实现：
           对多叉树的每一个节点，分别定义了child，brother，father与lastChild四个指针，其具体结构如下：
           ![输入图片说明](https://foruda.gitee.com/images/1683973920381286675/7cc67fa6_12755365.jpeg "微信图片_20230513183113.jpg")
           图中，节点1为父节点，而2、3、4均为它的子节点，其中2为1的第一个子节点，4为1的最后一个子节点。对每一个节点，都可以通过调取father来访问父节点，这可以用来方 
           便地访问文件系统中的上一层目录；通过调取child与child->brother来获取它所有的子节点，这可以用来方便地查看一个文件夹下的最高层目录内所有文件的信息；通过调取 
           lastChild访问当前的最后一个节点，用于快速找到插入下一个子节点的位置。
           在创建新节点时，先判断父节点的child是否为空，若child为空指针，则在child位置建立新节点，并将lastChild指向child；否则在lastChild->brother建立新阶段，然 
           后再将lastChild指向新建立的节点。
  2.2  字典树的实现：
           字典树实际上也是一个多叉树，但考虑到每一层的子节点数量可能较多，选择使用一个QMap容器来装载子节点，以节点名为键，以节点的指针为键值存储。
           在插入新分支时，在每一层寻找作为名称输入的QString对象对应位置的字符，若未找到，则先新建名为该字符的节点。找到后，再在下一层内寻找QString对象的下一个字 
           符，直到该QString被遍历了一遍。
  2.3  文件系统扫描的实现：
           通过调用Windows的Win32 API获取待扫描文件的句柄，当前文件信息与下一文件信息，完成以下逻辑：
       2.3.1  如果当前文件为符号链接，跳过，避免陷入死循环；
       2.3.2  将当前文件信息添加到多叉树中；
       2.3.3  如果当前文件是一个文件夹，且名字不为"."（目录本身）与".."（上级目录），以刚才添加的节点为新的根节点，递归调用扫描函数；
       2.3.4  处理下一个文件。
3.  后边懒得写了，就这样吧。


#### 编译与使用说明

1.  本程序使用QT6.5.0与C++17标准（qt creator自己选的，我好像没用到17的特性）编写，使用QT5编译会发生错误，请使用QT6以上版本编译。
2.  直接打开DiskusageAnalyser.pro，点击编译即可运行。
3.  如果配置好了QT6的系统环境变量，直接找到build-DiskusageAnalyser-Desktop_Qt_6_5_0_MinGW_64_bit-Debug\debug\DiskusageAnalyser.exe即可运行。