1数据结构绪论
概念和术语:
- 数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型,还包括字符及声音、图像、视频等非数值类型。
- 数据元素:是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理。比如在人类中,人就是数据元素
- 数据项:一个数据元素可以由若干个数据项组成。人都有姓名、生日、性别等相同的数据项
- 数据对象:是性质相同的数据元素的集合,是数据的子集。
- 数据结构: 结构是指各个组成部分相互搭配和排列的方式。结构就是关系,比如分子结构,就是说组成分子的原子之间的排列方式
逻辑结构:
- 集合结构
- 线性结构
- 树形结构
- 图形结构
2 算法
算法效率的度量方法:
- 事前分析估算方法:大O时间复杂度分析
- 事后统计方法:批量数据测试
常见的时间复杂度:
- 常数阶 O(n)
- 对数阶 O(logn)
- 线性阶 O(n)
- 常数对数阶(n * logn)
- 平方阶 O(n^2)
- O(2^n)
- O(n!)
- O(n^n)
3 线性表
image.png4 栈与队列
- 顺序栈
- 两栈共享存储空间
- 链栈
栈的应用:
- 递归
- 四则运算表达式求值
- 后缀表达式
- 中缀表达式
网友评论