408知识框架总结——数据结构_408数据结构

个人复习用，有用自取，欢迎转载，标明出处即可。

不推荐在第一遍复习时使用，第一遍建议还是认认真真看书做题，第二遍复习时可以配合框架来过知识点，哪里不熟翻书来强化记忆。

重点难点不构成参考建议，仅为个人想法！！！

第一章、绪论☆

1.2算法和算法评价

时间复杂度、空间复杂度（最好、最坏）

乘法原则、加法原则

常见的渐近时间复杂度（常对幂指阶）

原地工作的概念

循环主体中的变量参与循环条件时的计算

第二章、线性表☆☆☆（算法题基础）

2.1.2线性表基本操作

创销、增删改查（命名要具有可读性）——数据结构的基本操作集，按此顺序推断后续数据结构

2.2线性表的顺序表示

顺序表的定义：静态分配、动态分配——代码段

顺序表的主要特点（四点）

插入、删除、按值/按位查找——代码段——注意位序和数组下标，注意数组范围和存储空间的判断。

2.3线性表的链式表示

单链表：

头插法建立单链表（有/无头结点）、尾插法建立单链表——代码段

按序查找、按值查找、插入结点（前插后插）、删除结点、求表长——代码段

双链表——定义、插入与删除（代码段可掌握）

循环单/双链表、静态链表——定义和特性

顺序表和链表的比较：4点

如何选择存储结构？（逻辑结构、存储结构、操作环境三方面来回答）

第三章、栈、队列和数组☆☆☆☆☆

3.1栈

栈的定义（顺序栈）——代码段

初始化（创）、销毁栈（销）、进栈（push增）、出栈（pop删）、读栈顶元素（查）、判空——代码段

后进先出LIFO、初试top位置（-1）、共享栈的特性。

3.2队列

顺序队列的定义——代码段

基本操作：初始化、判空、入队、出队、读队头元素。

循环队列：判空判满条件（三种方法），指针位置，队列中元素位置

循环队列操作集：初始化、判空、入队、出队——代码段

链队的定义——代码段

操作集：初始化、判空、入队、出队。

双端队列和输入、输出受限的双端队列——操作方法。

3.3栈和队列的应用

栈：括号匹配、表达式求值（后缀表达式求值）、递归

队列：层次遍历、计算机系统中的应用（FCFS、缓冲区）

3.4数组和特殊矩阵

注意下标！！！

数组的存储结构——行优先和列优先

特殊矩阵压缩存储：

①对称矩阵-行/列优先、上/下三角，元素的关系

②三角矩阵-上下三角区

③三对角矩阵（带状矩阵）

④稀疏矩阵的存储-数组或十字链表法

第四章、串

KMP算法、KMP优化算法——只需掌握手算步骤以及如何计算next、nextval值[做两道题]

第五章、树与二叉树☆☆☆☆☆

5.1树的定义和基本术语

根结点、子树、n个结点的树有n-1条边（根节点没有上层节点）

祖先、子孙、双亲、孩子、兄弟

结点的度、树的度

分支结点/非终端结点、叶子结点/终端结点

结点的深度、高度、层次。

有序树和无序树

路径和路径长度（树的分支是有向的）

森林

树的性质：

树中结点数是所有节点的度数之和+1  [结点数=总度数+1]

度为m的树中第i层上至多有个结点（i>=1）

高度为h的m叉树至多有个结点（至少有h个结点）

具有n个结点的m叉树的最小高度为

注意区分 度为m的树 和 m叉树的区别

 5.2二叉树的概念☆☆☆☆☆

几种特殊的二叉树

满二叉树：高度、结点数、特征

完全二叉树：高度、结点数、特点：区分分支结点和叶子结点、叶子结点出现层数、结点数判断分支结点左右孩子数

二叉排序树（BST树）、平衡二叉树（AVL树）（重点在第七章）

二叉树的性质：

1、非空二叉树叶子结点数=度为2的结点数+1   [n0=n2+1——n=n0+n1+n2]

2、非空二叉树上第k层至多有个结点（k>=1）

3、高度为h的二叉树至多有个结点（h>=1）

4、具有n个结点的完全二叉树的高度为或

二叉树的链式结构定义——代码段

5.3 二叉树的遍历和线索二叉树

先序遍历、中序遍历、后序遍历——递归实现代码段

层次遍历——代码段 

由遍历序列构造二叉树（前中、后中、层中）

线索二叉树构造方式——先序、中序、后序——能够用手算法画出，找前驱、后继

5.4树、森林 

树的存储结构——双亲表示法、孩子表示法、孩子兄弟表示法——代码段

树、森林与二叉树的转换——手算法推导

树和三林的遍历与二叉树遍历的关系

5.5树与二叉树的应用 ☆☆☆

哈夫曼：

带权路径长度、哈夫曼树的构造、哈夫曼编码

并查集：

结构定义、初始化、find、union、优化find、优化union——代码题？

第六章、图

6.1图的基本概念

图G顶点集V边集E，G=(V,E)

有向图、无向图 完全图(简单完全图)-有向/无向

子图 联通、连通图、连通分量/极大连通子图、非连通图（最多有多少条边？）

强连通图、强连通分量（n个顶点的有向图如果是强连通图，最少需要多少条边？）

区分极大连通子图和极小连通子图

生成树、生成森林——树是特殊形态的图

无向图——顶点的度、有向图——入度、出度

简单路径、简单回路、距离、有向树、带权路径长度

6.2图的存储及基本操作

邻接矩阵法、邻接表法——代码段—特点、适用范围

十字链表法、邻接多重表（能看懂）

6.3图的遍历

广度优先搜索BFS、深度优先搜索DFS（手算）

图的连通性判断

6.4图的应用☆☆☆☆☆

最小生成树——Prim算法、Kruskal算法——手算推演、特点、适用范围

最短路径——Dijkstra算法、Floyd算法——手算推演、特点、适用范围

有向无环图——DAG图描述含有公共子式的表达式（咸鱼分层法）

拓扑排序——AOV网-拓扑排序算法

关键路径——关键路径长度——手算推演-关键活动、关键路径不唯一、如何缩短工期

第七章、查找

7.2顺序查找和折半查找

一般线性表的顺序查找、有序表的顺序查找

折半查找——代码段

分块查找

查找成功、查找失败平均长度

7.3树型查找

二叉排序树BST

定义、递归查找算法——代码段

BST的插入、构造、删除（叶节点、只有一棵左/右子树、有左右两棵子树）、查找效率（成功失败平均长度）

平衡二叉树AVL

插入（LL、RR、LR、RL）、删除、查找（查找效率）

红黑树：定义

结论：

1、从根到叶节点的最长路径不大于最短路径的2倍

2、有n个内部节点的红黑树的高度<=

如何插入新节点：根/非根，插入后不满足定义则看叔叔脸色红黑。

查找时间复杂度

7.4B树和B+树☆☆☆

重点在于B树

B树定义（每个结点、根节点、除根节点外、非叶结点结构、叶节点）

性质（矮胖）：

1、根节点子树数∈[2,m]，关键字数∈[1,m-1]；其他节点子树数∈[,m]，关键字数∈[,m-1]（尽可能满）

2、对任意节点，所有子树高度都相同（尽可能平衡）

3、关键字的值：类比二叉排序树

含有n个关键字的m叉B树——

B树的插入、删除（不在终端结点；在终端结点：直接能删、兄弟够借、兄弟不够借）

B+树基本概念

最大特点：叶节点串成一条链

B+树和B树的主要差异（四点）

7.5散列表

散列函数构造方法：直接定址法、除留余数法、数字分析法、平方取中法

处理冲突的方法：开放定址法（线性探测、平方探测、双散列、伪随机序列）、拉链法

散列查找及性能分析

 平均查找长度（成功、失败）、装填因子

第八章、排序

8.2插入排序

直接插入排序、希尔排序

8.3交换排序

冒泡排序、快速排序（优化快排）——代码段

8.4选择排序

简单选择排序、堆排序

8.5归并排序和基数排序

归并排序、基数排序

8.6内部排序算法比较

1、算法分析基本只看最坏情况

2、时间复杂度、空间复杂度、稳定性、过程特征

3、上述算法手算推演（主要了解过程特特征，能画出每一轮的排序后状态）

内部排序算法的应用——待排元素数目、元素信息量大小、稳定性要求、初始结构是否有序等

8.7外部排序

多路平衡归并及败者树——手算推演

置换-选择排序、最佳归并树