技术标签: 数据结构
由于本人水平有限,整理的代码若有错漏欢迎指出
```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;
}
文章浏览阅读304次。此博客主要记录在学习黑马程序员2023版JavaWeb开发课程的一些笔记,方便总结以及复习。_后端异步前端怎么处理
文章浏览阅读1w次。文章目录数值类型整型(int)long(长整型)浮点数复数不同进制表示数值类型转换数据类型信息获取math 模块、cmath 模块python数学函数abs(x)ceil()cmp()exp()fabs()floor()log()log10()max()min()modf()pow()round()sqrt()python随机数函数choice()randrange()random()seed()..._python[80., 20., 1000, 200]
文章浏览阅读876次,点赞23次,收藏21次。halcon 轮廓线处理 关键算子_halcon中的轮廓线 导数
文章浏览阅读544次。HMI产品是L4车辆的人机交互程序,为高速运营、港口单车、测试路测等提供状态可视化、任务交互、自动驾驶行车控制、编队控制功能。_自动驾驶hmi用什么开发
文章浏览阅读4w次,点赞13次,收藏120次。Matlab根据坐标点进行绘制散点图并拟合成图像可以使用cftool函数,下面以二维数据拟合进行举例:(1)首先输入数据点x=[0.20,2,4.01,5.99,8.08,9.98,11.96,14.00,15.99,18.00,19.98,21.98,23.99,25.97,28.01,30.00,32.04,33.99,35.98,37.99,39.99,42.00,43.99,45...._matlab散点图拟合函数
文章浏览阅读6.8k次。javac 用法:javac 其中,可能的选项包括: -g 生成所有调试信息 -g:none 不生成任何调试信息 -g:{lines,vars,source} _命令行运行java参数
文章浏览阅读419次。用户在使用 MySQL 实例时,会遇到空间使用告警甚至超过实例限额被锁定的情况。在 RDS 控制台的实例基本信息中,即会出现如下信息:本文将介绍造成空间使用率过高的常见原因及其相应的解决方法。对于MySQL 5.6版本的实例,升级实例规格和存储空间后即可解锁实例,关于如何升级实例配置,请参见变更配置。•常见原因造成 MySQL 实例空间使用率过高,主要有如下四种原因:Binlog 文件占用高。数据..._阿里云m2实例数超过限制99999
文章浏览阅读1.1w次,点赞5次,收藏13次。1.下载https://github.com/kamranahmedse/jquery-toast-plugin在线预览地址2.导入在页面中引入jquery.toast.css文件,jquery和jquery.toast.js文件。<link type="text/css" rel="stylesheet" href="css/jquery.toast.css">..._jquery.toast.js
文章浏览阅读271次。vue2+vue3
文章浏览阅读940次,点赞12次,收藏19次。本文介绍了四款远程控制电脑的软件,这四款远程控制电脑软件操作方法都很简单,大家可以根据自己的需要选择合适的软件即可。在另一台电脑的Chrome浏览器中登录同一个谷歌账号,打开谷歌远程桌面选择要控制的电脑,再输入PIN码即可远程控制电脑。是一款好用的电脑远程控制软件,用户可以通过网络远程连接到其他计算机,轻松实现远程监控、远程技术支持。在两台电脑上都登录QQ账号,主控端电脑打开要控制的好友聊天窗口,单击右上角的更多按钮。,在管理者的电脑上安装管理端,在员工的电脑上安装员工端,安装好后会自动进行连接和上线。_安企神控制软件
文章浏览阅读1w次,点赞10次,收藏7次。整理 | 郑丽媛出品 | CSDN(ID:CSDNnews)两年前,英特尔在公布新一代 Thunderbolt 4(以下简称雷电 4)接口标准时曾说:“不是所有 USB4 都能和雷电 4 平起平坐。”如今看来,这句话的顺序可能要颠倒一下了:本月初,USB 推广组官宣了 USB4 v2.0,其可通过 USB Type-C 提供高达 80 Gbps(相当于 10GB/s)的数据传输速率——不仅是 U..._usb4+2.0
文章浏览阅读123次。jdk8中文文档jdk17在线文档jdk21在线文档