导图社区 数据结构
- 50
- 1
- 0
- 举报
数据结构
仅供于复习、巩固和回顾的框架结构，详细的资料还需要阅读书籍。主要有：绪论、线性表、栈、队列和数组串、数与二叉树、图、查找排序等内容。
编辑于2022-10-15 16:00:41 江西- 相似推荐
- 大纲
数据结构
绪论
线性表
栈、队列和数组
串
数与二叉树
数的基本概念
数是n个节点的有限集。当n=0时，称为空树。 数的根节点没有前驱节点，除根节点外所有节点有且只有一个前驱 树中的所有节点可以有零个或多个后继
基本术语
树中的一个节点的孩子个数称为该节点的度，树中节点的最大度数称为树的度
度大于0的节点称为分支节点（非终端节点）
节点的深度是从根节点开始自顶向下逐层累加的 节点的高度是从叶节点开始自低向上逐层累加的 数的高度（深度）是树中节点的最大层数
有序数和无序数，树中的节点从左到右是有次序的，不能互换，称为有序树
路径和路径长度。树中两个节点的路径是这两个节点之间所经历的节点序列构成的，而路径长度是路径上所经历的边的个数
**以下称树节点的左子节点为左节点，右子节点为右节点
数的性质
树中的节点数等于所有节点的度数之和加一
度为m的树第i层最多有m^(i-1)个节点
高度为h的m叉树至多有m^h-1/(m-1)个节点
具有n个节点的m叉树最小的高度为log m n(m - 1)向上取整
二叉树的概念
二叉树每个节点至多只有两个子树
几个特殊的二叉树
满二叉树
高度为h且含有2^h-1个节点的二叉树称为满二叉树
完全二叉树
高度为h有n个节点的二叉树，当且仅当每个节点都与高度为h的满二叉树中编号为1到n的节点一一对应
i<=[n/2] 向下取整，则i的节点为分支节点，否则为叶子节点
叶子节点只可能在层次最大的两层出现，最大层而叶子结点依次排列在左侧
若有度为1的节点，则只可能有一个
n为奇数每个节点都有左右孩子，n为偶数只有最后一个分支节点没有右孩子
二叉排序数
左子数上所有节点的关键字均小于根节点的关键字，右子数上的所有节点关键字均大于根节点的关键字；左子数和右子数又各是一颗二叉排序树
二叉树的性质
非空子书上的叶子节点数等于度为2的节点数加1，即n0 = n2 + 1
非空二叉树上第k层至多有2^(k-1)个节点
高度为h的二叉树至多有2^h-1个节点
对于完全二叉树从上到下，从左到右依次编号为1到n 当i>1时，双亲为[i/2] 2i<=n时，左孩子为2i 2i+1 <= n 时，节点i的右孩子为2i+1
具有n个节点的完全二叉树定义有2^(h-1) - 1 < n <= 2^h - 1
二叉树的存储结构
顺序存储结构：用一组地址连续的存储单一自上而下、自左至右存储完全二叉树，第一个节点通常存在索引为1的位置
链式结构：每个节点包含三个域－数据域、左指针域、右指针域
二叉树的遍历和线索二叉树
二叉树的遍历
先序遍历：依次访问根节点，访问左子树，访问右子树
中序遍历：依次访问左子树，根节点，右子树
后序遍历：依次访问左子树，右子数，根节点
递归算法转换为非递归：用栈保持需要回溯的节点即可，前序，和中序相对简单，后序保证每个节点要出两次栈
层次便利：再访问一个节点后，将该节点的后续节点入队
线索二叉树
将节点的空指针域利用起来（左指针指向前驱节点，右指针指向后继节点），指向直接前驱或直接后继节点
中序线索二叉树的构建：在中序遍历二叉树时，用pre指向当前节点的前驱节点，当前节点的左指针为空，则将左指针指向前驱节点； 当pre节点的右指针为空，则用前驱节点的右指针指向当前节点
中序线索二叉树的遍历：若当前节点有右子树后继节点是右子树的最左下节点，若无右子树后继节点为右指针指向的节点
前序线索二叉树：若有左孩子左孩子就是后继节点，若无左孩子有右孩子，右孩子就是后继，若为叶子节点，则右指针指向的节点为后继节点
后序线索二叉树：后序线索二叉树的便利需要用到栈，或者带标志位的三叉链表存储
数、森林
数的存储结构
双亲表示法：用数组保持每个节点的值和双亲在数组中的索引 struct PTNode{ TYPE data, int parent; }; struct PTree { PTNode nodes[MAX_SIZE]; int n; ｝；
孩子兄弟表示法：又称二叉树表示法，左子树右兄弟 struct CsNode { TYPE data; CSNode* firstchild, *nextsubling; ｝；
孩子表示法：将每个节点的孩子用单链表链接起来形成一个线性结构
数、森林与二叉树的转换：每个节点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称为左孩子右兄弟
数和森林的遍历
先根遍历：先访问根节点，再依次访问根节点的颗子树；与对应二叉树的先序遍历相同
后根遍历：先依次遍历根节点的每颗子树，再访问根节点；与对应二叉树的中序遍历相同
先序遍历森林：访问森林的第一颗树中的根节点，前序遍历第一颗树的子树森林，先序遍历剩下的树
中序遍历森林：中序遍历森林中的第一颗树的子树森林，访问第一颗树的根节点，中序遍历除去第一颗树之后剩余的森林
数和二叉树的应用
哈夫曼数和哈夫曼编码
哈夫曼树的定义：从数的根到任意节点的路径长度与该节点的权值的乘积为该节点的带权路径长度。 所有叶子节点的带权路径长度和为这颗树的带权路径长度。 在n个带权叶子节点的二叉树中，其中带权路径长度最小的二叉树为哈夫曼树
哈夫曼树的构造：初始只有n个叶子节点的集合中，取权值最小的两个节点，最为左右节点构成新节点，新节点的权值是两个节点权值之和，再将新节点放入集合。经过n-1上述步骤即可得到
哈夫曼编码：是一种被广泛应用的数据压缩编码，也是前缀编码。将从根节点到叶子节点的转向记录，0表示左转，1表示右转，这样可得到每个叶子节点的编码。
并查集
利用数的双亲指针数组表示作为并查集
可用来处理集合的合并，判断是否有交集等
图
图的基本概念
图由顶点集合V和边集合E组成，其中图中的顶点集为有限非空集
有向图：E中为有向边（也称弧）的有限集合时，图G为有向图， <v,w> v称为弧尾，w称为弧头
无向图：E为无向边的有限集合时，图G为无向图。（v，w）或者（w，v）可以说v和w互为邻接点
简单图、多重图：不存在重复边，不存在顶点到自身的边称为简单图。若图G某两个顶点之间的边数大于1，又允许通过一条边和自身关联称为多重图。
完全图（简单完全图）：对于无向图，有n(n-1)/2条边的无向图称为完全图。对于有向图，有n(n-1)条弧的有向图称为有向完全图。
子图：设有两个图G=(V,E)和 G`=（V`,E`), 若V`是V的子集，且E`是E的子集，则称G`是G的子图。若有V(G`) = V(G) ，则称为G的生成子图。 注意－并非V和E的任何子集都能构成G的子图，因为这样的子集可能不是图。
联通、联通图和联通分量：在无向图中，v到w有路径存在，称v和w是联通的。若图中任意两个顶点都是联通的，则图G为联通图，否则为非联通图。 无向图的极大联通子图称为联通分量。
强联通图、强联通分量：在有向图中，v和w，v到w和w到v都有路径，则称这两个顶点是强联通的。图中任意两个顶点都是强联通的，则称此图为强联通图。 有向图的极大强联通子图称为强联通分量
生成数、生成森林：联通图的生成树是包含全部顶点的极小联通子图。在非联通图中，联通分量的生成树构成非联通图的生成森林。
定点的度、入度和出度：无向图中，顶点v的度是指依附于顶点v的边的数目。无向图全部顶点的度是边数的两倍。 有向图中，顶点v的度为出度和入度的和，出度为弧尾为v的边数，入度为弧头为v的边数。无向图全部顶点的度等于边数。
边的权和网：图中每个边可以标上某种含义的数值称为该边的权值。这种边上带权值的图也称网。
稠密图、稀疏图：一般当图G满足E < VlogV 时，可以视为稀疏图
路径、路径长度和回路：顶点v0到定点vn之间的一条路径是指定点序列v0,v1,v2....vn。路径上的边的数目称为路径长度。
简单路劲、简单回路：顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称简单回路。
距离：从顶点v到顶点w的最短路径若存在，则此路径称为v到w的距离。不存在记为∞
有向树：一个顶点入度为0，其余定点的入度均为1的有向图，称为有向树。
图的存储及基本操作
邻接矩阵法
用一个一维数组存储图中顶点信息，用一个二维数组存储图中的边信息。
A[i][j] 存在，对于无向图 表示顶点i到顶点j存在通路。对于有向图表示存在一条由i指向j的边。
A^n的元素A^n[i][j]等于由顶点i到顶点j的长度为n的路径数目。
空间复杂度为O(N^2)
邻接表法
图中每个顶点vi建立一条单链表，表示依附vi的边，这个单链表称为vi的边表。边表的头指针和顶点数据信息采用顺序存储（称为顶点表）。 使用邻接表法可节省当图为稀疏图时，存储空间的浪费。
存储有向图，空间复杂度为O（V+E）。存储无向图，空间复杂度为O（V+2E）
十字链表法
是有向图的一种链式存储结构。对应有向图中的每条弧有一个节点。弧节点增加了指向相同弧节点的弧节点的指针域，和指向相同弧头节点的弧节点的指针域。
可以很方便的找到vi的所有入度边，和出度边。
邻接多重表
是无向图的另一种链式存储结构。
邻接多重表和邻接表的区别仅在于，同一条边在邻接表中用两个节点表示，而在邻接多重表中只有一个节点。
图的遍历
广度优先搜索
类似二叉树的层次遍历算法。基本思想是：从首节点v1开始访问，再访问v1邻近的顶点v2v3v4...，然后访问v2的邻近节点，期间访问过的不要重复访问。
性能分析：对于邻接表存储，由于每个顶点都入站了一次，访问顶点为O（N），找到邻接顶点总共的时间开销为O(E)，故时间复杂度为O（N +E），空间复杂度O（N） 对于邻接矩阵存储，由于每个顶点寻找邻接顶点的时间消化为O（N），故总的时间复杂度为O（N^2），空间复杂度O（N）
广度优先生成数
深度优先遍历
类似树的先序遍历。基本思想是：先访问V1，再访问v1的邻近节点V2，再访问V2的邻近节点v3等等，若无邻近节点则回溯找前一个节点的下一个邻近节点。
性能分析：对于邻接表存储，每个顶点都会访问一次，顶点访问的开销为O（N），所以顶点搜索邻近节点的总消化为O（E），故时间复杂度为O（N + E），空间复杂度O（N） 对于邻接矩阵存储，每个顶点寻找邻近节点的消化为O（N），故时间复杂度为O（N^2），空间复杂度O（N）
深度优先生成数和森林
图的联通性判断：可以用图的遍历来判断该图是否联通
图的应用
最小生成数
对于一个带权无向图G（V，E），T为所有生成树中权值之和最小的那颗生成数，则T称为G的最小生成树。
prim算法
时间复杂度为O（V^2）不依赖E，因此适合求解稠密图的最小生成树
kruskal算法
时间复杂度：O（ElogE) ，适用于边稀疏而顶点多的图。
最短路径
Dijkstra算法求单源最短路径问题
时间复杂度：邻接表－O（N^2)，邻接矩阵－O（N^2）
边上有负权值时，不适用
Floyd算法求各顶点之间最短路径问题
A^k[i][j] = min(A^k-1[i][j], A^k-1[i][k] + A^k-1[k][j])
时间复杂度：O（V^3)
允许图中有带负权值的边，但不允许有包含负权值的边组成的回路。
有向无环图描述表达式
若一个有向图中不存在环，则称为有向无环图DAG图
拓扑排序
AOV网：用DAG图表示一个工程，其顶点表示活动，有向边<i,j>表示活动vi必须先与活动vj，将这种有向图称为顶点表示活动的网络（AOV网）
常用于检查有向图是否存在环。求依赖关系
关键路径
在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，称为用边表示活动的网络（AOE网）。 AOE网和AOV网都是有向无环图，不同之处在于她们的边和顶点所代表的含义是不同的，AOE网中的边有权值；而AOV网中的边无权值，仅表示顶点之间的前后关系
事件vk的最早发生时间ve(k): ve(k) = max(ve[j] + weight(j,k))，weight(j,k)为<j,k>的权值
事件vk的最迟发生时间vl(k): vl(k) = min(vl(j) - weight(k,j)), weight(k,j) 为<k,j>的权值
活动ai的最早开始时间e(i): 边<k,j>表示活动ai,e(i) = ve(k)
活动最晚开始时间l(i): <k,j> 表示活动l(i)，则l(i) = vl(j) - weigh(k,j)
活动最迟开始时间l(I)和最早开始时间e(i)的差额：d(i) = l(i) - e(i)，d(i)=0的活动室关键活动，根据关键活动得到关键路径。
关键活动缩短到一定程度，该关键活动可能会变成非关键活动。
有几条关键路径的网，只提高一条关键路径上的关键活动并不能缩短整个工程的工期，只有加快那些包含在所有关键路径上的关键活动才能缩短工期。
查找
顺序查找和折半查找
顺序查找又称线性查找，它对顺序表和链表都是适用的。
一般线性表的顺序查找：查找成功元素的平均比较次数为(n+1)/2，查找不成功元素的平均比较次数为n
有序顺序表查找：查找成功的平均比较次数为n(n + 1)/2，查找不成功的平均比较次数：n/2
折半查找
有称二分查找，适用于有序的顺序表，通过和序列中间元素比较确定目标元素的位置，再缩小区间，逐渐接近目的元素。
分块查找
又称索引查找，在索引表中确定待查找记录所在块，可以顺序查找或折半查找；在块内顺序查找
块数为根号n时，平均查找长度最小。
树型查找
二叉排序数
具备左子树节点值<根节点值<右子树节点值，所以对二叉排序树中序遍历可以得到一个递增的有序序列
二叉排序树的删除：在二叉树删除若是叶子节点之间删除，否则找到前驱节点或者后继节点代替自己，转去删除前驱节点或后继节点
二叉排序数的查找效率分析：二叉查找树的查找效率，主要取决于子树的高度。左右子数高度差不超过1的为平衡二叉树，平均查找长度为O（log n)
平衡二叉树
避免树的高度增长过快，规定在插入和删除二叉树节点时，要保证任意节点的左、右子树高度差不超过1，这样的二叉树称为平衡二叉树。
平衡二叉树的插入： 插入后LL型需要右旋，插入后RR型需要左旋，插入后LR型需先左旋再右旋，插入后为RL型需先右旋再左旋
平衡二叉树的删除： 删除非叶子节点需要转换成删除叶子节点。删除后导致的不平衡，调整方式和插入一样。
平衡二叉树的查找：时间复杂度为O（log N)
假设用Nh表示深度为h的平衡二叉树中含有的最少节点数。N0 = 0，N1=1，N2 = N1 + N0 + 1，.... , Nh = Nh-1 + Nh-2 +1
红黑数
性质
每个节点或是红色的，或是黑色的
根节点是黑色的
叶节点（虚构的外部节点、NULL节点）都是黑色的。
不存在两个相邻的红节点（即红节点的父节点和孩子节点均是黑色的）
对每个节点，从该节点到任一叶节点的简单路径上，所含黑节点的数目相同
结论
从根到叶子节点的最长路径不大于最短路径的2倍
有n个内部节点的红黑数的高度h<= 2log2 (n+1)
新插入红黑数的结点初始着为红色。
红黑数的插入调整
主要看新插入节点的叔结点
叔叔节点是黑节点，则通过LL，LR，RR，RL型旋转后再交换节点颜色达到平衡
叔叔节点是红节点，将父节点和叔节点设置为黑色，将祖父节点设置为红色视为新插入的节点向上迭代
红黑数的删除调整
主要看删除位置节点的兄弟节点
若兄弟节点是红节点，做一次左旋或者右旋得到x的兄弟为黑色
若兄弟为黑色，兄弟节点的左节点为红色，则对兄弟节点左旋或右旋得到兄弟节点为黑色，兄弟的右节点为红色
若兄弟为黑色，兄弟的右节点为红色，将兄弟右节点设为黑色后以父节点左旋，再交换颜色将自生设置为单黑
若兄弟为黑色，且兄弟的左右节点都是黑色，则将自己和兄弟脱去一层黑色，父节点加上一层黑，从父节点开始迭代
B数和B+数
B数及其基本操作
B树中所有节点的孩子个数最大值称为B树的阶
m阶B树性质
树中每个节点至多有m棵子树，即至多含有m-1个关键字
若根节点不是终端节点，则至少有两颗子树。
除根节点外的所有非叶子节点至少有ceil(m/2)颗子树，至少含有ceil(m/) - 1个关键字。（*ceil()表示向上去整，floor()表示向下取整）
所有非叶子节点结构如下： N| P0 | K1 | P1 | K2 | .... | Kn | Pn| N为节点中关键字的个数，Pi为指向子树根节点的指针，Ki为关键字
B数的高度（磁盘存取次数）
不熟每个节点最多有m棵子树，m-1个关键字，所以一颗高为h的m阶B树有n <= m^h -1; 故有h >= logm n+1
若让每个节点中的关键字个数最少：第一层1个节点；第二层2个节点；第三层至少2ceil(m/2)；h+1层至少有2ceil(m/2)^(h-1)个节点。 有n个节点的B树查找不成功的节点(外部节点或NULL)为n+1，有n + 1 >= 2ceil(m/2)^(h-1), 即 h <= log ceil(m/2) ((n +1)/2 +1)
B树的插入分裂：从中间位置ceil(m/2)将其中的关键字分为两个部分，左部分包含关键字放在原节点中，右部分包含关键字放到新节点中，中间位置节点插入原节点的父节点中
B树的删除：非终端节点的删除转换为终端节点的删除
终端节点内的关键字数大于ceil(m/2) - 1,则直接删除
终端节点的个数为<=ceil(m/2)- 1，若相邻的节点关键字子数>=ceil(m/2)则调整父节点和相邻的元素，借一个
若相邻节点个数均<= ceil(m/2) -1，则将发生合并操作，若根节点关键字减少到1，有两颗子树则合并两个子树成为新根。
B+树的基本概念
m阶B+树的性质
每个分支节点最多有m棵子树
非叶根节点至少有两颗子树，其他每个分支结点至少有ceil(m/2)棵子树。
节点的子树个数与关键字个数相等
所有叶子节点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小排序，并且相邻叶节点按大小顺序相互链接起来
所有分支节点（可以视为索引的索引）中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针
m阶B+树与m阶的B树主要差异
B+树中，n个关键字含有n个子结点，而在B树中，有n个关键字的结点含有n+1课子树
B+数中，每个节点（非根内部节点）关键字个数的范围为ceil(m/2) <= n <= m （根节点：2 <= n <= m） B树中每个结点（非根内部节点）的关键字个数ceil(m/2) - 1 <= n <= m -1, （根节点：1 <= n <= m - 1)
B+树中，叶结点包含信息，所有非叶节点仅起索引作用，非叶子节点的索引项只有对于子树的最大关键字和指向该子树的指针，不含该关键字对应记录的存储地址。
B+树中，叶结点包含了全部关键字，即非叶节点中出现的关键字也会出现在叶子节点中
B+的查找每次都是一条从根节点到叶节点的路径
散列表
散列表建立了关键字和存储地址之间的一种直接映射关系
散列函数的构建方法
直接定址法：H（key) = key或 H（key) = a*key +b
除留余数法：H（key) = key % p
数字分析法：进制转换成十进制
平方取中法
处理冲突的方法
开放定址法
线性探测法：Hi=（H（key) + di) % m
平方探测
双散列法：Hi = (H(key) + i * Hash2(key)) % m
伪随机序列法
拉链法
散列表性能分析
散列表查找效率取决于三个因素：散列函数、处理函数、处理冲突的方法和装填因子 装填因子： a = 表中记录数 / 散列表长度
排序
排序的基本概念
排序，重新排列表中的元素，使表中的元素满足关键字有序的过程
算法稳定性：待排序表中有两个元素Ri和Rj，其对应关键字相同即keyi=keyj,且Ri在Rj前面，排序完后Ri仍在Rj前面，则排序算法是稳定的，否则是不稳定的。
插入排序
将待排序的元素插入有序序列的合适位置
时间复杂度O（n^2），空间复杂度O（1），最好情况下O（n）最坏情况下 O(n^2)
每次插入元素总算从后向前比较移动，是个稳定的排序算法
折半插入排序
通过二分找到适合插入的位置，减少了比较次数，但是移动次数没有变，时间复杂度依旧O（n^2)
希尔排序
将待排序表分割为若干子表，对各个子表进行插入排序，待整个表中元素基本有序再进行一次插入排序。
时间复杂度O（n^1.3) 最坏情况O(n^2) 空间复杂度O（1）
是个不稳定的排序算法
交换排序
冒泡排序
时间复杂度O（n^2) 最好情况O（n) 最坏情况O(n^2)
是个稳定的排序算法
快速排序
时间复杂度O（nlog n) 最好情况下O（nlogn) 最坏情况O(n^2) 空间复杂度O(log n ) 最坏O（n)
是个不稳定的排序算法
选择排序
简单选择排序
时间复杂度O（n^2) 最好最坏都是O（n^2) 空间复杂度O（1）
是个不稳定的排序算法
堆排序
堆的调整时间和数高有关为O（log n ) 。在n个元素的堆初始化，关键字的比较总次数不超过4n，初始化时间复杂度O(N)
时间复杂度O(nlogn) 空间复杂度O（1）
是个不稳定的排序算法
归并排序和基数排序
归并排序
时间复杂度O(nlog n) 空间复杂度O（n)
是个稳定的排序算法
基数排序
借住多关键字拍下的思想对单逻辑关键字进行排序的方法
时间复杂度O(d（n + r）） d为位数、n为关键字数，r为队列数
是个稳定的排序算法
各种内部排序算法的比较及应用
从时间复杂度看：简单选择排序、直接插入排序、冒泡排序－O（n^2) 直接插入排序、冒泡排序－最好情况O（n） 堆排序、快速排序、归并排序－O（nlog n)
从空间复杂度看：简单选择排序、插入排序、冒泡排序、希尔排序、堆排序－O（1） 快速排序、归并排序－最好情况O（log N) 最坏情况O（n) 归并排序－O（n)
从稳定性看：插入排序、冒泡排序、归并排序、基数排序－稳定的排序算法 简单选择排序、快速排序、希尔排序、堆排序－不稳定的排序算法
选取排序方法需要考虑的因素： 待排序的元素数目n 元素本身信息量大小 关键字本身的机构及分布 稳定性要求 语言工具，存储结构，辅助空间的大小
外部排序
外部排序的方法：通常采用归并排序方法，包含两个阶段，首先是对归并段的排序，其次是进行逐躺归并 外部排序的总时间=内部排序所需的时间 +外存信息读写的时间 + 内部归并所需的时间
多路归并与败者树
败者树：通过分支节点记录左右子树中的失败者，让胜利者往上继续比较。k路败者树深度为ceil(log k)，因此从k个记录中选择最小关键字，最多需要ceil(log k)次比较
置换－选择排序（生成初始归并段）
采用内部排序方法得到的各个初始归并段长度都相同（除最后一个段外），它依赖内部排序时可用内存工作区的大小。 用置换－选择算法可以产生更长的初始归并段。
设某个初始归并段为s ={},工作区w = {}, 输入文件F = {} 一个初始段生成算法描述： 初始s为空，w为工作区大小； while ai = min(w) and (ai >= max(s)): //找出w中最小且大于等于s中所有元素的元素ai s = s + ai //ai加入初始段 bi = get(f) //从输入文件中顺序读取元素 w = w - ai + bi //放入工作区
最佳归并数
归并段的元素个数不同，在归并时可以利用哈夫曼树找出最佳归并方案
k叉哈夫曼树满足：no = (k - 1)nk + 1，其中nk为度为k的节点数，而n0为度为0的节点数
添加虚端: 初始段个数可能不能正好构建成最佳归并数，故需要添加个数为0的虚段。 nk = (n0 - 1)/(k -1) 其中nk一定为整数，而n0为初始段r和需要填写的虚段数u。 所以得到要添加的虚端为u=(k - 1) - (r - 1)/(k - 1), u为小于k-1的数。