数据结构最新考研知识点,完全贴合大纲讲解

1、数据结构知识点基本概念1.数据 能被计算机识别、存储和加工处理的信息的载体。2. 数据元素数据的基本单位，可由若干个数据项组成。例如，一 本书的书目信息为一个数据元素，而书目信息的每一 项（如书名，作者名等）为一个数据项。3. 数据结构 数据之间的相互关系，即数据的组织形式。它包括三 个要素：数据的逻辑结构（数据之间的逻辑关系） 、 数据的存储结构（数据在计算机中的存储方式）和数 据的运算。4. 数据的逻辑结构线性结构：若结构是非空集，则有且仅有一个开始 结点和一个终端结点，并且所有结点都最多只有一个 直接前趋和一个直接后继。 栈、队列等都是线性结构。非线性结构：一个结点可能有多个直接前趋和直

2、接 后继。数组、广义表、树和图等数据结构都是非线性 结构。5. 数据的存储结构顺序存储 借助数据在连续的存储空间中的相对位置表示元素 关系,通常用数组描述。链接存储 借助数据元素的存储地址的指针表示元素关系。索引存储 储存结点信息的同时，建立附加索引表， 。索引表由 若干索引项组成。索引项的一般形式是： （关键字、 地 址）。有稠密索引和稀疏索引。散列存储 按结点的关键字直接计算出存储地址第一章 栈、队列和数组 一、栈和队列的基本概念1. 栈(Stack) 1.1 概念 栈是仅在表的一端进行插入和删除运算的线性表， 又称栈为 LIFO 表(Last In First Out) 。栈的修改是按

3、后进先出的原则进行的。称插入、删除这一端为栈顶，另一端称为栈底。表 中无元素时为空栈。通常栈有顺序栈和链栈两种存储 结构。1.2 栈的基本运算 构造空栈： InitStack(S) 判栈空 : StackEmpty(S) 判栈满： StackFull(S) 进栈： Push(S,x) 退栈： Pop(S) 取栈顶元素： StackTop(S)2 队列 (Queue)2.1 概念队列是一种运算受限的线性表，又称作 FIFO 表 (First In First Out) ，插入在表的一端进行，而删除在 表的另一端进行，队列的操作原则是先进先出的。 允许删除的一端称为队头 (front) ，允许插入

4、的一端 称为队尾 (rear) , 队列也有顺序存储和链式存储两种存 储结构。2.2 队列的基本运算置空队： InitQueue(Q)判队空： QueueEmpty(Q)判队满： QueueFull(Q)入队： EnQueue(Q,x)出队： DeQueue(Q)取队头元素： QueueFront(Q)二、栈和队列的顺序存储结构1.栈的顺序存储结构1.1概念开辟一组地址连续的存储单元，依次存放自栈底到 栈顶的数据元素。设top指针指示栈顶元素的当前位置。当栈满时，做进栈运算必定产生空间溢出，称“上 溢”。 当栈空时，做退栈运算必定产生空间溢出，称 “下溢”。上溢是一种错误应设法避免，下溢常用作

5、 程序控制转移的条件。1.2基本运算新元素入栈顶时：先入栈 , 再移指针 top=top+1 删除元素时：先移指针 top=top-1,后删栈顶元素 3 栈的长度： top-base2. 队列的顺序存储结构2.1 概念用一组地址连续的存储单元依次存放从队头到队尾的元素。 设队头指针为 front，指向队头元素队尾指针为 rear，指向队尾元素的下一个位。当 front=rear=0 ，表示空队列。顺序队列中存在“假上溢”现象，由于入队和出队 操作使头尾指针只增不减导致被删元素的空间无法 利用，队尾指针超过向量空间的上界而不能入队。3 将队列的头、尾相连形成一个环，构成循环队列。并引 入数学中的

6、模运算计算队头和队尾指针。2.2基本运算入队操作：Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXQSIZE;出队操作： x=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;、栈和队列的链式存储结构1.栈的链式存储结构 1.1 概念采用链式存储结构称链栈，并由其栈顶指针惟一确设 ls为栈顶指针，栈 =(a1,a2,an)，a1 为栈底元素， an 为栈顶元素。1.2基本运算建栈。Void initstack(linkstack *s) s-top=NULL;判栈空。Int stackempty (linkstack *s)retur

7、n s-top=NULL;3 进栈。Void push(linkstack *s,datatype x)stacknode *p=(stacknode *)malloc(sizeof(stacknode); p-data=x;p-next=s-top;s-top=p;退栈。Datatype pop(linksatck *s)datatype x;stacknode *p=s-top;if(stackempty(s)error( “stack underflow” );x=p-data;s-top=p-next;free(p);return x;5 取栈顶元素。Datatype stacktop

8、(linkstack *s)if(stackempty(s)error( “stack is empty”);return s-top-data;2.队的链式存储结构2.1 概念 用链表示的队列简称为链队列。设两个指针 front、 rear 分别指示队头和队尾。为了链队列的操作方便， 增加一个头结点， front 指向头结点， rear 指向队尾元 素。如图所示：2.2基本运算建空队Void initqueue(linkqueue *q)q-front=q-rear=NULL;判队空。Int queueempty(linkqueue *q)return q-front=NULL&q-rear

9、=NULL;3 入队。Void enqueue(linkqueue *q,datatype x)queuenode *p=(queuenode *)malloc(sizeof(queuenode); p-data=x; p-next=NULL; if(queueempty(q)q-front=q-rear=p;elseq-rear-next=p;q-rear=p;出队。Datatype dequeue(linkqueue *q)datatype x;queuenode *p;if(queueempty(q)error( “queue is underflow”); p=q-front;x=p-

10、data;q-front=p-next;if(q-rear=p) q-rear=NULL; free(p);return x;5 取队头元素。Datatype queuefront(linkqueue *q) if(queueempty(q)error( “queue is empty”);return q-front-data;第二章 树与二叉树一、树的基本概念1.树是 n 个结点的有限集合，非空时必须满足：只有 一个称为根的结点；其余结点形成 m 个不相交的子 集，并称根的子树。2.树的表示方法： 树形表示法； 嵌套集合表示法； 3 凹入表表示法；广义表表示法；3. 一个结点拥有的子树数称

11、为该结点的度；一棵树的 度是指树中结点最大的度数。4. 度为零的结点称叶子或终端结点；度不为零的结点 称分支结点或非终端结点5. 根结点称开始结点，根结点外的分支结点称内部结 点；6. 树中某结点的子树根称该结点的孩子；该结点称为 孩子的双亲；7.树中存在一个结点序列 K1，K2， Kn，使 Ki 为 Ki+1 的双亲，则称该结点序列为 K1 到 Kn 的路径或 道路；8.树中结点 K 到 Ks 间存在一条路径，则称 K 是 Ks 的祖先， Ks 是 K 的子孙；9. 结点的层数从根算起，若根的层数为1，则其余结点层数是其双亲结点层数加 1；双亲在同一层的结点互为堂兄弟；树中结点最大层数称为树

12、的高度或深 度；10. 树中每个结点的各个子树从左到右有次序的称有 序树，否则称无序树；11. 森林是 m 棵互不相交的树的集合。二、二叉树1. 二叉树的定义及其主要特性1.1定义 树中每个结点至多有两棵子树，且子树有序。满二叉树是一棵深度为 k，结点数为 2k-1 的二叉树； 3 完全二叉树是至多在最下两层上结点的度数可以 小于 2，并且最下层的结点集中在该层最左的位置的 二叉树。1.2 二叉树的五种基本形态1.3 二叉树的主要特性二叉树第 i 层上的结点数最多为 2i-1；深度为 k 的二叉树至多有 2k-1 个结点；3 在任意二叉树中， 叶子数为 n0，度为 2 的结点数为 n2，则 n

13、0=n2+1；1.4 满二叉树与完全二叉树满二叉树深度为 k，且有 2k-1个结点。（对满二叉树中的结点约 定编号：自根起，从上到下，从左到右） 完全二叉树 仅允许最下层右侧分支不满，若按从上到下，从左到 右为树中结点编号，则与满二叉树相同。二者关系： 满二叉树是完全二叉树。 完全二叉树不一定是满二叉树1.5完全二叉树性质 n个结点，深度为 K的完全二叉树，其 K= log2N+1 对一棵 n个结点深度为 K 的完全二叉树上的结点按 层次编码（从第一层到第 K 层，从左到右），则树中编 号为i的结点 （1=i1时， i的双亲是 i/2 ； c: 当2in时，i是叶点（无左孩子） ；当2in时，

14、 i结点无右孩子；当 2i+11 则双亲结点是 i/2 取整； 左孩子是 2i, 右孩子是 2i+1；（要小于 n） 3 i（n/2 取整）的结点是叶子； 奇数没有右兄弟，左兄弟是 i-1 ；偶数没有左兄弟， 右兄弟是 i+1。但顺序存储结构适用于完全二叉树 特点： 即不浪费空间，又可以快速确定其结点的位置；对已 知的结点 i，其左孩子为 2i，右孩子为 2i+1，双亲为 i/22.2 链式存储结构 链表中每个结点至少含有三个域：数据域、左指针域 和右指针域。3. 二叉树的遍历根据访问结点的次序不同可分为：先序遍历 （ 前序 遍历或先根遍历 ） ，中序遍历 （或中根遍历 ）、后序遍 历（ 或后

15、根遍历 ） 。遍历线索二叉树。时间复杂度为 O（n）。先序：先访问根结点，然后访问左子树，再访问右子树中序：先访问左子树，然后访问根结点，再访问右 子树。后序：先访问左子树，然后访问右子树，再访问根 结点。4. 线索二叉树的基本概念和构造4.1 概念利用二叉链表中的 n+1个空指针域存放指向某种遍历 次序下的前趋和后继结点的指针，这种指针称线索。 加线索的二叉链表称线索链表。相应二叉树称线索二 叉树。4.2 构造、树和森林1. 树的存储结构双亲表示法（顺序存储结构）：开辟一组连续空间 存储树的结点，每个结点中附设一个指示双亲结点的 双亲域。孩子表示法（链式存储结构）：A.按树的度设结点指针域。

16、B.按结点的度设结点指针域C.按孩子结点排成线性表3 孩子兄弟表示法（二叉树表示法）：在这种表示法 中，树中每个结点有三个域。数据域：存放结点数据左指针域：指向该结点的第一个孩子结点 右指针域：指向该结点的右兄弟结点2. 森林与二叉树的转换二叉树和树都可以用二叉链表作为其存储结构。因 此，以二叉链表作为中间介，可以导出树与二叉树之 间存在对应关系。一棵树与惟一的一棵二叉树一一对 应。2.1 树转换成二叉树保持双亲和第一个孩子连线，其他连线去掉； 兄弟之间连线；3 使右兄弟结点成为右孩子， 使第一个孩子成为左孩 子。2.2 森林转换为二叉树将每棵树转化为二叉树；将各棵二叉树的根相连；3 使二叉树

17、的根成为右孩子。2.3 二叉树转换成森林若某结点是其父结点的左孩子，则把该结点的右孩 子、右孩子的右孩子、 ，都与该结点的父结 点用线线连；去掉树中所有父结点到其右孩子的连线，生成森 林。3. 树和森林的遍历3.1 树的遍历先根遍历 先访问树根，再依次先根遍历根的每棵子树。后根遍历 先依次后根遍历根的每棵子树，再访问树根。二叉树（续上例）先序：ABCEFD 中牙:BEFCDA结论: 树的先根遍历相当于其转化的二叉树的先序遍历: 树的后根遍历相当于其转化的二叉树的中序遍历;3.2 森林的遍历 先序（ 先根 ） 遍历森林中序（后根）遍历森林例:先根:ABCDEFGHJIK （二叉树的先序） 后根:

18、BADEFCJHKIG （二叉树的中庙）森林转化的二叉树:四、树与二叉树的应用1. 概念：树的路径长度是从树根到每一结点的路径长度之 和。将树中的结点赋予实数称为结点的权。结点的带权路径是该结点的路径长度与权的乘积。 树的带权路径长度又称树的代价，是所有叶子的带权 路径长度之和。带权路径长度最小的二叉树称最优二 叉树（ 哈夫曼树 ）。3 具有2n-1 个结点其中有 n个叶子，并且没有度为 1 的分支结点的树称为严格二叉树。对字符集编码时，要求字符集中任一字符的编码都 不是其它字符的编码前缀，这种编码称前缀码。5 字符出现频度与码长乘积之和称文件总长； 字符出 现概率与码长乘积之和称平均码长；6

19、 使文件总长或平均码长最小的前缀码称最优前缀码利用哈夫曼树求最优前缀码，左为 0，右为 1。编码 平均码长最小；没有叶子是其它叶子的祖先，不可能 出现重复前缀。2. 哈夫曼树构造算法 )根据给定的 n个权值 w1,w2, ,wn 构成 n棵二叉树 的集合F=T1,T2, ,Tn ，其中每棵二叉树 Ti 中只有 一个带权为 wi 的根结点，其左右子树为空。在 F中选取两棵根结点的权值最小的树作为左右子 树构造一棵新的二叉树，且置新的二叉树的根结点的 权值为左右子树上根结点的权值之和。3 在F中删除这两棵树， 同时将新得到的二叉树加入 F 中。 重复和 3 ，直到 F只含一棵树为止。 这棵树便是

20、哈夫曼树。3. 前缀码给定一个码的集合序列，若没有一个序列是另一个序列的前缀，则称这个集合中的码为前缀码。例：000, 00b Ob 10, 11询细刈乂容易翻译。0, I, 10, 11不是前缀码 特点：前缀码是码长不等的编码，既可以缩短报文的长度第四章 图一、图的基本概念1. 图：图 G 是由顶点集 V 和边集 E 组成，顶点集是有 穷非空集，边集是有穷集；2. G 中每条边都有方向称有向图；有向边称弧；边的 始点称弧尾；边的终点称弧头； G 中每条边都没有方 向的称无向图。3. 顶点 n 与边数 e 的关系：无向图的边数 e 介于 0n(n-1)/2 之间，有 n(n-1)/2 条边的称

21、无向完全图； 有向图的边数 e 介于 0n(n-1)之间，有 n(n-1)条边的 称有向完全图；4. 无向图中顶点的度是关联与顶点的边数；有向图中 顶点的度是入度与出度的和。所有图均满足：所有顶点的度数和的一半为边数。5. 图 G(V，E)，如 V是 V 的子集， E是 E 的子集， 且 E中关联的顶点均在 V中，则 G (V ,E是)G 的子 图。6. 在有向图中，从顶点出发都有路径到达其它顶点的 图称有根图；7. 在无向图中，任意两个顶点都有路径连通称连通图； 极大连通子图称连通分量；8. 在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；9. 将图中每条边赋上

22、权，则称带权图为网络二、图的存储及基本操作1. 邻接矩阵表示法用一维数组存储图中顶点的信息； 用矩阵（二维数组）表示图中各顶点之间的相邻关系2. 邻接表法构造方法： 与同一顶点邻接的所有邻接点构成一个单链表，用表 结点描述； 各链表设置表头结点，由头结点描述； 各表头结点构成一个顺序表。3. 邻接矩阵表示法与邻接表表示法的比较邻接矩阵是唯一的，邻接表不唯一；存储稀疏图用邻接表，存储稠密图用邻接矩阵；3 求无向图顶点的度都容易， 求有向图顶点的度邻接 矩阵较方便；判断是否是图中的边，邻接矩阵容易，邻接表最坏 时间为 O(n) ；5 求边数 e，邻接矩阵耗时为 O(n2)，与 e 无关，邻 接表的

23、耗时为 O(e+n)；三、图的遍历1. 深度优先搜索( DFS)搜索策略：访问当前顶点 vi ，寻找与 vi 相邻且未被访问顶点vj ，若存在，将其作为当前点，访问，并重复上述搜 寻过程。否则(所有邻接点都被访问过)，退回一步，寻找 与前一个顶点相邻的未被访问顶点，访问，并重复上 述过程。若上述过程无法访问图中的所有顶点，则另选一个 新顶点重新开始。深度优先搜索是一种纵向搜索的过程。2. 广度优先搜索( BFS)访问出发点 v0，依次访问 v0的各个未曾访问过的邻 接点，然后分别从这些邻接点出发重复上述过程。若上述过程无法访问图中的所有顶点，则另选一个 新顶点重新开始。广度优先搜索是一种横向搜

24、索的过程。 使用队列结构。四、图的基本应用1. 概念将没有回路的连通图定义为树称自由树。 生成树：连通图 G 的一个子图若是一棵包含 G 中 所有顶点的树，该子图称生成树。有 DFS 生成树和 BFS 生成树， BFS 生成树的高度最小。非连通图生成 的是森林。3 最小生成树：连通网 G=(V,E)，边是带权的，因而 G 的生成树的各边也是带权的。将生成树的各边的权 值总和称为生成树的权，并把权最小的生成树称为 G 的最小生成树。例：用Prim算法求最小生成树连通图如下所示：例：用克鲁斯卡尔算法求最小生成树 连通图如下所示:2.最短路径 路径的开始顶点称源点，路径的最后一个顶点称终 点。3.

25、拓扑排序3.1 概念AOV 网：顶点表示活动， 弧表示活动间的优先关系 的有向图。在无回路的 AOV 网中，所有的活动可以排成一个 线性序列，使得每个活动的所有前驱活动都排在该活 动的前边，称此序列为拓扑序列，由 AOV 网构成拓 扑序列的过程称为拓扑排序。3.2 拓扑排序算法思想选择有向图中入度为 0 的顶点输出，并从图中删去 该点相邻弧；重复上述操作，直到图中全部顶点均被输出或图中 已不存在入度为 0 的顶点（有回路）。第五章 动态查找一、平衡二叉树 （AVL 树）1.基本概念查找的同时对表做修改操作 （如插入或删除 ） 则相应 的表称之为动态查找表，否则称之为静态查找表。 衡量一个查找算

26、法次序优劣的标准是在查找过程 中对关键字需要执行的平均比较次数 （即平均查找长 度 ASL）.3 平衡二叉树 （AVL 树），或为空树 ,或为如下性质的二 叉排序树 :左右子树深度之差的绝对值不超过1;左右子树仍然为平衡二叉树 .平衡因子 BF=左子树深度右子树深度 . 平衡二叉树每个结点的平衡因子只能是 1，0，-1。若其绝对值超过 1，则该二叉排序树就是不平衡的。如图所示为平衡树和非平衡树示意图：2.平衡二叉树的算法思想 若向平衡二叉树中插入一个新结点后破坏了平衡 二叉树的平衡性。首先要找出插入新结点后失去平衡 的最小子树根结点的指针。然后再调整这个子树中有 关结点之间的链接关系，使之成为

27、新的平衡子树。当 失去平衡的最小子树被调整为平衡子树后，原有其他 所有不平衡子树无需调整，整个二叉排序树就又成为 一棵平衡二叉树。失去平衡的最小子树是指以离插入结点最近，且平 衡因子绝对值大于 1 的结点作为根的子树。假设用 A 表示失去平衡的最小子树的根结点，则调整该子树的 操作可归纳为下列四种情况。2.1 LL 型平衡旋转法由于在 A 的左孩子 B 的左子树上插入结点 F，使 A 的平衡因子由 1增至 2 而失去平衡。故需进行一次顺 时针旋转操作。 即将 A 的左孩子 B 向右上旋转代替 A 作为根结点， A 向右下旋转成为 B 的右子树的根结 点。而原来 B 的右子树则变成 A 的左子树

28、。2.2 RR 型平衡旋转法由于在 A 的右孩子 C 的右子树上插入结点 F，使 A 的平衡因子由 -1 减至-2 而失去平衡。 故需进行一次逆 时针旋转操作。即将 A 的右孩子 C 向左上旋转代替 A 作为根结点，A 向左下旋转成为 C 的左子树的根结点。 而原来 C 的左子树则变成 A 的右子树。2.3 LR 型平衡旋转法由于在 A 的左孩子 B 的右子数上插入结点 F，使 A 的平衡因子由 1 增至 2 而失去平衡。故需进行两次旋 转操作（先逆时针，后顺时针） 。即先将 A 结点的左 孩子 B 的右子树的根结点 D 向左上旋转提升到 B 结点的位置，然后再把该 D 结点向右上旋转提升到

29、A 结 点的位置。即先使之成为 LL 型，再按 LL 型处理。如图中所示，即先将圆圈部分先调整为平衡树，然后 将其以根结点接到 A 的左子树上，此时成为 LL 型， 再按 LL 型处理成平衡型。2.4 RL 型平衡旋转法由于在 A 的右孩子 C 的左子树上插入结点 F，使 A 的平衡因子由 -1 减至-2 而失去平衡。 故需进行两次旋 转操作（先顺时针，后逆时针） ，即先将 A 结点的右 孩子 C 的左子树的根结点 D 向右上旋转提升到 C 结 点的位置，然后再把该 D 结点向左上旋转提升到 A 结 点的位置。即先使之成为 RR 型，再按 RR 型处理。二、B 树及其基本操作、 B+树的基本概

30、念1.B 树的概念2. B 树的基本操作2.1 检索2.2 插入2.3 删除、散列（ Hash）表二、解决冲突的方法1、开放定址法：当冲突发生时，使用某种方法在Hash表中形成-个探査序列，然 后沿着此探查序列逐个单元地查找，直到找到给定关键字或碰到一个 开放的地址(即地址单元为空)为止。插入吋：碰到开放的地址，则将待査关键字插入。查找时：碰到开放的地址，则说明查找失败。仃八线性探测再散列di = (d+i) mod mi二 1, 2,m-1m为Hash表表长d为冲突产生时的Hash地址通过i取值的线性变化构造探查序列特点：线性(2)二次探测再散列:2i-i = (d + i2) mod md

31、2i = (d - i2) mod ml=i=(m-l)/2特点：将同义词來回散列在第一次产生冲突时的Hash地址的两端探测序列是跳跃似的减少堆积(二次聚集)的发生缺点：不易探测到整个Hash表空间(3)伪随机探测再散列di 二(d + Ri) mod mm为Hash表长d为冲突产生时的Hash地址Ri： Rl, R2, . , Rm-1是一个伪随机数序列2、再哈希法当冲突产生时，通过再计算另一个哈希函数地址解决冲突。即为 构造不同的哈希函数。di = RHi(K)i=l, 2,.，k其中：RHi (K)丰RHj (K)，即RHi均是不同的Hash函数。优点：不易产生堆积或聚集。缺点：计算量大

32、。3、链地址法将所有关键字为同义词的记录存储在同一单链表中。假设Hash函数产生的哈希地址在区间0旷1上，则将Hash表定义 为一个由m个头指针组成的指针数组chainllashm,凡Hash地址为i 的记录都插入到以数组元素chainllashEi为头指针的链表中，并保持 同义词在同一线性链表中按关键字有序。优缺点优点：不会产生堆积；空间是动态申请的，适用于造表前无法确 定表长的情况。缺点：空间开销大。三、哈希表的算法分析哈希表的装填因子_表中填入的记录数_ n_a哈希表的长度一 ma体现哈希表的装满程度哈希表的查找效率的决定因素哈希函数解决冲突的方法哈希表的装填因子假设Hash函数均匀的前

33、提下，不同的解决冲突的方法得到的Hash 表的ASL不同，且不是表中关键字个数n的函数，而是装填因子a的函 数。如下表所示：解决冲突的方法平均査找长度ASL成功查找不成功查找线性探测法(l+l/(l-a)/2(1+1/(1 -a)2)/2二次探测、随机探测 、再哈希法-ln(l-a)/a1/(1-a)链地址法1+ a /2a + exp(-a )ASLot越小，发生冲突的可能性越小。a越大，发生冲突的可能性越大。因此只要a选择合适，不管n多大，哈希表的平均查找长度就会限 定在一个范围之内。第六章 排序一、希尔排序( Shell Sort) 又称缩小增量排序，是直接插入排序的改进。 基本思想：将

34、待排记录序列按增量 dh 值分成若干 子表进行直接插入排序；然后缩小增量值，再分割， 再排序，直至整个序列“基本有序”时，再对整个序 列做一次直接插入排序。实现过程：将直接插入排序的间隔变为 d。 d 的取 值要注意：最后一次必为 1；避免 d 值互为倍数； 关键字比较次数最大为 n1.25；记录移动次数最大为 1.6n1.25；算法的平均时间是 O(n1.25)；是一种就地的不 稳定的排序。二、快速排序 基本思想：每趟让待排表中的第一元素作支点，排 序后入终位 k，将原表一分为二，使得 r1rk-1 中 元素小于等于 rk ，而 rk+1rn中元素都大于等于 rk ，递归进行，直到表长为 1 时，排序结束。 实现过程：将第一个值作为基准， 设置 i,j 指针交替