Posts

一、什么是数据结构 结构：实体 + 关系，比如分子结构，关系图等 数据结构：按照逻辑关系组织起来的一批数据，按一定的存储方法所把它存储在计算机中，并在这些数据上定义了一个运算的集合 二、数据的逻辑结构 线性结构 线性表（表、栈、队列、串等） 非线性结构 树（二叉树、Huffman树、二叉检索树等） 图（有向图、无向图等） 图 ⊇ 树 ⊇ 二叉树 ⊇ 线性表 三、数据的存储结构 将逻辑结构的结点映射到内存中，每一个结点都对应一个唯一的连续存储区域 内存可以看作从低地址到高地址的一个编码的线性结构，可以根据地址立即访问想要访问的内存单元，不需要搜索 存储结构主要有顺序、链接、索引和散列四种形式 顺序存储对应于数组 链接存储对应于链表 索引是对数据建立一个索引表，通过这个表有效的找到相应数据的存储地址 散列是一种特殊的索引结构，本身也是一种存储结构，通过关键码的映射关系，在整个散列表中用单位时间快速地找到其存储地址 四、抽象数据类型 ADT（Abstract Data Type） 定义了一组运算的数学模型 与物理存储结构无关 使软件系统建立在数据之上(面向对象) 五、定义抽象数据类型 抽象数据类型就是在逻辑结构上的运算，可以理解为抽象数据结构二元组 <数据对象D, 数据操作P> 先定义逻辑结构，再定义运算 逻辑结构：数据对象及其关系 运算：数据操作 就像面向对象语言中所定义的类（特别是抽象类），封装了数据成员和函数成员

算法 + 数据结构 = 程序 数据结构与算法是程序的灵魂，以问题求解为导向，进行问题抽象、数据抽象、算法抽象，通过有效地组织数据、设计高效的算法、完成高质量的程序，从而解决实际应用的问题。 流程：问题 => 数据 => 算法 理论（离散数学、概率统计、图论等） => 抽象（问题抽象、数据抽象、算法抽象等面向对象思想） => 设计（实现的某种具体编程语言） 逻辑抽象 + 运算抽象 => ADT 运算 + 存储 => 算法分析（时间和空间复杂度） 问题抽象：分析和抽象任务需求，建立问题模型 数据抽象：确定恰当的数据结构表示数学模型 算法抽象：在数据模型的基础上设计合适的算法

注意：这个对于单配置生成器是有效的，对于多配置生成器(例如Visual Studio)是无效的。因此在 Windows 平台，通过 MSYS 环境进行演示。 默认情况下（Linux平台），CMake 的一个构建目录(build dir)只包含一个配置，可以是 Debug、Release、MinSizeRel 或 RelWithDebInfo。但是，可以通过设置 CPack 来绑定多个构建目录，并构造一个包含同一项目的多个配置的发行包。 首先，我们希望确保 Debug 和 Release 构建对将要安装的可执行文件和库使用不同的名称。让我们使用 d 作为 Debug 可执行文件和库的后缀。在顶层 CMakeLists.txt 的开始部分添加 CMAKE_DEBUG_POSTFIX # 设置项目名称和版本 project(Tutorial VERSION 3.1)# 设置 CMAKE_DEBUG_POSTFIX，指定后缀为 d set(CMAKE_DEBUG_POSTFIX d)然后在 Tutorial 可执行文件上添加属性 DEBUG_POSTFIX： # 添加源码文件和生成的目标文件的名称 add_executable(Tutorial main.cpp)# And the DEBUG_POSTFIX property on the tutorial executable set_target_properties(Tutorial PROPERTIES DEBUG_POSTFIX ${CMAKE_DEBUG_POSTFIX})为 MathFunctions 库添加版本号信息，在 Mathfunctions/CMakelists.txt 中，设置 VERSION 和 SOVERSION 属性： # add the library that runs add_library(MathFunctions MathFunctions....

在安装和测试过程中，我们增加了 CMake 安装库文件和项目依赖的头文件(bin、lib、include)的能力。在打包可安装程序的过程中，我们增加了打包这些信息的能力，这样它就可以分发给其他人使用 接下来是如何添加必要的信息，以便其他 CMake 项目可以使用我们的项目，无论是在构建目录、本地安装还是打包的时候 第一步是更新我们的 install(TARGETS) 命令，不仅指定 DESTINATION，还指定 EXPORT。EXPORT 关键字生成一个 CMake 文件，其中包含从安装树导入安装命令中列出的所有目标的代码。 修改 MathFunctions/CMakeLists.txt 文件代码： # install rules set(installable_libs MathFunctions tutorial_compiler_flags)if(TARGET SqrtLibrary) list(APPEND installable_libs SqrtLibrary)endif()install(TARGETS ${installable_libs} EXPORT MathFunctionsTargets DESTINATION lib)install(FILES MathFunctions.h DESTINATION include)第二步我们还需要显式地安装生成的 MathFunctionsTargets.cmake 文件。在顶层的 CMakeLists.txt 文件底部添加如下代码： install(EXPORT MathFunctionsTargets FILE MathFunctionsTargets.cmake DESTINATION lib/cmake/MathFunctions )此时构建会有下面的错误： 这是因为在生成导出信息期间，它将导出内在绑定到当前计算机项目的路径，在其他计算机上路径无效。 第三步更新 MathFunctions/CMakeLists.txt 中的 target_include_directories() 用来设置在 build 时和在 install/package 时需要使用不同的 INTERFACE locations。 # 将当前二进制目录添加到包含目录列表中 target_include_directories(MathFunctions # INTERFACE ${CMAKE_CURRENT_SOURCE_DIR} INTERFACE $<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}> $<INSTALL_INTERFACE:include> )第四步我们还需要生成一个 MathFunctionsConfig.cmake，这样 CMake 的 find_package() 命令就可以找到我们的项目。在顶层的项目目录添加 Config....

target_compile_features target_compile_options COMPILE_LANG_AND_ID BUILD_INTERFACE 生成器表达式(Generator expressions)允许在许多目标属性的上下文中使用，比如 LINK LIBRARIES、INCLUDE DIRECTORIES、COMPILE DEFINITIONS 等。当使用命令来填充这些属性时，它们也可以被使用，例如 target_link_libraries()、target_include_directories()、target_compile_definitions() 等。 生成器表达式可以用于启用条件链接、编译时使用的条件定义、条件包含目录等。这些条件可能基于构建配置、目标属性、平台信息或任何其他可查询的信息。 有不同类型的生成器表达式，包括逻辑表达式、信息表达式和输出表达式。 逻辑表达式用于创建条件输出。基本的表达式是 0 和 1 表达式。 生成器表达式的一个常见用法是有条件地添加编译器标志，比如那些用于语言级别或警告的标志。一个很好的模式是将该信息关联到一个 INTERFACE 目标，从而允许该信息传播。让我们先构造一个接口目标，并指定所需的 c++ 标准 11，而不是使用 CMAKE CXX 标准。 # 指定 C++ 标准 # set(CMAKE_CXX_STANDARD 11) # set(CMAKE_CXX_STANDARD_REQUIRED True) # 将上面的代码替换为 add_library(tutorial_compiler_flags INTERFACE)target_compile_features(tutorial_compiler_flags INTERFACE cxx_std_11)接下来，我们为项目添加所需的编译器警告标志。由于警告标志因编译器的不同而不同，我们使用 COMPILE_LANG_AND_ID 生成器表达式来控制给定语言和一组编译器 ID 要应用哪些标志（注：将要使用的生成器表达式是在 3.15 中引入的，所以要更新 cmake_minimum_required 的版本为 3.15），如下所示： set(gcc_like_cxx "$<COMPILE_LANG_AND_ID:CXX,ARMClang,AppleClang,Clang,GNU,LCC>")set(msvc_cxx "$<COMPILE_LANG_AND_ID:CXX,MSVC>")target_compile_options(tutorial_compiler_flags INTERFACE "$<${gcc_like_cxx}:$<BUILD_INTERFACE:-Wall;-Wextra;-Wshadow;-Wformat=2;-Wunused>>" "$<${msvc_cxx}:$<BUILD_INTERFACE:-W3>>" )我们看到警告标志被封装在一个 BUILD_INTERFACE 条件中。这样做是为了让我们已安装项目的使用者不会继承我们的警告标志。 修改 Mathfunctions/cmakelists.txt，以便所有编译目标都有一个 target_link_libraries() 调用我们设置的编译条件标识 tutorial_compiler_flags。...