对于树型文件目录，有什么快速的查找算法？

我在写一个文件打包工具，支持树型文件结构。
请问，查找某个路径下的文件，有什么快速的查找算法？

11 个解决方案

#1

快速算法的前提是你这个树里的数据排列满足一定的要求，或者干脆你令建索引。比如stl的map和set就是红黑树实现的，快速查找也是靠红黑树本身的特性实现的。否则你只好遍历了~

#2

存成树形结构最好啊，N叉树就可以了。

#3

system("dir /b /a-d c:\\*.* >d:\\allfiles.txt");
//读文件d:\\allfiles.txt的内容即C:\\下所有文件的名字
system("dir /b /a-d /s c:\\*.* >d:\\allfilesinsub.txt");
//读文件d:\\allfilesinsub.txt的内容即C:\\下所有文件的名字包含子目录
system("dir /b /ad  c:\\*.* >d:\\alldirs.txt");
//读文件d:\\alldirs.txt的内容即C:\\下所有子目录的名字
请记住，能用shell命令获取文件、文件夹信息或者操作文件、文件夹最好用shell命令获取或者操作，而不要用各种API获取或者操作，因为当遇到非法文件夹名或非法文件名或非法文件长度、非法文件日期、压缩文件、链接文件、稀疏文件……等各种意料之外的情况时，API会处理的不全面或陷入死循环，而shell命令不会。

#4

引用 3 楼 zhao4zhong1 的回复:

system("dir /b /a-d c:\\*.* >d:\\allfiles.txt");
//读文件d:\\allfiles.txt的内容即C:\\下所有文件的名字
system("dir /b /a-d /s c:\\*.* >d:\\allfilesinsub.txt");
//读文件d:\\allfilesinsub.txt的内容即C:\\下所有文件的名字包含子目录
system("dir /b /ad  c:\\*.* >d:\\alldirs.txt");
//读文件d:\\alldirs.txt的内容即C:\\下所有子目录的名字
请记住，能用shell命令获取文件、文件夹信息或者操作文件、文件夹最好用shell命令获取或者操作，而不要用各种API获取或者操作，因为当遇到非法文件夹名或非法文件名或非法文件长度、非法文件日期、压缩文件、链接文件、稀疏文件……等各种意料之外的情况时，API会处理的不全面或陷入死循环，而shell命令不会。

你劳师动众地用shell不是自寻烦恼，还是保存到文件里~
LZ分明是自己想弄个工具，其中包含文件查找的功能，你却非要LZ用shell命令，看起来还是用c++调用shell命令~

#5

引用 4 楼 vipcxj 的回复:

Quote: 引用 3 楼 zhao4zhong1 的回复:

system("dir /b /a-d c:\\*.* >d:\\allfiles.txt");
//读文件d:\\allfiles.txt的内容即C:\\下所有文件的名字
system("dir /b /a-d /s c:\\*.* >d:\\allfilesinsub.txt");
//读文件d:\\allfilesinsub.txt的内容即C:\\下所有文件的名字包含子目录
system("dir /b /ad  c:\\*.* >d:\\alldirs.txt");
//读文件d:\\alldirs.txt的内容即C:\\下所有子目录的名字
请记住，能用shell命令获取文件、文件夹信息或者操作文件、文件夹最好用shell命令获取或者操作，而不要用各种API获取或者操作，因为当遇到非法文件夹名或非法文件名或非法文件长度、非法文件日期、压缩文件、链接文件、稀疏文件……等各种意料之外的情况时，API会处理的不全面或陷入死循环，而shell命令不会。

你劳师动众地用shell不是自寻烦恼，还是保存到文件里~
LZ分明是自己想弄个工具，其中包含文件查找的功能，你却非要LZ用shell命令，看起来还是用c++调用shell命令~

我是在设计游戏的封包格式，以前为了省事，只支持2级树，现在想做成无限层级的树型结构。
如果没什么好的方法，我就直接在初始化的时候，将所有文件路径和他的offset保存到map里，然后获取某个文件的时候，用这个map获得其offset

#6

引用 5 楼 weiwuyuan 的回复:

Quote: 引用 4 楼 vipcxj 的回复:

Quote: 引用 3 楼 zhao4zhong1 的回复:

system("dir /b /a-d c:\\*.* >d:\\allfiles.txt");
//读文件d:\\allfiles.txt的内容即C:\\下所有文件的名字
system("dir /b /a-d /s c:\\*.* >d:\\allfilesinsub.txt");
//读文件d:\\allfilesinsub.txt的内容即C:\\下所有文件的名字包含子目录
system("dir /b /ad  c:\\*.* >d:\\alldirs.txt");
//读文件d:\\alldirs.txt的内容即C:\\下所有子目录的名字
请记住，能用shell命令获取文件、文件夹信息或者操作文件、文件夹最好用shell命令获取或者操作，而不要用各种API获取或者操作，因为当遇到非法文件夹名或非法文件名或非法文件长度、非法文件日期、压缩文件、链接文件、稀疏文件……等各种意料之外的情况时，API会处理的不全面或陷入死循环，而shell命令不会。

你劳师动众地用shell不是自寻烦恼，还是保存到文件里~
LZ分明是自己想弄个工具，其中包含文件查找的功能，你却非要LZ用shell命令，看起来还是用c++调用shell命令~

我是在设计游戏的封包格式，以前为了省事，只支持2级树，现在想做成无限层级的树型结构。
如果没什么好的方法，我就直接在初始化的时候，将所有文件路径和他的offset保存到map里，然后获取某个文件的时候，用这个map获得其offset

你这也是个办法啊，实现起来也不麻烦。boost里有个支持多重索引的map和set，如果你不光用文件名索搜，还想用修改日期，文件大小之类的搜索，可以考虑用那个东西，否则用map就够了

#7

引用 6 楼 vipcxj 的回复:

Quote: 引用 5 楼 weiwuyuan 的回复:

Quote: 引用 4 楼 vipcxj 的回复:

Quote: 引用 3 楼 zhao4zhong1 的回复:

system("dir /b /a-d c:\\*.* >d:\\allfiles.txt");
//读文件d:\\allfiles.txt的内容即C:\\下所有文件的名字
system("dir /b /a-d /s c:\\*.* >d:\\allfilesinsub.txt");
//读文件d:\\allfilesinsub.txt的内容即C:\\下所有文件的名字包含子目录
system("dir /b /ad  c:\\*.* >d:\\alldirs.txt");
//读文件d:\\alldirs.txt的内容即C:\\下所有子目录的名字
请记住，能用shell命令获取文件、文件夹信息或者操作文件、文件夹最好用shell命令获取或者操作，而不要用各种API获取或者操作，因为当遇到非法文件夹名或非法文件名或非法文件长度、非法文件日期、压缩文件、链接文件、稀疏文件……等各种意料之外的情况时，API会处理的不全面或陷入死循环，而shell命令不会。

你劳师动众地用shell不是自寻烦恼，还是保存到文件里~
LZ分明是自己想弄个工具，其中包含文件查找的功能，你却非要LZ用shell命令，看起来还是用c++调用shell命令~

我是在设计游戏的封包格式，以前为了省事，只支持2级树，现在想做成无限层级的树型结构。
如果没什么好的方法，我就直接在初始化的时候，将所有文件路径和他的offset保存到map里，然后获取某个文件的时候，用这个map获得其offset

你这也是个办法啊，实现起来也不麻烦。boost里有个支持多重索引的map和set，如果你不光用文件名索搜，还想用修改日期，文件大小之类的搜索，可以考虑用那个东西，否则用map就够了

我还是宁愿效率差一些，也要让代码简洁易读。能不用class，就不用class，能不用第3方库就不用第3方库

#8

引用 7 楼 weiwuyuan 的回复:

Quote: 引用 6 楼 vipcxj 的回复:

Quote: 引用 5 楼 weiwuyuan 的回复:

Quote: 引用 4 楼 vipcxj 的回复:

Quote: 引用 3 楼 zhao4zhong1 的回复:

system("dir /b /a-d c:\\*.* >d:\\allfiles.txt");
//读文件d:\\allfiles.txt的内容即C:\\下所有文件的名字
system("dir /b /a-d /s c:\\*.* >d:\\allfilesinsub.txt");
//读文件d:\\allfilesinsub.txt的内容即C:\\下所有文件的名字包含子目录
system("dir /b /ad  c:\\*.* >d:\\alldirs.txt");
//读文件d:\\alldirs.txt的内容即C:\\下所有子目录的名字
请记住，能用shell命令获取文件、文件夹信息或者操作文件、文件夹最好用shell命令获取或者操作，而不要用各种API获取或者操作，因为当遇到非法文件夹名或非法文件名或非法文件长度、非法文件日期、压缩文件、链接文件、稀疏文件……等各种意料之外的情况时，API会处理的不全面或陷入死循环，而shell命令不会。

你劳师动众地用shell不是自寻烦恼，还是保存到文件里~
LZ分明是自己想弄个工具，其中包含文件查找的功能，你却非要LZ用shell命令，看起来还是用c++调用shell命令~

我是在设计游戏的封包格式，以前为了省事，只支持2级树，现在想做成无限层级的树型结构。
如果没什么好的方法，我就直接在初始化的时候，将所有文件路径和他的offset保存到map里，然后获取某个文件的时候，用这个map获得其offset

你这也是个办法啊，实现起来也不麻烦。boost里有个支持多重索引的map和set，如果你不光用文件名索搜，还想用修改日期，文件大小之类的搜索，可以考虑用那个东西，否则用map就够了

我还是宁愿效率差一些，也要让代码简洁易读。能不用class，就不用class，能不用第3方库就不用第3方库

那你就用map喽，stl应该不算第三方库吧，而且对你以前代码也改动比较小，也不需要另外搞个class，只要给你以前写的类里加个成员变量就行了，并且map的查找效率还是非常高的，这不是完全符合你的要求嘛

#9

引用 8 楼 vipcxj 的回复:

Quote: 引用 7 楼 weiwuyuan 的回复:

Quote: 引用 6 楼 vipcxj 的回复:

Quote: 引用 5 楼 weiwuyuan 的回复:

Quote: 引用 4 楼 vipcxj 的回复:

Quote: 引用 3 楼 zhao4zhong1 的回复:

system("dir /b /a-d c:\\*.* >d:\\allfiles.txt");
//读文件d:\\allfiles.txt的内容即C:\\下所有文件的名字
system("dir /b /a-d /s c:\\*.* >d:\\allfilesinsub.txt");
//读文件d:\\allfilesinsub.txt的内容即C:\\下所有文件的名字包含子目录
system("dir /b /ad  c:\\*.* >d:\\alldirs.txt");
//读文件d:\\alldirs.txt的内容即C:\\下所有子目录的名字
请记住，能用shell命令获取文件、文件夹信息或者操作文件、文件夹最好用shell命令获取或者操作，而不要用各种API获取或者操作，因为当遇到非法文件夹名或非法文件名或非法文件长度、非法文件日期、压缩文件、链接文件、稀疏文件……等各种意料之外的情况时，API会处理的不全面或陷入死循环，而shell命令不会。

你劳师动众地用shell不是自寻烦恼，还是保存到文件里~
LZ分明是自己想弄个工具，其中包含文件查找的功能，你却非要LZ用shell命令，看起来还是用c++调用shell命令~

我是在设计游戏的封包格式，以前为了省事，只支持2级树，现在想做成无限层级的树型结构。
如果没什么好的方法，我就直接在初始化的时候，将所有文件路径和他的offset保存到map里，然后获取某个文件的时候，用这个map获得其offset

你这也是个办法啊，实现起来也不麻烦。boost里有个支持多重索引的map和set，如果你不光用文件名索搜，还想用修改日期，文件大小之类的搜索，可以考虑用那个东西，否则用map就够了

我还是宁愿效率差一些，也要让代码简洁易读。能不用class，就不用class，能不用第3方库就不用第3方库

那你就用map喽，stl应该不算第三方库吧，而且对你以前代码也改动比较小，也不需要另外搞个class，只要给你以前写的类里加个成员变量就行了，并且map的查找效率还是非常高的，这不是完全符合你的要求嘛

在想想，或许能找到一种用线性结构存储树形文件的方法，

#10

引用 9 楼 weiwuyuan 的回复:

Quote: 引用 8 楼 vipcxj 的回复:

Quote: 引用 7 楼 weiwuyuan 的回复:

Quote: 引用 6 楼 vipcxj 的回复:

Quote: 引用 5 楼 weiwuyuan 的回复:

Quote: 引用 4 楼 vipcxj 的回复:

Quote: 引用 3 楼 zhao4zhong1 的回复:

system("dir /b /a-d c:\\*.* >d:\\allfiles.txt");
//读文件d:\\allfiles.txt的内容即C:\\下所有文件的名字
system("dir /b /a-d /s c:\\*.* >d:\\allfilesinsub.txt");
//读文件d:\\allfilesinsub.txt的内容即C:\\下所有文件的名字包含子目录
system("dir /b /ad  c:\\*.* >d:\\alldirs.txt");
//读文件d:\\alldirs.txt的内容即C:\\下所有子目录的名字
请记住，能用shell命令获取文件、文件夹信息或者操作文件、文件夹最好用shell命令获取或者操作，而不要用各种API获取或者操作，因为当遇到非法文件夹名或非法文件名或非法文件长度、非法文件日期、压缩文件、链接文件、稀疏文件……等各种意料之外的情况时，API会处理的不全面或陷入死循环，而shell命令不会。

你劳师动众地用shell不是自寻烦恼，还是保存到文件里~
LZ分明是自己想弄个工具，其中包含文件查找的功能，你却非要LZ用shell命令，看起来还是用c++调用shell命令~

我是在设计游戏的封包格式，以前为了省事，只支持2级树，现在想做成无限层级的树型结构。
如果没什么好的方法，我就直接在初始化的时候，将所有文件路径和他的offset保存到map里，然后获取某个文件的时候，用这个map获得其offset

你这也是个办法啊，实现起来也不麻烦。boost里有个支持多重索引的map和set，如果你不光用文件名索搜，还想用修改日期，文件大小之类的搜索，可以考虑用那个东西，否则用map就够了

我还是宁愿效率差一些，也要让代码简洁易读。能不用class，就不用class，能不用第3方库就不用第3方库

那你就用map喽，stl应该不算第三方库吧，而且对你以前代码也改动比较小，也不需要另外搞个class，只要给你以前写的类里加个成员变量就行了，并且map的查找效率还是非常高的，这不是完全符合你的要求嘛

在想想，或许能找到一种用线性结构存储树形文件的方法，

数组和线性链表都能实现存放树，但对于数组插入数据效率会很杯具，但用链表，你得弄两份，一份放数据，一份放拓扑结构，除了遍历实现起来方便，没一点比一般的树形结构好吧~

#11

引用 10 楼 vipcxj 的回复:

Quote: 引用 9 楼 weiwuyuan 的回复:

Quote: 引用 8 楼 vipcxj 的回复:

Quote: 引用 7 楼 weiwuyuan 的回复:

Quote: 引用 6 楼 vipcxj 的回复:

Quote: 引用 5 楼 weiwuyuan 的回复:

Quote: 引用 4 楼 vipcxj 的回复:

Quote: 引用 3 楼 zhao4zhong1 的回复:

system("dir /b /a-d c:\\*.* >d:\\allfiles.txt");
//读文件d:\\allfiles.txt的内容即C:\\下所有文件的名字
system("dir /b /a-d /s c:\\*.* >d:\\allfilesinsub.txt");
//读文件d:\\allfilesinsub.txt的内容即C:\\下所有文件的名字包含子目录
system("dir /b /ad  c:\\*.* >d:\\alldirs.txt");
//读文件d:\\alldirs.txt的内容即C:\\下所有子目录的名字
请记住，能用shell命令获取文件、文件夹信息或者操作文件、文件夹最好用shell命令获取或者操作，而不要用各种API获取或者操作，因为当遇到非法文件夹名或非法文件名或非法文件长度、非法文件日期、压缩文件、链接文件、稀疏文件……等各种意料之外的情况时，API会处理的不全面或陷入死循环，而shell命令不会。

你劳师动众地用shell不是自寻烦恼，还是保存到文件里~
LZ分明是自己想弄个工具，其中包含文件查找的功能，你却非要LZ用shell命令，看起来还是用c++调用shell命令~

我是在设计游戏的封包格式，以前为了省事，只支持2级树，现在想做成无限层级的树型结构。
如果没什么好的方法，我就直接在初始化的时候，将所有文件路径和他的offset保存到map里，然后获取某个文件的时候，用这个map获得其offset

你这也是个办法啊，实现起来也不麻烦。boost里有个支持多重索引的map和set，如果你不光用文件名索搜，还想用修改日期，文件大小之类的搜索，可以考虑用那个东西，否则用map就够了

我还是宁愿效率差一些，也要让代码简洁易读。能不用class，就不用class，能不用第3方库就不用第3方库

那你就用map喽，stl应该不算第三方库吧，而且对你以前代码也改动比较小，也不需要另外搞个class，只要给你以前写的类里加个成员变量就行了，并且map的查找效率还是非常高的，这不是完全符合你的要求嘛

在想想，或许能找到一种用线性结构存储树形文件的方法，

数组和线性链表都能实现存放树，但对于数组插入数据效率会很杯具，但用链表，你得弄两份，一份放数据，一份放拓扑结构，除了遍历实现起来方便，没一点比一般的树形结构好吧~

我研究下暴雪的MPQ文件，再看看，