二次整合导出于 2024.3 整合于 2023.1, 思源笔记导出
==说明==
数据结构代码是2022.10-11制作,大部分都用了引用(没必要),部分内容是阉割版的^（以下为部分阉割源码, Cpp笔记本中为更加归纳分割的源码）^,头文件自制(万能头文件打包): `#include <my/C.h>`
当初大二上时候可是把赵括大佐拷打致死了, 在狠狠Cpp手撸数据结构后代码功力大增.
# 数据表
# Tips
# 基操
修改: 通用重复代码删节
定义
typedef struct SSqlist { //Simple siquence list 基础顺序数据表
double data[MaxSize];
int length;
}*SSQ, qlist; //取个别名
typedef struct MSqlist { //Movable siquence list 动态顺序数据表
double* data;
int Maxlength, length;
}*MSQ, mlist; //取个别名
初始化
void SSQ_new(SSQ& L) { //简单初始化顺序表
L = new qlist;
L->length = 0; //我是用长度标记表尾,代表有几个元素
}
void MSQ_new(MSQ& L) { //简单初始化动态数据表
L = new mlist;
L->data = new double[MaxSize]; //C: L->data=(double*)malloc(sizeof(double) * MaxSize);
L->length = 0;
L->Maxlength = MaxSize;
}
void SSQ_add(SSQ& L, double x) { //简单添加元素
if (L->length < MaxSize) {
L->data[L->length] = x;
L->length++;
}
else cout << "数据表已满,插入失败\n";
}
==MSQ 动态扩容==
void MSQ_Addsize(MSQ& L, int len) { //动态增加长度,原理是申请新空间然后改变data指针指向
double* p = L->data;
L->data = new double[MaxSize]; //申请一片新空间
for (int i = 0; i < L->length; i++)
L->data[i] = p[i]; //复制数据-开销大
L->Maxlength = L->Maxlength + len; //增加最大热容量
free(p);
}
输出
void SSQ_print(SSQ L) { //简单输出元素
for (int i = 1; i < L->length + 1; i++)
cout << i << " -- " << L->data[i - 1] << endl;
}
写入
void SSQ_insert(SSQ& L, int sit, double x) { //数据表已有数据中的插入, 双判: 位置溢出,表格溢出,这里的x是第几个的意思
if (sit<1 || sit>L->length + 1 || L->length == MaxSize) //sit代表位置of第几位的插入操作的; 如果是动态的注意最大上限L->length >= L->Maxlength
return;
for (int j = L->length; j >= sit - 1; j--)
L->data[j + 1] = L->data[j];
L->data[sit - 1] = x; //插入到数据中
L->length++;
} //注意,采用Inlist初始化的list,判定无法插入的条件更为宽松,同时打印的时候也可以无脑全部打印.
删除
void SSQ_del(SSQ& L, int sit) { //删除指定位置的元素,容错判定x1
if (sit<1 || sit>L->length)
return;
for (int j = sit - 1; j < L->length; j++)
L->data[j] = L->data[j + 1];
L->length--;
}//可以定义一个引用形参&e, 这样就能返回被删除的元素了.
查找
int SSQ_find(SSQ& L, double x) { //简单查找对应值的下标
int i = 0;
while (i <= L->length && L->data[i] != x)
i++;
if (i > L->length) return -1;
else return i + 1;
}
比较
int SSQ_Compare(SSQ L1, SSQ L2) { //特种函数:比较大小(类似str的方法);
int s2 = 0; int i = 0; int s1 = 0;
while (i < L1->length && i < L2->length && L1->data[i] == L2->data[i])
i++;
s1 -= i; s2 -= i;
if (s1 == s2 && s1 == 0) return 0;
else if (s1 == 0 && s2 > 0 || s1 > 0 && s2 > 0 && L1->data[i] < L2->data[i])
return -1;
else return 1;
}
排序
void SSQ_sort(SSQ& L) { //降序排列,产生新的qlist,并更改L的指向.
SSQ N;
SSQ_new(N);
double baddest = -114514;
int sit = 0;
while (L->length > 0) {
baddest = -114514;
for (int i = 0; i < L->length; i++) {
if (L->data[i] > baddest) {
baddest = L->data[i];
sit = i + 1;
}
}
SSQ_add(N, baddest);
SSQ_del(L, sit);
}
L = N;
}
最值
double SSQ_max(SSQ L) { //在数组里找最大值,返回这个值
double baddest = -114514;
baddest = -114514;
for (int i = 0; i < L->length; i++)
if (L->data[i] > baddest)
baddest = L->data[i];
return baddest;
}
拷贝
SSQ SSQ_copy(SSQ L) { //完全复制返回一样的内容
SSQ N;
SSQ_new(N);
for (int i = 0; i < L->length; i++) {
SSQ_add(N, L->data[i]);
}
return N;
}
# 链表
# Tips
# 基操
定义+初始化
typedef struct Slinklist{
double data;
Slinklist* next;
}*SLL, snode;
void SLL_new(SLL& L){
L = new snode;
L->next = NULL; //L->before = NULL; //DLL
L->data = -1; //将头结点初始化.
}
头尾插入+定点前后插
void SLL_add(SLL& L, double data) { //尾插新项
SLL p = L;//遍历指针p
snode* N = new snode;
N->next = NULL; //N->before = NULL; //DLL
N->data = data;//新节点装填完毕
while (p->next != NULL)//有头结点就不需要考虑这个问题
p = p->next;
p->next = N; //N->before = p; //DLL
}
void SLL_insert(SLL& L, double data) { //头插新项,考虑原来是空的情况
snode* N = new snode;
N->next = NULL;
if (L->next == NULL) {
L->next = N;
N->data = data; //N->before = L; //DLL
return;
}
else {
N->next = L->next;
N->data = data; //N->next->before = N; //DLL
L->next = N; //N->before = L; //DLL
return;
}
}
void SLL_fin(SLL p, double data) { //给定指针节点的前插操作,O1的偷天换日方法
SLL s = new snode;
s->next = p->next; //s->before = p; //DLL
p->next = s;
s->data = p->data;
p->data = data;
}
void SLL_bin(SLL p, double data) { //给定指针节点的后插操作
SLL s = new snode;
s->data = data;
s->next = p->next; //s->before = p;
p->next = s;
}
删除
void SLL_Del(SLL& L, SLL& p) {
//删除一个节点p,当然也可以用偷天换日,把后面的节点覆盖到这里来,如果是表尾就delete
SLL q = L; //移动指针,跑到p节点的前一个节点
while (q->next != p)
q = q->next;
if (p->next != NULL)
q->next = q->next->next;
else
q->next = NULL;
}
void SLL_Delete(SLL& p) { //偷天换日
if (p->next == NULL)
delete(p);
else {
SLL q = p->next;
p->data = p->next->data;
p->next = q->next;
delete(q);
}
}
void DLL_Del(DLL& L, DLL& p) {//删除一个节点p,同样需要两个指针
DLL q = L; //移动指针,跑到p节点的前一个节点
while (q->next != p)
q = q->next;
if (p->next != NULL) {
q->next = p->next; //p"自动"移到了下一节点
p->before = q;
}
else
q->next = NULL;
}
长度
int SLL_Length(SLL L) { //简单求表长(头结点用next)
SLL p = L->next;
int length = 0;
for (p; p != NULL; p = p->next)
length++;
return length;
}
判空
bool SLL_isVoid(SLL& L) { //判空,是空就返回true
if (L->next == NULL)
return true;
else return false;
}
打印
void SLL_Print(SLL& L){
SLL p = L;//遍历指针p
while (p->next != NULL){//有头结点就不需要考虑这个问题
p = p->next;
cout << p->data << endl;
}
cout << endl;
}
查找+定位
SLL SLL_Get(SLL L, int i) { //简单按序号查找第i位指针
SLL p = L; //遍历指针
int j = 0;
while (p->next != NULL && j < i){
p = p->next;
j++;
}
if (j == i) return p;
else return NULL;
}
SLL SLL_Loc(SLL L, double x) { //简单定位元素
SLL p = L;
while (p->next != NULL && p->data != x)
p = p->next;
return p;
}
复制
SLL SLL_Copy(SLL& L) { //最简单由L生成相同list,两个的内容是完全相同的
SLL N;
SLL_new(N);
//构建N
SLL p = L; //遍历p
SLL q = N; //遍历q
while (p->next != NULL) {
snode* n = new snode;//新节点,每次都要申请空间
n->next = NULL;
p = p->next;
n->data = p->data;
q->next = n;
q = q->next;
}
return N;
}
最值
SLL SLL_max(SLL L){
SLL p = L; //遍历指针
SLL S = L; //存储指针
double maxpow = -114514;
for (p; p != NULL; p = p->next) { //经典for中的p查找
if (p->data > maxpow) { //链表选择排序
maxpow = p->data;
S = p;
}
}
return S;
}
连接链表
SLL SLL_Combine(SLL& A, SLL& B, SLL& L) { //最简单链接AB链表到L中去
SLL p = A; //a1移动到末尾A
SLL q = B; //q去链接b中元素到L余下,保证A,B不受影响
SLL t = L; //t去遍历L.
SLL_new(t);
while (p->next != NULL) {
snode* n = new snode;//新节点,每次都要申请空间
n->next = NULL;
p = p->next;
n->data = p->data;
t->next = n; //赋值构造得到的节点
t = t->next;
}
while (q->next != NULL) {
snode* n = new snode;//新节点,每次都要申请空间
n->next = NULL;
q = q->next;
n->data = q->data;
t->next = n; //赋值构造得到的节点
t = t->next;
}
return L;
}
去重
void SLL_Remove(SLL& L) { //简单的去重算法,删除连续的后一个
SLL q, p;
q = L;
if (L->next != NULL)
{
p = L->next;
while (p != NULL && q != NULL)
{
if (p->data == q->data)
{
SLL_Del(L, p);
p = q->next;
}
p = p->next;
q = q->next;
}
}
else return; //就一个去什么重啊?
}
节点调换
void SLL_Change(SLL& p, SLL& q) { //简单通过修改对应值进行两个节点的伪调换
double t = 0;
t = q->data;
q->data = p->data;
p->data = t;
}
逆转
void SLL_Reverse(SLL& L) { //头插法简单逆转链表
SLL N, p = L->next;
SLL_new(N);
while (p != NULL) {
SLL_insert(N, p->data);
p = p->next;
}
L = N;
}
切片
SLL SLL_Slice(SLL& p, SLL& q) { //返回一个新链表,由p,q节点以及之间的节点构成
SLL L;
SLL_new(L);
while (p != q) {
SLL_add(L, p->data);
p = p->next;
}
SLL_add(L, p->data);
return L;
}
降序排列
SLL SLL_sort(SLL& L) { //降序排列链表,返回个新链表
SLL p = L->next;
SLL N;
SLL s;
SLL_new(N);
int times = SLL_Length(L);//判定需要找最大值的次数
double maxpower = 0;
while (times > 0) {
maxpower = -114514;
while (p != NULL) {
if (p->data > maxpower) {
maxpower = p->data;
s = p;
}
p = p->next;
}
SLL_add(N, maxpower);
SLL_Del(L, s);
times--;
p = L->next;
}
return N;
}
# 串
# Tips
# 基操
初始化
typedef struct SS {
char ch[MaxSize];
int length;
}*SR;
void SS_new(SR& S) {
S = new SS; //分配空间
S->length = 0;
}
void SS_create(SR& S, char chs[]) { //用字符数组/字符串string创造字符串
int i = 0;
while (chs[i] != '\0'){ //循环，将字符串常量的值赋值给S
S->ch[i] = chs[i];
i++;
}
S->length = i;
}
复制
S->ch[i] = T->ch[i];S->length = T->length;
连接,切片,比较
void SS_concat(SR& S, SR& Q) { //连接Q到S
int j = 0;
int i = S->length;
for (j; j < Q->length; i++, j++)
S->ch[i] = Q->ch[j];
S->length += Q->length;
}
void SS_Sub(SR& S, SR& T, int pos, int len) {//用T返回S的第pos个字符起长度为len的子串
if (pos + len - 1 > S->length) return; //越界.
for (int i = pos; i < pos + len; i++)
T->ch[i - pos + 1] = S->ch[i]; //这步高明,可以实现i-pos
T->length = len;
}
int SS_Compare(SR& S, SR& T) {
// 这个是COm,自己实现的比较算法,返回-1,0,1. 当然可以用作那个验证相等,返回0
for (int i = 1; i < S->length && i < T->length; i++)
if (S->ch[i] != T->ch[i]) return S->ch[i] - T->ch[i];
return S->length - T->length;
}
查找
int SS_index(SR& S, SR& T) { // 最简单的朴素算法,
int i = 1, n = S->length, m = T->length; SR sub;
SS_new(sub); //创建暂存子串.
while (i < n - m + 1) {
SS_Sub(sub, S, i, m);
if (SS_Compare(sub, T) != 0) i++;
else return i; //返回位置
}
return -1; //找不到了.
}
# 栈
# Tips
采用无头结点,顺序栈与链式栈,未设置 bool 判断插入成功还是失败
# 基操
构建+判空
typedef struct Sqstack {//顺序栈定义
double data[MaxSize];
int top;
}*SST;
void SQ_new(SST& S) { //初始化:设置栈顶指针为-1,接下来会指向要插入的位置
S = new Sqstack;
S->top = -1;
}
if (S->top == -1) return true; //判断栈空
压入+弹出
void SQ_push(SST& S, double x) { //省略设置返回值
if (S->top == MaxSize - 1) return;
S->data[++S->top] = x;
}
void SQ_pop(SST& S) {
S->top--;
}
# 队列/双端
# Tips
# 基操
//创建一个循环队列--避免空间的浪费,指针中间空一格,同时指向一个则是空,中间差一个就是满
typedef struct SqQueue {
double data[MaxSize];
int front, back; //队头队尾指针,rear=back,代表插入的队尾,是不断前进的,别搞翻了哈
}*SQE, que; //重写名称
typedef struct Lqnode { //链队的节点
double data;
struct Lqnode* next;
}Linknode, * LQ;
typedef struct LQE { //链队- 有队头指针和队尾指针 ,无头结点
Linknode* front, * rear;
}LQE;
void SQE_new(SQE& Q) { //初始化指针
Q = new que;//申请
Q->back = Q->front = 0;
}
void LQE_new(LQE& Q) { //初始化链队
//Q.front = Q.rear = new Lqnode; //队头队尾同时指向相同的空间 -> 有头结点的
Q.front = NULL;
Q.rear = NULL;
}
判
bool SQE_isVoid(SQE Q) {
if (Q->back == Q->front) return true;
else return false;
}
bool LQE_isVoid(LQE Q) { //不带头结点的判空
if (Q.front == NULL) return true;
else return false;
}
bool SQE_isFull(SQE& Q) { //循环队列判断是否满的操作
if ((Q->back + 1) % MaxSize == Q->front) return true; //队尾的下一个就是fr,取mod就是
else return false;
}
出入
void SQE_in(SQE& Q, double x) { //入队操作,设置bool返回是否成功挺好
if (SQE_isFull(Q)) return; //判断满的条件:避免假满,则使用取模运算
Q->data[Q->back] = x;
Q->back = (Q->back + 1) % MaxSize; //空间化为环形
}
void LQE_in(LQE& Q, double x) { //没有头结点的
LQ N = new Lqnode; //N为新节点,LQ表示指针
N->data = x;
N->next = NULL;
if (Q.front == NULL) {
Q.front = N;
Q.rear = N;
}
else {
Q.rear->next = N;
Q.rear = N; //队伍越拉越长,队尾一直往后走了.
}
}
void SQE_out(SQE& Q) { //出队
if (Q->back == Q->front) return;//啥都没有
cout << Q->data[Q->front]; //简单输出
Q->front = (Q->front + 1) % MaxSize;
}
void LQE_out(LQE& Q) { //出队,没有头结点
if (Q.front == NULL) return; //无了
if (Q.rear == Q.front) { //出队是最后一个
Q.front = NULL;
Q.rear = NULL;
}
else Q.front = Q.front->next; //更改指向,之前的出去了.
//本来应该加上一个p指向当前要被删除的家伙,返回值后还有delete(p)来回收空间的,但是这里只是简单演示,就不搞了
//同时,也可以调换几步的顺序
}
# 树
# Tips
int Node_Counter = 0; //全局变量计算节点个数
//10月16日终于开始对树结构的冲击,此时已经是第8周了,原定于第二周就可以开始的作战计划终究还是被赵括大佐英明神武的微操干碎了
# 基操
初始化
//TR -
typedef struct BTnode { //普通二叉树,链式实现,双链域
double data;
struct BTnode* L, * R; //左孩子右孩子Left_child,Right_child
}btnode, * TR; //TR= tree
//BT -
typedef struct BBTnode { //孩子兄弟表示法的树
double data;
struct BBTnode* C, * B; //"第一个孩子"和ta右兄弟Child_first,Brother_right
}bbtnode, * BT; //BT =brother tree
//TT -
typedef struct TBTnode { //普通线索二叉树-先是一般的二叉树,然后通过不同的4种遍历方式完成线索化.
double data;
struct TBTnode* L, * R;
int ltag, rtag; //左右线索标志,0,1代表是有元素还是没有(0),没有则用来存放前驱后继线索
}tbtnode, * TB; //TT =thread(tag) tree
//二叉排序树,左小右大,不展示了,就是中序遍历的招数,左小于根小于右
//线索二叉树
//更改的匹配树结构的2个队列结构:
typedef struct Lqnode { //链队节点
TR Tree;
struct Lqnode* next;
}Linknode, * LQ;
typedef struct LQE { //链队- 有队头指针和队尾指针 ,无头结点
Linknode* front, * rear;
}LQE;
typedef struct TLqnode { //链队节点
TB Tree;
struct TLqnode* next;
}TLinknode, * TQ;
typedef struct TQE { //链队- 有队头指针和队尾指针 ,无头结点
TLinknode* front, * rear;
}TQE;
//线索二叉树适配:
void TQE_new(TQE& Q) { //初始化链队
Q.front = NULL;
Q.rear = NULL;
}
bool TQE_isVoid(TQE Q) { //不带头结点的判空
if (Q.front == NULL) return true;
else return false;
}
void TQE_in(TQE& Q, TB x) { //没有头结点的入队rear
TQ N = new TLqnode;
N->Tree = x;
N->next = NULL;
if (Q.front == NULL) {
Q.front = N;
Q.rear = N;
}
else {
Q.rear->next = N;
Q.rear = N;
}
}
void TQE_out(TQE& Q, TB& x) { //出队front
x = Q.front->Tree;
if (Q.front == NULL) return;
if (Q.rear == Q.front) {
Q.front = NULL;
Q.rear = NULL;
}
else Q.front = Q.front->next;
}
# 通用基操
void TR_void_tree(TR& T) {//树的销毁
T = NULL; //T变成空树
}
void TR_new_root(TR& T) { //插入根节点(这里设置为无意义
T = new btnode; //申请节点空间
T->data = 114514; //好臭的树
T->L = T->R = NULL;
}
void TR_new(TR& T) { //树的初始化
TR_void_tree(T);
TR_new_root(T);
}
int TR_Hight(TR T) { //递归求高度
if (T == NULL) return 0;
else return max(TR_Hight(T->L), TR_Hight(T->R)) + 1;
}
int TR_Depth(TR T, TR p) { return TR_Hight(T) - TR_Hight(p) + 1; } //复合求"节点"深度, 根节点和要求的节点
# TR 基操
void TR_lsert(TR& p, double x) { //对应节点之后的左差新节点
TR N = new btnode;
N->data = x;
N->L = N->R = NULL;
p->L = N;
}
void TR_rsert(TR& p, double x) { //对应节点之后的右差新节点
TR N = new btnode;
N->data = x;
N->L = N->R = NULL;
p->R = N;
}
void TR_SERT(int u, TR& p, double x) { //参数列表第一个是判断,对应节点插入 , 0左1右
TR N = new btnode;
N->data = x;
N->L = N->R = NULL;
if (u == 1) p->R = N;
else p->L = N;
}
void TR_delete(TR& p, int L_or_R) { //传入要删除的节点指针,判断进行删除的是左孩子还是右孩子
if (L_or_R == 0) { //0=Left;
delete(p->L);
p->L = NULL;
}
else {//
}
}
# BT 基操
void BT_Child_insert(BT& p, double x) { //孩子兄弟树的手动插入一个孩子节点.
BT N = new bbtnode;
N->data = x;
N->C = N->B = NULL;
p->C = N;
}
void BT_Brother_insert(BT& p, double x) { //孩子兄弟树的手动插入一个兄弟节点.
BT N = new bbtnode;
N->data = x;
N->C = N->B = NULL;
p->B = N;
}
# TB 基操
void TB_new_root(TB& T) { //插入根节点(这里设置为无意义
T = new tbtnode; //申请节点空间
T->data = 114514; //好臭的树
T->L = T->R = NULL;
}
void TB_lsert(TB& p, double x) { //对应节点之后的左差新节点
TB N = new tbtnode;
N->data = x;
N->L = N->R = NULL;
p->L = N;
p->ltag = 0;
}
void TB_rsert(TB& p, double x) { //对应节点之后的右差新节点
TB N = new tbtnode;
N->data = x;
N->L = N->R = NULL;
p->R = N;
p->rtag = 0;
}
# Pr,Po,In 遍历
void TR_visit(TR S) { //访问,简单输出
cout << " " << S->data << " ";
}
void TR_PreOrder(TR& T) { //先序遍历
if (T != NULL) {
TR_visit(T); //根
TR_PreOrder(T->L); //左
TR_PreOrder(T->R); //右
}
}
void TR_InOrder(TR& T) { //中序遍历
if (T != NULL) {
TR_InOrder(T->L); //左
TR_visit(T); //根
TR_InOrder(T->R); //右
}
}
void TR_PostOrder(TR& T) { //后序遍历
if (T != NULL) {
TR_PostOrder(T->L); //左
TR_PostOrder(T->R); //右
TR_visit(T); //根
}
}
void TR_count(TR& T) { //中序遍历计算节点个数
if (T != NULL) {
TR_InOrder(T->L); //左
Node_Counter++; //计数器
TR_InOrder(T->R); //右
}
else {
cout << "二叉树共有 " << Node_Counter << "个节点\n";
Node_Counter = 0;
}
}
void TR_LevelOrder(TR& T) { //print:层序遍历,需要用到队列
cout << "\n\n层序遍历T: \n\n";
LQE Q;
LQE_new(Q);
TR p = T; //遍历节点
LQE_in(Q, T); //根节点入队.
while (!LQE_isVoid(Q)) {
LQE_out(Q, p); //队头出队
TR_visit(p); //访问出队节点,这里就实现了把孩子入队的过程.
if (p->L != NULL) LQE_in(Q, p->L);
if (p->R != NULL) LQE_in(Q, p->R);
}
}
void TR_Print(TR& T) { //直接就在这里给我格式化输出了,要求: 每层换行,直观展示...
cout << "\n\n高级层序遍历T: \n\n";
int H = TR_Hight(T); //保存现在的树的高度
TR p = T;
LQE Q;
LQE_new(Q);
LQE_in(Q, T); //根节点入队.
while (!LQE_isVoid(Q)) {//这里判断要出队访问的对象的层数与当前的保存的对象层数是否一样.
LQE_out(Q, p); //队头出队
if (TR_Hight(p) != H) {
H = TR_Hight(p);
cout << endl;
}
TR_visit(p); //访问出队节点,这里就实现了把孩子入队的过程.
if (p->L != NULL) LQE_in(Q, p->L);
if (p->R != NULL) LQE_in(Q, p->R);
}
cout << endl << endl;
}
# 线索二叉树操作
构建操作: 索化遍历前中后
void TB_Pre_Create(TB& T) { //先序线索化二叉树
pre = NULL;
if (T != NULL)
TB_PreOrder(T);
}
void TB_In_Create(TB& T) { //中序线索化二叉树
pre = NULL;
if (T != NULL) {
TB_InOrder(T); //核心;
//if (pre->R == NULL) //这个老是报错很烦不写了,总之退出后之前记录的pre就是最后的一个了,记得处理一下.
// pre->rtag = 1; //处理遍历的最后一个节点:如果右子树为空,则线索化为NULL;
}
}
void TB_Post_Create(TB& T) { //后序线索化二叉树
pre = NULL;
if (T != NULL)
TB_PostOrder(T);
}
void TB_Normal_visit(TB T) { //简单访问:区别于之前的构造线索二叉树的遍历访问方式.
cout << " " << T->data << " \n";
}
//--------------PRE---------------------
//没有三叉链表指向父节点,无法反向输出序列 - 要么是父节点要么是左兄弟子树中最后一个被先序遍历的节点s(由于先序遍历中,子节点只可能是根节点的后续)
//有越位访问的bug,看个思维即可
TB TB_Pre_FirstNode(TB p) {
if (p->ltag == 0) return p->L;
else return p->R;
}
TB TB_Pre_NextNode(TB p) { //前序遍历p的后续:左孩子>右孩子
if (p->rtag == 0)return TB_Pre_FirstNode(p);
else return p->R;
}
void TB_Thread_PreOrder(TB& T) { //特种前序主函数
for (TB p = T; p != NULL; p = TB_Pre_NextNode(p))
TB_Normal_visit(p);
}
//--------------IN----------------------
TB TB_In_FirstNode(TB p) { //找中序线索二叉树的p的后继,并且通过这实现O(1)时间复杂度的非递归中序遍历中序线索二叉树 -01
while (p->ltag == 0) p = p->L; //找最左下节点
return p;
}
TB TB_In_LastNode(TB p) { //找中序线索二叉树的p的前驱,并且通过这实现O(1)时间复杂度的非递归中序反向遍历中序线索二叉树 -02
while (p->rtag == 0) p = p->R; //找最右下节点
return p;
}
TB TB_In_NextNode(TB p) { //直接找后继 / 推演找后继
if (p->rtag == 0) return TB_In_FirstNode(p->R);//根据中序展开的推演结果,后继不是rtag指向的目标就是右子树中的最左下节点(左根右)
else return p->R; //p.rtag==1 ->有线索化了.
}
TB TB_In_PreNode(TB p) { //直接找前驱 / 推演找前驱
if (p->ltag == 0) return TB_In_LastNode(p->L);//根据中序展开的推演结果,前驱不是ltag指向的目标就是左子树中的最右下节点(左根右)
else return p->L; //p.ltag==1 ->有线索化了.
}
void TB_Thread_InOrder(TB& T) { //特种中序主函数
for (TB p = TB_In_FirstNode(T); p != NULL; p = TB_In_NextNode(p))
TB_Normal_visit(p);
}
void TB_Thread_Rev_InOrder(TB& T) { //特种反向中序主函数
for (TB p = TB_In_LastNode(T); p != NULL; p = TB_In_PreNode(p))
TB_Normal_visit(p);
}
//--------------POST----------------
//没有三叉链表指向父节点,无法正向输出序列; -要么是他的父节点要么是右兄弟中第一个被后续遍历的节点
TB TB_Post_LastNode(TB p) {
if (p->rtag == 0) return p->R; //有右孩子, 前驱就是右孩子,否则有左孩子就是左孩子
else return p->L;
}
TB TB_Post_PreNode(TB p) { //前序遍历p的后续:左孩子>右孩子
if (p->ltag == 0)return TB_Post_LastNode(p);
else return p->L;
}
void TB_Thread_Rev_PostOrder(TB& T) { //特种前序主函数
for (TB p = T; p != NULL; p = TB_Post_PreNode(p))
TB_Normal_visit(p);
} //整体和先序的找后续一样,两个极端.
遍历基础二叉树
//线索二叉树的前序中序后序Pr,Po,In遍历
TB pre = NULL; //全局变量来指向当前访问的节点的前驱.
//构建线索二叉树: 直接使用visit来实现.
void TB_visit(TB q) {
if (q->L == NULL) { //左子树位子空了,当作前驱线索指向前面的pre;
q->L = pre;
q->ltag = 1;
}
if (pre != NULL && pre->R == NULL) { //前面有人,并且右子树是空的,当作它的后继线索指向现在的对象.
pre->R = q; //建立前驱节点的后继线索.
pre->rtag = 1;
}
pre = q; //让前驱跟上q节点.
}
void TB_PreOrder(TB& T) { //先序遍历
if (T != NULL) {
TB_visit(T); //根
TB_PreOrder(T->L); //左
TB_PreOrder(T->R); //右
}
}
void TB_InOrder(TB& T) { //中序遍历
if (T != NULL) {
TB_InOrder(T->L); //左
TB_visit(T); //根
TB_InOrder(T->R); //右
}
}
void TB_PostOrder(TB& T) { //后序遍历
if (T != NULL) {
TB_PostOrder(T->L); //左
TB_PostOrder(T->R); //右
TB_visit(T); //根
}
}
void TB_LevelOrder(TB& T) { //print:层序遍历,需要用到队列
cout << "\n\n层序遍历T: \n\n";
TQE Q;
TQE_new(Q);
TB p = T; //遍历节点
TQE_in(Q, T); //根节点入队.
while (!TQE_isVoid(Q)) {
TQE_out(Q, p); //队头出队
TB_visit(p); //访问出队节点,这里就实现了把孩子入队的过程.
if (p->L != NULL) TQE_in(Q, p->L);
if (p->R != NULL) TQE_in(Q, p->R);
}
}
//这个有问题,不搞了
void TB_Print(TB& T) { //直接就在这里给我格式化输出了,要求: 每层换行,直观展示...
cout << "\n\n高级层序遍历T: \n\n";
int H = TB_Hight(T); //保存现在的树的高度
TB p = T;
TQE Q;
TQE_new(Q);
TQE_in(Q, T); //根节点入队.
while (!TQE_isVoid(Q)) {//这里判断要出队访问的对象的层数与当前的保存的对象层数是否一样.
TQE_out(Q, p); //队头出队
if (TB_Hight(p) != H) {
H = TB_Hight(p);
cout << endl;
}
TB_visit(p); //访问出队节点,这里就实现了把孩子入队的过程.
if (p->L != NULL && p->ltag != 1) TQE_in(Q, p->L);
if (p->R != NULL && p->rtag != 1) TQE_in(Q, p->R);
}
cout << endl << endl;
}
# 图
# Tips
全局变量和定义
#define MaxSize 100 //一般最大值.
#define MaxV_num 10 //顶点数目最大值
#define Infinity 114514 //无穷数
bool visited[MaxV_num]; //访问标记
int Distance[MaxV_num]; //最短路径
int path[MaxV_num]; //最短路径的来源
# 基操
定义
//定义的顶点结构:
typedef string DataType; //指定string字符串为表内的数据对象
typedef struct VertexType { //顶点结构
int no{}; //N.O. 顶点的编号
DataType data; //顶点包含的数据
}VT;
//邻接矩阵 MG
typedef struct MGraph {
VT VG[MaxV_num]; //顶点表,类型为自定义VT
int EG[MaxV_num][MaxV_num]{}; //打上了{}代表已经提前都是0的邻接矩阵,0,1或是Wij和0或Infinity
int Vnum{}; //顶点数
int Enum{}; //边数 ==Anum
}MG, * AMG;
//邻接表 LG
typedef struct EdgeNode { //表(后继)结点的类型
int no{}; //代表的顶点序号
DataType data; //权值or信息
struct EdgeNode* next{}; //指向下一个节点
}ED, * EN;
typedef struct VertexNode { //头结点类型
VT data; //头结点
EN First_Edge{}; //指向第一个表结点的指针
}Vnode;
typedef struct Algraph { //邻接表类型
Vnode List[MaxV_num]; //表的本体
int Vnum{}; //顶点数
int Enum{}; //边数
}LG, * ALG;
//Queue存放顶点对象VT;
typedef struct Queue {
VT node[MaxSize]{};
int front{};
int back{}; //队头队尾指针,rear=back,代表插入的队尾,是不断前进的
}*QU, que;
构造: 输入式/数组式
void MG_input(MG& M) { //输入邻接矩阵的边的信息(0代表第一个点)
cin >> M.Enum >> M.Vnum; //输入邻接矩阵的顶点数和边数
int outone, inone;
for (int i = 0; i < M.Enum; i++) { //输入边的信息
inp:cin >> outone >> inone; //输入行,列(可以只搞上三角)
if (outone == inone) {//输到对角元素上了,不行,自己没有自己
cout << "\n错误!不能指向自己!\n";
goto inp;
}
M.EG[outone][inone] = 1; //对应的值赋1;
}
for (int i = 1; i < M.Vnum; i++) // 为邻接矩阵下三角赋值-简单的镜面对称
for (int j = 0; j < i; j++)
M.EG[i][j] = M.EG[j][i];
for (int i = 0; i < M.Vnum; i++) {
M.VG[i].no = i; //顶点元素赋值
}
}
void MG_EZnew(MG& M) { // 简单生成一个邻接矩阵5-5 (eg), 也可以有一个临时数组
M.Enum = M.Vnum = 5; //分别对5个顶点的出度赋值,然后后面景象到入度.无向图.
M.EG[0][4] = 1;
M.EG[0][2] = 1;
M.EG[1][2] = M.EG[1][3] = 1;
M.EG[2][0] = M.EG[2][1] = M.EG[2][3] = 1;
M.EG[3][2] = M.EG[3][1] = 1;
M.EG[4][0] = 1;
//还有顶点的名字赋值:no项:
for (int i = 0; i < M.Vnum; i++) {
M.VG[i].no = i; //顶点元素赋值
}
}
转换为邻接表
void LG_Create_from_MG(ALG& lg, MG mg) {//由图的邻接矩阵创建图的邻接表
EdgeNode* p; //指向表结点的临时指针
lg = new LG; //新建LG邻接表
for (int i = 0; i < mg.Vnum; i++) //为邻接表所有头结点的指针域赋初值
lg->List[i].First_Edge = NULL;
for (int i = 0; i < mg.Vnum; i++)
for (int j = mg.Vnum - 1; j >= 0; j--)
if (mg.EG[i][j] != 0) //这里有条边的话.
{ //若顶点i、j之间有边
p = new EdgeNode; // 新表结点
p->no = j;
p->data = mg.EG[i][j];
p->next = lg->List[i].First_Edge;
lg->List[i].First_Edge = p;
}
lg->Vnum = mg.Vnum;
lg->Enum = mg.Enum;
for (int i = 0; i < lg->Vnum; i++) {
lg->List[i].data.no = i; //顶点元素赋值
}
}
输出
void MG_print(MGraph mg) { //简单输出图的邻接矩阵
for (int i = 0; i < mg.Vnum; i++) {
for (int j = 0; j < mg.Vnum; j++)
printf("%3d", mg.EG[i][j]);
cout << endl;
}
}
void LG_print(ALG lg) {//输出图的邻接表
EN p;
for (int i = 0; i < lg->Vnum; i++) {
p = lg->List[i].First_Edge; //指向第一位
if (p) printf("%3d：", i); //打印结点
while (p) { //打印链表内元素
printf("%3d", p->no);
p = p->next;
}
cout << endl;
}
}
插入
void MG_inVex(MG& G, VT v) { //插入顶点 ,由于数组下标比数量少1，可用旧顶点数做下标
G.VG[G.Vnum] = v; //顶点表增加
G.Vnum++; //顶点数加1
for (int i = 0; i < G.Vnum; i++) { //初始化新顶点与其他顶点关联:0
G.EG[G.Vnum - 1][i] = 0;
G.EG[i][G.Vnum - 1] = 0; //倒置下三角赋值,学到了
}
}
删除
void MG_delVex(MG& G, VT v) { //顶点删除 - 简单的方法: 只是将节点对应的行和列变为0,同时加上一个isVoid变量来判断是否为无效点.
int p = MG_findVex(G, v); //存放待删顶点下标位置
for (int i = 0; i < G.Vnum; i++) { //删除待删顶点所在列数据
for (int j = p + 1; j < G.Vnum; j++) {
G.EG[i][j - 1] = G.EG[i][j]; //后面的移动到前面来覆盖
}
}
for (int i = 0; i < G.Vnum; i++) { //删除待删顶点所在行数据
for (int j = p + 1; j < G.Vnum; j++) {
G.EG[j - 1][i] = G.EG[j][i]; //后面的移动到前面来覆盖
}
}
for (int i = p + 1; i < G.Vnum; i++) //删除在顶点集中的待删顶点
G.VG[i - 1] = G.VG[i]; //后面的移动到前面来覆盖
G.Vnum--; //顶点数自减
}
边的操作
void MG_inEdge(MG& G, VT v1, VT v2) { //插入边,同时可以插入权值
int p1 = MG_findVex(G, v1), p2 = MG_findVex(G, v2); //存放两个关联点位置
G.EG[p1][p2] = G.EG[p2][p1] = 1; //将关联点在矩阵两处(边权)赋值
}
void MG_delEdge(MG& G, VT v1, VT v2) {//删除边
int p1 = MG_findVex(G, v1), p2 = MG_findVex(G, v2); //存放两个关联点位置
G.EG[p1][p2] = G.EG[p2][p1] = 0; //将关联点在矩阵两处边权赋为0
}
# BFS
void MG_BFS(MG& mg, QU& Q, int v) { //广度优先遍历核心部分.
MG_BDfs_visit(mg, v); //设计的MG矩阵的广度优先以及深度优先搜索visit函数
visited[v] = true;
QU_in(Q, mg.VG[v]); //入队0.
while (!QU_isVoid(Q)) {
int u = QU_head(Q); //
QU_out(Q); //简单的队头元素出队,并取值.
for (int j = 0; j < mg.Vnum; j++) { //从u元素对应的行开始找临界对象
if (mg.EG[u][j] != 0 && visited[j] == false) { //有边且未被访问过
MG_BDfs_visit(mg, j);
visited[j] = true; // 置顶点已被访问标志
QU_in(Q, mg.VG[j]); // 顶点j进队
}
}
}
}
void MG_BFS_Main(MG& mg) { //邻接矩阵的广度优先遍历
for (int i = 0; i < mg.Vnum; i++)
visited[i] = false; //标记数组初始化;
QU Q = QU_new(Q);
for (int i = 0; i < mg.Vnum; i++) //继续调用
if (visited[i] == false) //对于每个联通分量调用一次BFS
MG_BFS(mg, Q, i);
}
void LG_BFS(LG& lg, QU& Q, int v) { //
LG_BDfs_visit(lg, v);
visited[v] = true;
QU_in(Q, lg.List[v].data); //入队
EdgeNode* p;
while (!QU_isVoid(Q)) {
int u = QU_head(Q); //
QU_out(Q); //简单的队头元素出队,并取值.// 按邻接表顺序考察与顶点v邻接的各顶点w
for (p = lg.List[u].First_Edge; p != NULL; p = p->next) {
int k = p->no; //设置k为中介,获得边节点p的顶点值
if (visited[k] == false) {
LG_BDfs_visit(lg, k);
visited[k] = true; // 置顶点w已被访问标志
QU_in(Q, lg.List[k].data); //放入k
}
}
}
}
void LG_BFS_Main(LG& lg) { //邻接表的广度优先遍历.
for (int i = 0; i < lg.Vnum; i++)
visited[i] = false; //标记数组初始化;
QU Q = QU_new(Q);
for (int i = 0; i < lg.Vnum; i++)
if (visited[i] == false)
LG_BFS(lg, Q, i);
}
# DFS
void MG_DFS(MG& mg, int v) {
MG_BDfs_visit(mg, v);
visited[v] = true;
for (int j = 0; j < mg.Vnum; j++) {
if (mg.EG[v][j] != 0 && visited[j] == false)
MG_DFS(mg, j);
}
}
void MG_DFS_Main(MG& mg) { //邻接矩阵的深度优先遍历(from0)
for (int i = 0; i < mg.Vnum; i++)
visited[i] = false; //标记数组初始化;
for (int i = 0; i < mg.Vnum; i++) //继续调用
if (visited[i] == false) //对于每个联通分量调用一次BFS
MG_DFS(mg, i);
}
void LG_DFS(LG& lg, int v) {
EdgeNode* p;
LG_BDfs_visit(lg, v);
visited[v] = true;
p = lg.List[v].First_Edge;
while (p) { // 检查所有与顶点i相邻接的顶点
if (visited[p->no] == 0) // 如果该顶点未被访问过
LG_DFS(lg, p->no); // 从邻接顶点出发深度优先搜索
p = p->next; // 考察下一个邻接顶点
}
}
void LG_DFS_Main(LG& lg) { //邻接表的广度优先遍历.
for (int i = 0; i < lg.Vnum; i++)
visited[i] = false; //标记数组初始化;
for (int i = 0; i < lg.Vnum; i++)
if (visited[i] == false)
LG_DFS(lg, i);
}
# 最短路径
BFS 求无权图最短路径
void LG_MD_BFS(LG& lg, int u) { //求u到其他顶点的最短路径distance[u]
QU Q; //创建队列
QU_new(Q);
EdgeNode* p;
for (int i = 0; i < lg.Vnum; i++)
visited[i] = false; //标记数组初始化;
for (int i = 0; i < lg.Vnum; i++) {
Distance[i] = Infinity; //initial
path[i] = -1; //from where?
}
Distance[u] = 0;
visited[u] = true;
QU_in(Q, lg.List[u].data); //入队
while (!QU_isVoid(Q)) {
u = QU_head(Q); //
QU_out(Q); //简单的队头元素出队,并取u值.
for (p = lg.List[u].First_Edge; p != NULL; p = p->next) {
int k = p->no; //设置k为中介,获得边节点p的顶点值
if (visited[k] == false) {
Distance[k] = Distance[u] + 1; //路径长度加1(可改对应权值
path[k] = u;
visited[k] = true; // 置顶点w已被访问标志
QU_in(Q, lg.List[k].data); //放入k
}
}
}
cout << "目标顶点" << u << "到其他节点的带权路径长度为\n";
for (int i = 0; i < lg.Vnum; i++)
cout << Distance[i] << " ";
cout << endl;
}
void MG_MD_BFS(MG& mg, int u) { //求u到其他顶点的最短路径distance[u]
QU Q; //创建队列
QU_new(Q);
for (int i = 0; i < mg.Vnum; i++)
visited[i] = false; //标记数组初始化;
for (int i = 0; i < mg.Vnum; i++) {
Distance[i] = Infinity; //initial
path[i] = -1; //from where?
}
Distance[u] = 0;
visited[u] = true;
QU_in(Q, mg.VG[u]); //入队
while (!QU_isVoid(Q)) {
u = QU_head(Q); //
QU_out(Q); //简单的队头元素出队,并取u值.
for (int j = 0; j < mg.Vnum; j++) { //从u元素对应的行开始找临界对象
if (mg.EG[u][j] != 0 && visited[j] == false) {
Distance[j] = Distance[u] + 1;
path[j] = u;
visited[j] = true; // 置顶点j已被访问标志
QU_in(Q, mg.VG[j]); //放入j
}
}
}
cout << "目标顶点" << u << "到其他节点的带权路径长度为\n";
for (int i = 0; i < mg.Vnum; i++)
cout << Distance[i] << " ";
cout << endl;
}
# 查找排序
(只有部分内容)
# 希尔
void Shellsort(int A[], int n) {
int d, i, j;
for (d = n / 2; d >= 1; d = d / 2) //步长变化
for (i = d + 1; i <= n; ++i)
if (A[i] < A[i - d]) { //需要将A[i]插入有序增量子表
A[0] = A[i]; //暂存在A[0]
for (j = i - d; j > 0 && A[0] < A[j]; j -= d)
A[j + d] = A[j]; //后移寻找插入位置
A[j + d] = A[0]; //插入
}
}
# 堆
void HeadAdjust(int A[], int k, int len) { //把以k为根的子树调整为大根堆
A[0] = A[k]; //A[0]暂时存放子树的根节点.
for (int i = 2 * k; i <= len; i *= 2) { //从key较大的元素向下筛选
if (i < len&& A[i] < A[i + 1])
i++;
if (A[0] >= A[i])
break; //筛选结束.
else {
A[k] = A[i]; //调整双亲节点为A[i]
k = i; //更新k值以便向下筛选
}
}
A[k] = A[0]; //被筛选的节点的值放入最终位置.
}
void Build_Maxheap(int A[], int len) {
for (int i = len / 2; i > 0; i--)
HeadAdjust(A, i, len); //从后往前调整所有非终端节点.
}
void HeapSort_main(int A[], int len) {
Build_Maxheap(A, len); //初始化.大根堆
for (int i = len; i > 1; i--) {
swap(A[i], A[1]); //交换堆顶元素和堆底元素 , 自带函数.
HeadAdjust(A, 1, i - 1); //剩余元素整理为堆的形式
}
}
# 归并
//int* F = new int[7]; //辅助数组B(f), 用来镜面数组A.
int F[8];
void Merge(int A[], int low, int mid, int high) { //A[low...mid]和A[mid+1...high]各自有序,将两个部分归并
int i, j, k;
for (k = low; k < high; k++)
F[k] = A[k]; //构建镜面辅助数组;
for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
if (F[i] < F[j])
A[k] = F[i++];
else A[k] = F[j++]; //将二者的较小值复制到A中.
}
while (i <= mid) A[k++] = F[i++];
while (j <= high) A[k++] = F[j++];
}
void MergeSort_main(int A[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2; //从中间划分
MergeSort_main(A, low, mid); //对左半部分归并排序
MergeSort_main(A, mid + 1, high); //对右半部分归并排序
Merge(A, low, mid, high); //Merge!
}
}