目录
一、线性表
1.顺序表
2.单链表（不带头结点）
3.1单链表（带头结点）
3.2双链表（带头结点）
4.循环单链表（L指向表头）
5.循环单链表（L指向表尾)
6.循环双链表
7.静态链表

二、栈和队列
1.顺序栈
2.共享栈
3.链栈（带头）
4.链栈（不带头）
5.顺序队列
6.循环队列
6.1 rear指向队尾指针后一个位置and牺牲一个存储空间来区分队空和队满
6.2 rear指向队尾指针后一个位置and增设size判断
6.3 rear指向队尾指针后一个位置and增设tag判断
6.4 rear指向队尾and牺牲一个存储空间来区分队空和队满
6.2 rear指向队尾and增设size判断
6.3 rear指向队尾and增设tag判断
7.链队列（带头）
8.链队列（不带头）

三、串
1、串的基本操作
2、kmp模式匹配

四、树与二叉树
1、二叉树计算高度
2、二叉树的先序，中序，后序遍历（递归）
3、二叉树的先序，中序，后序遍历（非递归）
4、二叉树的层序遍历
5、中序线索化二叉树
6、先序线索化二叉树
7、后序线索化二叉树
8、先序，中序，后序线索二叉树总结
9、平衡二叉树

五、排序
1、插入排序
（1）直接插入排序
（2）折半插入排序
（3）希尔排序

2、交换排序
（1）冒泡排序
（2）快速排序

3、选择排序
（1）简单选择排序
（2）堆排序
4、归并排序





一、线性表
1.顺序表
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
using namespace std;
#define InitSize 10  //定义最大长度
 
静态分配
//typedef struct {
//	int data[InitList];
//	int length;
//}SqlList;
 
//动态分配
typedef struct {
	int *data;
	int length;	//当前长度
	int MaxSize;//最大长度
}SqlList;
 
//初始化顺序表
void InitList(SqlList &L) {
	L.data = (int *)malloc(InitSize * sizeof(int));
	L.length = 0;
	L.MaxSize = InitSize;
}
 
//增加顺序表的长度
void IncreaseSize(SqlList &L, int len) {
	int* p = L.data;
	L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));
	for (int i = 0; i < L.length; i++) {
		L.data[i] = p[i];
	}
	L.MaxSize += len;
	free(p);
}
 
//插入元素，在位序i的位置插入元素e
bool ListInsert(SqlList& L, int i, int e) {
	if (i<1 || i>L.length + 1) return false;	//i的范围是否有效
	if (L.length >= L.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;
}
 
//删除操作，删除位序i个位置上的元素,e是删除的元素
bool ListDelete(SqlList& L, int i, int& 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;
}
 
//按位查找  返回位序i的元素
int GetElem(SqlList L, int i) {
	if (i<1 || i>L.length) return -1;
	return L.data[i - 1];
}
 
//查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqlList L, int e) {
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e) return i + 1;
	}
	return -1;
}
 
//删除值位于s和t之间的数
bool Delete_s_t(SqlList& L, int s, int t) {
	if (L.length == 0 || s >= t) return false;
	int k = 0;
	for (int i = 0; i < L.length; i++) {
		if (L.data[i]<s || L.data[i]>t) {
			L.data[k++] = L.data[i];
		}
	}
	L.length = k;
	return true;
}
 
int main() {
		
	SqlList L;
	InitList(L);
	ListInsert(L, 1, 1);
	ListInsert(L, 2, 6);
	ListInsert(L, 3, 3);
	ListInsert(L, 4, 8);
	ListInsert(L, 5, 2);
	for (int i = 0; i < L.length; i++) {
		cout << L.data[i] << " ";
	}
	cout << endl;
	Delete_s_t(L, 2, 3);
	for (int i = 0; i < L.length; i++) {
		cout << L.data[i] << " ";
	}
	cout << endl;
 
	return 0;
}
2.单链表（不带头结点）
#include<iostream>
#include<algorithm>
 
using namespace std;
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
//struct LNode*  == LinkList
//强调节点  用LNode
//强调链表  用LinkList
 
//初始化单链表
bool InitList(LinkList& L) {
	L = NULL;
	return true;
}
 
//按位查找，返回第i个元素（不带带头节点）
LNode* GetElem(LinkList L, int i) {
	if (i <= 0) return NULL;
	int j = 1;
	LNode* p = L;
	while (p && j < i) {
		p = p->next;
		j++;
	}
	return p;
}
 
//按值查找，找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e) {
	LNode* p = L;
	while (p && p->data != e) {
		p = p->next;
	}
	return p;
}
 
//统计单链表的长度
int Length(LinkList L) {
	int len = 0;
	LNode* p = L;
	while (p) {
		len++;
		p = p->next;
	}
	return len;
}
 
//后插操作，在节点p之后插入元素e
bool InsertNextNode(LNode* p, int e) {
	if (!p) return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (!s) return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}
 
 
//不带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e) {
	if (i < 1) return false;
	if (i == 1) {
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;
		return true;
	}
	LNode* p;
	p = L;
	int j = 1;	//当前p指向的是第几个节点，没有头节点，所以从1开始
	while (p && j < i - 1) {
		p = p->next;
		j++;
	}
	if (!p) return false;
	return InsertNextNode(p, e);
}
 
//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e) {
	if (!p) return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (!s) return false;
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;
	return true;
}
 
//前插操作，在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
	if (!p || !s) return false;
	s->next = p->next;
	p->next = s;
	swap(s->data, p->data);
	return true;
}
 
//删除位序i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
	if (L == NULL) {
		e = -1;
		return false;
	}
	if (i < 1) return false;
	if (i > 1) {
		LNode* p = GetElem(L, i - 1);
		if (!p || !(p->next)) return false;
		LNode* q = p->next;
		e = q->data;
		p->next = q->next;
		free(q);
	}
	else {
		if (L->next == NULL) {
			e = L->data;
			L = NULL;
		}
		else {
			e = L->data;
			L = L->next;
		}
	}
	
	return true;
}
 
//删除指定节点P
bool DeleteNode(LNode* p) {
	if (p->next == NULL) return false;
	//下面这段代码有bug，不能删除最后一个节点，因此要是删除最后一个节点的话要重新进行操作
	LNode* q = p->next;
	p->data = q->data;
	p->next = q->next;
	free(q);
	return true;
}
 
 
//尾插法，不带头结点
LinkList List_TailInsert(LinkList& L) {
	InitList(L);
	LNode* s, * r = L ;	//r表示表尾指针
	int x;
	bool is_head = true;
	while (cin >> x) {
		s = (LNode*)malloc(sizeof(LNode));
 
		if (is_head) {
			is_head = false;
			s->data = x;
			L = s;
			r = s;
		}
		s->data = x;
		r->next = s;
		r = s;
 
	}
	r->next = NULL;
	return L;
}
 
//头插法，不带头结点
LinkList List_HeadInsert(LinkList& L) {
	InitList(L);
	LNode* s;
	int x;
	while (cin >> x) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L;
		L = s;
	}
	return L;
}
 
void print(LinkList L) {
	LNode* s = L;
	while (s!= NULL) {
		
		cout << s->data << " ";
		s = s->next;
	}
	cout << endl;
}
 
int main() {
 
	LinkList L;
	List_HeadInsert(L);
	cout << "头插法的结果" << endl;
	print(L);
	//List_TailInsert(L);
	//cout << "尾插法的结果" << endl;
	//print(L);
	cout << "链表的第1个元素：" << GetElem(L, 1)->data << endl;
	cout << "链表的长度：" << Length(L) << endl;
	int e;
	ListDelete(L, 5, e);
	cout << "删除的第1个元素是：" << e << endl;
	cout << "当前的链表" << endl;
	print(L);
	ListInsert(L, 5, e);
	cout << "插入的第1个元素是：" << e << endl;
	cout << "当前的链表" << endl;
	print(L);
	LNode* s = LocateElem(L, 5);
 
	return 0;
}
3.单链表（带头结点）
#include<iostream>
#include<algorithm>
 
using namespace std;
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, *LinkList;
//struct LNode*  == LinkList
//强调节点  用LNode
//强调链表  用LinkList
 
//按位查找，返回第i个元素（带头节点）
LNode* GetElem(LinkList L, int i) {
	if (i < 0) return NULL;
	int j = 0;
	LNode* p = L;
	while (p && j < i) {
		p = p->next;
		j++;
	}
	return p;
}
 
//按值查找，找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e) {
	LNode* p = L->next;
	while (p && p->data!=e) {
		p = p->next;
	}
	return p;
}
 
//统计单链表的长度
int Length(LinkList L) {
	int len = 0;
	LNode* p = L;
	while (p->next) {
		len++;
		p = p->next;
	}
	return len;
}
 
//后插操作，在节点p之后插入元素e
bool InsertNextNode(LNode *p, int e) {
	if (!p) return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (!s) return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}
 
//带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e) {
	if (i < 1) return false;
	LNode* p = GetElem(L, i - 1);
	if (!p) return false;
	return InsertNextNode(p, e);
}
 
//不带头节点的插入操作，在第i个位置插入元素e
bool NoHead_ListInsert(LinkList& L, int i, int e) {
	if (i < 1) return false;
	if (i == 1) {
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;
		return true;
	}
	LNode* p;
	p = L;
	int j = 1;	//当前p指向的是第几个节点，没有头节点，所以从1开始
	while (p && j < i - 1) {
		p = p->next;
		j++;
	}
	if (!p) return false;
	return InsertNextNode(p, e);
}
 
//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e) {
	if (!p) return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (!s) return false;
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;
	return true;
}
 
//前插操作，在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
	if ( !p || !s ) return false;
	s->next = p->next;
	p->next = s;
	swap(s->data , p->data);
	return true;
}
 
//删除位序i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
	if (i < 1) return false;
	LNode* p = GetElem(L, i - 1);
	if (!p || !(p->next)) return false;
	LNode* q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}
 
//删除指定节点P
bool DeleteNode(LNode* p) {
	if (p->next == NULL) return false;
	//下面这段代码有bug，不能删除最后一个节点，因此要是删除最后一个节点的话要重新进行操作
	LNode* q = p->next;
	p->data = q->data;
	p->next = q->next;
	free(q);
	return true;
}
 
bool InitList(LinkList& L) {
	L = (LNode* )malloc(sizeof(LNode));//分配一个头节点
	if (!L) return false;
	L->next = NULL;
	return true;
}
 
//尾插法，带头结点
LinkList List_TailInsert(LinkList& L) {
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	LNode* s, * r = L;	//r表示表尾指针
	int x;
	while (cin >> x) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
	}
	r->next = NULL;
	return L;
}
 
//头插法，带头结点
LinkList List_HeadInsert(LinkList& L) {
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	LNode* s;
	int x;
	while (cin >> x) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
	}
	return L;
}
 
void print(LinkList L) {
	LNode* s = L;
	while (s->next!=NULL) {
		s = s->next;
		cout << s->data << " ";
	}
	cout << endl;	
}
 
int main() {
 
	LinkList L;
	//List_HeadInsert(L);
	//cout << "头插法的结果" << endl;
	//print(L);
	List_TailInsert(L);
	cout << "尾插法的结果" << endl;
	print(L);
	cout << "链表的第2个元素："<< GetElem(L, 2)->data << endl;
	cout << "链表的长度："<< Length(L) << endl;
	int e;
	ListDelete(L, 3, e);
	cout << "删除的第3个元素是：" << e << endl;
	cout << "当前的链表" << endl;
	print(L);
	ListInsert(L, 3, e);
	cout << "插入的第3个元素是：" << e << endl;
	cout << "当前的链表" << endl;
	print(L);
	LNode* s = LocateElem(L, 5);
	
	return 0;
}
3.双链表（带头结点）
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
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;
}
 
//判断双链表是否为空
bool empty(DLinkList L) {
	if (L->next = NULL) {
		return true;
	}
	return false;
}
 
//按位查找：返回第i个结点
DNode* GetElem(DLinkList L, int i) {
	if (i < 0) return NULL;
	int j = 0;
	DNode* p = L;
	while (p != NULL && j < i) {
		p = p->next;
		j++;
	}
	return p;
}
 
//按值查找：找到第一个数据域为e的结点
DNode* LocateElem(DLinkList L, ElemType e) {
	DNode* p = L;
	if (p == NULL) return NULL;
	p = p->next;
	while (p != NULL && p->data != e) {
		p = p->next;
	}
	return p;
}
 
//在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;
	s->prior = p;
	p->next = s;
}
 
//在p节点后面插入值是e的节点
bool InsertNextDNode(DNode* p, ElemType e) {
	if (p == NULL) return false;
	DNode* q = (DNode*)malloc(sizeof(DNode));
	if (q == NULL) return false;
	q->data = e;
	q->next = NULL;
	q->prior = p;
	if (p->next != NULL) {
		p->next->prior = q;
		q->next = p->next;
	}
	p->next = q;
	return true;
}
 
//前插，在p节点前面插入节点s
bool InsertPriorDnode(DNode* p, DNode* s) {
	return InsertNextDNode(p->prior, s);
}
 
//按位插入，在第i个位置插入值为e的节点（位序i）
bool InsertDLinkList(DLinkList& L, int i, ElemType e) {
	if (i <= 0) return false;
	DNode* p = GetElem(L, i - 1);
	return InsertNextDNode(p, e);
}
 
//删除p节点的后继节点
bool DeleteNextNode(DNode* p) {
	if (p == NULL) return false;
	DNode* q = p->next;
	if (q == NULL) return false;
	p->next = q->next;
	if (q->next != NULL) q->next->prior = p;
	free(q);
	return true;
}
 
//销毁双链表
bool DestoryList(DLinkList& L) {
	while (L->next != NULL) {
		DeleteNextNode(L);
	}
	free(L);
	L = NULL;
	return true;
}
 
//尾插法
DLinkList List_TailInsert(DLinkList& L) {
	InitDLinkList(L);
	DNode* p = L;
	ElemType x;
	while (cin >> x) {
		InsertNextDNode(p, x);
		p = p->next;
	}
	return L;
}
 
//头插法
DLinkList List_HeadInsert(DLinkList& L) {
	InitDLinkList(L);
	ElemType x;
	while (cin >> x) {
		InsertNextDNode(L, x);
	}
	return L;
}
 
int Length(DLinkList L) {
	DNode* p = L;
	int len = 0;
	while (p->next != NULL) {
		len++;
		p = p->next;
	}
	return len;
}
 
 
//删除指定节点s
bool DeleteNode(DNode* s) {
	DNode* p;
	p = s->prior;
	p->next = s->next;
	if (s->next != NULL) {
		s->next->prior = p;
	}
	free(s);
	return true;
}
 
//删除位序i的节点，e是i节点的值
bool ListDelete(DLinkList& L, int i, ElemType& e) {
	if (i <= 0 || i > Length(L)) return false;
	DNode* s;
	s = GetElem(L, i);
	if (s == NULL) return false;
	e = s->data;
	return DeleteNode(s);
}
 
 
void print(DLinkList L) {
	DNode* p = L->next;
	while (p != NULL) {
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}
 
void testDLinkList() {
	DLinkList L;
	//cout << "头插法" << endl;
	//List_HeadInsert(L);
	//print(L);
	cout << "尾插法" << endl;
	List_TailInsert(L);
	print(L);
	cout << "长度：" << Length(L) << endl;
	cout << "第1个元素为：" << GetElem(L, 1)->data << endl;
	cout << "第5个元素为：" << GetElem(L, 5)->data << endl;
	cout << "在第一个位置插入元素0" << endl;
	InsertDLinkList(L, 1, 0);
	print(L);
	cout << "在最后一个位置插入元素6" << endl;
	InsertDLinkList(L, 7, 6);
	print(L);
	
	int e;
	ListDelete(L, 1, e);
	cout << "删除第一个节点：" << e << endl;
	cout << "当前链表为" << endl;
	print(L);
 
	ListDelete(L, 6, e);
	cout << "删除最后一个节点：" << e << endl;
	cout << "当前链表为" << endl;
	print(L);
 
	DestoryList(L);
}
 
int main() {
 
	testDLinkList();
	return 0;
}
4.循环单链表（L指向表头）
#include<iostream>
#include<algorithm>
 
using namespace std;
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
//struct LNode*  == LinkList
//强调节点  用LNode
//强调链表  用LinkList
 
bool InitList(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));//分配一个头节点
	if (L == NULL) return false;
	L->next = L;
	return true;
}
 
//按位查找，返回第i个元素（带头节点）
LNode* GetElem(LinkList L, int i) {
	if (i < 0) return NULL;
	if (i == 0) return L;
	int j = 1;
	LNode* p = L->next;
	while (p != L && j < i) {
		p = p->next;
		j++;
	}
	return p;
}
 
//按值查找，找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e) {
	LNode* p = L->next;
	while (p != L && p->data != e) {
		p = p->next;
	}
	if (p->data == e) return p;
	return NULL;
}
 
//统计单链表的长度
int Length(LinkList L) {
	int len = 0;
	LNode* p = L;
	while (p->next != L) {
		len++;
		p = p->next;
	}
	return len;
}
 
//后插操作，在节点p之后插入元素e
bool InsertNextNode(LNode* p, int e) {
	if (!p) return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (!s) return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}
 
//带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e) {
	if (i < 1) return false;
	LNode* p = GetElem(L, i - 1);
	if (!p) return false;
	return InsertNextNode(p, e);
}
 
 
//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e) {
	if (!p) return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (!s) return false;
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;
	return true;
}
 
//前插操作，在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
	if (!p || !s) return false;
	s->next = p->next;
	p->next = s;
	swap(s->data, p->data);
	return true;
}
 
//删除位序i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
	if (i < 1) return false;
	LNode* p = GetElem(L, i - 1);
	if (p == NULL || p->next == L) return false;
	LNode* q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}
 
//删除指定节点P
bool DeleteNode(LinkList& L, LNode* p) {
	LNode* q = p->next;
	p->data = q->data;
	p->next = q->next;
	
	if (L == q) {
		L = p;
	}
	free(q);
	return true;
}
 
//尾插法，带头结点
LinkList List_TailInsert(LinkList& L) {
	InitList(L);
	LNode* s, * r = L;	//r表示表尾指针
	int x;
	while (cin >> x) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
	}
	r->next = L;
	return L;
}
 
//头插法，带头结点
LinkList List_HeadInsert(LinkList& L) {
	InitList(L);
	LNode* s, * r = L;
	int x;
	bool isFirst = true;
	while (cin >> x) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		if (isFirst) {
			r = s;
			isFirst = false;
		}
	}
	r->next = L;
	return L;
}
 
bool Empty(LinkList L) {
	if (L->next == L) {
		return true;
	}
	return false;
}
 
//判断是否为表尾节点
bool isTail(LinkList L, LNode* p) {
	if (p->next == L) return true;
	return false;
}
 
void print(LinkList L) {
	LNode* s = L->next;
	while (s != L) {
 
		cout << s->data << " ";
		s = s->next;
	}
	cout << endl;
}
 
int main() {
 
	LinkList L;
	//List_HeadInsert(L);
	//cout << "头插法的结果" << endl;
	//print(L);
	List_TailInsert(L);
	cout << "尾插法的结果" << endl;
	print(L);
	cout << "链表的第1个元素：" << GetElem(L, 1)->data << endl;
	cout << "链表的第5个元素：" << GetElem(L, 5)->data << endl;
	cout << "链表的长度：" << Length(L) << endl;
	int e;
 
	ListDelete(L, 5, e);
	cout << "删除的第5个元素是：" << e << endl;
	cout << "当前的链表" << endl;
	print(L);
	ListInsert(L, 5, e);
	cout << "插入的第5个元素是：" << e << endl;
	cout << "当前的链表" << endl;
	print(L);
 
	ListDelete(L, 1, e);
	cout << "删除的第1个元素是：" << e << endl;
	cout << "当前的链表" << endl;
	print(L);
	ListInsert(L, 1, e);
	cout << "插入的第1个元素是：" << e << endl;
	cout << "当前的链表" << endl;
	print(L);
 
	LNode* s = LocateElem(L, 5);
	DeleteNode(L, s);
	print(L);
 
	return 0;
}
/*
输入样例：
1 2 3 4 5
*/
5.循环单链表（L指向表尾)
 

#include<iostream>
#include<algorithm>
 
using namespace std;
 
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;
//struct LNode*  == LinkList
//强调节点  用LNode
//强调链表  用LinkList
 
bool InitList(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));//分配一个头节点
	if (L == NULL) return false;
	L->next = L;
	return true;
}
 
//按位查找，返回第i个元素（带头节点）
LNode* GetElem(LinkList L, int i) {
	if (i < 0) return NULL;
	if (i == 0) return L->next;
	int j = 1;
	LNode* p = L->next->next;
	while (p != L->next && j < i) {
		p = p->next;
		j++;
	}
	if (p == L->next) return NULL;
	return p;
}
 
//按值查找，找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e) {
	LNode* p = L->next->next;
	while (p != L->next && p->data != e) {
		p = p->next;
	}
	if (p->data == e) return p;
	return NULL;
}
 
//统计单链表的长度
int Length(LinkList L) {
	int len = 0;
	LNode* p = L;
	while (p->next != L) {
		len++;
		p = p->next;
	}
	return len;
}
 
//后插操作，在节点p之后插入元素e
bool InsertNextNode(LinkList& L, LNode* p, int e) {
	if (!p) return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (!s) return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	if (p == L) L = s;
	return true;
}
 
//带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e) {
	if (i < 1) return false;
	LNode* p = GetElem(L, i - 1);
	if (!p) return false;
	return InsertNextNode(L, p, e);
}
 
 
//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e) {
	if (!p) return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (!s) return false;
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;
	return true;
}
 
//前插操作，在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
	if (!p || !s) return false;
	s->next = p->next;
	p->next = s;
	swap(s->data, p->data);
	return true;
}
 
//删除位序i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
	if (i < 1) return false;
	LNode* p = GetElem(L, i - 1);
	if (p == NULL || p == L) return false;
	if (p->next == L) {
		L = p;
	}
	LNode* q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}
 
 
//删除指定节点P
bool DeleteNode(LinkList& L, LNode* p) {
	LNode* q = p->next;
	p->data = q->data;
	p->next = q->next;
 
	if (L == p) {		//尾节点
		q = p;
		while (q->next != p) {
			q = q->next;
		}
		L = q;
	}
	//free(q)；   不能这样写，因为指针之间的赋值是指向同一块区域，就比如L和q就是指向相同的区域
	return true;
}
 
//尾插法，带头结点
LinkList List_TailInsert(LinkList& L) {
	InitList(L);
	LNode* s, * r = L;	//r表示表尾指针
	int x;
	while (cin >> x) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
	}
	r->next = L;
	L = r;
	return L;
}
 
//头插法，带头结点
LinkList List_HeadInsert(LinkList& L) {
	InitList(L);
	LNode* s, * r = L;
	int x;
	bool isFirst = true;
	while (cin >> x) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		if (isFirst) {
			r = s;
			isFirst = false;
		}
	}
	r->next = L;
	L = r;
	return r;
}
 
bool Empty(LinkList L) {
	if (L->next == L) {
		return true;
	}
	return false;
}
 
//判断是否为表尾节点
bool isTail(LinkList L, LNode* p) {
	if (p == L) return true;
	return false;
}
 
void print(LinkList L) {
	LNode* s = L->next->next;
	while (s != L->next) {
 
		cout << s->data << " ";
		s = s->next;
	}
	cout << endl;
}
 
int main() {
 
	LinkList L;
	//List_HeadInsert(L);
	//cout << "头插法的结果" << endl;
	//print(L);
	List_TailInsert(L);
	cout << L->data << endl;
	cout << "尾插法的结果" << endl;
	print(L);
	cout << "链表的第1个元素：" << GetElem(L, 1)->data << endl;
	cout << "链表的第5个元素：" << GetElem(L, 5)->data << endl;
	cout << "链表的长度：" << Length(L) << endl;
	int e;
 
	ListDelete(L, 5, e);
	cout << "删除的第5个元素是：" << e << endl;
	cout << "当前的链表" << endl;
	print(L);
	ListInsert(L, 5, e);
	cout << "插入的第5个元素是：" << e << endl;
	cout << "当前的链表" << endl;
	print(L);
 
	ListDelete(L, 1, e);
	cout << "删除的第1个元素是：" << e << endl;
	cout << "当前的链表" << endl;
	print(L);
	ListInsert(L, 1, e);
	cout << "插入的第1个元素是：" << e << endl;
	cout << "当前的链表" << endl;
	print(L);
 
	LNode* s = LocateElem(L, 5);
	DeleteNode(L, s);
	print(L);
 
	return 0;
}
/*
输入样例：
1 2 3 4 5
*/
6.循环双链表
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
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;
	L->next = L;
	return true;
}
 
//判断双链表是否为空
bool empty(DLinkList L) {
	if (L->next = L) {
		return true;
	}
	return false;
}
 
bool isTail(DLinkList L, DNode* p) {
	if (p->next == L) return true;
	return false;
}
 
//按位查找：返回第i个结点
DNode* GetElem(DLinkList L, int i) {
	if (i < 0) return NULL;
	if (i == 0) return L;
	int j = 1;
	DNode* p = L->next;
	while (p != L && j < i) {
		p = p->next;
		j++;
	}
	if (p == L) return NULL;
	return p;
}
 
//按值查找：找到第一个数据域为e的结点
DNode* LocateElem(DLinkList L, ElemType e) {
	DNode* p = L;
	if (p == NULL) return NULL;
	p = p->next;
	while (p != L && p->data != e) {
		p = p->next;
	}
	if (p == L) return NULL;
	return p;
}
 
//在p节点之后插入s节点
bool InsertNextDNode(DNode* p, DNode* s) {
	if (p == NULL || s == NULL) {
		return false;
	}
	s->next = p->next;
	p->next->prior = s;
	s->prior = p;
	p->next = s;
}
 
//在p节点后面插入值是e的节点
bool InsertNextDNode(DNode* p, ElemType e) {
	if (p == NULL) return false;
	DNode* q = (DNode*)malloc(sizeof(DNode));
	if (q == NULL) return false;
	q->data = e;
	q->prior = p;
	p->next->prior = q;
	q->next = p->next;
	p->next = q;
	return true;
}
 
//前插，在p节点前面插入节点s
bool InsertPriorDnode(DNode* p, DNode* s) {
	return InsertNextDNode(p->prior, s);
}
 
//按位插入，在第i个位置插入值为e的节点（位序i）
bool InsertDLinkList(DLinkList& L, int i, ElemType e) {
	if (i <= 0) return false;
	DNode* p = GetElem(L, i - 1);
	return InsertNextDNode(p, e);
}
 
//删除p节点的后继节点
bool DeleteNextNode(DNode* p) {
	if (p == NULL) return false;
	DNode* q = p->next;
	p->next = q->next;
	q->next->prior = p; 
	free(q);
	return true;
}
 
//销毁双链表
bool DestoryList(DLinkList& L) {
	while (L->next != L) {
		DeleteNextNode(L);
	}
	free(L);
	L = NULL;
	return true;
}
 
//尾插法
DLinkList List_TailInsert(DLinkList& L) {
	InitDLinkList(L);
	DNode* p = L;
	ElemType x;
	while (cin >> x) {
		InsertNextDNode(p, x);
		p = p->next;
	}
	return L;
}
 
//头插法
DLinkList List_HeadInsert(DLinkList& L) {
	InitDLinkList(L);
	ElemType x;
	while (cin >> x) {
		InsertNextDNode(L, x);
	}
	return L;
}
 
int Length(DLinkList L) {
	DNode* p = L;
	int len = 0;
	while (p->next != L) {
		len++;
		p = p->next;
	}
	return len;
}
 
 
//删除指定节点s
bool DeleteNode(DNode* s) {
	DNode* p;
	p = s->prior;
	p->next = s->next;
	s->next->prior = p;
	free(s);
	return true;
}
 
//删除位序i的节点，e是i节点的值
bool ListDelete(DLinkList& L, int i, ElemType& e) {
	if (i <= 0 || i > Length(L)) return false;
	DNode* s;
	s = GetElem(L, i);
	if (s == NULL) return false;
	e = s->data;
	return DeleteNode(s);
}
 
 
void print(DLinkList L) {
	DNode* p = L->next;
	while (p != L) {
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}
 
void testDLinkList() {
	DLinkList L;
	//cout << "头插法" << endl;
	//List_HeadInsert(L);
	//print(L);
	cout << "尾插法" << endl;
	List_TailInsert(L);
	print(L);
	cout << "长度：" << Length(L) << endl;
	cout << "第1个元素为：" << GetElem(L, 1)->data << endl;
	cout << "第5个元素为：" << GetElem(L, 5)->data << endl;
	cout << "在第一个位置插入元素0" << endl;
	InsertDLinkList(L, 1, 0);
	print(L);
	cout << "在最后一个位置插入元素6" << endl;
	InsertDLinkList(L, 7, 6);
	print(L);
 
	int e;
	ListDelete(L, 1, e);
	cout << "删除第一个节点：" << e << endl;
	cout << "当前链表为" << endl;
	print(L);
 
	ListDelete(L, 6, e);
	cout << "删除最后一个节点：" << e << endl;
	cout << "当前链表为" << endl;
	print(L);
 
	DestoryList(L);
}
 
int main() {
 
	testDLinkList();
	return 0;
}
7.静态链表
#include<iostream>
 
using namespace std;
 
#define MaxSize 10
#define ElemType int
 
typedef struct {
	ElemType data;
	int next;
}SLinkList[MaxSize];
 
 
void InitSLinkList(SLinkList L) {
	for (int i = 0; i < MaxSize; i++) {
		L[i].next = -2;		//-2表时链表这个位置是空的
	}
	L[0].next = -1;
}
 
 
//判断双链表是否为空
bool empty(SLinkList L) {
	if (L[0].next = -1) {
		return true;
	}
	return false;
}
 
//得到第i个元素的下标
int Get_Index(SLinkList L, int i) {
	int j = 0;	//模拟指针
	int cnt = 0;		//计数
	while (j != -1 && cnt < i) {
		cnt++;
		j = L[j].next;
		//cout << j << " " << L[j].next << endl;
	}
	if (cnt != i) return -1;	//不存在
	return j;
}
 
//得到第一个是空的元素
int Get_First_Empty_Node(SLinkList L) {
	for (int i = 1; i < MaxSize; i++) {
		if (L[i].next == -2) return i;
 	}
}
 
//	返回L的第i个元素
ElemType GetElem(SLinkList L, int i) {
	int j = Get_Index(L, i);
	return L[j].data;
}
 
//在第i个节点后面插入值是e的节点
bool InsertNextSNode(SLinkList L, int i, ElemType e) {
	int j = Get_Index(L, i);
	//cout << j << endl;
	int k = Get_First_Empty_Node(L);	//第一个空节点的位置
	
	L[k].next = L[j].next;
	L[j].next = k;
	L[k].data = e;
	return true;
 
}
 
//删除第i个节点 e是删除元素的值
bool DeleteNode(SLinkList L, int i, ElemType& e) {
	int j = Get_Index(L, i);
	//cout <<i<< "  " << j << endl;
	if (L[j].next == -1) {	//最后一个要特判
		//cout << "asdad" << endl;
		int k = Get_Index(L, i - 1);
		L[j].next = -2;
		e = L[j].data;
		L[k].next = -1;
		return true;
	}
	//相当于交换次序，跟王道之前的删除方法类似
	e = L[j].data;
	int tmp = L[j].next;
	L[j].data = L[L[j].next].data;
	L[j].next = L[L[j].next].next;
	L[tmp].next = -2;
	return true;
}
 
//插入(默认开始是空的)
bool List_Insert(SLinkList L) {
	int tot = 1 , pre = 0;
	ElemType x;
	while (cin >> x) {
		L[tot].data = x;
		L[tot].next = -1;
		L[pre].next = tot;
		pre = tot++;
	}
	return true;
}
 
void print(SLinkList L) {
	int i = L[0].next;
	while (~i) {
		cout << L[i].data << " ";
		i = L[i].next;
	}
	cout << endl;
}
 
void testSLinkList() {
	
	SLinkList L;
	
	InitSLinkList(L);
	
	List_Insert(L);
	print(L);
 
	cout <<"第1个元素是："<< GetElem(L, 1) << endl;
	cout <<"第3个元素是："<< GetElem(L, 3) << endl;
	cout <<"第5个元素是："<< GetElem(L, 5) << endl;
 
	InsertNextSNode(L, 0, 0);
	print(L);
	InsertNextSNode(L, 1, 6);
	print(L);
	InsertNextSNode(L, 7, 7);
	print(L);
 
	//cout << "-------------" << endl;
	//for (int i = 0; i <= 8; i++) {
	//	cout << L[i].next << endl;
	//}
 
	int e;
	DeleteNode(L, 8, e);
	cout << e << endl;
	print(L);
 
	DeleteNode(L, 2, e);
	cout << e << endl;
	print(L);
 
	DeleteNode(L, 1, e);
	cout << e << endl;
	print(L);
}
 
int main() {
 
 
	testSLinkList();
	return 0;
}
/*
1 2 3 4 5
 */
二、栈和队列
1.顺序栈
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
#define MaxSize 50
 
typedef struct {
	ElemType data[MaxSize];
	int top;
}SqStack;
 
void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool Push(SqStack& S, ElemType x);
bool Pop(SqStack& S, ElemType &x);
bool GetTop(SqStack S, ElemType& x);
bool DestoryStack(SqStack& S);
 
void InitStack(SqStack& S) {
	S.top = -1;
}
 
bool StackEmpty(SqStack S) {
	if (S.top == -1) {
		return true;
	}
	return false;
}
 
bool Push(SqStack& S, ElemType x) {
	if (S.top == MaxSize - 1) {
		return false;
	}
	S.data[++S.top] = x;
	return true;
}
 
bool Pop(SqStack& S, ElemType& x) {
	if (S.top == -1) return false;
	x = S.data[S.top--];
	return true;
}
 
bool GetTop(SqStack S, ElemType& x) {
	if (S.top == -1) return false;
	x = S.data[S.top];
	return true;
}
 
void test() {
 
	SqStack S;
	InitStack(S);
	for (int i = 0; i <= 5; i++) {
		Push(S, i);
	}
	ElemType x;
	GetTop(S, x);
	cout << x << endl;
	while (!StackEmpty(S)) {
		Pop(S, x);
		cout << x << endl;
	}
 
}
 
int main() {
		
	test();
	return 0;
}
2.共享栈
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
#define MaxSize 10
 
typedef struct {
	ElemType data[MaxSize];
	int top0;
	int top1;
}ShStack;
 
void InitStack(ShStack& S);
bool StackEmpty(ShStack S);
bool StackFull(ShStack S);	//判断栈是否满了
bool Push0(ShStack& S, ElemType x);
bool Push1(ShStack& S, ElemType x);
bool Pop0(ShStack& S, ElemType& x);
bool Pop1(ShStack& S, ElemType& x);
bool GetTop0(ShStack S, ElemType& x);
bool GetTop1(ShStack S, ElemType& x);
bool DestoryStack0(ShStack& S);
bool DestoryStack1(ShStack& S);
 
void InitStack(ShStack& S) {
	S.top0 = -1;
	S.top1 = MaxSize;
}
 
bool StackEmpty(ShStack S) {
	if (S.top0 == -1 && S.top1 == MaxSize) {
		return true;
	}
	return false;
}
 
bool StackFull(ShStack S) {
	if (S.top0 + 1 == S.top1) return true;
	return false;
}
 
bool Push0(ShStack& S, ElemType x) {
	if (StackFull(S) ){
		return false;
	}
	S.data[++S.top0] = x;
	return true;
}
 
bool Push1(ShStack& S, ElemType x) {
	if (StackFull(S) ){
		return false;
	}
	S.data[--S.top1] = x;
	return true;
}
 
bool Pop0(ShStack& S, ElemType& x) {
	if (S.top0 == -1) return false;
	x = S.data[S.top0--];
	return true;
}
 
bool Pop1(ShStack& S, ElemType& x) {
	if (S.top1 == MaxSize) return false;
	x = S.data[S.top1++];
	return true;
}
 
bool GetTop0(ShStack S, ElemType& x) {
	if (S.top0 == -1) return false;
	x = S.data[S.top0];
	return true;
}
 
bool GetTop1(ShStack S, ElemType& x) {
	if (S.top1 == MaxSize) return false;
	x = S.data[S.top1];
	return true;
}
 
void test() {
 
	ShStack S;
	InitStack(S);
	for (int i = 1; i <= 5; i++) {
		Push0(S, i);
	}
	for (int i = 1; i <= 5; i++) {
		Push1(S, i);
	}
	ElemType x;
	GetTop0(S, x);
	cout << x << endl;
 
	GetTop1(S, x);
	cout << x << endl;
 
	bool f = Push0(S, 6);
	if (f) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
 
	f = Push1(S, 6);
	if (f) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
 
	while (Pop0(S,x)) {
		cout << x << endl;
	}
	while (Pop1(S, x)) {
		cout << x << endl;
	}
}
 
int main() {
 
	test();
	return 0;
}
3.链栈（带头）
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
typedef struct LinkNode {
	ElemType data;
	struct LinkNode* next;
}*LiStack,LinkNode;
 
 
bool InitStack(LiStack& S);
bool StackEmpty(LiStack S);
bool Push(LiStack& S, ElemType x);
bool Pop(LiStack& S, ElemType& x);
bool GetTop(LiStack S, ElemType& x);
bool DestoryStack(LiStack& S);
 
bool InitStack(LiStack& S) {
	S = (LiStack)malloc(sizeof(LinkNode));
	if (S == NULL) return false;
	S->next = NULL;
	return true;
}
 
bool StackEmpty(LiStack S) {
	if (S->next == NULL) return true;
	return false;
}
 
bool Push(LiStack& S, ElemType x) {
	LinkNode* p;
	p = (LinkNode*)malloc(sizeof(LinkNode));
	if (p == NULL) return false;
	p->data = x;
	p->next = S->next;
	S->next = p;
	return true;
}
 
bool Pop(LiStack& S, ElemType& x) {
	if (StackEmpty(S)) return false;
	LinkNode* p = S->next;
	S->next = p->next;
	x = p->data;
	free(p);
	return true;
}
 
bool GetTop(LiStack S, ElemType& x) {
	if (StackEmpty(S)) return false;
	x = S->next->data;
	return true;
}
 
bool DestoryStack(LiStack& S) {
	while (S->next != NULL) {
		LinkNode* p = S->next;
		S->next = p->next;
		free(p);
	}
	free(S);
	return true;
}
 
void test() {
 
	LiStack S;
	InitStack(S);
	for (int i = 0; i <= 5; i++) {
		Push(S, i);
	}
	ElemType x;
	GetTop(S, x);
	cout << x << endl;
	while (!StackEmpty(S)) {
		Pop(S, x);
		cout << x << endl;
	}
}
 
int main() {
		
	test();
	return 0;
}
4.链栈（不带头）
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
typedef struct LinkNode {
	ElemType data;
	struct LinkNode* next;
}*LiStack, LinkNode;
 
 
bool InitStack(LiStack& S);
bool StackEmpty(LiStack S);
bool Push(LiStack& S, ElemType x);
bool Pop(LiStack& S, ElemType& x);
bool GetTop(LiStack S, ElemType& x);
bool DestoryStack(LiStack& S);
 
bool InitStack(LiStack& S) {
	S = NULL;
	return true;
}
 
bool StackEmpty(LiStack S) {
	if (S == NULL) return true;
	return false;
}
 
bool Push(LiStack& S, ElemType x) {
	LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));
	if (p == NULL) return false;
	p->data = x;
	p->next = S;
	S = p;
	return true;
}
 
bool Pop(LiStack& S, ElemType& x) {
	if (StackEmpty(S)) return false;
	LinkNode* p = S;
	S = S->next;
	x = p->data;
	free(p);
	return true;
}
 
bool GetTop(LiStack S, ElemType& x) {
	if (StackEmpty(S)) {
		return false;
	}
	x = S->data;
	return true;
}
 
bool DestoryStack(LiStack& S) {
	while (S != NULL) {
		LinkNode* p = S;
		S = S->next;
		free(p);
	}
	free(S);
	S = NULL;
	return true;
}
 
void test() {
 
	LiStack S;
	InitStack(S);
	for (int i = 0; i <= 5; i++) {
		Push(S, i);
	}
	ElemType x;
	GetTop(S, x);
	cout << x << endl;
	while (!StackEmpty(S)) {
		Pop(S, x);
		cout << x << endl;
	}
 
}
 
int main() {
		
	test();
	return 0;
}
5.顺序队列
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
#define MaxSize 5
 
typedef struct {
	int front, rear;
	ElemType data[MaxSize];
}SqQueue;
 
void InitQueue(SqQueue &Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue &Q, ElemType x);
bool DeQueue(SqQueue &Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
 
void InitQueue(SqQueue &Q) {
	Q.front = Q.rear = 0;
}
 
bool QueueEmpty(SqQueue Q) {
	if (Q.front == Q.rear) return true;
	return false;
}
 
bool QueueFull(SqQueue Q) {
	if (Q.rear == MaxSize) return true;
	return false;
}
 
bool EnQueue(SqQueue &Q, ElemType x) {
	if (QueueFull(Q)) return false; //队满
	Q.data[Q.rear++] = x;
	return true;
}
 
bool DeQueue(SqQueue& Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front++];
	return true;
}
 
bool GetHead(SqQueue Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	return true;
}
 
void test() {
 
	SqQueue Q;
	InitQueue(Q);
	for (int i = 1; i <= 5; i++) {
		EnQueue(Q, i);
	}
	if (!EnQueue(Q, 6)) {
		cout << "队列已满" << endl;
	}
	ElemType x;
	GetHead(Q, x);
	cout << x << endl << endl;
	while (!QueueEmpty(Q)) {
		
		DeQueue(Q, x);
		cout << x << endl;
	}
 
}
 
int main() {
 
	test();
	return 0;
}
6.循环队列
6.1 rear指向队尾指针后一个位置and牺牲一个存储空间来区分队空和队满
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
#define MaxSize 5
 
typedef struct {
	int front, rear;
	ElemType data[MaxSize];
}SqQueue;
 
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q);  //返回队列元素的个数
 
void InitQueue(SqQueue& Q) {
	Q.front = Q.rear = 0;
}
 
bool QueueEmpty(SqQueue Q) {
	if (Q.front == Q.rear) return true;
	return false;
}
 
bool QueueFull(SqQueue Q) {
	if ((Q.rear + 1) % MaxSize == Q.front) return true;
	return false;
}
 
bool EnQueue(SqQueue& Q, ElemType x) {
	if (QueueFull(Q)) return false; //队满
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
	return true;
}
 
bool DeQueue(SqQueue& Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	return true;
}
 
bool GetHead(SqQueue Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	return true;
}
 
int GetSize(SqQueue Q) {
	return (Q.rear - Q.front + MaxSize) % MaxSize;
}
 
void test() {
 
	SqQueue Q;
	InitQueue(Q);
	
 
	for (int i = 1; i <= 5; i++) {
		bool f = EnQueue(Q, i);
		if (!f) cout << i << endl;
	}
 
	ElemType x;
	DeQueue(Q, x);
	cout << x << endl;
	DeQueue(Q, x);
	cout << x << endl;
	EnQueue(Q, 1);
	EnQueue(Q, 2);
	cout << Q.front << " " << Q.rear << endl;
	if (!EnQueue(Q, 6)) {
		cout << "队列已满" << endl;
	}
	
	GetHead(Q, x);
	cout << x << endl << endl;
	while (!QueueEmpty(Q)) {
 
		DeQueue(Q, x);
		cout << x << endl;
	}
 
}
 
int main() {
 
	test();
	return 0;
}
6.2 rear指向队尾指针后一个位置and增设size判断
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
#define MaxSize 5
 
typedef struct {
	int front, rear;
	int size;
	ElemType data[MaxSize];
}SqQueue;
 
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q);  //返回队列元素的个数
 
void InitQueue(SqQueue& Q) {
	Q.front = Q.rear = Q.size = 0;
}
 
bool QueueEmpty(SqQueue Q) {
	if (Q.size == 0) return true;
	return false;
}
 
bool QueueFull(SqQueue Q) {
	if (Q.size == MaxSize) return true;
	return false;
}
 
bool EnQueue(SqQueue& Q, ElemType x) {
	if (QueueFull(Q)) return false; //队满
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.size++;
	return true;
}
 
bool DeQueue(SqQueue& Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	Q.size--;
	return true;
}
 
bool GetHead(SqQueue Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	return true;
}
 
int GetSize(SqQueue Q) {
	return Q.size;
}
 
void test() {
 
	SqQueue Q;
	InitQueue(Q);
 
 
	for (int i = 1; i <= 5; i++) {
		bool f = EnQueue(Q, i);
		if (!f) cout << i << endl;
	}
 
	ElemType x;
	DeQueue(Q, x);
	cout << x << endl;
	DeQueue(Q, x);
	cout << x << endl;
	EnQueue(Q, 1);
	EnQueue(Q, 2);
	cout << Q.front << " " << Q.rear << endl;
	if (!EnQueue(Q, 6)) {
		cout << "队列已满" << endl;
	}
 
	GetHead(Q, x);
	cout << x << endl << endl;
	while (!QueueEmpty(Q)) {
 
		DeQueue(Q, x);
		cout << x << endl;
	}
 
}
 
int main() {
 
	test();
	return 0;
}
6.3 rear指向队尾指针后一个位置and增设tag判断
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
#define MaxSize 5
 
typedef struct {
	int front, rear;
	int tag;
	ElemType data[MaxSize];
}SqQueue;
 
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q);  //返回队列元素的个数
 
void InitQueue(SqQueue& Q) {
	Q.front = Q.rear = Q.tag = 0;
}
 
bool QueueEmpty(SqQueue Q) {
	if (Q.tag == 0 && Q.front == Q.rear) return true;
	return false;
}
 
bool QueueFull(SqQueue Q) {
	if (Q.tag == 1 && Q.front == Q.rear) return true;
	return false;
}
 
bool EnQueue(SqQueue& Q, ElemType x) {
	if (QueueFull(Q)) return false; //队满
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.tag = 1;
	return true;
}
 
bool DeQueue(SqQueue& Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	Q.tag = 0;
	return true;
}
 
bool GetHead(SqQueue Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	return true;
}
 
int GetSize(SqQueue Q) {
	return (Q.rear - Q.front + MaxSize) % MaxSize;
}
 
void test() {
 
	SqQueue Q;
	InitQueue(Q);
 
 
	for (int i = 1; i <= 5; i++) {
		bool f = EnQueue(Q, i);
		if (!f) cout << i << endl;
	}
 
	ElemType x;
	DeQueue(Q, x);
	cout << x << endl;
	DeQueue(Q, x);
	cout << x << endl;
	EnQueue(Q, 1);
	EnQueue(Q, 2);
	cout << Q.front << " " << Q.rear << endl;
	if (!EnQueue(Q, 6)) {
		cout << "队列已满" << endl;
	}
 
	GetHead(Q, x);
	cout << x << endl << endl;
	while (!QueueEmpty(Q)) {
 
		DeQueue(Q, x);
		cout << x << endl;
	}
 
}
 
int main() {
 
	test();
	return 0;
}
6.4 rear指向队尾and牺牲一个存储空间来区分队空和队满
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
#define MaxSize 5
 
typedef struct {
	int front, rear;
	ElemType data[MaxSize];
}SqQueue;
 
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q);  //返回队列元素的个数
 
void InitQueue(SqQueue& Q) {
	Q.front =  0;
	Q.rear = -1;
}
 
bool QueueEmpty(SqQueue Q) {
	if (Q.front == Q.rear+1 ) return true;
	return false;
}
 
bool QueueFull(SqQueue Q) {
	if ((Q.rear + 2) % MaxSize == Q.front) return true;
	return false;
}
 
bool EnQueue(SqQueue& Q, ElemType x) {
	if (QueueFull(Q)) return false; //队满
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.data[Q.rear] = x;
	return true;
}
 
bool DeQueue(SqQueue& Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	return true;
}
 
bool GetHead(SqQueue Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	return true;
}
 
int GetSize(SqQueue Q) {
	return (Q.rear - Q.front +1 + MaxSize) % MaxSize;
}
 
void test() {
 
	SqQueue Q;
	InitQueue(Q);
 
 
	for (int i = 1; i <= 5; i++) {
		bool f = EnQueue(Q, i);
		if (!f) cout << i << endl;
	}
 
	ElemType x;
	DeQueue(Q, x);
	cout << x << endl;
	DeQueue(Q, x);
	cout << x << endl;
	EnQueue(Q, 1);
	EnQueue(Q, 2);
	cout << Q.front << " " << Q.rear << endl;
	if (!EnQueue(Q, 6)) {
		cout << "队列已满" << endl;
	}
 
	GetHead(Q, x);
	cout << x << endl << endl;
	while (!QueueEmpty(Q)) {
 
		DeQueue(Q, x);
		cout << x << endl;
	}
 
}
 
int main() {
 
	test();
	return 0;
}
6.2 rear指向队尾and增设size判断
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
#define MaxSize 5
 
typedef struct {
	int front, rear;
	int size;
	ElemType data[MaxSize];
}SqQueue;
 
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q);  //返回队列元素的个数
 
void InitQueue(SqQueue& Q) {
	Q.front = 0;
	Q.rear = -1;
	Q.size = 0;
}
 
bool QueueEmpty(SqQueue Q) {
	if (Q.size == 0) return true;
	return false;
}
 
bool QueueFull(SqQueue Q) {
	if (Q.size == MaxSize) return true;
	return false;
}
 
bool EnQueue(SqQueue& Q, ElemType x) {
	if (QueueFull(Q)) return false; //队满
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.data[Q.rear] = x;
	Q.size++;
	return true;
}
 
bool DeQueue(SqQueue& Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	Q.size--;
	return true;
}
 
bool GetHead(SqQueue Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	return true;
}
 
int GetSize(SqQueue Q) {
	return Q.size;
}
 
void test() {
 
	SqQueue Q;
	InitQueue(Q);
 
 
	for (int i = 1; i <= 5; i++) {
		bool f = EnQueue(Q, i);
		if (!f) cout << i << endl;
	}
 
	ElemType x;
	DeQueue(Q, x);
	cout << x << endl;
	DeQueue(Q, x);
	cout << x << endl;
	EnQueue(Q, 1);
	EnQueue(Q, 2);
	cout << Q.front << " " << Q.rear << endl;
	if (!EnQueue(Q, 6)) {
		cout << "队列已满" << endl;
	}
 
	GetHead(Q, x);
	cout << x << endl << endl;
	while (!QueueEmpty(Q)) {
 
		DeQueue(Q, x);
		cout << x << endl;
	}
 
}
 
int main() {
 
	test();
	return 0;
}
6.3 rear指向队尾and增设tag判断
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
#define MaxSize 5
 
typedef struct {
	int front, rear;
	int tag;
	ElemType data[MaxSize];
}SqQueue;
 
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q);  //返回队列元素的个数
 
void InitQueue(SqQueue& Q) {
	Q.front = 0;
	Q.rear = -1;
	Q.tag = 0;
}
 
bool QueueEmpty(SqQueue Q) {
	if (Q.front == Q.rear + 1 && Q.tag == 0) return true;
	return false;
}
 
bool QueueFull(SqQueue Q) {
	if (Q.front == Q.rear + 1 && Q.tag == 1) return true;
	return false;
}
 
bool EnQueue(SqQueue& Q, ElemType x) {
	if (QueueFull(Q)) return false; //队满
	Q.rear = (Q.rear + 1) % MaxSize;
	Q.data[Q.rear] = x;
	Q.tag = 1;
	return true;
}
 
bool DeQueue(SqQueue& Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;
	Q.tag = 0;
	return true;
}
 
bool GetHead(SqQueue Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	x = Q.data[Q.front];
	return true;
}
 
int GetSize(SqQueue Q) {
	return (Q.rear - Q.front + 1 + MaxSize) % MaxSize;
}
 
void test() {
 
	SqQueue Q;
	InitQueue(Q);
 
 
	for (int i = 1; i <= 5; i++) {
		bool f = EnQueue(Q, i);
		if (!f) cout << i << endl;
	}
 
	ElemType x;
	DeQueue(Q, x);
	cout << x << endl;
	DeQueue(Q, x);
	cout << x << endl;
	EnQueue(Q, 1);
	EnQueue(Q, 2);
	cout << Q.front << " " << Q.rear << endl;
	if (!EnQueue(Q, 6)) {
		cout << "队列已满" << endl;
	}
 
	GetHead(Q, x);
	cout << x << endl << endl;
	while (!QueueEmpty(Q)) {
 
		DeQueue(Q, x);
		cout << x << endl;
	}
 
}
 
int main() {
 
	test();
	return 0;
}
7.链队列（带头）
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
typedef struct LinkNode {
	ElemType data;
	struct LinkNode* next;
}LinkNode;
 
typedef struct {
	LinkNode* front, * rear;
}LinkQueue;
 
 
void InitQueue(LinkQueue& Q);
bool QueueEmpty(LinkQueue Q);
bool EnQueue(LinkQueue& Q, ElemType x);
bool DeQueue(LinkQueue& Q, ElemType& x);
bool GetHead(LinkQueue Q, ElemType& x);
 
void InitQueue(LinkQueue& Q) {
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next = NULL;
}
 
bool QueueEmpty(LinkQueue Q) {
	if (Q.front == Q.rear) return true;
	return false;
}
 
bool EnQueue(LinkQueue& Q, ElemType x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = Q.rear->next;
	Q.rear->next = s;
	Q.rear = s;
	return true;
}
 
bool DeQueue(LinkQueue& Q, ElemType& x) {
	if (QueueEmpty(Q)) return false;
	LinkNode* q = Q.front->next;
	x = q->data;
	Q.front->next = q->next;
	if (Q.rear == q) {
		Q.rear = Q.front;
	}
	free(q);
	return true;
}
 
bool GetHead(LinkQueue Q, ElemType& x) {
	if (QueueEmpty(Q)) return false;
	x = Q.front->next->data;
	return true;
}
 
void test() {
 
	LinkQueue Q;
	InitQueue(Q);
	for (int i = 1; i <= 5; i++) {
		EnQueue(Q, i);
	}
	ElemType x;
	GetHead(Q, x);
	cout << x << endl << endl;
	while (!QueueEmpty(Q)) {
 
		DeQueue(Q, x);
		cout << x << endl;
	}
 
}
 
int main() {
		
	test();
	return 0;
}
8.链队列（不带头）
#include<iostream>
 
using namespace std;
 
typedef int ElemType;
 
typedef struct LinkNode {
	ElemType data;
	struct LinkNode* next;
}LinkNode;
 
typedef struct {
	LinkNode* front, * rear;
}LinkQueue;
 
void InitQueue(LinkQueue& Q);
bool QueueEmpty(LinkQueue Q);
bool EnQueue(LinkQueue& Q, ElemType x);
bool DeQueue(LinkQueue& Q, ElemType& x);
bool GetHead(LinkQueue Q, ElemType& x);
 
void InitQueue(LinkQueue& Q) {
	Q.front = Q.rear = NULL;
}
 
bool QueueEmpty(LinkQueue Q) {
	if (Q.front == NULL) return true;
	return false;
}
 
bool EnQueue(LinkQueue& Q, ElemType x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	if (QueueEmpty(Q)) {
		Q.front = Q.rear = s;
	}
	else {
		Q.rear->next = s;
		Q.rear = s;
	}
	return true;
}
 
bool DeQueue(LinkQueue& Q, ElemType& x) {
	if (QueueEmpty(Q)) {
		return false;
	}
	LinkNode* s = Q.front;
	x = s->data;
	if (Q.rear == s) {
		Q.front = Q.rear = NULL;
	}
	else {
		Q.front = s->next;
	}
	free(s);
	return true;
}
 
bool GetHead(LinkQueue Q, ElemType& x) {
	if (QueueEmpty(Q)) return false;
	x = Q.front->data;
	return true;
}
 
void test() {
	LinkQueue Q;
	InitQueue(Q);
	for (int i = 1; i <= 5; i++) {
		EnQueue(Q, i);
	}
	ElemType x;
	GetHead(Q, x);
	cout << x << endl << endl;
	while (!QueueEmpty(Q)) {
 
		DeQueue(Q, x);
		cout << x << endl;
	}
 
 
}
 
int main() {
 
	test();
	return 0;
}
三、串
1、串的基本操作
//这儿的下标默认是1开始
#include<iostream>
 
using namespace std;
 
#define MAXLEN 255
 
typedef struct{
    char ch[MAXLEN];
    int length;
}SString;
 
typedef struct {
    char *ch;
    int length;
}HString;
 
//初始化串
void InitSting(HString &S);
//赋值操作，把串T复制为chars
bool StrAssign(HString &T,HString chars);
//复制操作，由串S复制到T
bool StrCopy(HString &T,HString S);
//判空，是返回true，否则false
bool StrEmpty(HString S);
//若s>t 返回>0  s=t 返回=0  s<t 返回<0
int StrCompare(HString S,HString T);
//返回串长
int StrLength(HString S);
//求字串，用sub返回串s的第pos个位置开始的长度为len的串
bool SubString(HString &Sub,HString S,HString pos,HString len);
//字符串拼接，用T返回由S1和S2连接的新串
bool Concat(HString &T,HString S1,HString S2);
//返回串T在S中第一次出现的位置，不存在返回0
int Index(HString S,HString T);
//清空操作
bool ClearString(HString &S);
//销毁串
bool DestoryString(HString &S);
 
 
void InitSting(HString &S){
    S.ch = (char *)malloc(MAXLEN*sizeof(char));
    S.length = 0;
}
 
bool StrAssign(HString &T,char* chars){
    T.length = 0;
    for(int i=1;chars[i];i++){
        T.ch[i] = chars[i];
        T.length++;
    }
    return true;
}
 
bool StrCopy(HString &T,HString S){
    T = S;
    return true;
}
 
bool StrEmpty(HString S){
    if(S.length == 0) return true;
    return false;
}
 
int StrCompare(HString S,HString T){
    int i=1;
    while(i<S.length&&i<T.length){
        if(S.ch[i]!=T.ch[i]) return S.ch[i]-T.ch[i];
        i++;
    }
    return S.length-T.length;
}
 
int StrLength(HString S){
    return S.length;
}
 
bool SubString(HString &Sub,HString S,int pos,int len){
    if(pos+len-1>S.length) return false;
    for(int i=1;i<=len;i++){
        Sub.ch[i] = S.ch[pos+i-1];
    }
    Sub.ch[len+1] = '\0';
//    cout<<Sub.ch+1<<endl;
    Sub.length=len;
 
    return true;
}
 
bool Concat(HString &T,HString S1,HString S2){
    for(int i=1;i<=S1.length;i++){
        T.ch[i] = S1.ch[i];
    }
    for(int i=1;i<=S2.length;i++){
        T.ch[i+S1.length] = S2.ch[i];
    }
    T.length = S1.length+S2.length;
    return true;
}
 
int Index(HString S,HString T){
    int i=1,n=StrLength(S),m=StrLength(T);
    HString sub;
    InitSting(sub);
    while(i<n-m+1){
        SubString(sub,S,i,m);
//        cout<<sub.ch+1<<endl;
        if(StrCompare(T,sub)!=0) i++;
        else return i;
    }
    return 0;
}
 
bool ClearString(HString &S){
    S.length = 0;
    return true;
}
//销毁串
bool DestoryString(HString &S){
    free(S.ch);
    S.length = 0;
}
 
void test(){
 
    HString s,t;
    InitSting(s);
    InitSting(t);
    char *sr =" 123456";
    char *tr =" 345";
    StrAssign(s,sr);
    StrAssign(t,tr);
    printf("%d\n",Index(s,t));
}
 
int main(){
 
    test();
    return 0;
}
2、kmp模式匹配
//串匹配下标是从1开始的，如果要从0开始，next数组减一即可（同时求next判断条件等于0应该改为等于-1）
#include<iostream>
#include<cstring>
#include<cstdio>
 
const int maxn = 1e3+10;
 
char t[maxn];   //模式串
char s[maxn];   //主串
int next[maxn];
int nextval[maxn];
 
void get_next(char *t,int next[]){
    int i=1,j=0;
    int len = strlen(t+1);
    next[1]=0;
    while(i<=len){
        if(j==0||t[i]==t[j]){
            i++;
            j++;
            next[i] = j;
        }else{
            j = next[j];
        }
    }
}
 
void get_nextval(char *t,int next[]){
    int i=1,j=0;
    int len = strlen(t+1);
    nextval[1]=0;
    while(i<=len){
        if(j==0||t[i]==t[j]){
            i++;
            j++;
            if(t[i]!=t[j]){
                next[i] = j;
            }else{
                next[i] = next[j];
            }
        }else{
            j = next[j];
        }
    }
}
 
int KMP(char *s,char *t,int next[]){
    int lens = strlen(s+1);
    int lent = strlen(t+1);
    int i=1,j=1;
    while(i<=lens&&j<=lent){
        if(j == 0||s[i] == t[j]){
            i++;
            j++;
        }else{
            j = next[j];
        }
    }
    if(j>lent){
        return i - j + 1;
    }else{
        return 0;
    }
}
 
void test(){
    char *s=" aaabaaaab";
    char *t=" aaaab";
    get_next(t,next);
    printf("%d\n",KMP(s,t,next));
    get_nextval(t,next);
    printf("%d\n",KMP(s,t,next));
}
 
int main(){
 
 
    test();
    return 0;
}
四、树与二叉树
1、二叉树计算高度
#include<iostream>
 
using namespace std;
 
typedef char ElemType;
 
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
 
bool InitBiTree(BiTree& T); //初始化
int treeDepth(BiTree T);   //计算树的深度
 
bool InitBiTree(BiTree& T){
    ElemType ch;
    cin>>ch;
    if(ch=='#'){
        T = NULL;
    }else{
        T = (BiTNode*)malloc(sizeof(BiTNode));
        T->data = ch;
        InitBiTree(T->lchild);
        InitBiTree(T->rchild);
    }
}
 
int treeDepth(BiTree T){
    if(T==NULL) return 0;
    int l = treeDepth(T->lchild);
    int r = treeDepth(T->rchild);
    return l>r?l+1:r+1;
}
 
void test(){
    BiTree T;
    InitBiTree(T);
 
    cout<<treeDepth(T);
}
 
int main(){
 
    test();
    return 0;
}
/*
输入样例：
ABD##E##C##
输出样例：
3
*/
2、二叉树的先序，中序，后序遍历（递归）
#include<iostream>
 
using namespace std;
 
typedef char ElemType;
 
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
 
bool InitBiTree(BiTree& T); //初始化
void visit(BiTNode* p);     //打印节点信息
void PreOrder(BiTree T);    //先序遍历
void InOrder(BiTree T);     //中序遍历
void PostOrder(BiTree T);   //后序遍历
 
bool InitBiTree(BiTree& T){
    ElemType ch;
    cin>>ch;
    if(ch=='#'){
        T = NULL;
    }else{
        T = (BiTNode*)malloc(sizeof(BiTNode));
        T->data = ch;
        InitBiTree(T->lchild);
        InitBiTree(T->rchild);
    }
}
 
void visit(BiTNode* p){
    cout<<p->data<<" ";
}
 
void PreOrder(BiTree T){
    if(T==NULL) return ;
    visit(T);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}
 
void InOrder(BiTree T){
    if(T==NULL) return ;
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
}
 
void PostOrder(BiTree T){
    if(T==NULL) return ;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T);
}
 
void test(){
    BiTree T;
    InitBiTree(T);
    cout<<"先序遍历"<<endl;
    PreOrder(T);
    cout<<endl;
 
    cout<<"中序序遍历"<<endl;
    InOrder(T);
    cout<<endl;
 
    cout<<"后序遍历"<<endl;
    PostOrder(T);
    cout<<endl;
}
 
int main(){
 
    test();
    return 0;
}
/*
输入样例：
ABD##E##C##
输出样例：
先序遍历
A B D E C
中序序遍历
D B E A C
后序遍历
D E B C A
*/
3、二叉树的先序，中序，后序遍历（非递归）
#include<iostream>
 
using namespace std;
 
typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
 
typedef struct LinkNode {
	BiTNode *data;
	struct LinkNode* next;
}*LiStack,LinkNode;
 
 
bool InitStack(LiStack& S);
bool StackEmpty(LiStack S);
bool Push(LiStack& S, BiTNode* x);
bool Pop(LiStack& S, BiTNode*& x);
bool GetTop(LiStack S, BiTNode*& x);
bool DestoryStack(LiStack& S);
 
bool InitBiTree(BiTree& T); //初始化
void visit(BiTNode* p);     //打印节点信息
 
void PostOrder(BiTree T);   //后序遍历
void InOrder(BiTree T);     //先序遍历
void PreOrder(BiTree T);    //前序遍历
 
bool InitStack(LiStack& S) {
	S = (LiStack)malloc(sizeof(LinkNode));
	if (S == NULL) return false;
	S->next = NULL;
	return true;
}
 
bool StackEmpty(LiStack S) {
	if (S->next == NULL) return true;
	return false;
}
 
bool Push(LiStack& S, BiTNode* x) {
	LinkNode* p;
	p = (LinkNode*)malloc(sizeof(LinkNode));
	if (p == NULL) return false;
	p->data = x;
	p->next = S->next;
	S->next = p;
	return true;
}
 
bool Pop(LiStack& S, BiTNode*& x) {
	if (StackEmpty(S)) return false;
	LinkNode* p = S->next;
	S->next = p->next;
	x = p->data;
	free(p);
	return true;
}
 
bool GetTop(LiStack S, BiTNode*& x) {
	if (StackEmpty(S)) return false;
	x = S->next->data;
	return true;
}
 
bool InitBiTree(BiTree& T){
    char ch;
    cin>>ch;
    if(ch=='#'){
        T = NULL;
    }else{
        T = (BiTNode*)malloc(sizeof(BiTNode));
        T->data = ch;
        InitBiTree(T->lchild);
        InitBiTree(T->rchild);
    }
}
 
 
void visit(BiTNode* p){
    cout<<p->data<<" ";
}
 
 
void PostOrder(BiTree T){
    LiStack S;
    InitStack(S);
    BiTree p = T;
    BiTNode *r = NULL;   //辅助指针，指向最近访问的节点
    while(p||!StackEmpty(S)){
        if(p){                              //走到最左边
            Push(S,p);
            p = p->lchild;
        }else{                              //走到最右边
            GetTop(S,p);                    //读栈顶元素（非出栈）
            if(p->rchild&&p->rchild!=r){    //若右子树存在且未被访问过
                p = p->rchild;              //转向右
                Push(S,p);                  //压入栈
                p = p->lchild;              //再走到最左
            }else{                          //否则弹出栈顶元素并访问
                Pop(S,p);
                visit(p);
                r = p;                      //记录最近访问过的节点
                p = NULL;                   //节点访问完后重置p指针
            }
        }
    }
}
 
void InOrder(BiTree T){
    LiStack S;
    InitStack(S);
    BiTree p = T;               //遍历指针
    while(p||!StackEmpty(S)){   //
        if(p){                  //一路向左
            Push(S,p);          //当前节点入栈
            p = p->lchild;      //左孩子不为空一直向左走
        }else{                  //出栈，并转向该节点的右孩子
            Pop(S,p);           //栈顶结点出栈，访问
            visit(p);
            p = p->rchild;      //向右子树走，
        }
    }
}
 
void PreOrder(BiTree T){
    LiStack S;
    InitStack(S);
    BiTree p = T;               //遍历指针
    while(p||!StackEmpty(S)){   //
        if(p){                  //一路向左
            visit(p);
            Push(S,p);          //当前节点入栈
            p = p->lchild;      //左孩子不为空一直向左走
        }else{                  //出栈，并转向该节点的右孩子
            Pop(S,p);           //栈顶结点出栈
            p = p->rchild;      //向右子树走，
        }
    }
}
 
void test(){
    BiTree T;
    InitBiTree(T);
 
    cout<<"----------后序遍历----------"<<endl;
    PostOrder(T);
    cout<<endl;
 
    cout<<"----------中序遍历----------"<<endl;
    InOrder(T);
    cout<<endl;
 
    cout<<"----------先序遍历----------"<<endl;
    PreOrder(T);
    cout<<endl;
}
 
int main(){
 
    test();
    return 0;
}
/*
输入样例：
ABD##E##C##
输出样例：
----------后序遍历----------
D E B C A
----------中序遍历----------
D B E A C
----------先序遍历----------
A B D E C
*/
4、二叉树的层序遍历
#include<iostream>
 
using namespace std;
 
typedef char ElemType;
 
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
 
 
typedef struct LinkNode {
	BiTNode* data;
	struct LinkNode* next;
}LinkNode;
 
typedef struct {
	LinkNode* front, * rear;
}LinkQueue;
 
 
bool InitBiTree(BiTree& T); //初始化树
void LevelOrder(BiTree T);  //层序遍历
void InitQueue(LinkQueue& Q);
bool QueueEmpty(LinkQueue Q);
bool EnQueue(LinkQueue& Q, BiTNode* x);
bool DeQueue(LinkQueue& Q, BiTNode*& x);
void visit(BiTNode* p);
 
void InitQueue(LinkQueue& Q) {
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next = NULL;
}
 
bool QueueEmpty(LinkQueue Q) {
	if (Q.front == Q.rear) return true;
	return false;
}
 
bool EnQueue(LinkQueue& Q, BiTNode* x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = Q.rear->next;
	Q.rear->next = s;
	Q.rear = s;
	return true;
}
 
bool DeQueue(LinkQueue& Q, BiTNode*& x) {
	if (QueueEmpty(Q)) return false;
	LinkNode* q = Q.front->next;
	x = q->data;
	Q.front->next = q->next;
	if (Q.rear == q) {
		Q.rear = Q.front;
	}
	free(q);
	return true;
}
 
bool InitBiTree(BiTree& T){
    ElemType ch;
    cin>>ch;
    if(ch=='#'){
        T = NULL;
    }else{
        T = (BiTNode*)malloc(sizeof(BiTNode));
        T->data = ch;
        InitBiTree(T->lchild);
        InitBiTree(T->rchild);
    }
}
 
void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T);
    while(!QueueEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL){
            EnQueue(Q,p->lchild);
        }
        if(p->rchild!=NULL){
            EnQueue(Q,p->rchild);
        }
    }
}
 
void visit(BiTNode* p){
    cout<<p->data<<" ";
}
 
void test(){
    BiTree T;
    InitBiTree(T);
    LevelOrder(T);
}
 
int main(){
 
    test();
    return 0;
}
/*
输入数据：
ABD##E##C##
输出数据：
A B C D E
*/
5、中序线索化二叉树
#include<iostream>
 
using namespace std;
 
typedef char ElemType;
 
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;
 
ThreadNode *pre;    //指向当前访问节点的前驱
 
 
void InitTree(ThreadTree& T);//初始化树
void visit(ThreadNode* q);
void InThread(ThreadTree T);//中序遍历二叉树，
void CreatInThread(ThreadTree T);//建立中序线索化二叉树
 
/*--------------------------*/
/*中序线索二叉树中找中序后继*/
ThreadNode* Firstnode(ThreadNode* p);//找中序线索二叉树中中序序列下的第一个节点
ThreadNode* Nextnode(ThreadNode* p);//找中序线索二叉树中节点p在中序序列下的后继
void Inorder(ThreadTree T);//遍历线索二叉树
/*--------------------------*/
 
/*--------------------------*/
/*中序线索二叉树中找中序前驱*/
ThreadNode* Lastnode(ThreadNode* p);//找到以p为根的子树中，最后一个被中序遍历的节点
ThreadNode* Prenode(ThreadNode* p);//在中序线索二叉树中找到节点p的前驱节点
void RevInorder(ThreadTree T);//逆向遍历线索二叉树
/*--------------------------*/
 
//初始化树
void InitTree(ThreadTree& T){
    ElemType ch;
    cin>>ch;
    if(ch=='#'){
        T = NULL;
    }else{
        T = (ThreadNode*)malloc(sizeof(ThreadNode));
        T->data = ch;
        T->ltag = 0;
        T->rtag = 0;
        InitTree(T->lchild);
        InitTree(T->rchild);
    }
 
}
 
void visit(ThreadNode* q){
    if(q->lchild==NULL){        //左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag =1;
    }
    if(pre!=NULL && pre->rchild == NULL){     //建立前驱节点的后续线索
        pre->rchild = q;
        pre->rtag = 1;
    }
    pre = q;
}
 
//中序遍历二叉树，
void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);
        visit(T);
        InThread(T->rchild);
    }
}
 
//建立中序线索化二叉树
void CreatInThread(ThreadTree T){
    pre = NULL;
    if(T!=NULL){
        InThread(T);            //中序线索化二叉树
        if(pre->rchild == NULL){
            pre->rtag = 1;      //处理遍历的最后一个节点
        }
    }
}
 
/*--------------------------*/
/*中序线索二叉树中找中序后继*/
 
 
//找中序线索二叉树中中序序列下的第一个节点
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);
    return p->rchild;   //rtag==1直接返回后继线索
}
 
//遍历线索二叉树
void Inorder(ThreadTree T){
    for(ThreadNode* p=Firstnode(T);p!=NULL;p = Nextnode(p)){
        cout<<p->data<<" ";
    }
    cout<<endl;
}
 
 
/*--------------------------*/
 
 
 
/*--------------------------*/
/*中序线索二叉树中找中序前驱*/
 
//找到以p为根的子树中，最后一个被中序遍历的节点
ThreadNode* Lastnode(ThreadNode* p){
    //循环找到最右下节点（不一定是叶节点）
    while(p->rtag == 0) p = p->rchild;
    return p;
}
 
//在中序线索二叉树中找到节点p的前驱节点
ThreadNode* Prenode(ThreadNode* p){
    //左子树中最右下节点
    if(p->ltag == 0) return Lastnode(p->lchild);
    return p->lchild;   //ltag==1直接返回前驱
}
 
//逆向遍历线索二叉树
void RevInorder(ThreadTree T){
    for(ThreadNode* p = Lastnode(T);p!=NULL;p = Prenode(p)){
        cout<<p->data<<" ";
    }
    cout<<endl;
}
 
/*--------------------------*/
 
 
void test(){
    ThreadTree T;
    T =(ThreadNode*)malloc(sizeof(ThreadNode));
    InitTree(T);
    CreatInThread(T);
    Inorder(T);
    RevInorder(T);
}
 
int main(){
 
    test();
    return 0;
}
 
/*
输入数据：
ABD##E##C##
输出数据：
D B E A C
C A E B D
*/
 
6、先序线索化二叉树
#include<iostream>
 
using namespace std;
 
typedef char ElemType;
 
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;
 
ThreadNode *pre;    //指向当前访问节点的前驱
 
 
void InitTree(ThreadTree& T);//初始化树
void visit(ThreadNode* q);
void PreThread(ThreadTree T);//先序遍历二叉树，
void CreatInThread(ThreadTree T);//建立先序线索化二叉树
 
/*--------------------------*/
/*先序线索二叉树中找先序后继*/
ThreadNode* Firstnode(ThreadNode* p);//找先序线索二叉树中先序序列下的第一个节点
ThreadNode* Nextnode(ThreadNode* p);//找先序线索二叉树中节点p在先序序列下的后继
void Preorder(ThreadTree T);//遍历线索二叉树
/*--------------------------*/
 
 
//初始化树
void InitTree(ThreadTree& T){
    ElemType ch;
    cin>>ch;
    if(ch=='#'){
        T = NULL;
    }else{
        T = (ThreadNode*)malloc(sizeof(ThreadNode));
        T->data = ch;
        T->ltag = 0;
        T->rtag = 0;
        InitTree(T->lchild);
        InitTree(T->rchild);
    }
 
}
 
void visit(ThreadNode* q){
    if(q->lchild==NULL){        //左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag =1;
    }
    if(pre!=NULL && pre->rchild == NULL){     //建立前驱节点的后续线索
        pre->rchild = q;
        pre->rtag = 1;
    }
    pre = q;
}
 
//先序遍历二叉树，
void PreThread(ThreadTree T){
    if(T!=NULL){
        visit(T);
        if(T->ltag!=1)  //lchild不是前驱节点
            PreThread(T->lchild);
        if(T->rtag!=1)  //rchild不是后驱节点，因为回溯回来可能造成死循环
            PreThread(T->rchild);
    }
}
 
//建立先序线索化二叉树
void CreatInThread(ThreadTree T){
    pre = NULL;
    if(T!=NULL){
        PreThread(T);            //先序线索化二叉树
        if(pre->rchild == NULL){
            pre->rtag = 1;      //处理遍历的最后一个节点
        }
    }
}
 
/*--------------------------*/
/*先序线索二叉树中找先序后继*/
 
 
//找先序线索二叉树中节点p在先序序列下的后继
ThreadNode* Nextnode(ThreadNode* p){
    if(p->rtag == 0){
        if(p->lchild!=NULL) return p->lchild;
        return p->rchild;
    }
    return p->rchild;   //rtag==1直接返回后继线索
}
 
//遍历线索二叉树
void Preorder(ThreadTree T){
    for(ThreadNode* p=T;p!=NULL;p = Nextnode(p)){
        cout<<p->data<<" ";
    }
    cout<<endl;
}
 
 
/*--------------------------*/
 
void test(){
    ThreadTree T;
    T =(ThreadNode*)malloc(sizeof(ThreadNode));
    InitTree(T);
    CreatInThread(T);
    Preorder(T);
}
 
int main(){
 
    test();
    return 0;
}
 
/*
输入数据：
ABD##E##C##
ABC####
输出数据：
A B D E C
A B C
*/
 
 
7、后序线索化二叉树
#include<iostream>
 
using namespace std;
 
typedef char ElemType;
 
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;
 
ThreadNode *pre;    //指向当前访问节点的前驱
 
 
void InitTree(ThreadTree& T);//初始化树
void visit(ThreadNode* q);
void PostThread(ThreadTree T);//后序遍历二叉树，
void CreatInThread(ThreadTree T);//建立后序线索化二叉树
 
/*--------------------------*/
/*后序线索二叉树中找后序前驱*/
ThreadNode* Prenode(ThreadNode* p);//找后序线索二叉树中节点p在后序序列下的前驱
void RevPostorder(ThreadTree T);//逆向遍历线索二叉树
/*--------------------------*/
 
 
//初始化树
void InitTree(ThreadTree& T){
    ElemType ch;
    cin>>ch;
    if(ch=='#'){
        T = NULL;
    }else{
        T = (ThreadNode*)malloc(sizeof(ThreadNode));
        T->data = ch;
        T->ltag = 0;
        T->rtag = 0;
        InitTree(T->lchild);
        InitTree(T->rchild);
    }
 
}
 
void visit(ThreadNode* q){
    if(q->lchild==NULL){        //左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag =1;
    }
    if(pre!=NULL && pre->rchild == NULL){     //建立前驱节点的后续线索
        pre->rchild = q;
        pre->rtag = 1;
    }
    pre = q;
}
 
//后序遍历二叉树，
void PostThread(ThreadTree T){
    if(T!=NULL){
        PostThread(T->lchild);
        PostThread(T->rchild);
        visit(T);
    }
}
 
//建立后序线索化二叉树
void CreatInThread(ThreadTree T){
    pre = NULL;
    if(T!=NULL){
        PostThread(T);            //后序线索化二叉树
        if(pre->rchild == NULL){
            pre->rtag = 1;      //处理遍历的最后一个节点
        }
    }
}
 
/*--------------------------*/
/*后序线索二叉树中找后序前驱*/
 
 
//找后序线索二叉树中节点p在后序序列下的前驱
ThreadNode* Prenode(ThreadNode* p){
    if(p->ltag == 0){
        if(p->rchild!=NULL) return p->rchild;
        return p->lchild;
    }
    return p->lchild;   //ltag==1直接返回前驱线索
}
 
//逆向遍历线索二叉树
void RevPostorder(ThreadTree T){
    for(ThreadNode* p=T;p!=NULL;p = Prenode(p)){
        cout<<p->data<<" ";
    }
    cout<<endl;
}
 
 
/*--------------------------*/
 
void test(){
    ThreadTree T;
    T =(ThreadNode*)malloc(sizeof(ThreadNode));
    InitTree(T);
    CreatInThread(T);
    RevPostorder(T);
}
 
int main(){
 
    test();
    return 0;
}
 
/*
输入数据：
ABD##E##C##
输出数据：
A C B E D
*/
 
8、先序，中序，后序线索二叉树总结
 	中序线索二叉树	先序线索二叉树	后序线索二叉树
找前驱	            √	            ×	            √
找后继	            √	            √	            ×
          除非采用暴力或者三叉树才能实现表中打叉的部分

9、平衡二叉树
/*
这个代码还没完善
*/
#include<iostream>
 
using namespace std;
 
typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
 
BSTNode *BST_Search(BSTree T,int key);//递归实现查找
BSTNode *BSTSearch(BSTree T,int key);//非递归实现查找
bool BST_Insert(BSTree &T,int k);//递归实现插入
bool BSTInsert(BSTree &T,int k);//非递归实现插入
void Creat_BST(BSTree &T,int str[],int n);//构造二叉树
 
//递归实现
BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL&&key!=T->key){
        if(key>T->key){
            T = T->rchild;
        }else{
            T = T->lchild;
        }
    }
    return T;
}
 
//非递归实现
BSTNode *BSTSearch(BSTree T,int key){
    if(T==NULL) return NULL;
    if(T->key==key) return T;
    if(key>T->key) return BSTSearch(T->rchild,key);
    if(key<T->key) return BSTSearch(T->lchild,key);
}
 
//递归实现插入
bool BST_Insert(BSTree &T,int k){
    if(T==NULL){
        T = (BSTNode*)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return true;    //插入成功
    }else if(T->key == k){
        return false;   //插入失败
    }else if(key>T->key){
        return BST_Insert(T->rchild,key);
    }else{
        return BST_Insert(T->lchild,key);
    }
}
 
//非递归实现插入
bool BSTInsert(BSTree &T,int k){
    BSTree p = T;
    BSTree pre = NULL;      //p的父节点，方便查找后插入
    while(p!=NULL){
        pre = p;
        if(p->key == key) return false;
        else if(p->key > key){
            p = p->lchild;
        }else{
            p = p->rchild;
        }
    }
    p = (BSTNode*)malloc(sizeof(BSTNode));
    p->key = k;
    p->lchild = p->rchild = NULL;
    if(pre == NULL) T = p;          //树为空
    else if(k<pre->key){
        pre->lchild = p;
    }else{
        pre->rchild = p;
    }
    return true;
}
 
//构造二叉树
void Creat_BST(BSTree &T,int str[],int n){
    T = NULL;
    for(int i=0;i<n;i++){
        BST_Insert(T,str[i]);
    }
}
 
void test(){
 
}
 
 
int main(){
 
    test();
    return 0;
}
五、排序
1、插入排序
（1）直接插入排序
//0相当于哨兵
void InsertSort(int a[],int n){
    for(int i=2;i<=n;i++){
        a[0] = a[i];
        int j;
        for(j=i-1;a[0]<a[j];j--){
            a[j+1] = a[j];
        }
        a[j+1] = a[0];
    }
}
（2）折半插入排序
//0相当于哨兵
void InsertSort(int a[],int n){
    for(int i=2;i<=n;i++){
        a[0] = a[i];
        int low = 1,high = i-1;
        while(low<=high){
            int mid = low+high>>1;
            if(a[mid]>a[0]) high = mid-1;
            else low = mid+1;
        }
        for(int j=i-1;j>=low;j--){
            a[j+1] = a[j];
        }
        a[low] = a[0];
    }
}
（3）希尔排序
//0相当于哨兵
void ShellSort(int a[],int n){
    for(int d=n/2;d>=1;d/=2){                   //增量
        for(int i=1;i<1+d;i++){                 //按照增量分为d个子表
            for(int j=i+d;j<=n;j+=d){           //对每个表进行排序
                a[0]=a[j];
                int k;
                for(k=j-d;k>0&&a[0]<a[k];k-=d){ //找到插入位置
                    a[k+d]=a[k];
                }
                a[k+d]=a[0];
            }
        }
    }
}
2、交换排序
（1）冒泡排序
//冒泡排序，元素下标从1开始，从后往前冒泡
void BubbleSort1(int a[],int n){
    for(int i=1;i<n;i++){
        bool flag = false;
        for(int j=n;j>i;j--){
            if(a[j-1]>a[j]){
                swap(a[j-1],a[j]);
                flag = true;
            }
        }
        if(!flag) return ;
    }
}
 
//冒泡排序，元素下标从1开始，从前往后冒泡
void BubbleSort2(int a[],int n){
    for(int j=n;j>1;j--){
        bool flag = false;
        for(int i=1;i<j;i++){
            if(a[i]>a[i+1]){
                swap(a[i],a[i+1]);
                flag = true;
            }
        }
        if(!flag) return;
    }
}
（2）快速排序
int Partition(int a[],int low,int high){
    int pivot = a[low];
    while(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);
    }
}
3、选择排序
（1）简单选择排序
//下标从1开始
void SelectSort(int a[],int n){
    for(int i=1;i<=n;i++){
        int tmp=i;
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[tmp]){
                tmp=j;
            }
        }
        swap(a[tmp],a[i]);
    }
 
}
（2）堆排序
大根堆排序（结果是升序）
//将元素k为根的子树进行调整（大根堆）
void HeadAdjust(int a[],int k,int n){
    a[0] = a[k];
    for(int i=k*2;i<=n;i*=2){
        if(i<n&&a[i]<a[i+1]){
            i++;
        }
        if(a[0]>=a[i]) break;
        else{
            a[k]=a[i];
            k=i;
        }
    }
    a[k] = a[0];
}
 
//建立大根堆
void BuildMaxHeap(int a[],int n){
    for(int i=n/2;i>=1;i--){
        HeadAdjust(a,i,n);
    }
}
 
 
 
//堆排序
void HeapSort(int a[],int n){
    BuildMaxHeap(a,n);
    for(int i=n;i>1;i--){
        swap(a[i],a[1]);
        HeadAdjust(a,1,i-1);
    }
}
小根堆排序（结果是降序）
//将元素k为根的子树进行调整（小根堆）
void HeadAdjust(int a[],int k,int n){
    a[0] = a[k];
    for(int i=k*2;i<=n;i*=2){
        if(i<n&&a[i]>a[i+1]){
            i++;
        }
        if(a[0]<=a[i]) break;
        else{
            a[k]=a[i];
            k=i;
        }
    }
    a[k] = a[0];
}
 
//建立小根堆
void BuildMaxHeap(int a[],int n){
    for(int i=n/2;i>=1;i--){
        HeadAdjust(a,i,n);
    }
}
 
 
 
//堆排序
void HeapSort(int a[],int n){
    BuildMaxHeap(a,n);
    for(int i=n;i>1;i--){
        swap(a[i],a[1]);
        HeadAdjust(a,1,i-1);
    }
}
4、归并排序
void Merge(int a[],int low,int mid,int high){
    for(int i=low;i<=high;i++){
        b[i] = a[i];
    }
    int k=low,i=low,j=mid+1;
    while(i<=mid&&j<=high){
        if(b[i]<=b[j]){
            a[k++] = b[i++];
        }else{
            a[k++] = b[j++];
        }
    }
    while(i<=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>>1;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
}


 
注：创建表时输入样例均为 1 2 3 4 5


原文链接：https://blog.csdn.net/qq_40679299/article/details/107721116