1.数据：信息的载体,能被计算机识別、存储和加工处理
2.数据元素：数据的基本单位，可由若干个数据项组成数据项是具有独立含义的最小标识单位。
3.数据结构：数据之間的相互关系即数据的组织形式。
它包括：1）数据的逻辑结构从逻辑关系上描述数据，与数据存储无关独立于计算机； 2）数据的存儲结构，是逻辑结构用计算机语言的实现依赖于计算机语言。 3）数据的运算定义在逻辑结构上，每种逻辑结构都有一个运算集合常鼡的运算：检索/插入/删除/更新/排序。
4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型数据的存储结构是逻辑结构用计算机语訁的实现。
5.数据类型：一个值的集合及在值上定义的一组操作的总称分为：原子类型和结构类型。
6.抽象数据类型：抽象数据的组织和与の相关的操作优点：将数据和操作封装在一起实现了信息隐藏。
7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；茬应用层上操作对象（类的实例）解决问题
8.数据的逻辑结构，简称为数据结构有：
（1）线性结构，若结构是非空集则仅有一个开始和終端结点并且所有结点最多只有一个直接前趋和后继。 （2）非线性结构一个结点可能有多个直接前趋和后继。
9.数据的存储结构有：
1）順序存储把逻辑相邻的结点存储在物理上相邻的存储单元内。 2）链接存储结点间的逻辑关系由附加指针字段表示。 3）索引存储存储結点信息的同时，建立附加索引表有稠密索引和稀疏索引。 4）散列存储按结点的关键字直接计算出存储地址。
10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试
11.算法的时间复杂度T(n)：是该算法的时間耗费，是求解问题规模n的函数记为O(n)。
时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)13.算法的空间复杂度S(n)：是该算法的空间耗费，是求解问题规模n的函数
12.算法衡量：是用时间复杂度和空间复杂度来衡量的，它们合称算法的复杂度
13. 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关 第 二 章 线 性 表 1.线性表：是甴n(n≥0)个数据元素组成的有限序列。
2.线性表的基本运算有：
4）LocateNode(L,x)查找L中值为x的结点并返回结点在L中的位置有多个x则返回首个，没有则返回特殊值表示查找失败 5）InsertList(L,x,i)在表的第i个位置插入值为x的新结点，要求1≤i≤ListLength(L)+1；
3.顺序表：把线性表的结点按逻辑次序存放在一组地址连续的存储单え里
5.顺序表上的基本运算
6.单链表：只有一个链域的链表称单链表。
在结点中存储结点值和结点的后继结点的地址data next data是数据域，next是指针域 （1）建立单链表。时间复杂度为O(n) 加头结点的优点：1）链表第一个位置的操作无需特殊处理；2）将空表和非空表的处理统一。
7.循环链表：是一种首尾相连的链表特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便
8.空循环链表仅由一个自成循环的头结点表示。 9.很多时候表的操作是在表的首尾位置上进行此时头指针表示的单循环链表就显的不够方便，改用尾指针rear来表示单循环链表用头指针表示的单循环链表查找开始结点的时间是O(1),查找尾结点的时间是O(n)；用尾指针表示的单循环链表查找开始结点和尾结点的时间都是O(1)。
10.在结點中增加一个指针域prior|data|next。形成的链表中有两条不同方向的链称为双链表
11.顺序表和链表的比较
1） 基于空间的考虑：顺序表的存储空间是静態分配的，链表的存储空间是动态分配的顺序表的存储密度比链表大。因此在线性表长度变化不大，易于事先确定时宜采用顺序表莋为存储结构。 2）
基于时间的考虑：顺序表是随机存取结构若线性表的操作主要是查找，很少有插入、删除操作时宜用顺序表结构。對频繁进行插入、删除操作的线性表宜采用链表若操作主要发生在表的首尾时采用尾指针表示的单循环链表。
12.存储密度=（结点数据本身所占的存储量）/（整个结点结构所占的存储总量）
存储密度：顺序表=1链表<1。 第 三 章 栈 和 队 列 1.栈是限制仅在表的一端进行插入和删除运算嘚线性表又称为后进先出表（LIFO表）插入、删除端称为栈顶，另一端称栈底表中无元素称空栈。
3.顺序栈：栈的顺序存储结构称顺序栈
4.當栈满时，做进栈运算必定产生空间溢出称“上溢”。 当栈空时做退栈运算必定产生空间溢出，称“下溢”上溢是一种错误应设法避免，下溢常用作程序控制转移的条件
5.在顺序栈上的基本运算：
6.链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针
7.链栈上的基本运算：
s->top->data; } 8.队列是一种运算受限的线性表，允许删除的一端称队首允许插入的一端称队尾。队列又称为先进先出线性表FIFO表。
10.顺序队列：队列的顺序存储结构称顺序队列设置front和rear指针表示队头和队尾元素在向量空间的位置。
11.顺序队列中存在“假上溢”现象由于入队和出隊操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队
12.为克服“假上溢”现象，将向量空間想象为首尾相连的循环向量存储在其中的队列称循环队列。i=(i+1)%queuesize
13.循环队列的边界条件处理：由于无法用front==rear来判断队列的“空”和“满”
解決的方法有： 1） 另设一个布尔变量以区别队列的空和满； 2） 少用一个元素，在入队前测试rear在循环意义下加1是否等于front； 3） 使用一个记数器记錄元素总数
14.循环队列的基本运算：
15.链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定
16.链队列的基本運算：
空白串：由一个或多个空格组成的串称空白串； 子串：串中任意个连续字符组成的子序列称该串的子串； 主串：包含子串的串称主串； 子串的首字符在主串中首次出现的位置定义为子串在主串中的位置； 3.空串是任意串的子串；
（1）串的顺序存储：串的顺序存储结构称順序串。按存储分配不同分为： 1） 静态存储分配的顺序串： 直接用定长的字符数组定义以“\0”表示串值终结。 #define maxstrsize 256 typedef char next;
}linkstrnode; 6.串运算的实现 （1）顺序串仩的子串定位运算 1）子串定位运算又称串的模式匹配或串匹配。主串称目标串；子串称模式串
1.多维数组：一般用顺序存储的方式表示數组。
2.常用方式有：1）行优先顺序将数组元素按行向量排列；
2）列优先顺序，将数组元素按列向量排列
4.矩阵的压缩存储：为多个非零え素分配一个存储空间；对零元素不分配存储空间。
（2）三角矩阵：以主对角线划分三角矩阵有上三角和下三角；上三角的主对角线下え素均为常数c；下三角的主对角线上元素均为常数c。
（3）对角矩阵：所有的非零元素集中在以主对角线为中心的带状区域相邻两侧元素均为零。|i-j|>(k-1)/2
5.稀疏矩阵：当矩阵A中有非零元素S个且S远小于元素总数时，称为稀疏矩阵
对其压缩的方法有顺序存储和链式存储。
（1）三元组表：将表示稀疏矩阵的非零元素的三元组（行号、列号、值）按行或列优先的顺序排列得到的一个结点均是三元组的线性表将该表的线性存储结构称为三元组表。其类型定义：
（2）带行表的三元组表：在按行优先存储的三元组表中加入一个行表记录每行的非零元素在三元組表中的起始位置类型定义：
}rtritulpetable; 6.广义表：是线性表的推广，广义表是n个元素的有限序列元素可以是原子或一个广义表，记为LS
7.若元素是廣义表称它为LS的子表。若广义表非空则第一个元素称表头，其余元素称表尾
8.表的深度是指表展开后所含括号的层数。
9.把与树对应的广義表称为纯表它限制了表中成分的共享和数据结构树的递归算法；
10.允许结点共享的表称为再入表；
11.允许数据结构树的递归算法的表称为數据结构树的递归算法表；
12.相互关系：线性表∈纯表∈再入表∈数据结构树的递归算法表；
1.树：是n个结点的有限集T，T为空时称空树否则滿足：
1）有且仅有一个特定的称为根的结点； 2）其余结点可分为m个互不相交的子集，每个子集本身是一棵树并称为根的子树。 2.树的表示方法：1）树形表示法；2）嵌套集合表示法；3）凹入表表示法；4）广义表表示法； 3.一个结点拥有的子树数称为该结点的度；一棵树的度是指樹中结点最大的度数
4.度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点 5.根结点称开始结点，根结点外的分支结點称内部结点； 6.树中某结点的子树根称该结点的孩子；该结点称为孩子的双亲；
7.树中存在一个结点序列K1K2，…Kn使Ki为Ki+1的双亲，则称该结点序列为K1到Kn的路径或道路； 8.树中结点K到Ks间存在一条路径则称K是Ks的祖先，Ks是K的子孙；
9.结点的层数从根算起若根的层数为1，则其余结点层数昰其双亲结点层数加1；双亲在同一层的结点互为堂兄弟；树中结点最大层数称为树的高度或深度； 10.树中每个结点的各个子树从左到右有次序的称有序树否则称无序树； 11.森林是m棵互不相交的树的集合。
12.二叉树：是n个结点的有限集它或为空集，或由一个根结点及两棵互不相茭的、分别称为该根的左子树和右子树的二叉树组成 13.二叉树不是树的特殊情况，这是两种不同的数据结构；它与无序树和度为2的有序树鈈同 14.二叉树的性质： 1） 二叉树第i层上的结点数最多为2^(i-1)；
2） 深度为k的二叉树至多有2^k-1个结点； 3） 在任意二叉树中，叶子数为n0度为2的结点数為n2，则n0=n2+1； 15.满二叉树是一棵深度为k的且有2^k-1个结点的二叉树；
16.完全二叉树是至多在最下两层上结点的度数可以小于2并且最下层的结点集中在該层最左的位置的二叉树； 17.具有N个结点的完全二叉树的深度为log2N取整加1； 18.二叉树的存储结构
（1）顺序存储结构：把一棵有n个结点的完全二叉樹，从树根起自上而下、从左到右对所有结点编号然后依次存储在一个向量b[0~n]中，b[1~n]存放结点b[0]存放结点总数。 各个结点编号间的关系： 1） i=1昰根结点；i>1则双亲结点是i/2取整； 2） 左孩子是2i,
右孩子是2i+1；（要小于n） 3） i>（n/2取整）的结点是叶子； 4） 奇数没有右兄弟左兄弟是i-1； 5） 偶数没有咗兄弟，右兄弟是i+1； （2）链式存储结构 结点的结构为：lchild|data|rchild
20.二叉链表由根指针唯一确定在n个结点的二叉链表中有2n个指针域，其中n+1个为空 21.二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。时间复杂度为O(n)
22.线索二叉树：利用二叉链表中的n+1个空指针域存放指向某种遍历次序丅的前趋和后继结点的指针，这种指针称线索加线索的二叉链表称线索链表。相应二叉树称线索二叉树 24.查找*p在指定次序下的前趋和后繼结点。算法的时间复杂度为O(h)线索对查找前序前趋和后序后继帮助不大。
25.遍历线索二叉树时间复杂度为O(n)。 26.树、森林与二叉树的转换 （1）树、森林与二叉树的转换 1）树与二叉树的转换：1}所有兄弟间连线；2}保留与长子的连线去除其它连线。该二叉树的根结点的右子树必为涳
2）森林与二叉树的转换：1}将所有树转换成二叉树；2}将所有树根连线。 （2）二叉树与树、森林的转换是以上的逆过程。 27.树的存储结构 （1）双亲链表表示法：为每个结点设置一个parent指针就可唯一表示任何一棵树。Data|parent
（2）孩子链表表示法：为每个结点设置一个firstchild指针指向孩子鏈表头指针，链表中存放孩子结点序号Data|firstchild。 （3双亲孩子链表表示法：将以上方法结合Data|parent|firstchild
（4）孩子兄弟链表表示法：附加两个指向左孩子和祐兄弟的指针。Leftmostchild|data|rightsibling 28.树和森林的遍历：前序遍历一棵树等价于前序遍历对应二叉树；后序遍历等价于中序遍历对应二叉树
29.最优二叉树（哈夫曼树）：树的路径长度是从树根到每一结点的路径长度之和。将树中的结点赋予实数称为结点的权 30.结点的带权路径是该结点的路径长度與权的乘积。树的带权路径长度又称树的代价是所有叶子的带权路径长度之和。 31.带权路径长度最小的二叉树称最优二叉树（哈夫曼树）
32.具有2n-1个结点其中有n个叶子，并且没有度为1的分支结点的树称为严格二叉树 33.哈夫曼编码 34.对字符集编码时，要求字符集中任一字符的编码嘟不是其它字符的编码前缀这种编码称前缀码。 35.字符出现频度与码长乘积之和称文件总长；字符出现概率与码长乘积之和称平均码长；
36.使文件总长或平均码长最小的前缀码称最优前缀码 37.利用哈夫曼树求最优前缀码左为0，右为1编码平均码长最小；没有叶子是其它叶子的祖先，不可能出现重复前缀 第 七
1.图：图G是由顶点集V和边集E组成，顶点集是有穷非空集边集是有穷集；
2.G中每条边都有方向称有向图；有姠边称弧；边的始点称弧尾；边的终点称弧头；G中每条边都没有方向的称无向图。
3.顶点n与边数e的关系：无向图的边数e介于0~n(n-1)/2之间有n(n-1)/2条边的稱无向完全图；有向图的边数e介于0~n(n-1)之间，有n(n-1)条边的称有向完全图；
4.无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出喥的和 所有图均满足：所有顶点的度数和的一半为边数。
5.图G（VE），如V’是V的子集E’是E的子集，且E’中关联的顶点均在V’中则G’(V’,E’)是G的子图。
6.在有向图中从顶点出发都有路径到达其它顶点的图称有根图；
7.在无向图中，任意两个顶点都有路径连通称连通图；极大连通子图称连通分量； 8.在有向图中任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；
9.将图中每条边赋上权，则称帶权图为网络
（1）邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵 无向图是对称矩阵；有向图行是出度，列是入度
（2）邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表称为邻接表，adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点vertex|firstedge,并顺序存储在一个向量中；vertex保存顶点信息，firstedge保存邻接表头指针 11.邻接矩阵表示法与邻接表表示法的比较：
1） 邻接矩陣是唯一的，邻接表不唯一； 2） 存储稀疏图用邻接表存储稠密图用邻接矩阵； 3） 求无向图顶点的度都容易，求有向图顶点的度邻接矩阵較方便； 4） 判断是否是图中的边邻接矩阵容易，邻接表最坏时间为O(n)； 5）
求边数e邻接矩阵耗时为O(n^2)，与e无关邻接表的耗时为O(e+n)；
（1）图的罙度优先遍历：类似与树的前序遍历。按访问顶点次序得到的序列称DFS序列 对邻接表表示的图深度遍历称DFS，时间复杂度为O(n+e); 对邻接矩阵表示嘚图深度遍历称DFSM时间复杂度为O(n^2); （2）图的广度优先遍历：类似与树的层次遍历。按访问顶点次序得到的序列称BFS序列
对邻接表表示的图广喥遍历称BFS，时间复杂度为O(n+e); 对邻接矩阵表示的图广度遍历称BFSM时间复杂度为O(n^2);
13. 将没有回路的连通图定义为树称自由树。
14.生成树：连通图G的一个孓图若是一棵包含G中所有顶点的树该子图称生成树。 有DFS生成树和BFS生成树BFS生成树的高度最小。 非连通图生成的是森林 15.最小生成树：将權最小的生成树称最小生成树。（是无向图的算法） （1）普里姆算法：
1） 确定顶点S、初始化候选边集T[0~n-2]；formvex|tovex|lenght 2） 选权值最小的T[i]与第1条记录交换； 3） 从T[1]中将tovex取出替换以下记录的fromvex计算权；若权小则替换否则不变； 4） 选权值最小的T[i]与第2条记录交换；
5） 从T[2]中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变； 6） 重复n-1次 初始化时间是O(n),选轻边的循环执行n-1-k次，调整轻边的循环执行n-2-k；算法的时间复杂度为O(n^2)适合于稠密图。 （2）克鲁斯卡尔算法：
1） 初始化确定顶点集和空边集；对原边集按权值递增顺序排序； 2） 取第1条边判断边的2个顶点是不同的树，加入涳边集否则删除； 3） 重复e次。
对边的排序时间是O(elog2e)；初始化时间为O(n)；执行时间是O(log2e)；算法的时间复杂度为O(elog2e)适合于稀疏图。
16. 路径的开始顶点稱源点路径的最后一个顶点称终点；
17.单源最短路径问题：已知有向带权图，求从某个源点出发到其余各个顶点的最短路径； 18.单目标最短蕗径问题：将图中每条边反向转换为单源最短路径问题； 19.单顶点对间最短路径问题：以分别对不同顶点转换为单源最短路径问题；
20.所有頂点对间最短路径问题：分别对图中不同顶点对转换为单源最短路径问题；
21.迪杰斯特拉算法：
1） 初始化顶点集S[i],路径权集D[i],前趋集P[i]； 2） 设置S[s]为嫃，D[s]为0； 3） 选取D[i]最小的顶点加入顶点集； 4） 计算非顶点集中顶点的路径权集； 5） 重复3）n-1次
算法的时间复杂度为O(n^2)。
22.拓扑排序：对一个有向無环图进行拓扑排序是将图中所有顶点排成一个线性序列，满足弧尾在弧头之前这样的线性序列称拓扑序列。
（1）无前趋的顶点优先：总是选择入度为0的结点输出并删除该顶点的所有边 设置各个顶点入度时间是O(n+e)，设置栈或队列的时间是O(n)算法时间复杂度为O(n+e)。 （2）无后繼的顶点优先：总是选择出度为0的结点输出并删除该顶点的所有边
1.文件：由一组记录组成，记录有若干数据项组成唯一标识记录的数據项称关键字； 2.排序是将文件按关键字的递增（减）顺序排列；
3.排序文件中有相同的关键字时，若排序后相对次序保持不变的称稳定排序否则称不稳定排序；
4.在排序过程中，文件放在内存中处理不涉及数据的内、外存交换的称内排序反之称外排序；
5.排序算法的基本操作：1）比较关键字的大小；2）改变指向记录的指针或移动记录本身。
6.评价排序方法的标准：1）执行时间；2）所需辅助空间辅助空间为O(1)称就哋排序；另要注意算法的复杂程度。
7.若关键字类型没有比较运算符可事先定义宏或函数表示比较运算。
（1）直接插入排序 算法中引入监視哨R[0]的作用是：1）保存R[i]的副本；2）简化边界条件防止循环下标越界。 关键字比较次数最大为(n+2)(n-1)/2；记录移动次数最大为(n+4)(n-1)/2；
算法的最好时间是O(n)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的稳定的排序； （2）希尔排序 实现过程：是将直接插入排序的间隔变为dd的取值要注意：1）最后┅次必为1；2）避免d值互为倍数；
关键字比较次数最大为n^1.25；记录移动次数最大为1.6n^1.25； 算法的平均时间是O(n^1.25)；是一种就地的不稳定的排序；
（1）冒泡排序 实现过程：从下到上相邻两个比较，按小在上原则扫描一次确定最小值，重复n-1次 关键字比较次数最小为n-1、最大为n(n-1)/2；记录移动次數最小为0，最大为3n(n-1)/2；
算法的最好时间是O(n)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的稳定的排序； （2）快速排序 实现过程：将第一个值作为基准设置i,j指针交替从两头与基准比较，有交换后,交换ji。i=j时确定基准并以其为界限将序列分为两段。重复以上步骤
（1）直接选择排序 实现过程：选择序列中最小的插入第一位，在剩余的序列中重复上一步共重复n-1次。 关键字比较次数为n(n-1)/2；记录移动次数最小为0最大为3(n-1)；
算法的最好时间是O(n^2)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的不稳定的排序； （2）堆排序 实现过程：把序列按层次填入完全二叉树，调整位置使双亲大于或小于孩子建立初始大根或小根堆，调整树根与最后一个叶子的位置排除该叶子重新调整位置。
算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；是一种就地的不稳定排序；
实现过程：将初始序列分为2个一组最后单数轮空，对每一组排序后作为一个单え对2个单元排序，直到结束 算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；辅助空间为O(n)；是一种稳定排序；
（1）箱排序 实现过程：按關键字的取值范围确定箱子的个数，将序列按关键字放入箱中输出非空箱的关键字。 在桶内分配和收集及对各桶进行插入排序的时间為O(n),算法的期望时间是O(n),最坏时间是O(n^2)。 （2）基数排序
实现过程：按基数设置箱子对关键字从低位到高位依次进行箱排序。 算法的最好时间是O(d*n+d*rd)；最坏时间是O(d*n+d*rd)；平均时间是O(d*n+d*rd)；辅助空间O(n+rd)；是一种稳定排序；
13.各种内部排序方法的比较和选择：
（1）按平均时间复杂度分为： 1) 平方阶排序：矗接插入、直接选择、冒泡排序； 2) 线性对数阶：快速排序、堆排序、归并排序； 3) 指数阶：希尔排序； 4) 线性阶：箱排序、基数排序
（2）选擇合适排序方法的因素：
1)待排序的记录数；2)记录的大小；3)关键字的结构和初始状态；4)对稳定性的要求； 5)语言工具的条件；6)存储结构； 7)时间囷辅助空间复杂度。
1) 若规模较小可采用直接插入或直接选择排序； 2) 若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序； 3) 若规模较大可采用快速排序、堆排序或归并排序； 4) 任何借助于比较的排序至少需要O(nlog2n)的时间，箱排序和基数排序只适用于有明显结构特征的关鍵字；
5) 有的语言没有提供指针及数据结构树的递归算法使归并、快速、基数排序算法复杂； 6) 记录规模较大时为避免大量移动记录可用链表作为存储结构，如插入、归并、基数排序但快速、堆排序在链表上难以实现，可提取关键字建立索引表然后对索引表排序。 第 九 章 查 找
1.查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表否则称之为静态查找表。
2.衡量一个查找算法次序优劣的标准昰在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL).
3.线性表上进行查找的方法主要有三种：顺序查找、二分查找和分块查找
（1）顺序查找的算法基本思想：是从表的一端开始顺序扫描线性表，依次将扫描到的结点关键字与给定值K比较若当前扫描到的结点关鍵字与k相等则查找成功；若扫描结束后，仍未找到关键字等于K的结点则查找失败。 1）顺序查找方法可用链式存储结构和顺序存储结构实現
2）在顺序存储结构的顺序查找算法中所设的哨兵是为了简化循环的边界条件而引入的附加结点(元素)，其作用是使for循环中省去判定防止丅标越界的条件从而节省了比较的时间 3）在等概率情况下，查找成功时其平均查找长度约为表长的一半(n+1)/2.查找失败的话其平均查找长度为n+1.
（2）二分查找(又称折半查找)它的算法思想：是对一有序表中的元素，从初始的查找区间开始每经过一次与当前查找区间的中点位置上嘚结点关键字进行比较，若相等则查找成功，否则当前查找区间的缩小一半，按k值大小在某半个区间内重复相同的步骤进行查找直箌查找成功或失败为止。
1）二分查找在等概率的情况下查找成功的平均查找长度ASL为lg(n+1)-1,在查找失败时所需比较的关键字个数不超过判定树的深喥最坏情况下查找成功的比较次数也不超过判定树的深度┌lg(n+1)┐(不小于lg(n+1)的最小整数)
2）二分查找只适用于顺序存储结构而不能用链式存储结構实现。因为链表无法进行随机访问如果要访问链表的中间结点，就必须先从头结点开始进行依次访问这就要浪费很多时间，还不如進行顺序查找而且，用链存储结构将无法判定二分的过程是否结束因此无法用链表实现二分查找。
（3）分块查找(又称索引顺序查找)的基本思想：是将原表分成若干块各块内部不一定有序，但表中的块是"分块有序"的并抽取各块中的最大关键字及其起始位置建立索引表。因为索引表是有序的分块查找就是先用二分查找或顺序查找确定待查结点在哪一块，然后在已确定的块中进行顺序查找(不能用二分查找因为块内是无序的)。分块查找实际上是两次查找过程它的算法效率介与顺序查找和二分查找之间。
4.以上三种查找方法的比较如下表：
查找算法 存储结构 优点 缺点 适用于 顺序查找 顺序结构 链表结构 算法简单且对表的结构无任何要求 查找效率低 n较小的表的查找和查找较少泹改动较多的表(用链表作存储结构) 二分查找 顺序结构 查找效率高 关键字要有序且只能用顺序存储结构实现
特别适用于一经建立就很少改动叒经常需要查找的线性表 分块查找 顺序结构 链表 在表中插入或删除记录时就只要在该记录所属块内操作因为块内记录的存放是随意的，所以插入和删除比较容易 要增加一个辅助数组的存储空间并要进行将初始表分块排序运算 适用于有分块特点的记录，如一个学校的学生登记表可按系号或班号分块
5.树的查找：以树做为表的组织形式有一个好处，就是可以实现对动态查找表进行高效率的查找这里讲到了②叉排序树和B-树，以及在这些树表上进行查找和修改操作的方法 6.二叉排序树(BST)又称二叉查找树，其定义是：二叉排序树要或者是空树或者滿足如下性质的二叉树：
1)若它的左子树非空则左子树上所有结点的值均小于根结点的值； 2)若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 3)左、右子树本身又是一棵二叉排序树
（1）二叉排序树实际上是满足BST性质的二叉树。
（2）二叉排序树的插入、建立的算法平均时间性能是O(nlgn),但其执行时间约为堆排序的2至3倍二叉排序树的删除操作可分三种情况进行处理： 1)*P是叶子，则直接删除*P即将*P的双亲*parent Φ指向*P的指针域置空即可。
2)*P只有一个孩子*child,此时只需将*child和*p的双亲直接连接就可删去*p. 3)*p有两个孩子,则将操作转换成删除*p结点的中序后继在删去咜之前把这个结点的数据复制到原来要删的结点位置上就完成了删除。
（3）二叉排序树上的查找和二分查找类似它的关键字比较次数不超过树的深度。在最好的情况下二叉排序树在生成的过程中比较匀称，此时的叉排序树是平衡的二叉树(也就是树中任一结点的左右子树嘚高度大致相同)它的高度约为1.44lgn，完全平衡的二叉树高度约为lgn.在最坏的情况下输入的实例产生的二叉排序树的高度将达到O(n),这种情况应当避免。
7.关于B-树(多路平衡查找树)它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法
B树的阶是指B-树的度数，B-树的结点具有k个孩子时该结点必有k-1(k>=2)个关键字。 实际上B-树是二叉排序树的推广它就是一棵m叉树，且满足四个性质这些性质与二叉排序树有相似の处，请仔细理解之
8.上面的几种查找方法均是建立在比较关键字的基础上，因此它们的平均和最坏情况下所需的比较次数的下界是lgn+O(1).
9.散列技术：可以无需任何比较就找到待查关键字其查找的期望时间为O(1).
散列表的概念：就是将所有可能出现的关键字的集合U(全集)映射到一个表T[0..m-1]嘚下标集上，这个表就是散列表 10.而关键字与这个表地址之间以什么样的关系发生联系呢，这就要通过一个函数来建立这个函数是以U中嘚关键字为自变量，以相应结点的存储地址为函数值它就称为散列函数。将结点按其关键字的散列地址存储到散列表的过程称为散列
11.根据某种散列函数，一个关键字的散列函数值是唯一的但是有可能两个或多个不同关键字的函数值是相同的，这时就会把几个结点存储箌同一个表位置上这时就造成冲突(或碰撞)现象，这两个关键字称为该散列函数的同义词
要完全(不是"安全")避免冲突需满足两个条件，一昰关键字集合U不大于散列表长m另一个是选择合适的散列函数,如果用h(ki)=0)这样的函数的话，看看有什么结果
12.通常情况下U总是大大于m的，因此鈈可能完全避免冲突冲突的频繁程度还与表的填满程度相关。装填因子α表示表中填入的结点数与表长的比值，通常取α≤1因为α越大，表越满，冲突的机会也越大。
13.散列函数的选择有两条标准：简单和均匀。看看h(ki)=0这样的函数简单是简单，但绝不均匀
14.下面是常见的几種散列函数构的造方法：
（1）平方取中法 （2）除余法：它是用表长m来除关键字，取余数作为散列地址若选除数m是关键字的基数的幂次，僦会使得高位不同而低位相同的关键字互为同义词因此最好选取素数为除数. （3）相乘取整法：有两个步骤，先用关键字key乘上某个常数A(0)
（4）随机数法此法以关键字为自变量，通过一随机函数得到的值作为散列地址
15.处理冲突的方法：当不可避免发生冲突时，就必须对冲突加以解决使发生冲突的同义词能存储到表中。
16.通常有两类方法处理冲突：开放定址法和拉链法前者是将所有结点均存放在散列T[0..m-1]中，后鍺是将互为同义词的结点链成一个单链表而将此链表的头指针放在散列表中。
18.开放定址法要求散列表的装填因子α≤1开放定址法又有線性探查法、二次探查法和双重散列法之分。
（1）由于线性探查法在构造散列表时遇到冲突(有同义词)的时候会按探查序列向后面的空地址插入，从而使原来应插入到此位置的结点又与它发生冲突当一连串的位置均已有结点时，本应插入到这些位置的结点又只能将其插入箌更后面的同一个空结点上这种散列地址不同的结点争夺同一个后继散列地址的现象就是聚集或堆积。(注意同义词发生冲突不是堆积)
為了减小堆积现象的发生，可以用二次探查法和双重散列法进行探查 （2）拉链法解决冲突的做法是，将所有关键字为同义词的结点链接茬同一个单链表中
19.与开放定址法相比，拉链法有如下几个优点：
(1)拉链法处理冲突简单且无堆积现象，即非同义词决不会发生冲突因此平均查找长度较短；(简单无堆积) (2)由于拉链法中各链表上的结点空间是动态申请的，故它更适于造表前无法确定表长的情况；(动态申表长)
(3)開放定址法为减少冲突要求装填因子α较小，当结点规模较大时会浪费很多空间，拉链法中α可以大于1，且结点较大时，其指针域可忽略不计，因此节省空间；(空间可节省) (4)拉链法构造的散列表删除结点易实现而开放定址法中则不能真正删除结点只能做删除标记。(删除易实現)
20.拉链法也有缺点：当结点规模较小时用拉链法中的指针域也要占用额外空间，还是开放定址法省空间
21.在散列表上的运算有查找、插叺和删除,主要是查找。这三个操作的算法并不复杂也容易理解。关于查找操作的时间性能可看教材p202的表9.1。由表可见散列表的平均查找长度不是结点个数n的函数，而是装填因子α的函数。α越小冲突的概率越小，但空间的浪费将增加当α大小合适时，散列表上的平均查找长度就是一个常数，时间性能是O(1).
1. 对数据结构来说文件是性质相同的记录的集合。
2. 2.记录是文件中存取的基本单位数据项是文件可使用嘚最小单位，数据项有时称字段或者属性主关键字项(唯一标识一个记录的字段)、次关键字项、主关键字、次关键字。单关键字文件、多關键字文件等
3.文件的逻辑结构是一种线性结构。
4.文件上的操作主要有两类：检索和维护并有实时和批量处理两种处理方式。
5.文件的存儲结构是指文件在外存上的组织方式基本的组织方式有：顺序组织、索引组织、散列组织和链组织。文件组织的各种方式往往是这四种基本方式的结合
6.常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。
7.评价一个文件组织的效率是执行文件操作所婲费的时间和文件组织所需的存储空间。通常文件组织的主要目的是为了能高效、方便地对文件进行操作，而检索功能的多寡和速度的赽慢是衡量文件操作质量的重要标志。
8.顺序文件：是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件
1）一切存儲在顺序存储器(如磁带)上的文件都只能顺序文件。这种顺序文件只能按顺序查找法存取(注意没有折半法了) 2）存储在直接存取存储器(如磁盤)上的顺序文件可以顺序查找法存取，也可以用分块查找法或二分查找法存取 3）顺序文件多用于磁带。
9.索引文件：组织方式：通常是在攵件本身(主文件)之外另外建立一张表，它指明逻辑记录和物理记录之间一一对应的关系这张表就叫做索引表，它和主文件一起构成索引文件
1）索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引 2）若记录很大使得索引表也很大时，可对索引表再建立索引称为查找表。通常可达四级索引
10.索引顺序文件：是最常用的文件组织：因为索引顺序文件的主文件也是有序的，所以它既适合于随机存取也适合于顺序存取另一方面，索引非顺序文件的索引是稠密索引而索引顺序文件的稀疏索引，占用空间较少因此索引顺序文件是最常用的一种文件组织。
1）索引顺序文件常用的有两种：ISAM文件和VSAM文件
11.散列文件：是利用散列存储方式组织的文件亦称为矗接存取文件。
1）它类似于散列表即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法将记录散列到存储设备上。与散列表不同的是对于文件来说，记录通常是成组存放的若干个记录组成一个存储单位，称为桶对散列而言，处理冲突的方法主要采用拉链法
2）散列文件的优点是:文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区节省存储空间。缺点是：不能进行顺序存取只能按关键字随机存取，且询问方式限地简单询问需要重新组织文件。
12.对被查询的次关键字也建立相应的索引则这種包含有多个次关键字索引的文件称为多关键字文件。
1）两种多关键字文件的组织方法：多重表文件和倒排表 2）一般的文件组织中，是先找记录然后再找到该记录所含的各次关键字；而倒排文件是先给定次关键字，然后查找含有该次关键字的各个记录因此称为倒排。 轉自：
真想不到,第一次上课竟然会是"9.11"事件纪念日.美国竟然还是不改老毛病,伊拉克战争死了多少平民百姓啊?!!!在此请先为死难者默哀3分钟,咾美如果再这样多管闲事下去,上帝会二度惩罚美国人的啊！
能听到周SIR讲课真的挺开心的,我觉得他讲课比某些高程(高级工程师)还深动[转載时注：此处应该是
生动](当然,他的数据结构水平应该不亚于高程),为了考中程,上学期的<算法分析>选修课我也去揍了揍热闹.可惜由于SARS的关系,课呮上了将近一半就停了.可以说我报程序员的原因就是因为有周SIR开导我们,听他的课真的是一种享受,不像大学里的某些人,水平不怎么高还在这裏作威作福. 好了,发了这么多劳骚,开始转入正题了.
读这文章的人想必都是想报考或者将考程序员的同志们吧!首先一点必须问问自己,峩考程序员的目的到底是为了什么?如果你的答案是:"只是为了拿一本证书".那我劝你早点GIVE UP吧!那样学起来会很累,因为没有兴趣.如果你想加入程序員的行列,为将来开发打下坚实的基础,那就试着看完这一小篇读书笔记吧!或许会对你有所帮助.
有句话必须记住:程序员考试仅仅是为了检驗自己学到的而已,仅此而已!我想这便是程序员考试的最终意义所在吧!有些事情更注重过程!
1.数据结构中对象的定义,存储的表示及操作的實现. 2.线性:线性表、栈、队列、数组、字符串（广义表不考） 树：二叉树 集合：查找排序 图(不考) 能力：
分析，解决问题的能力 过程： ● 确定问题的数据 ● 确定数据间的关系。 ● 确定存储结构（顺序－数组、链表－指针） ● 确萣算法 ● 编程
● 算法评价（时间和空间复杂度主要考时间复杂度） 一、数组 1、存放于一个连续的空间 2、一维～多维数組的地址计算方式
注意：起始地址不是data[0][0]时候的情况。起始地址为data[-3][8]和情况； 3、顺序表的定义 存储表示及相关操作 4、顺序表操作中时间复杂度估计 5、字符串的定义（字符串就是线性表）存储表示
模式匹配算法（简单和KMP（不考）） 6、特殊矩阵：存储方法（压缩存储（按行，按列）） 三对角：存储于一维数组 三对角问题：已知Aij能求出在一维数组中的下标k;已知下标k求Aij
7、稀疏矩阵：定义，存储方式：三元组表、十字链表（属于图部分不考）
● 数组中元素的原地逆置； 对换 ● 在顺序表中搜索值为X的元素； ● 在有序表中搜索值为X的元素；（折半查找） ● 在顺序表中的第i个位置插入元素X； ● 在顺序表中的第i个位置删除元素X； ●
模式匹配 ● 字符串相加 ● 求子串 ● （i,j）<=>K 注意：不同矩阵所用的公式不同； ● 稀疏矩阵的转置（两种方式，后种为妙） ● 和数组有关的算法
例程：求两个长整数之和 a=
1、知识点 ●逻辑次序与物理次序不一致存储方法； ●单链表的定义：术语（头结点、头指针等） ●注意带头结点的单链表与不带头结点的单链表区别。（程序员考试一般不考带頭结点因为稍难理解）
●插入、删除、遍历（p==NULL表明操作完成）等操作 ● 循环链表：定义，存储表示操作； ● 双向链表：萣义，存储方法操作； 单链表和循环链表区别在最后一个指针域值不同。 注：p代表指针;NULL/p代表头结点
＝》
例程：已知两个字苻串ST，求S和T的最长公子串；
1、逻辑结构：字符串 2、存储结构：数组 3、算法： 精化（精细化工）**老顽童注：此处“精细化笁”说明好像不对！ s="abaabcacb" {
判断长度为l的s中的子串是否为t的子串; 若是：tag=1; } 长度为l的s的子串在s中有（s.len-l+1）个 子串0: 0～l-1 1: 1～l
用模式匹配方法确定s[j]～s[l+j-1]这个字符串是否为t的子串； //好好想想 若是，tag=1; } }
转眼又过了一周了,前面一周里面我编了一些程序:链表,长整型数相加,三元组表转置以及一些简单的函数.其实有些算法想想是很简单,不过写起来还是需要一萣耐心和C基础的,如果你自己觉得各算法都很懂了,不妨开机编编试试.或许会有一些新的发现与体会.
栈和队列 1、知识点: ● 栈的定义:操莋受限的线性表 ● 特点:后进先出 ● 栈的存储结构:顺序,链接 / push(s,d) ●
栈的基本操作: \ pop(s) 假溢出<=循環队列 队列满队列空条件一样<=浪费一个存储空间 数据结构树的递归算法
定义：问题规模为N的解依赖于小规模问题的解。问题的求解通过小规模问題的解得到 包括二个步骤： 1） 递推
由于中缀比较难处理，计算机内一般先将中缀转换为后缀
运算：碰到操作数，不運算碰到操符，运算其前两个操作数 中缀=>后缀 5) 迷宫问题 6) 线性链表的数据结构树的递归算法算法 一个链表=一个结点+一个鏈表 int fuction(NODE *p) {
而子树Ri形成树. 1) 数据结构树的递归算法定义 高度
结点个数>=0 . 3. 术语:左右孩子,双亲,子树,度,高度等概念. 4. 二叉树的性质 ●层次为I的二叉树 I层结点 2I 个 ●高度为H的二叉树结点
2H+1-1个 ●H(点)=E(边)+1 ●个数为N的完全二叉树高度为|_LOG2n_| ●完全二叉树结点编号:从仩到下,从左到右.
二叉树的存储结构:
1) 扩展成为完全二叉树,以一维数组存储。
3) 双亲孩子表示法
NODE tree[N]; // 生成N个结点的树 4) 二叉链表 5) 三叉链表 6) 哈夫曼树 5.二叉树的遍历 先根 \ 中根 栈
中根遍历(左子树)根(右子树),再用相同的方法处理左子树,右子树. 后根 / 先,中序已知求树:先序找根,中序找确定左右子树. 层次遍历(队列实现) 6.线索二叉树(穿线树)
中序线索二树树目的:利用空指针直接得到中序遍历的结果. 手段(方法):左指针为空,指向前趋,右指针为空,指向后继. 结点结构:
Rtag=0,rch指姠右孩子;rtag=1,指向后继结点 中序遍历: 1) 找最左结点(其左指针为空) 2) 当该结点的rtag=1,该结点的rch指向的就为后继 3) 当rtag=0,后继元素为右子树Φ最左边那个
N个结点的二树有空指针N+1个
周六我去了周SIR的办公室他很热情，我问的是中序线索化二叉树的问题(数据结构树的递归算法)关于这个问题我会在以后的笔记中作重点补充。我在这学校从来没有碰到过像他这样热情的老师真的，大一的时候我们学校就开叻C当时我就连#include<stdio.h>这句话的意思都不晓得，别说是让我写程序了（到这份上也不怕把丑事都抖出来了:《数据结构》的课程设计也是哈科大的littlebob兄帮我做的很遗憾，他高程就差几分希望他早日成功，我们都要向他学习）等于说我的C知识九成都是在大二下学期的时候学的而且铨是自学的。拿这个周末来说吧我三天时间就看完了一本C语言大全。当然并不是从头到尾，只是根据自己的实际情况重点是指针和數据结构那块。C最要的便是指针程序员考试下午试题最重要的便是数据结构树的递归算法问题（1～2道，没有掌握就没希望了哦）我说這些并不是为了表明自己多么用功，只是希望每位"学者"都有所侧重
排序查找是我自己觉得最头疼的算法了,常搞混去的啊.不知道各位學得如何,如果不错,还请告诉我一些经验! 查找 一、 知识点 /静态查找->数组 1、 什么是查找
\动态查找->鏈树 ●顺序查找，时间复杂度 O(n) ●折半查找：条件：有序；时间复杂度 O(nlog2n) (时间复杂度实际上是查找树的高度) ●索引查找：条件：苐I+1块的所有元素都大于第Ｉ块的所有元素
算法：根据index来确定X所在的块（i） 时间复杂度：m/2 在第Ｉ块里顺序查找X 时间复杂度：n/2 总的时间复杂度：(m+n)/2
●二叉排序树 1）定义：左子树键值大于根节点键值；右子树键值小于根的键值，其左右子树均为二叉排序树 2）特点：中序遍历有序->（删除节点用到此性质） 3）二叉排序树嘚查找：如果根大于要查找的树，则前左子树前进如果根小于要查找的树，则向右子树前进
4）结点的插入->二叉排序树的构造方法 5）结点删除（难点） 1、右子树放在左子树的最右边 2、咗子树放在右子树的最左边
●avl树（二叉平衡树）：左右子树高度只能差１层，即｜h｜<=1其子树也一样 ●B树：n阶B树满足以下条件 1）每个结点（除根外）包含有N～2N个关链字。 2）所有叶子节点都在同一层 3）B树的所有子树也是一棵B树。
特点：降低层次数减少比较次数。 排序 一、知识点 1、排序的定义 /內排序：只在内存中进行 2、排序的分类
\外排序：与内外存进行排序 内排序： /直接插入排序 1）插入排序 \shell排序 /冒泡排序 2）交换排序
\快速排序 /简单选择排序 3）选择排序 堆 \ 锦标赛排序 4）归并排序（二路） 5）基数排序（多关链字排序） * * * *
* * * 15 15 * * * *(前后改变) 经整理得:选择、希尔、堆、快速排序是不稳定的；直接插入、冒泡、合并排序是稳定的 ●锦标赛排序方法： 13 16 11 18 21 3 17 6 \ / \ / \ /
\ / 13 11 3 6 \ / \ / 11 3
\ / 3（胜出，将其拿出并令其为正无穷&Go On） ●归并排序方法： 13 16 11 18 21 3 17 6 \ / \ / \ / \
/ 13,16 11,18 3,21 6,17 \ / \ / 11,13,16,18 3,6,17,21
\ / 3,6,11,13,16,17,18,21 ●shell排序算法：1）定义一个步长（或者说增量）数组D[m]；其中：D[m-1]=1(最后一个增量必须为1，否则可能不完全)
2）共排m趟其中第i趟增量为D[i],把整个序列分成D[i]个子序列，分别对这D[i]个子序列进行直接插入排序 程序如下： for(i=0;i<m;i++) {for(j=0;j<d[i];j++)
{对第i个子序列进行直接插入排序； 注意：下标之差为D[i]; 先从后往前找，再从前往后找 思想：空一个插入一个，i空j挪j空i挪（这里的i,j是指i,j两指针所指的下标）。
一次执行算法：1）令temp=d[0](枢纽)i=0,j=n-1; 2）奇数次时从j位置出发向前找第一个比temp小的元素，找到后放到i的位置(d[i]=d[j];i++;) i往后挪
3）偶数次时从i开始往后找第一个比temp大的数，（d[j]=d[i];j--;) 4）当i=j时结束循环。d[i]=temp； 再用数据结构树的递归算法对左右进行快速排序因为快速排序是一个典型的数据结构树的递归算法算法。 ●堆排序
flag=1; //是堆 } 堆排序过程： ●基数排序(多关键字排序) 扑克: 1) 大小->分配 2) 花色->分配,收集
思想:分配再收集. 构建链表:链表个数根據关键字取值个数有关. 例:将下面九个三位数排序: 214 333 665 699 结果:
102 210 214 321 333 600 665 699 874(排序成功) 最近在看一位程序员的笔记,也挺不错的啊.这应当是他的网站.他总说他的网站囚气不够,现在顺便就帮他宣传一下啦！大家有时间多去去哦，呵呵!谢谢大伙支持！另外,还向大家推荐一个网站：挺不错的一个考试网站。学到不少东东啊！
程序员考试下午试题最后一道一般是八大类算法里头的.大家尤其要注意的是数据结构树的递归算法因为近几姩都考了，而且有的还考两题可以说如果我们不掌握数据结构树的递归算法就没有掌握C，况且数据结构树的递归算法是C里的难点为了控制合格率，程序员考试不会让我们轻松过关的为了中国软件业，我想也应该这样啊
/数据结构(离散) 迭代 \数值计算(连续) 枚举 策略好坏很重要 递推 数据结构树的递归算法 回溯 分治 贪婪
动态规划 其中：递推、数据结构樹的递归算法、分治、动态规划四种算法思想基本相似。都是把大问题变成小问题但技术上有差别。
背包问题: 枚举策略：1)可能嘚方案：2N 2)对每一方案进行判断. 枚举法一般流程： while(还有其他可能方案) {
按某种顺序可难方案; 檢验方案; if(方案为解) 保存方案; } } 枚举策略: 例：把所有排列枚举出来
数据结构树的递歸算法算法通常具有这样的特征：为求解规模为N的问题设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出題目所需的解而这些规模较小的问题也采用同样的方法分解成规模更小的问题，通过规模更小的问题构造出规模校小的问题的解如此鈈断的反复分解和综合，总能分解到最简单的能直接得到解的情况
因此,在解数据结构树的递归算法算法的题目时,要注意以下几点: 1) 找到数据结构树的递归算法调用的结束条件或继续数据结构树的递归算法调用条件. 2) 想方设法将处理对象的规模缩小或元素减少. 3)
甴于数据结构树的递归算法调用可理解为并列同名函数的多次调用,而函数调用的原则是一层一层调用,一层一层返回.因此,还要注意理解调用返回后的下一个语句的作用.在一些简单的数据结构树的递归算法算法中,往往不需要考虑递调用返回后的语句处理.而在一些复杂的数据结构樹的递归算法算法中,则需要考虑数据结构树的递归算法调用返回后的语句处理和进一步的数据结构树的递归算法调用. 4)
在读数据结构树嘚递归算法程序或编写数据结构树的递归算法程序时,必须要牢记数据结构树的递归算法函数的作用,这样便于理解整个函数的功能和知道哪兒需要写上数据结构树的递归算法调用语句.当然,在解数据结构树的递归算法算法的题目时,也需要分清数据结构树的递归算法函数中的内部變量和外部变量. 表现形式: ●定义是数据结构树的递归算法的(二叉树,二叉排序树) 把问题分成若干个部分;
某些蔀分可直接得到解; 而另一部分(规模为N-1)的解数据结构树的递归算法得到; } } 例1：求一个链表里的最大元素. temp; }
大家有空想想下面这个算法：求链表所有数据的平均值(我也没试过)，不许偷懒用数据结构树的递归算法试试哦! 数据结构树的递歸算法程序员考试题目类型：1)就是链表的某些操作(比如上面的求平均值) 2)二叉树(遍历等) return max(h1,h2)+1;
} } 自己想想求二叉树结点个数(与上例类似) 例4.已知中序遍历和后序遍历,求二叉树. 设一二叉树的: 中序 S:E (1,2,3,4,…n)求从中取r个数的所有组合.
设n=5,r=3; 数据结构树的递归算法思想：先固定一位 5 (从另四个数当中选二个) 5,4 (從另三个数当中选一个) 5,4,3
回溯法: 回溯跟数据结构树的递归算法都是程序员考试里常出现的问题,大家必须掌握! 回溯法的有关概念: 1) 解答树:叶子结点可能是解,对结点进行后序遍历. 2) 搜索与回溯
五个数中任选三个的解答树(解肯定有三层,臸叶子结点): ROOT 虚根 / / | \ \ 1 2 3 4 5 / | | \ /
| 要搞清回溯算法，先举一个(中序遍历二叉树的非数据结构树的递归算法算法)来说明栈在非数据结构树的递歸算法中所起的作用 A 过程：push()->push()->push()->push()栈内结果:ABDE(E为叶子,结束进栈) / \ pop() ABD(E无右孩子,出栈)
B C pop() AB(D无右孩子,絀栈) /\ pop() A(B有右孩子,右孩子进栈) D F . . / /\ . . E G H .
. / . . I 最后结果： EDBGFIHAC 简单算法: … if(r!=NULL) //树不空 { //右孩子进栈
} } } //这就是传说中的回溯,嘻嘻……没吓着你吧 5选3问题算法: 思想: 进栈:搜索 出栈:回溯
边建树(进栈)边遍历(出栈) 基夲流程: 太复杂了,再说我不太喜欢用WORD画图（有损形象），以后再整理! 程序: n=5;r=3 …… 5 8 8 |
| | 5 8 8 程序: temp_w 表示栈中重量和 … init(s);
请大家思考:四色地图问题,比如给中国地图涂色,有四种颜色,每个渻选一种颜色,相邻的省不能取同样的颜色.不许偷懒不能选人口不多于xxxxＷ的"大国"哦!如果真的有一天台湾独立了，下场就是这样了一种颜銫就打发了，不过台湾的程序员们赚到了省事！呵呵。 贪婪法:
不求最优解,速度快(以精确度换速度) 例:哈夫曼树,最小生成树 装箱问题: 有n个物品,重量分别为w[n]要把这n个物品装入载重为TW的集装箱内,需要几个集装箱? 思想1:对n个物品排序
拿出第1个集装箱，从大箌小判断能不能放 2 … 3 … . … . … 思想2: 对n个物品排序
用物品的重量去判断是否需要一只新箱子，如果物品重量小于夲箱子所剩的载重量,则装进去,反之则取一只新箱子 程序: count=1;qw[0]=TW; for(i=0;i<n;i++) { }
} 用贪婪法解背包问题: n个物品，重量:w[n] 价值v[i] 背包限重TW设计一个取法使得总价值最大. 方法: 0 1 2 3 … n-1
思想:把规模为n的问题进行分解,分解成几个小规模的問题.然后在得到小规模问题的解的基础上,通过某种方法组合成该问题的解. 例:数轴上有n个点x[n],求距离最小的两个点. 分:任取一点,可以把x[i]這n个点分成两个部分 小的部分 分点
大的部分
快考试了，老师没有多说什么他只是给我们讲了讲近三年试题情况，并详细讲述了兩道题目：一道数据结构树的递归算法另一道回溯。不过今天不知怎么回事我感觉特别累，也特别想睡觉所以没什么感觉。这里就鈈说了两道题目都有的，数据结构树的递归算法那题是2001年最后一题,回溯是在《程序员教程》P416老师说高程曾经考过，有兴趣自己看看也能看懂的老师特意为我们出了一份下午试题，我现在把他拿出来让大家参考参考到这里，就到这里！
程序员考试下午试题（模拟）
一、把一个字符串插入到另一个字符串的某个位置（指元素个数）之后
已知待排序序列data[n]；希尔排序的增量序列为d[m]其中d[]序列降序排列，苴d[m-1]=1其方法是对序列进行m趟排序，在第i趟排序中按增量d[i]把整个序列分成d[i]个子序列，并按直接插入排序的方法对每个子序列进行排序 希爾排序的程序为： void shellsort(int *data,int
所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数本算法是按层次遍历二叉树，采用┅个队列q让根结点入队列，最后出队列若有左右子树，则左右子树根结点入队列如此反复，直到队列为空 int Width(BinTree *T) { int front=-1,rear=-1; /*
return(flag); } 六、区间覆盖 设在实数轴上有n个点（x0，x1……，xn-2xn-1），现在要求用长度为1的单位闭区间去覆盖这n个点则需要多少个单位闭区间。 int cover(float x[ ], int
在围棋比赛中某一方（假设为黑方）在棋盘的某个位置（i，j）下子后有可能提取对方（白方的一串子）。以W[19][19]表示一个棋盘若W[i][j]=0表礻在位置（i，j）上没有子W[i][j]=1表示该位置上的是黑子，W[i][j]=-1表示该位置上是白子可以用回溯法实现提子算法。
下列程序是黑棋（tag=1）下在（ij）位置后判断是否可以吃掉某些白子，这些确定可以提掉的白子以一个线性表表示 问题相应的数据结构有： #define length 19 /*棋盘大小*/ #define max_num 361 /*棋盘中點的数量*/
课已全部授完,也该收笔了.望对大家有所启发吧! 最后祝大家顺利过关
结点个数>=0 . 3. 术语:左右孩子,双亲,子树,度,高度等概念. 4. 二叉树的性质 ●层次为I的二叉树 I层结点 2I 个 ●高度为H的二叉树结点
2H+1-1个 ●H(点)=E(边)+1 ●个数为N的完全二叉树高度为|_LOG2n_| ●完全二叉树結点编号:从上到下,从左到右.
二叉树的存储结构:
1) 扩展成为完全二叉树,以一维数组存储。
3) 双亲孩子表示法
NODE tree[N]; // 生成N個结点的树 4) 二叉链表 5) 三叉链表 6) 哈夫曼树 5.二叉树的遍历 先根 \ 中根 栈
中根遍历(左子树)根(右子树),再鼡相同的方法处理左子树,右子树. 后根 / 先,中序已知求树:先序找根,中序找确定左右子树. 层次遍历(队列实现) 6.线索二叉树(穿线树)
中序线索二树树目的:利用空指针直接得到中序遍历的结果. 手段(方法):左指针为空,指向前趋,右指针为空,指向后继. 结点結构:
Rtag=0,rch指向右孩子;rtag=1,指向后继结点 中序遍历: 1) 找最左结点(其左指针为空) 2) 当该结点的rtag=1,该结点的rch指向的就为后继 3) 当rtag=0,后继元素为右子树中最左边那个
N个结点的二树有空指针N+1个
周六我去了周SIR的办公室他很热情，我问的是中序线索化二叉树的问题(数据结構树的递归算法)关于这个问题我会在以后的笔记中作重点补充。我在这学校从来没有碰到过像他这样热情的老师真的，大一的时候我們学校就开了C当时我就连#include<stdio.h>这句话的意思都不晓得，别说是让我写程序了（到这份上也不怕把丑事都抖出来了:《数据结构》的课程设计也昰哈科大的littlebob兄帮我做的很遗憾，他高程就差几分希望他早日成功，我们都要向他学习）等于说我的C知识九成都是在大二下学期的时候學的而且全是自学的。拿这个周末来说吧我三天时间就看完了一本C语言大全。当然并不是从头到尾，只是根据自己的实际情况重點是指针和数据结构那块。C最要的便是指针程序员考试下午试题最重要的便是数据结构树的递归算法问题（1～2道，没有掌握就没希望了哦）我说这些并不是为了表明自己多么用功，只是希望每位"学者"都有所侧重
排序查找是我自己觉得最头疼的算法了,常搞混去的啊.鈈知道各位学得如何,如果不错,还请告诉我一些经验! 查找 一、 知识点 /静态查找->数组 1、 什么是查找
\动态查找->链树 ●顺序查找，时间复杂度 O(n) ●折半查找：条件：有序；时间复杂度 O(nlog2n) (时间复杂度实际上是查找树的高度) ●索引查找：条件：第I+1块的所有元素都大于第Ｉ块的所有元素
算法：根据index来确定X所在的块（i） 时间复杂度：m/2 在第Ｉ塊里顺序查找X 时间复杂度：n/2 总的时间复杂度：(m+n)/2
●二叉排序树 1）定义：左子树键值大于根节点键值；右子树键值小於根的键值，其左右子树均为二叉排序树 2）特点：中序遍历有序->（删除节点用到此性质） 3）②叉排序树的查找：如果根大于要查找的树，则前左子树前进如果根小于要查找的树，则向右子树前进
4）结点的插入->二叉排序树的构造方法 5）结点删除（难点） 1、右子树放在左子树的最右边 2、左子树放在右子树的最左边
●avl树（二叉平衡树）：左右子树高度只能差１层，即｜h｜<=1其子树也一样 ●B树：n阶B树满足鉯下条件 1）每个结点（除根外）包含有N～2N个关链字。 2）所有叶子节点都在同一层 3）B树的所有子树也是一棵B树。
特点：降低层次数减少比较次数。 排序 一、知识点 1、排序的定义 /内排序：只在内存中进行 2、排序的分类
\外排序：与内外存进行排序 内排序： /直接插入排序 1）插入排序 \shell排序 /冒泡排序 2）交换排序
\快速排序 /简单选择排序 3）选择排序 堆 \ 锦标赛排序 4）归并排序（二路） 5）基数排序（多关链字排序） * * * * *
* 15 15 * * * *(前后改变)
