1、4.1单链表a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等b.带头结点的怎么判定空表：head和tail指向单链表的头结点c.链表的插入（q-next=p-next; p-next=q;）【（n）】d.链表的删除（q=p-next = q- delete q;e.不足：next仅指向后继，不能有效找到前驱4.2双链表a.增加前驱指针，弥补单链表的不足b.带头结点的怎么判定空表:c.插入：（q-next = p- q-prev = p;next = q;next-prev = q;d.删除：（p-prev-prev = p-prev;nex
2、t = NULL; delete p;4.3顺序表和链表的比较4.3.1主要优点a.顺序表的主要优点没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利b.链表的主要优点无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相 比其比例较大时，应该慎重选择第三章 栈与队列1.栈a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先
3、出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种b.应用：1）数制转换while （N） N%8入栈； N=N/8; while （栈非空） 出栈；输出；2）括号匹配检验不匹配情况：各类括号数量不同；嵌套关系不正确算法：逐一处理表达式中的每个字符ch：ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if （栈空） return false else 出栈，检查匹配情况， if （不匹配） return false 如果结束后，栈非空，返回false3）表达式求值3.1中缀表达式：计算规则：先括号内，再
4、括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右3.2后缀表达式： := + | | * |/| |栈顶运算符优先级），反复弹出栈顶运 算符并输入到PostfixExp中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP；while （表达式没有处理完） item = 读取表达式一项; 操作数：入栈OP； 运算符：退出两个操作数， 计算，并将结果入栈c.递归使用的场合：定义是递归的；数据结构是递归的；解决问题的方法是递归的2.队列a.若线性表的插入操作在一端进行，删除操作在另一端进行，则称此线性表为队列b.循环队列判断队满对空：队空
5、：front=rear；队满：（rear+1）%n=front第五章 二叉树1.概念a. 一个结点的子树的个数称为度数b.二叉树的高度定义为二叉树中层数最大的叶结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶结点的层数d.如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树e.如果一颗二叉树最多只有最下面的两层结点度数可以小于2；最下面一层的结点都集中在该层最左边的位置上，则称此二叉树为完全二叉树 f.当二叉树里出现空的子树时，就增加新的、特殊的结点空树叶组成扩充二叉树，扩充二叉树是满二叉树外部路径长度E：从扩充的二叉树的根到每个外部结点（新增的空树叶）
6、的路径长度之和内部路径长度I：扩充的二叉树中从根到每个内部结点（原来二叉树结点）的路径长度之和2.性质a. 二叉树的第i层（根为第0层，i0）最多有2i个结点b. 深度为k的二叉树至多有2k+1-1个结点c. 任何一颗二叉树，度为0的结点比度为2的结点多一个。n0 = n2 + 1d. 满二叉树定理：非空满二叉树树叶数等于其分支结点数加1e. 满二叉树定理推论：一个非空二叉树的空子树（指针）数目等于其结点数加1f. 有n个结点（n0）的完全二叉树的高度为log2（n+1），深度为log2（n+1）𝟏g. 对于具有n个结点的完全二叉树，结点按层次由左到右编号，则有：1） 如果i
7、= 0为根结点；如果i0，其父结点编号是 （i-1）/2 2） 当2i+1n，i结点的左子结点是2i+1；否则i结点没有左子结点 3） 当2i+2n，i结点的右子结点是2i+2；否则i结点没有右子结点3.周游（重点为由前序中序/中序后序求得二叉树）a.深度优先周游二叉树，可以有下列三种周游顺序：（实现：栈）1） 前序周游（tLR次序）：访问根结点；前序周游左子树；前序周游右子树 2） 中序周游（LtR次序）：中序周游左子树；中序周游右子树 3） 后序周游（LRt次序）：后序周游左子树；后序周游右子树；访问根结点b. 广度周游二叉树：从二叉树的顶层（根结点）开始，自上至下逐层遍历；在同一层中，按
8、照从左到右的顺序对结点逐一访问（实现：队列）4.存储链式存储结构，顺序存储结构（仅限完全二叉树：因为完全二叉树排列紧凑）5.二叉搜索树（BST）a.判定：是一颗空树；或者是具有下列性质的二叉树：对于任何一个结点，设其值为K，则该结点的 左子树（若不空）的所有结点的值都小于K；右子树（若不空）的所有结点的值都大于K；它的左右子树也分别为二叉搜索树b.性质：按照中序周游将各结点打印出来，得到的排列按照由小到大有序c.检索：从根结点开始，在二叉搜索树中检索值K 如果根结点储存的值为K，则检索结束 如果K小于根结点的值，则只需检索左子树 如果K大于根结点的值，则只检索右子树该过程一直持续到找到K或者遇
9、上叶子结点 如果遇上叶子结点仍没有发现K，则查找失败*查找关键码：把查找时所经过的点一次写出d.插入：用待插入结点与树根比较，若待插入的关键值小于树根的关键值，就进入左子树，否则进入右子树；在子树中，按照同样的方式沿检索路径直到叶结点，将新结点插入到二叉搜索树的叶子结点位置e.创建：从空的BST开始，将关键码按BST定义一次插入与插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性，删除过程分为如下情况：1）被删除的结点是叶子：直接将其删除即可2）被删除的结点只有左子树或只有右子树：直接将要删除的点删除后，将该点的左（右）孩子和上面结点相连3）被删
10、除结点有左、右子树：若p有左右子树，则在左子树里找中序周游的最后一个结点r，将r的右指针置成指向p的右子树的根，用结点p的左子树的根去代替被删除的结点p6.堆a.最小/大堆定义：最小堆：是个关键码序列k0, k1kn-1，具有如下特性（i=0,1,n/2-1）k i k 2i+1（左孩子） k i k 2i+2（右孩子） （即父2个孩子） 类似可以定义最大堆k i k 2i+1k i k 2i+2 （即父2个孩子）b.建“初堆”：按序列建立完全二叉树，从其中最后一个有孩子的结点开始按堆的定义调整插入点追加到最后，自下而上依次比较父与子，直到满足堆的定义用最后结点替换被删结点，自上至下调整成堆e
11、.移出最小/大值：可以将堆中最后一个位置上的元素（数组中实际的最后一个元素）移到根的位置上，利用从左开始向下筛选对堆重新调整 7.Huffman树a.概念路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径结点路径长度：从根结点到该结点的路径上分支的数目树的路径长度：树中每个结点的路径长度之和b.带权的路径长度树中所有叶子结点的带权路径长度之和 =其中： 𝒘𝒌：权值 𝒍 ：结点到根的路径长度c.编码：左0右1d.如何构建：选取序列中最小的相加生成树如此反复第六章 树若N，则称k是k的父结 点，k是k的子结点若有序对及N， 则称k和k互
12、为兄弟若有一条由 k到达ks的路径，则 称k是ks的祖先，ks是k的子孙2.树/森林与二叉树的相互转换a.树转换成二叉树加线: 在树中所有兄弟结点之间加一连线 抹线: 对每个结点，除了其最左孩子外，去除其与其余孩 子之间的连线 旋转: 以树的根结点为轴心，将整树顺时针转45b.二叉树转化成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构 c.森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺
13、时针旋转，构成二叉树型结构 d.二叉树转换成森林将二叉树中根结点与其右孩子连线，及沿右分支搜索到 的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树3.周游a.先根（次序）周游若树不空，则先访问根结点，然后依次先根周游各棵子树b.后根（次序）周游若树不空，则先依次后根周游各棵子树，然后访问根结点c.按层次周游若树不空，则自上而下自左至右访问树中每个结点4.存储结构“左子/右兄”二叉链表表示法：结点左指针指向孩子，右结点指向右兄弟，按树结构存储，无孩子或无右兄弟则置空5. “UNION/FIND算法”（等价类）判断两个结点是否在同一个集合中，查找一个给定结点的根结点的过
14、程称为FIND归并两个集合，这个归并过程常常被称为UNION“UNION/FIND”算法用一棵树代表一个集合，如果两个结点在同一棵树中，则认为它们在同一个集合中；树中的每个结点（除根结点以外）有仅且有一个父结点；结点中仅需保存父指针信息，树本身可以 存储为一个以其结点为元素的数组6.树的顺序存储结构a. 带右链的先根次序表示法 在带右链的先根次序表示中，结点按先根次序顺序存储在一片连续的存储单元中每个结点除包括结点本身数据外，还附加两个表示结构的信息字段，结点的形式为:info是结点的数据；rlink是右指针，指向结点的下一个兄弟；ltag是一个左标记，当结点没有子结点（即对应二 叉树中结点没
15、有左子结点时），ltag为 1，否则为 0 b. 带双标记位的先根次序表示法规定当结点没有下一个兄弟（即对应的二叉树中结点没有右子结点时）rtag为1，否则为0c. 带双标记位的层次次序表示法结点按层次次序顺序存储在一片连续的存储单元中第七章 图1.定义a.假设图中有n个顶点，e条边：含有e=n（n-1）/2条边的无向图称作完全图含有e=n（n-1） 条弧的有向图称作有向完全图若边或弧的个数e nlogn，则称作稀疏图，否则称作稠密图b. 顶点的度（TD）=出度（OD）+入度（ID）顶点的出度: 以顶点v为弧尾的弧的数目顶点的入度: 以顶点v为弧头的弧的数目c.连通图、连通分量 若图G中任意两
16、个顶点之间都有路径相通，则称此图为连通图 若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量 d.强连通图、强连通分量 对于有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图 否则，其各个极大强连通子图称作它的强连通分量 e.生成树、生成森林假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树 对非连通图，则将由各个连通分量构成的生成树集合称做此非连通图的生成森林 2.存储结构a.相邻矩阵表示法表示顶点间相邻关系的矩阵若G是一个具有n个顶点的图，则G的相邻矩阵是如下定义的nn矩阵：Ai,j=1，若（Vi,
17、 Vj）（或）是图G的边Ai,j=0，若（Vi, Vj）（或）不是图G的边b.邻接表表示法为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）（建立单链表时按结点顺序建立）a. 深度优先周游：从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发，深度优先搜索遍历图中的其余顶点，直至图中所有与V0有路径相通的顶点都被访问到为止b. 广度优先周游：从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，随后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有与V0有路径相通的顶点都被访问到为止
18、，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止4.拓扑排序拓扑排序的方法是：1）选择一个入度为0的顶点且输出之2）从图中删掉此顶点及所有的出边3）回到第1步继续执行，直至图空或者图不空但找不到无前驱（入度为0）的顶点为止5.单源最短路径（Dijkstra算法）6.每对顶点间的最短路径（Floyd算法）7.最小生成树a.Prim算法b.Kruskal算法c.两种算法比较：Prim算法适合稠密图，Kruskal算法适合稀疏图第八章 内排序算法 最大时间 平均时间 最小时间 S（n） 稳定性 直接插入排序 （n2） （n） （1）
19、稳定 冒泡排序 直接选择排序 不稳定 Shell排序 （n3/2） 快速排序 （nlog n） （log n） 归并排序 堆排序 桶式排序 （n+m） 基数排序 （d（n+r） （n+r） 第十章 检索1.平均检索长度（ASL）是待检索记录集合中元素规模n的函数， 其定义为：ASL=Pi为检索第i个元素的概率;Ci为找到第i个元素所需的比较次数2.散列a.除余法用关键码key除以M（取散列表长度），并取余数作为散列地址散列函数为：hash（key） key mod M b.解决冲突的方法 开散列方法：把发生冲突的关键码存储在散列表主表之外（在主表外拉出单链表） 闭散列方法：把发生冲突的关键码存
20、储在表中另一个位置上c.线性探查 基本思想：如果记录的基位置存储位置被占用，就在表中下移，直到找到一个空存储位置；依次探查下述地址单元：d0+1，d0+2，.，m-1，0， 1，.， d0-1；用于简单线性探查的探查函数是:p（K, i） = i d.散列表的检索1.假设给定的值为K，根据所设定的散列函数h，计算出散列地址h（K） 2. 如果表中该地址对应的空间未被占用，则检索失败，否则将该地址中的值与K比较3. 若相等则检索成功；否则，按建表时设定的处理冲突方法查找探查序列的下一个地址，如此反复下去，直到某个地址空间未被占用（可以插入），或者关键码比较相等（有重复记录，不需插入）为止e.散列
21、表的删除：删除后在删除地点应加上墓碑（被删除标记）f.散列表的插入：遇到墓碑不停止，知道找到真正的空位置第十一章 索引技术1.概念：a.主码：数据库中的每条记录的唯一标识b.辅码：数据库中可以出现重复值的码2.B树a.定义：B树定义：一个m阶B树满足下列条件：（1） 每个结点至多有m个子结点；（2） 除根和叶外其它每个结点至少有个子结点；（3） 根结点至少有两个子结点例外（空树，or独根）（4） 所有的叶在同一层,可以有- 1到m-1个关键码（5） 有k个子结点的非根结点恰好包含k-1个关键码 b.查找在根结点所包含的关键码K1，Kj中查找给定的关键码值（用顺序检索（key少）/二分检索（ke
22、y多）；找到：则检索成功;否则，确定要查的关键码值是在某个Ki和Ki+1之间，于是取pi所指结点继续查找;如果pi指向外部结点，表示检索失败. c.插入找到的叶是插入位置，若插入后该叶中关键码个数m,插入完成；否则分裂,中间为分界码（插入到父结点）,若父结点上溢则继续向上分裂d.删除删除的关键码不在叶结点层：先把此关键码与它在B树里的后继对换位置，然后再删除该关键码（叶中删）删除的关键码在叶结点层：删除后关键码个数不小于- 1直接删除关键码个数小于- 1，如果兄弟结点关键码个数不等于- 1从兄弟结点移若干个关键码到该结点中来（父结点中的一个关键码要做相应变化）如果兄弟结点关键码个数等于- 1合
23、并3.B+树m阶B+树的结构定义如下：（1）每个结点至多有m个子结点；（2）每个结点（除根外）至少有个子结点；（3）根结点至少有两个子结点；（4）叶在同一层，有.m个key，叶包含全部key，B+树的叶结点链接成一个双链表 （5）有k个子结点的结点必有k个关键码。第十二章 高级数据结构1.广义表a.广义表的结构特点:1. 广义表中的数据元素有相对次序2. 广义表的长度定义为最外层包含元素个数3. 广义表的深度定义为所含括弧的重数:“原子”的深度为 0 ;“空表”的深度为 14. 广义表可以共享5. 广义表可以是一个递归的表：递归表的深度是无穷值，长度是有限值 6. 任何一个非空广义表 LS =
24、 （1, 2, , n）均可分解为: 表头Head（ LS ） =1和表尾Tail（ LS ）=（2, , n）两部分b.广义表的各种类型纯表（pure list）：从根结点到任何叶结点只有一条路径；也就是说任何一个元素（原子、子表）只能在广义 表中出现一次可重入表（ reentrant list ）：图示对应于一个DAG；其元素（包括原子和子表）可能会在表中多次出现， 但不会出现回路循环表（ cyclic list ，递归表）：有向图中可能包含回路；循环表的深度为无穷大2.平衡的二叉搜索树（AVL）a.平衡因子 用bf（x）来表示结点x的平衡因子，它被定义为：bf（x）=x的右子树的高度x的左子树的高度b.AVL的插入：按BST建立，发现不满足AVL定义即调整，插入时出现的情况：1）LL/RR:中间元素成为双亲，左右各位孩子（满足BST定义）2）LR/RL:最后元素成为双亲，前两个为孩子（满足BST定义）附录：二叉树前序周游templatevoid
