数据结构 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+树的查找), 后续会对其一一进行解释
|