第一章 数据结构绪论
数据
数据：人类、动物、植物...
数据对象：人类
数据元素：一个人
数据项：眼、耳、鼻...(数据不可分割的最小单位)
结构
逻辑结构：集合结构、线性结构、树形结构、图形结构
物理结构：顺序存储结构、链式存储结构
抽象数据结构类型
第二章 算法
示例
算法效率的度量 -- 时间复杂度
时间复杂度：T(n) = O(f(n))
T(n):执行次数
n:问题规模
f(n):
测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数。运行时间和这个成正比。
常数阶 O(1)
线性阶 O(n)
对数阶 O(log n)
平方阶 O(n²)
心得：以是否存在循环和循环嵌套情况来判断时间复杂度
平均时间复杂度和最坏时间复杂度
常见时间复杂度
算法效率的度量 -- 空间复杂度
空间复杂度:S(n) = O(f(n))
第三章 线性表
线性表：零个或多个数据元素的有限序列
线性表抽象数据类型：
线性表的顺序存储结构
存取性能为O(1),这种称为随机存储结构
顺序存储结构的插入与删除
插入删除性能为O(n)
线性表的链式存储结构
结点：数据域+指针域
指针域
数据域
单链表
头指针
头结点：空的数据域+头指针（非必要）
单链表的读取
O(n)
单链表的插入与删除
O(1)
单链表的整表创建
“头插法”
“尾插法”
单链表的整表删除
静态链表
静态链表：数组描述的链表
循环链表
循环链表
双向链表
第四章 栈与队列
栈：仅在表尾进行插入和删除操作的线性表
进栈：压栈、入栈
出栈：弹栈
栈的抽象数据类型
栈的顺序存储结构及实现
栈的结构定义
入栈
出栈
两栈共享空间
栈的链式存储结构及实现
把栈顶放在单链表的头部，不需要头结点
进栈
出栈
栈的应用--递归
斐波拉切数列：前面两项相邻之和构成后一项 （1 2 3 5 8 ...）
递归 ：自己调用自己
栈的应用--四则运算表达式求值
中缀表达式转后缀表达式规则：
后缀表达式计算规则：
队列
队列：只允许在一端进行插入操作，另一端进行删除操作的线性表
队列的抽象数据类型
循环队列
队列的链式存储
第五章 串（字符串）
主串
子串
空格串
ASCII编码
串的比较
串的顺序和链式存储
串的模式匹配 -- 朴素的算法
太低效了
串的模式匹配 -- KMP算法
第六章 树
树
根
空树
子树
结点的度：结点拥有的子树数
叶结点、终端结点：度为0
分支结点、非终端结点：度不为0 （分支结点=根节点+内部结点）
结点的层次
树的深度、树的高度
有序树、无序树
森林
树的抽象结构类型
树的存储结构
双亲表示法:记录父节点
孩子表示法：记录所有的孩子；改进版双亲孩子表示法
孩子兄弟表示法：记录第一个孩子和右兄弟
二叉树
二叉树
特殊二叉树
斜树
满二叉树
完全二叉树:与满二叉树位置编号相同，只不过不满
二叉树性质
1-5
二叉树存储结构--顺序存储
顺序存储一般只用于完全二叉树
二叉树存储结构--链式存储
遍历二叉树--前序
算法实现：
遍历二叉树--中序
算法实现：
遍历二叉树--后序
算法实现：
遍历二叉树--层序遍历
推导遍历结果
前序：从根节点开始，先遍历左子树，再遍历右子树
中序：从“左下角"开始, 中 --> 右
后序：从“左下角"开始，右 --> 中
线索二叉树
树、森林与二叉树转换
赫夫曼树及其应用
赫夫曼编码：最基本的压缩编码方法
第七章 图
图：顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V,E），其中G表示为一个图，V表示顶点集合，G表示边的集合
顶点：和线性表、树不同，图中不可以没有顶点
边：
无向图：
完全无向图：
有向图
有向边 弧 弧头 弧尾
完全有向图简单图
稀疏图：
稠密图：
权：
网：
子图：
