前言
在学习专业知识的过程中,我们经常看到两个词一起出现,数据结构和算法,为什么呢?因为通常选择正确的数据结构往往能够让我们程序算法 的效率变得更好。
- 解决问题方法的效率,跟数据的组织方式是相关联的。例如在线性表中删除一个数,选择顺序表(数组),时间复杂度是O(N),而用链表删除一个数是比顺序表的效率要更高的。
- 解决问题方法的效率,跟空间的利用效率也是有关系的。
- 解决问题方法的效率,跟算法的巧妙程度有关。
抽象数据结构(Abstract Data Type)
数据类型
- 数据对象集(有那些东西)
- 数据集合相关联的操作集
抽象
- 与存放数据的机器无关
- 与数据存储的物理结构无关
- 与实现操作的算法和编程语言无关
算法
- 一个有限的指令集
- 接受一些输入(可以没有输入)
- 最少要有一个输出
- 一定是在有限步骤之后终止
- 每一条指令必须
- 有充分明确的目标,不可以有歧义
- 计算机能处理的范围
- 描述不应该依赖于任何一种计算机语言以及具体的实现手段
描述一个算法的好坏,有两个指标,时间复杂度和空间复杂度。
时间复杂度T(n)------------根据算法写成的程序在执行时耗费时间的长度
空间复杂度S(n)------------占用存储单元的长度
线性表
线性表的实现有两种,一种是顺序存储和链式存储。
堆栈
堆栈是一个具有一定操作约束的线性表,只能在一段(栈顶,top)做插入和删除
堆栈的应用
表达式求值,把中缀表达式转换成后缀表达式
函数的递归调用
深度优先搜索
回溯算法