数据结构概述

目录

• 数据结构
  • 定义
  • 逻辑结构
  • 物理结构
• 算法
  • 定义
  • 时间复杂度
• 线性表
  • 定义
  • 单链表和顺序数组的效率
  • 单链表设头结点的目的
  • 其他链表
• 栈和队列
  • 栈
  • 队列
  • 链栈和顺序栈的适用情况
  • 计算机处理中缀表达式

数据结构

定义

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

逻辑结构

• 集合结构
• 线性结构
• 树形结构
• 图形结构

物理结构

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

算法

定义

解决特定问题求解步骤的描述

时间复杂度

一般在没有特殊说明的情况下，都是指最坏的时间复杂度

线性表

定义

零个或多个数据元素的有限序列

单链表和顺序数组的效率

对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显

单链表设头结点的目的

使空链表与非空链表处理一致

其他链表

双向链表：用空间换取时间

栈和队列

栈

限定仅在表尾进行插入和删除操作的线性表 分为顺序栈和链栈 顺序栈的拓展：两栈共享空间

队列

只允许在一端进行插入操作，而在另一端进行删除操作 分为顺序队列和链队列 顺序队列的拓展：循环队列

链栈和顺序栈的适用情况

选择链栈：如果栈的使用过程中元素变化不可预料，有时很小，有时非常大。 选择顺序栈：它的变化在可控范围内

计算机处理中缀表达式

• 将中缀表达式转化为后缀表达式
• 将后缀表达式进行运算得出结果