数据结构

1.数据结构的概念

数据:数据就是计算机中存储的一切信息， 无论是一个商品的价格、种类、尺寸, 还是一个用户的账号、密码、昵称、年龄, 都能称之为数据

结构:事物和事物之间的关系, 就是结构. 以现实生活中举例, 一趟火车中, 车厢和车厢之间的关系; 一个公司中, 员工和员工之间, 员工和领导之间, 员工和部门之间的关系, 这些都可以成为结构

数据结构:数据结构简而言之就是数据和数据之间的关系

2.常见的数据结构

在计算机中, 最常见的数据结构有栈、队列、链表、树
2.1 栈

栈也是一种线性表，属于顺序存储，但是先进后出、后进先出，就像子弹夹一样。栈结构只能在一端（尾部）进行数据的插入和删除，插入也叫进栈或压栈，删除也叫出栈或弹栈。

现实生活中,有很多使用栈结构的例子:

比如说浏览器的”后退”功能,如果打开多个页面再点击后退,那么第一次打开的页面将会最后才能看到.

再比如说, 如果我们要往一个箱子里面放满东西, 那么最开始放的东西肯定在箱子最底下, 当我们要往外取的时候, 最开始取到的是最后放上去的东西.

2.2 队列:

队列这种结构见名知意, 就像生活中排队一样, 比如说排队买票, 最先开始排队的人会第一个买到,排在队伍末尾的人最后一个买到.

2.3 链表:

(1) 链表简述

如果把每个存储数据的空间分割成两个部分，一部分用于存储正常的数据， 另一部分存储的是下一个空间的位置， 这样的形式就是链表。

概念上理解比较抽象，下面的图比较直观

链表结构是数据结构中非常常见也非常重要的结构!

2.3.2链表分类

A.单向链表

单向链表就是每个节点只记录自身数据和下一个节点的位置, 如下图所示

B.双向链表

双向链表将每个节点的空间划分为三个部分， 一部分用来存储数据， 一部分用来存储该节点前一个节点的位置，一部分用来存储该节点后一个节点的位置

C.循环链表

循环链表就是链表的最后一个节点指向该链表的首节点,这样就形成了一个循环链表

2.4 树:

树的结构和链表很相似, 区别在于链表大多是一个节点关联一个节点, 而树是一个节点关联零个或多个节点, 如下图所示

2.4.1 树结构涉及的术语

(1)父节点与子节点:

父节点和子节点是相对的, 如上图所示, A节点就是B节点和C节点的父节点, 而B和C是A节点的子节点,

同样而言, B节点是D节点和E节点的父节点, 而D节点和E节点是B节点的子节点

(2)根节点:

当一个节点没有任何父节点的时候, 这个节点通常称之为根节点, 通常根节点是唯一的, 如上图中,A节点就是根节点

(3)高度

如下图所示, h就是树的高度, 为3. 也就是这个树总共有多少层,一般情况下,高度是从下往上数,

(4)深度

深度一般是从上往下数, 比如图上的B节点, 深度就是2, 也就是从根节点(根节点为1)往下数到当前节点的位置

2.4.2 树的常见种类

   常见的树结构中, 有平衡二叉树, 红黑树, B-树(这个就是B树, B-Tree,不念B减, 也不念B杠), B+树(Mysql就是基于B+树的查找), 后续会对其一一进行解释

数据结构

1.数据结构的概念

数据:数据就是计算机中存储的一切信息， 无论是一个商品的价格、种类、尺寸, 还是一个用户的账号、密码、昵称、年龄, 都能称之为数据

结构:事物和事物之间的关系, 就是结构. 以现实生活中举例, 一趟火车中, 车厢和车厢之间的关系; 一个公司中, 员工和员工之间, 员工和领导之间, 员工和部门之间的关系, 这些都可以成为结构

数据结构:数据结构简而言之就是数据和数据之间的关系

2.常见的数据结构

在计算机中, 最常见的数据结构有栈、队列、链表、树
2.1 栈

栈也是一种线性表，属于顺序存储，但是先进后出、后进先出，就像子弹夹一样。栈结构只能在一端（尾部）进行数据的插入和删除，插入也叫进栈或压栈，删除也叫出栈或弹栈。

现实生活中,有很多使用栈结构的例子:

比如说浏览器的”后退”功能,如果打开多个页面再点击后退,那么第一次打开的页面将会最后才能看到.

再比如说, 如果我们要往一个箱子里面放满东西, 那么最开始放的东西肯定在箱子最底下, 当我们要往外取的时候, 最开始取到的是最后放上去的东西.

2.2 队列:

队列这种结构见名知意, 就像生活中排队一样, 比如说排队买票, 最先开始排队的人会第一个买到,排在队伍末尾的人最后一个买到.

2.3 链表:

(1) 链表简述

如果把每个存储数据的空间分割成两个部分，一部分用于存储正常的数据， 另一部分存储的是下一个空间的位置， 这样的形式就是链表。

概念上理解比较抽象，下面的图比较直观

链表结构是数据结构中非常常见也非常重要的结构!

2.3.2链表分类

A.单向链表

单向链表就是每个节点只记录自身数据和下一个节点的位置, 如下图所示

B.双向链表

双向链表将每个节点的空间划分为三个部分， 一部分用来存储数据， 一部分用来存储该节点前一个节点的位置，一部分用来存储该节点后一个节点的位置

C.循环链表

循环链表就是链表的最后一个节点指向该链表的首节点,这样就形成了一个循环链表

2.4 树:

树的结构和链表很相似, 区别在于链表大多是一个节点关联一个节点, 而树是一个节点关联零个或多个节点, 如下图所示

2.4.1 树结构涉及的术语

(1)父节点与子节点:

父节点和子节点是相对的, 如上图所示, A节点就是B节点和C节点的父节点, 而B和C是A节点的子节点,

同样而言, B节点是D节点和E节点的父节点, 而D节点和E节点是B节点的子节点

(2)根节点:

当一个节点没有任何父节点的时候, 这个节点通常称之为根节点, 通常根节点是唯一的, 如上图中,A节点就是根节点

(3)高度

如下图所示, h就是树的高度, 为3. 也就是这个树总共有多少层,一般情况下,高度是从下往上数,

(4)深度

深度一般是从上往下数, 比如图上的B节点, 深度就是2, 也就是从根节点(根节点为1)往下数到当前节点的位置

2.4.2 树的常见种类

   常见的树结构中, 有平衡二叉树, 红黑树, B-树(这个就是B树, B-Tree,不念B减, 也不念B杠), B+树(Mysql就是基于B+树的查找), 后续会对其一一进行解释