数据结构是指数据元互的集合, 及元素间的相互关系和构造方法. 元素之间的相互关系是数据的逻辑结构, 数据及元素之间关系的存储形式称为存储结构.

• 逻辑结构:元素之间的相互关系
• 存储结构:元素存储和相互关系的存储

线性表

逻辑结构: 数据元素之间呈现一种线性关系, 即"一个接一个地排列"
存储结构:顺序存储和链式存储

栈和队列

逻辑结构: 栈和队列罗逻辑结构和线性表相同

栈

栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构.
特点: 后进先出(Last In First Out, LIFO)

队列

队列是一种先进先出的线性表, 它只允许在表的一端插入元素, 而表的另一端删除元素.

tips:在队列中, 允许插入元素的一端称为队尾, 允许删除元素的一端为队头.

串

串是仅由字符构成的有限序列, 是聚会范围受限的线性表.

tips: 一般记为 S=a1a2a3...an'

数组

数组是定长线性表在维数的扩张, 即线性表中的元素又是一个线性表.
特点:

1. 数据元素固定
2. 数据元素具有相同的数据类型
3. 数据元素的下标关系具有上下界的约束且下标有序

tips: 基于上述特点, 数据适合顺序存储

广义表

广义表是线性表的推广, 是由 0 个或多个单元素或子表组成的有限序列.

树

树是 n(n>=0)个结点的有限集合, 当 n=0 时称为空树.在任何一非空树(n>0)中, 有且仅有一个称为根的结点.
树的定义是递归的, 它表明了树本身固有的特性, 也就是一棵树由若干个子树构成, 而子树又由更小的子树构成.

二叉树

二叉树中的结点的子树要区分左子树和右子树, 即二叉树最大度为 2.

1. 二叉树的性质

   • 结点数
   • 满二叉树

2. 存储结构

   • 完全二叉树用顺序存储
   • 也可以用链式存储(三叉链表, 二叉链表)

二叉树的遍历

二叉树的遍历是按某种策略访问树中的每个结点, 且仅访问一次的过程.
按照先遍历左子树后遍历右子树的编写, 根据访问根结点位置的不同, 可得到二叉树的先序,中序和后序三种遍历方法.

1. 先序遍历: 根结点->左孩子->右孩子
2. 中序遍历: 左孩子->根结点->右孩子
3. 后序遍历: 左孩子->右孩子->根结点