第2章?基本数据结构及运算
数据处理：数据如何组织，以便提高处理速度，节省存贮空间——关键问题。
研究内容：
逻辑结构：数据元素间的关系。
物理结构/存贮结构：各数据元素在计算机中的存贮关系。
运算：对各种数据结构的操作。
2.1 数据结构的基本概念数据处理：对数据元素进行运算：包括插入、删除、查找、更新等，也包括分析。
建立数学模型固然好，但有时难以表示成模型，感兴趣的是数据元素之间的关系。为了提高处理效率，应如何组织他们，即如何表示数据元素。
书上通过实例说明数据采用不同表示方法对处理效率的影响。
数据结构是一门研究数据如何组织、存储和运算的一般方法的学科。
2.1.2 什么是数据结构数据：描述客观事务的数字符以及所有能输入计算机中并被程序识别和处理的符号的集合，计算机处理的对象。
数据元素(Data Element),数据的基本单位。
一个数据元素可由若干数据项(Data Item)组成。
数据项：数据的最小单位。
数据元素亦称结点或记录数据项亦称字段或域
数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。
数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。
数据的逻辑结构
数据结构可描述为 Group=（D，R）
D：有限个数据元素的集合；R有限个结点间关系的集合例题见书图形表示：见书
数据的存贮结构
2.1.4 线性数据结构与非线性数据结构
A,线性结构（一对一）
特性：1.有且只有一个根结点
2.每个结点最多一个前件，最多一个后件。（第一个数据元素无前件，最后一个无后件，其它 有且仅有一个前驱和一个后继。）
例：（A,B,C,·······,X,Y,Z）
例,学 生 成 绩 表
B．非线性结构:树形结构（一对多）
B．非线性结构:图形结构（多对多）
D={ 1,2,3,4}
R={(1,2),(1,3),(1,4),(2,3)
(3,4),(2,4) }
2、数据的存储结构
A,顺序存储顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。
顺序存储结构的三个弱点：
1.插入或删除操作时，需移动大量元素。
2.长度变化较大时，需按最大空间分配。
3.表的容量难以扩充。
B.链式存储
每个节点都由两部分组成：数据域和指针域。
数据域存放元素本身的数据，指针域存放指针。
数据元素之间逻辑上的联系由指针来体现。
链式存储结构特点：
1.比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成)。
2.逻辑上相邻的节点物理上不必相邻。
3.插入、删除灵活(不必移动节点，只要改变节点中的指针)。
2.2 线性表及其存贮结构线性表逻辑结构
n个数据元素的有限序列:(a1,a2,a3,…an)
n为线性表的长度(n≥0)，n=0的表称为空表特性：
数据元素呈线性关系.
所有数据元素ai在同一个线性表中须是相同的数据类型线性表的基本运算：
(1)插入：在两个确定的元素之间插入一个新的元素；
(2)删除：删除线性表中某个元素；
(3)修改：按某种要求查找元素，需要时，还可找到元素进行值的更新；
1.顺序存储结构及插入删除运算
.线性表的顺序存储结构,可用C语言中的一维数组来描述.
#define LISTINITSIZE 100 //线性表存储空间的初始分配量
typedef struct{
ElemType *elem；//数组指针表示存储空间基址
int length； //当前长度
int listsize //当前分配的存储容量（以sizeof（ElemType）为单位）
}Sqlist
Status ListInsert_sq（Sqlist (V，int i,ElemType x）
{
//在线性表V中第i个元素之前插入x,i 的合法值为 1( i(V.Length+1
if（i<1‖i>V.length+1）return ERROR; //i值不合法
if(V.length>V.listsize) return OVERFLOW; //无存储空间
q=(V.elem[i-1]; //下行注：插入位置后的元素依次右移
for(p=(V.elem[V.length-1]; p>=q; ( (p)
((p+1)= (p;
(q=x; // 插入x
++V.length; //表长加1
return OK;
}
Status ListDelete_sq（Sqlist (V，int i,ElemType x）{
if（i<1‖i>V.length）return ERROR;
P=(V.elem[i-1];
x =(P;
q= V.elem+ V.length(1 ;
for(++p;p<=q;++p) *(p(1)=*p
( (V.length;
return OK;
}
2.链式存储结构及插入删除运算特点：用一组任意的存储单元(可以是连续的,也可以是不连续的)存放线性表的数据元素。
上图为(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG)
线性表的线性链表存储结构，存储从头指针开始进行。
（1）线性表的单链式存储结构线性表的链式存储结构可用C语言中的“结构指针”来描述
Typedef struct Lnode
{
Elem Type data；
struct Lnode *next；
} Lnode，*linklist；
单链表的插入运算
ListInsert_L(LinkList &L,int i,ElemType x){
p=L; j=0;
while( p&&j<i-1)
{p=p->next; ++j;}
if( ! p (( j>i-1) return ERROR;
s=(struct LNode *)malloc(sizeof(struct LNode));
s->data=x; s->next=p->next; p->next=s;
return OK;
}
单链表的删除运算
ListDelete_L(LinkList &L，int i,ElemType x){
p=L; j=0;
while( p->next && j<i-1)
{ p=p->next; ++j; }
if( ! (p->next) (( j>i-1) return ERROR;
q=p->next ; p->next=q->next; free(q);
return OK;
}
（2） 循环链表 P64
将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。
（3） 双向链表 P55
在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。—插入和删除作业2,对以下单链表分别执行下列各程序段,并画出结果示意图.
(1) L=P->link;
(2) R->data=P->data;
(3) R->data=P->link->data;
(4) P->link->link->link->data=P->data;
(5) T=P;
while(T!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
(6) T=P;
while(T->link!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
(8) T=L;
T->link=P->link;
free(P);
(9) S->link=L;
习题：2。10 逆转线性单链表扫描单链表,将第一个节点的next设置为NULL,将第二个节点的next指向第一个节点,将第三个节点的next指向第二个节点,…
Invert(head)
Node *head;
{ node *p,*q,*r;
P=head; q=p—>next;
While (q!=NULL)
{ r=q—>next; q—>next=p; p=q; q=r; }
head—>next=NULL;
head=p;}
3.3 栈
1,栈 stack的定义栈是特殊的线性表，仅在表的一端进行插入或删除操作
特点：（1）对栈内数据的操作总在栈顶进行
（2）数据进栈称为“压入”push
（3）数据出栈称为“弹出”pop
（4）遵循“后进先出”的原则LIFO
例题：输入顺序A,B,C，输出顺序有几种？
ABC,ACB,BAC,BCA,CBA,不可能产生CAB
2.栈的顺序存储结构及运算用数组实现栈,a[0]为栈底，top为栈顶
（1）定义
typedef struct stack_type{
elemtype data[MAXNUM];
int top;
}stack_type;
（2）进栈 push
当新元素进栈时，栈顶上移，新元素放在栈顶。
stack.top = stack.top + 1; stack.data[stack.top] = new_one;
（3）出栈 pop,从栈顶移出一个数据。
栈顶元素拷贝出栈，栈顶下移
elemptype pop(stack_type *stack)
{ elemtype out;
if(stack->top < 0) error(3);
else{
out = stack->data[stack->top];
stack->top = stack->top -1;
}
return out; }
（4）栈空判断
stack.top = = 0 (stack.top < 0)
栈满判断：stack.top >= MAXNUM - 1;
（5）置栈空
stack.top = -1;
（6）栈的应用例 程序的嵌套，中断的嵌套见书P35
3.栈的链式存储结构及运算用链表实现栈
（1）定义
typedef struct lstack_type{
node_type * top;
int length;
}lstack_type;
（2）压入push
void push(stack,new_node){
new_node->next = stack->top;
stack->top = new_node;
stack->length ++;}
（3）弹出pop
node_type * pop(stack){
node_type* out;
out = stack->top;
stack->top = stack->top->next;
stack->length --;
return out;}
（4）栈空判断
stack.top == NULL;
（5）置栈空能否简单的使用 stack.top = NULL?
如果栈中还有链点，必须逐个将链点占用的空间释放
1、逐个将链点弹出
2、释放链点空间
void clean(stack){
node_type * temp;
while( ! empty(stack)){
temp = pop(stack);
free(temp); }
}
3.4 队列
1.队列定义类似于排队机制的结构,队列是特殊的线性表，
节点的插入仅限于在表尾进行，节点的删除仅限于在表头进行.
队列特点特点：
（1）对队列的操作在表的两端进行
（2）仅在队尾加入节点——入队enqueue
（3）仅在队首移出节点——出队dequeue
（4）遵循“先进先出”的原则——FIFO
队列的顺序存储结构及运算
2,用数组实现队列
（1）定义
typedef struct queue_type
{ elemtype data[MAXNUM];
int front;
int rear;
}queue_type;
（2）入队与出队用循环数组实现队列
void enqueue(queue,new_one)
{ if( (queue->rear + 1) % MAXNUM = = queue->front ) error(1);
else{ queue->data[queue->rear] = new_one;
queue->rear = (queue->rear +1) % MAXNUM;
}
}
elemtype dequeue(queue)
{ elemtype out；
if( queue->rear = = queue->front ) error(2);
else{ out ＝queue->data[queue->front];
queue->front = (queue->front +1) % MAXNUM;
}
return out；
}
思考：数组Q[0,4]
front=1,rear=3
front=3,rear=1
3．用链表实现队列
（一）定义
typedef struct lqueue_type
{ node_type * front;
node_type * rear;
int length;
}
（二） 入队新链点插入到队尾注意：队列为空时，rear和front都要指向新元素
new_node->next = NULL; list->rear ->next = new_node;
（三） 出队删除队首链点注意：当队列被删空时，rear指针要置空
temp = list->front; list->front = list->front->next;
习题:
例1 若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的一个出栈次序是（ d ）。
(a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3
例2 用一维数组设计栈，初态是栈空，top=0。现有输入序列是 a、b、c、d，经过 push、push、pop、push、pop、push操作后，输出序列是（ b,c ），栈顶指针是（ 2 ）
例 3 对于下面的程序调用过程，请问入栈序列是（1,2,3 ），出栈次序是（ 2,1,3）。
例4 设栈S为空，队Q的状态是abcd，其中a为队首元素，d为队尾元素，经过下面两个操作后，队Q的状态是（ c ）。
（1）删除队Q中的元素，将删除的元素插入栈S，直到队Q为空。
（2）依次将栈S中的元素插入队Q，直到栈S为空。
(a) abcd (b) acbd (c) dcba (d) bacd
例5 Josephus问题
设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，。。。，如此反复直到所有的人都出局为止。下面要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。请以n=9,s=3,m=4为例，模拟Josephus的求解过程求问题的解。
用顺序表结构和循环单链表结构求解Josephus问题的一般步骤为,
1）首先利用线性表的一些运算如创建空线性表、插入元素等构造Josephus表；
2）从Josephus表中的第s个结点开始寻找、输出和删除表中的第m个结点，然后再从该结点后的下一结点开始寻找、输出和删除表中的第m个结点，重复此过程,
3.5 二维数组（矩阵）
1.二维数组定义行关系，列关系均是线性关系
2,二维数组的顺序存放
（一）行优先存放：a11 a12..,a1na21 a22..,ai1 ai2,..ain..,am1 am2,.,amn
计算aij的存放位置：设每个元素占据S个存储单元
Loc(aij) = Loc(a11) + (( i - 1)*n + (j - 1))*S 计算前面有多少个元素
（二）列优先存放
a11 a21..,am1a12 a22..,am2a1j a2j,..aii..,a1n a2n,.,amn
Loc(aij) = Loc(a11) + (( j - 1)*m + (i - 1))*S
3,规则矩阵的压缩存储
(1)对称矩阵，三角矩阵的压缩对称矩阵：a[ i,j ] = a[ j,i ]
三角矩阵：上三角为0，或下三角为0
只存储上或下三角内的元素，节约近一半的存储空间
(1)对称矩阵，三角矩阵的压缩
i >= j 时，元素位于下三角
Loc(aij) = Loc(a11) + ( i ( i - 1) / 2 + ( j - 1))*S
i < j 时，元素位于上三角
Loc(aij) = Loc(a11) + ( j ( j - 1) / 2 + ( i - 1))*S
(2)稀疏矩阵矩阵中的非零元素很少，分布没有规律利用三元存储法 （行值，列值，元素值）
先形成三元矩阵再按照行优先顺序方式存储。
稀疏矩阵三元组定义
1)定义三元组元素
typedef struct tuple3tp{
int row_num; /*行号*/
int col_num; /*列号*/
elemtype value; /*元素值*/
} tuple3tp
2)定义三元组
typedef struct tuple3{
int row; /*行数*/
int col; /*列数*/
int num; /*非零元素个数*/
tuple3tp data[ MAXNUM];/* 三元组*/
}tuple3;
3.5 树与二叉树
3.5.1 树的基本概念
1,树的定义树是以分支关系定义的层次结构。
倒生树：树根在上，根上分茎，茎上分叶是族谱、社会组织机构一类实体的逻辑抽象对定义的理解
（1）有限集
（2）递归定义：树，根，子树
（3）有且仅有一个根结点不存在空树
（4）子树是互不相交的有限集
（5）树的层次性除根结点以外的结点有且仅有一个父结点树是一种数据结构
Tree = ( D,R )
D：元素的集合
R：元素关系的集合
（父、子关系 前驱、后继关系）
各结点没有或仅有一个父结点有且仅有一个根结点各结点可以有任意个子树
2,树的术语
1）结点
根结点,没有前驱，仅有后继
(茎)分支结点,有且仅有一个前驱，可以有多个后继叶结点,没有后继，仅有前驱
2）度与深度结点的度：该结点拥有的子树数目。
树的度：最大的结点度深度：最大的层次数
3）A节点的双亲,孩子,兄弟,祖先,子孙
4）路径（树枝，分支）
从K1出发自上而下到K2所经历的所有结点序列
5）有序树与无序树有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。
6）森林不相交的树的集合
3.5.2 二叉树
1、定义二叉树是结点的有限集，或为空，或由根的左、右子树组成，左右子树又分别是符合定义的二叉树。
对比树的定义：
空二叉树 树的定义中没有空树的概念不多于2个孩子 树的节点可以有任意个子树子树有左右之分 无序树可不区分左右树的其它定义适用于二叉树：根茎叶、度、路径
（2）二叉树的形态：5种
2,二叉树的性质
（1）在二叉树的第i层上最多有2i-1个结点第i层的结点数最多是第i-1层的两倍
（2）深度为k的二叉树最多有2k - 1个结点
（3）叶结点数比具有两个孩子的结点数多 1 个
（3）叶结点数比具有两个孩子的结点数多1个设n0为叶结点个数，
n1为具有一个孩子的分支结点个数，
n2为具有两个孩子的分支结点个数，
n为结点总个数结论,n0 = n2 + 1;
条件1,n = n0 + n1 + n2
条件2,n = 分支的个数 + 1
设为分支的个数为B
条件3,B = 2 n2 + n1
所以,2n2 + n1 + 1 = n0 + n1 + n2
（4）深度为K的满二叉树，结点个数为2k-1
满二叉树：所有的结点有两个孩子,所有的叶结点都位于同一层。
满二叉树：“装满”节点的二叉树半满二叉树：深度为K的二叉树，K－1层是满二叉树，K层节点个数不足2K－1个
（5）具有n个节点的完全二叉树，深度为 [log2n]+1
完全二叉树：特殊的半满二叉树，最后一层节点从左至右依次排列，没有间断。
如果对节点数为n的完全二叉树自上而下，从左至右依次编号，则节点i的父结点为[ i / 2 ]
若2i≤n，则i的左后继是2i；若2i>n,则i无左后继若2i＋1≤n，则i的右后继是2i＋1；若2i>n,则i无右后继关于完全二叉树的其他描述形式如果对满二叉树的节点从上至下，从左至右连续编号，具有n个节点的完全二叉树各节点与同样深度的满二叉树的前n个节点一一对应叶节点仅位于下两层，对任一节点，若其右子树的深度为1，则其左子树的深度不小于1
3.5.4 二叉树存储
1,顺序存储二叉树将完全二叉树从上到下，从左到右编号后，结点号码可作为数组的下标，从而将完全二叉树顺序存储下来。当给出任意结点i，我们可以知道它的父结点为[ i/2 ]，两个孩子分别为2i和2i＋1。
一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来。以维持结点编号之间的父子换算关系如此存放，将浪费较多空间
2,用链表实现二叉树二叉树链点的定义
typedef struct tnode_type{
elemtype data;
struct tnode_type *Lchild;
struct tnode_type *Rchild;
}tnode_type;
二叉树的定义
typedef struct tree_type{
tnode_type *root;
int num;
}tree_type;
每个结点由数据域、左指针域和右指针域组成。
3.5.5 二叉树的遍历遍历：指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。
作用：查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。
特点:
以根被访问顺序来划分不同的遍历方法在子树的访问顺序中始终以左子树优先
1）先根遍历（先序遍历）
2）中根遍历（中序遍历）
3）后根遍历（后序遍历）
中根遍历算法遍历过程：从根开始
1、找到B，但不访问B
2、根据B找到A，访问A
3、再回到B、访问B
4、根据B找到C，访问C
方法一、利用栈来实现回朔
1、树（子树）根入栈，不访问
2、左子树入栈，左子树的各子树根依次入栈即反复进行步骤1
3、当左子树为空时，出栈，访问根结点
4、根节点右子树入栈（新树入栈，到步骤1去遍历右子树）
5、当右子树为空时，出栈，访问（祖先）爷结点，将爷结点的右子树入栈
（新树入栈，回到步骤1)
总结：树入栈后一直朝左走（一路进栈），走不动时出栈并访问节点。同时将该节点右子树入栈。如果其右子树为空，就再出栈一个节点，访问，出栈节点右子树入栈
方法二：利用递归调用来实现回溯
void inorder( root )
{ if( root->Lchild != NULL) inorder (root->Lchild);
process(root);
if( root->Rchild != NULL) inorder(root->Rchild);
}
对比递归与非递归算法递归算法更简洁，更多依靠系统提供的“用户程序调用栈”，该栈的使用对用户是不可见的非递归算法在算法中直接掌握栈结构的调用二叉树的深度决定了递归调用的深度，决定了栈的长度。
当二叉树的深度较深时，系统提供的“用户程序调用栈”可能出现溢出，这时需要算法自行掌握栈的使用。
例：二叉排序树建立二叉树时，将关键值小于根结点的结点放在左子树，关键值大于根结点的的结点放在右子树，就可以形成一颗二叉排序树如学生成绩分别为71、65、40、88、67、90、60、70、77……，以下方式建立二叉排序树
（中序遍历二叉排序树，获得从低到高的排序结果！）
例:已知前序遍历：ABCDEFG 中序遍历：CBDAFEG
写出该二叉树的后序遍历,C D B F G E A
分析：前序遍历中的第一个元素必为二叉树的根结点。
中序遍历中的根结点恰为左、右子树的分界点。
例:已知后序遍历：CDBFGEA 中序遍历：CBDAFEG
写出该二叉树的前序遍历
分析：后序遍历中的最后一个元素必为二叉树的根结点。
中序遍历中的根结点恰为左、右子树的分界点。
3.5.6 树和森林转换为二叉树
（1）树转换为二叉树 (特点：转换后的二叉树，根结点没有右子树)
方法：·对每个孩子进行从左到右的排序；
在兄弟之间加一条连线；
对每个结点，除了左孩子外，去除其与其余孩子之间的联系；
以根结点为轴心，将整个树顺时针转45度。
(2) 森林与二叉树的转换方法：
· 将各棵树分别转成二叉树；
· 把每棵树的根结点用线连起来；
· 以第一棵树的根结点作为二叉树的根结点，按顺时针方向旋转。
3.5.7 二叉树的应用例：建立二叉排序树，进行排序和提高查询算法效率问题分析输入：一组无序元素输出：二叉排序树核心算法分析分析从假设二叉排序树已部分建立，现输入一个新元素开始核心算法分析
1、新元素与树根结点比较。
2、如果比根小，则取根的左子树，回到1；如果根无左子树，则将新结点插入在根结点左孩子处
3、如果比根大，取根的右子树，回到1；如果根无右子树，则将新结点插入在根结点右孩子处
例：哈夫曼树 最优二叉树 最小费用树什么是哈夫曼树、怎样建立、有什么用?
哈夫曼树是最优二叉树最优？路径带权总长最小路径？从树根到节点经历的分支序列，路径长度是分支数目总长？从根到所有节点的路径长度之和带权？（仅）叶节点带有权值带权路径长度：路径长度×权值树的带权路径长度：所有带权路径长度之和
带权路径长：5×2＋7×2＋2×2＋4×2＝36
5×2＋7×3＋4×3＋2×1＝46
2×3＋4×3＋5×2＋7×1＝35
哈夫曼树的建立
哈夫曼树的应用：利用哈夫曼树构造通讯中电文编码
例：要传输的电文是{CAS；CAT；SAT；AT}
3.6 图
图的邻接矩阵实现
typedef struct graph_m{
elemtype node[MAXNUM]; 顶点集合
int arcs[MAXNUM][MAXNUM]; 边的邻接矩阵
}graph_m;
图的邻接表存储法的特点优点：节省存储空间，边的插入和删除操作比较简便缺点：结构复杂，具有两种不同的基本组成单元
图的遍历 深优
1,深度优先遍历
（1）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。
（2）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。
（3）对于前两个步骤是递归的
深度优先遍历的特点
“深度”：总是访问顶点的一个相邻顶点，好像是沿着图中的一条路径走到“底”，然后后退一点，再选一条路。如此“进进退退”，直到所有顶点都被访问对于连通图，如果第一个被访问的顶点的所有相邻顶点都被访问了，意味着图中所有顶点都被访问了。
即栈空时用递归调用实现深度优先遍历算法
void dfs （g，v）
{ visit（v）；visited[ v ] = 1; 1 访问顶点v
p = g[v]->next_adj 2取得顶点的一个未被访问过的顶点w；
while(p != NULL){
w = p->node_index;
if(visited[w] == 0)
3 dfs（g，w）； 回到2；
p = p->next_adj; 4重复2，3直到该顶点所有的相邻顶点都被访问过；
广度优先遍历的特点
“广度”：总是在访问了一个顶点后，依次访问它的所有相邻顶点。然后再从它的第一个相邻顶点开始，访问其所有的相邻顶点。如此逐个顶点地逐步扩散，直到所有的顶点都被访问。
广度优先遍历操作具有队列操作的特点，当从队列中取出最后一个顶点，发现该顶点的所有相邻顶点都被访问过时，意味着图中所有的顶点都已被访问过
4,拓 扑 排 序按一定顺序进行的活动，可以使用顶点表示活动、顶点之间的有向边表示活动间的先后关系的有向图来表示，这种有向图称为顶点表示活动网络(Activity On Vertex network，简称AOV网)。
AOV网中的有向边表示了活动之间的制约关系。
将AOV网中的所有顶点排列成一个线性序列vi1,vi2,…,vin，并且这个序列同时满足关系：若在AOV网中从顶点vi到顶点vj存在一条路径，则在线性序列中vi必在vj之前，我们就称这个线性序列为拓扑序列。把对AOV网构造拓扑序列的操作称为拓扑排序。
在实际的意义上，AOV网中存在的有向环就意味着某些活动是以自己为先决条件，这显然是荒谬的。例如对于程序的数据流图而言，AOV网中存在环就意味着程序存在一个死循环。
任何一个无环的AOV网中的所有顶点都可排列在一个拓扑序列里，拓扑排序的基本操作如下：
(1) 从网中选择一个入度为0的顶点并且输出它。
(2) 从网中删除此顶点及所有由它发出的边。
(3) 重复上述两步，直到网中再没有入度为0的顶点为止。
以上的操作会产生两种结果：
一种是网中的全部顶点都被输出，整个拓扑排序完成；
另一种是网中顶点未被全部输出，剩余的顶点的入度均不为0，则说明网中存在有向环。
用以上操得到了一种拓扑序列：
C1,C2,C3,C4,C5,C7,C9,C10,C12,C11,C6,C8。
拓扑序列可以是 多 种
5,关键路径 AOE网络(Activity On Edge network)：
有向边：表示一个子工程（活动）
边上的权值：表示一个活动持续的时间顶点：表示事件，它表示了一种状态，即它的入边所表示的活动均已完成，它的出边所表示的活动可以开始。这种带权的有向网络称为 AOE网络(Activity On Edge network)，即边表示活动网络。
关键路径：
从源点到汇点的具有最大路径长度的路径。
关键活动：
关键路径上的各个活动。
明确了哪些活动是关键活动就可以设法提高关键活动的功效，以便缩短整个工期。
按(1)式和(2)式，可计算出图该AOE网各个事件的最早发生时间和最迟发生时间：
ve(1)=0
ve(2)=max{ve(1)+dur(<1,2>)}=max{0+3}=3
ve(3)=max{ve(1)+dur(<1,3>)}=max{0+2}=2
ve(4)=maw{ve(2)+dur(<2,4>),ve(3)+dur(<3,4>)}=max{3+4,2+3}=7
ve(5)=max{ve(4)+dur(<4,5>),ve(2)+dur(<2,5>)}=max{7+4,3+8}=11
ve(6)=max{ve(3)+dur(<3,6>),ve(4)+dur(<4,6>)}=max{2+7,7+2}=9
ve(7)=max{ve(5)+dur(<5,7>),ve(6)+dur(<6,7>)}=max{11+9,9+6}=20
vl(7)=ve(7)=20
vl(6)=min{vl(7)－dur(<6,7>)}=min{20－6}=14
vl(5)=min{vl(7)－dur(<5,7>)}=min{20－9}=11
vl(4)=min{vl(5)－dur(<4,5>),vl(6)－dur(<4,6>)}=min{11－4,11－2}=7
vl(3)=min{vl(4)－dur(<3,4>),vl(6)－dur(<3,6>)}=min{7－3,14－7}=4
vl(2)=min{vl(4)－dur(<2,4>),vl(5)－dur(<2,5>)}=min{7－4,11－8}=3
vl(1)=min{vl(2)－dur(<1,2>),vl(3)－dur(<1,3>)}=min{3－3,4－2}=0
关键活动算法主要由以下步骤组成：
(1) 对AOE网进行拓扑排序，同时按拓扑排序顺序求出各顶点事件的最早发生时间ve，若网中有回路，则算法终止，否则执行(2)。
(2) 按拓扑序列的逆序求出各顶点事件的最迟发生时间vl。
(3) 根据ve和vl的值求出ai的最早开始时间e(i)和最迟开始时间l(i)。若l(i)=e(i)，则ai为关键活动。
因为计算各顶点的ve值是在拓扑排序的过程中进行的，所以可通过对拓扑排序算法进行一些修正来实现求关键路径的算法。
第四章 查找与排序技术
4.1 基本的查找技术查找：查找是在一个给定的数据结构中，根据给定的条件查找满足条件的结点。
不同的数据结构采用不同的查找方法。
查找的效率直接影响数据处理的效率。
查找的结果：
成功：找到满足条件的结点失败：找不到满足条件的结点。
4.1.1 顺序查找（线性查找）
查找过程：
对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。
· 可以采用从前向后查，也可采用从后向前查的方法。
· 在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。
· 在下面两种情况下只能采取顺序查找：
a,线性表为无序表（元素排列是无序的）；
b,即使是有序线性表，但采用的是链式存储结构。
1,顺序查找 (线性表在顺序存储结构下的顺序查找）
数据结构：
typedef struct{
int key;
float info;
}SSTable;
查找成功时的平均查找次数为：
ASL=(1+2+3+4+……+n)/n=(n+1)/2
查找不成功时的比较次数为,n+1
则顺序查找的平均查找长度为：
ASL==((n+1)/2+n+1)/2=(n+1)3/4
顺序查找的优点：算法简单，无需排序，采用顺序和链式存储均可。
缺点：平均查找长度较大。
2,线性表在链式存储结构下的顺序查找
struct node
{ int data;
struct node *next;
};
int searlb(struct node *h,int x)
{
struct node *m;
m=h;
while (m->next!=NULL && m->data!=x) m=m->next;
return(m);
}
4.1.2 折半查找（二分法查找）
思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。
前提：必须在具有顺序存储结构的有序表中进行。
分三种情况：
1）若中间项的值等于x,则说明已查到。
2）若x小于中间项的值，则在线性表的前半部分查找；
3）若x大于中间项的值，则在线性表的后半部分查找。
特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。
折半查找的c语言算法程序：
int Search_Bin( SSTable ST[ ],int n,int key)
{int low,high,mid;
low=1; high=n;
while(low<=high)
{ mid=(low+high)/2;
if(ST[mid].key= = key) return (mid); /*查找成功*/
else if( key< ST[mid].key) high=mid-1; /*在前半区间继续查找*/
else low=mid+1; /*在后半区间继续查找*/
}
return (0); /*查找不成功*/
}
4.1.3分块查找（索引顺序查找）
是顺序查找的一种改进方法，就是把被查找的表分成若干块，每块中记录的存放顺序是无序的，但块与块之间必须按关键字有序。即第一块中任一记录的关键字都小于第二块中任一记录的关键字，而第二块中任一记录的关键字都小于第三块中任一记录的关键字，依此类推。
该法要为被查找的表建立一个索引表，索引表中的一项对应于表中的一块，索引表中含有这一块中的最大关键字和指向块内第一个记录位置的指针，索引表中各项关键字有序。
4.2 利用二叉排序树进行查找
（2） 在指针t 所指向的二叉排序树中查找关键字值为K的结点(找8)
#define M 100
typedef struct node{
int key;
struct node (L,(R;}JD
JD ( pxscz(JD (t,int K)
{JD (p;
if(t!=NULL)
{p=t;
while(p!=NULL)
{ printf(“key= %d\n”,p->key);
if(p->key==k) return (p);
else if(p->key>k) p=p->L;
else p=p->R;} }
return(NULL); }
4.3 哈希表技术
4.3.1,基本概念——哈希函数，冲突主要目标：提高查找效率—缩短查表和填表的时间。
基本思想：对被查找元素的关键字做某种运算后直接确定所要查找元素在表中的位置。
哈希函数：根据关键字直接计算出元素所在位置的函数。
哈希表技术的关键——处理好表中元素的冲突问题主要需要解决两方面的问题：
构造好的哈希函数，使冲突的现象尽可能少
Hash码均匀性好
Hash码的计算要尽量简单设计有效的解决冲突的方法
4.3.2 构造哈希函数的方法
（1） 直接定址法—取关键字或关键字的某个线性函数值为散列地址，
即 H（K）=K 或 H（K）=A*K+B；（其中A、B为常数）
例：某公司一险种投保费交纳表（20年），
将年份作关键字，哈希函数取关键字本身，若查找第3年应交纳的保费，只要查找表的第3项即可。
（2）平方取中法——取关键字平方后的中间几位为哈希函数。
如：K=308，K2=94864，H（K）=486
（3） 除后余数法——取关键字被不大于散列表表长m的数p除后所得的余数为哈希函数。 即
H（K）=K MOD p （p(m）
例：设Hash函数 H(k)=k MOD 11
求,60(5)、17(6)、29(7)、38(5)在散列表中的位置。
作业1
在地址空间0—16的散列区中，对以下关键字序列构造两个哈希表：
（Jan-9,Feb-5,Mar-12,Apr-0,May-,June,July,Aug,Sep-18,Oct-14,Nov-13,Dec-3)
用线性开放定址法处理冲突；
用链地址法处理。
并分别求这两个哈希表在等概率情况下查找成功的平均查找长度。
设哈希函数为H（x）=int（i/2）,其中i为关键字中第一个字母在字母表中的序号。 字母序号从1开始,31/12,18/12
4.4 基本排序
4.4.1 概 述
1、排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。
2、排序过程的组成步骤：
首先比较两个关键字的大小；
然后将记录从一个位置移动到另一个位置。
3、用于内存文件的排序
4.4.2 插入排序
插入排序基本思想：
每步将一个待排序的记录按其关键字大小插入到前面已排序表中的适当位置，直到全部插入完为止。
方法:Ki与Ki-1,K i-2,…K1依次比较,直到找到应插入的位置。
void insertSort(RedType L[ ],int n)
{ int i,j;
for(i=2; i<=n; i++)
if(L[i].key<L[i-1].key)
{ L[0]=L[i]; /* 作为监视哨*/
for( j=i-1; L[0].key<L[j].key; ( (j )
L[j+1]=L[j]; /* 记录后移*/
L[j+1]=L[0]; /* 插入 */
} }
4.4.3 选择排序
基本思想：
每一趟在n-i+1个记录中选取关键码最小的记录作为有序序列中第i个记录。
简单选择排序的算法如下：
void SelectSort( RedType L[ ],int n)
{ int i,j,k,t;
for (i=1,i<=n; ++i） /*选择第i小的元素，并交换到位*/
{ k=i；
for(j=i+1;j<=n; ++j)
if ( L[j].key<L[k].key) k=j; /*L[k] 中存放的是第I小的元素*/
if(k!=i) { t=L[i]; /*交换*/
L[i]=L[k]; L[k]=t ；}
} /*FOR*/
} /* SelectSort*/
4.4.4 交 换 排 序（互换排序）
互换排序：借助数据元素之间的相互交换进行的一种排序方法。
特点：交换。 有冒泡和快速排序两种。
思想：小的浮起，大的沉底。从左端开始比较。
第一趟：第1个与第2个比较，大则交换；第2个与第3个比较,
大则交换，……关键字最大的记录交换到最后一个位置上；
第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换到第n-1个位置上；
依次类推，则完成排序。
时间复杂度：
正序：时间复杂度为O(n) 逆序：时间复杂度为O(n2)
适合：数据较少的情况。排序n个记录的文件最多需要n-1趟冒泡排序。
Void bubsort(RedType L[ ],int n)
{ int i,x,j=1,k=1;
while (j<n)&&(k>0);
{ k=0;
for (i=1;i<=n-j; i++)
if (L[i+1].key<L[i].key)
{k++; x=L[i]; L[i]=L[i+1]; L[i+1]=x;}
j++;
} /*while*/
} /*Bobsort*/
2、快速排序 (对冒泡排序的改进）
思想：通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。
关键字通常取第一个记录的值为基准值。
做法：附设两个指针low和high,初值分别指向第一个记录和最后一个记录，设关键字为 key,首先从 high所指位置起向前搜索，找到第一个小于基准值的记录与基准记录交换，然后从low 所指位置起向后搜索，找到第一个大于基准值的记录与基准记录交换，重复这两步直至low=high为止。
时间复杂度：O(log2n)
4.4 小结
各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有：待排序的记录个数；记录本身的大小；记录的键值分布情况等。
若待排序的记录个数n较小时，可采用简单排序方法。
若n 较大时，应采用快速排序。
若待排序的记录已基本有序，可采用直接插入排序或 起泡排序。
数据处理：数据如何组织，以便提高处理速度，节省存贮空间——关键问题。
研究内容：
逻辑结构：数据元素间的关系。
物理结构/存贮结构：各数据元素在计算机中的存贮关系。
运算：对各种数据结构的操作。
2.1 数据结构的基本概念数据处理：对数据元素进行运算：包括插入、删除、查找、更新等，也包括分析。
建立数学模型固然好，但有时难以表示成模型，感兴趣的是数据元素之间的关系。为了提高处理效率，应如何组织他们，即如何表示数据元素。
书上通过实例说明数据采用不同表示方法对处理效率的影响。
数据结构是一门研究数据如何组织、存储和运算的一般方法的学科。
2.1.2 什么是数据结构数据：描述客观事务的数字符以及所有能输入计算机中并被程序识别和处理的符号的集合，计算机处理的对象。
数据元素(Data Element),数据的基本单位。
一个数据元素可由若干数据项(Data Item)组成。
数据项：数据的最小单位。
数据元素亦称结点或记录数据项亦称字段或域
数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。
数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。
数据的逻辑结构
数据结构可描述为 Group=（D，R）
D：有限个数据元素的集合；R有限个结点间关系的集合例题见书图形表示：见书
数据的存贮结构
2.1.4 线性数据结构与非线性数据结构
A,线性结构（一对一）
特性：1.有且只有一个根结点
2.每个结点最多一个前件，最多一个后件。（第一个数据元素无前件，最后一个无后件，其它 有且仅有一个前驱和一个后继。）
例：（A,B,C,·······,X,Y,Z）
例,学 生 成 绩 表
B．非线性结构:树形结构（一对多）
B．非线性结构:图形结构（多对多）
D={ 1,2,3,4}
R={(1,2),(1,3),(1,4),(2,3)
(3,4),(2,4) }
2、数据的存储结构
A,顺序存储顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。
顺序存储结构的三个弱点：
1.插入或删除操作时，需移动大量元素。
2.长度变化较大时，需按最大空间分配。
3.表的容量难以扩充。
B.链式存储
每个节点都由两部分组成：数据域和指针域。
数据域存放元素本身的数据，指针域存放指针。
数据元素之间逻辑上的联系由指针来体现。
链式存储结构特点：
1.比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成)。
2.逻辑上相邻的节点物理上不必相邻。
3.插入、删除灵活(不必移动节点，只要改变节点中的指针)。
2.2 线性表及其存贮结构线性表逻辑结构
n个数据元素的有限序列:(a1,a2,a3,…an)
n为线性表的长度(n≥0)，n=0的表称为空表特性：
数据元素呈线性关系.
所有数据元素ai在同一个线性表中须是相同的数据类型线性表的基本运算：
(1)插入：在两个确定的元素之间插入一个新的元素；
(2)删除：删除线性表中某个元素；
(3)修改：按某种要求查找元素，需要时，还可找到元素进行值的更新；
1.顺序存储结构及插入删除运算
.线性表的顺序存储结构,可用C语言中的一维数组来描述.
#define LISTINITSIZE 100 //线性表存储空间的初始分配量
typedef struct{
ElemType *elem；//数组指针表示存储空间基址
int length； //当前长度
int listsize //当前分配的存储容量（以sizeof（ElemType）为单位）
}Sqlist
Status ListInsert_sq（Sqlist (V，int i,ElemType x）
{
//在线性表V中第i个元素之前插入x,i 的合法值为 1( i(V.Length+1
if（i<1‖i>V.length+1）return ERROR; //i值不合法
if(V.length>V.listsize) return OVERFLOW; //无存储空间
q=(V.elem[i-1]; //下行注：插入位置后的元素依次右移
for(p=(V.elem[V.length-1]; p>=q; ( (p)
((p+1)= (p;
(q=x; // 插入x
++V.length; //表长加1
return OK;
}
Status ListDelete_sq（Sqlist (V，int i,ElemType x）{
if（i<1‖i>V.length）return ERROR;
P=(V.elem[i-1];
x =(P;
q= V.elem+ V.length(1 ;
for(++p;p<=q;++p) *(p(1)=*p
( (V.length;
return OK;
}
2.链式存储结构及插入删除运算特点：用一组任意的存储单元(可以是连续的,也可以是不连续的)存放线性表的数据元素。
上图为(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG)
线性表的线性链表存储结构，存储从头指针开始进行。
（1）线性表的单链式存储结构线性表的链式存储结构可用C语言中的“结构指针”来描述
Typedef struct Lnode
{
Elem Type data；
struct Lnode *next；
} Lnode，*linklist；
单链表的插入运算
ListInsert_L(LinkList &L,int i,ElemType x){
p=L; j=0;
while( p&&j<i-1)
{p=p->next; ++j;}
if( ! p (( j>i-1) return ERROR;
s=(struct LNode *)malloc(sizeof(struct LNode));
s->data=x; s->next=p->next; p->next=s;
return OK;
}
单链表的删除运算
ListDelete_L(LinkList &L，int i,ElemType x){
p=L; j=0;
while( p->next && j<i-1)
{ p=p->next; ++j; }
if( ! (p->next) (( j>i-1) return ERROR;
q=p->next ; p->next=q->next; free(q);
return OK;
}
（2） 循环链表 P64
将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。
（3） 双向链表 P55
在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。—插入和删除作业2,对以下单链表分别执行下列各程序段,并画出结果示意图.
(1) L=P->link;
(2) R->data=P->data;
(3) R->data=P->link->data;
(4) P->link->link->link->data=P->data;
(5) T=P;
while(T!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
(6) T=P;
while(T->link!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
(8) T=L;
T->link=P->link;
free(P);
(9) S->link=L;
习题：2。10 逆转线性单链表扫描单链表,将第一个节点的next设置为NULL,将第二个节点的next指向第一个节点,将第三个节点的next指向第二个节点,…
Invert(head)
Node *head;
{ node *p,*q,*r;
P=head; q=p—>next;
While (q!=NULL)
{ r=q—>next; q—>next=p; p=q; q=r; }
head—>next=NULL;
head=p;}
3.3 栈
1,栈 stack的定义栈是特殊的线性表，仅在表的一端进行插入或删除操作
特点：（1）对栈内数据的操作总在栈顶进行
（2）数据进栈称为“压入”push
（3）数据出栈称为“弹出”pop
（4）遵循“后进先出”的原则LIFO
例题：输入顺序A,B,C，输出顺序有几种？
ABC,ACB,BAC,BCA,CBA,不可能产生CAB
2.栈的顺序存储结构及运算用数组实现栈,a[0]为栈底，top为栈顶
（1）定义
typedef struct stack_type{
elemtype data[MAXNUM];
int top;
}stack_type;
（2）进栈 push
当新元素进栈时，栈顶上移，新元素放在栈顶。
stack.top = stack.top + 1; stack.data[stack.top] = new_one;
（3）出栈 pop,从栈顶移出一个数据。
栈顶元素拷贝出栈，栈顶下移
elemptype pop(stack_type *stack)
{ elemtype out;
if(stack->top < 0) error(3);
else{
out = stack->data[stack->top];
stack->top = stack->top -1;
}
return out; }
（4）栈空判断
stack.top = = 0 (stack.top < 0)
栈满判断：stack.top >= MAXNUM - 1;
（5）置栈空
stack.top = -1;
（6）栈的应用例 程序的嵌套，中断的嵌套见书P35
3.栈的链式存储结构及运算用链表实现栈
（1）定义
typedef struct lstack_type{
node_type * top;
int length;
}lstack_type;
（2）压入push
void push(stack,new_node){
new_node->next = stack->top;
stack->top = new_node;
stack->length ++;}
（3）弹出pop
node_type * pop(stack){
node_type* out;
out = stack->top;
stack->top = stack->top->next;
stack->length --;
return out;}
（4）栈空判断
stack.top == NULL;
（5）置栈空能否简单的使用 stack.top = NULL?
如果栈中还有链点，必须逐个将链点占用的空间释放
1、逐个将链点弹出
2、释放链点空间
void clean(stack){
node_type * temp;
while( ! empty(stack)){
temp = pop(stack);
free(temp); }
}
3.4 队列
1.队列定义类似于排队机制的结构,队列是特殊的线性表，
节点的插入仅限于在表尾进行，节点的删除仅限于在表头进行.
队列特点特点：
（1）对队列的操作在表的两端进行
（2）仅在队尾加入节点——入队enqueue
（3）仅在队首移出节点——出队dequeue
（4）遵循“先进先出”的原则——FIFO
队列的顺序存储结构及运算
2,用数组实现队列
（1）定义
typedef struct queue_type
{ elemtype data[MAXNUM];
int front;
int rear;
}queue_type;
（2）入队与出队用循环数组实现队列
void enqueue(queue,new_one)
{ if( (queue->rear + 1) % MAXNUM = = queue->front ) error(1);
else{ queue->data[queue->rear] = new_one;
queue->rear = (queue->rear +1) % MAXNUM;
}
}
elemtype dequeue(queue)
{ elemtype out；
if( queue->rear = = queue->front ) error(2);
else{ out ＝queue->data[queue->front];
queue->front = (queue->front +1) % MAXNUM;
}
return out；
}
思考：数组Q[0,4]
front=1,rear=3
front=3,rear=1
3．用链表实现队列
（一）定义
typedef struct lqueue_type
{ node_type * front;
node_type * rear;
int length;
}
（二） 入队新链点插入到队尾注意：队列为空时，rear和front都要指向新元素
new_node->next = NULL; list->rear ->next = new_node;
（三） 出队删除队首链点注意：当队列被删空时，rear指针要置空
temp = list->front; list->front = list->front->next;
习题:
例1 若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的一个出栈次序是（ d ）。
(a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3
例2 用一维数组设计栈，初态是栈空，top=0。现有输入序列是 a、b、c、d，经过 push、push、pop、push、pop、push操作后，输出序列是（ b,c ），栈顶指针是（ 2 ）
例 3 对于下面的程序调用过程，请问入栈序列是（1,2,3 ），出栈次序是（ 2,1,3）。
例4 设栈S为空，队Q的状态是abcd，其中a为队首元素，d为队尾元素，经过下面两个操作后，队Q的状态是（ c ）。
（1）删除队Q中的元素，将删除的元素插入栈S，直到队Q为空。
（2）依次将栈S中的元素插入队Q，直到栈S为空。
(a) abcd (b) acbd (c) dcba (d) bacd
例5 Josephus问题
设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，。。。，如此反复直到所有的人都出局为止。下面要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。请以n=9,s=3,m=4为例，模拟Josephus的求解过程求问题的解。
用顺序表结构和循环单链表结构求解Josephus问题的一般步骤为,
1）首先利用线性表的一些运算如创建空线性表、插入元素等构造Josephus表；
2）从Josephus表中的第s个结点开始寻找、输出和删除表中的第m个结点，然后再从该结点后的下一结点开始寻找、输出和删除表中的第m个结点，重复此过程,
3.5 二维数组（矩阵）
1.二维数组定义行关系，列关系均是线性关系
2,二维数组的顺序存放
（一）行优先存放：a11 a12..,a1na21 a22..,ai1 ai2,..ain..,am1 am2,.,amn
计算aij的存放位置：设每个元素占据S个存储单元
Loc(aij) = Loc(a11) + (( i - 1)*n + (j - 1))*S 计算前面有多少个元素
（二）列优先存放
a11 a21..,am1a12 a22..,am2a1j a2j,..aii..,a1n a2n,.,amn
Loc(aij) = Loc(a11) + (( j - 1)*m + (i - 1))*S
3,规则矩阵的压缩存储
(1)对称矩阵，三角矩阵的压缩对称矩阵：a[ i,j ] = a[ j,i ]
三角矩阵：上三角为0，或下三角为0
只存储上或下三角内的元素，节约近一半的存储空间
(1)对称矩阵，三角矩阵的压缩
i >= j 时，元素位于下三角
Loc(aij) = Loc(a11) + ( i ( i - 1) / 2 + ( j - 1))*S
i < j 时，元素位于上三角
Loc(aij) = Loc(a11) + ( j ( j - 1) / 2 + ( i - 1))*S
(2)稀疏矩阵矩阵中的非零元素很少，分布没有规律利用三元存储法 （行值，列值，元素值）
先形成三元矩阵再按照行优先顺序方式存储。
稀疏矩阵三元组定义
1)定义三元组元素
typedef struct tuple3tp{
int row_num; /*行号*/
int col_num; /*列号*/
elemtype value; /*元素值*/
} tuple3tp
2)定义三元组
typedef struct tuple3{
int row; /*行数*/
int col; /*列数*/
int num; /*非零元素个数*/
tuple3tp data[ MAXNUM];/* 三元组*/
}tuple3;
3.5 树与二叉树
3.5.1 树的基本概念
1,树的定义树是以分支关系定义的层次结构。
倒生树：树根在上，根上分茎，茎上分叶是族谱、社会组织机构一类实体的逻辑抽象对定义的理解
（1）有限集
（2）递归定义：树，根，子树
（3）有且仅有一个根结点不存在空树
（4）子树是互不相交的有限集
（5）树的层次性除根结点以外的结点有且仅有一个父结点树是一种数据结构
Tree = ( D,R )
D：元素的集合
R：元素关系的集合
（父、子关系 前驱、后继关系）
各结点没有或仅有一个父结点有且仅有一个根结点各结点可以有任意个子树
2,树的术语
1）结点
根结点,没有前驱，仅有后继
(茎)分支结点,有且仅有一个前驱，可以有多个后继叶结点,没有后继，仅有前驱
2）度与深度结点的度：该结点拥有的子树数目。
树的度：最大的结点度深度：最大的层次数
3）A节点的双亲,孩子,兄弟,祖先,子孙
4）路径（树枝，分支）
从K1出发自上而下到K2所经历的所有结点序列
5）有序树与无序树有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。
6）森林不相交的树的集合
3.5.2 二叉树
1、定义二叉树是结点的有限集，或为空，或由根的左、右子树组成，左右子树又分别是符合定义的二叉树。
对比树的定义：
空二叉树 树的定义中没有空树的概念不多于2个孩子 树的节点可以有任意个子树子树有左右之分 无序树可不区分左右树的其它定义适用于二叉树：根茎叶、度、路径
（2）二叉树的形态：5种
2,二叉树的性质
（1）在二叉树的第i层上最多有2i-1个结点第i层的结点数最多是第i-1层的两倍
（2）深度为k的二叉树最多有2k - 1个结点
（3）叶结点数比具有两个孩子的结点数多 1 个
（3）叶结点数比具有两个孩子的结点数多1个设n0为叶结点个数，
n1为具有一个孩子的分支结点个数，
n2为具有两个孩子的分支结点个数，
n为结点总个数结论,n0 = n2 + 1;
条件1,n = n0 + n1 + n2
条件2,n = 分支的个数 + 1
设为分支的个数为B
条件3,B = 2 n2 + n1
所以,2n2 + n1 + 1 = n0 + n1 + n2
（4）深度为K的满二叉树，结点个数为2k-1
满二叉树：所有的结点有两个孩子,所有的叶结点都位于同一层。
满二叉树：“装满”节点的二叉树半满二叉树：深度为K的二叉树，K－1层是满二叉树，K层节点个数不足2K－1个
（5）具有n个节点的完全二叉树，深度为 [log2n]+1
完全二叉树：特殊的半满二叉树，最后一层节点从左至右依次排列，没有间断。
如果对节点数为n的完全二叉树自上而下，从左至右依次编号，则节点i的父结点为[ i / 2 ]
若2i≤n，则i的左后继是2i；若2i>n,则i无左后继若2i＋1≤n，则i的右后继是2i＋1；若2i>n,则i无右后继关于完全二叉树的其他描述形式如果对满二叉树的节点从上至下，从左至右连续编号，具有n个节点的完全二叉树各节点与同样深度的满二叉树的前n个节点一一对应叶节点仅位于下两层，对任一节点，若其右子树的深度为1，则其左子树的深度不小于1
3.5.4 二叉树存储
1,顺序存储二叉树将完全二叉树从上到下，从左到右编号后，结点号码可作为数组的下标，从而将完全二叉树顺序存储下来。当给出任意结点i，我们可以知道它的父结点为[ i/2 ]，两个孩子分别为2i和2i＋1。
一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来。以维持结点编号之间的父子换算关系如此存放，将浪费较多空间
2,用链表实现二叉树二叉树链点的定义
typedef struct tnode_type{
elemtype data;
struct tnode_type *Lchild;
struct tnode_type *Rchild;
}tnode_type;
二叉树的定义
typedef struct tree_type{
tnode_type *root;
int num;
}tree_type;
每个结点由数据域、左指针域和右指针域组成。
3.5.5 二叉树的遍历遍历：指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。
作用：查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。
特点:
以根被访问顺序来划分不同的遍历方法在子树的访问顺序中始终以左子树优先
1）先根遍历（先序遍历）
2）中根遍历（中序遍历）
3）后根遍历（后序遍历）
中根遍历算法遍历过程：从根开始
1、找到B，但不访问B
2、根据B找到A，访问A
3、再回到B、访问B
4、根据B找到C，访问C
方法一、利用栈来实现回朔
1、树（子树）根入栈，不访问
2、左子树入栈，左子树的各子树根依次入栈即反复进行步骤1
3、当左子树为空时，出栈，访问根结点
4、根节点右子树入栈（新树入栈，到步骤1去遍历右子树）
5、当右子树为空时，出栈，访问（祖先）爷结点，将爷结点的右子树入栈
（新树入栈，回到步骤1)
总结：树入栈后一直朝左走（一路进栈），走不动时出栈并访问节点。同时将该节点右子树入栈。如果其右子树为空，就再出栈一个节点，访问，出栈节点右子树入栈
方法二：利用递归调用来实现回溯
void inorder( root )
{ if( root->Lchild != NULL) inorder (root->Lchild);
process(root);
if( root->Rchild != NULL) inorder(root->Rchild);
}
对比递归与非递归算法递归算法更简洁，更多依靠系统提供的“用户程序调用栈”，该栈的使用对用户是不可见的非递归算法在算法中直接掌握栈结构的调用二叉树的深度决定了递归调用的深度，决定了栈的长度。
当二叉树的深度较深时，系统提供的“用户程序调用栈”可能出现溢出，这时需要算法自行掌握栈的使用。
例：二叉排序树建立二叉树时，将关键值小于根结点的结点放在左子树，关键值大于根结点的的结点放在右子树，就可以形成一颗二叉排序树如学生成绩分别为71、65、40、88、67、90、60、70、77……，以下方式建立二叉排序树
（中序遍历二叉排序树，获得从低到高的排序结果！）
例:已知前序遍历：ABCDEFG 中序遍历：CBDAFEG
写出该二叉树的后序遍历,C D B F G E A
分析：前序遍历中的第一个元素必为二叉树的根结点。
中序遍历中的根结点恰为左、右子树的分界点。
例:已知后序遍历：CDBFGEA 中序遍历：CBDAFEG
写出该二叉树的前序遍历
分析：后序遍历中的最后一个元素必为二叉树的根结点。
中序遍历中的根结点恰为左、右子树的分界点。
3.5.6 树和森林转换为二叉树
（1）树转换为二叉树 (特点：转换后的二叉树，根结点没有右子树)
方法：·对每个孩子进行从左到右的排序；
在兄弟之间加一条连线；
对每个结点，除了左孩子外，去除其与其余孩子之间的联系；
以根结点为轴心，将整个树顺时针转45度。
(2) 森林与二叉树的转换方法：
· 将各棵树分别转成二叉树；
· 把每棵树的根结点用线连起来；
· 以第一棵树的根结点作为二叉树的根结点，按顺时针方向旋转。
3.5.7 二叉树的应用例：建立二叉排序树，进行排序和提高查询算法效率问题分析输入：一组无序元素输出：二叉排序树核心算法分析分析从假设二叉排序树已部分建立，现输入一个新元素开始核心算法分析
1、新元素与树根结点比较。
2、如果比根小，则取根的左子树，回到1；如果根无左子树，则将新结点插入在根结点左孩子处
3、如果比根大，取根的右子树，回到1；如果根无右子树，则将新结点插入在根结点右孩子处
例：哈夫曼树 最优二叉树 最小费用树什么是哈夫曼树、怎样建立、有什么用?
哈夫曼树是最优二叉树最优？路径带权总长最小路径？从树根到节点经历的分支序列，路径长度是分支数目总长？从根到所有节点的路径长度之和带权？（仅）叶节点带有权值带权路径长度：路径长度×权值树的带权路径长度：所有带权路径长度之和
带权路径长：5×2＋7×2＋2×2＋4×2＝36
5×2＋7×3＋4×3＋2×1＝46
2×3＋4×3＋5×2＋7×1＝35
哈夫曼树的建立
哈夫曼树的应用：利用哈夫曼树构造通讯中电文编码
例：要传输的电文是{CAS；CAT；SAT；AT}
3.6 图
图的邻接矩阵实现
typedef struct graph_m{
elemtype node[MAXNUM]; 顶点集合
int arcs[MAXNUM][MAXNUM]; 边的邻接矩阵
}graph_m;
图的邻接表存储法的特点优点：节省存储空间，边的插入和删除操作比较简便缺点：结构复杂，具有两种不同的基本组成单元
图的遍历 深优
1,深度优先遍历
（1）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。
（2）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。
（3）对于前两个步骤是递归的
深度优先遍历的特点
“深度”：总是访问顶点的一个相邻顶点，好像是沿着图中的一条路径走到“底”，然后后退一点，再选一条路。如此“进进退退”，直到所有顶点都被访问对于连通图，如果第一个被访问的顶点的所有相邻顶点都被访问了，意味着图中所有顶点都被访问了。
即栈空时用递归调用实现深度优先遍历算法
void dfs （g，v）
{ visit（v）；visited[ v ] = 1; 1 访问顶点v
p = g[v]->next_adj 2取得顶点的一个未被访问过的顶点w；
while(p != NULL){
w = p->node_index;
if(visited[w] == 0)
3 dfs（g，w）； 回到2；
p = p->next_adj; 4重复2，3直到该顶点所有的相邻顶点都被访问过；
广度优先遍历的特点
“广度”：总是在访问了一个顶点后，依次访问它的所有相邻顶点。然后再从它的第一个相邻顶点开始，访问其所有的相邻顶点。如此逐个顶点地逐步扩散，直到所有的顶点都被访问。
广度优先遍历操作具有队列操作的特点，当从队列中取出最后一个顶点，发现该顶点的所有相邻顶点都被访问过时，意味着图中所有的顶点都已被访问过
4,拓 扑 排 序按一定顺序进行的活动，可以使用顶点表示活动、顶点之间的有向边表示活动间的先后关系的有向图来表示，这种有向图称为顶点表示活动网络(Activity On Vertex network，简称AOV网)。
AOV网中的有向边表示了活动之间的制约关系。
将AOV网中的所有顶点排列成一个线性序列vi1,vi2,…,vin，并且这个序列同时满足关系：若在AOV网中从顶点vi到顶点vj存在一条路径，则在线性序列中vi必在vj之前，我们就称这个线性序列为拓扑序列。把对AOV网构造拓扑序列的操作称为拓扑排序。
在实际的意义上，AOV网中存在的有向环就意味着某些活动是以自己为先决条件，这显然是荒谬的。例如对于程序的数据流图而言，AOV网中存在环就意味着程序存在一个死循环。
任何一个无环的AOV网中的所有顶点都可排列在一个拓扑序列里，拓扑排序的基本操作如下：
(1) 从网中选择一个入度为0的顶点并且输出它。
(2) 从网中删除此顶点及所有由它发出的边。
(3) 重复上述两步，直到网中再没有入度为0的顶点为止。
以上的操作会产生两种结果：
一种是网中的全部顶点都被输出，整个拓扑排序完成；
另一种是网中顶点未被全部输出，剩余的顶点的入度均不为0，则说明网中存在有向环。
用以上操得到了一种拓扑序列：
C1,C2,C3,C4,C5,C7,C9,C10,C12,C11,C6,C8。
拓扑序列可以是 多 种
5,关键路径 AOE网络(Activity On Edge network)：
有向边：表示一个子工程（活动）
边上的权值：表示一个活动持续的时间顶点：表示事件，它表示了一种状态，即它的入边所表示的活动均已完成，它的出边所表示的活动可以开始。这种带权的有向网络称为 AOE网络(Activity On Edge network)，即边表示活动网络。
关键路径：
从源点到汇点的具有最大路径长度的路径。
关键活动：
关键路径上的各个活动。
明确了哪些活动是关键活动就可以设法提高关键活动的功效，以便缩短整个工期。
按(1)式和(2)式，可计算出图该AOE网各个事件的最早发生时间和最迟发生时间：
ve(1)=0
ve(2)=max{ve(1)+dur(<1,2>)}=max{0+3}=3
ve(3)=max{ve(1)+dur(<1,3>)}=max{0+2}=2
ve(4)=maw{ve(2)+dur(<2,4>),ve(3)+dur(<3,4>)}=max{3+4,2+3}=7
ve(5)=max{ve(4)+dur(<4,5>),ve(2)+dur(<2,5>)}=max{7+4,3+8}=11
ve(6)=max{ve(3)+dur(<3,6>),ve(4)+dur(<4,6>)}=max{2+7,7+2}=9
ve(7)=max{ve(5)+dur(<5,7>),ve(6)+dur(<6,7>)}=max{11+9,9+6}=20
vl(7)=ve(7)=20
vl(6)=min{vl(7)－dur(<6,7>)}=min{20－6}=14
vl(5)=min{vl(7)－dur(<5,7>)}=min{20－9}=11
vl(4)=min{vl(5)－dur(<4,5>),vl(6)－dur(<4,6>)}=min{11－4,11－2}=7
vl(3)=min{vl(4)－dur(<3,4>),vl(6)－dur(<3,6>)}=min{7－3,14－7}=4
vl(2)=min{vl(4)－dur(<2,4>),vl(5)－dur(<2,5>)}=min{7－4,11－8}=3
vl(1)=min{vl(2)－dur(<1,2>),vl(3)－dur(<1,3>)}=min{3－3,4－2}=0
关键活动算法主要由以下步骤组成：
(1) 对AOE网进行拓扑排序，同时按拓扑排序顺序求出各顶点事件的最早发生时间ve，若网中有回路，则算法终止，否则执行(2)。
(2) 按拓扑序列的逆序求出各顶点事件的最迟发生时间vl。
(3) 根据ve和vl的值求出ai的最早开始时间e(i)和最迟开始时间l(i)。若l(i)=e(i)，则ai为关键活动。
因为计算各顶点的ve值是在拓扑排序的过程中进行的，所以可通过对拓扑排序算法进行一些修正来实现求关键路径的算法。
第四章 查找与排序技术
4.1 基本的查找技术查找：查找是在一个给定的数据结构中，根据给定的条件查找满足条件的结点。
不同的数据结构采用不同的查找方法。
查找的效率直接影响数据处理的效率。
查找的结果：
成功：找到满足条件的结点失败：找不到满足条件的结点。
4.1.1 顺序查找（线性查找）
查找过程：
对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。
· 可以采用从前向后查，也可采用从后向前查的方法。
· 在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。
· 在下面两种情况下只能采取顺序查找：
a,线性表为无序表（元素排列是无序的）；
b,即使是有序线性表，但采用的是链式存储结构。
1,顺序查找 (线性表在顺序存储结构下的顺序查找）
数据结构：
typedef struct{
int key;
float info;
}SSTable;
查找成功时的平均查找次数为：
ASL=(1+2+3+4+……+n)/n=(n+1)/2
查找不成功时的比较次数为,n+1
则顺序查找的平均查找长度为：
ASL==((n+1)/2+n+1)/2=(n+1)3/4
顺序查找的优点：算法简单，无需排序，采用顺序和链式存储均可。
缺点：平均查找长度较大。
2,线性表在链式存储结构下的顺序查找
struct node
{ int data;
struct node *next;
};
int searlb(struct node *h,int x)
{
struct node *m;
m=h;
while (m->next!=NULL && m->data!=x) m=m->next;
return(m);
}
4.1.2 折半查找（二分法查找）
思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。
前提：必须在具有顺序存储结构的有序表中进行。
分三种情况：
1）若中间项的值等于x,则说明已查到。
2）若x小于中间项的值，则在线性表的前半部分查找；
3）若x大于中间项的值，则在线性表的后半部分查找。
特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。
折半查找的c语言算法程序：
int Search_Bin( SSTable ST[ ],int n,int key)
{int low,high,mid;
low=1; high=n;
while(low<=high)
{ mid=(low+high)/2;
if(ST[mid].key= = key) return (mid); /*查找成功*/
else if( key< ST[mid].key) high=mid-1; /*在前半区间继续查找*/
else low=mid+1; /*在后半区间继续查找*/
}
return (0); /*查找不成功*/
}
4.1.3分块查找（索引顺序查找）
是顺序查找的一种改进方法，就是把被查找的表分成若干块，每块中记录的存放顺序是无序的，但块与块之间必须按关键字有序。即第一块中任一记录的关键字都小于第二块中任一记录的关键字，而第二块中任一记录的关键字都小于第三块中任一记录的关键字，依此类推。
该法要为被查找的表建立一个索引表，索引表中的一项对应于表中的一块，索引表中含有这一块中的最大关键字和指向块内第一个记录位置的指针，索引表中各项关键字有序。
4.2 利用二叉排序树进行查找
（2） 在指针t 所指向的二叉排序树中查找关键字值为K的结点(找8)
#define M 100
typedef struct node{
int key;
struct node (L,(R;}JD
JD ( pxscz(JD (t,int K)
{JD (p;
if(t!=NULL)
{p=t;
while(p!=NULL)
{ printf(“key= %d\n”,p->key);
if(p->key==k) return (p);
else if(p->key>k) p=p->L;
else p=p->R;} }
return(NULL); }
4.3 哈希表技术
4.3.1,基本概念——哈希函数，冲突主要目标：提高查找效率—缩短查表和填表的时间。
基本思想：对被查找元素的关键字做某种运算后直接确定所要查找元素在表中的位置。
哈希函数：根据关键字直接计算出元素所在位置的函数。
哈希表技术的关键——处理好表中元素的冲突问题主要需要解决两方面的问题：
构造好的哈希函数，使冲突的现象尽可能少
Hash码均匀性好
Hash码的计算要尽量简单设计有效的解决冲突的方法
4.3.2 构造哈希函数的方法
（1） 直接定址法—取关键字或关键字的某个线性函数值为散列地址，
即 H（K）=K 或 H（K）=A*K+B；（其中A、B为常数）
例：某公司一险种投保费交纳表（20年），
将年份作关键字，哈希函数取关键字本身，若查找第3年应交纳的保费，只要查找表的第3项即可。
（2）平方取中法——取关键字平方后的中间几位为哈希函数。
如：K=308，K2=94864，H（K）=486
（3） 除后余数法——取关键字被不大于散列表表长m的数p除后所得的余数为哈希函数。 即
H（K）=K MOD p （p(m）
例：设Hash函数 H(k)=k MOD 11
求,60(5)、17(6)、29(7)、38(5)在散列表中的位置。
作业1
在地址空间0—16的散列区中，对以下关键字序列构造两个哈希表：
（Jan-9,Feb-5,Mar-12,Apr-0,May-,June,July,Aug,Sep-18,Oct-14,Nov-13,Dec-3)
用线性开放定址法处理冲突；
用链地址法处理。
并分别求这两个哈希表在等概率情况下查找成功的平均查找长度。
设哈希函数为H（x）=int（i/2）,其中i为关键字中第一个字母在字母表中的序号。 字母序号从1开始,31/12,18/12
4.4 基本排序
4.4.1 概 述
1、排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。
2、排序过程的组成步骤：
首先比较两个关键字的大小；
然后将记录从一个位置移动到另一个位置。
3、用于内存文件的排序
4.4.2 插入排序
插入排序基本思想：
每步将一个待排序的记录按其关键字大小插入到前面已排序表中的适当位置，直到全部插入完为止。
方法:Ki与Ki-1,K i-2,…K1依次比较,直到找到应插入的位置。
void insertSort(RedType L[ ],int n)
{ int i,j;
for(i=2; i<=n; i++)
if(L[i].key<L[i-1].key)
{ L[0]=L[i]; /* 作为监视哨*/
for( j=i-1; L[0].key<L[j].key; ( (j )
L[j+1]=L[j]; /* 记录后移*/
L[j+1]=L[0]; /* 插入 */
} }
4.4.3 选择排序
基本思想：
每一趟在n-i+1个记录中选取关键码最小的记录作为有序序列中第i个记录。
简单选择排序的算法如下：
void SelectSort( RedType L[ ],int n)
{ int i,j,k,t;
for (i=1,i<=n; ++i） /*选择第i小的元素，并交换到位*/
{ k=i；
for(j=i+1;j<=n; ++j)
if ( L[j].key<L[k].key) k=j; /*L[k] 中存放的是第I小的元素*/
if(k!=i) { t=L[i]; /*交换*/
L[i]=L[k]; L[k]=t ；}
} /*FOR*/
} /* SelectSort*/
4.4.4 交 换 排 序（互换排序）
互换排序：借助数据元素之间的相互交换进行的一种排序方法。
特点：交换。 有冒泡和快速排序两种。
思想：小的浮起，大的沉底。从左端开始比较。
第一趟：第1个与第2个比较，大则交换；第2个与第3个比较,
大则交换，……关键字最大的记录交换到最后一个位置上；
第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换到第n-1个位置上；
依次类推，则完成排序。
时间复杂度：
正序：时间复杂度为O(n) 逆序：时间复杂度为O(n2)
适合：数据较少的情况。排序n个记录的文件最多需要n-1趟冒泡排序。
Void bubsort(RedType L[ ],int n)
{ int i,x,j=1,k=1;
while (j<n)&&(k>0);
{ k=0;
for (i=1;i<=n-j; i++)
if (L[i+1].key<L[i].key)
{k++; x=L[i]; L[i]=L[i+1]; L[i+1]=x;}
j++;
} /*while*/
} /*Bobsort*/
2、快速排序 (对冒泡排序的改进）
思想：通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。
关键字通常取第一个记录的值为基准值。
做法：附设两个指针low和high,初值分别指向第一个记录和最后一个记录，设关键字为 key,首先从 high所指位置起向前搜索，找到第一个小于基准值的记录与基准记录交换，然后从low 所指位置起向后搜索，找到第一个大于基准值的记录与基准记录交换，重复这两步直至low=high为止。
时间复杂度：O(log2n)
4.4 小结
各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有：待排序的记录个数；记录本身的大小；记录的键值分布情况等。
若待排序的记录个数n较小时，可采用简单排序方法。
若n 较大时，应采用快速排序。
若待排序的记录已基本有序，可采用直接插入排序或 起泡排序。
