# 基本的数据结构

# 认识数据结构

数据结构起源于程序设计，是用计算机来存储、组织数据的方式。数据结构不是使我们学会编码，而是为我们提供一种编程的思想，具有更好的思路。

关于数据结构有两种说法，如下：

数据结构与算法是相互依托的关系。计算机解决问题，应该是先从具体问题中抽象出一个适当的数据模型，设计出一个解此数据模型的算法：

它们之间的关系就像下图一样：

算法的几个基本概念

数据元素相互之间的关系称为结构。数据结构是与算法紧密结合的。

数据结构分类

数据结构与算法体系图

基本的逻辑结构

数据结构中的集合关系就类似于数学中的集合。

线性结构中的数据元素之间是一对一的关系。也就是数据元素一个接一个地排列。

栈是一种被限制操作的线性表。栈是一种先进后出 LIFO(Last In First Out) 的数据结构。(桶装的薯片是现实中一个最简单的栈结构))

队列是一种被限制操作的线性表。队列是一种先进先出 FIFO(First In First Out) 的数据结构。(我们在吃自助的时候,放冰淇凌筒的那个管子就是一种队列,只能从上往下走)

也有一些特殊的队列，比如生活中在车站买票的时候有军人优先，这就是优先队列；事件循环机制是一种环形队列；

树是由若干个有限节点组成的一个具有层次关系的集合。我们把它叫做“树”是因为它看起来像一棵倒挂的树。树是基本的几种数据结构之一。

以下基本概念不如看图来的简单明了，请优先看图，或在看基本概念的时候请结合上图（树）。

主要基本概念
- 每个元素称为结点(node)
- 有一个特定的结点被称为根结点或树根(root)
- 除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti(1<=i<=m)本身也是一棵树，被称作原树的子树(subtree)
其余基本概念
- 单个结点是一棵树，树根就是该结点本身
- 空集合也是树，称为空树。空树中没有结点
- 一个结点含有的子树的个数称为该结点的度
- 度为0的结点称为叶结点或终端结点
- 度不为0的结点称为非终端结点或分支结点
- 若一个结点含有子结点，则这个结点称为其子结点的父结点
- 一个结点含有的子树的根结点称为该结点的子结点
- 具有相同父结点的结点互称为兄弟结点
- 一棵树中，最大的结点的度称为树的度
- 从根开始定义起，根为第1层，根的子结点为第2层，也叫深1，深2
- 树的高度或深度说的就是树中结点的最大层次
- 从根到该结点所经分支上的所有结点称为该节点的祖先
树的数学基础是:
- 图论
树的特点
- 每个结点有零个或多个子结点；
- 没有父结点的结点称为根结点；
- 每一个非根结点有且只有一个父结点；
- 除了根结点外，每个子结点可以分为多个不相交的子树；
- 一棵树中每两个点之间都有且只有一条路径
- 一颗有N个点的树有N-1条边