技术标签: 数据结构
由于本人水平有限,整理的代码若有错漏欢迎指出
```c++
#include<bits/stdc++.h>
#include<string>
#include<cctype>
using namespace std;
//浙江大学数据结构练习
//多项式加法的实现
struct PolyNode{
int coef;//系数
int expon;//指数
struct PolyNode * link;//指向下一个结点的指针
};
typedef struct PolyNode *Poly;
Poly P1, P2;
int Compare(int a,int b)
{
if(a>b) return 1;
else if(a==b) return 0;
else return -1;
}
void Attach(int c,int e,Poly * pRear)
{
Poly P;
P=(Poly)malloc(sizeof(struct PolyNode));
P->coef=c;
P->expon=e;
P->link=NULL;//对新结点赋值
(*pRear)->link=P;//把新结点插到rear的后面
*pRear=P;//pRear是指针的指针
}
Poly PolyAdd(Poly P1, Poly P2)
{
Poly front, rear, temp;
int sum;
rear = (Poly)malloc(sizeof(struct PolyNode));
front = rear;//由front记录结果多项式链表的头节点
while (P1&&P2) {
switch(Compare(P1->expon,P2->expon)){
//Compare函数第一个参数值大就返回1
case 1:
Attach(P1->coef,P1->expon,&rear);
//把这一项拷贝到结果多项式
P1=P1->link;//P1后挪
break;
case -1:
Attach(P2->coef,P2->expon,&rear);
P2=P2->link;
break;
case 0:
sum=P1->coef+P2->coef;
if(sum) Attach(sum,P1->expon,&rear);
P1=P1->link;
P2=P2->link;
break;
}
}
//将未处理完的另一个多项式所有结点复制到结果
for(;P1;P1=P1->link) Attach(P1->coef,P1->expon,&rear);
for(;P2;P2=P2->link) Attach(P2->coef,P2->expon,&rear);
rear->link=NULL;
temp=front;
front=front->link;
free(temp);
return front;
}
Poly ReadPoly()
{
int N,c,e;
Poly Rear,P,t;
cin>>N;
P=(Poly)malloc(sizeof(struct PolyNode));//申请空结点
//链表空头节点
P->link=NULL;
Rear=P;
while(N--){
cin>>c>>e;//输入系数指数
Attach(c,e,&Rear);
}
t=P;P=P->link;free(t);//删除临时生产的头节点 free释放malloc申请的内存
//P指向链表头节点
return P;
}
void PrintPoly(Poly p)
{
int flag=0;
if(!p) cout<<"0"<<endl;
while(p){
if(!flag) flag=1;//判断是不是第一项
else cout<<" ";
cout<<p->coef<<" "<<p->expon<<" ";
p=p->link;
}
}
int main()//读入多项式
{
Poly P1,P2,PS;
P1=ReadPoly();
P2=ReadPoly();
PS=PolyAdd(P1,P2);
PrintPoly(PS);
return 0;
}
二叉树的储存结构
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode{
ElementType Data;
BinTree Left;//左儿子
Bintree Right;//右儿子
};
void PreOrderTraversal(BinTree BT)
{
if(BT){
cout<<BT->Data;
PreOrderTraversal(BT->Left);
PreOrderTraversal(BT->Right);
}
}
void InorderTraversal(BinTree BT)
{
if(BT){
InOrderTraversal(BT->Left);
cout<<BT->Data;
InorderTraversal(BT->Right);
}
}
void PostOrderTraversal(BinTree BT)
{
if(BT){
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
cout<<BT->Data;
}
}
1.从队列中取出有个元素2.访问该元素所指的结点3.若该结点所指的左右结点非空则将其左右儿子是指针顺序入队
#include<bits/stdc++.h>
using namespace std;
#define MaxSize 10000
//浙江大学数据结构二叉树
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode{
int Data;
BinTree Left;
BinTree Right;
};
struct QNode{
BinTree Data[MaxSize];
int rear;
int front;
};
typedef struct QNode *Queue;//队列
void CreatQueue(Queue Q)
{
Q->front=0;Q->rear=0;
}
bool IsemptyQ(Queue Q)
{
return (Q->front==Q->rear);
}
void AddQ(Queue ptrQ,BinTree item)
{
//入队函数
if((ptrQ->rear+1)%MaxSize==ptrQ->front )
cout<<"队列满";
ptrQ->rear= (ptrQ->rear+1)%MaxSize;
ptrQ->Data[ptrQ->rear]=item;
}
BinTree DeleteQ(Queue ptrQ)
{
//出队函数
if(ptrQ->front==ptrQ->rear){
cout<<"队列空";
return ERROR;}
else{
ptrQ->front=(ptrQ->front+1)%MaxSize;
return ptrQ->Data[ptrQ->front];
}
}
void LevelOrderTraversal(BinTree BT)
{
//层序遍历
Queue Q;
BinTree T;
if(!BT) return;//若是空树则返回
CreatQueue(Q);//创建并初始化队列
AddQ(Q,BT);
while(!IsemptyQ(Q)){
T=DeleteQ(Q);
cout<<T->Data<<endl;
if(T->Left) AddQ(Q,T->Left);
if(T->Right) AddQ(Q,T->Right);
}
}
由两种遍历序列确定二叉树必须要有中序遍历!
1.根据先序遍历第一个结点确定根节点
2.根据根节点在中序遍历中分割成左子树和右子树
3.分别递归实现
知前序和中序遍历求后续遍历(hdu1710)
#include<bits/stdc++.h>
using namespace std;
//hdu1710知道二叉树前序和中序遍历求后序遍历
const int N=1010;
int pre[N],in[N],post[N];
int k;
struct TreeNode{
int value;
TreeNode * Left;
TreeNode * Right;
TreeNode(int value=0,TreeNode * Left=NULL,TreeNode * Right=NULL):value(value),Left(Left),Right(Right){
}
};
void buildtree(int L,int R,int &t,TreeNode* &root){
//建树
int flag=-1;
for(int i=L;i<=R;i++)
if(in[i]==pre[t]){
//先序的第一个是根,找到对应中序的位置
flag=i;break;
}
if(flag==-1) return;
root=new TreeNode(in[flag]);//新建结点
t++;
if(flag>L) buildtree(L,flag-1,t,root->Left);
if(flag<R) buildtree(flag+1,R,t,root->Right);
}
void PostOrder(TreeNode* root){
if(root!=NULL){
PostOrder(root->Left);
PostOrder(root->Right);
post[k++]=root->value;
}
}
void remove(TreeNode* root)
{
if(root==NULL) return;
remove(root->Left);
remove(root->Right);
delete root;//释放空间
}
int main()
{
int n;
while(cin>>n){
for(int i=1;i<=n;i++) cin>>pre[i];
for(int j=1;j<=n;j++) cin>>in[j];
TreeNode* root;
int t=1;
buildtree(1,n,t,root);
k=0;
PostOrder(root);
for(int i=0;i<k;i++) {
cout<<post[i];
if(i==k-1) cout<<endl;
else cout<<" ";
}
remove(root);
}
return 0;
}
两棵树通过若干次左右儿子的互换可变成对方则这两棵树同构
判断根节点:静态数组里面没有用到的结点即对应的Element为根
//二叉树的表示:静态链表
#define MaxTree 10
#define ElementType char
#define ELT ElementType
#define Tree int
#define Null -1//区分NULL
struct TreeNode{
ELT Element;
Tree Left;
Tree Right;
}T1[MaxTree],T2[MaxTree];
Tree BuildTree(struct TreeNode T[])//建树
{
char cl,cr;
int N,check[MaxTree],Root;
cin>>N;
if(N){
for(int i=0;i<N;i++) check[i]=0;
for(int i=0;i<N;i++){
scanf("%c %c %c\n",&T[i].Element,&cl,&cr);
if(cl!='-'){
T[i].Left=cl-'0';
check[T[i].Left]=1;
}
else T[i].Left=Null;
if(cr!='-'){
T[i].Right=cl-'0';
check[T[i].Right]=1;
}
else T[i].Right=Null;
}
for(int i=0;i<N;i++)
if(!check[i]) {
Root=i;break;}
}
return Root;
}
#include<bits/stdc++.h>
using namespace std;
//二叉树的表示:静态链表
#define MaxTree 100
#define ElementType char
#define ELT ElementType
#define Tree int
#define Null -1//区分NULL
struct TreeNode{
ELT Element;
Tree Left;
Tree Right;
}T1[MaxTree],T2[MaxTree];
Tree BuildTree(struct TreeNode T[])//建树
{
char cl,cr;
int N,check[MaxTree],Root;
cin>>N;
if(N){
for(int i=0;i<N;i++) check[i]=0;
for(int i=0;i<N;i++){
scanf("%c %c %c\n",&T[i].Element,&cl,&cr);
if(cl!='-'){
T[i].Left=cl-'0';
check[T[i].Left]=1;
}
else T[i].Left=Null;
if(cr!='-'){
T[i].Right=cl-'0';
check[T[i].Right]=1;
}
else T[i].Right=Null;
}
for(int i=0;i<N;i++)
if(!check[i]) {
Root=i;break;}
}
return Root;
}
int Isomorphic(Tree R1,Tree R2)//判断两棵树是否同构
{
if((R1==Null)&&(R2==Null))
return 1;
if(((R1==Null)&&(R2!=Null))||((R1!=Null)&&(R2==Null)))
return 0;
if(T1[R1].Element!=T2[R2].Element)
return 0;
if((T1[R1].Left==Null)&&(T2[R2].Left==Null))//左子树都是空的
return Isomorphic(T1[R1].Right,T2[R2].Right);
if(((T1[R1].Left!=Null)&&(T2[R2].Left!=Null))&&
((T1[T1[R1].Left].Element)==(T2[T2[R2].Left].Element)))
return(Isomorphic(T1[R1].Left,T2[R2].Left)&&
(Isomorphic(T1[R1].Right,T2[R2].Right)));
else
return (Isomorphic(T1[R1].Left,T2[R2].Right)&&
(Isomorphic(T1[R1].Right,T2[R2].Left)));
}
int main()//判断两个二叉树是否同构
{
Tree R1,R2;
R1=BuildTree(T1);
R2=BuildTree(T2);
if(Isomorphic(R1,R2)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
主要思路:先建一棵树,然后把每个序列分别比较。对于一个序列,如果在查找过程中经过在树上有为被访问过的点则不是一棵树
#include<bits/stdc++.h>
using namespace std;
// 判别是否同一颗二叉树
typedef struct TreeNode *Tree;
struct TreeNode{
int v;//结点的值
Tree Left,Right;
int flag; //标志这个点是否访问过
};
Tree NewNode(int V)
{
Tree T=(Tree)malloc(sizeof(struct TreeNode));
T->v=V;
T->Left=T->Right=NULL;
T->flag=0;
return T;
}
Tree Insert(Tree T,int V)
{
if(!T) T=NewNode(V);
else{
if(V>T->v)
T->Right=Insert(T->Right,V);
else
T->Left=Insert(T->Left,V);
}
return T;
}
Tree MakeTree(int N)
{
Tree T;
int i,V;
cin>>V;
T=NewNode(V);
for(int i=1;i<N;i++){
cin>>V;
T=Insert(T,V);
}
return T;
}
int check(Tree T,int V)
{
if(T->flag){
if(V<T->v) return check(T->Left,V);
else if(V>T->v) return check(T->Right,V);
else return 0;//同一个数字出现两次
}
else{
if(V==T->v){
T->flag=1;
return 1;
}
else return 0;
}
}
int Judge(Tree T,int N)
{
int i,V,flag=0;
//flag=0代表目前还一致,1代表已经不一致
cin>>V;
if(V!=T->v) flag=1;
else T->flag=1;
for(int i=1;i<N;i++){
cin>>V;
if((!flag)&&(!check(T,V))) flag=1;
//如果不行则不再check但要继续读完
}
if(flag) return 0;
else return 1;
}
void ResetT(Tree T)
{
if(T->Left) ResetT(T->Left);
if(T->Right) ResetT(T->Right);
T->flag=0;
}
void FreeTree(Tree T)//释放空间
{
if(T->Left) FreeTree(T->Left);
if(T->Right) FreeTree(T->Right);
free(T);
}
int main()
{
int N,L,i;
Tree T;
cin>>N;
while(N)
{
cin>>L;
T=MakeTree(N);
for(int i=0;i<L;i++)
{
if(Judge(T,N)) cout<<"Yes\n";
else cout<<"No"<<endl;
ResetT(T);//清楚T中的标记flag
}
FreeTree(T);
cin>>N;
}
return 0;
}
文章浏览阅读385次。基于Arduino uno,获取红外寻迹传感器的原始值_怎么检测红外寻迹模块返回值
文章浏览阅读494次,点赞5次,收藏9次。单片机(Microcontroller)是一种集成了微处理器核心、存储器、输入/输出接口和定时器等功能模块的集成电路芯片,具有体积小、功耗低、性价比高等特点,被广泛应用于各个领域。单片机的发展历史可以追溯到20世纪70年代,当时的单片机功能有限,主要用于简单的控制任务。
文章浏览阅读412次。https://zhuanlan.zhihu.com/p/54096381_生成对抗网络 python代码
文章浏览阅读5.2k次,点赞7次,收藏18次。有时候我们需要在网页上展示一些数据,如某公司想在网页上展示公司的库存清单。如下表:想在网页上展示上述表格效果可以使用以下代码:创建表格的四个元素:table、tbody、tr、th、td1、…:整个表格以标记开始、标记结束。2、…:当表格内容非常多时,表格会下载一点显示一点,但如果加上标签后,这个表格就要等表格内容全部下载完才会显示。如右侧代码编辑器中的代码。3、…_怎样在网站中添加表格别人可以下载
文章浏览阅读770次。到目前为止,我们已经讨论了如何将对象实例公开给QML上下文。有时我们还希望在QML中可以使用注册类本身。注册允许将类当作QML中的数据类型来使用。此外,注册还可以提供其他功能,比如允许在QML中将类用作可实例化的QML对象类型,或者允许在QML中导入和使用类的单例实例。通常我们使用Q_OBJECT宏注册从QObject派生的类,也可以用Q_GADGET宏声明一个比QObject“更轻”的版本。在这些更轻的类中,我们可以访问它们的属性、枚举和可调用的方法,但不能使用信号槽系统,我们稍后会进行介绍。1. 注_qmlregisteruncreatabletype
文章浏览阅读2.1k次,点赞7次,收藏15次。头文件与命名空间的关系 Q:有些书说有些头文件不在std里是什么意思?std里包含些什么?为什么不用std就不能使用cout?头文件中声明的东西为什么在使用的时候需要先using namespace std;一下?如果我不用#include和其他头文件。只用using namespace std 的话,是不能用cout的。这说明cout是在iostream里声明_c#中命名空间和c语言中头文件之间的关系
文章浏览阅读1.2k次,点赞2次,收藏8次。注释dtype=np.int代表导入数据的格式为整数delimiter=’,'代表原始数据的存储格式为以‘,’为间隔原始文件中以‘#’开头的行代表被注释,不会被np.loadtxt读取通过[[0] * b for i in range(a)]的方式初始化一个x[a][b]的二维数组np.savetxt()函数可以用来保存数据,第一个参数为保存数据的路径,其中C是自定义的文件名,如果该文..._python 读取csv矩阵乘法
文章浏览阅读1.4k次。军团要塞2绘画渲染(a)美术概念 (b)游戏内玩家看到的角色摘要在《军团要塞2》中我们提出了一整套美术方案和新的实时渲染技术,这种技术能实现出一种独一无二的渲染风格。《军团要塞2》由美术和程序基于20世纪初时商业插画中的传统风格合作完成。在这篇论文中,我们会结合美术方向与技术选择,来讨论如何支持美术目标和玩法限制。除了实现一种有冲击力的风格外,我们也设计了边缘光照和亮度与色调变化的着色器技..._军团要塞画师
文章浏览阅读9.6k次,点赞8次,收藏65次。这里介绍:RGB图3个通道的提取、RGB图转灰度图、图片反转、图片亮度调整具体操作,需导入的库如下:原图如下:结果如下,从左到右分别是:Red,Green,Blue这里借助skimage库中的exposure函数来进行图像亮度的调整结果如下:........._jupter rgb灰度直方图提取
文章浏览阅读931次。2023年地级、省级、县级、国界、九段线的shp数据_九段线shp数据
文章浏览阅读797次,点赞16次,收藏19次。二十一世纪我们的社会进入了信息时代,信息管理系统的建立,大大提高了人们信息化水平。传统的管理方式对时间、地点的限制太多,而在线管理系统刚好能满足这些需求,在线管理系统突破了传统管理方式的局限性。于是本文针对这一需求设计并实现了一个基于django高校本科生学习成长记录系统,为了简捷并有效的解决学习各方面的问题。
文章浏览阅读7.7k次。为什么要共享session?我们使用单台Tomcat的时候不会有共享sesssion的疑虑,只要使用Tomcat的默认配置即可,session即可存储在Tomcat上。但是随着业务的扩大,增加Tomcat节点构成Tomcat集群大势所趋,分布式带来了增加更大规模并发请求的优势,但是也随之到来了一个问题,每个Tomcat只存储来访问自己的请求产生的session,如果Tomcat-A已经为客..._redis分布式session共享