数据结构复习
线性表
1. 线性表的逻辑结构定义、抽象数据类型定义。
2. 线性表的两种存储结构的不同特点及其适用场合。
顺序存储：借助元素在存储器中的相对位置来表示元素之间的逻辑关系。
链式存储：借助指示元素存储地址的指针来表示元素之间的逻辑关系。
顺序表和链表的优缺点比较（正好是相对的）。
3. 在线性表的两种存储结构上实现基本操作的算法。
查找、插入、删除、归并、分解、就地逆置等。
注意：单链表与双向链表、普通链表与循环链表的区别。
双向链表中结点的特征：p=p->next->prior=p->prior->next
因此，在插入和删除时，对单链表，必须要知道第i-1个结点
的地址，而对双向链表则不必如此。
例1.已知la是不带头结点的单链表的头指针，试编写逆序
输出表中各元素值的递归算法。
例2.按递增有序输出单链表中的元素值。
例3.实现集合的交、并、差等运算。
堆和队列
1. 栈的定义、特征以及抽象数据类型定义。
会灵活运用栈的特征（后进先出）。
例：设输入元素为1, 2, 3, P, A，输入次序为123PA，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？
2.栈的存储结构顺序栈：栈满和栈空的条件
链栈
入栈、出栈、取栈顶元素等基本操作的实现算法。
3.栈的应用表达式计算：了解基本思想、栈在算法中的作用
实现递归算法
4. 队列的定义、特征以及抽象数据类型定义。
5.队列的存储结构（顺序）循环队列
链队列
入队、出队、取队头元素等基本操作的实现算法。
循环队列：入队：Q->queue[Q->rear]＝x；
Q->rear＝(Q->rear+1)%MaxQueueSize；
出队：*d=Q->queue[Q->front]；
Q->front＝(Q->front＋1) %MaxQueueSize；
判断队满和队空：（1）少用一个存储单元；
（2）设置一个标志位；
（3）设置一个计数器。
6. 队列的应用：结合后面二叉树和图的遍历算法。
数组
1. 数组采用行优先或列优先顺序存储时，数组元素的
存储地址的计算方法（重点掌握二维、三维数组）。
2. 特殊矩阵进行压缩存储时下标变换公式的推导方法。
要求掌握上三角矩阵、下三角矩阵、对称矩阵、三对角
矩阵分别按行优先或列优先压缩存储时的下标变换公式。
树
1. 树、二叉树的结构特性；二叉树的五种基本形态。
2. 满二叉树和完全二叉树的定义、特点；二叉树的性质
（五条，其中有两条只对完全二叉树满足）。
1、若深度从0开始计算则第i层有2^i个结点
2、共有2^(i+1) -1个结点
3、n0=n2+1
4、完全二叉树有n个结点，则他的深度为log2(n+1)-1
5、完全二叉树：第i个结点的左孩子在2i+1 右孩子是2i+2
3. 二叉树的遍历策略及算法（递归和非递归）。由前序
和中序遍历序列、中序和后序遍历序列能唯一构造出一棵二叉树。
会灵活运用遍历算法求解其他问题。
例1.输出某类结点的值或求某类结点的个数（如叶子结点）。
例2.判定一棵二叉树是否为二叉排序树（采用中序遍历策略，判断正在访问的结点与它的前驱结点之间是否递增有序）。
4. 树的三种存储结构及其特点（双亲表示法、孩子表示法和孩子兄弟表示法，重点掌握孩子兄弟表示法）；树、
森林与二叉树的转换方法。
5. 树的遍历方法：
先根（对应二叉树的前序遍历）
后根（对应二叉树的中序遍历）
森林的遍历方法：先序和中序。
6.
Huffman树的概念及构造方法，哈夫曼编码的设计。
注意：Huffman树是扩充二叉树（只含度为0和度为2的结点）。
补充作业：写出二叉树的中序和后序遍历的非递归算法。
voidNInOrder(BiTreeNode*bt)
/*中序遍历二叉树bt的非递归算法*/
{BiTreeNode*stack [MaxNode], *p;
int top;
if (bt==NULL)
return;
top=0；p=bt；
while (! (p==NULL&&top==0))
{ while (p!=NULL)
{ if (top
{stack[top]=p;
top++;
}
else {printf(“\noverflow！”);
return;
}p=p->leftChild;/*访问左子树*/
}/*while (p!=NULL)*/
if (top==0) return;
else { top--;
p=stack[top];
visit (p);/*访问根结点*/
p=p->rightChild;/*访问右子树*/
}
}/*while*/
}
typedefstruct
{BiTreeNode*pt;
inttag;
} Node;
voidNPostOrder(BiTreeNode*bt)
/*后序遍历二叉树bt的非递归算法*/
{ Node stack [MaxNode],BiTreeNode*p;
inttop;
if (bt==NULL)
return;
top=0；p=bt；
while (! (p==NULL&&top==0))
{ while (p!=NULL)
{ if (top
{stack[top].pt=p;stack[top].tag=1;
top++;
}else {printf(“\noverflow！”);
return;
}
p=p->leftChild;/*访问左子树*/
}/*while (p!=NULL)*/
if (top==0) return;
else {if (stack[top-1].tag==1)
{ p=stack[top-1].pt;stack[top-1].tag=2;
p=p->rightChild;/*访问右子树*/
}
else { top--;
visit (stack[top].pt);/*访问根结点*/
}
}
}/*while*/
}
图
图的定义、基本术语。
（如：无向完全图、有向完全图、路径、回路、连通图和连通分量、强连通图和强连通分量、连通图的生成树）
无向完全图：弧数量为Cn2 的图，有向完全图的弧数量为An2
连通图 ：任意两个结点能连通
连通分量：在无向图中，极大的连通子图成为图的连通分量
连通图的生成树：一个连通图的生成树是一个极小连通子图，他含有途中全部定点n但只有足以构成一棵树的n-1条边。
注意：边数与顶点数、度之间的关系：
完全图、连通图以及生成树的特点。
判断图中是否存在回路的方法。?
无向图中结点的度均>=2 则改图一定存在回路
利用BFS，在遍历过程中，为每个节点标记一个深度deep，如果存在某个节点为v，除了其父节点u外，还存在与v相邻的节点w使得deep[v]<=deep[w]的，那么该图一定存在回路；
2.
图的各种存储结构（重点掌握邻接矩阵和邻接表）的
特点及构造方法。
注意：图和网的区别。
3. 图的两种遍历策略及遍历算法（深度优先和广度优先）。
会灵活运用遍历算法求解其他问题。
4. 图的应用
（1）生成树的定义、类型（深度优先和广度优先生成树）；
最小生成树的定义；
Kruskal算法和Prim算法(破圈法)求网的最小生成树的方法（注意：记住算法特点，不要混淆）。
（2）Dijkstra算法求单源最短路径的方法（有向网和无向网都适用）。
查找
1.静态查找表的顺序查找、折半查找方法的实现算法；
描述折半查找过程的二叉判定树的构造方法；三种方
法的比较。
2.
二叉排序树的定义、构造以及查找、插入的实现方法。
注意：二叉排序树按中序遍历是递增有序序列。
3.
哈希表的定义、构造及查找方法，重点掌握开放定址法和链地址法处理冲突时的构造方法。
开放地址法：线性探测、平方再散列法（-1^2,1^2,-2^2,2^2....）
链地址法：将冲突的结点连接在地址上，采用链式结构
4.
根据公式计算各种查找方法在等概率情况下的平均查找长度。
内部排序
1.
排序的定义，排序方法“稳定”或“不稳定”的含义。
注意：希尔排序、直接选择排序、堆排序、快速排序是不稳定的排序算法。
2.
各种排序方法的基本思想、算法特点、排序过程
以及它们的时间和空间复杂度分析。
（包括基本算法及它们的改进算法：直接插入排序、
折半插入排序、希尔排序、直接选择排序、堆排序、
冒泡排序、快速排序、归并排序及基数排序）
会根据实际应用情况选择合适的排序算法。
错误题目总结
1、数据的最小单位是数据项
2、时间复杂度不受初始状态影响而恒为 nlog2n 的是 堆排序。
