1.数据结构基础

数据结构概念：

是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：Data_Structure=(D,R)
其中 D 是数据元素的集合，R 是该集合中所有元素之间的关系的有限集合。

数据的逻辑结构：

指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。逻辑结构包括：

1.集合
数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系

2.线性结构
数据结构中的元素存在一对一的相互关系

3.树形结构
数据结构中的元素存在一对多的相互关系

4.图形结构
数据结构中的元素存在多对多的相互关系

数据结构的存储方式（物理结构）：

顺序存储结构：

用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构（关系），数据元素存放的地址是连续的

链式存储结构：

在每一个数据元素中增加一个存放另一个元素地址的指针，用该指针来表示数据元素之间的逻辑结构，数据元素存放的地址是是否连续没有要求

空间复杂度：

空间复杂度(Space Complexity) 是对一个算法在运行过程中临时占用存储空间大小的量度，记做 S(n)=O(f(n))。

该存储空间一般包括三个方面
1.指令常数变量所占用的存储空间
2.输入数据所占用的存储空间
3.辅助（存储）空间

一般地，算法的空间复杂度指的是辅助空间
一维数组 a[n] :空间复杂度 O(n)
二维数组 a[n][m] :空间复杂度 O(n*m)

2.栈和队列

栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出或先进后出的线性表

栈顶： 允许进行插入、删除操作的一端，又称为表尾
栈底： 是固定端，又称为表头
   栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈
   根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈
   栈的链式存储结构称为链栈，是运算受限的单链表

队列：也是运算受限的线性表，是一种先进先出先性表

例如：排队购物

3.线性表基础

线性表表示一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。

在这种结构中：
  一、存在一个唯一的被称为“第一个”的数据元素
  二、存在一个唯一的被称为“最后一个的数据元素
  三、除第一个元素外，每个元素均有唯一一个直接前驱
  四、除最后一个元素外，每个元素均有唯一一个直接后继

线性表的顺序存储

顺序存储：把线性表的结点按逻辑结构依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表

线性表的链式存储

链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表
参考： (opens new window)
链表是通过每个节点的指针域将线性表的 n 个结点按其逻辑次序链接在一起的
链表类型：

单链表是只包含指向下一个节点的指针，只能单向遍历。
双链表即包含指向下一个节点的指针，也包含指向前一个节点的指针，因此可以双向遍历。
循环单链表则是将尾节点与首节点链接起来，形成了一个环状结构，在某些情况下会非常有用。
还有循环双链表，与循环单链表类似。

4.前、中、后缀表达式

概念, 前缀表达式, 前缀记法, 中缀表达式, 中缀记法, 波兰式, 后缀表达式, 后缀记法, 逆波兰式

它们之间的区别在于运算符相对与操作数的位置不同
前缀表达式基本没有在商业计算机中使用过，所以现实中用的更多的是后缀表达式。
参考 (opens new window)

举例：

(3 + 4) × 5 - 6 就是中缀表达式

- × + 3 4 5 6 前缀表达式

3 4 + 5 × 6 - 后缀表达式

中缀表达式（中缀记法）中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。
中缀表达式是人们常用的算术表示方法。

虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。