数据结构代码总结（C++）

博主： wmicheng
发布时间：2025 年 02 月 11 日
51 次浏览
1 条评论
13756字数
分类：数据结构

# 一、线性表

## 1.顺序表

```cpp
#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.单链表（不带头结点）**

```cpp
#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.单链表（带头结点）

```cpp
#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.双链表（带头结点）

```cpp
#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指向表头）

```cpp
#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指向表尾)

```cpp
#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.循环双链表

```cpp
#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.静态链表

```cpp
#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.顺序栈

```cpp
#include<iostream>
using namespace std;

typedef int ElemType;

#define MaxSize 50

typedef struct {
    ElemType data[MaxSize]; // 存储元素的数组
    int top; // 栈顶元素的下标
} SqStack;

InitStack(&S); 	//初始化栈。构造一个空栈S ，分配内存空间。
DestroyStack(&S);//销毁栈。销毁并释放栈S 所占用的内存空间。
Push(&S,x); 	//进栈，若栈S 未满，则将x 加入使之成为新栈顶。
Pop(&S,&x);		//出栈，若栈S 非空，则弹出栈顶元素，并用x 返回。
GetTop(S, &x);	//读栈顶元素。若栈S 非空，则用x 返回栈顶元素
StackEmpty(S);	//判断栈空。若S 为空，则返回true ，否则返回false 。

// 初始化栈为空
void InitStack(SqStack& S) {
    S.top = -1;
}

// 检查栈是否为空
bool StackEmpty(SqStack S) {
    if (S.top == -1) { // 如果栈顶下标为-1，说明栈为空
        return true;
    }
    return false;
}

// 压入元素
bool Push(SqStack& S, ElemType x) {
    if (S.top == MaxSize - 1) { // 如果栈顶下标等于数组长度-1，说明栈已满
        return false;
    }
    S.data[++S.top] = x; // 下标加1，将元素存入栈顶位置
    return true;
}

// 弹出元素
bool Pop(SqStack& S, ElemType& x) {
    if (S.top == -1) { // 如果栈顶下标为-1，说明栈为空
        return false;
    }
    x = S.data[S.top--]; // 取出栈顶元素，下标减1
    return true;
}

// 获取栈顶元素
bool GetTop(SqStack S, ElemType& x) {
    if (S.top == -1) { // 如果栈顶下标为-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.共享栈

```cpp
#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.链栈（带头）

```cpp
#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.链栈（不带头）

```cpp
#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.顺序队列

```cpp
#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牺牲一个存储空间来区分队空和队满

```cpp
#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判断

```cpp
#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判断

```cpp
#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牺牲一个存储空间来区分队空和队满

```cpp
#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判断

```cpp
#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判断

```cpp
#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.链队列（带头）

```cpp
#include<iostream>
using namespace std;
 
typedef int ElemType; // 定义元素类型为int类型
 
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.链队列（不带头）

```cpp
#include<iostream>
using namespace std;
 
typedef int ElemType; // 定义元素类型为int类型
 
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; // 将元素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; // 用指针s指向队头结点
    x = s->data; // 将队头结点的元素值赋给x
    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++) { // 入队5个元素
        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、串的基本操作

```cpp
#include<iostream>

using namespace std;

#define MAXLEN 255

// todo 定义一个静态顺序存储结构的字符串类型
typedef struct{
    char ch[MAXLEN]; //字符数组
    int length; //串的长度
}SString;

// todo 定义一个动态存储结构的字符串类型
typedef struct {
    char *ch; //字符指针
    int length; //串的长度
}HString;

// todo 初始化串
void InitSting(HString &S);

// todo 赋值操作，把串T复制为chars
bool StrAssign(HString &T,HString chars);

// todo 复制操作，由串S复制到T
bool StrCopy(HString &T,HString S);

// todo 判空，是返回true，否则false
bool StrEmpty(HString S);

// todo 若s>t 返回>0  s=t 返回=0  s<t 返回<0
int StrCompare(HString S,HString T);

// todo 返回串长
int StrLength(HString S);

// todo 求字串，用sub返回串s的第pos个位置开始的长度为len的串
bool SubString(HString &Sub,HString S,HString pos,HString len);

// todo 字符串拼接，用T返回由S1和S2连接的新串
bool Concat(HString &T,HString S1,HString S2);

// todo 返回串T在S中第一次出现的位置，不存在返回0
int Index(HString S,HString T);

// todo 清空操作
bool ClearString(HString &S);

// todo 销毁串
bool DestoryString(HString &S);

void InitSting(HString &S){
    S.ch = (char *)malloc(MAXLEN*sizeof(char)); //为字符指针分配内存
    S.length = 0; //初始化长度为0
}

bool StrAssign(HString &T,char* chars){
    T.length = 0; //初始化长度为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; //直接将传入的串S赋值给串T
    return true;
}

bool StrEmpty(HString S){
    if(S.length == 0) return true; //如果长度为0，说明串为空
    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]; //如果遇到不相等的字符，比较它们的ASCII码大小
        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]; //将原串中从pos开始的len个字符赋值给子串
    }
    Sub.ch[len+1] = '\0'; //在子串末尾添加结束符
    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]; //将S1中的字符复制到新串T中
    }
    for(int i=1;i<=S2.length;i++){
        T.ch[i+S1.length] = S2.ch[i]; //将S2中的字符复制到新串T s1内容后中
    }
    T.length = S1.length+S2.length; //计算新串T的长度
    return true;
}
/* todo 暴力匹配算法，也称为朴素匹配算法
TODO 具体实现原理如下：
1. 从原串的第一个字符开始（下标为0），依次与子串的第一个字符（下标为0）进行比较。
2. 如果字符相等，则继续比较原串和子串的下一个字符，直到子串的所有字符都匹配成功，此时返回原串中子串的起始位置。
3. 如果字符不相等，则从原串的下一个字符开始重新匹配子串，直到原串的剩余部分长度不足以匹配子串为止。
4. 如果在原串中找不到与子串匹配的部分，则返回-1。*/
int Index(HString S,HString T){
    int i=1,n=StrLength(S),m=StrLength(T); //n为原串长度，m为子串长度
    HString sub;
    InitSting(sub); //初始化子串
    while(i<n-m+1){ //遍历原串
        SubString(sub,S,i,m); //取出从i开始长度为m的子串
        if(StrCompare(T,sub)!=0) i++; //如果子串与目标串不相等，i++
        else return i; //如果相等，返回子串在原串中的位置
    }
    return 0; //如果没有找到，返回0
}
/* todo 该函数的实现过程如下：
1. 定义变量i为1，n为原串长度，m为子串长度。
2. 定义一个HString类型的子串变量sub，并使用InitString函数对其进行初始化，即将子串的data字段设置为空串，将length字段设置为0。
3. 使用while循环遍历原串（i从1到n-m+1）。
4. 在循环中，使用SubString函数取出从i开始长度为m的子串，并将其存储在sub中。
5. 使用StrCompare函数比较T和sub是否相等，如果不相等，则i加1，继续下一次循环；如果相等，则返回i，即子串在原串中的位置。
6. 如果循环结束后仍然没有找到子串，则返回0。*/

bool ClearString(HString &S){
    S.length = 0; //将串长度设置为0
    return true;
}

bool DestoryString(HString &S){
    free(S.ch); //释放动态存储结构的内存
    S.length = 0; //将串长度设置为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模式匹配

```cpp
#include<iostream>
#include<cstring>
#include<cstdio>

const int maxn = 255;

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;
    for (int j = 2; j <= len; j++) {
        if (t[next[j]] == t[j]) {
            nextval[j] = nextval[next[j]];
        } else {
            nextval[j] = next[j];
        }
    }
}

int KMP(char *s,char *t,int next[]){
    // s: 主串，t: 模式串，next: 模式串的 next 数组
    int lens = strlen(s+1); // 计算主串的长度
    int lent = strlen(t+1); // 计算模式串的长度
    int i=1,j=1; // 定义两个指针 i 和 j，分别指向主串和模式串中进行比较的字符的位置
    while(i<=lens && j<=lent){ // 在主串和模式串中进行比较，直到其中一个串被比较完
        if(j == 0 || s[i] == t[j]){ // 如果模式串中的字符和主串中的字符相同，或者 j=0，表示模式串已经匹配完了，可以移动指针继续比较
            i++; // 移动主串指针
            j++; // 移动模式串指针
        }else{
            j = next[j]; // 如果模式串中的字符和主串中的字符不同，或者 j!=0，需要将模式串指针移动到合适的位置，这里使用 next 数组来进行移动
        }
    }
    if(j>lent){ // 如果模式串匹配成功，返回匹配成功的起始位置
        return i - j + 1;
    }else{ // 如果模式串匹配失败，返回 0
        return 0;
    }
}
int Print_val(int val[]){
    for (int i = 1; i <=5; ++i) {
        printf("[%d]",val[i]);
    }
    printf("}\n");
}

int main(){
    char *s=" aaabaaaab";
    char *t=" aaaab";
    get_next(t,next);
    printf("naxt[]:{");
    Print_val(next);
    printf("%d\n",KMP(s,t,next));
    get_nextval(t,next);
    printf("naxtval[]:{");
    Print_val(nextval);
    printf("%d\n",KMP(s,t,next));

return 0;
}
```

# 四、树与二叉树

## 1、二叉树计算高度

```cpp
#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、二叉树的先序，中序，后序遍历（递归）

```cpp
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

// todo  递归初始化二叉树函数
void InitBiTree(BiTree& T);
// todo  遍历节点函数
void visit(BiTNode* p);
// todo  先序遍历二叉树函数
void PreOrder(BiTree T);
// todo  中序遍历二叉树函数
void InOrder(BiTree T);
// todo  后序遍历二叉树函数
void PostOrder(BiTree T);

int main() {
    BiTree T=0;
    InitBiTree(T);
    PreOrder(T);
    printf("\n");
    InOrder(T);
    printf("\n");
    PostOrder(T);
    return 0;
}
// todo  递归初始化二叉树函数
void InitBiTree(BiTree &T){
    ElemType ch;
    scanf_s("%c",&ch);
    if(ch=='#')
        T=NULL;                        // 如果输入的是#，则表示该节点为空
    else{
        T=(BiTree)malloc(sizeof (BiTNode));
        T->data=ch;                    // 将节点数据域初始化为输入的字符
        InitBiTree(T->lchild);      // 递归初始化左子树
        InitBiTree(T->rchild);      // 递归初始化右子树
    }
}
// todo 遍历节点函数的实现，打印节点的值
void visit(BiTNode* p){
    printf("%c ",p->data);
}
// todo 先序递归遍历二叉树函数的实现
void PreOrder(BiTree T){
    if(T==NULL)
        return;
    visit(T);               //根
    PreOrder(T->lchild);    //左
    PreOrder(T->rchild);    //右
}
// todo 中序递归遍历二叉树函数的实现
void InOrder(BiTree T){
    if(T==NULL)
        return;
    InOrder(T->lchild);    //左
    visit(T);              //根
    InOrder(T->rchild);    //右
}
// todo 后序递归遍历二叉树函数的实现
void PostOrder(BiTree T){
    if(T==NULL)
        return;
    PostOrder(T->lchild);    //左
    PostOrder(T->rchild);    //右
    visit(T);                //根
}
/*
输入样例：
ABD##E##C##
输出样例：
先序遍历
A B D E C
中序序遍历
D B E A C
后序遍历
D E B C A
*/
```

## 3、二叉树的先序，中序，后序遍历（非递归）

```cpp
#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、二叉树的层序遍历

```cpp
#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、中序线索化二叉树

```cpp
#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、先序线索化二叉树

```cpp
#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、后序线索化二叉树

## 8、先序，中序，后序线索二叉树总结

|        | 中序线索二叉树 | 先序线索二叉树 | 后序线索二叉树 |
| -----: | -------------- | -------------- | -------------- |
| 找前驱 | √              | ×              | √              |
| 找后继 | √              | √              | ×              |

除非采用暴力或者三叉树才能实现表中打叉的部分

---

# 五、图

```cpp
#define MaxVertexNum 100	//顶点数目的最大值
#define INFINITY 最大的int值	//宏定义常量"无穷"

typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值的数据类型

itypedef structt//顶点

VertexType Vex[MaxVertexNum];
//边的权
EdgeType Edge[MaxVertexNum] [MaxVertexNum];
int vexnum,arcnum;
//图的当前顶点数和弧数
MGraph;
```

# 六、查找

## 1、顺序查找

```cpp
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    int i;
    for(i=0;i<ST.TableLen && ST.elem[i]!=ket;++i)//查找成功,则返回元素下标;查找失败则返回-1
        return i==St.TableLen?-1:i;
}
```

## 2、折半查找

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

## 3、分块查找

```c++
/* 定义分块查找的结构体 */
struct index {
   int key; /* 关键字 */
   int start; /* 起始位置 */
   int end; /* 结束位置 */
};

/* 分块查找函数 */
int block_search(int *arr, int n, struct index *idx_arr, int m, int key) {
    int i, j;
    /* 先在索引表中查找 */
    for (i = 0; i < m; i++) {
        if (key >= idx_arr[i].key && key <= idx_arr[i+1].key) {
            /* 在该块中顺序查找 */
            for (j = idx_arr[i].start; j <= idx_arr[i].end; j++) {
                if (arr[j] == key) {
                    return j; /* 找到了，返回位置 */
                }
            }
            /* 没有找到，直接返回-1 */
            return -1;
        }
    }
    /* 如果查遍了所有的索引表还没有找到，返回-1 */
    return -1;
}
```

## 4、二叉排序树

```c++
/* 查找结点的函数 */
struct bst_node* search_node(struct bst_node *root, int key) {
    if (root == NULL || root->data == key) {
        /* 如果树为空或者找到了对应的结点，直接返回 */
        return root;
    }
    if (key < root->data) {
        /* 如果查找的关键字小于当前结点的数据，向左子树中查找 */
        return search_node(root->left, key);
    }
    /* 如果查找的关键字大于当前结点的数据，向右子树中查找 */
    return search_node(root->right, key);
}
```

## 5、平衡二叉树

```cpp
#include <stdio.h>
#include <stdlib.h>

// 定义节点
struct Node {
    int key; // 关键字
    int height; // 节点高度
    struct Node *left, *right; // 左右子节点指针
};

// 创建节点
struct Node* create_node(int key) {
    struct Node *node = (struct Node*)malloc(sizeof(struct Node)); // 分配内存
    node->key = key;
    node->height = 1; // 新插入的节点默认高度为1
    node->left = node->right = NULL;
    return node;
}

// 获取节点的高度
int get_height(struct Node *node) {
    if (node == NULL) {
        return 0;
    } else {
        return node->height;
    }
}

// 获取节点的平衡因子
int get_balance_factor(struct Node *node) {
    if (node == NULL) {
        return 0;
    } else {
        return get_height(node->left) - get_height(node->right);
    }
}

// 更新节点的高度
void update_height(struct Node *node) {
    node->height = 1 + (get_height(struct Node*)max(get_height(node->left), get_height(node->right)));
}

// 右旋转
struct Node* rotate_right(struct Node *node) {
    struct Node *child = node->left; // 取左子节点
    struct Node *grandchild = child->right; // 取左子节点的右子节点
    child->right = node; // 将当前节点变为左子节点的右子节点
    node->left = grandchild; // 将左子节点的右子节点变为当前节点的左子节点
    update_height(node); // 更新当前节点的高度
    update_height(child); // 更新左子节点的高度
    return child; // 返回新的根节点
}

// 左旋转
struct Node* rotate_left(struct Node *node) {
    struct Node *child = node->right; // 取右子节点
    struct Node *grandchild = child->left; // 取右子节点的左子节点
    child->left = node; // 将当前节点变为右子节点的左子节点
    node->right = grandchild; // 将右子节点的左子节点变为当前节点的右子节点
    update_height(node); // 更新当前节点的高度
    update_height(child); // 更新右子节点的高度
    return child;}

// 插入节点
struct Node* insert(struct Node *node, int key) {
    if (node == NULL) {
        return create_node(key); // 如果当前节点为空，则创建新节点
    } else if (key < node->key) {
        node->left = insert(node->left, key); // 如果插入节点的关键字小于当前节点的关键字，则插入到左子树
    } else {
        node->right = insert(node->right, key); // 如果插入节点的关键字大于等于当前节点的关键字，则插入到右子树
    }
    update_height(node); // 更新当前节点的高度
    int balance_factor = get_balance_factor(node); // 获取当前节点的平衡因子
    if (balance_factor > 1 && key < node->left->key) {
        return rotate_right(node); // 如果左子树的左子树高，则进行右旋转
    } else if (balance_factor > 1 && key > node->left->key) {
        node->left = rotate_left(node->left); // 如果左子树的右子树高，则先对左子节点进行左旋转，再进行右旋转
        return rotate_right(node);
    } else if (balance_factor < -1 &&key > node->right->key) {
        return rotate_left(node); // 如果右子树的右子树高，则进行左旋转
    } else if (balance_factor < -1 && key < node->right->key) {
        node->right = rotate_right(node->right); // 如果右子树的左子树高，则先对右子节点进行右旋转，再进行左旋转
        return rotate_left(node);
    } else {
        return node; // 如果当前节点平衡，则直接返回当前节点
    }
}

// 中序遍历
void inorder_traversal(struct Node *node) {
    if (node != NULL) {
        inorder_traversal(node->left);
        printf("%d ", node->key);
        inorder_traversal(node->right);
    }
}

int main() {
    struct Node *root = NULL; // 初始化根节点
    int keys[] = { 5, 3, 7, 1, 9, 2, 4, 6, 8 }; // 待插入的关键字
    int n = sizeof(keys) / sizeof(keys[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, keys[i]); // 插入节点并更新根节点
    }
    printf("Inorder traversal:\");
    inorder_traversal(root); // 中序遍历并输出结果
    return 0;
}
```

## 6、红黑树

```c
#include <stdio.h>
#include <stdlib.h>

// 定义颜色
enum Color {
    RED,
    BLACK
};

// 定义节点
struct Node {
    int key; // 关键字
    enum Color color; // 颜色
    struct Node *left, *right, *parent; // 左右子节点和父节点指针
};

// 定义红黑树
struct RedBlackTree {
    struct Node *root; // 根节点指针
};

// 创建节点
struct Node* create_node(int key) {
    struct Node *node = (struct Node*)malloc(sizeof(struct Node)); // 分配内存
    node->key = key;
    node->color = RED; // 新插入的节点默认为红色
    node->left = node->right = node->parent = NULL;
    return node;
}

// 左旋转
void rotate_left(struct RedBlackTree *tree, struct Node *node) {
    struct Node *child = node->right; // 取右子节点
    node->right = child->left; // 右子节点的左子节点变为当前节点的右子节点
    if (child->left != NULL) {
        child->left->parent = node; // 更新左子节点的父节点指针
    }
    child->parent = node->parent; // 将右子节点的父节点指针指向当前节点的父节点
    if (node->parent == NULL) {
        tree->root = child; // 如果当前节点为根节点则更新根节点指针
    } else if (node == node->parent->left) {
        node->parent->left = child; // 如果当前节点为父节点的左子节点则更新父节点的左子节点指针
    } else {
        node->parent->right = child; // 如果当前节点为父节点的右子节点则更新父节点的右子节点指针
    }
    child->left = node; // 当前节点变为右子节点的左子节点
    node->parent = child; // 当前节点的父节点指针指向右子节点
}

// 右旋转
void rotate_right(struct RedBlackTree *tree, struct Node *node) {
    struct Node *child = node->left;			 // 取左子节点
    node->left = child->right; 					// 左子节点的右子节点变为当前节点的左子节点
    if (child->right != NULL) {
        child->right->parent = node; 			// 更新右子节点的父节点指针
    }
    child->parent = node->parent; 				// 将左子节点的父节点指针指向当前节点的父节点
    if (node->parent == NULL) {
        tree->root = child; 					// 如果当前节点为根节点则更新根节点指针
    } else if (node == node->parent->right) {
        node->parent->right = child; 			// 如果当前节点为父节点的右子节点则更新父节点的右子节点指针
    } else {
        node->parent->left = child; 			// 如果当前节点为父节点的左子节点则更新父节点的左子节点指针
    }
    child->right = node; 						// 当前节点变为左子节点的右子节点
    node->parent = child; 					// 当前节点的父节点指针指向左子节点
}

// 插入节点
void insert(struct RedBlackTree *tree, int key) {
    struct Node *node = create_node(key); // 创建新节点
    if (tree->root == NULL) {
        tree->root = node; // 如果根节点为空则将新节点作为根节点
        node->color =BLACK; // 根节点为黑色
    } else {
        struct Node *cur = tree->root;
        struct Node *parent = NULL;
        while (cur != NULL) {
            parent = cur; // 保存父节点指针
            if (key < cur->key) {
                cur = cur->left; // 如果插入节点的关键字小于当前节点的关键字则向左子树查找
            } else {
                cur = cur->right; // 如果插入节点的关键字大于等于当前节点的关键字则向右子树查找
            }
        }
        node->parent = parent;
        if (key < parent->key) {
            parent->left = node; // 如果插入节点的关键字小于父节点的关键字则插入到左子树
        } else {
            parent->right = node; // 如果插入节点的关键字大于等于父节点的关键字则插入到右子树
        }
        while (node->parent != NULL && node->parent->color == RED) { // 如果父节点为红色则需要调整
            if (node->parent == node->parent->parent->left) { // 父节点为祖父节点的左子节点
                struct Node *uncle = node->parent->parent->right; // 取叔叔节点
                if (uncle != NULL && uncle->color == RED) { // 叔叔节点为红色
                    node->parent->color = BLACK; // 将父节点和叔叔节点设为黑色
                    uncle->color = BLACK;
                    node->parent->parent->color = RED; // 将祖父节点设为红色
                    node = node->parent->parent; // 将当前节点设为祖父节点
                } else { // 叔叔节点为黑色
                    if (node == node->parent->right) { // 如果当前节点为父节点的右子节点则需要左旋转
                        node = node->parent;
                        rotate_left(tree, node);
                    }
                    node->parent->color = BLACK; // 将父节点设为黑色
                    node->parent->parent->color = RED; // 将祖父节点设为红色
                    rotate_right(tree, node->parent->parent); // 对祖父节点进行右旋转
                }
            } else { // 父节点为祖父节点的右子节点，与上面的情况类似
                struct Node*uncle = node->parent->parent->left;
                if (uncle != NULL && uncle->color == RED) {
                    node->parent->color = BLACK;
                    uncle->color = BLACK;
                    node->parent->parent->color = RED;
                    node = node->parent->parent;
                } else {
                    if (node == node->parent->left) {
                        node = node->parent;
                        rotate_right(tree, node);
                    }
                    node->parent->color = BLACK;
                    node->parent->parent->color = RED;
                    rotate_left(tree, node->parent->parent);
                }
            }
        }
        tree->root->color = BLACK; // 根节点始终为黑色
    }
}

int main() {
    struct RedBlackTree tree = { NULL }; // 初始化红黑树
    int keys[] = { 5, 3, 7, 1, 9, 2, 4, 6, 8 }; // 待插入的关键字
    int n = sizeof(keys) / sizeof(keys[0]);
    for (int i = 0; i < n;i++) {
        insert(&tree, keys[i]); // 插入节点
    }
    printf("Inorder traversal:\n");
    inorder_traversal(tree.root); // 中序遍历红黑树
    printf("\n");
    return 0;
}
```

# 七、排序

## 1、插入排序

### （1）直接插入排序

```cpp
//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）折半插入排序

```cpp
//0相当于哨兵
void InsertSort(int a[],int n){
    for(int i=2;i<=n;i++){ // 从第二个元素开始插入
        a[0] = a[i]; // 将当前元素存放到哨兵位置
        int low = 1,high = i-1; // low为插入位置的下标，high为上限下标
        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）希尔排序

```cpp
//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）冒泡排序

```cpp
//冒泡排序，元素下标从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）`快速排序★★★`

```cpp
// 将数组a[low...high]划分为两个部分，左边部分的所有元素都小于等于a[low]，右边部分的所有元素都大于a[low]，返回划分后的分界点下标
int Partition(int a[], int low, int high) {
    int pivot = a[low]; // 选择第一个元素作为枢轴元素						pivot=基准/基轴
    while (low < high) { // 循环，直到low和high相遇
        while (low < high && a[high] >= pivot) high--; // 循环查找右边第一个小于pivot的元素
        a[low] = a[high]; // 将右边小于pivot的元素移到左边
        while (low < high && a[low] <= pivot) low++; // 循环查找左边第一个大于pivot的元素
        a[high] = a[low]; // 将左边大于pivot的元素移到右边
    }
    a[low] = pivot; // 将枢轴元素放到分界点上
    return low; // 返回分界点下标
}

//快速排序算法，将数组a[low...high]排序
void QuickSort(int a[], int low, int high) {
    if (low < high) { // 当low<high时，继续递归排序
        int pivotpos = Partition(a, low, high); // 划分数组，获取分界点下标
        QuickSort(a, low, pivotpos - 1); // 对左边部分递归排序
        QuickSort(a, pivotpos + 1, high); // 对右边部分递归排序
    }
}
```

## 3、选择排序

### （1）简单选择排序

```cpp
//下标从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）`堆排序★★★`

- 大根堆排序（结果是`升序`）

```cpp
// 将元素k为根的子树进行调整，使得它满足大根堆的性质
void HeadAdjust(int a[], int k, int n) {
    a[0] = a[k]; // 将a[k]存放在a[0]中，用于后续的调整操作
    for (int i = k * 2; i <= n; i *= 2) { // 从k的左子节点开始，循环调整k及其子节点的位置，直到满足大根堆的性质
        if (i < n && a[i] < a[i+1]) { // 如果右子节点比左子节点大，则将i指向右子节点
            i++;
        }
        if (a[0] >= a[i]) break; // 如果a[k]比左右子节点都大，则调整结束
        else { // 将较大的子节点上移，继续向下进行调整
            a[k] = a[i];
            k = i;
        }
    }
    a[k] = a[0]; // 将a[k]插入到合适的位置
}

// 建立大根堆
void BuildMaxHeap(int a[], int n) {
    for (int i = n/2; i >= 1; i--) { // 从最后一个非叶子节点开始，循环调用HeadAdjust函数，建立大根堆
        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); // 对堆顶元素进行调整，使得其满足大根堆的性质
    }
}
```

- 小根堆排序（结果是`降序`）

```cpp
// 将元素k为根的子树进行调整，使得它满足小根堆的性质
void HeadAdjust(int a[], int k, int n) {
    a[0] = a[k]; // 将a[k]存放在a[0]中，用于后续的调整操作
    for (int i = k * 2; i <= n; i *= 2) { // 从k的左子节点开始，循环调整k及其子节点的位置，直到满足小根堆的性质
        if (i < n && a[i] > a[i+1]) { // 如果右子节点比左子节点小，则将i指向右子节点
            i++;
        }
        if (a[0] <= a[i]) break; // 如果a[k]比左右子节点都小，则调整结束
        else { // 将较小的子节点上移，继续向下进行调整
            a[k] = a[i];
            k = i;
        }
    }
    a[k] = a[0]; // 将a[k]插入到合适的位置
}

// 建立小根堆
void BuildMaxHeap(int a[], int n) {
    for (int i = n/2; i >= 1; i--) { // 从最后一个非叶子节点开始，循环调用HeadAdjust函数，建立小根堆
        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、归并排序

```cpp
// 归并排序中的归并操作，将两个有序序列合并成一个有序序列
void Merge(int a[], int low, int mid, int high) {
    // 复制a[low..high]到辅助数组b[low..high]
    for (int i = low; i <= high; i++) {
        b[i] = a[i];
    }
    // 使用指针i、j、k分别指向b[low..mid]、b[mid+1..high]和a[low..high]中的元素
    int k = low, i = low, j = mid + 1;
    // 依次比较b[i]和b[j]的大小，将较小的元素存放在a[k]中，并将i和j分别加1
    while (i <= mid && j <= high) {
        if (b[i] <= b[j]) {
            a[k++] = b[i++];
        } else {
            a[k++] = b[j++];
        }
    }
    // 将b[low..mid]中未被选取的元素复制到a[low..high]中
    while (i <= mid) {
        a[k++] = b[i++];
    }
   // 将b[mid+1..high]中未被选取的元素复制到a[low..high]中
    while (j <= high) {
        a[k++] = b[j++];
    }
}

// 归并排序算法
void MergeSort(int a[], int low, int high) {
    if (low < high) { // 如果序列长度大于1，则继续进行归并排序
        int mid = (low + high) / 2; // 将序列分成两个子序列
        MergeSort(a, low, mid); // 对左子序列进行归并排序
        MergeSort(a, mid + 1, high); // 对右子序列进行归并排序
        Merge(a, low, mid, high); // 将左右子序列合并成一个有序序列
    }
}
```

最后修改：2025 年 02 月 11 日

如果觉得我的文章对你有用，请随意赞赏

1 条评论

wmicheng
February 11th, 2025 at 01:38 pm

回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

数据结构代码总结（C++）

wmicheng • 2025 年 02 月 11 日

# 一、线性表

## 1.顺序表

## **2.单链表（不带头结点）**

## 3.单链表（带头结点）

```cpp
#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.双链表（带头结点）

## 4.循环单链表（L指向表头）

```cpp
#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指向表尾)

```cpp
#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.循环双链表

```cpp
#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.静态链表

# 二、栈和队列

## 1.顺序栈

```cpp
#include<iostream>
using namespace std;

typedef int ElemType;

#define MaxSize 50

typedef struct {
    ElemType data[MaxSize]; // 存储元素的数组
    int top; // 栈顶元素的下标
} SqStack;

// 初始化栈为空
void InitStack(SqStack& S) {
    S.top = -1;
}

// 检查栈是否为空
bool StackEmpty(SqStack S) {
    if (S.top == -1) { // 如果栈顶下标为-1，说明栈为空
        return true;
    }
    return false;
}

int main() {
    test();
    return 0;
}
```

## 2.共享栈

## 3.链栈（带头）

## 4.链栈（不带头）

```cpp
#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.顺序队列

## 6.循环队列

### 6.1 rear指向队尾指针后一个位置and牺牲一个存储空间来区分队空和队满

```cpp
#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判断

### 6.3 rear指向队尾指针后一个位置and增设tag判断

### 6.4 rear指向队尾and牺牲一个存储空间来区分队空和队满

```cpp
#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判断

```cpp
#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判断

```cpp
#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.链队列（带头）

## 8.链队列（不带头）

```cpp
#include<iostream>
using namespace std;
 
typedef int ElemType; // 定义元素类型为int类型
 
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; // 将元素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; // 用指针s指向队头结点
    x = s->data; // 将队头结点的元素值赋给x
    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++) { // 入队5个元素
        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、串的基本操作

```cpp
#include<iostream>

using namespace std;

#define MAXLEN 255

// todo 定义一个静态顺序存储结构的字符串类型
typedef struct{
    char ch[MAXLEN]; //字符数组
    int length; //串的长度
}SString;

// todo 定义一个动态存储结构的字符串类型
typedef struct {
    char *ch; //字符指针
    int length; //串的长度
}HString;

// todo 初始化串
void InitSting(HString &S);

// todo 赋值操作，把串T复制为chars
bool StrAssign(HString &T,HString chars);

// todo 复制操作，由串S复制到T
bool StrCopy(HString &T,HString S);

// todo 判空，是返回true，否则false
bool StrEmpty(HString S);

// todo 若s>t 返回>0  s=t 返回=0  s<t 返回<0
int StrCompare(HString S,HString T);

// todo 返回串长
int StrLength(HString S);

// todo 求字串，用sub返回串s的第pos个位置开始的长度为len的串
bool SubString(HString &Sub,HString S,HString pos,HString len);

// todo 字符串拼接，用T返回由S1和S2连接的新串
bool Concat(HString &T,HString S1,HString S2);

// todo 返回串T在S中第一次出现的位置，不存在返回0
int Index(HString S,HString T);

// todo 清空操作
bool ClearString(HString &S);

// todo 销毁串
bool DestoryString(HString &S);

void InitSting(HString &S){
    S.ch = (char *)malloc(MAXLEN*sizeof(char)); //为字符指针分配内存
    S.length = 0; //初始化长度为0
}

bool StrCopy(HString &T,HString S){
    T = S; //直接将传入的串S赋值给串T
    return true;
}

bool StrEmpty(HString S){
    if(S.length == 0) return true; //如果长度为0，说明串为空
    return false;
}

int StrLength(HString S){
    return S.length; //返回串的长度
}

bool ClearString(HString &S){
    S.length = 0; //将串长度设置为0
    return true;
}

bool DestoryString(HString &S){
    free(S.ch); //释放动态存储结构的内存
    S.length = 0; //将串长度设置为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模式匹配

```cpp
#include<iostream>
#include<cstring>
#include<cstdio>

const int maxn = 255;

char t[maxn];   //模式串
char s[maxn];   //主串
int next[maxn];
int nextval[maxn];

return 0;
}
```

# 四、树与二叉树

## 1、二叉树计算高度

## 2、二叉树的先序，中序，后序遍历（递归）

```cpp
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

## 3、二叉树的先序，中序，后序遍历（非递归）

## 4、二叉树的层序遍历

## 5、中序线索化二叉树

## 6、先序线索化二叉树

```cpp
#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、后序线索化二叉树

## 8、先序，中序，后序线索二叉树总结

除非采用暴力或者三叉树才能实现表中打叉的部分

---

# 五、图

```cpp
#define MaxVertexNum 100	//顶点数目的最大值
#define INFINITY 最大的int值	//宏定义常量"无穷"

typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值的数据类型

itypedef structt//顶点

VertexType Vex[MaxVertexNum];
//边的权
EdgeType Edge[MaxVertexNum] [MaxVertexNum];
int vexnum,arcnum;
//图的当前顶点数和弧数
MGraph;
```

# 六、查找

## 1、顺序查找

## 2、折半查找

## 3、分块查找

```c++
/* 定义分块查找的结构体 */
struct index {
   int key; /* 关键字 */
   int start; /* 起始位置 */
   int end; /* 结束位置 */
};

## 4、二叉排序树

## 5、平衡二叉树

```cpp
#include <stdio.h>
#include <stdlib.h>

// 定义节点
struct Node {
    int key; // 关键字
    int height; // 节点高度
    struct Node *left, *right; // 左右子节点指针
};

// 获取节点的高度
int get_height(struct Node *node) {
    if (node == NULL) {
        return 0;
    } else {
        return node->height;
    }
}

// 更新节点的高度
void update_height(struct Node *node) {
    node->height = 1 + (get_height(struct Node*)max(get_height(node->left), get_height(node->right)));
}

## 6、红黑树

```c
#include <stdio.h>
#include <stdlib.h>

// 定义颜色
enum Color {
    RED,
    BLACK
};

// 定义节点
struct Node {
    int key; // 关键字
    enum Color color; // 颜色
    struct Node *left, *right, *parent; // 左右子节点和父节点指针
};

// 定义红黑树
struct RedBlackTree {
    struct Node *root; // 根节点指针
};

# 七、排序

## 1、插入排序

### （1）直接插入排序

### （2）折半插入排序

### （3）希尔排序

## 2、交换排序

### （1）冒泡排序

### （2）`快速排序★★★`

## 3、选择排序

### （1）简单选择排序

### （2）`堆排序★★★`

- 大根堆排序（结果是`升序`）

- 小根堆排序（结果是`降序`）

## 4、归并排序

1 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

数据结构代码总结（C++）

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款