一、线性表
1.顺序表
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
using namespace std;
#define InitSize 10 //定义最大长度
静态分配
//typedef struct {
// int data[InitList];
// int length;
//}SqlList;
//动态分配
typedef struct {
int *data;
int length; //当前长度
int MaxSize;//最大长度
}SqlList;
//初始化顺序表
void InitList(SqlList &L) {
L.data = (int *)malloc(InitSize * sizeof(int));
L.length = 0;
L.MaxSize = InitSize;
}
//增加顺序表的长度
void IncreaseSize(SqlList &L, int len) {
int* p = L.data;
L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));
for (int i = 0; i < L.length; i++) {
L.data[i] = p[i];
}
L.MaxSize += len;
free(p);
}
//插入元素，在位序i的位置插入元素e
bool ListInsert(SqlList& L, int i, int e) {
if (i<1 || i>L.length + 1) return false; //i的范围是否有效
if (L.length >= L.MaxSize) return false; //当前存储空间已满，不能插入
for (int j = L.length; j >= i; j--) {
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e;
L.length++;
return true;
}
//删除操作，删除位序i个位置上的元素,e是删除的元素
bool ListDelete(SqlList& L, int i, int& e) {
if (i<1 || i>L.length) return false;
e = L.data[i - 1];
for (int j = i; j < L.length; j++) {
L.data[j-1] = L.data[j];
}
L.length--;
return true;
}
//按位查找 返回位序i的元素
int GetElem(SqlList L, int i) {
if (i<1 || i>L.length) return -1;
return L.data[i - 1];
}
//查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqlList L, int e) {
for (int i = 0; i < L.length; i++) {
if (L.data[i] == e) return i + 1;
}
return -1;
}
//删除值位于s和t之间的数
bool Delete_s_t(SqlList& L, int s, int t) {
if (L.length == 0 || s >= t) return false;
int k = 0;
for (int i = 0; i < L.length; i++) {
if (L.data[i]<s || L.data[i]>t) {
L.data[k++] = L.data[i];
}
}
L.length = k;
return true;
}
int main() {
SqlList L;
InitList(L);
ListInsert(L, 1, 1);
ListInsert(L, 2, 6);
ListInsert(L, 3, 3);
ListInsert(L, 4, 8);
ListInsert(L, 5, 2);
for (int i = 0; i < L.length; i++) {
cout << L.data[i] << " ";
}
cout << endl;
Delete_s_t(L, 2, 3);
for (int i = 0; i < L.length; i++) {
cout << L.data[i] << " ";
}
cout << endl;
return 0;
}
2.单链表（不带头结点）
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct LNode {
int data;
struct LNode* next;
}LNode, * LinkList;
//struct LNode* == LinkList
//强调节点 用LNode
//强调链表 用LinkList
//初始化单链表
bool InitList(LinkList& L) {
L = NULL;
return true;
}
//按位查找，返回第i个元素（不带带头节点）
LNode* GetElem(LinkList L, int i) {
if (i <= 0) return NULL;
int j = 1;
LNode* p = L;
while (p && j < i) {
p = p->next;
j++;
}
return p;
}
//按值查找，找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e) {
LNode* p = L;
while (p && p->data != e) {
p = p->next;
}
return p;
}
//统计单链表的长度
int Length(LinkList L) {
int len = 0;
LNode* p = L;
while (p) {
len++;
p = p->next;
}
return len;
}
//后插操作，在节点p之后插入元素e
bool InsertNextNode(LNode* p, int e) {
if (!p) return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (!s) return false;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
//不带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e) {
if (i < 1) return false;
if (i == 1) {
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = L;
L = s;
return true;
}
LNode* p;
p = L;
int j = 1; //当前p指向的是第几个节点，没有头节点，所以从1开始
while (p && j < i - 1) {
p = p->next;
j++;
}
if (!p) return false;
return InsertNextNode(p, e);
}
//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e) {
if (!p) return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (!s) return false;
s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;
return true;
}
//前插操作，在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
if (!p || !s) return false;
s->next = p->next;
p->next = s;
swap(s->data, p->data);
return true;
}
//删除位序i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
if (L == NULL) {
e = -1;
return false;
}
if (i < 1) return false;
if (i > 1) {
LNode* p = GetElem(L, i - 1);
if (!p || !(p->next)) return false;
LNode* q = p->next;
e = q->data;
p->next = q->next;
free(q);
}
else {
if (L->next == NULL) {
e = L->data;
L = NULL;
}
else {
e = L->data;
L = L->next;
}
}
return true;
}
//删除指定节点P
bool DeleteNode(LNode* p) {
if (p->next == NULL) return false;
//下面这段代码有bug，不能删除最后一个节点，因此要是删除最后一个节点的话要重新进行操作
LNode* q = p->next;
p->data = q->data;
p->next = q->next;
free(q);
return true;
}
//尾插法，不带头结点
LinkList List_TailInsert(LinkList& L) {
InitList(L);
LNode* s, * r = L ; //r表示表尾指针
int x;
bool is_head = true;
while (cin >> x) {
s = (LNode*)malloc(sizeof(LNode));
if (is_head) {
is_head = false;
s->data = x;
L = s;
r = s;
}
s->data = x;
r->next = s;
r = s;
}
r->next = NULL;
return L;
}
//头插法，不带头结点
LinkList List_HeadInsert(LinkList& L) {
InitList(L);
LNode* s;
int x;
while (cin >> x) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L;
L = s;
}
return L;
}
void print(LinkList L) {
LNode* s = L;
while (s!= NULL) {
cout << s->data << " ";
s = s->next;
}
cout << endl;
}
int main() {
LinkList L;
List_HeadInsert(L);
cout << "头插法的结果" << endl;
print(L);
//List_TailInsert(L);
//cout << "尾插法的结果" << endl;
//print(L);
cout << "链表的第1个元素：" << GetElem(L, 1)->data << endl;
cout << "链表的长度：" << Length(L) << endl;
int e;
ListDelete(L, 5, e);
cout << "删除的第1个元素是：" << e << endl;
cout << "当前的链表" << endl;
print(L);
ListInsert(L, 5, e);
cout << "插入的第1个元素是：" << e << endl;
cout << "当前的链表" << endl;
print(L);
LNode* s = LocateElem(L, 5);
return 0;
}
3.单链表（带头结点）
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct LNode {
int data;
struct LNode* next;
}LNode, *LinkList;
//struct LNode* == LinkList
//强调节点 用LNode
//强调链表 用LinkList
//按位查找，返回第i个元素（带头节点）
LNode* GetElem(LinkList L, int i) {
if (i < 0) return NULL;
int j = 0;
LNode* p = L;
while (p && j < i) {
p = p->next;
j++;
}
return p;
}
//按值查找，找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e) {
LNode* p = L->next;
while (p && p->data!=e) {
p = p->next;
}
return p;
}
//统计单链表的长度
int Length(LinkList L) {
int len = 0;
LNode* p = L;
while (p->next) {
len++;
p = p->next;
}
return len;
}
//后插操作，在节点p之后插入元素e
bool InsertNextNode(LNode *p, int e) {
if (!p) return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (!s) return false;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
//带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e) {
if (i < 1) return false;
LNode* p = GetElem(L, i - 1);
if (!p) return false;
return InsertNextNode(p, e);
}
//不带头节点的插入操作，在第i个位置插入元素e
bool NoHead_ListInsert(LinkList& L, int i, int e) {
if (i < 1) return false;
if (i == 1) {
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = L;
L = s;
return true;
}
LNode* p;
p = L;
int j = 1; //当前p指向的是第几个节点，没有头节点，所以从1开始
while (p && j < i - 1) {
p = p->next;
j++;
}
if (!p) return false;
return InsertNextNode(p, e);
}
//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e) {
if (!p) return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (!s) return false;
s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;
return true;
}
//前插操作，在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
if ( !p || !s ) return false;
s->next = p->next;
p->next = s;
swap(s->data , p->data);
return true;
}
//删除位序i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
if (i < 1) return false;
LNode* p = GetElem(L, i - 1);
if (!p || !(p->next)) return false;
LNode* q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}
//删除指定节点P
bool DeleteNode(LNode* p) {
if (p->next == NULL) return false;
//下面这段代码有bug，不能删除最后一个节点，因此要是删除最后一个节点的话要重新进行操作
LNode* q = p->next;
p->data = q->data;
p->next = q->next;
free(q);
return true;
}
bool InitList(LinkList& L) {
L = (LNode* )malloc(sizeof(LNode));//分配一个头节点
if (!L) return false;
L->next = NULL;
return true;
}
//尾插法，带头结点
LinkList List_TailInsert(LinkList& L) {
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
LNode* s, * r = L; //r表示表尾指针
int x;
while (cin >> x) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
}
r->next = NULL;
return L;
}
//头插法，带头结点
LinkList List_HeadInsert(LinkList& L) {
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
LNode* s;
int x;
while (cin >> x) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
}
return L;
}
void print(LinkList L) {
LNode* s = L;
while (s->next!=NULL) {
s = s->next;
cout << s->data << " ";
}
cout << endl;
}
int main() {
LinkList L;
//List_HeadInsert(L);
//cout << "头插法的结果" << endl;
//print(L);
List_TailInsert(L);
cout << "尾插法的结果" << endl;
print(L);
cout << "链表的第2个元素："<< GetElem(L, 2)->data << endl;
cout << "链表的长度："<< Length(L) << endl;
int e;
ListDelete(L, 3, e);
cout << "删除的第3个元素是：" << e << endl;
cout << "当前的链表" << endl;
print(L);
ListInsert(L, 3, e);
cout << "插入的第3个元素是：" << e << endl;
cout << "当前的链表" << endl;
print(L);
LNode* s = LocateElem(L, 5);
return 0;
}
3.双链表（带头结点）
#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct DNode {
ElemType data;
struct DNode* prior, * next;
}DNode, * DLinkList;
//初始化双链表
bool InitDLinkList(DLinkList& L) {
L = (DNode*)malloc(sizeof(DNode));
if (L == NULL) {
return false;
}
L->prior = NULL;
L->next = NULL;
return true;
}
//判断双链表是否为空
bool empty(DLinkList L) {
if (L->next = NULL) {
return true;
}
return false;
}
//按位查找：返回第i个结点
DNode* GetElem(DLinkList L, int i) {
if (i < 0) return NULL;
int j = 0;
DNode* p = L;
while (p != NULL && j < i) {
p = p->next;
j++;
}
return p;
}
//按值查找：找到第一个数据域为e的结点
DNode* LocateElem(DLinkList L, ElemType e) {
DNode* p = L;
if (p == NULL) return NULL;
p = p->next;
while (p != NULL && p->data != e) {
p = p->next;
}
return p;
}
//在p节点之后插入s节点
bool InsertNextDNode(DNode* p, DNode* s) {
if (p == NULL || s == NULL) {
return false;
}
s->next = p->next;
if(p->next != NULL)
p->next->prior = s;
s->prior = p;
p->next = s;
}
//在p节点后面插入值是e的节点
bool InsertNextDNode(DNode* p, ElemType e) {
if (p == NULL) return false;
DNode* q = (DNode*)malloc(sizeof(DNode));
if (q == NULL) return false;
q->data = e;
q->next = NULL;
q->prior = p;
if (p->next != NULL) {
p->next->prior = q;
q->next = p->next;
}
p->next = q;
return true;
}
//前插，在p节点前面插入节点s
bool InsertPriorDnode(DNode* p, DNode* s) {
return InsertNextDNode(p->prior, s);
}
//按位插入，在第i个位置插入值为e的节点（位序i）
bool InsertDLinkList(DLinkList& L, int i, ElemType e) {
if (i <= 0) return false;
DNode* p = GetElem(L, i - 1);
return InsertNextDNode(p, e);
}
//删除p节点的后继节点
bool DeleteNextNode(DNode* p) {
if (p == NULL) return false;
DNode* q = p->next;
if (q == NULL) return false;
p->next = q->next;
if (q->next != NULL) q->next->prior = p;
free(q);
return true;
}
//销毁双链表
bool DestoryList(DLinkList& L) {
while (L->next != NULL) {
DeleteNextNode(L);
}
free(L);
L = NULL;
return true;
}
//尾插法
DLinkList List_TailInsert(DLinkList& L) {
InitDLinkList(L);
DNode* p = L;
ElemType x;
while (cin >> x) {
InsertNextDNode(p, x);
p = p->next;
}
return L;
}
//头插法
DLinkList List_HeadInsert(DLinkList& L) {
InitDLinkList(L);
ElemType x;
while (cin >> x) {
InsertNextDNode(L, x);
}
return L;
}
int Length(DLinkList L) {
DNode* p = L;
int len = 0;
while (p->next != NULL) {
len++;
p = p->next;
}
return len;
}
//删除指定节点s
bool DeleteNode(DNode* s) {
DNode* p;
p = s->prior;
p->next = s->next;
if (s->next != NULL) {
s->next->prior = p;
}
free(s);
return true;
}
//删除位序i的节点，e是i节点的值
bool ListDelete(DLinkList& L, int i, ElemType& e) {
if (i <= 0 || i > Length(L)) return false;
DNode* s;
s = GetElem(L, i);
if (s == NULL) return false;
e = s->data;
return DeleteNode(s);
}
void print(DLinkList L) {
DNode* p = L->next;
while (p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
void testDLinkList() {
DLinkList L;
//cout << "头插法" << endl;
//List_HeadInsert(L);
//print(L);
cout << "尾插法" << endl;
List_TailInsert(L);
print(L);
cout << "长度：" << Length(L) << endl;
cout << "第1个元素为：" << GetElem(L, 1)->data << endl;
cout << "第5个元素为：" << GetElem(L, 5)->data << endl;
cout << "在第一个位置插入元素0" << endl;
InsertDLinkList(L, 1, 0);
print(L);
cout << "在最后一个位置插入元素6" << endl;
InsertDLinkList(L, 7, 6);
print(L);
int e;
ListDelete(L, 1, e);
cout << "删除第一个节点：" << e << endl;
cout << "当前链表为" << endl;
print(L);
ListDelete(L, 6, e);
cout << "删除最后一个节点：" << e << endl;
cout << "当前链表为" << endl;
print(L);
DestoryList(L);
}
int main() {
testDLinkList();
return 0;
}
4.循环单链表（L指向表头）
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct LNode {
int data;
struct LNode* next;
}LNode, * LinkList;
//struct LNode* == LinkList
//强调节点 用LNode
//强调链表 用LinkList
bool InitList(LinkList& L) {
L = (LNode*)malloc(sizeof(LNode));//分配一个头节点
if (L == NULL) return false;
L->next = L;
return true;
}
//按位查找，返回第i个元素（带头节点）
LNode* GetElem(LinkList L, int i) {
if (i < 0) return NULL;
if (i == 0) return L;
int j = 1;
LNode* p = L->next;
while (p != L && j < i) {
p = p->next;
j++;
}
return p;
}
//按值查找，找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e) {
LNode* p = L->next;
while (p != L && p->data != e) {
p = p->next;
}
if (p->data == e) return p;
return NULL;
}
//统计单链表的长度
int Length(LinkList L) {
int len = 0;
LNode* p = L;
while (p->next != L) {
len++;
p = p->next;
}
return len;
}
//后插操作，在节点p之后插入元素e
bool InsertNextNode(LNode* p, int e) {
if (!p) return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (!s) return false;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
//带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e) {
if (i < 1) return false;
LNode* p = GetElem(L, i - 1);
if (!p) return false;
return InsertNextNode(p, e);
}
//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e) {
if (!p) return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (!s) return false;
s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;
return true;
}
//前插操作，在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
if (!p || !s) return false;
s->next = p->next;
p->next = s;
swap(s->data, p->data);
return true;
}
//删除位序i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
if (i < 1) return false;
LNode* p = GetElem(L, i - 1);
if (p == NULL || p->next == L) return false;
LNode* q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}
//删除指定节点P
bool DeleteNode(LinkList& L, LNode* p) {
LNode* q = p->next;
p->data = q->data;
p->next = q->next;
if (L == q) {
L = p;
}
free(q);
return true;
}
//尾插法，带头结点
LinkList List_TailInsert(LinkList& L) {
InitList(L);
LNode* s, * r = L; //r表示表尾指针
int x;
while (cin >> x) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
}
r->next = L;
return L;
}
//头插法，带头结点
LinkList List_HeadInsert(LinkList& L) {
InitList(L);
LNode* s, * r = L;
int x;
bool isFirst = true;
while (cin >> x) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
if (isFirst) {
r = s;
isFirst = false;
}
}
r->next = L;
return L;
}
bool Empty(LinkList L) {
if (L->next == L) {
return true;
}
return false;
}
//判断是否为表尾节点
bool isTail(LinkList L, LNode* p) {
if (p->next == L) return true;
return false;
}
void print(LinkList L) {
LNode* s = L->next;
while (s != L) {
cout << s->data << " ";
s = s->next;
}
cout << endl;
}
int main() {
LinkList L;
//List_HeadInsert(L);
//cout << "头插法的结果" << endl;
//print(L);
List_TailInsert(L);
cout << "尾插法的结果" << endl;
print(L);
cout << "链表的第1个元素：" << GetElem(L, 1)->data << endl;
cout << "链表的第5个元素：" << GetElem(L, 5)->data << endl;
cout << "链表的长度：" << Length(L) << endl;
int e;
ListDelete(L, 5, e);
cout << "删除的第5个元素是：" << e << endl;
cout << "当前的链表" << endl;
print(L);
ListInsert(L, 5, e);
cout << "插入的第5个元素是：" << e << endl;
cout << "当前的链表" << endl;
print(L);
ListDelete(L, 1, e);
cout << "删除的第1个元素是：" << e << endl;
cout << "当前的链表" << endl;
print(L);
ListInsert(L, 1, e);
cout << "插入的第1个元素是：" << e << endl;
cout << "当前的链表" << endl;
print(L);
LNode* s = LocateElem(L, 5);
DeleteNode(L, s);
print(L);
return 0;
}
/*
输入样例：
1 2 3 4 5
*/
5.循环单链表（L指向表尾)
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct LNode {
int data;
struct LNode* next;
}LNode, * LinkList;
//struct LNode* == LinkList
//强调节点 用LNode
//强调链表 用LinkList
bool InitList(LinkList& L) {
L = (LNode*)malloc(sizeof(LNode));//分配一个头节点
if (L == NULL) return false;
L->next = L;
return true;
}
//按位查找，返回第i个元素（带头节点）
LNode* GetElem(LinkList L, int i) {
if (i < 0) return NULL;
if (i == 0) return L->next;
int j = 1;
LNode* p = L->next->next;
while (p != L->next && j < i) {
p = p->next;
j++;
}
if (p == L->next) return NULL;
return p;
}
//按值查找，找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e) {
LNode* p = L->next->next;
while (p != L->next && p->data != e) {
p = p->next;
}
if (p->data == e) return p;
return NULL;
}
//统计单链表的长度
int Length(LinkList L) {
int len = 0;
LNode* p = L;
while (p->next != L) {
len++;
p = p->next;
}
return len;
}
//后插操作，在节点p之后插入元素e
bool InsertNextNode(LinkList& L, LNode* p, int e) {
if (!p) return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (!s) return false;
s->data = e;
s->next = p->next;
p->next = s;
if (p == L) L = s;
return true;
}
//带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e) {
if (i < 1) return false;
LNode* p = GetElem(L, i - 1);
if (!p) return false;
return InsertNextNode(L, p, e);
}
//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e) {
if (!p) return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (!s) return false;
s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;
return true;
}
//前插操作，在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
if (!p || !s) return false;
s->next = p->next;
p->next = s;
swap(s->data, p->data);
return true;
}
//删除位序i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
if (i < 1) return false;
LNode* p = GetElem(L, i - 1);
if (p == NULL || p == L) return false;
if (p->next == L) {
L = p;
}
LNode* q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}
//删除指定节点P
bool DeleteNode(LinkList& L, LNode* p) {
LNode* q = p->next;
p->data = q->data;
p->next = q->next;
if (L == p) { //尾节点
q = p;
while (q->next != p) {
q = q->next;
}
L = q;
}
//free(q)； 不能这样写，因为指针之间的赋值是指向同一块区域，就比如L和q就是指向相同的区域
return true;
}
//尾插法，带头结点
LinkList List_TailInsert(LinkList& L) {
InitList(L);
LNode* s, * r = L; //r表示表尾指针
int x;
while (cin >> x) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
}
r->next = L;
L = r;
return L;
}
//头插法，带头结点
LinkList List_HeadInsert(LinkList& L) {
InitList(L);
LNode* s, * r = L;
int x;
bool isFirst = true;
while (cin >> x) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
if (isFirst) {
r = s;
isFirst = false;
}
}
r->next = L;
L = r;
return r;
}
bool Empty(LinkList L) {
if (L->next == L) {
return true;
}
return false;
}
//判断是否为表尾节点
bool isTail(LinkList L, LNode* p) {
if (p == L) return true;
return false;
}
void print(LinkList L) {
LNode* s = L->next->next;
while (s != L->next) {
cout << s->data << " ";
s = s->next;
}
cout << endl;
}
int main() {
LinkList L;
//List_HeadInsert(L);
//cout << "头插法的结果" << endl;
//print(L);
List_TailInsert(L);
cout << L->data << endl;
cout << "尾插法的结果" << endl;
print(L);
cout << "链表的第1个元素：" << GetElem(L, 1)->data << endl;
cout << "链表的第5个元素：" << GetElem(L, 5)->data << endl;
cout << "链表的长度：" << Length(L) << endl;
int e;
ListDelete(L, 5, e);
cout << "删除的第5个元素是：" << e << endl;
cout << "当前的链表" << endl;
print(L);
ListInsert(L, 5, e);
cout << "插入的第5个元素是：" << e << endl;
cout << "当前的链表" << endl;
print(L);
ListDelete(L, 1, e);
cout << "删除的第1个元素是：" << e << endl;
cout << "当前的链表" << endl;
print(L);
ListInsert(L, 1, e);
cout << "插入的第1个元素是：" << e << endl;
cout << "当前的链表" << endl;
print(L);
LNode* s = LocateElem(L, 5);
DeleteNode(L, s);
print(L);
return 0;
}
/*
输入样例：
1 2 3 4 5
*/
6.循环双链表
#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct DNode {
ElemType data;
struct DNode* prior, * next;
}DNode, * DLinkList;
//初始化双链表
bool InitDLinkList(DLinkList& L) {
L = (DNode*)malloc(sizeof(DNode));
if (L == NULL) {
return false;
}
L->prior = L;
L->next = L;
return true;
}
//判断双链表是否为空
bool empty(DLinkList L) {
if (L->next = L) {
return true;
}
return false;
}
bool isTail(DLinkList L, DNode* p) {
if (p->next == L) return true;
return false;
}
//按位查找：返回第i个结点
DNode* GetElem(DLinkList L, int i) {
if (i < 0) return NULL;
if (i == 0) return L;
int j = 1;
DNode* p = L->next;
while (p != L && j < i) {
p = p->next;
j++;
}
if (p == L) return NULL;
return p;
}
//按值查找：找到第一个数据域为e的结点
DNode* LocateElem(DLinkList L, ElemType e) {
DNode* p = L;
if (p == NULL) return NULL;
p = p->next;
while (p != L && p->data != e) {
p = p->next;
}
if (p == L) return NULL;
return p;
}
//在p节点之后插入s节点
bool InsertNextDNode(DNode* p, DNode* s) {
if (p == NULL || s == NULL) {
return false;
}
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
}
//在p节点后面插入值是e的节点
bool InsertNextDNode(DNode* p, ElemType e) {
if (p == NULL) return false;
DNode* q = (DNode*)malloc(sizeof(DNode));
if (q == NULL) return false;
q->data = e;
q->prior = p;
p->next->prior = q;
q->next = p->next;
p->next = q;
return true;
}
//前插，在p节点前面插入节点s
bool InsertPriorDnode(DNode* p, DNode* s) {
return InsertNextDNode(p->prior, s);
}
//按位插入，在第i个位置插入值为e的节点（位序i）
bool InsertDLinkList(DLinkList& L, int i, ElemType e) {
if (i <= 0) return false;
DNode* p = GetElem(L, i - 1);
return InsertNextDNode(p, e);
}
//删除p节点的后继节点
bool DeleteNextNode(DNode* p) {
if (p == NULL) return false;
DNode* q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);
return true;
}
//销毁双链表
bool DestoryList(DLinkList& L) {
while (L->next != L) {
DeleteNextNode(L);
}
free(L);
L = NULL;
return true;
}
//尾插法
DLinkList List_TailInsert(DLinkList& L) {
InitDLinkList(L);
DNode* p = L;
ElemType x;
while (cin >> x) {
InsertNextDNode(p, x);
p = p->next;
}
return L;
}
//头插法
DLinkList List_HeadInsert(DLinkList& L) {
InitDLinkList(L);
ElemType x;
while (cin >> x) {
InsertNextDNode(L, x);
}
return L;
}
int Length(DLinkList L) {
DNode* p = L;
int len = 0;
while (p->next != L) {
len++;
p = p->next;
}
return len;
}
//删除指定节点s
bool DeleteNode(DNode* s) {
DNode* p;
p = s->prior;
p->next = s->next;
s->next->prior = p;
free(s);
return true;
}
//删除位序i的节点，e是i节点的值
bool ListDelete(DLinkList& L, int i, ElemType& e) {
if (i <= 0 || i > Length(L)) return false;
DNode* s;
s = GetElem(L, i);
if (s == NULL) return false;
e = s->data;
return DeleteNode(s);
}
void print(DLinkList L) {
DNode* p = L->next;
while (p != L) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
void testDLinkList() {
DLinkList L;
//cout << "头插法" << endl;
//List_HeadInsert(L);
//print(L);
cout << "尾插法" << endl;
List_TailInsert(L);
print(L);
cout << "长度：" << Length(L) << endl;
cout << "第1个元素为：" << GetElem(L, 1)->data << endl;
cout << "第5个元素为：" << GetElem(L, 5)->data << endl;
cout << "在第一个位置插入元素0" << endl;
InsertDLinkList(L, 1, 0);
print(L);
cout << "在最后一个位置插入元素6" << endl;
InsertDLinkList(L, 7, 6);
print(L);
int e;
ListDelete(L, 1, e);
cout << "删除第一个节点：" << e << endl;
cout << "当前链表为" << endl;
print(L);
ListDelete(L, 6, e);
cout << "删除最后一个节点：" << e << endl;
cout << "当前链表为" << endl;
print(L);
DestoryList(L);
}
int main() {
testDLinkList();
return 0;
}
7.静态链表
#include<iostream>
using namespace std;
#define MaxSize 10
#define ElemType int
typedef struct {
ElemType data;
int next;
}SLinkList[MaxSize];
void InitSLinkList(SLinkList L) {
for (int i = 0; i < MaxSize; i++) {
L[i].next = -2; //-2表时链表这个位置是空的
}
L[0].next = -1;
}
//判断双链表是否为空
bool empty(SLinkList L) {
if (L[0].next = -1) {
return true;
}
return false;
}
//得到第i个元素的下标
int Get_Index(SLinkList L, int i) {
int j = 0; //模拟指针
int cnt = 0; //计数
while (j != -1 && cnt < i) {
cnt++;
j = L[j].next;
//cout << j << " " << L[j].next << endl;
}
if (cnt != i) return -1; //不存在
return j;
}
//得到第一个是空的元素
int Get_First_Empty_Node(SLinkList L) {
for (int i = 1; i < MaxSize; i++) {
if (L[i].next == -2) return i;
}
}
// 返回L的第i个元素
ElemType GetElem(SLinkList L, int i) {
int j = Get_Index(L, i);
return L[j].data;
}
//在第i个节点后面插入值是e的节点
bool InsertNextSNode(SLinkList L, int i, ElemType e) {
int j = Get_Index(L, i);
//cout << j << endl;
int k = Get_First_Empty_Node(L); //第一个空节点的位置
L[k].next = L[j].next;
L[j].next = k;
L[k].data = e;
return true;
}
//删除第i个节点 e是删除元素的值
bool DeleteNode(SLinkList L, int i, ElemType& e) {
int j = Get_Index(L, i);
//cout <<i<< " " << j << endl;
if (L[j].next == -1) { //最后一个要特判
//cout << "asdad" << endl;
int k = Get_Index(L, i - 1);
L[j].next = -2;
e = L[j].data;
L[k].next = -1;
return true;
}
//相当于交换次序，跟王道之前的删除方法类似
e = L[j].data;
int tmp = L[j].next;
L[j].data = L[L[j].next].data;
L[j].next = L[L[j].next].next;
L[tmp].next = -2;
return true;
}
//插入(默认开始是空的)
bool List_Insert(SLinkList L) {
int tot = 1 , pre = 0;
ElemType x;
while (cin >> x) {
L[tot].data = x;
L[tot].next = -1;
L[pre].next = tot;
pre = tot++;
}
return true;
}
void print(SLinkList L) {
int i = L[0].next;
while (~i) {
cout << L[i].data << " ";
i = L[i].next;
}
cout << endl;
}
void testSLinkList() {
SLinkList L;
InitSLinkList(L);
List_Insert(L);
print(L);
cout <<"第1个元素是："<< GetElem(L, 1) << endl;
cout <<"第3个元素是："<< GetElem(L, 3) << endl;
cout <<"第5个元素是："<< GetElem(L, 5) << endl;
InsertNextSNode(L, 0, 0);
print(L);
InsertNextSNode(L, 1, 6);
print(L);
InsertNextSNode(L, 7, 7);
print(L);
//cout << "-------------" << endl;
//for (int i = 0; i <= 8; i++) {
// cout << L[i].next << endl;
//}
int e;
DeleteNode(L, 8, e);
cout << e << endl;
print(L);
DeleteNode(L, 2, e);
cout << e << endl;
print(L);
DeleteNode(L, 1, e);
cout << e << endl;
print(L);
}
int main() {
testSLinkList();
return 0;
}
/*
1 2 3 4 5
*/
二、栈和队列
1.顺序栈
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 50
typedef struct {
ElemType data[MaxSize]; // 存储元素的数组
int top; // 栈顶元素的下标
} SqStack;
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.共享栈
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 10
typedef struct {
ElemType data[MaxSize];
int top0;
int top1;
}ShStack;
void InitStack(ShStack& S);
bool StackEmpty(ShStack S);
bool StackFull(ShStack S); //判断栈是否满了
bool Push0(ShStack& S, ElemType x);
bool Push1(ShStack& S, ElemType x);
bool Pop0(ShStack& S, ElemType& x);
bool Pop1(ShStack& S, ElemType& x);
bool GetTop0(ShStack S, ElemType& x);
bool GetTop1(ShStack S, ElemType& x);
bool DestoryStack0(ShStack& S);
bool DestoryStack1(ShStack& S);
void InitStack(ShStack& S) {
S.top0 = -1;
S.top1 = MaxSize;
}
bool StackEmpty(ShStack S) {
if (S.top0 == -1 && S.top1 == MaxSize) {
return true;
}
return false;
}
bool StackFull(ShStack S) {
if (S.top0 + 1 == S.top1) return true;
return false;
}
bool Push0(ShStack& S, ElemType x) {
if (StackFull(S) ){
return false;
}
S.data[++S.top0] = x;
return true;
}
bool Push1(ShStack& S, ElemType x) {
if (StackFull(S) ){
return false;
}
S.data[--S.top1] = x;
return true;
}
bool Pop0(ShStack& S, ElemType& x) {
if (S.top0 == -1) return false;
x = S.data[S.top0--];
return true;
}
bool Pop1(ShStack& S, ElemType& x) {
if (S.top1 == MaxSize) return false;
x = S.data[S.top1++];
return true;
}
bool GetTop0(ShStack S, ElemType& x) {
if (S.top0 == -1) return false;
x = S.data[S.top0];
return true;
}
bool GetTop1(ShStack S, ElemType& x) {
if (S.top1 == MaxSize) return false;
x = S.data[S.top1];
return true;
}
void test() {
ShStack S;
InitStack(S);
for (int i = 1; i <= 5; i++) {
Push0(S, i);
}
for (int i = 1; i <= 5; i++) {
Push1(S, i);
}
ElemType x;
GetTop0(S, x);
cout << x << endl;
GetTop1(S, x);
cout << x << endl;
bool f = Push0(S, 6);
if (f) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
f = Push1(S, 6);
if (f) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
while (Pop0(S,x)) {
cout << x << endl;
}
while (Pop1(S, x)) {
cout << x << endl;
}
}
int main() {
test();
return 0;
}
3.链栈（带头）
#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct LinkNode {
ElemType data;
struct LinkNode* next;
}*LiStack,LinkNode;
bool InitStack(LiStack& S);
bool StackEmpty(LiStack S);
bool Push(LiStack& S, ElemType x);
bool Pop(LiStack& S, ElemType& x);
bool GetTop(LiStack S, ElemType& x);
bool DestoryStack(LiStack& S);
bool InitStack(LiStack& S) {
S = (LiStack)malloc(sizeof(LinkNode));
if (S == NULL) return false;
S->next = NULL;
return true;
}
bool StackEmpty(LiStack S) {
if (S->next == NULL) return true;
return false;
}
bool Push(LiStack& S, ElemType x) {
LinkNode* p;
p = (LinkNode*)malloc(sizeof(LinkNode));
if (p == NULL) return false;
p->data = x;
p->next = S->next;
S->next = p;
return true;
}
bool Pop(LiStack& S, ElemType& x) {
if (StackEmpty(S)) return false;
LinkNode* p = S->next;
S->next = p->next;
x = p->data;
free(p);
return true;
}
bool GetTop(LiStack S, ElemType& x) {
if (StackEmpty(S)) return false;
x = S->next->data;
return true;
}
bool DestoryStack(LiStack& S) {
while (S->next != NULL) {
LinkNode* p = S->next;
S->next = p->next;
free(p);
}
free(S);
return true;
}
void test() {
LiStack S;
InitStack(S);
for (int i = 0; i <= 5; i++) {
Push(S, i);
}
ElemType x;
GetTop(S, x);
cout << x << endl;
while (!StackEmpty(S)) {
Pop(S, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
4.链栈（不带头）
#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct LinkNode {
ElemType data;
struct LinkNode* next;
}*LiStack, LinkNode;
bool InitStack(LiStack& S);
bool StackEmpty(LiStack S);
bool Push(LiStack& S, ElemType x);
bool Pop(LiStack& S, ElemType& x);
bool GetTop(LiStack S, ElemType& x);
bool DestoryStack(LiStack& S);
bool InitStack(LiStack& S) {
S = NULL;
return true;
}
bool StackEmpty(LiStack S) {
if (S == NULL) return true;
return false;
}
bool Push(LiStack& S, ElemType x) {
LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));
if (p == NULL) return false;
p->data = x;
p->next = S;
S = p;
return true;
}
bool Pop(LiStack& S, ElemType& x) {
if (StackEmpty(S)) return false;
LinkNode* p = S;
S = S->next;
x = p->data;
free(p);
return true;
}
bool GetTop(LiStack S, ElemType& x) {
if (StackEmpty(S)) {
return false;
}
x = S->data;
return true;
}
bool DestoryStack(LiStack& S) {
while (S != NULL) {
LinkNode* p = S;
S = S->next;
free(p);
}
free(S);
S = NULL;
return true;
}
void test() {
LiStack S;
InitStack(S);
for (int i = 0; i <= 5; i++) {
Push(S, i);
}
ElemType x;
GetTop(S, x);
cout << x << endl;
while (!StackEmpty(S)) {
Pop(S, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
5.顺序队列
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue &Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue &Q, ElemType x);
bool DeQueue(SqQueue &Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
void InitQueue(SqQueue &Q) {
Q.front = Q.rear = 0;
}
bool QueueEmpty(SqQueue Q) {
if (Q.front == Q.rear) return true;
return false;
}
bool QueueFull(SqQueue Q) {
if (Q.rear == MaxSize) return true;
return false;
}
bool EnQueue(SqQueue &Q, ElemType x) {
if (QueueFull(Q)) return false; //队满
Q.data[Q.rear++] = x;
return true;
}
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front++];
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
return true;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
EnQueue(Q, i);
}
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
ElemType x;
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
6.循环队列
6.1 rear指向队尾指针后一个位置and牺牲一个存储空间来区分队空和队满
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q); //返回队列元素的个数
void InitQueue(SqQueue& Q) {
Q.front = Q.rear = 0;
}
bool QueueEmpty(SqQueue Q) {
if (Q.front == Q.rear) return true;
return false;
}
bool QueueFull(SqQueue Q) {
if ((Q.rear + 1) % MaxSize == Q.front) return true;
return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
if (QueueFull(Q)) return false; //队满
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize;
return true;
}
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
return true;
}
int GetSize(SqQueue Q) {
return (Q.rear - Q.front + MaxSize) % MaxSize;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
bool f = EnQueue(Q, i);
if (!f) cout << i << endl;
}
ElemType x;
DeQueue(Q, x);
cout << x << endl;
DeQueue(Q, x);
cout << x << endl;
EnQueue(Q, 1);
EnQueue(Q, 2);
cout << Q.front << " " << Q.rear << endl;
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
6.2 rear指向队尾指针后一个位置and增设size判断
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
int size;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q); //返回队列元素的个数
void InitQueue(SqQueue& Q) {
Q.front = Q.rear = Q.size = 0;
}
bool QueueEmpty(SqQueue Q) {
if (Q.size == 0) return true;
return false;
}
bool QueueFull(SqQueue Q) {
if (Q.size == MaxSize) return true;
return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
if (QueueFull(Q)) return false; //队满
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize;
Q.size++;
return true;
}
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
Q.size--;
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
return true;
}
int GetSize(SqQueue Q) {
return Q.size;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
bool f = EnQueue(Q, i);
if (!f) cout << i << endl;
}
ElemType x;
DeQueue(Q, x);
cout << x << endl;
DeQueue(Q, x);
cout << x << endl;
EnQueue(Q, 1);
EnQueue(Q, 2);
cout << Q.front << " " << Q.rear << endl;
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
6.3 rear指向队尾指针后一个位置and增设tag判断
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
int tag;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q); //返回队列元素的个数
void InitQueue(SqQueue& Q) {
Q.front = Q.rear = Q.tag = 0;
}
bool QueueEmpty(SqQueue Q) {
if (Q.tag == 0 && Q.front == Q.rear) return true;
return false;
}
bool QueueFull(SqQueue Q) {
if (Q.tag == 1 && Q.front == Q.rear) return true;
return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
if (QueueFull(Q)) return false; //队满
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize;
Q.tag = 1;
return true;
}
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
Q.tag = 0;
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
return true;
}
int GetSize(SqQueue Q) {
return (Q.rear - Q.front + MaxSize) % MaxSize;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
bool f = EnQueue(Q, i);
if (!f) cout << i << endl;
}
ElemType x;
DeQueue(Q, x);
cout << x << endl;
DeQueue(Q, x);
cout << x << endl;
EnQueue(Q, 1);
EnQueue(Q, 2);
cout << Q.front << " " << Q.rear << endl;
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
6.4 rear指向队尾and牺牲一个存储空间来区分队空和队满
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q); //返回队列元素的个数
void InitQueue(SqQueue& Q) {
Q.front = 0;
Q.rear = -1;
}
bool QueueEmpty(SqQueue Q) {
if (Q.front == Q.rear+1 ) return true;
return false;
}
bool QueueFull(SqQueue Q) {
if ((Q.rear + 2) % MaxSize == Q.front) return true;
return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
if (QueueFull(Q)) return false; //队满
Q.rear = (Q.rear + 1) % MaxSize;
Q.data[Q.rear] = x;
return true;
}
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
return true;
}
int GetSize(SqQueue Q) {
return (Q.rear - Q.front +1 + MaxSize) % MaxSize;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
bool f = EnQueue(Q, i);
if (!f) cout << i << endl;
}
ElemType x;
DeQueue(Q, x);
cout << x << endl;
DeQueue(Q, x);
cout << x << endl;
EnQueue(Q, 1);
EnQueue(Q, 2);
cout << Q.front << " " << Q.rear << endl;
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
6.2 rear指向队尾and增设size判断
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
int size;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q); //返回队列元素的个数
void InitQueue(SqQueue& Q) {
Q.front = 0;
Q.rear = -1;
Q.size = 0;
}
bool QueueEmpty(SqQueue Q) {
if (Q.size == 0)
return true;
return false;
}
bool QueueFull(SqQueue Q) {
if (Q.size == MaxSize) return true;
return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
if (QueueFull(Q))
return false; //队满
Q.rear = (Q.rear + 1) % MaxSize;
Q.data[Q.rear] = x;
Q.size++;
return true;
}
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
Q.size--;
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
return true;
}
int GetSize(SqQueue Q) {
return Q.size;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
bool f = EnQueue(Q, i);
if (!f) cout << i << endl;
}
ElemType x;
DeQueue(Q, x);
cout << x << endl;
DeQueue(Q, x);
cout << x << endl;
EnQueue(Q, 1);
EnQueue(Q, 2);
cout << Q.front << " " << Q.rear << endl;
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
6.3 rear指向队尾and增设tag判断
#include<iostream>
using namespace std;
typedef int ElemType;
#define MaxSize 5
typedef struct {
int front, rear;
int tag;
ElemType data[MaxSize];
}SqQueue;
void InitQueue(SqQueue& Q);
bool QueueEmpty(SqQueue Q);
bool QueueFull(SqQueue Q);
bool EnQueue(SqQueue& Q, ElemType x);
bool DeQueue(SqQueue& Q, ElemType& x);
bool GetHead(SqQueue Q, ElemType& x);
int GetSize(SqQueue Q); //返回队列元素的个数
void InitQueue(SqQueue& Q) {
Q.front = 0;
Q.rear = -1;
Q.tag = 0;
}
bool QueueEmpty(SqQueue Q) {
if (Q.front == Q.rear + 1 && Q.tag == 0) return true;
return false;
}
bool QueueFull(SqQueue Q) {
if (Q.front == Q.rear + 1 && Q.tag == 1) return true;
return false;
}
bool EnQueue(SqQueue& Q, ElemType x) {
if (QueueFull(Q)) return false; //队满
Q.rear = (Q.rear + 1) % MaxSize;
Q.data[Q.rear] = x;
Q.tag = 1;
return true;
}
bool DeQueue(SqQueue& Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
Q.tag = 0;
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (QueueEmpty(Q)) {
return false;
}
x = Q.data[Q.front];
return true;
}
int GetSize(SqQueue Q) {
return (Q.rear - Q.front + 1 + MaxSize) % MaxSize;
}
void test() {
SqQueue Q;
InitQueue(Q);
for (int i = 1; i <= 5; i++) {
bool f = EnQueue(Q, i);
if (!f) cout << i << endl;
}
ElemType x;
DeQueue(Q, x);
cout << x << endl;
DeQueue(Q, x);
cout << x << endl;
EnQueue(Q, 1);
EnQueue(Q, 2);
cout << Q.front << " " << Q.rear << endl;
if (!EnQueue(Q, 6)) {
cout << "队列已满" << endl;
}
GetHead(Q, x);
cout << x << endl << endl;
while (!QueueEmpty(Q)) {
DeQueue(Q, x);
cout << x << endl;
}
}
int main() {
test();
return 0;
}
7.链队列（带头）
#include<iostream>
using namespace std;
typedef int ElemType; // 定义元素类型为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.链队列（不带头）
#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、串的基本操作
#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模式匹配
#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、二叉树计算高度
#include<iostream>
using namespace std;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
bool InitBiTree(BiTree& T); //初始化
int treeDepth(BiTree T); //计算树的深度
bool InitBiTree(BiTree& T){
ElemType ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = ch;
InitBiTree(T->lchild);
InitBiTree(T->rchild);
}
}
int treeDepth(BiTree T){
if(T==NULL) return 0;
int l = treeDepth(T->lchild);
int r = treeDepth(T->rchild);
return l>r?l+1:r+1;
}
void test(){
BiTree T;
InitBiTree(T);
cout<<treeDepth(T);
}
int main(){
test();
return 0;
}
/*
输入样例：
ABD##E##C##
输出样例：
3
*/
2、二叉树的先序，中序，后序遍历（递归）
#include <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、二叉树的先序，中序，后序遍历（非递归）
#include<iostream>
using namespace std;
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct LinkNode {
BiTNode *data;
struct LinkNode* next;
}*LiStack,LinkNode;
bool InitStack(LiStack& S);
bool StackEmpty(LiStack S);
bool Push(LiStack& S, BiTNode* x);
bool Pop(LiStack& S, BiTNode*& x);
bool GetTop(LiStack S, BiTNode*& x);
bool DestoryStack(LiStack& S);
bool InitBiTree(BiTree& T); //初始化
void visit(BiTNode* p); //打印节点信息
void PostOrder(BiTree T); //后序遍历
void InOrder(BiTree T); //先序遍历
void PreOrder(BiTree T); //前序遍历
bool InitStack(LiStack& S) {
S = (LiStack)malloc(sizeof(LinkNode));
if (S == NULL) return false;
S->next = NULL;
return true;
}
bool StackEmpty(LiStack S) {
if (S->next == NULL) return true;
return false;
}
bool Push(LiStack& S, BiTNode* x) {
LinkNode* p;
p = (LinkNode*)malloc(sizeof(LinkNode));
if (p == NULL) return false;
p->data = x;
p->next = S->next;
S->next = p;
return true;
}
bool Pop(LiStack& S, BiTNode*& x) {
if (StackEmpty(S)) return false;
LinkNode* p = S->next;
S->next = p->next;
x = p->data;
free(p);
return true;
}
bool GetTop(LiStack S, BiTNode*& x) {
if (StackEmpty(S)) return false;
x = S->next->data;
return true;
}
bool InitBiTree(BiTree& T){
char ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = ch;
InitBiTree(T->lchild);
InitBiTree(T->rchild);
}
}
void visit(BiTNode* p){
cout<<p->data<<" ";
}
void PostOrder(BiTree T){
LiStack S;
InitStack(S);
BiTree p = T;
BiTNode *r = NULL; //辅助指针，指向最近访问的节点
while(p||!StackEmpty(S)){
if(p){ //走到最左边
Push(S,p);
p = p->lchild;
}else{ //走到最右边
GetTop(S,p); //读栈顶元素（非出栈）
if(p->rchild&&p->rchild!=r){ //若右子树存在且未被访问过
p = p->rchild; //转向右
Push(S,p); //压入栈
p = p->lchild; //再走到最左
}else{ //否则弹出栈顶元素并访问
Pop(S,p);
visit(p);
r = p; //记录最近访问过的节点
p = NULL; //节点访问完后重置p指针
}
}
}
}
void InOrder(BiTree T){
LiStack S;
InitStack(S);
BiTree p = T; //遍历指针
while(p||!StackEmpty(S)){ //
if(p){ //一路向左
Push(S,p); //当前节点入栈
p = p->lchild; //左孩子不为空一直向左走
}else{ //出栈，并转向该节点的右孩子
Pop(S,p); //栈顶结点出栈，访问
visit(p);
p = p->rchild; //向右子树走，
}
}
}
void PreOrder(BiTree T){
LiStack S;
InitStack(S);
BiTree p = T; //遍历指针
while(p||!StackEmpty(S)){ //
if(p){ //一路向左
visit(p);
Push(S,p); //当前节点入栈
p = p->lchild; //左孩子不为空一直向左走
}else{ //出栈，并转向该节点的右孩子
Pop(S,p); //栈顶结点出栈
p = p->rchild; //向右子树走，
}
}
}
void test(){
BiTree T;
InitBiTree(T);
cout<<"----------后序遍历----------"<<endl;
PostOrder(T);
cout<<endl;
cout<<"----------中序遍历----------"<<endl;
InOrder(T);
cout<<endl;
cout<<"----------先序遍历----------"<<endl;
PreOrder(T);
cout<<endl;
}
int main(){
test();
return 0;
}
/*
输入样例：
ABD##E##C##
输出样例：
----------后序遍历----------
D E B C A
----------中序遍历----------
D B E A C
----------先序遍历----------
A B D E C
*/
4、二叉树的层序遍历
#include<iostream>
using namespace std;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct LinkNode {
BiTNode* data;
struct LinkNode* next;
}LinkNode;
typedef struct {
LinkNode* front, * rear;
}LinkQueue;
bool InitBiTree(BiTree& T); //初始化树
void LevelOrder(BiTree T); //层序遍历
void InitQueue(LinkQueue& Q);
bool QueueEmpty(LinkQueue Q);
bool EnQueue(LinkQueue& Q, BiTNode* x);
bool DeQueue(LinkQueue& Q, BiTNode*& x);
void visit(BiTNode* p);
void InitQueue(LinkQueue& Q) {
Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
Q.front->next = NULL;
}
bool QueueEmpty(LinkQueue Q) {
if (Q.front == Q.rear) return true;
return false;
}
bool EnQueue(LinkQueue& Q, BiTNode* x) {
LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
s->data = x;
s->next = Q.rear->next;
Q.rear->next = s;
Q.rear = s;
return true;
}
bool DeQueue(LinkQueue& Q, BiTNode*& x) {
if (QueueEmpty(Q)) return false;
LinkNode* q = Q.front->next;
x = q->data;
Q.front->next = q->next;
if (Q.rear == q) {
Q.rear = Q.front;
}
free(q);
return true;
}
bool InitBiTree(BiTree& T){
ElemType ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = ch;
InitBiTree(T->lchild);
InitBiTree(T->rchild);
}
}
void LevelOrder(BiTree T){
LinkQueue Q;
InitQueue(Q);
BiTree p;
EnQueue(Q,T);
while(!QueueEmpty(Q)){
DeQueue(Q,p);
visit(p);
if(p->lchild!=NULL){
EnQueue(Q,p->lchild);
}
if(p->rchild!=NULL){
EnQueue(Q,p->rchild);
}
}
}
void visit(BiTNode* p){
cout<<p->data<<" ";
}
void test(){
BiTree T;
InitBiTree(T);
LevelOrder(T);
}
int main(){
test();
return 0;
}
/*
输入数据：
ABD##E##C##
输出数据：
A B C D E
*/
5、中序线索化二叉树
#include<iostream>
using namespace std;
typedef char ElemType;
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
ThreadNode *pre; //指向当前访问节点的前驱
void InitTree(ThreadTree& T);//初始化树
void visit(ThreadNode* q);
void InThread(ThreadTree T);//中序遍历二叉树，
void CreatInThread(ThreadTree T);//建立中序线索化二叉树
/*--------------------------*/
/*中序线索二叉树中找中序后继*/
ThreadNode* Firstnode(ThreadNode* p);//找中序线索二叉树中中序序列下的第一个节点
ThreadNode* Nextnode(ThreadNode* p);//找中序线索二叉树中节点p在中序序列下的后继
void Inorder(ThreadTree T);//遍历线索二叉树
/*--------------------------*/
/*--------------------------*/
/*中序线索二叉树中找中序前驱*/
ThreadNode* Lastnode(ThreadNode* p);//找到以p为根的子树中，最后一个被中序遍历的节点
ThreadNode* Prenode(ThreadNode* p);//在中序线索二叉树中找到节点p的前驱节点
void RevInorder(ThreadTree T);//逆向遍历线索二叉树
/*--------------------------*/
//初始化树
void InitTree(ThreadTree& T){
ElemType ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (ThreadNode*)malloc(sizeof(ThreadNode));
T->data = ch;
T->ltag = 0;
T->rtag = 0;
InitTree(T->lchild);
InitTree(T->rchild);
}
}
void visit(ThreadNode* q){
if(q->lchild==NULL){ //左子树为空，建立前驱线索
q->lchild = pre;
q->ltag =1;
}
if(pre!=NULL && pre->rchild == NULL){ //建立前驱节点的后续线索
pre->rchild = q;
pre->rtag = 1;
}
pre = q;
}
//中序遍历二叉树，
void InThread(ThreadTree T){
if(T!=NULL){
InThread(T->lchild);
visit(T);
InThread(T->rchild);
}
}
//建立中序线索化二叉树
void CreatInThread(ThreadTree T){
pre = NULL;
if(T!=NULL){
InThread(T); //中序线索化二叉树
if(pre->rchild == NULL){
pre->rtag = 1; //处理遍历的最后一个节点
}
}
}
/*--------------------------*/
/*中序线索二叉树中找中序后继*/
//找中序线索二叉树中中序序列下的第一个节点
ThreadNode* Firstnode(ThreadNode* p){
while(p->ltag==0) p = p->lchild; //最左下节点（不一定是叶节点）
return p;
}
//找中序线索二叉树中节点p在中序序列下的后继
ThreadNode* Nextnode(ThreadNode* p){
if(p->rtag == 0) return Firstnode(p->rchild);
return p->rchild; //rtag==1直接返回后继线索
}
//遍历线索二叉树
void Inorder(ThreadTree T){
for(ThreadNode* p=Firstnode(T);p!=NULL;p = Nextnode(p)){
cout<<p->data<<" ";
}
cout<<endl;
}
/*--------------------------*/
/*--------------------------*/
/*中序线索二叉树中找中序前驱*/
//找到以p为根的子树中，最后一个被中序遍历的节点
ThreadNode* Lastnode(ThreadNode* p){
//循环找到最右下节点（不一定是叶节点）
while(p->rtag == 0) p = p->rchild;
return p;
}
//在中序线索二叉树中找到节点p的前驱节点
ThreadNode* Prenode(ThreadNode* p){
//左子树中最右下节点
if(p->ltag == 0) return Lastnode(p->lchild);
return p->lchild; //ltag==1直接返回前驱
}
//逆向遍历线索二叉树
void RevInorder(ThreadTree T){
for(ThreadNode* p = Lastnode(T);p!=NULL;p = Prenode(p)){
cout<<p->data<<" ";
}
cout<<endl;
}
/*--------------------------*/
void test(){
ThreadTree T;
T =(ThreadNode*)malloc(sizeof(ThreadNode));
InitTree(T);
CreatInThread(T);
Inorder(T);
RevInorder(T);
}
int main(){
test();
return 0;
}
/*
输入数据：
ABD##E##C##
输出数据：
D B E A C
C A E B D
*/
6、先序线索化二叉树
#include<iostream>
using namespace std;
typedef char ElemType;
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
ThreadNode *pre; //指向当前访问节点的前驱
void InitTree(ThreadTree& T);//初始化树
void visit(ThreadNode* q);
void PreThread(ThreadTree T);//先序遍历二叉树，
void CreatInThread(ThreadTree T);//建立先序线索化二叉树
/*--------------------------*/
/*先序线索二叉树中找先序后继*/
ThreadNode* Firstnode(ThreadNode* p);//找先序线索二叉树中先序序列下的第一个节点
ThreadNode* Nextnode(ThreadNode* p);//找先序线索二叉树中节点p在先序序列下的后继
void Preorder(ThreadTree T);//遍历线索二叉树
/*--------------------------*/
//初始化树
void InitTree(ThreadTree& T){
ElemType ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (ThreadNode*)malloc(sizeof(ThreadNode));
T->data = ch;
T->ltag = 0;
T->rtag = 0;
InitTree(T->lchild);
InitTree(T->rchild);
}
}
void visit(ThreadNode* q){
if(q->lchild==NULL){ //左子树为空，建立前驱线索
q->lchild = pre;
q->ltag =1;
}
if(pre!=NULL && pre->rchild == NULL){ //建立前驱节点的后续线索
pre->rchild = q;
pre->rtag = 1;
}
pre = q;
}
//先序遍历二叉树，
void PreThread(ThreadTree T){
if(T!=NULL){
visit(T);
if(T->ltag!=1) //lchild不是前驱节点
PreThread(T->lchild);
if(T->rtag!=1) //rchild不是后驱节点，因为回溯回来可能造成死循环
PreThread(T->rchild);
}
}
//建立先序线索化二叉树
void CreatInThread(ThreadTree T){
pre = NULL;
if(T!=NULL){
PreThread(T); //先序线索化二叉树
if(pre->rchild == NULL){
pre->rtag = 1; //处理遍历的最后一个节点
}
}
}
/*--------------------------*/
/*先序线索二叉树中找先序后继*/
//找先序线索二叉树中节点p在先序序列下的后继
ThreadNode* Nextnode(ThreadNode* p){
if(p->rtag == 0){
if(p->lchild!=NULL) return p->lchild;
return p->rchild;
}
return p->rchild; //rtag==1直接返回后继线索
}
//遍历线索二叉树
void Preorder(ThreadTree T){
for(ThreadNode* p=T;p!=NULL;p = Nextnode(p)){
cout<<p->data<<" ";
}
cout<<endl;
}
/*--------------------------*/
void test(){
ThreadTree T;
T =(ThreadNode*)malloc(sizeof(ThreadNode));
InitTree(T);
CreatInThread(T);
Preorder(T);
}
int main(){
test();
return 0;
}
/*
输入数据：
ABD##E##C##
ABC####
输出数据：
A B D E C
A B C
*/
7、后序线索化二叉树
#include<iostream>
using namespace std;
typedef char ElemType;
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
ThreadNode *pre; //指向当前访问节点的前驱
void InitTree(ThreadTree& T);//初始化树
void visit(ThreadNode* q);
void PostThread(ThreadTree T);//后序遍历二叉树，
void CreatInThread(ThreadTree T);//建立后序线索化二叉树
/*--------------------------*/
/*后序线索二叉树中找后序前驱*/
ThreadNode* Prenode(ThreadNode* p);//找后序线索二叉树中节点p在后序序列下的前驱
void RevPostorder(ThreadTree T);//逆向遍历线索二叉树
/*--------------------------*/
//初始化树
void InitTree(ThreadTree& T){
ElemType ch;
cin>>ch;
if(ch=='#'){
T = NULL;
}else{
T = (ThreadNode*)malloc(sizeof(ThreadNode));
T->data = ch;
T->ltag = 0;
T->rtag = 0;
InitTree(T->lchild);
InitTree(T->rchild);
}
}
void visit(ThreadNode* q){
if(q->lchild==NULL){ //左子树为空，建立前驱线索
q->lchild = pre;
q->ltag =1;
}
if(pre!=NULL && pre->rchild == NULL){ //建立前驱节点的后续线索
pre->rchild = q;
pre->rtag = 1;
}
pre = q;
}
//后序遍历二叉树，
void PostThread(ThreadTree T){
if(T!=NULL){
PostThread(T->lchild);
PostThread(T->rchild);
visit(T);
}
}
//建立后序线索化二叉树
void CreatInThread(ThreadTree T){
pre = NULL;
if(T!=NULL){
PostThread(T); //后序线索化二叉树
if(pre->rchild == NULL){
pre->rtag = 1; //处理遍历的最后一个节点
}
}
}
/*--------------------------*/
/*后序线索二叉树中找后序前驱*/
//找后序线索二叉树中节点p在后序序列下的前驱
ThreadNode* Prenode(ThreadNode* p){
if(p->ltag == 0){
if(p->rchild!=NULL) return p->rchild;
return p->lchild;
}
return p->lchild; //ltag==1直接返回前驱线索
}
//逆向遍历线索二叉树
void RevPostorder(ThreadTree T){
for(ThreadNode* p=T;p!=NULL;p = Prenode(p)){
cout<<p->data<<" ";
}
cout<<endl;
}
/*--------------------------*/
void test(){
ThreadTree T;
T =(ThreadNode*)malloc(sizeof(ThreadNode));
InitTree(T);
CreatInThread(T);
RevPostorder(T);
}
int main(){
test();
return 0;
}
/*
输入数据：
ABD##E##C##
输出数据：
A C B E D
*/
8、先序，中序，后序线索二叉树总结
| 中序线索二叉树 | 先序线索二叉树 | 后序线索二叉树 | |
|---|---|---|---|
| 找前驱 | √ | × | √ |
| 找后继 | √ | √ | × |
除非采用暴力或者三叉树才能实现表中打叉的部分
五、图
#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、顺序查找
//顺序查找
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、折半查找
// 折半查找
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、分块查找
/* 定义分块查找的结构体 */
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、二叉排序树
/* 查找结点的函数 */
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、平衡二叉树
#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、红黑树
#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; // 根节点始终为黑色
}
}
// 中序遍历
void inorder_traversal(struct Node *node) {
if (node != NULL) {
inorder_traversal(node->left);
printf("%d ", node->key);
inorder_traversal(node->right);
}
}
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）直接插入排序
//0相当于哨兵
void InsertSort(int a[],int n){
for(int i=2;i<=n;i++){ // 从第二个元素开始插入
a[0] = a[i]; // 将当前元素存放到哨兵位置
int j;
for(j=i-1;a[0]<a[j];j--){ // 在已经排好序的前面的序列中找到合适的插入位置
a[j+1] = a[j]; // 如果当前元素小于前面的元素，则将前面的元素后移一位
}
a[j+1] = a[0]; // 将当前元素插入到插入位置
}
}
（2）折半插入排序
//0相当于哨兵
void InsertSort(int a[],int n){
for(int i=2;i<=n;i++){ // 从第二个元素开始插入
a[0] = a[i]; // 将当前元素存放到哨兵位置
int low = 1,high = i-1; // 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）希尔排序
//0相当于哨兵
void ShellSort(int a[],int n){
for(int d=n/2;d>=1;d/=2){ //增量
for(int i=1;i<1+d;i++){ //按照增量分为d个子表
for(int j=i+d;j<=n;j+=d){ //对每个表进行排序
a[0]=a[j];
int k;
for(k=j-d;k>0&&a[0]<a[k];k-=d){ //找到插入位置
a[k+d]=a[k];
}
a[k+d]=a[0];
}
}
}
}
2、交换排序
（1）冒泡排序
//冒泡排序，元素下标从1开始，从后往前冒泡
void BubbleSort1(int a[], int n) {
for (int i = 1; i < n; i++) { // 外层循环，控制冒泡次数，每次冒泡可以确定一个元素的位置
bool flag = false; // 标记变量，用于记录本轮冒泡是否有交换操作
for (int j = n; j > i; j--) { // 内层循环，从后往前冒泡
if (a[j-1] > a[j]) { // 如果前一个元素比后一个元素大，则交换位置
swap(a[j-1], a[j]);
flag = true; // 标记本轮冒泡有交换操作
}
}
if (!flag) return; // 如果本轮冒泡没有交换操作，则说明序列已经有序，直接返回
}
}
//冒泡排序，元素下标从1开始，从前往后冒泡
void BubbleSort2(int a[], int n) {
for (int j = n; j > 1; j--) { // 外层循环，控制冒泡次数，每次冒泡可以确定一个元素的位置
bool flag = false; // 标记变量，用于记录本轮冒泡是否有交换操作
for (int i = 1; i < j; i++) { // 内层循环，从前往后冒泡
if (a[i] > a[i+1]) { // 如果前一个元素比后一个元素大，则交换位置
swap(a[i], a[i+1]);
flag = true; // 标记本轮冒泡有交换操作
}
}
if (!flag) return; // 如果本轮冒泡没有交换操作，则说明序列已经有序，直接返回
}
}
（2）快速排序
// 将数组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）简单选择排序
//下标从1开始
void SelectSort(int a[], int n) {
for (int i = 1; i <= n; i++) { // 外层循环，控制选择排序的次数，每次选择可以确定一个元素的位置
int tmp = i; // 将当前位置设为最小值的位置
for (int j = i+1; j <= n; j++) { // 内层循环，从后面的元素中选择最小值
if (a[j] < a[tmp]) { // 如果发现更小的元素，则更新最小值的位置
tmp = j;
}
}
swap(a[tmp], a[i]); // 将最小值和当前位置的元素交换位置
}
}
（2）堆排序
- 大根堆排序（结果是
升序）
// 将元素k为根的子树进行调整，使得它满足大根堆的性质
void HeadAdjust(int a[], int k, int n) {
a[0] = a[k]; // 将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); // 对堆顶元素进行调整，使得其满足大根堆的性质
}
}
- 小根堆排序（结果是
降序）
// 将元素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、归并排序
// 归并排序中的归并操作，将两个有序序列合并成一个有序序列
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); // 将左右子序列合并成一个有序序列
}
}