当前位置：首页 > news >正文

26考研11408数据结构

news 2025/7/30 6:09:42

数据结构

1.绪论

1.1.1数据结构的基本概念

数据
数据元素：数据的基本单位，一个数据元素由多个数据项组成，数据项是组成数据元素不可分割的最小单位
数据对象：具有相同性质的数据元素的集合，是数据的一个子集
数据类型：是一个值的集合和定义在此集合上的一组操作的总称
1. 原子类型：值不可再分
2. 结构类型：值可以再分解为若干成分
3. 抽象数据类型（ADT）：一个数学模型及定义在该数学模型上的一组操作，通常包括数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据操作的集合
数据结构：相互之间寸止一种或多种特定关系的数据元素的集合，包括三方面：逻辑结构、存储结构、数据的运算

1.1.2数据结构三要素

逻辑结构

集合、线性结构、树形结构、图状结构、网状结构

存储结构

顺序存储：逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元之间的邻接关系来体现

优点：随机存取元素占用的存储空间最少

缺点：只能使用相邻的存储单元外部碎片多

链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来指示元素之间的逻辑关系

优点：不产生碎片

缺点：存储指针占用额外的存储空间只能顺序存取

索引存储：存储元素信息同时建立索引表，索引表中的每一项称为索引项，索引项的一般形式（关键字、地址）

有点：检索速度快

缺点：索引表占用额外存储空间增加和删除数据时也要修改索引表

散列存储：根据元素的关键字直接计算其存储地址（哈希存储）

优点：计算，增加、删除节点快

缺点：散列函数的性能造成哈希冲突，解决冲突造成时间和空间开销

1.2算法及其评价

1.2.1算法

五大特性

有穷性：算法必须在有限步之后结束，每一步在有限时间内完成
确定性：每条指令有明确的含义，相同的输入只能有相同的输出
可行性：算法描述操作都可以通过已实现的基本运算执行有限次实现
输入：零个或多个输入
输出：一个或多个输出

目标

确定性：正确的解决求解问题

可读性：便于理解

健壮性：对非法输入做出反应/处理，不会产生莫名其妙的输出

高效率与低存储量要求

1.2.2算法效率

时间复杂度

最坏时间复杂度（一般考虑最坏时间复杂度）

平均时间复杂度

最好时间复杂度

空间复杂度

2.线性表

2.1.1定义与基本操作

特点：

元素个数有限
元素具有逻辑上的顺序性，表中元素有其先后次序
元素都是数据元素，每个元素单个
元素数据类型相同，每个元素占用相同大小的存储空间
元素具有抽象性

2.1.2线性表的基本操作

2.2.1顺序表的定义

线性表的顺序存储也称顺序表，用一组地址连续的存储单元一次存储线性表中的数据元素，从而使逻辑上相邻的两个元素在物理位置上也相邻

特点：逻辑顺序与其存储的物理顺序相同

注意：线性表中的元素位序是从1开始的，而数组中的元素下标从0开始

优缺点

优点：

随机访问，可通过首地址和元素序号在O(1)时间复杂度内查找元素

存储密度高

缺点：

元素的插入和删除需要移动大量元素，插入平均移动n/2，删除平均移动(n-1)/2

需要连续的存储空间

静态分配

#define MaxSize 50
typedef struct{ElemType data{MaxSize};int length;
}SqList;

动态分配

#define InitSize 50
typedef struct{ElemType *data;int Maxsize,length;
}SeqList;  L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize)

2.2.2顺序表基本操作实现

初始化

//静态
void InitList(SqList &L){L.length = 0 ;
}
//动态
void InitList(SeqList &L){L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);L.length = 0 ;L.MaxSize = InitSize;
}

插入

在顺序表的第i个位置插入元素

判断i是否合法
将第i个元素及其后所有元素一次向后移动一个位置
插入新元素e
顺序表长度加1

bool ListInsert(SqList &L,int i,ElemType e){if(i < 1 || i > L.length+1)return false;if(L.length >= MaxSize)return false;for(int j = L.length;j>=i;j--)L.data[j] = L.data[j-1];L.data[i-1] = e;L.length++;return true;
}

最好情况：在表尾插入，O(1)
最坏情况：表首插入，O(n)
平均：O(n)

删除操作

删除表中第i个位置的元素，用引用变量e返回

判断i是否合法
将被删除元素赋值给e
将第i+1个元素及其后所有元素依次向前移动一个位置

bool ListDelete(SqList &L,int i, ElemType &e){if(i<1||i>L.length)return false;e=L.data[i-1];for(int j = i;j<L.length;j++){L.data[j-1] = L.data[j];}L.length--;return true;
}

最好情况：删除表尾元素，O(1)

最坏情况：删除表头元素，O(n)

平均：O(n)

顺序表的插入和删除操作时间耗费主要在元素移动上

按值查找

查找第一个元素值等于e的元素，并返回其位序

int LocateElem(SqList L,ElemType e){int i;for(int j = 0;j<L.length;j++){if(L.data[j]==e){return i+1;}return 0;}
}

最好：查找元素在表头，O(1)

最坏：查找元素在表尾，O(n)

平均：O(n)

2.3.1单链表的定义

线性表的链式存储也称单链表，通过任意一组存储单元来存储线性表中数据元素，对于每个链表节点，出存放其自身信息外，还需要存放一个指向其后继的指针

typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;

优点：不再需要大量连续存储单元

缺点：增加了指针域，资源占用多非随机存取，不能直接找到表中某个特定节点，查找节点需要从头遍历

通常使用一个头指针来标识一个单链表，指出链表的起始地址，头指针为NULL表示一个空表

另外，为了操作方便，也会在第一个数据节点之前附加一个头节点，数据域可以不设任何信息，也可以记录表长等信息

单链表带头节点时，头指针指向头节点，不带头结点时，头指针指向第一个数据节点

头节点与头指针的关系：不管带不带头节点，头指针始终指向链表的第一个节点，而头节点时带头结点的链表中的第一个节点，通常不保存信息

引入头节点的好处：

第一个数据节点的位置与被存放在头节点的指针域中，因此链表的第一个外置上的操作和在表其他位置上的操作一致，无须特殊处理
无论链表是否为空，头指针都是指向头节点的非空指针，因此空表和非空表的处理也统一

2.3.2单链表基本操作实现

单链表初始化

带头结点

bool InitList(LinkList &L){L = (LNode*)malloc(sizeof(LNode));L->next = NULL;return true
}

不带头节点

bool InitList(LinkList &L){L=NULL;return true;
}

求表长

从第一个节点开始依次访问每一个节点,计数值加1

//求表的长度
int Length(LinkList L){int len = 0;	//统计表长 LNode *p = L;while(p->next != NULL){p = p->next;len++;}return len;
}

O(n)

按序号查找节点

//按位查找，返回第i个元素（带头结点）
LNode * GetElem(LinkList L, int i){if(i<0)return NULL;LNode *p;	//指针p指向当前扫描到的结点 int j=0;	//当前p指向的是第几个结点 p = L;		//L指向头结点，头结点是第0个结点（不存数据） while(p!=NULL && j<i){	//循环找到第i个结点 p = p->next;j++;}return p;
}

O(n)

按值查找节点

//按值查找，找到数据域==e的结点
LNode *LocateElem(LinkList L, ElemType e){LNode *p = L->next;//从第1个结点开始查找数据域为e的结点while(p!=NULL && p->data!=e)p = p->next;return p;	//找到后返回该结点指针，否则返回NULL 
}

插入节点

需要先找到待插入位置的前驱，即第i-1个节点

注意顺序

//在第i个位置插入元素e（带头结点） 
bool ListInsert(LinkList &L,int i, ElemType e){if(i<1)return false;LNode *p;	//指针p指向当前扫描到的结点 int j=0;	//当前p指向的是第几个结点 p = L;		//L指向头结点，头结点是第0个结点（不存数据） while(p!=NULL && j<i-1){	//循环找到第 i-1 个结点 p=p->next;j++;}if(p==NULL)		//i值不合法 return false;LNode *s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;	//将结点s连到p之后 return true;	//插入成功 
}

O(n)

删除节点

检查合法性
找到第 i-1 个节点
再删除第 i 个节点

//删除指定结点p
bool DeleteNode (LNode *p){if(p==NULL)return false;LNode *q = p->next;		//令q指向*p的后继结点 p->data = p->next->data;//和后继结点交换数据域 p->next = q->next;		//将*q结点从链中“断开” free(q);				//释放后继结点的存储空间 return true;
}

O(n)

插入时，若链表不带头节点，需要判断插入位置是否为1，若是，需要修改头指针：若带头节点则不修改

删除时，若链表不带头节点，需要判断删除节点是否为第一个数据节点，若是，则需要修改头指针；若带头节点则不修改

头插法建立单链表（重点）

生成链表中节点的次序与输入数据的次序不一致

LinkList List_HeadInsert(LinkList &L){	//逆向建立单链表 LNode *s;int x;L = (LinkList)malloc(sizeof(LNode));//创建头结点 L->nest = NULL;						//初始为空链表 scanf("%d",&x);						//输入结点的值 while(x!=9999){						//输入9999表示结束 s=(LNode*)malloc(sizeof(LNode));//创建新结点 s->data = x;s->next = L->next;L->next = s;					//将新结点插入表中，L为头指针 scanf("%d",&x);}return L;
}

尾插法建立单链表（重点）

链表中节点的顺序与输入顺序一致

增加一个尾指针，指向链表尾部

LinkList List_TailInsert(LinkList &L){	//正向建立单链表 int x;								//设ElemType为整型 L = (LinkList)malloc(sizeof(LNode));//建立头结点 LNode *s, *r=L;						//r为表尾指针 scanf("%d",&x);						//输入结点的值 while(x!=9999){						//输入9999表示结束 s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r=s;							//r指向新的表尾结点 scanf("%d",&x);} r->next->NULL;						//尾结点指针置空 return L;
}

2.3.3双链表

单链表局限：只有一个指向其后继的指针，只能从前向后遍历，要访问某个节点的前驱，只能从头开始遍历

prior和next分别指向某节点的直接前驱和直接后继

typedef struct DNode{			//定义双链表结点类型ElemType data;				//数据域 struct DNode *prior,*next;	//前驱和后继指针 
}DNode, *DLinklist;				//初始化双链表(带头结点) 
bool InitDLinklist(DLinklist &L){L = (DNode *)malloc(sizeof(DNode));if(L == NULL)return false;L->prior = NULL;L->next = NULL;return true; 
} void testDLinkList(){//初始化双链表DLinklist L;InitDLinkList(L);...... 
}

双链表的插入和删除操作时间复杂度只有O(1)

插入

被插入节点先连后继再连前驱

//在p结点之后插入s结点
bool InsertNextDNode (DNode *p, DNode *s){if(p==NULL || s==NULL)	//非法参数 return false;s->next = p->next;if(p-next != NULL)p->next->prior=s;	//如果p结点后有后继节点 s->prior = p;p->next = s;return true; 
}

删除

//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){if(p == NULL)	return false;DNode *q = p->next;		//找到p的后继结点qif(q == NULL)	return false;	//p没有后继 p->next = q->next;if(q->next != NULL)q->next->prior = p;free(q);		//释放结点空间 return true; 
} void DestoryList(DLinklist &L){//循环释放各个数据节点while (L->next != NULL)DeleteNextDNode(L);free(L);	//释放头结点 L = NULL; 	//头指针指向NULL 
}

2.3.4循环链表

循环链表与单链表的区别：表中最后一个节点的指针不是指向NULL，而是指向头节点，从而整个链表形成一个环

单链表只能从头节点开始遍历，循环单链表可以从任意节点开始遍历

typedef	struct LNode{	//定义单链表结点类型 ElemType data;		//每个结点存放一个数据元素 struct LNode *next;	//指针指向下一个结点 
}LNode, *LinkList;//初始化一个循环单链表
bool InitList(LinkList &L){L = (LNode *)malloc(sizeof(LNode));	//分配一个头结点 if(L==NULL)			//内存不足，分配失败 return false;L->next = L;		//头结点next指向头结点 return true;
}//判断循环单链表是否为空
bool Empty(LinkList L){if(L->next == L)return true;elsereturn false;
} //判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode *p){if(p->next == L)return true;elsereturn false;
}

2.3.4循环双链表

 
typedef struct DNode{ElemType data;struct DNode *prior,*next;
}DNode,*DLinklist;//初始化空的循环双链表
bool InitDLinkList(DLinklist &L){L = (DNode *)malloc(sizeof(DNode));	//分配一个头结点 if(L==NULL)			//内存不足，分配失败 return false;L->prior = L;		//头结点的 prior 指向头结点 L->next = L;		//头结点的 next 指向头结点 return true;
} void testDLinkList(){//初始化循环双链表DLinklist L;InitDLinkList(L);......
}//判断循环双链表是否为空
bool Empty(DLinklist L){if(L->next == L)return true;elsereturn false;
} //判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L, DNode *p){if(p->next == L)return true;elsereturn false;
}

2.3.5静态链表

使用数组来描述链表的链式存储结构，节点也有数据域和指针域，但是指针是节点在数组中的相对地址（数组下标），也称游标，和顺序表一样，静态链表也需要预先分配一块连续的内存空间

#define MaxSize 10	//静态链表的最大长度 
struct Node{		//静态链表结构类型的定义 ElemType data;	//存储数据元素  int next;		//下一个元素的数组下标 
};
typeof struct Node SLinkList [MaxSize];

2.3.6顺序表和链表的比较（重点）

存取方式

顺序表既可以顺序存取，又可以随机存取，链表只能从表头开始依次顺序存取

逻辑结构和物理结构

采用顺序存储时，逻辑上相邻的元素，对应物理位置也相邻

采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应逻辑关系是通过指针链接实现的

查找、插入、删除

按值查找，顺序表无序时，时间复杂度均为O(n)，顺序表有序时，可采用折半查找，此时时间复杂度为O(longn)

按序号查找，顺序表支持随机访问，时间复杂度只有O(1)，而链表的时间复杂度为O(n)，

顺序表的插入和删除平均需要移动半个表长元素，链表的插入删除只需修改相关节点的指针域

空间分配

顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。此外，链表的每个结点都带有指针域，因此存储密度不够大。

3.栈、队列、数组

3.1.1栈的基本概念

栈是只允许在一端进行插入或删除操作的线性表

栈顶：线性表允许进行插入和删除操作的一端

栈底：固定的，不允许进行插入或删除操作的一端

空栈：不含任何元素的空表

后进先出 LIFO

基本操作

栈的数学性质：卡特兰数公式，当有n个不同的元素入栈时，出栈元素不同排列个数为
$\frac{1}{n+1}C_{2n}^n$

3.1.2栈的顺序存储结构

采用顺序存储的栈称为顺序栈，使用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时增加一个指示当前栈顶元素位置的指针

//初始化栈
void InitStack(SqStack &S){S.top = -1; 	//初始化栈顶指针 
} void testStack(){SqStack S;	//声明一个顺序栈（分配空间）InitStack(S);...... 
} //判断栈空
bool StackEmpty(SqStack S){if(S.top == -1)		//栈空return true;elsereturn false;	//不空 
}

顺序栈的入栈操作手数组上界的约束，入栈时可能会发生栈上溢

顺序栈基本操作

入栈

判断栈满
栈顶指针加1
元素入栈

//新元素入栈
bool Push(SqStack &S,ElemType x){if(S.top == MaxSize-1)	//栈满，报错return false;S.top = S.top+1;		//指针先+1 S.data[S.top] = x; 		//新元素入栈 return true; 
}

出栈

判断栈空
元素出栈
栈顶指针减1

//出栈操作
bool Pop(SqStack &S,ElemType &x){if(S.top == -1)		//栈空，报错return false;x = S.data[S.top];	//栈顶元素先出栈 S.top = S.top-1;	//指针再-1 return true;
}

读栈顶元素

//读栈顶元素操作 
bool Pop(SqStack &S,ElemType &x){if(S.top == -1)		//栈空，报错return false;x = S.data[S.top];	//x记录栈顶元素	return true;
}

共享栈

将两个栈底分别设置在共享空间的两端，两个栈顶向共享空间中间延伸

3.1.3栈的链式存储结构

采用链式存储结构的栈称为链栈，其优点是便于多个栈共享存储空间提高效率，且不存在栈上溢

typedef struct Linknode{ElemType data;			//数据域 struct Linknode *next;	//指针域 
}*LiStack;					//栈类型定义

3.2.1队列的定义

队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，在表的另一端进行删除

先进先出 FIFO

队头：只允许删除的一端，也称队首

队尾：允许插入的一端

空队列：不含任何元素的空表

基本操作

栈和队列都不可以直接读取中间元素

3.2.2队列的顺序存储结构

两个指针：队首指针front指向队首元素，队尾指针rear指向队尾元素的下一个位置

#define MaxSize 10	//定义队列中元素的最大个数
typedef struct{ElemType data[MaxSize];	//用静态数组存放队列元素int front,rear;			//队头指针和队尾指针 
}SqQueue;//初始化队列
void InitQueue(SqQueue &Q){//初始时 队头、队尾指针指向0Q.rear = Q.front = 0; 
} void testQueue(){//声明一个队列（顺序存储）SqQueue Q;InitQueue(Q);...... 
}//判断队列是否为空
bool QueueEmpty(SqQueue Q) {if(Q.rear == Q.front)	//队空条件return true;else return false; 
}

入队

判断队满
元素队尾入队
队尾指针加1

//入队操作
bool EnQueue(SqQueue &Q,ElemType x){if(队列已满)return false;	//队满则报错Q.data[Q.rear] = x;Q.rear = Q.rear+1;return true; 
}

出队

判断对空
队首元素出队
对数指针加1

循环队列（模运算）

把存储队列元素的表在逻辑上视为一个环，称为循环队列

初始时：Q.front == (Q.front + 1) %MaxSize

队首指针进1：Q.front = (Q.rear + 1)%MaxSize

队尾指针进1：Q.rear = (Q.rear + 1)%MaxSize

队列长度：(Q.rear + MaxSize - Q.front)%MaxSize

出入队时，指针都按顺时针方向进1

队空条件：Q.front == Q.rear

区分队满队空：

牺牲一个存储单元来区分队空和队满，入队时少用一个队列单元

约定——队首指针在队尾指针的下一个位置作为队满标志

队满条件：(Q.rear+1)%MaxSize == Q.front

队空条件：Q.front == Q.rear

队列中元素个数：(Q.rear - Q.front + MaxSize)%MaxSize
增设size数据成员，表示元素个数，若删除成功，size–，若插入成功，size++

队空：Q.size == 0

队满：Q.size == MaxSize

都会使Q.front == Q.rear
增设tag数据成员，以区分队满队空

删除成功 tag = 0 若Q.front == Q.rear ，则队空

插入成功 tag = 1 若Q.front == Q.rear ，则队满

//判断队列是否为空
bool QueueEmpty(SqQueue Q){if(Q.rear == Q.front)	//队空条件return true;elsereturn false; 
} //入队
bool EnQueue(SqQueue &Q,ElemType x){if((Q.rear+1)%MaxSize == Q.front)return false;			//队满则报错Q.data[Q.rear] = x;			//新元素插入队尾 Q.rear = (Q.rear+1)%MaxSize; //队尾指针+1取模return true; 
} //出队(删除一个队头元素，并用x返回) 
bool DeQueue(SqQueue &Q,ElemType &x){if(Q.rear == Q.front)return false;		//队空则报错 x = Q.data[Q.front];Q.front = (Q.front+1)%MaxSize;return true; 
} //获得队头元素的值，用x返回
bool GetHead(SqQueue Q,ElemType &x){if(Q.rear == Q.front)return false;	//队空则报错x = Q.data[Q.front]return true; 
}

3.2.3队列的链式存储结构

队列的链式表示称为链式队列，实际上是一个同时具有队首指针和队尾指针的单链表

typedef struct LinkNode {	//链式队列结点ElemType data;struct LinkNode *next; 
}LinkNode;typedef struct{				//链式队列 LinkNode *fron,*rear;	//队列的队头和队尾指针 
}LinkQueue;

初始化

//初始化队列（带头结点）
void InitQueue (LinkQueue &Q){//初始时 front、rear 都指向头结点Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));Q.front->next = NULL;
} 
//判断队列是否为空（带头结点）
bool IsEmpty(LinkQueue Q){if(Q.front == Q.rear)return true;elsereturn false;
} 
----------------------------------------
//初始化队列（不带头结点）
void InitQueue(LinkQueue &Q){//初始时 front、rear 都指向NULLQ.front= NULL;Q.rear = NULL; 
} 
//判断队列是否为空（不带头结点）
bool IsEmpty(LinkQueue Q){if(Q.front == NULL)return true;elsereturn false;
} void testLinkQueue(){LinkQueue Q;	//声明一个队列InitQueue(Q);	//初始化队列...... 
}

入队

//新元素入队（带头结点）
void EnQueue(LinkQueue &Q,ElemType x){LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));s->data = x;s->next = NULL;Q.rear->next = s;	//新结点插入到rear之后 Q.rear = s;			//修改表尾指针 
} 
------------------------------------------------------- 
//新元素入队（不带头结点）
void EnQueue(LinkQueue &Q,ElemType x){LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));s->data = x;s->next = NULL;if(Q.front == NULL){	//在空队列中插入第一个元素 Q.front= s;			//修改队头队尾指针 Q.reat= s;}else{Q.rear->next = s;	//新结点插入到 rear 之后 Q.rear = s; 		//修改rear指针 }
}

出队

//队头元素出队（带头结点）
bool DeQueue(LinkQueue  &Q,ElemType &x){if(Q.front == Q.rear)return false;	//空队LinkNode *p = Q.front->next;//p指针指向要删除的结点（队头元素出队）x = p->data;	//用变量x返回队头元素Q.front->next = p->next;	//修改头结点的next指针if(Q.rear == p)				//此次是最后一个结点出队 Q.rear = Q.front;		//修改 rear 指针 free(p);					//释放结点空间 return true;
}

3.2.4双端队列

两端都可以进行插入和删除的线性表，两端地位平等，左前右后

输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列

输入受限的双端队列：允许一端进行插入和删除，但在另一端只允许删除的双端队列

若限定从某个端点插入元素只能从该端点删除，则双端队列==两个栈底相连的栈

重要例题：各种双端队列序列输出序列

3.3.1栈在括号匹配中的应用(重点)

题目描述

bool bracketCheck(char str[],int length){SqStack S;InitStack(S);	//初始化一个栈for(int i=0; i<length; i++){if(str[i] == '(' || str[i] == '[' || str[i] == '{')Push(S,str[i]);		//扫描到左括号，压入栈 }else{if(StackEmpty(S))		//扫描到右括号，且当前栈空 return false; 		//扫描失败char topElem;Pop(S,topElem);			//栈顶元素出栈 if(str[i] == ')' && topElem != '(')return false;if(str[i] == ']' && topElem != '[')return false;if(str[i] == '}' && topElem != '{')return false;} return StackEmpty(S);		//检索完全部括号后，栈空说明匹配成功 
}

3.3.2栈在表达式求值中的应用

中缀表达式与前缀、后缀表达式有何不同：中缀表达式中括号是必须的

中缀表达式转后缀表达式

按照运算符的运算顺序队所有运算单位加括号
将运算符移至对应括号的后面，相当于左操作数右操作数运算符重新组合
去除所有括号

使用栈实现中缀表达式转后缀表达式：

遇到操作数，直接加入后缀表达式
遇到界限符，若为（则直接入栈，若为）则不入栈，且依次弹出栈中的运算符并加入后缀表达式，直到遇到（为止，并直接删除（
遇到运算符
1. 若其优先级高于栈顶运算符或遇到栈顶为（，则直接入栈
2. 若其优先级低于或等于栈顶运算符，则依次弹出栈中的运算符并加入后缀表达式，直到遇到一个优先级低于他的运算符或（栈空为止，之后将当前运算符入栈

栈的深度：栈中元素个数，通常是给出入栈和出栈序列，求最大深度（栈的容量应大于或等于最大深度）

后缀表达式求值

从左往右扫描表达式每一项，若是操作数，将其压入栈中

若是操作符，则从栈中退出两个操作数X、Y形成运算指令 X （运算符）Y，并将结果入栈

所有项都扫描之后，栈顶存放的就是最后的计算结果

3.3.3栈在递归中的应用

递归：若在一个函数、过程或数据结构的定义中有应用到了它自身

递归通常把一个大型的复杂问题转化为一个与原问题相似的规模较小的问题来求解

递归组成：

递归表达式（递归体）
边界条件（递归出口）

在递归调用的过程中，系统为每一层的返回点，局部遍历，传入实参等开辟了递归工作栈来进行数据存储，递归次数过多容易造成栈溢出

效率不高的原因——包含许多重复的过程

3.3.4队列在层次遍历中的应用

如果问题需要逐层或逐行处理，解决方法通常是在处理当前层或当前行之前就对下一层或下一行进行预处理

队列实现二叉树的层序遍历

描述:

根节点入队
若队空，则结束遍历，否则重复操作3
队列中的队首节点出队，并访问之，若其有左孩子，左孩子入队，若其有右孩子，右孩子入队，返回2

3.3.5队列在计算机系统中的应用

3.4.1数组的定义

数组是由n个相同类型的数据元素构成的有限序列，每个元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界

数组与线性表的关系：数组是线性表的推广，一位数组可视为一个线性表，二维数组可视为其元素是定长数组的线性表

数组一旦定义，其维数和维界就不再改变

3.4.2数组的存储结构

一个数组的所有元素在内存中占用一段连续的存储空间

多维数组映射：

按行优先：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素

按列存储

3.4.3特殊矩阵的压缩存储

压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配空间

特殊矩阵：具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律的矩阵

对称矩阵

三角矩阵

下三角矩阵

上三角矩阵

三对角矩阵

稀疏矩阵

十字链表存储稀疏矩阵

4.串

4.2.1简单的模式匹配算法

模式匹配：在主串中找到与模式串相同的子串，并返回其所在的位置，串采用定长顺序存储结构

//朴素模式匹配算法
int Index(SSring S,SString T){int i=1,j=1;while(i<=s.length && j<=T.length){if(S.ch[i] == S.ch[j]){++i; ++j;	//继续比较后续字符 }else{i=i-j+2;	//i=(i-(j-1))+1 j=1;	//指针后退重新开始匹配 } }if(j>T.length)return i-T.length;elsereturn 0; 
}

算法思想：从主串S的第一个字符起，与模式串T的第一个字符比较，若相等，则继续逐个比较后续字符，否则从主串的下一个字符起，再重新和模式串T的字符比较

设主串和模式串长度分别为n和m，则最多需要n-m+1趟匹配，每趟最多进行m次比较，最坏时间复杂度O(mn)

4.2.2KMP算法

kmp算法的PM表 next数组都是对模式串来说的

算法思想：若已匹配相等的前缀序列中有某个后缀正好是模式串的前缀，则可将模式串向右滑动到与这些相等字符对齐的位置，主串指针 i 无须回溯

kmp算法原理

前缀：除最后一个字符外，字符串中所有头部子串

后缀：除第一个字符外，字符串的所有尾部子串

部分匹配值：字符串的前缀和后缀的最长相等前后缀的长度

ababa：

主串 S=ababcabcacbab

模式串 T=abcac

PM表——对模式串求部分匹配值

利用PM表进行模式匹配

next数组手算方法

每趟匹配失败时，只有模式串指针j在变化，主串指针i不会回溯，为此可以定义一个next数组

next[j]的含义是每当模式串的第j个字符失配时，跳到next[j]的位置进行比较

next数组与PM表的关系

编号从1开始，PM表右移一位并整体加1

第一个元素右滑后的空缺用0来填充，因为若是第一个元素匹配失效，则需要将主串指针与模式串同步向右移动一位，从而不需要计算模式串指针移动位数
最后一个元素在右滑过程中溢出，因为原来的模式串中，最后一个元素的部分匹配值是下一个元素使用的，但已经没有下一个元素了，所以舍去
PM表右移一位并整体加1，编号从0开始，不加1，从1开始加1

4.2.3KMP算法的进一步优化

5.树与二叉树

5.1.1树的定义

树是n个节点的有限集，n=0时为空树

任何一颗非空树都需要满足：

有且只有一个特定的根节点
n>1时其余节点可以分为m个互不相交的有限集T1,T2…Tm，其中每个集合本身又是一棵树，并且称为根的子树

树的定义是 递归定义 的

树的特点：

树的根节点没有前驱，除根节点外的所有节点有且只有一个前驱
树中所有节点都可以有零个或多个后继

n个节点的树有n-1条边

5.1.2基本术语

祖先、子孙、双亲、孩子、兄弟、堂兄弟
层次、深度、高度
1. 节点的层次：从根节点开始为第一层，其孩子为第二层
2. 树的高度/深度：树中节点的最大层数
3. 节点的高度：以该节点为根的子树的高度
节点的度和树的度
1. 节点的度：一个节点孩子的个数
2. 树的度：树中节点的最大度数
分支节点和叶节点
1. 分支节点：度大于0的节点
2. 叶节点：度为0（没有孩子节点）的节点
有序树和无序树
1. 有序树：树中节点的各子树从左到右是有次序的，不能互换
2. 无序树：不满足以上条件
路径和路径长度
1. 路径：两个节点之间经过的节点序列
2. 路径长度：路径上所经过的边的个数
森林
1. m棵互不相交的树的集合

5.1.3树的性质

树的节点数n等于 = 节点的度数之和 + 1 = 边数 + 1

常用于求解树节点与度之间的关系

5.2.1二叉树的定义及其主要特性

每个节点至多只有两棵子树（二叉树不存在度大于二的节点），并且子树有左右之分，次序不能随意颠倒

二叉树与度为2的有序树的区别：

度为2的树至少有3个节点，而二叉树可以为空
度为2的有序树的孩子的左右次序是相对于另一个孩子而言的，若某个节点只有一个孩子，则这个孩子无须七分左右次序，而二叉树无论其孩子个数是否为2，均需确定其左右次序

特殊的二叉树

满二叉树

一棵树高为h，节点个数等于 2^h-1

每一层都含有最多的节点

叶节点只位于二叉树的最底层

分支节点度为2

若对按二叉树层序编号，对于一个编号为 i 的节点，若有双亲则其编号为 i/2 ，左孩子为 2i ，右孩子为 2i+1

完全二叉树

高为h的完全二叉树，当且仅当每个节点与高为h的满二叉树中的节点编号一一对应

完全二叉树 = 满二叉树去掉部分大编号节点

分支节点数 = 最大叶子节点数 / 2

性质

完全二叉树从上到下，从左到右编号有以下性质：

叶节点只能在最后两层上出现（相当于在相同高度的满二叉树的最底层，最右边减少一些连续的叶节点，当减少2个或以上的叶节点时，次底层出现叶节点）
若有度为1的节点，则至多有一个，且该节点只有左孩子没有右孩子（度为1的分支节点只可能是最后一个分支节点，编号为 n/2）
按层序编号后，一旦出现某节点为叶节点或只有做孩子的情况，则编号大于该节点的节点均为叶节点
若n为奇数，每个分支节点都有左右孩子，若n为偶数，则编号最大的分支节点只有左孩子没有右孩子，其余分支节点都有左右孩子
节点i所在的层次（深度）为 long2i + 1

二叉排序树

左子树上所有节点的关键字小于根节点的关键字，右子树上所有节点的关键字均大于根节点的关键字

左右子树仍为二叉排序树

平衡二叉树

树中任意一个节点的左子树和右子树的高度只差绝对值不超过1

正则二叉树

树中每个分支节点都有2个孩子

树只有度为0或2的节点

二叉树的性质

叶节点数等于度为2的节点数加1 n0 = n2 + 1
非空二叉树的第k层最多有 2^(k-1)个节点
高度为h的二叉树至多有 2^h -1个节点

5.2.2二叉树的存储结构

顺序存储结构

用一组连续的存储单元依次从上到下，从左到右存储完全二叉树上的节点元素

完全二叉树和满二叉树适用于顺序存储，因为树中的节点序号可以唯一的反映节点之间的逻辑关系

对于一般的二叉树，需要添加一些不存在的空节点，每个节点需要与完全二叉树上的节点对应

链式存储结构

顺序存储结构空间利用率低

//二叉树的结点（链式存储）
struct ElemType{int value;
};typedef struct BiTNode{ElemType data;		//数据域struct BiTNode *lchild,*rchild;	//左、右孩子指针 (sruct BiTNode *parent;)	//父结点指针 
}BiTNode,*BiTNode; //定义一棵空树
BiTree root = NULL;//插入根节点
root = (BiTree) malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;//插入新结点
BiTree *p = (BiTNode *) malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;	//作为根节点的左孩子

在含有n个节点的二叉链表中，含有n+1个空链域

5.3.1二叉树的遍历

先序遍历

中左右


//先序遍历
void PreOrder(BiTree T){if(T != NULL){visit(T);			//访问根节点PreOrder(T->lchild);//递归遍历左子树 PreOrder(T->rchild);//递归遍历右子树 }
}

中序遍历

左中右


//中序遍历
void InOrder(BiTree T) {if(T != NULL){InOrder(T->lchild);//递归遍历左子树 visit(T);			//访问根节点InOrder(T->rchild);//递归遍历右子树 }
}

后序遍历


//后序遍历 
void PostOrder(BiTree T){if(T != NULL){PostOrder(T->lchild);//递归遍历左子树 PostOrder(T->rchild);//递归遍历右子树visit(T);			//访问根节点}
}

层序遍历

引入一个队列
首先将根节点入队
若队列非空，从队首头节点出队，若其有左孩子，左孩子入队，若其有右孩子，右孩子入队

//层序遍历
void LevelOrder(BiTree T){LinkQueue Q;	InitQueue(Q); 			//初始化辅助队列 BiTree p;EnQueue(Q,T);			//将根节点入队while(!IsEmpty(Q)){		//队列不空则循环 DeQueue(Q,p); 		//对头结点出队visit(p);			//访问出队结点if(p->lchild!=NULL)EnQueue(Q,p->lchild);	//左孩子入队 if(p->rchild!=NULL)EnQueue(Q,p->rchild);	//右孩子入队 } 
} typedef struct BiTNode{ElemType data;	struct BiTNode *lchild,*rchild;	
}BiTNode,*BiTNode; //链式队列结点
typedef struct LinkNode{BiTNode * data;struct LinkNode *next;
}LinkNode;typedef struct{LinkNode *front,*rear;	//队头队尾 
}LinkQueue;

遍历序列构造二叉树

中序序列+其他三种序列中的任意一种 = 一颗二叉树

一、中序序列 + 前序序列构造二叉树

确定根节点
- 前序序列的第一个元素是整棵树的根节点。
- 例如，前序序列为ABDECF，中序序列为DBEAFC。那么A就是整棵树的根节点。
划分左右子树
- 在中序序列中找到根节点的位置，根节点左边的序列是左子树的中序序列，右边的序列是右子树的中序序列。
- 根节点A在中序序列DBEAFC中的位置是第4个。那么DBE就是左子树的中序序列，FC是右子树的中序序列。
- 同时，根据左子树和右子树的节点数量，可以确定前序序列中左子树和右子树对应的序列。左子树有3个节点（D、B、E），所以前序序列ABDECF中，ABDE是左子树的前序序列，CF是右子树的前序序列。
递归构造左右子树
- 对左子树的前序序列ABDE和中序序列DBE重复上述步骤，确定左子树的根节点B，划分左子树的左右子树，继续递归。
- 对右子树的前序序列CF和中序序列FC也重复上述步骤，确定右子树的根节点C，划分右子树的左右子树，继续递归。
- 递归的终止条件是序列为空，即没有子树可以划分。

二、中序序列 + 后序序列构造二叉树

确定根节点
- 后序序列的最后一个元素是整棵树的根节点。
- 例如，后序序列为DEBFCA，中序序列为DBEAFC。那么A就是整棵树的根节点。
划分左右子树
- 在中序序列中找到根节点的位置，根节点左边的序列是左子树的中序序列，右边的序列是右子树的中序序列。
- 根节点A在中序序列DBEAFC中的位置是第4个。那么DBE就是左子树的中序序列，FC是右子树的中序序列。
- 同时，根据左子树和右子树的节点数量，可以确定后序序列中左子树和右子树对应的序列。左子树有3个节点（D、B、E），所以后序序列DEBFCA中，DEB是左子树的后序序列，FC是右子树的后序序列。
递归构造左右子树
- 对左子树的后序序列DEB和中序序列DBE重复上述步骤，确定左子树的根节点B，划分左子树的左右子树，继续递归。
- 对右子树的后序序列FC和中序序列FC也重复上述步骤，确定右子树的根节点C，划分右子树的左右子树，继续递归。
- 递归的终止条件是序列为空，即没有子树可以划分。

三、中序序列 + 层序序列构造二叉树

确定根节点：
- 层序遍历的第一个节点是整棵树的根节点。
- 在上面的例子中，根节点是A。
划分左右子树：
- 在中序序列中找到根节点的位置，根节点左边的序列是左子树的中序序列，右边的序列是右子树的中序序列。
- 在上面的例子中，A在中序序列D B E A F C中的位置是第4个。那么D B E是左子树的中序序列，F C是右子树的中序序列。
确定左右子树的层序序列：
- 从层序序列中去掉根节点后，剩下的节点需要根据中序序列的划分来分配到左右子树。
- 在上面的例子中，去掉A后，层序序列剩下B C D E F。
- 左子树的中序序列是D B E，右子树的中序序列是F C。
- 我们可以假设左子树的层序序列是B D E，右子树的层序序列是C F（但这只是一个假设，实际上可能有多种分配方式）。
递归构造左右子树：
- 对左子树的层序序列B D E和中序序列D B E重复上述步骤。
- 对右子树的层序序列C F和中序序列F C重复上述步骤。

5.3.2线索二叉树

若无左子树，令lchild指向其前驱节点，若无右子树，rchild指向其后继节点

Ltag = 0 ：lchild指示节点左孩子
Ltag = 1 ：lchild指示节点的前驱
Rtag = 0 ：rchild指示节点的右孩子
Rtaag = 1 ：rchild指示节点的后继

//线索二叉树结点
typedef struct ThreadNode{ElemType data;struct ThreaDNode *lchild,*rchild;int ltag,rtag;	//左、右线索标志 //ltag == 1，表示lchild指向前驱；ltag == 0，表示lchild指向左孩子//rtag == 1，表示rchild指向前驱；rtag == 0，表示rchild指向右孩子
}ThreadNode,*ThreadTree;

中序线索二叉树构造

快慢指针：pre指示刚刚访问过的节点，p指示正在访问的节点，即pre指向p的前驱
检查p的左指针是否为空（p节点是否有左孩子），若为空就将它指向pre
检查pre的右指针是否为空（pre是否有右孩子），若为空就将它指向p

void InThread(ThreadTree &p, ThreadTree &pre) {if (p != NULL) {InThread(p->lchild, pre); // 递归，线索化左子树if (p->lchild == NULL) { // 当前结点的左子树为空p->lchild = pre; // 建立当前结点的前驱线索p->ltag = 1;}if (pre != NULL && pre->rchild == NULL) { // 前驱结点非空且其右子树为空pre->rchild = p; // 建立前驱结点的后继线索pre->rtag = 1;}pre = p; // 标记当前结点成为刚刚访问过的结点InThread(p->rchild, pre); // 递归，线索化右子树}
}void CreateInThread(ThreadTree T) {ThreadTree pre = NULL;if (T != NULL) { // 非空二叉树，线索化二叉树InThread(T, pre); // 线索化二叉树pre->rchild = NULL; // 处理遍历的最后一个结点pre->rtag = 1;}
}

中序线索二叉树的遍历

思路：线索二叉树包含节点的前驱后继信息，遍历时需要先找到第一个节点（最左下节点），然后依次找后继节点：若右标志（Rtag = 1）为线索，则其指示后继，否则指示右子树，继续找右子树最左下节点

//中序线索二叉树找中序后继//找到以P为根的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){//循环找到最左下结点（不一定是叶结点）while(p->ltag == 0)p=p->lchild;return p; 
} 
//在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){//右子树中最左下结点if(p->rtag == 0)return Firstnode(p->rchild);else return p->rchild;	//rtag==1直接返回后继线索 
} 
//对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
void Inorder(ThreadNode *T){for(ThreadNode *p=Firstnode(T); p!=NULL; p=Nextnode(p))visit(p);
}

线序线索二叉树和后序线索二叉树

线序线索二叉树找后继：若有左孩子，左孩子是后继，若无左孩子有右孩子，右孩子是后继，若为叶节点，右链域为后继

后序二叉树找后继：

若节点x是二叉树的根，则其后继为空
若节点x是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲
若节点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历的第一个节点

5.4.1树的存储结构（注意与二叉树的区分）

树会有多个孩子节点

双亲表示法

采用一组连续的存储空间存储每个节点，同时增设一组伪指针，指示其双亲节点在数组中的位置

//双亲表示法（顺序存储）
#define MAX_TREE_SIZE 100		//树中最多结点数
typedef struct{					//树中的结点定义ElemType data;				//数据元素 int parent;					//双亲位置域 
}PTNode;
typedef struct{					//树的类型定义 PTNode nodes[MAX_TREE_SIZE];//双亲表示 int n;						//结点数 
}PTree;

利用了每个节点只有唯一双亲的特性，很快就能找到每个节点的双亲节点，但求孩子节点时需要遍历整个数组

孩子表示法

将每个节点的孩子视为一个线性表，且以单链表作为存储结构，则n个节点就有n个孩子链表

n个头指针又组成一个线性表，可采用顺序存储结构

孩子表示法寻找孩子操作简单，寻找双亲操作则需要遍历

孩子兄弟表示法

二叉树表示法，使用二叉链表作为树的存储结构，每个节点包括：节点值、指向节点第一个孩子节点的指针，指向节点下一个兄弟节点的指针

优点：可以方便的实现树转二叉树的操作

5.4.2树、森林、二叉树的转换

树转二叉树

每个节点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟

根没有兄弟，所以树转换为二叉树时没有右子树

在兄弟节点之间加一条线
对每个节点，只保留它与左边第一个孩子的连线，与其他孩子的连线删除
以树根为中心，旋转

森林转二叉树

先将森林中的每一棵树转二叉树，森林中的各棵树视为兄弟关系，后一棵树作为前一棵树的右子树

森林中的每一棵树都转换成相应的二叉树
每棵树的根视为兄弟，每棵树的跟之间增加一条连线
以一颗树的根为中心旋转

二叉树转森林

若二叉树非空，二叉树的根及其左子树作为第一棵树的二叉树形式，将根的右连接断开。二叉树根的右子树视为一个由除第一棵树外的森林转换后的二叉树

5.4.3树和森林的遍历

树的遍历

先根遍历
1. 先访问根节点
2. 再依次访问根节点的每一棵子树，遍历子树时仍遵循先根后子树
后根遍历
1. 先依次遍历根节点的每棵子树，子树遍历时仍遵循先子树后根
2. 访问根节点

二叉树的后根遍历 = 中序遍历

森林的遍历

先序遍历森林
1. 访问森林中每一棵树的根节点
2. 先序遍历第一棵树中根节点的子树森林
3. 先序遍历除去第一棵树之后剩余的树构成的森林
中序遍历森林
1. 中序遍历森林中第一棵树的根节点的子树森林
2. 访问第一棵树的根节点
3. 中序遍历除去第一棵树之后剩余的树构成的森林

5.5.1哈夫曼树与哈夫曼编码

带权路径长度：从树的根到一个节点的路径长度与该节点上权值的乘积

哈夫曼树：n个节点的二叉树中，其中带权路径长度 WPL最小的二叉树

哈夫曼树的构造

将n个节点分别作为n棵仅含一个节点的二叉树，构成森林F
构造一个新节点，从F中选出两棵根节点权值最小的树作为新节点的左右子树，并且新节点的权值置为左右子树上根节点的权值之和
从F中删除刚才选出的两棵树，同时加入新树
重复

特点：

每个初始节点最终都成为叶节点，权值越小的节点到根节点的路径长度越大
构造过程共创建了n-1个新节点，因此节点总数为2n-1
每次构造选取2棵子树作为新节点的孩子，因此哈夫曼树不存在度为1的节点

哈夫曼编码

固定长度编码：对每个字符使用相等长度的二进制位表示

可变长度编码：允许对不同字符使用不等长的二进制位编码

前缀编码：没有一个编码是另一个编码的前缀

哈夫曼编码：

将每个字符作为一个独立的节点，其权值为它出现的频度（次数），构造出对应的哈夫曼树，从根到叶节点的路径上的分支标记字符串作为该字符编码

左分支、右分支表示0或者1不确定，得出的哈夫曼树不一定

5.5.2并查集

树的双亲表示作为并查集的存储结构，每个子集合使用一棵树表示，所有表示集合的树构成表示全集合的森林，存放在双亲表示数组内，通常使用数组元素下标表示元素名，用根节点的下标代表子集合名，根节点的双亲域为负数（可设置为该子集合元素数量的相反数）

并查集初始化

树表示并查集

两个集合的并

基本实现

//并查集的基本操作
#define SIZE 13
int UFSets[SIZE];	//集合元素数组//初始化并查集
void Initial(int S[]){for(int i=0; i<SIZE; i++)S[i] = -1;
} //Find “查”操作，找x所属集合（返回x所属根节点）
int Find(int S[],int x){while(S[x]>=0)		//循环寻找x的根x = S[x];return x;			//根的S[]小于0 
} 
//Union “并”操作，将两个集合合并为一个 
void Union(int S[],int Root1,int Root2){//要求Root1与Root2是不同的集合if(Root1 == Root2)	return;//将根Root2连接到另一根Root1下面S[Root2] = Root1; 
}

并查集优化

6.图

6.1.1图的定义

图G由顶点集V和边集E组成，记为 G = （V，E），其中V（G）表示图的有限非空集，E（G）表示图G中顶点之间的关系

线性表可以是空表，树可以是空树，但图不能是空图

图中不能一个顶点也没有，即顶点集V一定非空，但边集E可以为空

有向图

E是有向边（弧）的有限集合，弧是顶点的有序对，记为<v,w>，其中v,w是顶点，v称为弧尾，w称为弧头

无向图

边是顶点的无序对，记为（v，w）

简单图

不存在重复边

不存在顶点到自身的边

多重图

某两个顶点之间的边数大于1条，又允许顶点通过一条边和自身关联

顶点的度

顶点的度：依附于顶点v的边的条数，TD(v)

无向图的全部顶点的度之和等于边数的2倍

入度：有向图中，以顶点为终点的有向边的数目，ID（v）

出度：有向图中，以顶点为起点的有向边的数目，OD（v）

路径

指从顶点 vp 到 vq 之间的顶点序列

路径长度：路径上边的数目

回路/环：第一个顶点和最后一个顶点相同的路径

若一个图有n个顶点，且有大于n-1条边，则图一定有环

简单路径：顶点不重复出现的路径

简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路

距离

两顶点之间最短路径长度

子图

设有两个图 G = （V，E）和 G’ = （V’，E’），若 V‘ 是 V 的子集，E’ 是 E 的子集，则称 G‘ 是 G 的子图

并非V E的任何子集都可以构成子图——有可能不是图，即E的子集中的某些边关联的顶点不在 V的子集中

连通

无向图中，从顶点v到顶点w有路径存在

连通图

图G中任意两个顶点都是连通的，否则为非连通图

连通分量

无向图的极大连通子图

一个图有n个顶点，若边数小于n-1，必为非连通图

强连通图

强连通：有向图中，一对顶点 v 和 w 之间，既有 v 到 w 的路径，又有 w 到 v 的路径

若任意一对顶点都是强连通的，则称之为强连通图

强连通分量

有向图中的极大强连通子图

生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图，若图中顶点数为n，则它的生成树含有n-1条边

生成树若删除一条边就会变成非连通图，若加上一条边就是形成回路

边的权重

一个图中，每条边都可以标上含有某种含义的数值，该数值称为权值

带权图：边上带有权值的图

带权路径长度：路径上所有边的权值之和

完全图

对于无向图，|E|的取值范围从 0 到 n(n-1)/2，有 n(n-1)/2的图称为完全图

完全图任意两个顶点之间存在边

有向完全图

对于有向图，|E|的取值范围为 0 到 n(n-1) ，有 n(n-1)条弧的有向图称为有向完全图

有向完全图两顶点之间存在方向相反的两条弧

稠密图

边数很少的图，一般 |E| < |V|log2|V|

又向树

一个顶点的入度为0，其余顶点的入度均为1的有向图

6.2.1图的存储——邻接矩阵法

用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（各顶点之间的邻接关系），存储顶点之间的邻接关系的二维数组称为邻接矩阵

出入度计算：

第i个节点的出度 = 第 i 行非0元素

第i个节点的入度 = 第 i 列非0元素

//邻接矩阵法
#define MaxVertexNum 100		//顶点数目的最大值 
typedef struct{char Ver[MaxVertexNum];					//顶点表 int Edge[MaxVertexNum][MaxVertexNum];	//邻接矩阵、边表int vexnum,arcnum; 						//图的当前顶点数和边数/弧数 
}MGraph; 
//邻接矩阵法存储带权图	
#define MaxVertexNum 100		//顶点数目的最大值 
#define INFINITY 最大的int值	//宏定义常量“无穷” 
typedef char VertexType;		//顶点的数据类型 
typedef int EdgeType;			//带权图中边上权值的数据类型 
typedef struct{VertexType Vex[MaxVertexNum];				//顶点 EdgeType Edge[MaxVertexNum][MaxVertexNum];	//边的权 int vexnum,arcnum;							//图的当前顶点数和弧数 
}MGraph;

无向图的邻接矩阵是对称矩阵，规模大时可使用压缩存储

邻接矩阵表示法的空间复杂度 O(n^2)，n为顶点数 |V|

特点

无向图的邻接矩阵一定是一个唯一的对称矩阵，因此，实际存储邻接矩阵时只需要存储上（下）三角矩阵
对于无向图，邻接矩阵的第 i 行非零元素的个数正好是顶点 i 的出度，第 i 列非零元素的个数正好是顶点 i 的入度
邻接矩阵存储很容易确定两个顶点之间是否有边相连
稠密图适合邻接矩阵存储

6.2.2图的存储——邻接表法

对图G中的每个顶点建立单链表，第 i 个单链表中的节点表示依附于顶点 v 的边（有向图表示以顶点 v 为尾的弧），这个单链表称为顶点 v 的边表（对于有向图称为出边表）

边表的头指针和顶点的数据信息采用顺序存储，称为顶点表

//用邻接表存储的图
typedef struct{AdjList vertices;int vexnum,arcnum;
}ALGRaph; 
//“边/弧” 
typedef struct ArcNode{int adjvex;				//边/弧指向哪个结点 struct ArcNode *next;	//指向下一条弧的指针 //InfoType info;		//边权值 
}ArcNode; 
//顶点
typedef struct VNode{VertexType data;	//顶点信息 ArcNode *first;		//第一条边/弧 
}VNode,AdjList[MaxvertexNum];

特点

若G为无向图，所需存储空间 O(|V| + 2|E|)，若G是有向图，所需存储空间O(|V| + |E|)
对于稀疏图，适合采用邻接表存储
给定一个顶点很容易找到它所有的邻边，O(n)
无向图邻接表中，某个顶点的度只需计算其邻接表中边表节点的个数，在有向图的邻接表中，求某个顶点的出度只需计算其邻接表中的边表节点的个数，但求某个顶点的入度则需要遍历全部邻接表
图的邻接表表示不唯一

6.2.3图的存储——十字链表

十字链表是有向图的一种链式存储结构，有向图的每一条弧用一个节点来表示，每个顶点也用一个节点来表示

很容易找到顶点的入度和出度，图的十字链表示不唯一，但十字链表示唯一确定一个图

6.2.4邻接多重表

邻接多重表是无向图的一种链式存储结构

邻接多重表中，所有依附于同一顶点的边串联在同一链表中，因为每条边依附于两个顶点，所以每个边节点同时连接在两个链表中

对比

6.2.5图的基本操作

6.3.1广度优先搜索

类似于树的层次遍历，首先访问起点v，接着由v出发，依次访问v的各个未访问过的邻接顶点 w1,w2,w3…，然后依次访问w1,w2,w3…的所有未被访问过的邻接顶点，再从这些访问过的顶点出发，访问他们所有未被访问过的邻接顶点，直至所有节点都被访问

算法必须借助一个辅助队列

广度优先搜索地伪码

bool visited[MAX_VERTEX_NUM]
void BFSTraverse(Graps G){for(i = 0 ; i < G.vexnum; i++){visited[i] = FALSE;}IniQueue(Q);for(i = 0 ; i < G.vernum ; i++){if(!visited[i])BFS(G,i);}
}

邻接表实现广度优先搜索

void BFS(ALGraph G,int i){//访问初始节点visit(i); //对 i 做已访问标记visited[i] = TRUE;//顶点i入队EnQueue(Q,i);while(!IsEmpty(Q)){//队首v出队DeQueue(Q,v);//检测v的所有邻接点for(p = G.vertices[v].firstarc;p;p=p->nextarc){w = p->adjvex;if(visited[w] == FALSE){//w为v的尚未访问的邻接点，访问wvisit(w);//对 w 做已访问标记visited[w] = TRUE;//顶点 w 入队EnQueue(Q,w);}}}
}

邻接矩阵实现广度优先搜索

//广度优先遍历 
bool visited[MAX_VERTEX_NUM];	//访问标记数组 
void BFSTraverse(Graph G){		//对图G进行广度优先遍历	for(i=0; i<G.vexnum; ++i)	 visited[i] = FALSE;		//访问标记数组初始化 InitQueue(Q);				//初始化辅助队列Q for(i=0; i<G.vexnum; ++i)	//从0号顶点开始遍历	 if(!visited[i])			//对每个连通分量调用一次BFS BFS(G,i);			//vi未访问过，从vi开始BFS 
} 
void BFS(Graph G,int v){		//从顶点v出发，广度优先遍历图G visit(v);					//访问初始顶点v visited[i] = TRUE;			//对v做已访问标记 Enqueue(Q,v);				//顶点v入队列Q while(!isEmpty(Q)){DeQueue(Q,v);			//顶点v出队列 for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w))//检测v所有邻接点if(!visited[w]){	//w为v的尚未访问的邻接顶点 visit(w);		//访问顶点w visited[w]=TRUE;//对w做已访问标记 EnQueue(Q,w);	//顶点w入队列 }//if}//while
}

广度优先遍历的过程

性能分析

需要借助一个辅助队列Q，n个顶点均需入队一次，最坏空间复杂度为O(|V|)

时间复杂度邻接矩阵 O(|V| + |V|^2) 邻接表 O(|V|+|E|)

BFS求解单源最短路径问题

非带权图的单源最短路径：从顶点u到顶点v的最短路径为从u到v的任何路径中边数最少

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int u){//d[i]表示u到i结点最短路径 for(i=0; i<G.vexnum; ++i){d[i] = ∞;		//初始化路径长度 path[i] = -1;	//最短路径从哪个顶点过来 } d[u] = 0;visited[u] = TRUE;EnQueue(Q,u);while(!isEmpty(Q)){while(!isEmpty(Q)){				//BFS算法主过程 DeQueue(Q,u);				//队头元素u出队 for(w=FirstNeighbor(G,u); w>=0; w=NextNeighbor(G,u,w))if(!visited[w]){		//w为u的尚未访问的邻接顶点 d[w] = d[u]+1;		//路径长度加1 path[w] = u;		//最短路径应从u到w visited[w] = TRUE;	//设已访问标记 EnQueue(Q,w);		//顶点w入队 }//if}//while}
}

广度优先生成树

广度优先搜索的遍历树为一棵广度优先生成树

图的邻接矩阵存储表示是唯一的，所以其广度优先生成树唯一

图的邻接表存储表示不唯一，所以其广度优先生成树不唯一

6.3.2深度优先搜索

它的基本思想如下：首先访问图中某一起始顶点v，然后由ν出发，访问与ν邻接且未被访问的任意一个顶点w1，再访问与w1邻接且未被访问的任意一个顶点w2··重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

//深度优先遍历
bool visited[MAX_VERTEX_NUM];	//访问标记数组
void DFSTraverse(Graph G){		//对图G进行深度优先遍历 for(v=0; v<G.vexnum; ++v)visited[v] = FALSE;		//初始化已访问标记数据 for(v=0; v<G.vexnum; ++v)	//从v = 0开始遍历 if(!visited[w])DFS(G,v);
} 
void DFS(Graph G,int v){	//从顶点v出发，深度优先遍历G visit(v);				//访问顶点v visited[v] = TRUE;		//设已访问标记 for(w=FirstNeighbor(G,v); w>=0; w=NextNeighor(G,v,w))if(!visited[w]){	//w为u的尚未访问的邻接顶点 DFS(G,w);}	//if
}void DFS(MGraph G,int i){visit(i);visited[i] = TRUE;for(j = 0 ; j < G.vexnum ; j++){if(visited[j] == FALSE && G.edge[i][j] == 1){DFS(G,j);}}
}

图的邻接矩阵遍历得到的DFS和BFS序列唯一

图的邻接表遍历得到的DFS和BFS序列不唯一

性能分析

空间复杂度 DFS是一个递归算法，需要一个递归工作栈，空间复杂度为 O(|V|)

时间复杂度邻接矩阵 O(|V|^2) 邻接表 O(|V|+|E|)

深度优先生成树与生成森林

只有连通图调用DFS时才能生成深度优先生成树，否则产生的是深度优先生成森林，且邻接表产生的结果不唯一

6.3.3图的遍历与图的连通性

6.4.1最小生成树

一个连通图的最小生成树包含图中所有顶点，且含有尽可能少的边

权值之和最小的那棵生成树称为G的最小生成树

性质

若图G中存在权值相同的边，则G的最小生成树可能不唯一，即最小生成树的树形不唯一，当图G中各边的权值互不相等时，G的最小生成树唯一；若无向连通图G的边数比定点数少1，即G本身是一棵树时，G的最小生成树就是它本身
虽然最小生成树不唯一，但其对应边的权值之和是唯一的，而且是最小的
最小生成树的边数为顶点数减1

最小生成树中所有边的权值之和最小，但是不能保证任意两个顶点之间的路径是最短路径

Prim算法

初始时从图中任取一顶点，加入树T，此时树中只包含一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T的顶点数和边数加1

时间复杂度 O(|V|^2)

不依赖于|E|，适用于求边稠密图的最小生成树

Kruskal算法

初始时只有n个顶点而无边的非连通图T{V，{}}，每个顶点自成一个连通分量，然后按照边的权值大小排序，不断选取当前未被选取过的权值最小的边，，若该边依附的顶点落在T中不同的连通分类上（使用并查集判断这两个顶点是否属于一棵集合树），则将边加入T，否则舍弃此边而选择下一条权值最小的边

时间复杂度 O(|E|log2|E|)

不依赖于|V|适用于边稀疏而顶点数多的图

6.4.2最短路径

广度优先搜索查找最短路径——无向图

带权有向图的最短路径问题可以分为两类：

单源最短路径：求图中某一顶点到其他各点的最短路径——Dijkstra算法
求每对顶点的最短路径——Floyed算法

Dijkstra求解单源最短路径问题

构造过程设置3个辅助数组：

final[]:标记各顶点是否已找到最短路径，即是否加入S集合
dist[]:记录从源点v到其他各点的最短路径长度，初始值为：若v到顶点有弧，则dist[i]为弧长，否则置∞
path[]：path[i]表示从源点到顶点i之间的最短路径的前驱节点，算法结束时可通过它追溯最短路径

实例

时间复杂度邻接表和邻接矩阵表示 O(|V|^2)

边上带有负权值时，Dijkstra算法并不适用

Floyd算法求各顶点之间最短路径问题

Floyd算法的基本思想是：递推产生一个 n 阶方阵序列 A—1 A0.，A0.，AF1，其中AP国历表示从顶点v到顶点 v的路径长度，k表示绕行第 k个顶点的运算步骤。初始时，对于任意两个顶点v，和v，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以。作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点k作为中间顶点。若增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径

时间复杂度 O(|V|^3)

允许带有负权值的边，但不允许总权值为负的回路

6.4.3有向无环图描述表达式

有向无环图：若一个有向图中不存在环，则称有向无环图，简称DAG图

6.4.4拓扑排序

AOV网：若用有向无环图表示一个工程，其顶点表示活动，用有向边<Vi,Vj>表示活动Vi必须经过活动Vj进行的这样一种关系，则这种有向图称为顶点表示活动的网络

拓扑排序：由一个有向无环图的顶点组成的序列，当且仅当满足：

每个顶点只出现一次
若顶点A在序列中排在顶点B的前面，则在图中不存在B到A的路径

称为一个拓扑图

对一个AOV网进行拓扑排序：

从AOV网中选择一个没有前驱（入度为0）的顶点并输出
从网中删除该顶点和所有以它为起点的有向边
重复1和2，直到当前AOV网为空所当前网中不存在无前驱的顶点为止

//拓补排序
#define MaxVertexNum 100	//图中顶点数目的最大值
typedef struct ArcNode{		//边表结点 int adjvex;			//该弧所指向的顶点的位置 struce ArcNode *nextarc;//指向下一条弧的指针 //InfoType info; 		//网的边权值 
}ArcNode;
typedef struct VNode{		//顶点表结点 VertexType data;		//顶点信息 ArcNode * firstare;		//指向第一条依附该顶点的弧的指针 
}VNode,AdjList[MaxvertexNum];
typedef struct{AdjList vertices;		//邻接表 int vexnm,arcnum;		//图的顶点数和弧数 
}Graph; 					//Graph是以邻接表存储的图类型 bool TopologicalSort(Graph G){InitStack(S);for(int i=0 ;i<G.vexnum; i++)if(indegree[i] == 0)Push(S,i);int count=0;while(!IsEmpty(S)){Pop(S,i);print[count++]=i;for(P=G.vertices[i].firstarc; p; p->nextarc){//将所有i指向的顶点的入度减1，并且讲入度减为0的顶点压入栈Sv=p->adjvex;if(!(--indegree[v])) Push(S,v);	}}//while
if(count<G.vexnum)return false;
elsereturn true;
}

因为输出每个顶点的同时还要删除以它为起点的边，所以采用邻接表存储时时间都咋读为O(|V|+|E|)，采用邻接矩阵存储时时间复杂度为O(|V|^2)

对于有向无环图G中的任意节点u，v，他们之间的关系必然如下：

若u是v的祖先，则在调用dfs访问u之前，必然已经对v进行了dfs访问，即v的dfs结束时间先于u的dfs结束时间，从而可以考虑在dfs函数中设置一个时间标记，在DFS调用结束时，对各顶点计时，因此祖先的结束时间必然大于子孙的结束时间
若u和v没有路径关系，则在u和v拓扑序列的关系任意

于是，按结束时间从大到小排列，就可以得到一个拓扑序列

逆拓扑序列

从AOV网中选择一个没有后继的顶点并输出
从网中删除该顶点和所有以它为终点的有向边
重复

拓扑排序处理AOV网时的问题：

入度为0的顶点，即没有前驱活动或前驱活动都已经完成的顶点，工程可以从这个顶点代表的活动开始或继续
拓扑排序的结果可能不唯一：拓扑序列唯一的条件是在每次输出顶点时，检测入度为0的顶点是否唯一，若每次都是唯一，则拓扑序列唯一
AOV网中各顶点地位相等，每个顶点的编号是人为的

6.4.5关键路径

用边表示活动的网络——AOE网：带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销

AOE网与AOV网对比：AOE网和AOV网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE网的边有权值，AOV网的边无权值

AOE网的性质：

只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
只有在进入某顶点的各有向边所代表的活动都已经结束时，该顶点所代表的事件才能发生

AOE网中仅有一个入度为0的顶点，称为开始顶点，表示整个工程的开始，也仅有一个出度为0的顶点，称为结束顶点，表示整个工程的结束

关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动

完成整个工程的最短时间就是关键路径的长度，即关键路径上各项活动花费开销的总和

事件的最早发生时间

从源点到事件顶点的最长路径长度

事件的最迟发生时间

活动最早开始时间

该活动的弧的起点所表示的事件的最早发生时间

活动的最迟开始时间

一个活动的最迟开始时间和最早开始时间的差

指该活动完成的时间余量，即在不增加整个工程完成所需时间的情况下，活动可以拖延的时间

若一个活动的时间余量为0，则说明该活动必须要如期完成，否则会拖延整个工程进度，所以这样的活动为关键活动

求关键路径

实例

关键路径上的所有活动都是关键活动，决定整个工期的关键因素，可以通过加快关键路径来缩短整个工程的工期，但也不能任意缩短关键轰动，因为一旦缩短到一定程度，该关键活动就可能会变成非关键活动
网中的关键路径并不唯一，对于有多条关键路径的网，仅缩短一条关键路径上的关键活动并不能缩短整个工程的工期，只有缩短包含在所有关键路径上的关键活动的才能缩短工期

7.查找

7.1.1查找的基本概念

查找：在数据结构中寻找满足某种条件的数据元素的过程

查找表：用于查找的数据集合，由同一类的数据元素组成

静态查找表：静态查找表。若一个查找表的操作只涉及查找操作，则无须动态地修改查找表，此类查找表称为静态查找表。与此对应，需要动态地插入或删除的查找表称为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等；适合动态查找表的查找方法有二叉排序树的查找、散列查找等。

关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的

平均查找长度：一次查找的长度是指需要比较的关键字的次数，平均查找长度是指所有查找过程进行关键字比较次数的平均值

7.2.1顺序查找

顺序查找也称线性查找，对顺序表和链表都适用

一般线性表的顺序查找

从线性表的一端开始，逐个检查关键字是否满足给定条件
若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置
若已经查找到表的另一端，但还没查找到符合给定条件的元素，则返回查找失败信息

typedef struct{		//查找表的数据结构（顺序表） ElemType *elem;	//动态数组基址 int TableLen;	//表的长度 
}SSTable;
//顺序查找 
int Search_Seq(SSTable ST,ElemType key){int i;for(i=0; i<ST.TableLen && ST.elem[i] != key; ++i);//查找成功，则返回元素下标；查找失败，则返回-1return i==ST.TableLen? -1:i; 
} //顺序查找(哨兵）
int Search_Seq(SSTable ST,ElemType key){(ST.elem[0] = key;)	//哨兵 int i;for(i=ST.TableLen; ST.elem[i] != key; --i);	//引入哨兵时 //查找成功，则返回元素下标；查找失败，则返回0 return i; 
}

查找成功时的平均查找次数

查找失败时的平均查找次数

优点：对数据元素的存储没有要求

缺点：n比较大时，平均查找长度大，效率低

链表只能进行顺序查找

有序线性表的顺序查找

若在查找之前就已经知道表中所有关键字是有序的，则查找失败时可以不用比较到表的另一端就能返回查找失败的信息，从而降低查找失败的平均查找长度

判定树

查找成功的平均查找长度和一般线性表的顺序查找一样

查找失败时的平均查找长度

优于一般的顺序查找

注意有序顺序表的顺序查找的数据结构可以是链式存储结构，但折半查找只能是顺序存储结构

7.2.2折半查找

首先将给定值key与表中间位置的元素进行比较，若相等，则查找成功，返回该元素的存储位置
若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分
在缩小的范围内继续查找

//折半查找
int Binary_Search(SSTable L, ElemType key){int low = 0, high = L.TableLen-1, mid;while(low <= high){mid = (low + high)/2;		//取中间位置 if(L.elem[mid] == key)return mid;				//查找成功则返回所在位置 else if(L.elem[mid] > key)high = mid - 1;			//从前半部分继续查找 elselow = mid + 1;			//从后半部分继续查找 }return -1;						//查找失败，返回-1 
}

折半查找下标从零开始

折半查找判定树

每个圆形节点表示一个记录，节点中的值为该记录的关键字值，树中最下面的叶节点都是方形的，表示查找失败的区间

特点

每个节点值均大于左子节点值，均小于右子节点值

若有序序列有n各元素，则对应判定树有n个圆形的非叶节点和n+1个方形的叶节点

折半查找的判定树是一棵平衡二叉树

查找成功时的平均查找长度

判定树求查找成功与失败的查找长度

查找成功时的查找长度是从根节点到目的节点的路径上的节点数

查找失败时的查找长度是从根节点到对应失败节点的父节点的路径上的节点数

7.3.2分块查找

分块查找也称索引顺序查找

基本思想：

将查找表分为若干个小块，块内元素可以无须，但块间元素是有序的，即第一块的最大关键字小于第二块中所有记录的关键字
建立一个索引表，索引表中每个元素含有各块的最大关键字和各块中第一个元素的地址，索引表按关键字有序排列
查找时，在索引表中确定待查找记录所在的块，可以顺序查找或折半查找索引表
在块内顺序查找

7.3.1二叉排序树

特性：

若左子树非空，则左子树上所有节点的值均小于根节点的值
若右子树非空，则右子树上所有节点的值均大于根节点的值
左右子树也是一棵二叉排序树

对二叉排序树进行中序遍历可以得到一个递增有序序列

二叉排序树的查找

若二叉排序树非空，先将给定值与根节点关键字比较，若相等，则查找成功，若不等，当小于根节点的关键字，则在根节点的左子树上查找，否则在根节点的右子树上查找

这是一个递归的过程

//二叉排序树结点
typedef struct BSTNode{int key;struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree; 
//在二叉排序树中查找值为key的结点
BSTNode *BST_Search(BSTree T,int key){while(T!=NULL && key!=T->key){	//若树空或等于根结点值，则结束循环 if(key<T->key)T=T->lchild;	//小于，则在左子树上查找 elseT=T->rchild;	//大于，则在右子树上查找 }return T;
} //在二叉排序树中查找值为key的结点（递归实现）
BSTNode *BSTSearch(BSTree T, int key){if(T == NULL)return NULL;	//查找失败if(key == T->key)return T;		//查找成功else if(key < T->key)return BSTSearch(T->lchild,key);	//在左子树中找elsereturn BSTSearch(T->rchild,key);	//在右子树中找 
}

二叉排序树的插入

若二叉排序树为空，则直接插入，否则，若关键字k小于根节点值，则插入到左子树，若关键字k大于根节点值，则插入到右子树

新插入节点一定是一个叶节点，且是查找失败时查找路径上访问的最后一个节点的左孩子或右孩子

//在二叉排序树插入关键字为k的新结点（递归实现）
int BST_Insert(BSTree &T, int k){if(T==NULL){			//原树为空，新插入结点为根结点 T=(BSTree)malloc(sizeof(BSTNode));T->key = k;T->lchild = T->rchild = NULL;return 1; 			//返回1.插入成功 }else if(k == T->key)	//树中存在相同关键字的结点，插入失败 return 0; else if(k<T->key)		//插入到T的左子树 return BST_Insert(T->lchild,k);else					//插入到T的右子树 return BST_Insert(T->rchild,k); 
}

二叉排序树的构造

//按照 str[] 中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T,int str[],int n){T=NULL;			//初始时T为空树 int i=0;while(i<n){		//依次将每个关键字插入到二叉排序树中 BST_Insert(T,str[i]);i++;}
}

二叉排序树的删除

三种情况：

若被删除节点z是叶节点，则直接删除，不会破坏二叉排序树的性质
若节点z只有一棵左子树或右子树，则让z的子树成为z父节点的子树，替代z的位置
若节点z有左右两棵子树，则令z的直接后继（或直接前驱）代替，然后从二叉排序树中删除这个最直接后序（直接前驱），转化为第一二中情况

二叉树中序序列找前驱、后继：

前驱：左子树最右下节点

后继：右子树最左下节点

查找效率分析

主要取决于树的高度

二叉排序树与折半查找对比：

7.3.2平衡二叉树（AVL树）

规定在插入和删除节点时，要保证任意节点的左右子树高度差的绝对值不超过1

平衡因子：节点左右子树的高度差，取值 -1 0 1

平衡二叉树的插入

每当在二叉排序树中插入（删除）一个节点时，首先检查其插入路径上的节点是否因为此次操作导致了不平衡，，若导致了不平衡，则先找到插入路径上李插入节点最近的平很因子大于1的节点A，在对以A为根的子树（最小不平衡子树），进行调整

LL平衡旋转（右单旋转）：在节点A的左孩子（L）的左子树（L）上插入了新节点

A的左孩子B向右上旋转代替A成为根节点，将A向右下旋转成为B的右孩子，而B的原右子树作为A的左子树
RR平衡旋转（左单旋转）：在节点A的右孩子（R）的右子树（R）上插入了新节点

将A的右孩子B向左上旋转代替A成为根节点，将A向坐下旋转成为B的左孩子，而B的原左子树作为A的右子树
LR平衡旋转（先左后右双旋转）：在节点A的左孩子（L）的右子树（R）上插入了新节点

先将A的左孩子B的右子树根节点C向左上旋转提升到B的位置，然后把C向右下旋转提升到A的位置
RL平衡旋转（先右后左双旋转）：在节点A的右孩子（R）的左子树（L）上插入新节点

先将A的右孩子B的左子树的根节点C向右上旋转提升到B的位置，然后把C向左上旋转提升到A的位置

平衡二叉树的构造

平衡二叉树的删除

平衡二叉树的查找

进行关键字比较的次数不超过树的深度

7.3.3红黑树

每个节点是红色或者黑色的
根节点是黑色的
叶节点（虚构的外部节点，NULL节点）都是黑色的
不存在两个相邻的红节点（红节点的父节点和孩子节点都是黑色的）
对每个节点，从该节点到任意一个节叶节点的简单路径上，所含黑节点的数量相同

左根右根叶黑

不红红黑路同

黑高：从某节点出发（不含该节点）到达一个叶节点的任意一个简单路径上的黑节点总数称为黑高，根节点的黑高为红黑树的黑高

从根节点到叶节点的最长路径不能大于最短路径的2倍：从根节点到任意一个叶节点的简单路径最短时，这条路径必然全由黑节点构成，某条路径最长时，必然由黑节点和红节点相间构成，黑红节点数量相同
有n个内部节点的红黑树的高度
新插入红黑树中的节点初始为红色——只需要关注是否满足条件：不红红

平衡二叉树——任意一个节点的左右子树高度差不超过1

红黑树——任意一个节点的左右子树的高度，相差不超过2倍

红黑树的插入

二叉排序树插入法插入，并将新插入节点z着色为红色，若节点z的父节点为黑色，无须做任何调整，此时就是一个标准的红黑树，结束
若节点z是根节点，则将z着色为黑色（树的黑高增加1），结束
若节点z不是根节点，且z的父节点z.p不是红色的，则按照z的叔父系欸但的颜色不同，分为三种情况：
1. z的叔节点y是黑色的，且z是一个右孩子：（LR，先左旋，后右旋）即z是其爷节点的左孩子的右孩子——先做一次左旋，转化为情况2（变为情况2 后再做一次右旋），左旋后z和父节点z.p交换位置
2. z的叔节点y是黑色的，且z是一个左孩子：（LL，右单选）即z是其爷节点的左孩子的左孩子，做一次右旋，并交换z的原父节点和原爷节点的颜色
3. z的叔节点是红色的，z的父节点z.p和叔节点都是红色的，因为爷节点z.p.p是黑色的，将z.p和y都着为黑色，z.p.p着为红色

7.4.1B树及其基本操作

m阶B树是所有节点的平衡因子均小于等于0的m路平衡查找树

m阶B树：

树中每一节点至多有m棵子树，即至多m-1个关键字
若根节点不是叶结点，则至少有2棵子树，即至少1个关键字
除根节点之外的所有非叶节点至少有 m/2 向上取整棵子树，即至少有 m/2向上取整-1 个关键字
所有非叶节点结构如下：
所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部节点或类似于折半查找判定树的失败节点，实际上这些节点并不存在，指向这些节点的指针为空）

一颗 5 阶B树

节点的孩子个数等于该节点的关键字个数加1
若根节点没有关键字就没有子树，则此时B树为空，若根节点有关键字，则其子树个数必然大于等于2，因为子树个数等于关键字个数加1
1. 除根节点之外，所有非叶节点至少有 3 棵子树，至多有5棵子树
结点中的关键字从左到右递增有序，关键字两侧均有指向子树的指针，左侧指针所指子树的所有关键字均小于该关键字，右侧指针所指子树的所有关键字均大于该关键字。或者看成下层结点的关键字总是落在由上层结点的关键字所划分的区间内，如第二层最左结点的关键字划分成了3个区间：（—∞，5），（5，11），（11，+∞），该结点中的3个指针所指子树的关键字均分别落在这3个区间内。
所有叶结点君主第4层，代表查找失败位置

B树的查找

B树的查找包含两个基本操作：0在B树中找结点； 2在结点内找关键字。B树常存储在磁盘上，因此前一查找操作是在磁盘上进行的，而后一查找操作是在内存中进行的，即在磁盘上找到目标结点后，先将结点信息读入内存，然后再采用顺序查找法或折半查找法。因此，在磁盘上进行查找的次数即目标结点在B树上的层次数，决定了B树的查找效率。

B树的高度

B树中大部分操作所需的磁盘存取次数与B树高度成正比

B树的插入

定位：利用B树的查找算法，找出插入该关键字的终端节点（在B树中查找key时会找到表示查找失败的叶结点，因此插入位置一定是最底层的叶结点）
插入：每个非根节点的关键字个数都在 [ m/2 向上取整 -1 , m -1]，若节点插入后的关键字个数小于m，可以直接插入，若节点插入后的关键字个数大于m-1，必须对节点进行分裂
- 分裂的方法：取一个新节点，在插入key后的源节点，从中间位置（m/2 向上取整）将其中的关键字分为两部分，做部分放在源节点中，有部分包含的关键字放到新系欸但中，中间位置 ( m/2 向上取整) 的节点插入源节点的父节点

B树的删除

要保证删除后的节点中的关键词个数 >= m/2 向上取整 -1 ——需要进行节点合并操作

直接删除关键字：若被删关键字所在的节点删除前的关键字个数 >= m/2 向上取整，表明删除该关键字后仍满足B树的定义，则直接删除
兄弟够借：若被删关键字所在节点删除前的关键字个数 = m/2向上取整 - 1 ，且与该节点相邻的右（左）兄弟节点的关键字个数 >= m/2 向上取整，则需要调整该节点、右兄弟节点及其双亲节点
兄弟不够借：若被删关键字所在节点删除前的关键字个数 = m/2 向上取整 - 1，且此时与该节点相邻的左右兄弟节点的关键字个数都 = m/2向上取整 - 1 ，则将关键字删除后与左右兄弟节点及双亲节点中的关键字进行合并

7.4.2B+树的基本概念

一棵m阶B+树应满足：

每个分支节点最多m棵子树
非叶根节点至少有两棵子树，其他分支节点至少有 m/2 向上取整棵子树
节点的子树个数与关键字个数相等
所有叶结点包含全部的关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序链接起来（支持顺序查找）
所有分支节点（可视为索引的索引）中仅包含它的各个子节点（下一级索引块）中关键字的最大值及指向其子节点的指针

B+树与B树的差异：

在B+树中，具有n个关键字的节点只含有 n 棵子树，，即每个关键字对应一颗子树：而在B树中，具有n个关键字的节点含有n+1棵子树
在B+树中，叶结点包含了全部的关键字，非叶节点出现的关键字也会出现在叶结点中；而在B+树中最外层的终端节点包含的关键字和其他节点包含的关键字是不重复的
在B+树中，叶结点包含信息，所有非叶节点仅起索引作用，非叶节点的每个索引项只含有对应子树的最大关键字和指向该树的指针，不含有对应记录得存储地址，这样能使一颗磁盘块存储更多的关键字，使得磁盘存读写次数更少，查找速度更快

7.5.1散列表的基本概念

散列函数（也称哈希函数）：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash（key）=Addr（这里的地址可以是数组下标、索引或内存地址等）。

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生冲突的不同关键字称为同义词。一方面，设计得好的散列函数应尽量减少这样的冲突；另一方面，因为这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。

散列表：根据关键字至今进行访问的数据结构，时间复杂度O（1）

7.5.2散列函数构造方法

在构造散列函数时，必须注意以下几点：

1）散列函数的定义域必须包含全部关键字，而值域的范围则依赖于散列表的大小。

2）散列函数计算出的地址应尽可能均匀地分布在整个地址空间，尽可能地减少冲突。

3）散列函数应尽量简单，能在较短的时间内计算出任意一个关键字对应的散列地址。

下面介绍常用的散列函数。

直接定址法

除留取余法

数字分析法

平方取中法

7.5.3处理冲突的方法

开放定址法

表中可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放

拉链法

可以把所有的同义词存储在一个线性链表中，这个线性链表由其他散列地址唯一标识

7.5.4散列查找及性能分析

8.排序

8.1.1排序的定义

排序：重新排列表中元素，使表中元素满足关键字有序的过程

算法的稳定性：关键字相同的元素在表中的相对位置排序后是否发生改变

内部排序：排序期间元素全部放在内存中

外部排序：排序期间元素无法全部同时放在内存中，必须在排序过程中根据要求不断地在内外存中移动

8.2.1直接插入排序

插入排序基本思想

每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成

直接插入排序

查找L(i)在L(1 … i-1)中插入的位置k
将L(k … i-1)中所有元素依次后移一个位置
将L(i)复制到L(k)

//直接插入排序
void InsertSort(int A[], int n){int i,j,temp;for(i=1; i<n; i++)			//将各元素插入已排好序的序列中 if(A[i]<A[i-1]){		//若A[i]关键字小于前驱 temp = A[i];		//用temp暂存A[i] for(j=i-1; j>=0&&A[j]>temp; --j)	//检查所有前面已排好序的元素 A[j+1] = A[j];	//所有大于temp的元素都向后挪位 A[j+1] = temp;		//复制到插入位置 }
} 
//直接插入排序（带哨兵）
void InsertSort(int A[], int n){int i,j;for(i=2; i<=n; i++)			//依次将A[2]~A[n]插入到前面已排序序列 if(A[i]<A[i-1]){		//若A[i]关键字小于前驱，将A[i]插入有序表 A[0] = A[i];		//复制为哨兵，A[0]不存元素 for(j=i-1; A[0]<A[j]; --j)	//向后往前查找待插入位置 A[j+1] = A[j];	//向后挪位 A[j+1] = A[0];		//复制到插入位置 }
}

8.2.2折半插入排序

直接插入排序过程：

①从前面的有序子表中查找出待插入元素应该被插入的位置；

②给插入位置腾出空间，将待插入元素复制到表中的插入位置。注意到在该算法中，总是边比较边移动元素。

当待排序表是顺序存储的线性表时，查找有序子表时可以使用折半查找来实现

//折半插入排序
void InsertSort(int A[], int n){int j,i,low,high,mid;for(i=2; i<=n; i++){			//依次将A[2]~A[n]插入前面的已排序序列 A[0]=A[i];					//将A[i]暂存到A[0] low = 1; high = i-1; 		//设置折半查找的范围 while(low<=high){			//折半查找（默认递增有序） mid=(low+high)/2;		//取中间点 if(A[mid]>A[0])	high = mid-1;//查找左半子表 else low = mid+1;		//查找右半子表 }for(j=i-1; j>=high+1; --j)A[j+1] = A[j];			//统一后移元素，空出插入位置 A[high+1] = A[0];			//插入操作 }
}

8.2.3希尔排序

基本思想：先将待排序表分割成若干个形如 L[i,i+d,i+2d…i+kd]的特殊子表，即把相隔某个增量的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中元素已成基本有序时，再对全体记录进行一次直接插入排序

//希尔排序
void ShellSort(int A[],int n){int d,i,j;//A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到for(d=n/2; d>=1; d=d/2)	//步长变化for(i=d+1; i<=n; ++i)if(A[i]<A[i-d]){	//需要将A[i]插入有序增量子表 A[0]=A[i];			//暂存在A[0] for(j=i-d; j>0 && A[0]<A[j]; j-=d) A[j+d]=A[j];	//记录后移，查找插入位置 A[j+d]=A[0];		//插入 }
}

8.3.1冒泡排序

交换排序

根据序列中两个关键字的比较结果来对换这两个记录在序列中的位置

冒泡排序

基本思想：从后往前（从前往后）两两比较相邻元素的值，若为逆序，则交换他们，直到序列比较完。称为——第一趟冒泡，结果是将最小的元素交换到第一个位置…

//交换
void swap(int &a,int &b){int temp = a;a = b;b = temp;
} 
//冒泡排序
void BubbleSort(int A[], int n){for(int i=0; i<n-1; i++){bool flag = false;			//表示本趟冒泡是否发生交换的标志 for(int j=n-1; j>i; j--)	//一趟冒泡过程 if(A[j-1] > A[j]){		//若为逆序 swap(A[j-1],A[j]);	//交换 flag = true;}if(flag == false)return					//本趟遍历后没有发生交换，说明表已经有序 }
}

8.3.2快速排序

基本思想：在待排序表L[1…n]中，任取一个元素piovt作为枢轴（基准，通常取首元素），通过一趟排序将待排序表划分为两个独立部分L[1…k-1]和L[k+2…n]，使得L[1…k-1]中的所有元素小于piovt，L[k+1…n]中的所有元素大于或等于piovt，则piovt放在了最终位置L[k]，这是一次划分，递归重复

//用第一个元素将待排序序列划分成左右两个部分
int Partition(int A[], int low, int high){int pivot = A[low];		//第一个元素作为枢轴 while(low<high){		//用low、high搜索枢轴的最终位置 while(low<high&&A[high]>=pivot)	--high;A[low] = A[high];	//比枢轴小的元素移动到左端 while(low<high&&A[low]<=pivot)	++low;A[high] = A[low];	//比枢轴大的元素移动到右端 }A[low] = pivot;			//枢轴元素存放到最终位置 return low;				//返回存放枢轴的最终位置 
} 
//快速排序
void QuickSort(int A[], int low, int high){if(low<high){	//递归跳出的条件 int pivotpos = Partition(A,low,high);	//划分	 QuickSort(A,low,pivotpos-1);	//划分左子表 QuickSort(A,pivotpos+1,high); 	//划分右子表 }
}

8.4.1简单选择排序

选择排序

每一趟（第 i 趟）在后面n-i+1个待排序元素中选取关键字最小的元素，作为有序序列的第 i 个元素，直至 n-1 趟做完，待排序元素只剩一个

简单选择排序

基本思想：假设排序表为L[1…n]，第 i 趟排序即从 L[i…n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序可使排序表有序

//简单选择排序
void SelectSort (int A[],int n){for(int i=0; i<n-1;i++){		//一共进行n-1躺 int min=i;					//记录最小元素位置 for(int j=i+1; j<n; j++)	//在A[i...n-1]中选择最小的元素 if(A[j]<A[min])	min=j;	//更新最小元素位置 if(min!=i) swap(A[i],A[min]);//封装的swap()函数共移动元素3次 }
} 
//交换
void swap(int &a,int &b){int temp = a;a = b;b = temp;
}

8.4.2堆排序

堆

大根堆: 父结点的值大于或等于其子结点的值
小根堆: 父结点的值小于或等于其子结点的值

堆 = 一棵完全二叉树

堆排序思路：首先将存放在L[1…n]中的n个元素构建初始堆，因为堆本身的特点，所以堆顶元素就是最大值，输出堆顶元素之后，通常将堆底元素送入堆顶，此时根节点已不再满足大根堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质，再输出堆顶元素

初始堆

堆删除与调整

//建立大根堆
void BuildMaxHeap(int A[], int len){for(int i=len/2; i>0; i--)	//从后往前调整所有非终端结点HeadAdjust(A,i,len); 
} 
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k, int len){A[0]=A[k];						//A[0]暂存子树的根结点 for(int i=2*k; i<=len; i*=2){	//沿key较大的子结点向下筛选 if(i<len&&A[i]<A[i+1])i++;					//取key较大的字结点的下标 if(A[0]>=A[i])	break;		//筛选结束 else{		A[k] = A[i];			//将A[i]调整到双亲结点下 k = i;					//修改k值，以便向下继续筛选 }	}A[k] = A[0];					//被筛选结点的值放入最终位置 
} 
//完整逻辑
void HeapSort(int A[], int len){BuildMaxHeap(A,len);		//初始建堆 for(int i=len; i>1; i--){	//n-1躺的交换和建堆过程 swap(A[i],A[1]);		//把堆顶元素和堆底元素交换 HeadAjdust(A,1,i-1);	//把剩余的待排序元素整理成堆 }
}

堆的插入及调整

性能分析

8.5.1归并排序

归并：将两个或两个以上的有序表合并成一个新的有序表

//归并排序
int *B = (int *)malloc(n*sizeof(int)); //辅助数组B//A[low...mid]和A[mid+1...high]各自排序，将两个部分归并
void Merge(int A[], int low, int mid, int high){int i,j,k;for(k=low; k<=high; k++)B[k] = A[k];		//将A中所有元素复制到B中for(i=low,j=mid+1,k=i; i<=mid&&j<=high; k++){if(B[i] <= B[j])A[k] = B[i++];	//将较小值复制到A中elseA[k] = B[j++]; }//if while(j<=mid)	A[k++] = B[i++];while(j<=high) 	A[k++] = B[j++];
} void MergeSort(int A[], int low, int high){if(low<high){int mid = (low+high)/2;		//从中间划分 MergeSort(A,low,mid);		//对左半部分归并排序 MergeSort(A,mid+1,high);	//对右半部分归并排序Merge(A,low,mid,high);		//归并 }//if 
}

8.5.2基数排序

8.6.1内部排序算法比较

8.7.1外部排序基本概念

外部排序指的是大文件的排序，即待排序的记录存储在外存中，待排序的元素无法依次性装入内存，需要在内存和外存之间进行多次数据交换，达到排序整个文件的目的
减少平衡归并中外存堆笑次数的方法：增大归并路数和减少归并段个数
利用败者树增大归并路数
利用置换—选择算法进行多路平衡归并，需要构造最佳归并树

外部排序：对大文件进行排序，因为文件中的记录很多，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换。这种排序算法就称为外部排序。

8.7.2外部排序方法

外部排序通常采用归并排序算法，包括两个阶段：

根据内存缓冲区的大小，将外存上的文件分成若干长度为 l 的子文件，依次读入内存并利用内部排序算法对他们进行排序，并将排序后得到的额有序子文件重新写回万村，称这些有序子文件为归并段或串
对这些归并段进行逐趟归并，使归并段由小到大排列，直至得到整个有序文件

外部排序总时间 = 内部排序时间 + 外存信息度/写时间 + 内部归并时间

8.7.3多路平衡归并与败者树

为了使内部排序不受k的增大的影响：引入败者树

败者树：是树形选择排序的一种变体，可视为一棵完全二叉树，k个叶结点分别存放k个归并段唉归并过程中当前参加比较的元素，内部节点用来记忆左右子树中的失败者，而让胜利者继续向上比较，一直到根节点

8.7.4置换—选择算法

8.7.5最佳归并树

文件经过置换选择排序后，得到的是长度不等的初始归并段

如何组织长度不等的初始归并段的归并顺序使得I/O次数最少

特点，所以堆顶元素就是最大值，输出堆顶元素之后，通常将堆底元素送入堆顶，此时根节点已不再满足大根堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质，再输出堆顶元素

初始堆

[外链图片转存中…(img-FiVCZU10-1753781638178)]

[外链图片转存中…(img-YeeQ02y1-1753781638179)]

堆删除与调整

[外链图片转存中…(img-GUWtKPdk-1753781638179)]

//建立大根堆
void BuildMaxHeap(int A[], int len){for(int i=len/2; i>0; i--)	//从后往前调整所有非终端结点HeadAdjust(A,i,len); 
} 
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k, int len){A[0]=A[k];						//A[0]暂存子树的根结点 for(int i=2*k; i<=len; i*=2){	//沿key较大的子结点向下筛选 if(i<len&&A[i]<A[i+1])i++;					//取key较大的字结点的下标 if(A[0]>=A[i])	break;		//筛选结束 else{		A[k] = A[i];			//将A[i]调整到双亲结点下 k = i;					//修改k值，以便向下继续筛选 }	}A[k] = A[0];					//被筛选结点的值放入最终位置 
} 
//完整逻辑
void HeapSort(int A[], int len){BuildMaxHeap(A,len);		//初始建堆 for(int i=len; i>1; i--){	//n-1躺的交换和建堆过程 swap(A[i],A[1]);		//把堆顶元素和堆底元素交换 HeadAjdust(A,1,i-1);	//把剩余的待排序元素整理成堆 }
}

[外链图片转存中…(img-3irwjcCI-1753781638179)]

堆的插入及调整

[外链图片转存中…(img-PWlceYcR-1753781638179)]

性能分析

[外链图片转存中…(img-sc3YrpRF-1753781638179)]

8.5.1归并排序

归并：将两个或两个以上的有序表合并成一个新的有序表

[外链图片转存中…(img-g3AKwHp5-1753781638179)]

//归并排序
int *B = (int *)malloc(n*sizeof(int)); //辅助数组B//A[low...mid]和A[mid+1...high]各自排序，将两个部分归并
void Merge(int A[], int low, int mid, int high){int i,j,k;for(k=low; k<=high; k++)B[k] = A[k];		//将A中所有元素复制到B中for(i=low,j=mid+1,k=i; i<=mid&&j<=high; k++){if(B[i] <= B[j])A[k] = B[i++];	//将较小值复制到A中elseA[k] = B[j++]; }//if while(j<=mid)	A[k++] = B[i++];while(j<=high) 	A[k++] = B[j++];
} void MergeSort(int A[], int low, int high){if(low<high){int mid = (low+high)/2;		//从中间划分 MergeSort(A,low,mid);		//对左半部分归并排序 MergeSort(A,mid+1,high);	//对右半部分归并排序Merge(A,low,mid,high);		//归并 }//if 
}