数据结构

数据结构简介

• 什么是数据结构？

  • 计算机存储、组织数据的方式
  • 相互之间存在的一种或多种特定关系的数据元素的集合

• 常见的数据结构

  • 线性表(数组、链表、栈、队列)
  • 数
  • 图

• 逻辑结构

  
  Snip20180311_11.png

• 存储结构

  • 顺序存储结构
  • 链式存储结构

  • ...

    
    Snip20180311_12.png

• 数据运算

  • 检索
  • 排序
  • 插入
  • 删除
  • ...

线性表简介：

• 什么是线性表
  • 线性表是n个具有相同特性的数据元素(节点)a1,a2,...an组成的有序序列(n>=0)
  • 当n=0时，成为空表。
  • a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。
  • 当a1,a2,...ai-1都是ai的前驱，其中ai-1是ai的直接前驱。

  • ai+1,ai+2...an是ai的后续，其中ai+1是ai的直接后续。

    
    Snip20180311_13.png

线性表的顺序存储结构

• 用一组地址连续的存储单元依次存储线性表的数据元素 Snip20180311_14.png

• 线性表的常见操作：

  • 创建线性表
  • 销毁线性表
  • 获得线性表的当前长度
  • 获得某个位置的节点数据
  • 设置某个节点位置的节点数据
  • 在某个位置插入节点数据
  • 在最后位置添加节点数据
  • 获得某个节点的索引位置
  • 移除某个位置的节点数据
  • 移除某个节点的数据
  • 清空线性表
  • ...

• 顺序线性表的内存分布

  
  Snip20180311_15.png

• 线性表的链式存储结构

  • 用一组任意的存储单元存储线性表中的数据元素，它的存储单元可以是连续的，也可以是不连续的。

    
    Snip20180311_16.png

• 链式线性表的内存分布

Snip20180311_17.png

• 栈：一种特殊的线性表，后进先出的原则(Last In First Out, LIFO)

• 常见操作：

  • 创建
  • 销毁
  • 清空
  • 压栈
  • 出栈
  • 获得栈顶元素

  • 获得元素数量

    
    Snip20180311_18.png

• 队列：一种特殊的线性表，先进先出的原则(First In First Out, LIFO)

• 常见操作：

  • 创建
  • 销毁
  • 清空
  • 入列
  • 出列
  • 获得头元素
  • 获得元素数量

  • ...

    
    Snip20180311_19.png