Skip to content

boyu-ai/Hands-on-DS

Repository files navigation

动手学数据结构与算法 电子资料仓库

仓库各目录中的内容

  • textcode 目录包含本书代码清单中的所有代码,按照章节进行排列,通常类名即为文件名,类名 + Test.cpp 即为该类的测试程序。例如,textcode/chapter2/seqList.h 及对应的 .cpp 文件包含代码清单 2-2 ~ 代码清单 2-5 顺序表的完整定义与实现。此外,本书介绍的数据结构简单应用也包含在内,例如,textcode/chapter2/multinomial.h 及 multinomialTest.cpp 是代码清单 2-14 所示的多项式类的实现与测试程序。

  • code 目录包含本书除第 1 章、第 7 章和第 11 章以外,每章的大型应用实现中各个应用模块的代码。由于涉及文件较多,将它们与 textcode 目录分开。通常,类名即为子目录名,例如,code/TrainScheduler 目录包含 2.5 节中列车运行计划管理类的完整实现与测试代码。

  • trainsys 目录包含整个大型应用——火车票管理系统的代码。

    • DataStructure 子目录是大型应用中使用的数据结构实现。注意,作为一个完整应用,其实现可能和textcode目录与code 目录中的代码有所差异。例如,余票管理类和行程管理类均使用了一对多B+树进行存储而非8.4节介绍的一对一B+树,这些差异已在每章介绍大型应用实现时阐明,读者可以亲自动手运行代码,比对这些差异,体会从简单的数据结构到复杂的大型应用实现的变化。
    • main.cpp 文件是火车票管理系统的主入口,与火车票管理系统的交互方式为命令行。
    • CommandParser.h 和 CommandParser.cpp 文件是火车票管理系统的命令解析类,它负责解析用户输入的指令,调用对应管理类的系统功能。
    • 其余 .h 文件和对应的 .cpp 文件是大型应用各个类的定义与具体实现。
    • input.in 文件(位于根目录)是火车票管理系统测试样例输入。
    • station.txt 文件(位于根目录)是火车票管理系统测试样例的站点列表。
    • init_database.sh 文件(位于根目录)用于清除火车票管理系统在磁盘上保存的数据文件。
  • 习题答案.docx 包含每章最后一节习题中客观题的答案和部分主观题的解题思路。

本地环境搭建和仓库代码运行

火车票管理系统这一大型应用由许多文件构成,读者下载代码仓库后需要在本地搭建C++编译与测试环境后方可动手学习,具体环境搭建方法参见本书附录 B.3。

本书的所有代码在 GNU/Linux 环境下测试编译通过,因此推荐读者采用 g++ 9.4 或更新版本的 GNU C++ 编译器,并选用 -lm、-Wall、-Wextra、-O1、-std=c++14 等编译参数。例如,读者可以在命令行中执行 g++ max1max2Test.cpp -o max1max2Test -lm -Wall -Wextra -O1 -std=c++14 ,将代码清单1-1 函数 max1 与 max2 的实现及其测试程序的源文件max1max2Test.cpp 编译为可执行文件 max1max2Test。