算法、数据结构、线性结构、栈、队列

算法

1.算法的基本特征

• 可行性
  • 步骤实现，执行结果达到预期
    • 确定性
  • 步骤明确
    • 有穷性
  • 有限的时间完成
    • 拥有足够的情报
  • 拥有足够的输入信息和初始化信息

2.算法的复杂度

• 时间复杂度
  • 执行算法所需要的计算工作量
• 空间复杂度
  • 执行算法所需要的内存空间

数据结构

1. 定义：有关联的数据元素的集合就是数据结构。

• 数据结构的概念
  • 根节点
    • 没有前件的节点
  • 终端节点
    • 没有后件的节点
  • 内部节点
    • 除了根节点和终端节点以外的节点

线性结构与非线性结构

1.线性结构

• 有且只有一个根节点
• 每个节点最多只有一个前件，也最多只有一个后件

2.非线性结构：不满足线性结构的两个条件就是非线性结构

• 树形结构
• 网状结构

线性表

1.线性结构也被称为线性表

2.非空线性表

• 只有一个根节点
• 有且只有一个终端节点
• 除根节点与终端节点外，其他所有节点有且只有一个前件，也有且只有一个后件

线性表的顺序存储

1.定义：线性表的顺序存储是将线性表中的元素一个接一个地存储在一片相邻的存储区域中，这种线性表也叫顺序表

2.顺序表特征

• 线性表中所有元素所占的存储空间是连续的
• 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的

栈

1.定义：栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。当栈中没有元素时，称为空栈。

2.栈的修改原则是后进先出或先进后出

3.栈的基本运算： 入栈、退栈、读栈顶元素

队列

1.定义：允许在一端进行插入，而在另一端进行删除的线性表

2.允许进行删除运算的一端称为队头，允许进行插入运算的一端称为队尾

顺序表和链表的对比

1.顺序表

• 优点
  • 可随机存取表中的任意节点
  • 无需为表示节点间的逻辑关系额外增加存储空间
• 缺点
  • 顺序表的插入和删除运算效率很低
  • 顺序表的存储空间不便扩充
  • 顺序表不便于对存储空间的动态分配

2.链表

• 优点
  • 在进行插入和删除运算时，只需要改变指针即可，不需要移动元素
  • 链表的存储空间易于扩充并且方便空间的动态分配

• 缺点

  • 需要额外的空间来表示数据元素之间的逻辑关系，存储密度比顺序表低

• 链表类型

  • 单向链表
    • 链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始，链表是使用指针进行构造的列表；又称为结点列表
    • 单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小
    • 结点的删除非常方便，不需要像线性结构那样移动剩下的数据
    • 结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表

  • 双向链表

    • 每个数据结点中都有两个指针，分别指向直接后继和直接前驱。双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点

  • 环形链表

    • 最后一个结点指向头结点，形成一个环。从循环链表中的任何一个结点出发都能找到任何其他结点