#常见的麦克劳林公式
数据结构笔记
Posted on
第1章 绪论
###基本概念
元素(结点、顶点、记录)、数据项
元素 + 关系 = 数据结构
数据结构 + 操作 = 抽象数据类型(ADT)
数据域 + 指针域(顺序实现时无)= 结点
逻辑结构
- 集合(查找表)(元素之间没有关系)
- 线性(线性表、栈、队列)(元素之间存在一对一的关系)
- 树形(树、二叉树)(元素之间存在一对多关系)
- 图形(无向图、有向图)(元素之间存在多对多关系)
存储结构
- 顺序(可随机访问,会满)
- 链式(不可随机访问、一般不会满)
算法五大特性:有穷性、确定性、可行性、输入(可以没有)、输出(至少一个)
好算法的目标:正确性、可读性、健壮性(稳健性、鲁棒性)、高效率(时间复杂度、空间复杂度)
###时间复杂度
与程序的具体执行时间有关的因素:P14
$$
常见时间复杂度比较:O(1) < O(logn) < O(\sqrt{n}) < O(n)<O(nlogn)<O(n\sqrt{n})<O(n^2)<O(n^3)<O(2^n)
$$
第2章
概念
线性结构(P18,第1段)、线性表、直接前驱、直接后继、长度、空表、位序
顺序存储结构——顺序表
P22,下面常量与类型定义
P24,算法2.4(插入)与P24-25,算法2.5(删除)T(n)=O(n)
具体移动多少原有元素?平均移动多少原有元素?