数据结构基本概念和数据结构类型

• 有哪些数据结构
  • 线性表、栈、队列、串、数组、广义表、树、二叉树、图
• 对数据结构实现添加、删除、更新、查询、排序等

数据
数据是描述客观事物的数值，字符以及能输入机器且能被处理的各种符号集合。
数据含义广泛，除了通常的数值数据，字符，字符串是数据以外，声音，图像等一切可以输入计算机并能被处理的都是数据。

数据项
数据项具有原子性，是不可分割的最小数据单元。
如描述学生相关信息的姓名、性别、学号等都是数据项，如红框的

数据元素
数据元素是数据的基本单元，是数据集合的个体，通常有若干个数据项组成，在计算机程序中通常作为一个整体来进行处理。
例如一条描述一位学生的完整信息的数据记录就是一条数据元素，如蓝框

数据对象
数据对象是性质相同的数据元素的集合，是数据的子集。
例如一个学校所有的学生的集合就是数据对象，如黄框

数据结构
是相互之间存在一种或多种特定关系的数据元素的集合。

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

数据的逻辑结构

• 线性结构与非线性结构
  • 线性结构：有且只有一个节点和一个终端节点，并且所有节点都最多只有一个直接前驱和一个直接后继。
  • 线性表是典型的线性结构，其基本特征：
    （1）集合中必存在卫衣的一个 第一个元素
    （2）集合中必存在唯一的一个 最后的元素
    （3）除最后元素外，其他数据元素有唯一的 后继
    （4）除第一元素外，其他数据元素有唯一的 前驱
    
• 相对于非线性结构，就是一个节点元素可能对应多个直接前驱和多个后继。
• 常见的有：树，图
  
• 集合结构 线性结构 树状结构 网状结构
  • 表和树是最常用的两种高效的数据结构
  • 集合结构：就是数学中的集合
    • 确定性
    • 唯一性
    • 无序性
    • 数据元素之间关系很弱
  • 线性结构：数据元素之间一对一关系
  • 树状结构：数据元素之间一对多关系
  • 网状结构：数据元素之间多对多关系

数据的存储结构

• 数据的存储结构主要包括数据元素本身的寻相互以及数据元素关系的表示，是数据的逻辑结构在计算机中的表示
• 常见的存储结构有顺序存储、链式存储、索引存储以及散列存储。

顺序存储结构

• 把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，节点之间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储结构为顺序存储结构。
• 优点：节省存储空间，分配给数据的存储单元存放节点的数据，节点之间的逻辑关系没有占用额外的存储空间。
• 缺点：插入和删除元素需要移动元素，效率低下。

链式存储结构

• 数据元素的存储对应的不是连续的空间，每一个节点对应一个需要存储的数据元素，每个节点由数据域和指针域组成，元素之间的逻辑关系通过指针域反映。
• 特点：
  • 比顺序存储结构的存储密度小
  • 逻辑上相邻的节点物理上不必相邻
  • 插入和删除灵活
  • 查找节点时链式存储较慢
    

索引存储结构

• 除建立存储节点信息外，还建立附加的索引来标识节点的位置，比如图书字典的目录
  散列存储结构
• 根据节点的关键字直接计算除该节点的存储位置，添加，查询极快