跳转至

教材：《数据结构与算法》 王曙燕 人民邮电出版社

Programs = Data Structures + Algorithm

数据结构中讨论的结构：

数据：描述客观事物的数值、字符以及能输入到计算机且能被处理的各种符号的集合。 数据元素（Data Element）:是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。 数据项（Data Item）：一个或多个数据项组成一个数据元素，数据项是具有独立含义的最小单位。 数据对象（Data Object）：性质相同的数据元素的集合，是数据的一个子集。 数据结构（Data Structure）:相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合。

数据类型（Data Type）：数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。 抽象数据类型（Abstract Data Type）：指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。

  • 实现：1. 传统的面向过程的程序设计；面向对象的程序设计；包、模型的设计方法。
  • 特征：数据抽象、数据封装

数据的逻辑结构：描述数据元素之间的逻辑关系。四种基本结构：集合结构、线性结构、树结构、图结构

  • 集合结构：数据元素之间没有明显关系
  • 线性结构：数据元素之间存在着一对一的关系。如超市的商品，以表的形式存储
  • 非线性结构：
  • 树型结构：存在一对多的关系。如：家谱、人机对弈、文件存储
  • 图状结构（或网状结构）：存在多对多的任意关系。如：图问题、交通问题 数据的存储结构：是逻辑结构在计算机中的实现，它包含元素的表示和关系的表示。
  • 元素的表示：用若干个二进制“位串”表示
  • 关系的表示：顺序映像、非顺序映像(不是紧凑、非紧凑) 运算集合：在计算机中进行运算操作的集合。增删改查 数据结构（Data Structure）:按某种逻辑关系组织起来的一批数据，按一定映象方式把他们存放在计算机存储器中，并在这些数据上定义了一个运算的集合。（数据结构包括数据的逻辑结构、存储结构以及相关运算。） 数据结构是计算机上存储、组织和运算数据的学科。

算法：Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. 特征： 有限性；确定性；无二义性；输入或输出；可行性 特征：正确性、可读性、健壮性；高效率、低存储 性能评价：

  • 时间复杂度：时间复杂度详解
  • 一个算法中语句的执行条目总数称之为语句频度（时间频度）。
  • 如果程序的代码量非常庞大，用时间频度进行评估十分的麻烦。因此，我们对于时间频度进行简化得出一个简化后的估算值，即为时间复杂度。算法的时间复杂度取决于问题的规模以及待处理数据的初态。
  • 时间复杂度是衡量原操作的语句频度。T(n)=O(f(n)); O(1)常量阶；O(n)线性阶；O(n^2)平方阶; O(n^3);指数型；对数性
  • 若设计出了某种时间复杂度的算法，那么它只适用于给定规模的问题，否则就会超时。某算法的时间复杂度是O(n^2)，表明该算法的A.执行时间与n^2成正比。
  • 空间复杂度 | 排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 | | ---- | ---- | ---- | ---- | ---- | ---- | | 冒泡 | \(O(n^2)\) | \(O(n^2)\) | 稳定 | \(O(1)\) | n小时较好 | | 交换 | \(O(n^2)\) | \(O(n^2)\) | 不稳定 | \(O(1)\) | n小时较好 | | 选择 | \(O(n^2)\) | \(O(n^2)\) | 不稳定 | \(O(1)\) | n小时较好 | | 插入 | \(O(n^2)\) | \(O(n^2)\) | 稳定 | \(O(1)\) | 大部分已排序时较好 | | 基数 | \(O(\log_R B)\) | \(O(\log_R B)\) | 稳定 | \(O(n)\) | B是真值(0-9)，R是基数(个十百) | | Shell | \(O(n\log n)\) | \(O(n^s) \quad 1<2\) | 不稳定 | \(O(1)\) | s是所选分组 | | 快速 | \(O(n\log n)\) | \(O(n^2)\) | 不稳定 | \(O(n\log n)\) | n大时较好 | | 归并 | \(O(n\log n)\) | \(O(n\log n)\) | 稳定 | \(O(1)\) | n大时较好 | | 堆 | \(O(n\log n)\) | \(O(n\log n)\) | 不稳定 | \(O(1)\) | n大时较好 |

一、decltype(C++11)

C 语言中文网 decltype

常与 auto 一起用于模板并作为返回类型。常与 using 一起用于定义类型。

  • 如果 exp 是一个不被括号( )包围的表达式，或者是一个类成员访问表达式，或者是一个单独的变量，那么 decltype(exp) 的类型就和 exp 一致，这是最普遍最常见的情况。 （注：const和& &&原封不动，而static不保留）
  • 如果 exp 是函数调用，那么 decltype(exp) 的类型就和函数返回值的类型一致。但函数不能是重载对象。
  • 如果 exp 是一个左值，且被括号( )包围，那么 decltype(exp) 的类型就是 exp 的引用。

cpp_3-数据结构_260718_005953.png

特例：i++ 是右值(纯右值 prvalue)，++i 是左值(lvalue)。 对 decltype(i++) 到底得到什么？答案是 普通类型 int，不是 int&&——"传入右值就产生右值引用"是误记。decltype 看的是表达式的值类别(value category)，三类对应三类结果：

表达式 e 的值类别 例子 decltype(e)
纯右值 prvalue i++、字面量 42、i+j 普通 T
亡值 xvalue std::move(x)、static_cast(x) T&&
左值 lvalue (i)(带括号)、++i、*p、arr[0] T&

所以 decltype(i++) 是 int，decltype(++i) 是 int&，decltype(std::move(i)) 才是 int&&。

标准与实现

decltype 的值类别规则是 C++ 标准良定义的（[dcl.type.decltype]），不是实现定义、不依赖 ABI，三大编译器(GCC/Clang/MSVC)行为完全一致。C++17 起术语从"lvalue/xvalue/prvalue"统一为值类别三分类，规则本身自 C++11 即定型。

二、auto

StackOverflow: What does auto&& tell us?

By using auto&& var = <initializer> you are saying: I will accept any initializer regardless of whether it is an lvalue or rvalue expression and I will preserve its constness. As an example, imagine that you want to get a std::vector, take an iterator to its first element and modify the value pointed to by that iterator in some way:

auto&& vec = some_expression_that_may_be_rvalue_or_lvalue;
auto i = std::begin(vec);
(*i)++;

This code will compile just fine regardless of the initializer expression. The alternatives to auto&& fail in the following ways:

auto         => will copy the vector, but we wanted a reference
auto&        => will only bind to modifiable lvalues
const auto&  => will bind to anything but make it const, giving us const_iterator
const auto&& => will bind only to rvalues

标准与实现

auto&& 在模板/auto 语境下成为万能引用(forwarding reference)，配合引用折叠(reference collapsing)实现转发——这是 C++ 标准良定义的（[temp.deduct.call]），与 ABI 无关：T& &、T& &&、T&& & 三者折叠为 T&，仅 T&& && 保持 T&&。三大编译器实现一致。

三、作用域

::i 表示直接引用全局作用域中的变量 i（:: 是 C++ 标准定义的作用域解析运算符；前缀无命名空间时指向全局作用域）。若局部作用域中已存在同名 i，加 :: 前缀可强制访问全局版本，避免被局部变量遮蔽。

四、线性表

线性表（Linear List）是由N个相同类型的数据元素组成的有序序列。数据元素之间是一对一的关系，即每个数据元素最多有一个前驱和一个后继。 特点：同一，有穷，有序 基本操作：查找，插入，删除 线性存储的线性表为顺序表。

采用链式存储结构的线性表称为链表。 连接方式分为：单链表，双向链表，循环链表 实现方式：静态链表，动态链表

  • 对于单链表而言，头指针和头结点哪一个是必须的？：头指针和头结点不同，头结点即第一个结点，头指针是指向第一个结点的指针。
  • 在单循环链表中设置尾指针比设置头指针更好

栈：作为一种限定线性表，是将线性表的插入和删除运算限定为仅在表的一端进行。表中允许插入和删除的一端称为栈顶，表的另一端被称为栈底。 双端栈：可让多个栈共享一个足够大的数组空间，通过利用栈的动态特性来使其存储空间互相补充，这就是多栈的共享技术。