（一）数据结构 1.线性表 　　  1）线性表的定义 求合集；归并操作   2）线性表的顺序存储和基本运算（查找、插入和删除）的实现 1.用物理相邻表示逻辑相邻 随机存取结构LOC(ai)=LOC(ai-1)+C 查找性能是O(1) 2.静态定义； 动态定义 3.线性表插入：(前插)相应之后元素后移 时间复杂度O(n) 4.线性表删除：相应元素前移     3）线性表的链式存储和基本运算（查找、插入和删除）的实现 1.顺序存储结构 按值查找的时间性能是O(n) 2.头指针 为了操作的方便，添加头结点 3.插入 在第i个位置前插入（即使得被插入节点序号为i），找到第i-1个节点，转换为在i-1个节点后插 前插 在第i个节点前插入节点；找到第i-1转换为后插；或者在i位置后插，之后新节点和i调换 4.删除 修改指针 5.构造单链表 逐个插入的过程 头插法（相反） 第一个插入的（最后一个元素）需要将next为NULL；如果带头节点其初始next为NULL，可以统一操作 尾插法（相同） 不带头结点：第一个节点特殊处理使得头指针L和尾指针r同时指向该节点，next为NULL，下一个节点使得 next为NULL ，r->next为新节点地址，r重新赋值为新节点地址 带头结点：r->next=new,r=new; 6.双向链表 data prior next 循环链表 r-next=L 末尾节点 双向循环链表   4）线性表的应用 2.栈、队列和矩阵 　    1）栈和队列的定义      栈：Fist In Last Out 队列：First In First Out       2）栈和队列的实现         （1）栈的顺序存储和基本操作（入栈、出栈和判栈空、栈满）的实现 先进后出：压栈，弹栈 top指向当前栈顶元素的下一个位置，栈顶的头部。 base指向栈低元素         （2）栈的链式存储和基本操作（入栈、出栈和判栈空）的实现 栈顶指针指向栈顶元素；链栈不需要头结点         （3）队列的链式存储和基本操作（入队、出队和判队空）的实现 1.front指向第一个节点 rear指向最后一个节点 2.入队 队尾；出队 队头。 只有一个节点的队列出队，还需要修改尾指针。         （4）循环队列的定义和基本操作（入队、出队和判队空、队满）的实现 1.一组地址连续的存储单元，队头指向第一个元素，队尾指向队尾元素的下一个位置。普通顺序队列有假上 溢。 2.用循环队列解决普通顺序队列假上溢情况。 少用一个空间， 判断队满：当rear+1==front （rear+1）%Length=front 入队操作 rear=rear+1; rear=(rear+1)%Length 出队操作 front=front+1 front=(front+1)%Length 出队入队都是指针加一 队列长度 rear-front; rear-front+Length; (rear-front+Length)%Length         3）栈和队列的应用 1.栈的应用 1）.数值转换 十进制转换成2进制是 除2取余 N=(N div d)*d+ N mod d 十进制转换八进制为例，N%8的余数进栈，N=N/8，继续求余数压栈 2）.括号匹配 左括号压栈，遇到右括号弹栈，直到出现左括号为止  3）.行编辑程序问题 4）.表达式求值（二元运算符表达式） 前缀表达式；中缀表达式；后缀表达式 后缀表达式，栈应用 构造后缀表达式 括号起隔离作用（右括号全部出栈）； 数字直接输出，运算符进栈，遇到比他运算级别低的先出栈再进栈，高的运算符先进栈入栈 5）.实现递归 4）矩阵的压缩存储 行优先 列优先 不丧失随机存取特性         （1）特殊矩阵（对称矩阵、三角矩阵、对角矩阵）的压缩存储 对称矩阵： 主对角线及以下的元素（下三角） 元素总数，空间总数：1/2（n*（n+1）） aij 前i-1行共 （1+i-1+1）*（i-1+1）*1/2=（1+i）*i*1/2个元素 k=1+i）*i*1/2+j 上三角 对换 ij即可 上三角矩阵： 对角矩阵：三对角矩阵 aij 前i-1行共 2+（i-1-1）*3=3i-4         （2）稀疏矩阵的压缩存储 三元组顺序表 i，j ，data 行数；列数；非零元素个数 3.树与二叉树 1）树的基本概念 有向树（双亲孩子节点之间）； 有序树、无序树（兄弟节点之间）     2）二叉树        （1）二叉树的定义及性质 1.二叉树有五种基本形态：空树、只含根节点、右子树为空、左子树为空、左右子树都不 为空。 区别于度为2的有序树（一个孩子节点时不区分左右） 2.性质1：在二叉树的第i层上至多有2^(n-1)个节点 性质2：深度为k的二叉树至多含有2^n-1个节点 性质2推广： 性质3：任何一棵二叉树，若它含有n0个叶子节点、n2个度为2的结点，则有n2+1=n0 n=n0+n1+n2 b=n1+2n2 p=n-1 3.满二叉树；完全二叉树        （2）二叉树的顺序存储和链式存储 1.顺序存储：完全二叉树，空的空着 2.链式存储： 二叉链表：每个节点（数据域，2个指针域） 三叉链表：二叉链表+双亲指针 由根指针唯一确定。 分支数=节点数-1 二叉链表有n个节点，2n个指针域；分支数b=n-1，即有n-1个指针域不为空，空指针 有2n-n+1=n+1个        （3）二叉树的先序、中序、后序遍历和层序遍历运算 1.先序遍历：第一次经过根节点就访问；中序遍历：第二次经过根节点访问；后序遍历：第三次 经过根节点访问。 每个节点访问三次。 2.递归描述； 非递归描述： 中序遍历（栈的应用）：根节点进栈；根节点的左进栈…左的左进栈；没有左则出栈，该节点 的右进栈（循环，左的左进栈……）；没有左出栈；右也访问过了，则下一个节点出栈。        （4）线索二叉树的定义 将空的指针域存储对应遍历算法的前驱或后继并添加标志位标志指针域存储为孩子或线索。 3）树和森林        （1）树的存储结构 1.双亲表示法：一组连续的存储单元（数组结构），存储节点信息之外也存储该节点的双亲 节点的信息 2.孩子链表表示法：将孩子穿成链表（数组结构+链表），数组存储节点信息和孩子链表头 指针；链表存储兄弟节点 3.树的孩子兄弟表示法：左指针表示第一个孩子，右指针表示右临兄弟。 和二叉树的二叉链表表示法对应        （2）树（森林）与二叉树的相互转换 1.森林转换成树 第一棵树转换为根和右子树，其他的左子树   2. 树转换成二叉树 关系二叉树的二叉链表和树的孩子兄弟表示法 连接树的兄弟节点，只保留一个到双亲节点的连线 3.森林转换成二叉树 将森林中的每棵树分别转换成二叉树； 从第二棵二叉树开始，作为前一棵二叉树的左子树 4.二叉树还原 没有右子树则是树，有右子树则是森林     （3）树和森林的遍历 树 1.先根遍历（同该树对应的二叉树的先序遍历一致） 2.后根遍历（同该树对应的二叉树的中序遍历一致） 3.层序遍历 森林 1.先序遍历（依次从左至右对森林中的每棵树进行先根遍历） 2.中序遍历（依次从左至右对森林中的每棵树进行后根遍历） 4）树与二叉树的应用    （1）二叉查找树（Binary Search Tree）        （2）平衡二叉树（Balanced Binary Tree或 Height-Balanced Tree或AVL Tree）        （3）哈夫曼（Huffman）树和哈夫曼编码 1.节点的路径长度：从根节点到该节点的路径上的分支数目 树的路径长度：树的每个节点的路径长度之和 树的带权路径长度：树的叶子节点的带权路径长度之和WPL(T) 最优树：一棵带权路径长度之和最小的树 赫夫曼树：最优二叉树 2.构造最优二叉树（赫夫曼树） a.构造只有根没有左右子树的二叉树 b.选取权值最小的组成一棵二叉树的左右子树，根节点为左右孩子节点权值之和 c.从包括b的根节点在内但不包括已经选过的树中选取两个节点组成二叉树…… 3.赫夫曼编码 左为1右为0；从根到叶子节点的01序列就是该叶子节点表示字符的赫夫曼编码。 叶子节点的权值为该编码的使用频率 使用频率高的编码短，反之长。 前缀编码：赫夫曼编码是前缀编码，即任何编码都不是另外一个字符的前缀 4.图 1）图的基本概念 1.定义：Graph 关系集&顶点集 2.有向图，弧<>； 无向图，边（）。 3.图在逻辑上是多对多的关系，没有所谓第一最后，在确定存储结构后有了第一、最后。 4.（不考虑顶点到自身的边或弧前提下）n个顶点的无向图图，有0~1/2*n*n-1)条边（每个顶底 都有到其他顶点的边）。 完全图： 无向完全图：有最多的边 n个顶点，有0~n*（n-1） 5.稀疏图；稠密图 6.子图：顶点是图的顶点的子集，边或弧也是边或弧的子集。前提是图。 7.邻接点 两点之间有弧或者边 8.度 入度，出度 总边数是总度数的二分之一，即有向图的出度等于入度（弧一定有弧头和弧尾） 9.权 边上的数，边上有权的图是网 10.路径 图中的顶点序列 简单路径 顶点不重复 路径长度 路径上经过的弧或边的数目 回路或环 路径中第一个顶点和最后一个顶点相同 简单回路 顶点不重复的回路 11.连通图 连通 两个顶点之间有路径 连通图 任意两个顶点之间连通 连通分量 无向图 中的 极大连通子图 （连通子图拥有最多边数） 连通图的连通分量就是他自身 非连通图有多个连通分量 12.强连通图 有向图中，每对顶点都有 路径（可以由多条弧组成） 强连通图分量 有向图 中的 极大连通分量 强连通图只有一个强连通分量，即其自身 非强连通图有多个连通分量 13.生成树 极小连通子图（n-1） 在生成树上加一个边形成环     2）图的存储       （1）数组表示法（邻接矩阵表示法） 两个数组，一个一维数组放置顶点信息，一个二维数组放置关系       （2）邻接表表示法 一个数组，一堆链表。数组存放顶底信息和邻接点组成的链表的头指针。 读入顶点的顺序，尾插头插有区别     3）图的遍历       （1）深度优先搜索（DFS）算法 递归：从一个顶点开始，访问该顶点未被访问的邻接点；再从这个邻接点出发，循环（连通图） 连通图类似树的先根遍历，因为有回路出现，需要设置一个访问标记。 非连通图，有多个连通分量。设置标志位，从第一个未被访问的顶点开始，深度优先遍历一次，访问完全一个连通分量（有 回溯的过程）。循环。 连通图可有深度优先生成树。非连通图就是森林了       （2）广度优先搜索（BFS）算法 队列：第一个顶点入队，出队并访问，并所有邻接点入队； 4）图的应用   （1）最小（代价）生成树求解方法（Prim算法和Kruskal算法） n个顶点选取n-1条边构成树（多一条边可能构成环，少一条边一个顶点游离） 1.prim算法 选取一个顶点作为树的根，选取连接该顶点权值最小的边，带入新顶点，以该新顶点为出发点，选取剩余顶点权值 最小的边带入新顶点（不能造成回路为原则，否则回溯）……循环，指导有n-1条边。稠密图 2.kruskal算法（加边法） 构造含有所有顶点的子图，选取权值最小的边，选取次小的边（不能造成回路）……循环，直到n-1条边 时间复杂度与边的排序有关。 稀疏图       （2）最短路径求解方法（Dijkstra算法和Floyd算法） 1.Dijkstra，从某个源点到其余各点的最短路径 从一个顶点开始，第一趟记录该顶点到邻接点弧的路径及权值 10，选取权值最小的作为下一个出发点（顶 点集合变为两个顶点）；从新出发点开始添加可到的节点，并与第一趟比较出最小权值的顶点作为出发点，期间可 以修改路径，经由较短 路径，间接到达，以期待最小的路径长度……直到到达确定最后一个顶点 2.Floyd算法，每一对顶点之间的最短路径 1）.图的邻接矩阵 2）.加入一个顶点，修改矩阵权值 3）.直到最后一个顶点       （3）AOV-网和拓扑排序方法 1.有向图原本有一定的次序关系，但不是线性的，在不破坏原有关系基础上（即原来没有次序关系的顶点人为添加 关系），使得顶点构成一个线性序列。 有回路的图不能求得拓扑排序序列 2.方法：选取一个入度为零的顶点，删除该顶点的所有出度指向顶点；循环。 加一个栈，保存入度为零的顶点。       （4）AOE-网和关键路径求解方法 关键活动延长时间会导致工程延长时间（关键路径唯一的情况下）。 工程完成时间：有向图起点到汇点的最长路径。 关键活动的最早开始时间 等于 最迟开始时间 1.事件的最早发生时间=从源点到顶点j的最长路径长度（j顶点必须完成前驱事件才能执行）。 事件的最迟发生时间=汇点的最早发生时间-汇点到顶点j的最短路径长度 2.活动 ab ac…… 活动的最早开始时间就是弧头事件的最早开始时间； 活动的最晚开始时间就是弧尾的最晚开始时间-事件的权值 3.活动最早开始时间=活动最晚开始时间就是关键路径 5.查找 1）查找的基本概念 静态查找：只做检索； 动态查找：查找并插入没有的数据 average search length 平均查找长度 ASL=∑ PiCi Pi是第i个数据被检索的概率，Ci是第i个数据检索比较的次数     2）顺序查找法 顺序表，链表 将a[0]放置哨兵；从最后开始查找，返回为0则没找到 等概率； 不等概率：将经常查找的放置在尾部；或者每次查找后将其放置在末尾。  （1）顺序查找算法  （2）平均查找长度计算 3）折半查找法   （1）折半查找算法 有序表的折半查找 low high mid   （2）折半查找判定树的构造 表长为n的折半查找判定树的深度和有n个节点的完全二叉树相同，不同的是，折半查找判定书平均分配，完全二叉树左边集中   （3）平均查找长度计算     4）动态查找表       （1）二叉查找树（也称为二叉排序树）的构造及查找、插入和删除运算 1.非空二叉排序树，左子树所有节点值小于根节点；右子树所有节点值大于根节点；左子树、右子树递归 2.通常采取二叉链表作为二叉查找树的存储结构 3.静态查找，递归，比根大，左边找，小右边找，直到找到或指针为空为止。 4.动态查找，用p记录当前查找指针的父节点指针，当当前指针指向的值为空时，即p->left p->right为空，直接在该处插入 若树非空，则插入的数据一定是叶子节点，树为空则为根节点 5.二叉排序树的插入构成也是二叉排序树的构造过程 6.对二叉排序树中序遍历则得到有序序列 7.二叉排序树的删除算法（基于查找）： 被删节点是叶子节点，直接删除 被删节点只有做或者右，将其的双亲节点的指针直接指向其唯一孩子节点 被删节点左右孩子都有，用其前驱节点替换被删节点，删除其前驱节点的原位置数据，可根据其情况递归（只有一个孩子，左 右孩子都有，叶子节点）；用后继节点替换 8.二叉查找树尽可能矮；如果是单支树，则其查找性能退化为顺序查找的性能       （2）平衡二叉树的构造及查找运算 1.左右子树深度之差的绝对值不大于1。 2.构造平衡二叉树：平衡旋转技术 LL RR LR RL 找到最小不平衡子树调整       （3）B-树的特点及查找运算 B-树是一种 平衡 的 多路（不止二叉） 查找树 m阶B-树，每个非终端节点可能还有n个关键字（1<=n<=m）,n个指针，n+1个指向子树的指针 非叶子节点的关键字从小到大排列；    （4）平均查找长度计算     5）哈希表   （1）哈希表的构造及查找运算 1.f(key) 解决冲突 2.数字 构造 直接定值法：地址是其线性结果H（key）=a*key+b 数字分析法；分析关键字的数字，取不容易冲突的组合作为地址 平方取中法 ：平方运算扩大差别； 折叠法：将关键字分割为若干位，叠加； 除留余数法：H（key）=key MOD p （p取不大于表长的素数） 9就不行 随机数法：H(key)=Random（key） 3.解决冲突 1）.开放定址法： H0=H(key) Hi=（H(key）+di）M OD m //给原地址加一个数 di 线性探测再散列 di=c*i //向后移 平方探测再散列 di= 1^2,-1^2,2^2,-2^2 //右左右左跳 随机探测再散列 di是一组伪随机数列 或 di=i*H2（key） 查找次数=探测次数 2）.链地址法 真正空间放置头指针 ；链表放数据 装载因子 4.删除 需要特殊处理 逻辑删除       （2）平均查找长度计算 6）字符串的模式匹配   （1）基本的模式匹配算法 i从0开始++   （2）KMP模式匹配算法（模式串的next函数计算） next函数： next（1）=0；next（其他情况）=1；next（n）=头尾相同长度+1； 滑动：i=next（i）；//第i位置不相等了，就滑行next（i） 6.内部排序 排序前a领先于b，排序后a仍领先于b是稳定排序，反之不稳定排序。 1）简单排序方法  （1）直接插入排序算法 （扑克牌） 0位置放标志位。1.假设第一个数字有序，后一个比较前一个，后一个小于前一个，前一个后移，直接覆盖，指针也前移一个 ，否则直接覆盖到指针位。  （2）冒泡排序算法 相邻的比较，第一趟最大的沉底，第二趟次大的沉底…… 可在交换处加一个标志位  （3）简单选择排序算法 买苹果 找出最小的，和第一个交换；找出次小的和第二个交换……  （4）简单排序算法的时间复杂度、空间复杂度及稳定性分析 2）快速排序   （1）划分过程及分析 找一个基准，从后往前，比基准小，将该数交换到基准位置   （2）快速排序算法及其时间复杂度、空间复杂度及稳定性分析   3）堆排序       （1）堆的定义及初始堆的建立 大根堆：根值大于等于左右孩子； 小根堆 从叶子节点根据堆的定义调整。       （2）堆排序算法及其时间复杂度、空间复杂度及稳定性分析 建堆；输出堆顶元素；将最后一个元素补在堆顶位置，并调整堆，输出堆顶元素……       4）归并排序   （1）归并过程及分析 两个两个两个 有序=》四个四个 有序=》八个有序       （2）二路归并排序算法的时间复杂度、空间复杂度及稳定性分析      5）基数排序   （1）多关键排序方法 扑克牌，面值和花 {MOD}； 低位优先：先按面值，每叠四张，共13叠； 高位优先：先按花 {MOD}；每叠13张，共四叠；按面值，每叠排序       （2）链式基数排序方法及特点 按个位分配，收集；按十位分配，收集；按百位分配，收集……  6）内部排序方法的比较和应用