PAT 常见数据结构及其表示

特殊格式

时间

通常转化为分钟数或秒数,也可以直接用字符串格式来比较,都是可以的

如果时间需要进行相互之间的运算,可以考虑用同一时间的偏移来表示,比如MM:DD:HH:MM:SS - 01:01:00:00:00,比如不同时间有不同权值,这样计算时会方便很多

多项式

数组表示,下标表示次幂,值表示系数,没有的值按0算

线性结构

链表

多用id - key - next的三元组表示,存储的时候直接开两个大数组,key和next,这样操作就跟普通链表没有什么区别了。

二叉树

根据前中、后中建树,递归实现:

1
Node *build(int posL, int posR, int inL, int inR);

根据 parent-left-right 建树

先开数组存所有节点,再根据关系,确定指针关系

多叉树

二维数组,a[i]表示根节点为i的子节点数组

二维数组

矩阵表示,如果没有权,那么用bool,有权值为权