数据结构基础

1.概述

  • 存储数据的空间排列
  • 查询数据的操作方式
  • 核心:有效占用空间、查询数据时间

2.数组

  1. 特性

    • 内存中连续存储多个数据
    • 内存空间分配是连续的
  2. 存储

    • 数组长度
    • 索引
  3. CRUD操作

    • 查询:根据数组的首地址,使用索引×单个数据的长度即可得到指定索引的地址
    • 修改:在查询到指定索引的地址即可覆盖重写数据
    • 增加:一旦声明便固定,不可变
    • 删除:需要移位数据,达到内存空间连续
  4. 利弊

    • 利:查询、修改
    • 弊:新增、删除

3.栈

  1. 特性

    • 线性表的实现(一块连续的内存空间)
    • 栈顶允许操作,栈底不允许操作
    • 先进后出,后进先出(手枪弹夹)
  2. 存储

    • 栈顶指针
    • 栈底指针
  3. 操作

    • 快速的加载和读取(删除)数据
    • 数据操作只有一个出入口(栈顶)
  4. 利弊

      • 内部数据一直都是连续的,没有内存碎片,用于方法中局部变量的存储

4.队列-Queue

  1. 特性

    • 线性表的实现
    • 先进先出,后进后出(火车进入隧道)
  2. 存储

    • 队首-前置计数器(front/head)
    • 队尾-后置计数器(tail/rear)
  3. 操作

    • 读取(删除)后,数据内存地址前移
    • 新增,从队尾操作
  4. 利弊

    • 弊:新增、删除后耗费时间
  5. 改进

    • 双向队列,队首队尾相接,解决弊端

5.链表

  1. 特性

    • 非连续、非顺序的存储结构
    • 数据逻辑顺序由指针指向
  2. 类别-根据指针的功能

    • 单向链表
    • 双向链表
    • 循环链表
  3. 存储

    • 头指针-head
    • 下一个数据的指针-next
  4. 利弊

    • 新增、删除快
    • 查询慢

6.二叉树

  1. 特性

    • 每个根节点至多有两节点
    • 左节点小于中间节点
    • 右节点大于中间节点
  2. 存储

    • 根节点
  3. 操作

    • 查询数据从根节点开始
  4. 利弊

    • 利:查询速度快
    • 弊:极端情况,形成单向树结构(链表),影响查询性能
  5. 改进

    • 平衡二叉树
    • 满二叉树
    • 完全二叉树
    • 红黑树

7.散列表

  1. 特性

    • 即哈希表
    • 根据关键码和值(key和value)直接进行访问的数据结构
  2. 存储

    • 底层实现仍旧是数组,单个数组的对象是Entry
    • 数组加链表

8.图

  1. 特性
    • 顶点和边的组合
    • 链表和树,是最简单的图
    • 可以解决更加复杂的交互关系

9.线性表

  • 含义:
    • n个元素的有限序列
  • 包含数组和链表
------ 本文结束感谢您的阅读 ------

本文标题:数据结构基础

文章作者:MangoCheng

发布时间:2020年05月27日 - 11:25:39

最后更新:2020年09月17日 - 19:49:41

原始链接:http://mangocheng.com/posts/79666db.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。