[Code Journal#1] 2022/2/20

1. 求最大公约数gcd(a,b) OJW1T2

int gcd(int a,int b)
{
    return b ? gcd(b ,a % b) : a;
}

2. Trie树：OJW1T4

一种数据结构，利用公共前缀压缩存储空间。

本质为一棵26叉树，树干上存储每一条字符对应的结点。

支持单词的插入、查询、求前缀等功能。

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
struct node{
	node* nxt[26];
	bool isend;
};
node* New()
{
	node* p = new node;
	for (int i = 0 ; i <= 25 ; i++)
		p->nxt[i] = NULL;
	p->isend = false;
	return p;
}
node *root = New();//建立根节点 
int n;
void insert(string s)
{
	node* cur = root;
	int len = s.size();
	for (int i = 0 ; i < len ; i++)
		{
			if(cur->nxt[s[i] - 'a'] == NULL) //若当前位置结点不存在s[i]的后继连边，建立新节点
				{
					node* p = New();	
					cur->nxt[s[i] - 'a'] = p;
				}
			cur = cur->nxt[s[i] - 'a'];//往后连接。 
		}
	cur->isend = true;//标记为结尾。 
}
bool search(string s)
{
	node* cur = root;
	int len = s.size();
	for (int i = 0 ; i < len ; i++)
		{
			if(cur->nxt[s[i] - 'a'] == NULL)
				return false;
			cur = cur->nxt[s[i] - 'a'];
		}
	return cur != NULL && cur->isend;
 } 
int main()
{
	root->isend = false;
	scanf("%d", &n);
	char t;
	string str;
	for (int i = 1 ; i <= n ; i++)
		{
			cin >> t;
			cin >> str;	
			if(t == 'I')
				{
					insert(str);
					continue;
				}
			if(t == 'S')
				{
					if(search(str))
						printf("YES\n");
					else
						printf("NO\n");
					continue;
				}
				
		}
	return 0;
}

尤其注意的是，当我们在结构体类型中声明指针类型的时候。一定要对其内部的指针进行初始化！这样其指针才处于正确的初始状态，本题中要求每个结点的指针预处理成空指针。细节！

3. C++提供的STL二分查找

#include <algorithm>
//头文件库为alg

int a[N];
//注意，二分查找的对象应当为有序表，所以需要对数组进行预处理：排序！
sort(a + 1,a + 1 + n);
cin >> val;//input the queryed val;

int pos = lower_bound(a + 1,a + 1 + n,val) - a;//lower_bound里面的三个参数，第一个为查找起始，
//第二个为查找终点，第三个为查找的数。在有序表中找到第一个大于等于val的数，并返回其地址。
//和数组开头元素的地址做差之后，就能得到对应的，第一个大于等于val的元素在序列中的下标。
a[pos]>=val

4.快速读入：

inline long long read() {
	long long x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}

5. 二叉搜索树：

OJW2T4

/*
维护一颗二叉搜索树
支持插入、删除、打印 

树的结点应当维护以下信息：
（1）本身的电锯“标号” ，数值域 
（2） 结点的插入次数k
（3）左、右儿子 
*/
#include <cstdio>
#include <iostream>
using namespace std;
struct node{
	int val;//记录数据域 
	int cnt;//记录插入次数
	node *l,*r,*fa; 
};//二叉搜索树结点定义
node *rt = NULL;
node* New(node* t,int data)//新建结点函数，返回结点地址 
{
	node* p = new node;
	p->cnt = 1;
	p->fa = t;//记录父亲 
	p->l = NULL;
	p->r = NULL;
	p->val = data;
	return p;
}
/*Insert Function */ 
void insert(node* root,int data)//将data插入到这棵树
{
	if(root == NULL) //若新插入的结点是第一个结点，也就是新建树，单独处理一下
		{
			node* p = New(NULL,data);
			rt = p;//维护全局根节点 
			return;
		} 
	if(root->val == data)//如果已经找到对应结点，直接加权
		{
			root->cnt++;
			return;	
		} 
	if(root->val > data)//若根节点比data大，递归访问左子树 
		{
			if(root->l == NULL)//若不存在左子结点，直接新建并且与父结点连接 
				{
					node* p = New(root,data);
					root->l = p;//父结点的左子结点为p 
					return;
				} 
			insert(root->l,data);
		}
	else
		{
			if(root->r == NULL)//若不存在左子结点，直接新建并且与父结点连接 
				{
					node* p = New(root,data);
					root->r = p;//父结点的左子结点为p 
					return;
				} 
			insert(root->r,data);		
		}
}
/*Find the direct succession*/
node* s(node* root)//找到直接后继 
{
	while(root->l)
		{
			root = root->l;
		}
	return root;
}
/*Delete Function*/
void erase(node* root)//删除根的结点 
{
	if(root->l == NULL && root->r == NULL)//没有左右结点 
		{
			if(root->fa)//不是根节点 
				{
					if(root->fa->l == root)//被删除结点是父结点的左儿子 
						root->fa->l = NULL;//删除 
					else//删除右儿子 
						root->fa->r = NULL;
					root->fa = NULL;
				}
			//此时可以放心大胆地删除！ 
			else //若删除的结点是一个根节点
				rt = NULL;//还需要清空标准根地址 
			delete root;
			return;
		}
	if(root->l != NULL && root->r == NULL)//如果只存在左子结点 
		{
			if(root->fa != NULL)//fa如果不是根节点，调整root左子结点为root位置即可。 
				{
					if(root->fa->l == root)//如果root是父结点的左儿子 
					{
						root->fa->l = root->l;//把父节点的左儿子设置成root的左儿子 
						root->l->fa = root->fa;
					}
					else
					{
						root->fa->r = root->l;
						root->l->fa = root->fa;
					}
					delete root;
					return;
				}
			//若为根节点，则直接把左子结点设置为根节点即可。 
			rt = root->l;
			root->l->fa = NULL;
			delete root;
			return;
		}
	if(root->l == NULL && root->r != NULL)//如果只存在右子结点 
		{
			if(root->fa != NULL)//fa如果不是根节点，调整root左子结点为root位置即可。 
				{
					if(root->fa->l == root)
					{
						root->fa->l = root->r;
						root->r->fa = root->fa;
					}
					else
					{
						root->fa->r = root->r;
						root->r->fa = root->fa;
					}
					delete root;
					return;
				}
			//若为根节点，则直接把右子结点设置为根节点即可。 
			rt = root->r;
			root->r->fa = NULL;
			delete root;
			return;
		}
	//最后一种情况，同时存在左右节点，需要找到后继来。
	node* suc = s(root->r);//先找到后继，再进行数据交换
	int t1 = root->val, t2 = root->cnt;
	root->val = suc->val;
	root->cnt = suc->cnt;
	suc->val = t1;
	suc->cnt = t2;
	erase(suc);
	return; 
}
/*Minus Function*/
void sub(node* root,int data)
{
	if(root == NULL) //若删除结点是空结点，忽略操作 
		{
			return;
		} 
	if(root->val == data)//如果已经找到对应结点，直接删去一次 
		{
			root->cnt--;
			if(root->cnt == 0)
				erase(root);
			return;	
		} 
	if(root->val > data)//若根节点比data大，递归在左子树查找删除结点 
		{
			sub(root->l,data);
		}
	else
		{
			sub(root->r,data);	
		}
		return;
}

/*First Order dfs*/
void VLR(node* root)
{
	if(root == NULL)
		return;
	printf("%d ", root->val);
	if(root->l)
		VLR(root->l);
	if(root->r)
		VLR(root->r);
	return;
}
int M;
int main()
{
	int type, tmp;
	scanf("%d", &M);
	while(M--)
		{
			scanf("%d", &type);
			if(type == 0)
				{
					VLR(rt);
					printf("\n");
					continue;
				}
			if(type == 1)
				{
					scanf("%d", &tmp);
					insert(rt,tmp);
					continue;
				}
			if(type == 2)
				{
					scanf("%d", &tmp);
					sub(rt,tmp);
					continue;
				}
		}
	return 0;
}

原文链接：https://blog.csdn.net/hjrxfly/article/details/123036189

你可能也喜欢