datetime:2022-04-09 17:46
author:nzb
数据结构与算法
绪论
基本概念
数据
数据元素、数据项
数据对象、数据结构
数据类型、抽象数据类型（ADT）
数据结构三要素
逻辑结构
集合
线性结构
树形结构
图状结构（网状结构）
物理结构（存储结构）
顺序存储
物理内存中是连续的非顺序存储
物理内存中是分散的链式存储
索引存储
散列存储
数据的运算
学习建议
- 概念多，比较无聊。抓大放小，重要的是形成框架，不必纠结细节概念。
栈（Stack）
定义
一种操作受限的线性表，只能在栈顶插入、删除
特性：后进先出（FIFO）
术语：栈顶、栈底、空栈
基本操作
创、销
增、删（元素进栈、出栈，只能在栈顶操作）
增
删
查（获得栈顶元素，但不删除）
判空
S.top = -1 栈顶指针为-1
顺序栈
顺序存储
用静态数组实现 ，并需要记录栈顶指针基本操作
- 创、增、删、查
- 销：清空、回收 只需要 top = -1
- 都是 O(1) 时间复杂度
两种实现
初始化 top = -1
指向栈顶元素入栈
- S.data[++S.top] = x
- 是先栈顶指针加一后赋值，不能先赋值在加一，这样会覆盖元素
出栈
- x = S.data[S.top--]
- 是先赋值后栈顶指针减一
获得栈顶元素
x = S.data[S.top]栈空/满栈条件？
到达栈顶：s.top = MaxSize -1
初始化 top = 0
指向栈顶元素的后一位，接下来可以插入元素的位置入栈
- S.data[S.top++] = x
- 先赋值在加一
出栈
- x = S.data[--S.top]]
- 是先栈顶指针减一后赋值
获得栈顶元素
x = S.data[S.top-1]栈空/满栈条件？
到达栈顶：s.top = MaxSize
共享栈
两个栈共享同一片内存空间，两个栈从两边往中间增长
初始化
0 号栈栈顶指针初始时 top0 = -1；1 号栈栈顶指针初始时 top1 = MaxSize栈满条件
top0 + 1 = top1
链栈
跟单链表类似，只是只能在头部操作用链式方式实现的栈
两种实现方式
带头结点
不带头结点（推荐）
基本操作
创（初始化）
增（进栈）
删（出栈）
查（获取栈顶元素）
如何判空、判满？
栈的应用
括号匹配
依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配
匹配失败情况
左括号单身
栈非空右括号单身
栈已空左右括号不匹配
表达式求值
概念
运算符、操作数、界限符三种表达式
中缀表达式（人算）
运算符在操作数中间后缀表达式（机算，常用）
运算符在操作数后面 一个中缀表达式可以对应多个后缀、前缀表达式前缀表达式（机算，不常用）
运算符在操作数前面
后缀表达式
中缀转后缀
按“左优先”原则确定运算符的运算次序
一个中缀表达式只对应一个后缀表达式（确保算法的“确定性”）根据上面确定的次序，依次将各个运算符和与之相邻的两个操作数按 <左操作数 右操作数 运算符> 的规则合体
后缀转中缀
从左往右扫描，每遇到一个运算符，就 将 <左操作数 右操作数 运算符>变为 (左操作数 运算符 右操作数)的形式计算
从左往右扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈（注意：先弹出的元素是“右操作数”）
前缀表达式
中缀转前缀
按“右优先”原则确定运算符的运算次序
根据上面确定的次序，依次将各个运算符和与之相邻的两个操作数按 < 运算符 左操作数 右操作数> 的规则合体
计算
从右往左扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈（注意：先弹出的元素是“左操作数”）
递归
栈中的每一个元素对应内存中的一块区域里面的数据不跟其他元素冲突
