线性表：插入、删除、查找
链表：插入、删除、查找
栈：压栈、出栈、读栈、顺序栈和链式栈、表达式求值和转换
队列：队列操作、顺序和链式、循环队列、优先队列、
字符串：C++内置函数、基本操作、模式匹配、KMP
数组：多维数组、对称/对角/稀疏矩阵的压缩存储、稀疏矩阵快速转置、十字链表、广义表

稀疏矩阵快速转置

首先将稀疏矩阵转换为三元组表 $(i, j, val)$，并先按行后按列排序。

假设行数为 $N$，列数为 $M$，非零元素数为 $A$。

暴力转置算法：每次对于相同的列 $j$，添加相同列下标的三元组 $(i, j, val) \to (j, i, val)$.

时间复杂度为 $O(MA)$.

基于计数排序的转置算法：建立大小为 $M$ 的桶 $c_{1}, c_2, \cdots, c_M$ 记录每列非零元素，做前缀和后，就得到每列元素的首个位置。从前往后考虑每个 $(i, j, val)$ 并自增 $c_j$ 可以得到它们的位置。

十字链表

十字链表是稀疏矩阵的一种表示方式，每个节点表示一个非零元素，记录 $(i,j, val, down, right)$

$down$ 记录同一列且行数比它大且最近的非零元素的指针，若没有则为空指针（或者指向对应的列指针，构成循环链表）。
$right$ 记录同一行且列数比它大且最近的非零元素的指针，若没有则为空指针（或者指向对应的行指针，构成循环链表）。同时还要建立头指针 $(rn, cn, tn, *rhead, *chead)$
$rn$ 表示行数，$cn$ 表示列数，$tn$ 表示非零元素总数
$*rhead$ 表示每行最靠左的节点，$*chead$ 表示每列最靠上的节点

广义表中，表中的元素可以是表，形成复杂的图结构（一般是树结构）。