当前位置：首页 > news >正文

DS | 冲刺阶段考点整理 —— 绪论、线性表、栈与队列、特殊矩阵、串

news 来源：原创 2024/5/5 18:23:33

零、绪论

O(1)< O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

【命题重点】

1、给定代码段，分析算法的时间复杂度。

循环类代码――分析每层循环的循环次数与问题规模n之间的关系，若有多层嵌套循环，则使用乘法规则

递归类代码――分析递归次数与问题规模n之间的关系。若要分析空间复杂度,则应找到递归深度与问题规模n之间的关系。

如：若对一棵n个结点的完全二叉树，进行遍历时，时间复杂度为O(n)，空间复杂度为(logn) 树高。

2、结合算法题考查，分析自己设计的算法的时、空复杂度。

顺序表与链表：

逻辑结构：都是线性表

物理结构:：

顺序表――顺序存储，逻辑上相邻的物理上也相邻【随机存取】

链表――链式存储，逻辑上相邻的物理上可以不相邻，用指针描述逻辑上的前驱后继关系

顺序表的基本操作：创销增删改查

Tips:目前为止，顺序表的算法题只需简单定义一个数组即可，基于数组实现算法

int data [N]; //文字说明数组里存了什么数据，数组长度为N

考察顺序表时，大多数情况下就是在对数组操作

Key：

        基于数组的算法题（保命重点）

        查找――顺序遍历查找、折半查找

        排序――快速排序（不变长)、归并排序（变长)

会用c语言定义链表结点
单链表的遍历
删除某结点插入某结点
用头插法(逆置单链表）

常考题型:输出序列合法性

某个元素出栈时，只要是在其后出栈且早于它进栈的元素，那么这些元素（包括该元素)的出栈顺序与它的进栈顺序相反。

【考点笔记】队列的应用

解决逐行或逐层的问题，如层序遍历二叉树。
解决主机与外部设备之间速度不匹配的问题，如缓冲区。
解决由多用户引起的资源竞争问题，如进程的就绪队列。

【考点笔记】栈的应用

栈在括号匹配的应用
栈在表达式求值的应用
- 三种算数表达式
  - 中缀表达式：运算符在操作数中间
  - 后缀表达式：运算符在操作数后面
  - 前缀表达式：运算符在操作符前面
- 后缀表达式（逆波兰表达式）—— 注意操作数的顺序！
  - 中缀转后缀
    - 运算顺序不唯一，因此对应的后缀表达式也不唯一
    - “左优先”原则：只要左边的运算符能先计算，就优先算左边的
  - 后缀求值
    - 后缀表达式的手算方法
      - 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数。注意：两个操作数的左右顺序。
      - 后缀表达式用栈实现计算
- 前缀表达式（波兰表达式）
  - 中缀转前缀
  - 前缀求值
栈在递归中的应用
- 函数调用时，需要用一个栈存储：①调用返回地址 ②实参 ③局部变量
- 注：理论上所有的递归算法都可以手动建栈，用非递归的方式实现
- 越靠后被调用的函数信息越靠近栈顶，其个函数return后该函数在栈中的信息就会消失。