本文最后更新于 1843 天前，其中的信息可能已经有所发展或是发生改变。

ADT（抽象数据类型）

包含

{
数据对象：（数据元素集合）
数据关系：（数据关系二元组结合）
基本操作：（操作函数的罗列）
}

ADT在设计的时候，并不关心操作对象的数据具体是什么类型的，只要求他拥有ADT最基本的三元素即可

线性结构

多项式：

多项式的包含的变量包括自变量的系数和指数，因此只需存储（用链表或数组）自变量的系数和指数就能表示整个多项式了。但是这只能满足仅有一种变量的多项式（例如只有x），如果表示一个多项式要含X，Y，Z甚至更多变量，可以使用广义表的形式。

广义表：

对于一般的线性表而言，它的所含元素是基本的单元素，但是广义表的元素也可以是另一个广义表。

多重链表：

如果一个链表的指针域包含多个指针，那么就说这个链表是多重链表。广义表也是一种多重链表，但是双向链表不是多重链表，因为双向链表的两个指针均是指向一个链表。

对于一个“稀疏矩阵”（即大部分数据为零），可以用一个十字链表只存储非零元素来节省空间占用。

十字链表：

十字链表通过两个指针域连接起来，其中包括一个行指针（指向右边元素）和一个列指针（指向下面元素）。用十字链表来存储稀疏矩阵，它的每个节点的数据域需要有一个行坐标和一个列坐标以及数据。它还需要一个头节点来保存矩阵大小和节点数量。

二叉树是一个包含两个指针域和一个数据域的结构，二叉树还分为：满二叉树和完全二叉树

满二叉树：

定义：每一层的节点数都达到的最大值的树称为满二叉树。

满二叉树层数为K，且结点总数是(2^k) -1 。

完全二叉树：

定义：一个树中的节点按照从左到右从上到下标号，在顺序上和满二叉树完全一致（但节点数不一定一致），即完全二叉树是满二叉树取掉“最后”几个元素而形成的。

二叉树遍历：

有三种遍历法，分别是：先序遍历、中序遍历、后序遍历和层序遍历。

先序遍历的顺序是根 左右

中序遍历的顺序是 左根右

后序遍历的顺序是 左右根

层序遍历的顺序是 从左到右，从上到下

层序遍历可以通过队列方式遍历整棵二叉树。

已知中序遍历序列和先序或后序遍历的序列即可推算出整个二叉树的结构。

平衡二叉树(AVL):

一个二叉树的每个节点的左子树和右子树的高度相差不超过2，那么这个二叉树就叫做平衡二叉树（AVL树） ，它的最大高度为 log2 n（n为节点数量）。