数据结构与算法笔记

基本概念

一、数据结构

1. 其他定义

数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。 ——Sartaj Sahni 《数据结构、算法与应用》
数据结构是 ADT（Abstract Data Type，数据抽象类型）的物理实现。 ——Clifford A.Shaffer 《数据结构与算法分析》
数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。 ——中文维基百科

2. 解决问题方法的效率

跟数组的组织方式有关
跟空间的利用效率有关
跟算法的巧妙程度有关

3. 最终定义

数据对象在计算机中的组织方式
- 逻辑结构
- 物理存储结构
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法

4. 抽象数据类型（Abstract Data Type）

数据类型
- 数据对象集
- 数据集合相关联的操作集
抽象：描述数据类型的方法不依赖于具体实现
- 与存放数据的机器无关
- 与数据存储的物理结构无关
- 与实现操作的算法和编程语言均无关

只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题

二、算法

1. 定义

一个有限指令集
≥ 0 的输入
==>==0 的输出
一定在有限步骤之后终止
每一条指令必须
- 有充分明确的目标，不可以有歧义
- 计算机能处理范围内
- 描述应不依赖于任何一种计算机语言以及具体的实现手段

2. 描述算法的手段

空间复杂度 S(n)

根据算法写成的程序在执行时占用存储空间的长度
时间复杂度 T(n)

根据算法写成的程序在执行时耗费的时间的长度

3. 评价

在分析一般算法的效率时，常常关注
- 最坏情况复杂度$T_{\text {worst}}(n)$
- 平均情况复杂度 $T_{\text {avg}}(n)$
- $T_{\text {avg}}(n) \leq T_{\text {worst}}(n)$
一般情况下更多关注的是最坏情况复杂度

4. 复杂度的渐进表示法

$T(n)=O(f(n))$ 表示存在常数 $\mathrm{C}>0, n_{0}>0,$ 使得当 $n \geq n_{0}$ 时有 $T(n) \leq$$C \cdot f(n),$ 即 $O(f(n))$ 表示 $f(n)$ 是 $\mathrm{T}(\mathrm{n})$ 的某种上界
$T(n)=\Omega(g(n))$ 表示存在常数 $\mathrm{C}>0, n_{0}>0,$ 使得当 $n \geq n_{0}$ 时有 $T(n) \geq$$C \cdot g(n),$ 即 $\Omega(g(n))$ 表示 $g(n)$ 是 $\mathrm{T}(\mathrm{n})$ 的某种下界
$T(n)=\theta(h(n))$ 表示同时有 $T(n)=O(h(n))$ 和 $T(n)=\Omega(h(n)),$ 即$\theta(h(n))$ 既是上界也是下界

5. 复杂度分析小窍门

若两段算法分别有复杂度 $T_{1}(n)=O\left(f_{1}(n)\right)$ 和 $T_{2}(n)=O\left(f_{2}(n)\right),$ 则
$T_{1}(n)+T_{2}(n)=\max \left(O\left(f_{1}(n)\right), O\left(f_{2}(n)\right)\right)$
$T_{1}(n) \times T_{2}(n)=O\left(f_{1}(n) \times f_{2}(n)\right)$
若 $T(n)$ 是关于 $n$ 的 $k$ 阶多项式, 那么 $T(n)=\theta\left(n^{k}\right)$
一个 for 循环的时间复杂度等于循环次数乘以循环体代码的复杂度
if-else 结构的复杂度取决于 if 的条件判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大

线性表

1. 什么是线性表

“线性表”：由同类型数据元素构成有序序列的线性结构

表中元素个数称为线性表的长度
线性表没有元素时，称为空表
表起始位置称为表头，表结束位置称表尾

2. 线性表的抽象数据类型描述

类型名称：线性表（List）
数据对象集：线性表是 n (≥0) 个元素构成的有序序列$\left(a_{1}, a_{2}, \ldots, a_{n}\right)$
操作集：线性表 L ∈ List，整数 i 表示位置，元素 X ∈ ElementType

线性表基本操作主要有：
- List MakeEmpty()：初始化一个空线性表 L
- ElementType FindKth(int K,List L)：根据位序 K，返回相应元素
- int Find(ElementType X,List L)：在线性表 L 中查找 X 的第一次出现位置
- void Insert(ElementType X,int i,List L)：在位序 i 前插入一个新元素 X
- void Delete(int i,List L)：删除指定位序 i 的元素
- int Length(List L)：返回线性表 L 的长度 n

1. 线性表的顺序存储实现

利用数组的连续存储空间顺序存放线性表的各元素

注：顺序存储中是序号是下标，从 0 开始

#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100  // MAXSIZE 定义为 Data 数组的大小
typedef int ElementType;  // ElementType 可定义为任意类型
typedef struct LNode *List; 
struct LNode{
   ElementType Data[MAXSIZE]; 
   int Last;  // Last 定义线性表的最后一个元素的位置
};
List L;
//访问下标为 i 的元素：L->Data[i]
//线性表的长度：L->Last+1

List MakeEmpty(); //初始化顺序表 
int Find(ElementType X,List L); //查找 X 第一次出现的下标 
void Insert(ElementType X,int i,List L); //在下标为 i 的地方插入 X 
void Delete(int i,List L);   //删除下标为 i 的当前值 
ElementType FindKth(int K,List L);  //返回下标为 K 的当前值
int Length(List L);  //返回顺序表的长度 
 
//初始化 
List MakeEmpty(){
    List L;
    L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;
    return L;
}

// 按值查找 ，返回查到的第一个位置
int Find(ElementType X,List L){
    int i=0;
    while(i <= L->Last && L->Data[i] != X)  
        i++;
    if(L->Last < i)  //如果没找到，返回 -1
        return -1; 
    else    // 找到后返回下标 
        return i;
}

// 插入
void Insert(ElementType X,int i,List L){
    int j;
    if(L->Last == MAXSIZE-1){  //位置已满 
        printf("表满");
        return;
    }
    if(i < 0 || L->Last+1 < i){  //位置越界，如果将数插入 L->Data[L->Last+1]，下面都不用腾位置了 
        printf("位置不合法");
        return;
    }
    for(j=L->Last;j>=i;j--)   // 从后往前依次向后挪一个，给 a[i]腾出位置     
        L->Data[j+1] = L->Data[j];   
    L->Data[i] = X;    //新元素插入
    L->Last++;    // Last仍然指向最后元素
    return;
} 

//删除
void Delete(int i,List L){
    int j;
    if(i < 0 || L->Last <i){  //位置越界，而删除最多到 L->Data[L->Last]
        printf("L->Data[%d]不存在元素",i);
        return;
    }
    for(j=i;j<=L->Last;j++)   // 从前往后依次向前挪一个，将 a[i] 覆盖了 
        L->Data[j-1] = L->Data[j];
    L->Last--;  // Last仍然指向最后元素
    return;
}

// 按序查找
ElementType FindKth(int K,List L){
	if(K < 0 || L->Last < K){  //位置越界
        printf("L->Data[%d]不存在元素",K);
        return;
    }
    return L->Data[K];
}

//表长
int Length(List L){
	return L->Last+1;
} 

int main(){
	int i=0;
	L = MakeEmpty();
	Insert(11,0,L);
	printf("在线性表L-Data[0]插入11\n");
	Insert(25,0,L);
	printf("在线性表L-Data[0]插入25\n");
	Insert(33,0,L);
	printf("在线性表L-Data[0]插入33\n");
	Insert(77,0,L);
	printf("在线性表L-Data[0]插入77\n");
	printf("此时的线性表为："); 
	for(i=0;i<Length(L);i++)
		printf("%d ",L->Data[i]);
	printf("\n");
	printf("查找值为12的下标是：%d\n",Find(12,L));
	printf("下标为3的线性表的值是：%d\n",FindKth(3,L));
	Delete(2,L);
	printf("删除线性表中下标为2的元素\n");
	Delete(2,L);
	printf("删除线性表中下标为2的元素\n");
	printf("此时的线性表为："); 
	for(i=0;i<Length(L);i++)
		printf("%d ",L->Data[i]);
	printf("\n"); 
	return 0;
}

2. 线性表的链表存储实现

不要求逻辑上相邻的两个元素物理上也相邻，通过”链”建立起数据之间的逻辑关系

插入、删除不需要移动数据元素，只需要修改”链”

注：链表存储中序号从 1 开始

#include<stdio.h>
#include<malloc.h>
typedef int ElementType; // ElementType 可定义为任意类型
typedef struct LNode *List;
struct LNode{
	ElementType Data;   //数据域 
	List Next;   // 下一个链表的地址 
}; 
List L;

List MakeEmpty(); //初始化链表 
int Length(List L);  // 以遍历链表的方法求链表长度 
List FindKth(int K,List L);  // 按序号查找 
List Find(ElementType X,List L);  // 按值查找 
List Insert(ElementType X,int i,List L);  //将 X 插入到第 i-1(i>0) 个结点之后 
List Delete(int i,List L); // 删除第 i(i>0) 个结点 
void Print(List L); // 输出链表元素 

// 初始化链表 
List MakeEmpty(){
	List L = (List)malloc(sizeof(struct LNode));
	L = NULL;
	return L;
}

//求表长 
int Length(List L){
	List p = L;
	int len=0;
	while(p){  // 当 p 不为空 
		p = p->Next;
		len++;
	}
	return len;
} 

// 按序查找 
List FindKth(int K,List L){
	List p = L;
	int i = 1;  //从 1 开始 
	while(p && i<K){
		p = p->Next;
		i++;
	}
	if(i == K)    // 找到了 
		return p;
	else    // 未找到 
		return NULL;
} 

// 按值查找  
List Find(ElementType X,List L){
	List p = L;
	while(p && p->Data!=X)
		p = p->Next;
	// 找到了，返回 p
	// 未找到，返回 NULL，此时 p 等于 NULL 
	return p;   
} 

/* 插入
1. 用 s 指向一个新的结点
2. 用 p 指向链表的第 i-1 个结点 
3. s->Next = p->Next，将 s 的下一个结点指向 p 的下一个结点 
4. p->Next = s，将 p 的下一结点改为 s   */
List Insert(ElementType X,int i,List L){
	List p,s;
	if(i == 1){     // 新结点插入在表头 
		s = (List)malloc(sizeof(struct LNode));
		s->Data = X;
		s->Next = L;
		return s;     //插入的结点为头结点 
	}
	p = FindKth(i-1,L);   // 找到第 i-1 个结点
	if(!p){   // 第 i-1 个结点不存在 
		printf("结点错误");
		return NULL;
	}else{
		s = (List)malloc(sizeof(struct LNode));
		s->Data = X;
		s->Next = p->Next;   //将 s 的下一个结点指向 p 的下一个结点 
		p->Next = s;   // 将 p 的下一结点改为 s
		return L;
	}
}

/* 删除
1. 用 p 指向链表的第 i-1 个结点 
2. 用 s 指向要被删除的的第 i 个结点
3. p->Next = s->Next，p 指针指向 s 后面
4. free(s)，释放空间 
*/
List Delete(int i,List L){
	List p,s;
	if(i==1){   //如果要删除头结点 
		s = L;
		if(L)   // 如果不为空 
			L = L->Next;
		else
			return NULL;
		free(s);   // 释放被删除结点 
		return L; 
	}
	p = FindKth(i-1,L);    // 查找第 i-1 个结点
	if(!p || !(p->Next)){     // 第 i-1 个或第 i 个结点不存在 
		printf("结点错误");
		return NULL;
	}else{
		s = p->Next;    // s 指向第 i 个结点 
		p->Next = s->Next;  //从链表删除 
		free(s);  // 释放被删除结点 
		return L;
	}
}

// 输出链表元素 
void Print(List L){
	List t;
	int flag = 1;
	printf("当前链表为：");
	for(t = L;t;t =t->Next){
		printf("%d  ",t->Data);
		flag = 0;
	}
	if(flag)
		printf("NULL");
	printf("\n"); 
}

int main(){
	L = MakeEmpty();
	Print(L);
	L = Insert(11,1,L);
	L = Insert(25,1,L);
	L = Insert(33,2,L);
	L = Insert(77,3,L);
	Print(L);
	printf("当前链表长度为：%d\n",Length(L));
	printf("此时链表中第二个结点的值是：%d\n",FindKth(2,L)->Data);
	printf("查找22是否在该链表中：");
	if(Find(22,L))
		printf("是！\n");
	else
		printf("否！\n");
	printf("查找33是否在该链表中：");
	if(Find(33,L))
		printf("是！\n");
	else
		printf("否！\n");
	L = Delete(1,L);
	L = Delete(3,L);
	printf("----------删除后-----\n"); 
	Print(L);
	return 0;
}

堆栈

1. 什么是堆栈

堆栈（Stack）：具有一定操作约束的线性表

只在一端（栈顶，Top）做插入、删除
插入数据：入栈（Push）
删除数据：出栈（Pop）
后入先出：Last In First Out（LIFO）

2. 堆栈的抽象数据类型描述

类型名称：堆栈（Stack）
数据对象集：一个有 0 个或多个元素的有穷线性表
操作集：长度为 MaxSize 的堆栈 S ∈ Stack，堆栈元素 item ∈ ElementType

堆栈的基本操作主要有：
- Stack CreateStack(int MaxSize)：生成空堆栈，其最大长度为 MaxSize
- int IsFull(Stack S,int MaxSize)：判断堆栈 S 是否已满
- void Push(Stack S,ElementType item)：将元素 item 压入堆栈
- int IsEmpty(Stack S)：判断堆栈 S 是否为空
- ElementType Pop(Stack S)：删除并返回栈顶元素

1. 栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成

#include<stdio.h>
#include<malloc.h> 
#define MaxSize 100   // 堆栈元素的最大个数 
typedef int ElementType; // ElementType 暂时定义为 int 类型 
typedef struct SNode *Stack;
struct SNode{
	ElementType Data[MaxSize];   // 存储堆栈元素
	int Top;  // 记录栈顶元素下标 
}; 
Stack S;

Stack CreateStack();  // 初始化堆栈 
int IsFull(Stack S); // 判断堆栈是否已满 
int IsEmpty(Stack S);   // 判断堆栈是否为空 
void Push(Stack S,ElementType item);   // 入栈 
ElementType Pop(Stack S);   // 出栈 

// 初始化堆栈 
Stack CreateStack(){
	S = (Stack)malloc(sizeof(struct SNode));
	S->Top = -1;
	return S;
} 

// 是否已满 
int IsFull(Stack S){
	return (S->Top == MaxSize-1);
}

// 是否为空 
int IsEmpty(Stack S){
	return (S->Top == -1); 
} 

// 入栈 
void Push(Stack S,ElementType item){
	if(IsFull(S)){   // Top 从 0 开始 
		printf("堆栈满");
		return;
	}else{
		S->Top++;   // 栈顶元素加一 
		S->Data[S->Top] = item;   // 放进最上 
		return;
	}
}

// 出栈
ElementType Pop(Stack S){
	if(IsEmpty(S)){
		printf("堆栈空");
		return;
	}else{
		ElementType val = S->Data[S->Top];  //取出最上 
		S->Top--;  // 栈顶元素减一 
		return val;
	}
}
int main(){
	S = CreateStack();
	printf("5入栈\n");
	Push(S,5);
	printf("7入栈\n");
	Push(S,7);
	printf("66入栈\n");
	Push(S,66);
	printf("%d出栈\n",Pop(S));
	printf("%d出栈\n",Pop(S));
	return 0;
}

2. 栈的链表存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行

#include<stdio.h>
#include<malloc.h>
typedef int ElementType;
typedef struct SNode *Stack;
struct SNode{
	ElementType Data;
	Stack Next;
};


Stack CreateStack();  // 初始化链栈 
int IsEmpty(Stack S);  // 判断链栈是否为空 
void Push(Stack S,ElementType item);  // 入栈 
ElementType Pop(Stack S);  // 出栈
 

// 初始化 
Stack CreateStack(){
	Stack S;
	S = (Stack)malloc(sizeof(struct SNode));
	S->Next = NULL;
	return S;
}

// 判断是否为空 
int IsEmpty(Stack S){
	return (S->Next == NULL);
}

// 入栈
void Push(Stack S,ElementType item){
	Stack tmp;
	tmp = (Stack)malloc(sizeof(struct SNode));
	tmp->Data = item;
	// 链栈栈顶元素是链表头结点，新入栈的链表在栈顶元素后面 
	tmp->Next = S->Next;   
	S->Next = tmp;
} 

// 出栈
ElementType Pop(Stack S){
	Stack First;
	ElementType TopVal;
	if(IsEmpty(S)){
		printf("堆栈空");
		return;
	}else{
		First = S->Next;   // 出栈第一个元素在栈顶元素后面 
		S->Next = First->Next;  //把第一个元素从链栈删除 
		TopVal = First->Data;   // 取出被删除结点的值 
		free(First);  // 释放空间 
		return TopVal;
	}
} 

int main(){
	Stack S;
	S = CreateStack();
	printf("5入栈\n");
	Push(S,5);
	printf("7入栈\n");
	Push(S,7);
	printf("66入栈\n");
	Push(S,66);
	printf("%d出栈\n",Pop(S));
	printf("%d出栈\n",Pop(S));
	return 0;
}

队列

1. 什么是队列

队列（Queue）：具有一定操作约束的线性表

插入和删除操作：只能在一端（front）插入，而在另一端（rear）删除
数据插入：入队列（AddQ）
数据删除：出队列（DeleteQ）
先进先出：FIFO

2. 队列的抽象数据类型描述

类型名称：队列（Queue）
数据对象集：一个有 0 个或多个元素的有穷线性表
操作集：长度为 MaxSize 的队列 Q∈Queue，队列元素 item∈ElementType

队列的基本操作主要有：
- Queue CreateQueue(int MaxSize)：生成长度为 MaxSize 的空队列
- int IsFull(Queue Q)：判断队列 Q 是已满
- void AddQ(Queue Q,ElementType item)：将数据元素 item 插入队列 Q 中
- int IsEmpty(Queue Q)：判断队列 Q 是否为空
- ElementType DeleteQ(Queue Q)：将队头数据元素从队列中删除并返回

1. 循环队列的顺序存储实现

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量 front 以及一个记录队列尾元素位置的变量 rear 组成，其中 front 指向整个队列的头一个元素的再前一个，rear 指向的是整个队列的最后一个元素，从 rear 入队，从 front 出队，且仅使用 n-1 个数组空间

#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef int ElementType;
typedef struct QNode *Queue;
struct QNode{
	ElementType Data[MaxSize];
	int front;   // 记录队头 
	int rear;    // 记录队尾 
};

Queue CreateQueue();  // 初始化队列 
void AddQ(Queue Q,ElementType item);  //  入队
int IsFull(Queue Q); // 判断队列是否已满 
ElementType DeleteQ(Queue Q);  // 出队 
int IsEmpty(Queue Q); // 判断队列是否为空 

// 初始化 
Queue CreateQueue(){
	Queue Q;
	Q = (Queue)malloc(sizeof(struct QNode));
	Q->front = -1;
	Q->rear = -1;
	return Q;
} 

// 判断队列是否已满
int IsFull(Queue Q){
 	return ((Q->rear+1) % MaxSize == Q->front);
}

// 入队 
void AddQ(Queue Q,ElementType item){
	if(IsFull(Q)){
		printf("队列满");
		return;
	}else{ 
		Q->rear = (Q->rear+1) % MaxSize;
		Q->Data[Q->rear] = item; 
	}
}

//判断队列是否为空
int IsEmpty(Queue Q){
	return (Q->front == Q->rear);
}
 
// 出队
ElementType DeleteQ(Queue Q){
	if(IsEmpty(Q)){
		printf("队列空");
		return 0;
	}else{
		Q->front = (Q->front+1) % MaxSize;
		return Q->Data[Q->front];
	}
} 

int main(){
	Queue Q;
	Q = CreateQueue();
	AddQ(Q,3);
	printf("3入队\n");
	AddQ(Q,5);
	printf("5入队\n");
	AddQ(Q,11);
	printf("11入队\n");
	printf("%d出队\n",DeleteQ(Q));
	printf("%d出队\n",DeleteQ(Q));
	return 0;
}

2. 队列的链式存储实现

队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行，front 在链表头，rear 在链表尾，从 rear 入队，从 front 出队

#include<stdio.h>
#include<malloc.h>
typedef int ElementType;
typedef struct QNode *Queue;
struct Node{
	ElementType Data;
	struct Node *Next;
};
struct QNode{
	struct Node *rear;    // 指向队尾结点 
	struct Node *front;   // 指向队头结点 
};

Queue CreateQueue();  // 初始化队列 
void AddQ(Queue Q,ElementType item);  //  入队
ElementType DeleteQ(Queue Q);  // 出队 
int IsEmpty(Queue Q); // 判断队列是否为空 

// 初始化 
Queue CreateQueue(){
	Queue Q;
	Q = (Queue)malloc(sizeof(struct QNode));
	Q->front = NULL;
	Q->rear = NULL;
	return Q;
}

// 是否为空 
int IsEmpty(Queue Q){
	return (Q->front == NULL);
}

// 入队
void AddQ(Queue Q,ElementType item){
	struct Node *node;
	node = (struct Node *)malloc(sizeof(struct Node));
	node->Data = item;
	node->Next = NULL;
	if(Q->rear==NULL){  //此时队列空 
		Q->rear = node;
		Q->front = node;
	}else{ //不为空 
		Q->rear->Next = node;  // 将结点入队 
		Q->rear = node;   // rear 仍然保持最后 
	}
} 

// 出队
ElementType DeleteQ(Queue Q){
	struct Node *FrontCell;
	ElementType FrontElem;
	if(IsEmpty(Q)){
		printf("队列空");
		return 0;
	}
	FrontCell = Q->front;
	if(Q->front == Q->rear){ // 队列中只有一个元素 
		Q->front = Q->rear = NULL; 
	}else{
		Q->front = Q->front->Next;
	}
	FrontElem = FrontCell->Data;
	free(FrontCell);
	return FrontElem;
}

int main(){
	Queue Q;
	Q = CreateQueue();
	printf("入队5\n"); 
	AddQ(Q,5);
	printf("入队4\n"); 
	AddQ(Q,4);
	printf("入队4\n"); 
	AddQ(Q,3);
	printf("出队%d\n",DeleteQ(Q));
	printf("出队%d\n",DeleteQ(Q));
	printf("出队%d\n",DeleteQ(Q));
	printf("%d\n",DeleteQ(Q));
	return 0;
}

树

1. 树的定义

树（Tree）：n（n≥0）个结点构成的有限集合

当 n=0 时，称为空树

1. 特征

对于任一棵非空树（n＞0），它具备以下特征：

树中有个称为“根（Root）”的特殊结点，用 r 表示
其余结点可分为 m(m>0) 个互不相交的有限集$\mathrm{T}_{1}, \mathrm{T}_{2}, \ldots, \mathrm{T}_{m}$,其中每个集合本身又是一棵树，称为原来树的”子树（SubTree）”
子树是不相交的
除根结点外，每个结点有且仅有一个父结点
一棵 N 个结点的树有 N-1 条边

2. 基本术语

结点的度（Degree）：结点的子树个数
树的度：树的所有结点中最大的度数
叶结点（Leaf）：度为 0 的结点
父结点（Parent）：有子树的结点是其子树的根结点的父结点
子结点（Child）：若 A 结点是 B 结点的父结点，则称 B 结点是 A 结点的子结点，也称孩子结点
兄弟结点（Sibling）：具有同一父结点的各个结点彼此是兄弟结点
路径：从结点 $\mathrm{n}_{1}$ 到 $\mathrm{n}_{k}$ 的路径为一个结点序列$\mathrm{n}_{1}, \mathrm{n}_{2}, \ldots, \mathrm{n}_{k}$,其中 $\mathrm{n}_{i}$是$\mathrm{n}_{i}$的父结点
路径长度：路径所包含边的个数
祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点
子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙
结点的层次（Level）：规定根结点在 1 层，其他任一结点的层数是其父结点的层数加一
树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度

3. 树的表示

1. 儿子-兄弟表示法

Element 存值
FirstChild 指向第一个儿子
NextSibling 指向下一个兄弟

2. 二叉树

即度为 2 的树

Element 存值
Left 指向左子树
Right 指向右子树

二叉树其实就是儿子-兄弟表示法的链表右移 45° 得到的结果

2. 二叉树

1. 定义

二叉树 T：一个有穷的结点集合

这个集合可以为空

若不为空，则它是由根结点和称为其左子树TL_LL和右子树TR_RR的两个不相交的二叉树组成

二叉树的子树有左右顺序之分

2. 五种基本形态

3. 特殊形态

斜二叉树

只有左儿子或只有右儿子
完美二叉树（满二叉树）

除最后一层叶结点外，每个结点都有两个子结点
完全二叉树

有 n 个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为 i（1 ≤ i ≤ n）结点与满二叉树中编号为 i 结点在二叉树中位置相同

4. 重要性质

一个二叉树第 i 层的最大结点数为：$2^{i-1}, i \geq1$
深度为 k 的二叉树有最大结点总数为：$2^{k}-1, k \geq 1$
对任何非空二叉树 T，若 $\mathrm {n}_{0}$表示叶结点的个数、$\mathrm {n}_{2}$是度为 2 的非叶结点个数，那么二者满足关系 $\mathrm {n}_{0} = {n}_{2}+1$

5. 抽象数据类型定义

类型名称：二叉树
数据对象集：一个有穷的结点集合，若不为空，则由根结点和其左、右二叉子树组成
操作集：BT ∈ BinTree，Item ∈ ElementType

主要操作有：
- Boolean IsEmpty(BinTree BT)：判别 BT 是否为空
- void Traversal(BinTree BT)：遍历，按某顺序访问每个结点
- BinTree CreatBinTree()：创建一个二叉树
常用的遍历方法有：
- void PreOrderTraversal(BinTree BT)：先序——根、左子树、右子树
- void InOrderTraversal(BinTree BT)：中序——左子树、根、右子树
- void PostOrderTraversal(BinTree BT)：后序——左子树、右子树、根
- void LevelOrderTraversal(BinTree BT)：层次遍历，从上到下、从左到右

1. 顺序存储结构

按从上至下、从左到右顺序存储 n 个结点的完全二叉树的结点父子关系：

非根结点（序号 i > 1）的父结点的序号是 ⌊i/2⌋（向下取整）
结点（序号为 i）的左孩子结点的序号是 2i（若 2 i ≤ n，否则没有左孩子
结点（序号为 i）的右孩子结点的序号是 2i+1（若 2 i +1 ≤ n，否则没有右孩子

2. 链表存储

typedef struct TreeNode *BinTree;
struct TreeNode{
	Element Data;  // 存值 
	BinTree Left;    // 左儿子结点 
	BinTree Right;   // 右儿子结点 
};

二叉树的遍历

0. 树的表示

typedef struct TreeNode *BinTree;
struct TreeNode{
	int Data;  // 存值 
	BinTree Left;    // 左儿子结点 
	BinTree Right;   // 右儿子结点 
};

1. 先序遍历

遍历过程：

访问根结点
先序遍历其左子树
先序遍历其右子树

1.递归实现

void  PreOrderTraversal(BinTree BT){
	if(BT){
		printf("%d",BT->Data);  // 打印根 
		PreOrderTraversal(BT->Left);  // 进入左子树 
		PreOrderTraversal(BT->Right);  // 进入右子树 
	}
}

2. 非递归实现

void PreOrderTraversal(BinTree BT){
	BinTree T = BT;
	Stack S = CreateStack();  // 创建并初始化堆栈 S
	while(T || !IsEmpty(S)){  // 当树不为空或堆栈不空 
		while(T){     
			Push(S,T);    // 压栈，第一次遇到该结点 
			printf("%d",T->Data);  // 访问结点
			T = T->Left;   // 遍历左子树 
		}
		if(!IsEmpty(S)){  // 当堆栈不空 
			T = Pop(S);    // 出栈，第二次遇到该结点 
			T = T->Right;  // 访问右结点 
		}
	} 
}

2.中序遍历

递归过程：

中序遍历其左子树
访问根结点
中序遍历其右子树

1. 递归实现

void InOrderTraversal(BinTree BT){
	if(BT){
		InOrderTraversal(BT->Left);  // 进入左子树 
		printf("%d",BT->Data);  // 打印根 
		InOrderTraversal(BT->Right);  // 进入右子树 
	} 
}

2. 非递归实现

void InOrderTraversal(BinTree BT){
	BinTree T = BT;
	Stack S = CreateStack();  // 创建并初始化堆栈 S
	while(T || !IsEmpty(S)){  // 当树不为空或堆栈不空 
		while(T){     
			Push(S,T);    // 压栈
			T = T->Left;   // 遍历左子树 
		}
		if(!IsEmpty(S)){  // 当堆栈不空 
			T = Pop(S);    // 出栈
			printf("%d",T->Data);  // 访问结点
			T = T->Right;  // 访问右结点 
		}
	} 
}

3. 后序遍历

遍历过程：

后序遍历其左子树
后序遍历其右子树
访问根结点

1. 递归实现

void PostOrderTraversal(BinTree BT){
	if(BT){
		PostOrderTraversal(BT->Left);  // 进入左子树 
		PostOrderTraversal(BT->Right);  // 进入右子树 
		printf("%d",BT->Data);  // 打印根 
	} 
}

2. 非递归实现

void PostOrderTraversal(BinTree BT){
	BinTree T = BT;
	Stack S = CreateStack();  // 创建并初始化堆栈 S
	vector<BinTree> v;   // 创建存储树结点的动态数组
	Push(S,T);
	while(!IsEmpty(S)){  // 当树不为空或堆栈不空 
		T = Pop(S);
		v.push_back(T);  // 出栈元素进数组
		if(T->Left)
			Push(S,T->Left);
		if(T->Right)
			Push(S,T->Right);
	}
	reverse(v.begin(),v.end());  // 逆转 
	for(int i=0;i<v.size();i++)  // 输出数组元素
		printf("%d",v[i]->Data);
}

4. 总结

先序、中序和后序遍历过程：遍历过程中经过结点的路线一样，只是访问各结点的时机不同，即：

先序遍历是第一次”遇到”该结点时访问
中序遍历是第二次”遇到”该结点（此时该结点从左子树返回）时访问
后序遍历是第三次”遇到”该结点（此时该结点从右子树返回）时访问

5. 层序遍历

遍历过程：从上至下，从左至右访问所有结点

队列实现过程：

根结点入队
从队列中取出一个元素
访问该元素所指结点
若该元素所指结点的左孩子结点非空，左孩子结点入队
若该元素所指结点的右孩子结点非空，右孩子结点入队
循环 1 - 4，直到队列中为空

void LevelOrderTraversal(BinTree BT){
	queue<BinTree> q;   // 创建队列
	BinTree T;
	if(!BT)
		return;
	q.push(BT);  // BT 入队 
	while(!q.empty()){
		T = q.front();  // 访问队首元素 
		q.pop();  // 出队
		printf("%d",T->Data);
		if(T->Left)  // 如果存在左儿子结点
			q.push(T->Left);  // 入队
	 	if(T->Right)
	 		q.push(T->Right);
	}
}

6. 例子

1. 输出叶子结点

前序遍历加个没有孩子结点的约束即可

void  FindLeaves(BinTree BT){
	if(BT){
		if( !BT->Left && !BT->Right)
			printf("%d",BT->Data);  // 打印叶子结点
		FindLeaves(BT->Left);  // 进入左子树 
		FindLeaves(BT->Right);  // 进入右子树 
	}
}

2. 树的高度

当前树的高度为其子树最大高度 +1

int  GetHeight(BinTree BT){
	int hl,hr,maxh;
	if(BT){
		hl = GetHeight(BT->Left);  // 求左子树高度 
		hr = GetHeight(BT->Right);  // 求右子树高度 
		maxh = (hl>hr)?hl:hr;
		return maxh+1;  // 当前结点高度为左右子树最大的高度+1 
	}else
		return 0;
}

3. 由两种遍历序列确定二叉树

前提：有一种序列必须是中序！

方法：

根据先序（或后序）遍历序列第一个（或最后一个）结点确定根结点
根据根结点在中序序列中分割出左右两个子序列
对左子树和右子树分别递归使用同样的方法继续分解

例如：

前序：ABCDEFG
中序：CBDAFEG

先序遍历为”根左右”，则 A 是根，对应可以划分出中序中：(CBD)A(FEG)，CBD 为左子树，FEG 为右子树，再根据前序的 BCD，B 为根，划分出中序中 (C(B)D)A(FEG)，则 C D 分别是 B 的左右子树…最后可得树为：

    A
   /  \
  B    E
 / \  / \
C   D F  G

二叉搜索树

1. 定义

二叉搜索树（BST）也称二叉排序树或二叉查找树

二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：

非空左子树的所有键值小于其根结点的键值
非空右子树的所有键值大于其根结点的键值
左、右子树都是二叉搜索树

2. 特殊函数

BinTree Find(ElementType X,BinTree BST)：从二叉搜索树 BST 中查找元素 X，返回其所在结点地址
BinTree FindMin(BinTree BST)：从二叉搜索树 BST 中查找并返回最小元素所在结点的地址
BinTree FindMax(BinTree BST)：从二叉搜索树 BST 中查找并返回最大元素所在结点的地址
BinTree Insert(ElementType X,BinTree BST)：插入一个元素进 BST
BinTree Delete(ElementType X,BinTree BST)：从 BST 中删除一个元素

1. 查找

查找从根结点开始，如果树为空，返回 NULL
若搜索树不为空，则根结点键值和 X 进行比较，并进行不同处理：
1. 若 X 小于根结点键值，在左子树中继续查找
2. 若 X 大于根结点键值，在右子树中继续查找
3. 如 X 等于根节点键值，查找结束，返回指向此结点的指针

2. 查找最大和最小元素

最大元素一定是在树的最右分支的端结点上
最小元素一定是在树的最左分支的端结点上

3. 删除

删除的三种情况：

要删除的是叶结点：直接删除，并将其父结点指针置为 NULL
要删除的结点只有一个孩子结点：将其父结点的指针指向要删除结点的孩子结点
要删除的结点有左、右两棵子树：用右子树的最小元素或左子树的最大元素替代被删除结点

4. 代码实现

#include<iostream>
#include<malloc.h>
using namespace std;
typedef int ElementType;
typedef struct TreeNode *BinTree;
struct TreeNode{
	ElementType Data;
	BinTree Left;
	BinTree Right;
};

// 查找递归实现 
BinTree Find(ElementType X,BinTree BST){
	if(!BST)  // 如果根结点为空，返回 NULL 
		return NULL; 
	if(X < BST->Data) // 比根结点小，去左子树查找 
		return Find(X,BST->Left); 
	else if(BST->Data < X)  // 比根结点大，去右子树查找 
		return Find(X,BST->Right);
	else if(BST->Data == X) // 找到了 
		return BST;
}

// 查找非递归实现
BinTree IterFind(ElementType X,BinTree BST){
	while(BST){
		if(X < BST->Data)
			BST = BST->Left;
		else if(BST->Data < X)  // 比根结点大，去右子树查找 
			BST = BST->Right;
		else if(BST->Data == X) // 找到了 
			return BST;
	}
	return NULL;
} 

// 查找最小值的递归实现
BinTree FindMin(BinTree BST){
	if(!BST)    // 如果为空了，返回 NULL 
		return NULL;  
	else if(BST->Left)   // 还存在左子树，沿左分支继续查找 
		return FindMin(BST->Left);
	else  // 找到了 
		return BST;
} 

// 查找最大值的非递归实现
BinTree FindMax(BinTree BST){
	if(BST)  // 如果不空 
		while(BST->Right)   // 只要右子树还存在 
			BST = BST->Right;
	return BST;
} 

// 插入
BinTree Insert(ElementType X,BinTree BST){
	if(!BST){  // 如果为空，初始化该结点 
		BST = (BinTree)malloc(sizeof(struct TreeNode));
		BST->Data = X;
		BST->Left = NULL;
		BST->Right = NULL;
	}else{ // 不为空 
		if(X < BST->Data)  // 如果小，挂在左边 
			BST->Left = Insert(X,BST->Left);
		else if(BST->Data < X)  // 如果大，挂在右边 
			BST->Right = Insert(X,BST->Right);
		// 如果相等，什么都不用做 
	}
	return BST;
} 

// 删除
BinTree Delete(ElementType X,BinTree BST){
	BinTree tmp;
	if(!BST)
		cout<<"要删除的元素未找到";
	else if(X < BST->Data)   // X 比当前结点值小，在左子树继续查找删除 
		BST->Left = Delete(X,BST->Left);
	else if(BST->Data < X)   // X 比当前结点值大，在右子树继续查找删除 
		BST->Right = Delete(X,BST->Right);
	else{  //  找到被删除结点 
		if(BST->Left && BST->Right){  // 被删除结点有俩孩子结点 
			tmp = FindMin(BST->Right);   // 找到右子树中值最小的
			BST->Data = tmp->Data;     // 用找到的值覆盖当前结点 
			BST->Right = Delete(tmp->Data,BST->Right);    // 把前面找到的右子树最小值结点删除 
		}else{  // 被删除结点只有一个孩子结点或没有孩子结点 
			tmp = BST;
			if(!BST->Left && !BST->Right)  // 没有孩子结点 
				BST = NULL;
			else if(BST->Left && !BST->Right)  // 只有左孩子结点 
				BST = BST->Left;
			else if(!BST->Left && BST->Right)  // 只有右孩子结点 
				BST = BST->Right;
			free(tmp);
		}
	}
	return BST;
} 

// 中序遍历 
void  InOrderTraversal(BinTree BT){
	if(BT){
		InOrderTraversal(BT->Left);  // 进入左子树 
		cout<<BT->Data;  // 打印根 
		InOrderTraversal(BT->Right);  // 进入右子树 
	}
}
int main(){
	BinTree BST = NULL;
	BST = Insert(5,BST); 
	BST = Insert(7,BST); 
	BST = Insert(3,BST); 
	BST = Insert(1,BST); 
	BST = Insert(2,BST); 
	BST = Insert(4,BST); 
	BST = Insert(6,BST); 
	BST = Insert(8,BST); 
	BST = Insert(9,BST); 
	/*
			    5
			   /\
			  3  7
             /\	 /\
            1 4 6  8
			\      \
			 2      9
	*/
	cout<<"中序遍历的结果是："; 
	InOrderTraversal(BST);
	cout<<endl;
	cout<<"查找最小值是："<<FindMin(BST)->Data<<endl;
	cout<<"查找最大值是："<<FindMax(BST)->Data<<endl; 
	cout<<"查找值为3的结点左子树结点值为："<<Find(3,BST)->Left->Data<<endl;
	cout<<"查找值为7的结点右子树结点值为："<<IterFind(7,BST)->Right->Data<<endl;
	cout<<"删除值为5的结点"<<endl;
	Delete(5,BST);
	/*
			    6
			   /\
			  3  7
             /\	  \
            1 4    8
			\      \
			 2      9
	*/
	cout<<"中序遍历的结果是："; 
	InOrderTraversal(BST);
	cout<<endl;
	return 0;
}

平衡二叉树

0. 为何要使用AVL树？

二叉搜索树的搜索效率与其树的深度相关，而二叉搜索树的组成又与其插入序列相关，在极端情况下，二叉搜索树退化为一条单链（比如插入序列是 1 2 3 … n），使得搜索效率大大降低，为了避免这种情况出现，我们采用二叉平衡树对插入结点进行调整，使得树的深度尽可能小

1. 定义

平衡因子
BF(T) = $ {h}_{L}-{h}_{R}$，其中${h}_{L}$、$h_R$分别是左右子树的高度
平衡二叉树(AVL 树)
空树，或者任一结点左、右子树高度差的绝对值不超过 1，即 |BF(T)|≤1 的树

2. 平衡二叉树的调整

0. 遵循原则

从离插入结点最近的结点调整

1. RR 单旋

当”插入结点”(BR)是”被破坏平衡结点”(A)右子树的右子树时，即 RR 插入时，采用 RR 旋转调整

其基本思路是把 B 的左子树腾出来挂到 A 的右子树上，返回 B 作为当前子树的根

示意图：

AVLTree RRRotation(AVLTree A){
	AVLTree B = A->right;   // B 为 A 的右子树  
	A->right = B->left;    // B 的左子树挂在 A 的右子树上 
	B->left = A;   //  A 挂在 B 的左子树上 
	return B;  // 此时 B 为根结点了   
}
123456

2. LL 单旋

当”插入结点”(BL)是”被破坏平衡结点”(A)左子树的左子树时，即 LL 插入，采用 RR 旋转调整

其基本思路是把 B 的右子树腾出来挂到 A 的左子树上，返回 B 作为当前子树的根

示意图：

AVLTree LLRotation(AVLTree A){
	// 此时根节点是 A 
	AVLTree B = A->left;  // B 为 A 的左子树  
	A->left = B->right;   // B 的右子树挂在 A 的左子树上 
	B->right = A;     //  A 挂在 B 的右子树上 
	return B;  // 此时 B 为根结点了 
}
1234567

3. LR 双旋

当”插入结点”(CL 或者 CR)是”被破坏平衡结点”(A)左子树的右子树时，即 LR 插入，采用 LR 旋转调整

基本思想是先将 B 作为根结点进行 RR 单旋转化为 LL 插入，再将 A 作为根结点进行 LL 单旋（先 RR 再 LL）

示意图：

AVLTree LRRotation(AVLTree A){
	// 先 RR 单旋
	A->left = RRRotation(A->left);
	// 再 LL 单旋 
	return LLRotation(A);
}
123456

总结：叫 LR 双旋是从上到下看，而实际先 RR 单旋再 LL 单旋是从下往上的过程

4. RL 双旋

当”插入结点”(CL 或者 CR)是”被破坏平衡结点”(A)右子树的左子树时，即 RL 插入，采用 RL 旋转调整

基本思想是先将 B 作为根结点进行 LL 单旋转化为 RR 插入，再将 A 作为根结点进行 RR单旋（先 LL 再 RR）

示意图：

AVLTree RLRotation(AVLTree A){
	// 先 LL 单旋
	A->right = LLRotation(A->right);
	// 再 RR 单旋 
	return RRRotation(A); 
}
123456

总结：叫 RL 双旋是从上到下看，而实际先 LL 单旋再 RR 单旋是从下往上的过程

堆

1. 什么是堆

优先队列（priority Queue）：特殊的”队列”，取出元素的顺序是依照元素的优先级（关键字）大小，而不是元素进入队列的先后顺序，以完全二叉树存储

两个特性

结构性：用数组表示的完全二叉树
有序性：任一结点的关键字是其子树所有结点的最大值（或最小值）
- “最大堆(MaxHeap)”，也称”大顶堆”：最大值
- “最小堆(MinHeap)”，也称”小顶堆”：最小值

2. 堆的抽象数据类型描述

数据名称：最大堆（MaxHeap）
数据对象集：完全二叉树，每个结点的元素值不小于其子结点的元素值
操作集：最大堆 H ∈ MaxHeap，元素 item ∈ ElementType

主要操作有：
- MaxHeap Create(int MaxSize)：创建一个空的最大堆
- Boolean IsFull(MaxHeap H)：判断最大堆 H 是否已满
- Boolean Insert(MaxHeap H,ElementType item)：将元素 item 插入最大堆 H
- Boolean IsEmpty(MaxHeap H)：判断最大堆 H 是否为空
- ElementType DeleteMax(MaxHeap H)：返回 H 中最大元素（高优先级）

1. 插入

插入数组最后一个位置，再从下往上找合适地方

2. 删除

删除根结点，将数组最后一个位置的数取到根结点，从上往下找合适地方

#include<stdio.h>
#include<malloc.h>
#define MaxData 100000
#define ERROR -1
typedef int ElementType;
typedef struct HeapStruct *MaxHeap;
struct HeapStruct{
	ElementType *Elements;   // 存储堆元素的数组 
	int Size;      // 堆的当前元素个数 
	int Capacity;  // 堆的最大容量 
};

MaxHeap Create(int MaxSize);  // 建堆 
bool IsFull(MaxHeap H);    // 判断堆是否满
bool Insert(MaxHeap H,ElementType item);   // 插入元素
bool IsEmpty(MaxHeap H);    //  判断堆是否为空
ElementType DeleteMax(MaxHeap H);  // 删除并返回堆中最大元素
void LevelOrderTraversal(MaxHeap H);  // 层序遍历 

// 建堆 
MaxHeap Create(int MaxSize){
	MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapStruct));
	// Elements[0] 作为哨兵，堆元素从  Elements[1] 开始存放 
	H->Elements = (ElementType *)malloc((MaxSize+1) * sizeof(ElementType));
	H->Size = 0;
	H->Capacity = MaxSize;
	// "哨兵"大于堆中所有可能的值 
	H->Elements[0] = MaxData;
	return H;
} 

// 插入，从完全二叉树的最后一个位置插入 
bool Insert(MaxHeap H,ElementType item){
	if(IsFull(H)){
		printf("堆已满，无法插入！\n");
		return false;
	}
	int i = ++H->Size;  // 指向堆中最后一个位置 
	for(;H->Elements[i/2] < item;i/=2)    // 向上找比 item 大的结点 
		H->Elements[i] = H->Elements[i/2];  //  向下赋值 
	H->Elements[i] = item;  // 找到了，把 item 值放进去 
	return true;
}

// 删除，从根结点删除 
ElementType DeleteMax(MaxHeap H){
	int parent,child;
	ElementType Max,tmp;
	if(IsEmpty(H)){
		printf("堆为空，无法删除！\n");
		return ERROR;
	}
	Max = H->Elements[1];  // 拿到最大值
	tmp = H->Elements[H->Size--];  // 拿到完全二叉树最后一个值 
	// 判别条件：parent 是否有左孩子结点 
	for(parent=1;parent*2<=H->Size;parent=child){
		// 左右孩子结点中找较大的值 
		child = 2 * parent;  // 左孩子结点 
		// child!=H->Size 表示 child 不为当前最后一个结点，即 parent 有右孩子结点 
		if((child!=H->Size) &&(H->Elements[child] < H->Elements[child+1]))
			child++;  
		// 给 tmp 找个合适的位置 
		// 如果当前左右孩子结点比 tmp 都小，说明 tmp 位置已经合适 
		if(H->Elements[child] <= tmp)
			break;
		else    // 否则把较大的孩子结点提上来，自己继续下去找 
			H->Elements[parent] = H->Elements[child];
	}
	H->Elements[parent] = tmp;  // 在合适的位置把 tmp 放进去 
	return Max;
} 

// 判断是否已经满 
bool IsFull(MaxHeap H){
	return (H->Size == H->Capacity);
}

// 判断是否为空
bool IsEmpty(MaxHeap H){
	return !H->Size;
}

// 层序遍历
void LevelOrderTraversal(MaxHeap H){
	int i;
	printf("层序遍历的结果是：");
	for(i = 1;i<=H->Size;i++){
		printf("%d ",H->Elements[i]);
	} 
	printf("\n"); 
} 

int main(){
	MaxHeap H;
	int MaxSize = 100;
	H = Create(MaxSize);
	Insert(H,55);
	Insert(H,66);
	Insert(H,44);
	Insert(H,33);
	Insert(H,11);
	Insert(H,22);
	Insert(H,88);
	Insert(H,99);
	/*
		 99
		/  \
	   88  66
	  / \  / \
	 55 11 22 44
	/ 
   33	  
	*/
	LevelOrderTraversal(H);
	DeleteMax(H);
	LevelOrderTraversal(H);
	DeleteMax(H);
	LevelOrderTraversal(H);
	DeleteMax(H);
	LevelOrderTraversal(H);
	DeleteMax(H);
	LevelOrderTraversal(H);
	return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124

3. 最小堆的建立

不是初始化堆啦！
堆的建立：将已经存在的 N 个元素按最小堆的要求存放在一个一维数组中

0. 注意

对于一组相同数据，插入建堆和调整建堆建出来的堆也许不一样

1. 插入建堆

通过插入，将 N 个元素一个一个相继插入到一个初始为空的堆中去，其时间代价最大是 O(NlogN)O(N logN)O(NlogN)（每次插入是 logN，总共 N 次）

#include<iostream>
#include<malloc.h>
const int MinData = -100000;  // 哨兵值
const int MaxSize = 1005;   // 最大个数 
using namespace std;
typedef struct HeapStruct *Heap;
struct HeapStruct{
	int *data;   // 存值的数组 
	int size;   // 当前元素个数 
	int capacity;  // 最大容量 
};

// 初始化堆
#include<iostream>
#include<malloc.h>
const int MinData = -100000;  // 哨兵值
const int MaxSize = 1005;   // 最大个数 
using namespace std;
typedef struct HeapStruct *Heap;
struct HeapStruct{
	int *data;   // 存值的数组 
	int size;   // 当前元素个数 
	int capacity;  // 最大容量 
};

// 初始化堆
Heap Create(){
	Heap H;
	H = (Heap)malloc(sizeof(struct HeapStruct));
	H->data = (int *)malloc(sizeof(int) * (MaxSize+1));
	H->size = 0;
	H->capacity = MaxSize;
	H->data[0] = MinData;
	return H;
} 

// 插入
void Insert(Heap H,int x){
	int i = ++H->size;  // 指向数组最后一个 
	for(;H->data[i/2]>x;i/=2)
		H->data[i] = H->data[i/2];
	H->data[i] = x;
} 

// 遍历 
void bl(Heap H){
	for(int i=1;i<=H->size;i++)
		cout<<H->data[i]<<" ";
}

int main(){
	Heap H;
	H = Create();
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int t;
		cin>>t;
		Insert(H,t);
	}
	bl(H);
	return 0;
} 
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263

2. 调整建堆

将 N 个元素直接按顺序存入，再调整各结点的位置（简单说来，对于从最后一个有孩子结点的结点来说，其本身结点和孩子结点共同构成”子最小堆”，借助前面删除的想法，对每个”子最小堆”排序，当排序完成，整个最小堆也建立成功），时间代价是 O(n)O(n)O(n)

#include<iostream>
#include<malloc.h>
const int MinData = -100000;  // 哨兵值
const int MaxSize = 1005;   // 最大个数 
using namespace std;
typedef struct HeapStruct *Heap;
struct HeapStruct{
	int *data;   // 存值的数组 
	int size;   // 当前元素个数 
	int capacity;  // 最大容量 
};

// 初始化堆
Heap Create(){
	Heap H;
	H = (Heap)malloc(sizeof(struct HeapStruct));
	H->data = (int *)malloc(sizeof(int) * (MaxSize+1));
	H->size = 0;
	H->capacity = MaxSize;
	H->data[0] = MinData;
	return H;
} 

// 排序，类似堆的"删除操作" 
void sort(Heap H,int i){
	int child,parent;
	int tmp = H->data[i];  // 拿到当前"根结点的值" 
	for(parent = i;parent*2<=H->size;parent = child){
		child = 2 * parent;
		if((child!=H->size) && (H->data[child+1] < H->data[child]))
			child++;
		if(H->data[child] >= tmp)
			break;
		else
			H->data[parent] = H->data[child]; 
	}
	H->data[parent] = tmp;
}
// 调整
void adjust(Heap H){
	int i= H->size/2;
	for(;i>0;i--){
		// 以每个有孩子结点的结点作为根结点，对其子树进行堆排序 
		sort(H,i);
	}
} 

// 遍历 
void bl(Heap H){
	for(int i=1;i<=H->size;i++){
		cout<<H->data[i]<<" ";
	}
	cout<<endl;
}


int main(){
	Heap H;
	H = Create();
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>H->data[++H->size];
	adjust(H);
	bl(H); 
	return 0;
}

哈夫曼树

1. 定义

带权路径长度（WPL）：设二叉树有 nnn 个叶子结点，每个叶子结点带有权值 wkw_kw**k，从根结点到每个叶子结点的长度为 lkl_kl**k，则每个叶子结点的带权路径长度之和就是：WPL = ∑nk=1wklk\sum_{k=1}^{n}w_kl_k∑k=1nwklk

最优二叉树或哈夫曼树：WPL 最小的二叉树

2. 哈夫曼树的构造

每次把权值最小的两颗二叉树合并

3. 哈夫曼树的特点

没有度为 1 的结点
n 个叶结点的哈夫曼树共有 2n-1 个结点
哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树
对同一组权值，可能存在不同构的多棵哈夫曼树

4. 最小堆实现哈夫曼树

刚开始挺懵逼，堆里面怎么还出哈夫曼树了呢…看姥姥留言堆里本来就是放东西的，既然可以放数…那为什么不能放树，醍醐灌顶

#include<iostream>
#include<malloc.h>
#define MaxSize 1000
#define MinData -1000 
int A[] = {1,3,5,8};  // 预先定义好一组权值 
int A_length = 4;  // 定义其长度 
typedef struct HeapStruct *MinHeap;   
typedef struct TreeNode *HuffmanTree;
struct HeapStruct{  // 存放哈夫曼树的堆 
	HuffmanTree *data;   // 存值的数组  
	int size;   // 堆的当前大小  
	int capacity; // 最大容量	
};
struct TreeNode{ // 哈夫曼树 
	int weight;  //权值
	HuffmanTree Left;  // 左子树 
	HuffmanTree right; // 右子树 
}; 
using namespace std;

MinHeap create(); // 初始化堆
HuffmanTree Create(); // 初始化哈夫曼树 
void sort(MinHeap H,int i); // 调整子最小堆 
void adjust(MinHeap H); // 调整最小堆 
void BuildMinHeap(MinHeap H);  // 建堆 
HuffmanTree Delete(MinHeap H); // 删除最小堆元素 
void Insert(MinHeap H,HuffmanTree Huff);  // 插入最小堆元素 
void PreOrderTraversal(HuffmanTree Huff); // 先序遍历 
HuffmanTree Huffman(MinHeap H); // 哈夫曼树的构建 

// 初始化堆
MinHeap create(){
	MinHeap H;
	HuffmanTree Huff;
	H = (MinHeap)malloc(sizeof(struct HeapStruct));
	H->data = (HuffmanTree *)malloc(sizeof(struct TreeNode) * (MaxSize+1));
	H->capacity = MaxSize;
	H->size = 0;
	// 给堆置哨兵 
	Huff = Create();
	Huff->weight = MinData;
	H->data[0] = Huff;
	return H;
} 

// 初始化哈夫曼树 
HuffmanTree Create(){
	HuffmanTree Huff;
	Huff = (HuffmanTree)malloc(sizeof(struct TreeNode));
	Huff->weight = 0;
	Huff->Left = NULL;
	Huff->right = NULL;
	return Huff;
}

// 调整子最小堆 
void sort(MinHeap H,int i){
	int parent,child;
	int tmp = H->data[i]->weight; // 取出当前"根结点"值
	for(parent=i;parent*2<=H->size;parent = child){
		child = 2 * parent;
		if((child!=H->size) && (H->data[child+1]->weight < H->data[child]->weight))
			child++;
		if(H->data[child]->weight >= tmp)
			break;
		else
			H->data[parent] = H->data[child];
	} 
	H->data[parent]->weight = tmp;
}

// 调整最小堆 
void adjust(MinHeap H){
	for(int i =H->size/2;i>0;i--)
		sort(H,i);// 每个"子最小堆"调整 
}

// 建堆 
void BuildMinHeap(MinHeap H){
	// 将权值读入堆中
	HuffmanTree Huff;  
	for(int i=0;i<A_length;i++){
		Huff = Create();
		Huff->weight = A[i];
		H->data[++H->size] = Huff;
	}
	// 调整堆 
	adjust(H);
}


// 删除最小堆元素
HuffmanTree Delete(MinHeap H){
	int parent,child;
	HuffmanTree T = H->data[1];  // 取出根结点的哈夫曼树 
	HuffmanTree tmp = H->data[H->size--]; // 取出最后一个结点哈夫曼树的权值 
	for(parent=1;parent*2<=H->size;parent = child){
		child = 2 * parent;
		if((child!=H->size) && (H->data[child+1]->weight < H->data[child]->weight))
			child++;
		if(H->data[child]->weight >= tmp->weight)
			break;
		else
			H->data[parent] = H->data[child];
	} 
	H->data[parent] = tmp;
	// 构造一个 HuffmanTree 结点，附上刚才取出来的权值，返回该结点 
	return T;
}

// 插入一个哈夫曼树
void Insert(MinHeap H,HuffmanTree Huff){
	int weight = Huff->weight; // 取出权值
	int i = ++H->size;
	for(;H->data[i/2]->weight > weight;i/=2)
		H->data[i] = H->data[i/2];
	H->data[i] = Huff;
} 

//遍历 
void PreOrderTraversal(HuffmanTree Huff){
	if(Huff){
		cout<<Huff->weight<<" ";
		PreOrderTraversal(Huff->Left);
		PreOrderTraversal(Huff->right);
	}
}

// 哈夫曼树的构造 
HuffmanTree Huffman(MinHeap H){
	HuffmanTree T;
	BuildMinHeap(H); // 建堆 
	int times = H->size;
	// 做 times-1 次合并 
	for(int i=1;i<times;i++){
		T = (HuffmanTree)malloc(sizeof(struct TreeNode));
		T->Left = Delete(H);   // 从堆中删除一个结点，作为新 T 的左子结点 
		T->right = Delete(H);  // 从堆中删除一个结点，作为新 T 的右子结点 
		T->weight = T->Left->weight + T->right->weight; // 重新计算权值 
		Insert(H,T);  // 再加进堆中 
	}
	T = Delete(H);
	return T;
} 



int main(){
	MinHeap H;
	HuffmanTree Huff; 
	H = create();
	Huff = Huffman(H); 
	PreOrderTraversal(Huff);
	return 0;
}

并查集

1. 数组存储的基础实现

此时并查集用一个结构体存储，data 存值（下标+1），parent 存父结点下标
查找操作中先线性查找到需要找到的值，再循环查找其根结点
并操作先找到两合并数组的树根，如果不相等，把一棵树挂到另一棵树根下

#include<iostream>
#include<cstring>
#define MaxSize 1000
typedef int ElementType;
typedef struct{
	ElementType Data; // 存值
	int parent;  // 指向父结点 
}SetType;
using namespace std;

// 查找 
int Find(SetType s[],ElementType x){
	int i;  
	// 找到数组中该值对应的下标 
	for(i=0;i<MaxSize && s[i].Data!=x;i++);
	if(MaxSize <= i) // 如果没有找到，返回 -1 
		return -1;
	// 找到该结点的根结点 
	for(;s[i].parent >= 0;i = s[i].parent); 
	return i; // 返回根结点在数组 s 中的下标 
}

// 并 
void Union(SetType s[],ElementType x1,ElementType x2){
	int root1 = Find(s,x1);  // 找到 x1 的根结点下标 
	int root2 = Find(s,x2);  // 找到 x2 的根结点下标 
	// 如果根结点的下标不同，说明不是一个集合
	if(root1 != root2){   
		s[root1].parent = root2;   // 把 x1 挂到 x2 的集合 
	}
}

int main(){
	SetType s[MaxSize];
	// 初始化数组，父结点全部指向 -1 
	for(int i=0;i<MaxSize;i++){
		s[i].Data = i+1;
		s[i].parent = -1;
	}
	cout<<Find(s,5)<<endl;
	Union(s,3,5);
	cout<<Find(s,4)<<endl;
	cout<<Find(s,3)<<endl;
	Union(s,1,3);
	Union(s,2,4);
	Union(s,8,6);
	cout<<Find(s,6)<<endl;
	cout<<Find(s,8)<<endl;
	return 0;
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950

2. 优化存储结构

观察上面的结构体，其实值和数组下标差一，那可以直接把值 1 ~ n 映射为下标的 0 ~ n-1
查找操作直接去找其父结点
并操作直接把一棵树挂另一棵树上去

#include<cstdio>
#include<iostream>
#define MaxSize 10005
typedef int SetType; 
using namespace std;
// 初始化 
void Init(SetType s[]){
	for(int i=0;i<MaxSize;i++)
		s[i] = -1;
}

// 查找 
int Find(SetType s[],int x){
	// 直接去找父结点 
	for(;s[x]>=0;x = s[x]); 
	return x;
} 

// 并
void Union(SetType s[],int x1,int x2){
	// 直接合并 
	s[x1] = x2;
} 

int main(){
	// 此时数组下标既做下标又存值，数组值存父结点下标 
	SetType s[MaxSize];
	Init(s);
	cout<<Find(s,5)<<endl;
	Union(s,3,5);
	cout<<Find(s,4)<<endl;
	cout<<Find(s,3)<<endl;
	Union(s,1,3);
	Union(s,2,4);
	Union(s,8,6);
	cout<<Find(s,6)<<endl;
	cout<<Find(s,8)<<endl;
	return 0;
}

3. 按秩归并优化 Union

当多次并操作时，其中一个操作数固定，另一个操作数一直递增或一直递减时，树会退化成单链表

1. 根据树高归并

一种解决办法是每次将 “矮” 的树挂到 “高”树上去
树高信息存储在根结点的数组值中（之前根结点的数组值都存的 -1，现在存 -树高）
这样当”矮”树挂到”高”树上，树的高度不会增加，只有当两棵树一样高，高度才+1

// 并，假设此时 x1 x2 已经分别是根
void Union(SetType s[],int x1,int x2){
	// x1 更高，负数啊！ 
	if(s[x1] < s[x2]){
		s[x2] = x1;
	}else{
		// 树高相等 
		if(s[x1] == s[x2])
		   s[x2]--;  // 树高 +1 ，是负数 
		s[x1] = x2;
	}
} 
123456789101112

2. 根据规模归并

另一种解决办法是规模小的树挂到规模更高的树上去
规模信息存储在根结点的数组值中（之前根结点的数组值都存的 -1，现在存 -元素个数）
这样当小树挂到大树上，只有较少的树会高一层

// 并，假设此时 x1 x2 已经分别是根
void Union(SetType s[],int x1,int x2){
	// x1 规模更大，负数啊！ 
	if(s[x1] < s[x2]){
		s[x1] += s[x2];    //  两树合并，规模相加 
		s[x2] = x1;   // x2 挂到 x1 上 
	}else{
		s[x2] += s[x1];   //  两树合并，规模相加 
		s[x1] = x2;
	}
} 

123456789101112

4. 路径压缩优化 Find

查找不可避免的越查越深，路径压缩可以把待查找结点与根结点之间的一系列结点的上一结点都变为根结点，即当查找 D 后：

// 查找 
int Find(SetType s[],int x){
	if(s[x] < 0)  // 本身已经是根 
		return x;
	else  // 1. 找到根  2. 把根变成 x 的父结点  3.再返回根 
		return s[x] = Find(s,s[x]);
}

图

图的定义

1. 什么是图

表示”多对多”的关系
包含
- 一组顶点：通常用 V（Vertex）表示顶点集合
- 一组边：通常用 E（Edge）表示边的集合
  - 边是顶点对：（v,w）∈ E，其中 v,w ∈ V v—w
  - 有向边表示从 v 指向 w 的边（单行线） v→w
  - 不考虑重边和自回路

2. 常见术语

无向图：图中所有的边无所谓方向
有向图：图中的边可能是双向，也可能是单向的，方向是很重要的
权值：给图中每条边赋予的值，可能有各种各样的现实意义
网络：带权值的图
邻接点：有边直接相连的顶点
出度：从某顶点发出的边数
入度：指向某顶点的边数
稀疏图：顶点很多而边很少的图
稠密图：顶点多边也多的图
完全图：对于给定的一组顶点，顶点间都存在边

3. 抽象数据类型定义

类型名称：图（Graph）
数据对象集：G（V，E）由一个非空的有限顶点集合 V 和一个有限边集合 E 组成
操作集：对于任意图 G ∈ Graph，以及 v ∈ V，e ∈ E

主要操作有：
- Graph Crate()：建立并返回空图
- Graph InsertVertex(Graph G,Vertex v)：将 v 插入 G
- Graph InsertEdge(Graph G,Edge e)：将 e 插入 G
- void DFS(Graph G,Vertex v)：从顶点 v 出发深度优先遍历图 G
- void BFS(Graph G,Vertex v)：从顶点 v 出发宽度优先遍历图 G

1. 邻接矩阵表示

邻接矩阵$G[N][N]$——N 个顶点从 0 到 N-1 编号
$\begin{equation}G[i][j]=\left\{\begin{array}{ll} 1 & \text { 若 }<v_{i}, v_{j}>\text { 是 } G \text { 中的边 } \\ 0 & \text { 否则 } \end{array}\right.\end{equation}$
特征：
- 对角线元素全 0
- 关于对角线对称
优点：
- 直观、简单、好理解
- 方便检查任意一对顶点间是否存在边
- 方便找任一顶点的所有邻接点
- 方便计算任一顶点的度
  - 无向图：对应行（或列）非 0 元素的个数
  - 有向图：对应行非 0 元素的个数是出度；对应列非 0 元素的个数是入度
缺点：
- 浪费空间——存稀疏图
- 浪费时间——统计稀疏图的边

#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 100
typedef int weightType;
typedef int Vertex;
typedef int DataType;
typedef struct GNode *ptrToGNode;
struct GNode{   // 图 
	int Nv;   // 顶点数 
	int Ne;   // 边数
	weightType G[MaxVertexNum][MaxVertexNum];
	DataType Data[MaxVertexNum]; // 存顶点的数据 
}; 
typedef ptrToGNode MGraph;
typedef struct ENode *ptrToENode;
struct ENode{  // 边 
	Vertex V1,V2;    // 有向边<V1,V2> 
	weightType Weight;  // 权重 
};
typedef ptrToENode Edge;

// 初始化图 
MGraph Create(int VertexNum){
	Vertex v,w;
	MGraph Graph;
	
	Graph = (MGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	
	for(v=0;v<VertexNum;v++)
		for(w=0;w<VertexNum;w++)
			Graph->G[v][w] = 0;
	return Graph;
}

// 插入边 
MGraph Insert(MGraph Graph,Edge E){
	
	// 插入边 <V1,V2>
	Graph->G[E->V1][E->V2] = E->Weight;
	
	// 如果是无向图，还需要插入边 <V2,V1>
	Graph->G[E->V2][E->V1] = E->Weight;
	
} 

// 建图 
MGraph BuildGraph(){
	MGraph Graph;
	Edge E;
	Vertex V;
	int Nv,i;
	scanf("%d",&Nv);   // 读入顶点数 
	Graph = Create(Nv);
	scanf("%d",&(Graph->Ne));  // 读入边数 
	if(Graph->Ne != 0){   
		E = (Edge)malloc(sizeof(struct ENode));
		for(i=0;i<Graph->Ne;i++){
			scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);  // 读入每个边的数据 
			Insert(Graph,E);
		}
	}
	return Graph;
}

// 遍历图
void print(MGraph Graph){
	Vertex v,w;
	for(v=0;v<Graph->Nv;v++){
		for(w=0;w<Graph->Nv;w++)
			printf("%d ",Graph->G[v][w]);
		printf("\n");
	}
} 

int main(){
	MGraph Graph;
	Graph = BuildGraph();
	print(Graph);
	return 0;
}

简洁版

#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
int G[MAXN][MAXN],Nv,Ne;

void BuildGraph(){
	int i,j,v1,v2,w;
	
	scanf("%d",&Nv);
	// 初始化图 
	for(i=0;i<Nv;i++) 
		for(j=0;j<Nv;j++)
			G[i][j] = 0;
	scanf("%d",&Ne);
	// 插入边 
	for(i=0;i<Ne;i++){
		scanf("%d %d %d",&v1,&v2,&w);
		G[v1][v2] = w;
		G[v2][v1] = w;
	}
}


// 遍历图
void print(){
	int i,j;
	for(i=0;i<Nv;i++){
		for(j=0;j<Nv;j++)
			printf("%d ",G[i][j]);
		printf("\n");
	}
} 

int main(){
	BuildGraph();
	print();
	return 0;
}

2. 邻接表表示

邻接表：G[N] 为指针数组，对应矩阵每行一个链表，只存非 0 元素
特点：
- 方便找任一顶点的所有邻接顶点
- 节省稀疏图的空间
  - 需要 N 个头指针 + 2E 个结点（每个结点至少 2 个域）
- 对于是否方便计算任一顶点的度
  - 无向图：方便
  - 有向图：只能计算出度
- 不方便检查任意一对顶点间是否存在边

#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 100
typedef int Vertex; 
typedef int DataType; 
typedef int weightType;  

typedef struct ENode *ptrToENode;
struct ENode{  // 边 
	Vertex V1,V2;    // 有向边<V1,V2> 
	weightType Weight;  // 权重 
};
typedef ptrToENode Edge;

typedef struct AdjVNode *ptrToAdjVNode;
struct AdjVNode{  // 邻接表内元素 
	Vertex AdjV;  // 邻接点下标 
	weightType Weight;  // 权值 
	ptrToAdjVNode Next;  // 下一个 
};

typedef struct VNode{  // 邻接表头 
	ptrToAdjVNode FirstEdge;  // 存每个顶点指针
	DataType Data;  // 顶点数据 
}AdjList[MaxVertexNum];

typedef struct GNode *ptrToGNode;
struct GNode{  // 图 
	int Nv;  // 顶点
	int Ne;  // 边数 
	AdjList G; // 邻接表 
}; 
typedef ptrToGNode LGraph;

// 初始化 
LGraph create(int VertexNum){
	Vertex v,w;
	LGraph Graph;
	
	Graph = (LGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;  // 初始化边
	Graph->Ne = 0;   // 初始化点
	
	// 每条边的 FirstEdge 指向 NULL 
	for(v=0;v<Graph->Nv;v++)
		Graph->G[v].FirstEdge = NULL;
	return Graph;
}

// 插入一条边到邻接表的顶点指针之后 
void InsertEdge(LGraph Graph,Edge E){
	ptrToAdjVNode newNode; 
	
	/**************** 插入边<V1,V2> ******************/ 
	// 为 V2 建立新的结点 
	newNode = (ptrToAdjVNode)malloc(sizeof(struct AdjVNode));
	newNode->AdjV = E->V2;
	newNode->Weight = E->Weight;
	
	// 将 V2 插入到邻接表头 
	newNode->Next = Graph->G[E->V1].FirstEdge;
	Graph->G[E->V1].FirstEdge = newNode;
	
	/*************** 若为无向图，插入边<V2,V1> *************/ 
	newNode = (ptrToAdjVNode)malloc(sizeof(struct AdjVNode));
	newNode->AdjV = E->V1;
	newNode->Weight = E->Weight;
	
	newNode->Next = Graph->G[E->V2].FirstEdge;
	Graph->G[E->V2].FirstEdge = newNode;
} 

// 建图
LGraph BuildGraph(){
	LGraph Graph;
	Edge E;
	Vertex V;
	int Nv,i;
	scanf("%d",&Nv);
	Graph = create(Nv);
	scanf("%d",&(Graph->Ne));
	if(Graph->Ne != 0){
		for(i=0;i<Graph->Ne;i++){
			E = (Edge)malloc(sizeof(struct ENode));
			scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
			InsertEdge(Graph,E);
		}
	}
	return Graph;
} 

// 打印 
void print(LGraph Graph){
	Vertex v;
	ptrToAdjVNode tmp;
	for(v=0;v<Graph->Nv;v++){
		tmp = Graph->G[v].FirstEdge;
		printf("%d ",v);
		while(tmp){
			printf("%d ",tmp->AdjV);
			tmp = tmp->Next;
		}
		printf("\n");
	}
}

int main(){
	LGraph Graph;
	Graph = BuildGraph();
	print(Graph);
	return 0;
}

简化版

#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 100
typedef struct AdjVNode *AdjList;
struct AdjVNode{
	int weight;  // 权值 
  	int adjv;   // 下标 
	AdjList next;  // 其后一个 
};
AdjList Graph[MaxVertexNum];
int Ne,Nv;

// 建图
void BuildGraph(){
	int i;
	int v1,v2,w;
	AdjList NewNode;
	scanf("%d",&Nv);
	for(i=0;i<Nv;i++){
		Graph[i] = (AdjList)malloc(sizeof(struct AdjVNode));
		Graph[i]->adjv = i;
		Graph[i]->next = NULL;
	}
	scanf("%d",&Ne);
	for(i=0;i<Ne;i++){
		scanf("%d %d %d",&v1,&v2,&w);
		NewNode = (AdjList)malloc(sizeof(struct AdjVNode));
		NewNode->adjv = v1;
		NewNode->weight = w;
		
		NewNode->next = Graph[v2]->next;
		Graph[v2]->next = NewNode;
		
		NewNode = (AdjList)malloc(sizeof(struct AdjVNode));
		NewNode->adjv = v2;
		NewNode->weight = w;
		
		NewNode->next = Graph[v1]->next;
		Graph[v1]->next = NewNode;
	}
} 

void print(){
	AdjList tmp;
	int i;
	for(i=0;i<Nv;i++){
		tmp = Graph[i];
		while(tmp){
			printf("%d ",tmp->adjv);
			tmp = tmp->next;
		}
		printf("\n");
	}
}

int main(){
	
	BuildGraph();
	print();
	return 0;
}

图的遍历

1. DFS

深度优先搜索（Depth First Search)，类似于树的先序遍历

void DFS ( Vertex V ){
    visited[ V ] = true;
    for ( V 的每个邻接点 W )
        if( !visited[ W ])
            DFS( W );
}
123456

若有 N 个顶点、E 条边，时间复杂度是

用邻接表存储，O(N + E)
用邻接矩阵存储，O(N2^22)

2. BFS

广度优先搜索（Breadth First Search)，相当于树的层序遍历

void BFS( Vertex V ){
    queue<Vertex> q;
    visited[V] = true;
    q.push(V);
    while(!q.empty()){
        V = q.front(); q.pop();
        for( V 的每个邻接点 W ){
        	if( !visited[ W ]){
            	visited[W] = true;s
            	q.push(W);
            }
        }
    }
}

若有 N 个顶点、E 条边，时间复杂度是

用邻接表存储，O(N + E)
用邻接矩阵存储，$O(n^{2})$

最短路径问题

1. 概述

1. 抽象

在网络（带权图）中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径

这条路径就是两点之间的最短路径（ShorttestPath）
第一个顶点为源点（Source）
最后一个顶点为终点（Destination）

2. 分类

单源

最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
- （有向）无权图
- （有向）有权图
多源最短路径问题：求任意两顶点间的最短路径

2. 无权图的单源最短路算法

按照递增（非递减）的顺序找出到各个顶点的最短路

void Unweighted( Vertex s){
    queue<Vertex> q;
    q.push(s);
    wile(!q.empty()){
        v = q.front(); q.pop();
        for( V 的每个临界点 W){
            dist[W] = dist[v] + 1; // 当前距离上一距离 + 1
            path[W] = v;  // s 到 w 的必经顶点就是前一个顶点 v
            q.push(W);
        }
    }
}

3. 有权图的单源最短路算法

Dijkstra 算法

令 S = {源点s + 已经确定了最短路径的顶点 $v_i$}
对任一未收录的顶点 v，定义 dist[v] 为 s 到 v 的最短路径长度，但该路径仅经过 S 中的顶点。即路径 {s→($v_i$∈S)→v} 的最小长度
若路径是按照递增（非递减）的顺序生成的，则
- 真正的最短路必须只经过 S 中的顶点
- 每次从未收录的顶点中选一个 dist 最小的收录
- 增加一个 v 进入 S，可能影响另外一个 w 的 dist 值
  - dist[w] = min{dist[w],dist[v] + 的权重}

void Dijkstra( Vertex s ){
    while(1){
        V = 未收录顶点中dist最小值;
        if( 这样的V不存在 )
            break;
        collected[V] = true;
        for( V 的每个邻接点 W )
            if( collected[W] == false )
                if(dist[V] + E<V,W> < dist[W]){
             		dist[W] = dist[V] + E<V,W>;
                    path[W] = V;
                }
    }
}

取出未收录顶点中dist最小值和更新dist[W]的操作可以考虑两种方法：

直接扫描所有未收录顶点 ——O(|V|)

T = O($|V|^2$ + |E|) ——稠密图效果更好
将dist存在最小堆中 ——O(log|V|)

更新dist[w]的值 —O(log|V|)

T = O(|E|log|V|) —— 稀疏图效果更好

#include<iostream>
#include<stdlib.h>
#define Inf 1000000
#define Init -1
#define MaxVertex 100
typedef int Vertex;
int G[MaxVertex][MaxVertex];
int dist[MaxVertex];  // 距离 
int path[MaxVertex];  // 路径 
int collected[MaxVertex];  // 被收录集合 
int Nv;   // 顶点 
int Ne;   // 边 
using namespace std;

// 初始化图信息 
void build(){
	Vertex v1,v2;
	int w;
	cin>>Nv;
	// 初始化图 
	for(int i=1;i<=Nv;i++)
		for(int j=1;j<=Nv;j++)
			G[i][j] = 0;
	// 初始化路径 
	for(int i=1;i<=Nv;i++)
		path[i] = Init;
	// 初始化距离
	for(int i=0;i<=Nv;i++)
		dist[i] = Inf;
	// 初始化收录情况 
	for(int i=1;i<=Nv;i++)
		collected[i] = false;
	cin>>Ne;
	// 初始化点
	for(int i=0;i<Ne;i++){
		cin>>v1>>v2>>w;
		G[v1][v2] = w;  // 有向图 
	}
}

// 初始化距离和路径信息 
void crate(Vertex s){
	dist[s] = 0;
	collected[s] = true;
	for(int i=1;i<=Nv;i++)
		if(G[s][i]){
			dist[i] = G[s][i];
			path[i] = s;
		}
}

// 查找未收录顶点中dist最小者
Vertex FindMin(Vertex s){
	int min = 0;  // 之前特地把 dist[0] 初始化为正无穷 
	for(Vertex i=1;i<=Nv;i++)
		if(i != s && dist[i] < dist[min] && !collected[i])
			min = i;
	return min;
}


void Dijkstra(Vertex s){
	crate(s); 
	while(true){
		Vertex V = FindMin(s);   // 找到 
		if(!V)
			break;
		collected[V] = true;  //收录
		for(Vertex W=1;W<=Nv;W++)
			if(!collected[W] && G[V][W]){  // 如果未被收录
				if(dist[V] + G[V][W] < dist[W]){
					dist[W] = G[V][W] + dist[V];
					path[W] = V;
				}
			}
	}
}

void output(){
	for(int i=1;i<=Nv;i++)
		cout<<dist[i]<<" ";
	cout<<endl;
	for(int i=1;i<=Nv;i++)
		cout<<path[i]<<" ";
	cout<<endl;
}


int main(){
	build();
	Dijkstra(1);
	output();
	return 0;
}

4. 多源最短路算法

直接将单源最短路算法调用|V|遍

T = O($|V|^3$ + |E|×|V|) ——对于稀疏图效果好
Floyd 算法

T = O($|V|^3$) ——对于稠密图效果好

Floyd 算法

$D^k[i][j]$= 路径{ i →{$l$≤ $k$} → j } 的最小长度
$D^0,D^1,…,D^{|V|-1}[i][j]$即给出了 i 到 j 的真正最短距离
最初的 $D^{-1}$ 是全 0 的邻接矩阵
若 i 和 j 不直接相连，初始化为无穷大
当 $D^{k-1}$已经完成，递推到 $D^k$时：
- 或者 k 不属于最短路径 { i →{$ l$ ≤ $k$ } → j }，则
- 或者$ k $属于最短路径 { i →{ $l≤ $$k$} → j }，则该路径必定由两段最短路径组成：$D^k[i][j]=D^{k-1}[i][k]+D^{k-1}[k][j]$

void Floyd(){
    for( i = 0; i < N; i++ )
        for( j = 0; j < N; j++ ){
            D[i][j] = G[i][j];
            path[i][j] = -1;
        }
    for( k = 0; k < N; k++ )
        for( i = 0; i< N; i++)
            for( j = 0; j < N; j++ )
            	if( D[i][k] + D[k][j] < D[i][j] ) {
            		D[i][j] = D[i][k] + D[k][j];
                    path[i][j] = k;
                }
}

#include<iostream>
#include<stdlib.h>
#define INF 1000000
#define MaxVertex 100
typedef int Vertex;
int G[MaxVertex][MaxVertex];
int dist[MaxVertex][MaxVertex];  // 距离 
int path[MaxVertex][MaxVertex];  // 路径 
int Nv;   // 顶点 
int Ne;   // 边 
using namespace std;

// 初始化图信息 
void build(){
	Vertex v1,v2;
	int w;
	cin>>Nv;
	// 初始化图 
	for(int i=1;i<=Nv;i++)
		for(int j=1;j<=Nv;j++)
			G[i][j] = INF;
	cin>>Ne;
	// 初始化点
	for(int i=0;i<Ne;i++){
		cin>>v1>>v2>>w;
		G[v1][v2] = w;  
		G[v2][v1] = w;
	}
}

void Floyd(){
	for(Vertex i=1;i<=Nv;i++)
		for(Vertex j=1;j<=Nv;j++){
			dist[i][j] = G[i][j];
			path[i][j] = -1;
		}
	for(Vertex k=1;k<=Nv;k++)
		for(Vertex i=1;i<=Nv;i++)
			for(Vertex j=1;j<=Nv;j++)
				if(dist[i][k] + dist[k][j] < dist[i][j]){
					dist[i][j] = dist[i][k] + dist[k][j];
					path[i][j] = k;
				}
} 

void output(){
	for(Vertex i=1;i<=Nv;i++){ 
		for(Vertex j=1;j<=Nv;j++)
			cout<<dist[i][j]<<" ";	
		cout<<endl;
	}
	cout<<endl;
	for(Vertex i=1;i<=Nv;i++){ 
		for(Vertex j=1;j<=Nv;j++)
			cout<<path[i][j]<<" ";	
		cout<<endl;
	}
}


int main(){
	build();
	Floyd();
	output();
	return 0;
}

最小生成树问题

1. 什么是最小生成树

是一棵

树
- 无回路
- |V|个顶点一定有 |V|-1 条边
是

生成

树
- 不唯一
- 包含全部顶点
- |V|-1 条边都在图里
边的权值和最小

2. 贪心算法

什么是 “贪”：每一步都是最好的
什么是 “好”：权重最小的边
需要约束：
- 只能用图里有的边
- 只能正好用掉 |V|-1 条边
- 不能有回路

1. Prim 算法

void Prim(){
    MST = {s};  // parent[s] = -1
    while(1){
        V = 未收录顶点中dist最小者;   // dist[V] = E<V,W> 或 正无穷
        if ( 这样的V不存在 )
            break;
        dist[V] = 0;  // 将V收录进MST
        for ( V 的每个邻接点 W )
            if ( dist[W]!= 0)
                if ( E<V,W> < dist[w] ){
                    dist[W] = E<V,W>;
                    parent[W] = V;
                }
    }
    if ( MST 中收的顶点不到|V|个)
        Error ( "图不连通" );
}

时间复杂度：T = O($|V|^2$) —— 稠密图合算

#include<iostream>
#include<vector>
#define INF 100000
#define MaxVertex 105
typedef int Vertex; 
int G[MaxVertex][MaxVertex];
int parent[MaxVertex];   // 并查集 
int dist[MaxVertex]; // 距离 
int Nv;    // 结点 
int Ne;    // 边 
int sum;  // 权重和 
using namespace std; 
vector<Vertex> MST;  // 最小生成树 

// 初始化图信息 
void build(){
	Vertex v1,v2;
	int w;
	cin>>Nv>>Ne;
	for(int i=1;i<=Nv;i++){
		for(int j=1;j<=Nv;j++)
			G[i][j] = 0;  // 初始化图 
		dist[i] = INF;   // 初始化距离
		parent[i] = -1;  // 初始化并查集 
	}
	// 初始化点
	for(int i=0;i<Ne;i++){
		cin>>v1>>v2>>w;
		G[v1][v2] = w;
		G[v2][v1] = w;
	}
}

// Prim算法前的初始化 
void IniPrim(Vertex s){
	dist[s] = 0;
	MST.push_back(s);
	for(Vertex i =1;i<=Nv;i++)
		if(G[s][i]){
			dist[i] = G[s][i];
			parent[i] = s;
		} 
}

// 查找未收录中dist最小的点 
Vertex FindMin(){
	int min = INF;
	Vertex xb = -1;
	for(Vertex i=1;i<=Nv;i++)
		if(dist[i] && dist[i] < min){ 
			min = dist[i];
			xb = i;
		}
	return xb;
}

void output(){
	cout<<"被收录顺序："<<endl; 
	for(Vertex i=1;i<=Nv;i++)
		cout<<MST[i]<<" ";
	cout<<"权重和为："<<sum<<endl; 
	cout<<"该生成树为："<<endl; 
	for(Vertex i=1;i<=Nv;i++)
		cout<<parent[i]<<" ";
}

void Prim(Vertex s){
	IniPrim(s);
	while(1){
		Vertex v = FindMin();
		if(v == -1)
			break;
		sum += dist[v];
		dist[v] = 0;
		MST.push_back(v);
		for(Vertex w=1;w<=Nv;w++)
			if(G[v][w] && dist[w])
				if(G[v][w] < dist[w]){
					dist[w] = G[v][w];
					parent[w] = v;
				}
	}
}


int main(){
	build();
	Prim(1);
	output();
	return 0;
}

2. Kruskal 算法

void Kruskal ( Graph G ){
    MST = { };
    while ( MST 中不到|V|-1条边 &&  E中还有边 ) {
        从 E 中取一条权重最小的边 E<V,W>;    // 最小堆
        将 E<V,W> 从 E 中删除;
        if ( E<V,W> 不在 MST 中构成回路 )  // 并查集
            将 E<V,W> 加入MST;
        else
            彻底无视 E<V,W>;
    }
    if ( MST 中不到|V|-1条边 )
        Error("图不连通");
}

时间复杂度：T = O(|E|log|E|) —— 稀疏图合算

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#define INF 100000
#define MaxVertex 105
typedef int Vertex; 
int G[MaxVertex][MaxVertex];
int parent[MaxVertex];   // 并查集最小生成树 
int Nv;    // 结点 
int Ne;    // 边 
int sum;  // 权重和 
using namespace std; 
struct Node{
	Vertex v1;
	Vertex v2;
	int weight; // 权重 
	// 重载运算符成最大堆 
	bool operator < (const Node &a) const
	{
		return weight>a.weight;
	}
};
vector<Node> MST;  // 最小生成树 
priority_queue<Node> q;   // 最小堆 

// 初始化图信息 
void build(){
	Vertex v1,v2;
	int w;
	cin>>Nv>>Ne;
	for(int i=1;i<=Nv;i++){
		for(int j=1;j<=Nv;j++)
			G[i][j] = 0;  // 初始化图
		parent[i] = -1;
	}
	// 初始化点
	for(int i=0;i<Ne;i++){
		cin>>v1>>v2>>w;
		struct Node tmpE;
		tmpE.v1 = v1;
		tmpE.v2 = v2;
		tmpE.weight = w;
		q.push(tmpE); 
	}
}

//  路径压缩查找 
int Find(int x){
	if(parent[x] < 0)
		return x;
	else
		return parent[x] = Find(parent[x]);
} 

//  按秩归并 
void Union(int x1,int x2){
    x1 = Find(x1);
    x2 = Find(x2);
	if(parent[x1] < parent[x2]){
		parent[x1] += parent[x2];
		parent[x2] = x1;
	}else{
		parent[x2] += parent[x1];
		parent[x1] = x2;
	}
} 

void Kruskal(){
	// 最小生成树的边不到 Nv-1 条且还有边 
	while(MST.size()!= Nv-1 && !q.empty()){
		Node E = q.top();  // 从最小堆取出一条权重最小的边
		q.pop(); // 出队这条边 
		if(Find(E.v1) != Find(E.v2)){  // 检测两条边是否在同一集合 
			sum += E.weight; 
			Union(E.v1,E.v2);     // 并起来 
			MST.push_back(E);
		}
	}
	
} 


void output(){
	cout<<"被收录顺序："<<endl; 
	for(Vertex i=0;i<Nv;i++)
		cout<<MST[i].weight<<" ";
	cout<<"权重和为："<<sum<<endl; 
	for(Vertex i=1;i<=Nv;i++)
		cout<<parent[i]<<" ";
	cout<<endl;
}


int main(){
	build();
	Kruskal();
	output();
	return 0;
}

排序

散列查找

1. 基本思想

以关键字 key 为自变量，通过一个确定的函数 h（散列函数），计算出对应的函数值 h(key)，作为数据对象的存储地址
可能不同的关键字会映射到同一个散列地址上，即 $h(key_i)=h(key_j)$（当 $key_i$≠ $key_j$），称为“冲突”——需要某种冲突解决策略

2. 基本工作

计算位置：构造散列函数确定关键词存储位置
解决冲突：应用某种策略解决多个关键词位置相同的问题

时间复杂度几乎为是常数：O(1)

3. 散列函数的构造

1. 考虑因素

计算简单，以便提高转换速度
关键词对应的地址空间分布均匀，以尽量减少冲突

2. 数字关键词

1. 直接定址法

取关键词的某个线性函数值为散列地址，即：h(key) = a x key + b （a、b为常数)

2. 除留余数法

散列函数为：h(key) = key mod p （p 一般取素数)

3. 数字分析法

分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址

4. 折叠法

把关键词分割成位数相同的几个部分，然后叠加

5. 平方取中法

将关键词平方，取中间几位

3. 字符串关键字

1. ASCII码加和法

h(key) = (Σkey[i]) mod TableSize

2. 前3个字符移位法

h(key) = (key[0]×$27^2$ + key[1]×27 + key[2])mod TableSize

3. 移位法

h(key) = $\begin{equation}\left(\sum_{i=0}^{n-1} \mathrm{key}[\mathrm{n}-\mathrm{i}-1] \times 32^{i}\right)\end{equation}$ mod TableSize

例子（移位法）

h(“abcde”) = ‘a’x$32^4$ + ‘b’x$32^3$ +’c’x$32^2$+ ‘d’x32 + ‘e’= (((‘a’x32+‘b’)x32+‘c’)x32+‘d’)x32+‘e’

Index Hash( const char *Key,int TableSize){
    unsigned int h = 0;   // 散列值函数，初始化为 0 
    while ( *Key != '\0' )    // 位移映射
        h = ( h << 5) + *Key++;
    return h % TableSize;
}

4. 冲突处理方法

1. 常用策略

换个位置：开放地址法
同一位置的冲突对象组织在一起：链地址法

2. 开放定址法

一旦产生了冲突（该地址已有其它元素），就按某种规则去寻找另一空地址
若发生了第 i 次冲突，试探的下一个地址将增加 di_ii，基本公式是： $h_i(key)=(h(key)+d_i)$mod TableSize （1 ≤ i ≤ TableSize）
di_ii 决定了不同的解决冲突方案

1. 线性探测

以增量序列 1,2,…, (TableSize - 1) 循环试探下一个存储地址

2. 平方探测法

以增量序列$1^2,-1^2,2^2,-2^2,…,q^2,-q^2$且 q ≤ ⌊ TableSize/2 ⌋ 循环试探下一个存储地址

如果散列表长度是某个 4k+3（k是正整数）形式的素数时，平方探测法就可以探查到整个散列表空间

3. 双散列

$d_i$为$i*h_2(key)$，$h_2(key)$ 是另一个散列函数，探测序列成:$h_2(key),2h_2(key),3h_2(key)$

对任意 key,$h_2(key)\neq 0$

$h_2(key)$ = p - (key mod p) （p < TableSize，p、TableSize 都是素数）

4. 再散列

当散列表元素太多（即装填因子 α 太大）时，查找效率会下降

解决的方法是加倍扩大散列表，这个过程就叫”再散列”，扩大时，原有元素需要重新计算放置到新表中

3. 分离链接法

将相应位置上冲突的所有关键词存储在同一个单链表中

5. 抽象数据类型定义

数据类型：符号表（SymbolTable）
数据对象集：符号表是”名字(Name)-属性(Attribute)”对的集合
操作集：Table ∈ SymbolTable，Name ∈ NameType，Attr ∈ AttributeType

主要操作：
- SymbolTable InitalizeTable(int TableSize)：创建一个长度为 TableSize 的符号表
- Boolean IsIn(SymbolTable Table,NameType Name)：查找特定的名字 Name 是否在 Table 中
- AttributeType Find(SymbolTable Table,NameType Name)：获取 Table 中指定名字 Name 对应的属性
- SymbolTable Modefy(SymbolTable Table,NameType Name,AttributeType Attr)：将 Table 中指定名字 Name 的属性修改为 Attr
- SymbolTable Insert(SymbolTable Table,NameType Name,AttributeType Attr)：向 Table 中插入一个新名字 Name 及其属性 Attr
- SymbolTable Delete(SymbolTable Table,NameType Name)：从 Table 中删除一个名字 Name 及其属性

1. 平方探测法实现

#include<iostream>
#include<stdlib.h>
#include<cmath>
#define MAXTABLESIZE 100000   // 定义允许开辟的最大散列表长度 
typedef int Index;
typedef int ElementType; 
typedef Index Position;
typedef enum{   // 分别对应：有合法元素、空、有已删除元素 
	Legitimate,Empty,Deleted
} EntryType;  // 定义单元状态类型 

typedef struct HashEntry Cell;
struct HashEntry{   //  哈希表存值单元 
	ElementType Data;  // 存放元素
	EntryType Info;  // 单元状态	
};

typedef struct HashTbl *HashTable;
struct HashTbl{  // 哈希表结构体 
	int TableSize;   // 哈希表大小 
	Cell *Cells;   // 哈希表存值单元数组 
};

using namespace std;

int NextPrime(int N);  // 查找素数 
HashTable CreateTable( int TableSize); // 创建哈希表 
Index Hash(int Key,int TableSize);   // 哈希函数 

// 查找素数 
int NextPrime(int N){
	int p = (N%2)?N+2:N+1;  // 从大于 N 的下个奇数开始
	int i;
		
	while(p <= MAXTABLESIZE){
		for(i = (int)sqrt(p);i>2;i--)
			if(!(p%i))  // p 不是素数 
				break;
		if(i==2) 
			break; 
		p += 2;  // 继续试探下个奇数 
	}
	return p;
}

// 创建哈希表 
HashTable CreateTable( int TableSize){
	HashTable H;
	int i;
	H = (HashTable)malloc(sizeof(struct HashTbl));
	// 保证哈希表最大长度是素数 
	H->TableSize = NextPrime(TableSize);
	// 初始化单元数组
	H->Cells = (Cell *)malloc(sizeof(Cell)*H->TableSize);
	// 初始化单元数组状态 
	for(int i=0;i<H->TableSize;i++)
		H->Cells[i].Info = Empty;
	return H;
}

// 平方探测查找 
Position Find(HashTable H,ElementType Key){
	Position CurrentPos,NewPos; 
	int CNum = 0 ;   // 记录冲突次数
	CurrentPos = NewPos = Hash(Key,H->TableSize);
	// 如果当前单元状态不为空，且数值不等，则一直做 
	while(H->Cells[NewPos].Info != Empty && H->Cells[NewPos].Data != Key){
		if(++CNum % 2 ){ // 冲突奇数次发生 
			NewPos = CurrentPos + (CNum+1)/2*(CNum+1)/2;
			// 如果越界，一直减直到再次进入边界 
			while(H->TableSize <= NewPos){
				NewPos -= H->TableSize; 
			}
		}else{  // 冲突偶数次发生 
			NewPos = CurrentPos - CNum/2*CNum/2;
			// 如果越界，一直加直到再次进入边界 
			while(NewPos < 0){
				NewPos += H->TableSize; 
			}
		}
	} 
	return NewPos;
}

// 插入
bool Insert( HashTable H,ElementType Key,int i){
	Position Pos = i;
	Pos = Find(H,Key);
	// 如果单元格状态不是"存在合法元素" 
	if( H->Cells[Pos].Info != Legitimate){
		H->Cells[Pos].Info = Legitimate;
		H->Cells[Pos].Data = Key;
	}
	return true;
} 

// 除留余数法哈希函数 
Index Hash(int Key,int TableSize){
	return Key % TableSize;
}


void output(HashTable H){
	for(int i=0;i<H->TableSize;i++)
		cout<<i<<" "<<H->Cells[i].Data<<endl;
} 

int main(){
	HashTable H = CreateTable(9);
	int N;
	cin>>N;
	for(int i=0;i<N;i++){
		int tmp;
		cin>>tmp;
		Insert(H,tmp,i);
	}
	output(H);
	return 0;
}

2. 分离链接法实现

#include<iostream>
#include<cstdlib>
#include<cmath>
#define MAXTABLESIZE 100000
typedef int Index;
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode{   // 单链表 
	ElementType Data;
	PtrToLNode Next;
}; 
typedef PtrToLNode Position;
typedef PtrToLNode List;

typedef struct TblNode *HashTable;  // 散列表
struct TblNode{
	int TableSize;   // 表的最大长度 
	List Heads;  // 指向链表头结点的数组 
}; 
using namespace std;

int NextPrime(int N){
	int p = (N%2)?(N+2):(N+1);   // 比 tablesize 大的奇数 
	int i;
	while(p <= MAXTABLESIZE){
		for(i = (int)sqrt(p);i>2;i--)
			if(!(p%i))
				break;
		if(i==2)  // 找到素数了 
			break;
		p += 2; // 下一个奇数
	}
	return p;
}

// 创建哈希表 
HashTable CreateTable( int TableSize){
	HashTable H;
	H = (HashTable)malloc(sizeof(struct TblNode));
	H->TableSize = NextPrime(TableSize);
	H->Heads = (List)malloc(sizeof(struct TblNode) * H->TableSize);
	for(int i=0;i<H->TableSize;i++) 
		H->Heads[i].Next = NULL;  // 链表头：H->Heads[i] 是不存东西的 
	return H;
}

// 除留余数法哈希函数 
Index Hash(	int TableSize,ElementType Key){
	return  Key%TableSize;
}

// 查找
Position Find(HashTable H,ElementType Key){
	Position p;
	Index pos;
	
	pos = Hash(H->TableSize,Key); 
	p = H->Heads[pos].Next;  //获得链表头 
	while(p && p->Data != Key)
		p = p->Next;
	return p;
} 

// 插入
bool Insert(HashTable H,ElementType Key){
	Position p,NewCell;
	Index pos;
	
	p = Find(H,Key);
	if(!p){  // 关键词未找到，可以插入 
		NewCell = (Position)malloc(sizeof(struct LNode));
		NewCell->Data = Key;
		pos = Hash(H->TableSize,Key);   // 初始散列表地址
		// 将新增结点插到最前面
		NewCell->Next = H->Heads[pos].Next;
		H->Heads[pos].Next = NewCell;
		return true;
	}else{
		return false;
	}
}

void output(HashTable H){
	for(int i=0;i<H->TableSize;i++){
		cout<<i;
		List p = H->Heads[i].Next;  
		while(p){
			cout<<" "<<p->Data;
			p = p->Next;
		} 
		cout<<endl;
	}
}

void DestroyTable(HashTable H){
	Position P,tmp;
	for(int i=0;i<H->TableSize;i++){
		P = H->Heads[i].Next;
		while( P ){
			tmp = P->Next;
			free(P);
			P = tmp;
		}
	}
	free(H->Heads);
	free(H);
} 


int main(){
	HashTable H = CreateTable(9);
	int N;
	cin>>N;
	for(int i=0;i<N;i++){
		int tmp;
		cin>>tmp;
		Insert(H,tmp);
	}
	output(H);
	DestroyTable(H);
	return 0;
}

数据结构与算法 笔记

基本概念

一、数据结构

1. 其他定义

2. 解决问题方法的效率

3. 最终定义

4. 抽象数据类型（Abstract Data Type）

二、算法

1. 定义

2. 描述算法的手段

3. 评价

4. 复杂度的渐进表示法

5. 复杂度分析小窍门

线性表

1. 什么是线性表

2. 线性表的抽象数据类型描述

1. 线性表的顺序存储实现

2. 线性表的链表存储实现

堆栈

1. 什么是堆栈

2. 堆栈的抽象数据类型描述

1. 栈的顺序存储实现

2. 栈的链表存储实现

队列

1. 什么是队列

2. 队列的抽象数据类型描述

1. 循环队列的顺序存储实现

2. 队列的链式存储实现

树

1. 树的定义

1. 特征

2. 基本术语

3. 树的表示

1. 儿子-兄弟表示法

2. 二叉树

2. 二叉树

1. 定义

2. 五种基本形态

3. 特殊形态

4. 重要性质

5. 抽象数据类型定义

1. 顺序存储结构

2. 链表存储

二叉树的遍历

0. 树的表示

1. 先序遍历

1.递归实现

2. 非递归实现

2.中序遍历

1. 递归实现

2. 非递归实现

3. 后序遍历

1. 递归实现

2. 非递归实现

4. 总结

5. 层序遍历

6. 例子

1. 输出叶子结点

2. 树的高度

3. 由两种遍历序列确定二叉树

二叉搜索树

1. 定义

2. 特殊函数

1. 查找

2. 查找最大和最小元素

3. 删除

4. 代码实现

平衡二叉树

0. 为何要使用AVL树？

1. 定义

2. 平衡二叉树的调整

0. 遵循原则

1. RR 单旋

2. LL 单旋

3. LR 双旋

4. RL 双旋

堆

1. 什么是堆

2. 堆的抽象数据类型描述

1. 插入

数据结构与算法笔记