swust oj 数据结构后40

  • 博主码风太丑,勿喷。
  • 比较简单的我就没写思路,只贴了代码。
  • hint: <bits/stdc++.h> 是万能头文件,大多oj和编译器都能用,这样就不用写这么多头文件了。
  • 有错误请指出,thanks。
  • 有的题数据输出格式改了,PE的题请在下面评论区留言。不懂的也可以在下面留言,可能会解答。
  • 数据结构前40

[960] 双向链表的操作问题

传送门

描述

建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成,数据类型为整型。)

输入

第一行:双向表的长度;
第二行:链表中的数据元素。

输出

输出双向链表中的数据元素的值。

样例输入

1
2
10
2 4 6 3 5 8 10 21 12 9

样例输出

1
2 3 4 5 6 8 9 10 12 21
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))

typedef struct node
{
int data;
node *pre;
node *next;
} DLinkNode;

void Create (DLinkNode *&Head,int n)
{
int x;
DLinkNode *p1,*p2;
p1=(DLinkNode *)malloc(sizeof(DLinkNode));
Head=p2=p1;
Head->pre=NULL;
Head->next=NULL;

while(n--)
{
cin>>x;p1=Head;
while(p1->next!=NULL&&p1->next->data<=x)
p1=p1->next;

p2=(DLinkNode *)malloc(sizeof(DLinkNode));
p2->data=x;
p2->pre=p1;
p2->next=p1->next;
if(p1->next!=NULL)
p1->next->pre=p2;
p1->next=p2;
}
}

void Put(DLinkNode *Head)
{
DLinkNode *p1=Head->next;
while(p1!=NULL)
{
cout<<p1->data<<" ";
p1=p1->next;
}
}

int main()
{
DLinkNode *Head;

int len;
cin>>len;
Create(Head,len);
Put(Head);
return 0;
}

[980] 输出利用先序遍历创建的二叉树的层次遍历序列

队列写bfs。

传送门

描述

利用先序递归遍历算法创建二叉树并输出该二叉树的层次遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建,否则创建该结点。最后再输出创建完成的二叉树的层次遍历序列。需要注意输入数据序列中的”#”字符和非”#”字符的序列及个数关系,这会最终决定创建的二叉树的形态。

输入

输入为接受键盘输入的由大写英文字符和”#”字符构成的一个字符串(用于创建对应的二叉树)。

输出

每个用例用一行出该用例对应的二叉树的层次遍历序列。

样例输入

1
2
3
4
5
A##
ABC####
AB##C##
ABCD###EF##G##H##
A##B##

样例输出

1
2
3
4
5
A
ABC
ABC
ABHCEDFG
A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define NewNode (TreeNode *) malloc (sizeof(TreeNode))

typedef struct node
{
char data;
node *Lchild,*Rchild;
} TreeNode;

queue <node *> q;

TreeNode * Built()
{
TreeNode *T;
char ch;
cin>>ch;
if(ch=='#')
T=NULL;
else
{
T=NewNode;
T->data=ch;
T->Lchild=Built();
T->Rchild=Built();
}
return T;
}

void Put(TreeNode *Tem)
{
q.push(Tem);
while(!q.empty())
{
cout<<q.front()->data;
if(q.front()->Lchild!=NULL) q.push(q.front()->Lchild);
if(q.front()->Rchild!=NULL) q.push(q.front()->Rchild);
q.pop();
}
}

int main()
{
TreeNode *Root;
Root=Built();
Put(Root);
return 0;
}

[981] 统计利用二叉树存储的森林中树的棵数

找根节点的右儿子,再找右儿子的右儿子,直到没有右儿子为止,这些右儿子的总数就是棵数。

传送门

描述

普通树及其构成的森林均可转换成相应的二叉树,反之亦然。故而可以根据相应的转换方法去统计某一二叉树对应的森林中树的棵数。相应的二叉树可利用先序递归遍历算法创建。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建,否则创建该结点。最后再统计该二叉树对应的森林中树的棵数。需要注意输入数据序列中的”#”字符和非”#”字符的序列及个数关系,这会最终决定创建的二叉树的形态(序列里面允许无效字符但需要正确处理)。

输入

输入为接受键盘输入的由大写英文字符和”#”字符构成的一个字符串(用于创建对应的二叉树)。

输出

输出该用例对应的二叉树表示的森林中树的棵数。

样例输入

1
2
3
4
5
A#B#CD###
ABC####
AB##C##
ABCD###EF##G##H##
A##B##

样例输出

1
2
3
4
5
3
1
2
2
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define NewNode (node*)malloc(sizeof(node))
using namespace std;

struct node
{
char data;
node *Lchild;
node *Rchild;
};

node * Built()
{
node *T;
char ch=getchar();
if(ch=='#')
T=NULL;
else
{
T=NewNode;
T->data=ch;
T->Lchild=Built();
T->Rchild=Built();
}
return T;
}

int Count(node *&root){
return root->Rchild==NULL? 1:1+Count(root->Rchild);
}

int main()
{
node *root=Built();
cout<<Count(root);
return 0;
}


[982] 输出利用二叉树存储的普通树的度

传送门

描述

普通树可转换成相应的二叉树(该二叉树的根结点一定缺少右儿子),反之亦然。故而可以根据相应的转换方法去统计某一二叉树对应的普通树的度。普通树的度为其结点儿子数的最大值。相应的二叉树可利用二叉树的先序递归遍历算法创建。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建,否则创建该结点。最后再统计该二叉树对应的森林中树的棵数。需要注意输入数据序列中的”#”字符的序列及个数关系,这会最终决定创建的二叉树的形态(序列里面允许无效字符但需要正确处理)。

输入

输入为接受键盘输入的由大写英文字符和”#”字符构成的一个字符串(用于创建对应的二叉树)。

输出

若表示的二叉树对应普通树,则该普通树的度;否则输出ERROR。

样例输入

1
2
3
4
5
AB#CD##E###
ABC####
AB##C##
ABCD###EF##G###
A##B##

样例输出

1
2
3
4
5
3
1
ERROR
3
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define NewNode (node*)malloc(sizeof(node))
using namespace std;

int ans=0;

struct node {
char data;
node *Lchild;
node *Rchild;
};

node * Built() {
node *T;
char ch=getchar();
if(ch=='#')
T=NULL;
else {
T=NewNode;
T->data=ch;
T->Lchild=Built();
T->Rchild=Built();
}
return T;
}

//二叉树储存数的时候,每个节点的左儿子依旧表示儿子,而右儿子则变成了兄弟节点

int Count(node *&T) {
if(T==NULL) return 0; //如果这个节点不存在,返回0
ans=max(ans,Count(T->Lchild)); //否则,查看儿子节点中度数最大的,和当前的ans作比较
ans=max(ans,Count(T->Rchild)+1) ;//查看当前节点有几个兄弟,兄弟数+1(自己)就是父节点的度数,和ans作比较
return ans;
}

int main() {

node *root=Built();
if(root->Rchild!=NULL) //如果根节点有兄弟,则说明不止一棵树
cout<<"ERROR";
else
cout<<Count(root);
return 0;
}


[983] 利用二叉树中序及后序遍历确定该二叉树的先序序列

当前树的后续遍历的最后一个元素肯定是根节点。中序遍历中根节点右边是左子树,右边是右子树,递归处理。

传送门

描述

已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及后序遍历结果,要求输出其先序遍历结果。

输入

第一行为中序序列
第二行为后续序列

输出

输出为遍历二叉树得到的先序序列

样例输入

1
2
BFDAEGC
FDBGECA

样例输出

1
ABDFCEG
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define NewNode (node*)malloc(sizeof(node))
using namespace std;

char Zhong[1000],Hou[1000];

void Ac(int Z,int H,int n) { //Z:当前的中序的开头位置 H:当前的后序的开头位置 n:序列长度
if(n<=0) return;

cout<<Hou[H+n-1]; //后续遍历的最后一个元素是根节点 所以先输出
int i=Z;
while(Zhong[i]!=Hou[H+n-1]) i++; //在中序遍历中寻找根节点
//中序遍历中根节点右边是左子树,右边是右子树,递归处理。
Ac(Z,H,i-Z); //递归处理左儿子
Ac(i+1,H+i-Z,n+Z-i-1); //递归处理右儿子
}

int main() {
while(~scanf("%s%s",Zhong,Hou))
Ac(0,0,strlen(Zhong));
return 0;
}

这个博客
建树的话会好理解一点,代码也会长一点。


[984] 利用二叉树中序及先序遍历确定该二叉树的后序序列

当前树的先续遍历的第一个元素肯定是根节点。中序遍历中根节点右边是左子树,右边是右子树,递归处理。

传送门

描述

已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果,要求输出其后序遍历结果。

输入

输入数据占2行,其中第一行表示中序遍历结果,第二行为先序遍历结果。

输出

对测试数据,输出后序遍历结果。

样例输入

1
2
BFDAEGC
ABDFCEG

样例输出

1
FDBGECA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define NewNode (node*)malloc(sizeof(node))
using namespace std;

char Zhong[1000],Xian[1000];

void Ac(int Z,int X,int n) { //Z:当前的中序的开头位置 X:当前的先序的开头位置 n:序列长度
if(n<=0) return;

int i=Z;
while(Zhong[i]!=Xian[X]) i++; //树的先续遍历的第一个元素是根节点 所以找到后最后输出
//序遍历中根节点右边是左子树,右边是右子树,递归处理。
Ac(Z,X+1,i-Z); //递归处理左儿子
Ac(i+1,X+i-Z+1,n+Z-i-1); //递归处理右儿子
cout<<Xian[X]; //输出根节点
}

int main() {
while(~scanf("%s%s",Zhong,Xian))
Ac(0,0,strlen(Zhong));
return 0;
}

这个博客
建树的话会好理解一点,代码也会长一点。


[986] 哈夫曼译码

传送门

描述

通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。(建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写译码函数void ccode(haffnode hafftree[],int n)即可。

输入

根据哈夫曼树编码表,针对字符串做好的编码结果。

输出

对每一行需要解码的串,进行解码,并输出解码后的结果。

样例输入

1
000100011011101110

样例输出

1
aabcc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
const int maxvalue=100;
const int maxbit=100;
const int maxn=100;
#include "iostream"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
using namespace std;
struct haffnode
{
char ch;
int weight;
int flag;
int parent;
int leftchild;
int rightchild;
};
struct code
{
int bit[maxn];
int start;
int weight;
char ch;
};
void haffman(int weight[],char text[],int n,haffnode hafftree[])
{
int j,m1,m2,x1,x2,i;
for(i=0; i< 2*n-1; i++)
{
if(i < n)
{
hafftree[i].weight=weight[i];
hafftree[i].
ch=text[i];
}
else
{
hafftree[i].weight=0;
hafftree[i].ch='#';
}
hafftree[i].parent=0;
hafftree[i].flag=0;
hafftree[i].leftchild=-1;
hafftree[i].rightchild=-1;
}
for(i=0; i< n-1; i++)
{
m1=m2=maxvalue;
x1=x2=0;
for(j=0; j< n+i; j++)
{
if(hafftree[j].weight< m1&&hafftree[j].flag==0)
{
m2=m1;
x2=x1;
m1=hafftree[j].weight;
x1=j;
}
else if(hafftree[j].weight< m2&&hafftree[j].flag==0)
{
m2=hafftree[j].weight;
x2=j;
}
}
hafftree[x1].parent=n+i;
hafftree[x2].parent=n+i;
hafftree[x1].flag=1;
hafftree[x2].flag=1;
hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight;
hafftree[n+i].leftchild=x1;
hafftree[n+i].rightchild=x2;
}
}
void haffmancode(haffnode hafftree[],int n,code haffcode[])
{
code cd;
int i,j;
int child,parent;
for( i=0; i< n; i++)
{
cd.start=n-1;
cd.weight=hafftree[i].weight;
cd.ch=hafftree[i].ch;
child=i;
parent=hafftree[child].parent;
while(parent!=0)
{
if(hafftree[parent].leftchild==child)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
child=parent;
parent=hafftree[child].parent;
}
for(j=cd.start+1; j< n; j++)
haffcode[i].bit[j]=cd.bit[j];
haffcode[i].start=cd.start;
haffcode[i].weight=cd.weight;
haffcode[i].ch=cd.ch;
}
}
void ccode(haffnode hafftree[],int n)
{
int i,j=0,m=2*n-1;
char b[maxn];
memset(b,'\0',sizeof(b));
i=m-1;
scanf("%s",b);
while(b[j]!='\0')
{
if(b[j]=='0')
i=hafftree[i].leftchild;
else
i=hafftree[i].rightchild;
if(hafftree[i].leftchild==-1)
{
printf("%c",hafftree[i].ch);
i=m-1;
}
j++;
}
}
int main( )
{
int n=8;
int weight[]= {5,29,7,8,14,23,3,11};
char text[]= {'a','b','c','d','e','f','g','h'};
haffnode myhafftree[maxvalue];
code myhaffcode[maxvalue];
haffman(weight,text,n,myhafftree);
haffmancode(myhafftree,n,myhaffcode);
ccode(myhafftree,n);
return 0;
}

1


[987] 输出用先序遍历创建的二叉树是否为完全二叉树的判定结果

完全二叉树是依次排列的,我们按层次遍历,找到第一个空节点,如果之前等于总结点,就是,否则不是。

传送门

描述

利用先序递归遍历算法创建二叉树并判断该二叉树是否为完全二叉树。完全二叉树只能是同深度的满二叉树缺少最后一层倒数连续个叶子结点。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建,否则创建该结点。最后判断创建完成的二叉树度是否为完全二叉树。需要注意输入数据序列中的”#”字符和非”#”字符的序列及个数关系,这会最终决定创建的二叉树的形态。

输入

输入为接受键盘输入的由大写英文字符和”#”字符构成的一个字符串(用于创建对应的二叉树)。

输出

对应的二叉树是否为完全二叉树的判断结果。若是输出”Y”,否则输出”N”。

样例输入

1
2
3
4
5
6
A##
ABC####
AB##C##
ABCD###EF##G###
A##B##
ABC##D##EG###

样例输出

1
2
3
4
5
6
Y
N
Y
N
Y
Y
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;

int sum=0,Count=1;
struct node
{
char date;
node *Lchild;
node *Rchild;
};

node *Built()
{
node *T;
char tem=getchar();
if(tem=='#') return T=NULL;
sum++;
T=new node;
T->Lchild=Built();
T->Rchild=Built();
return T;
}

queue <node *> Q;

void Judge()
{
while(!Q.empty())
{
node *tem=Q.front();
if(tem->Lchild==NULL) return;
Count++;
Q.push(tem->Lchild);
if(tem->Rchild==NULL) return;
Count++;
Q.push(tem->Rchild);
Q.pop();
}
}

int main()
{
node *root=Built();
Q.push(root);
Judge();
cout<<(sum==Count? 'Y':'N');
return 0;
}


[1010] 折半查找的实现

二分。

传送门

描述

编写程序实现折半查找算法。

输入

第一行是查找表的长度n
第二行是查找表中的数据元素 ;
第三行是要查找的数据元素的关键字.

输出

查找成功返回位序,不成功返回-1 ,第二行为比较的次数。

样例输入

1
2
3
11
5 13 19 21 37 56 64 75 80 88 92
100

样例输出

1
2
-1
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

int Search(int x,int l,int r,int a[],int &times)
{
times++;
int mid=l+r>>1;
if(x==a[mid]) return mid;
if(l==r) return -1;
return x<a[mid]? Search(x,l,mid,a,times):Search(x,mid+1,r,a,times);
}

int main()
{
int a[1000],x,times=0,n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
cin>>x;

cout<<Search(x,0,n-1,a,times)<<endl;cout<<times;
return 0;
}

[1011] 二叉排序树的实现和查找

博主懒了,sort+二分

传送门

描述

按照给定的关键字集合,建立二叉排序树。在建立的二叉排序树上查找指定的关键字,查找成功,输出找到该关键字比较的次数;查找不成功,输出-1.

输入

关键字个数n;
关键字集合;
要查找的关键字;

输出

查找成功输出比较的次数,否则输出-1。

样例输入

1
2
3
12
25 18 46 2 53 39 32 4 74 67 60 11
74

样例输出

1
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

int Search(int x,int l,int r,int a[],int times) //二分查找
{
int mid=l+r>>1;
if(x==a[mid]) return times; //找到了,返回下标
if(l==r) return -1; //没找到返回-1
return x<a[mid]? Search(x,l,mid,a,times+1):Search(x,mid+1,r,a,times+1); //比中间小在左边找,否则在右边找。
}

int main()
{
int a[1000],x,n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
cin>>x;sort(a,a+n);

cout<<Search(x,0,n-1,a,1);
return 0;
}


[1012] 哈希表(链地址法处理冲突)

往后放就行了。

传送门

描述

采用除留余数法(H(key)=key %n)建立长度为n的哈希表,处理冲突用链地址法。建立链表的时候采用尾插法。

输入

第一行为哈西表的长度m;
第二行为关键字的个数n;
第三行为关键字集合;
第四行为要查找的数据。

输出

如果查找成功,输出该关键字所在哈希表中的地址和比较次数;如果查找不成功,输出-1。

样例输入

1
2
3
4
13
13
16 74 60 43 54 90 46 31 29 88 77 78 79
16

样例输出

1
3,1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;

struct Hnode
{
int data;
Hnode *next;
}*Rear[1000];

struct Hash
{
Hnode *Head[1000];
int len,n;
}L;

void Insert(int x)
{
Hnode *tem= new Hnode;
tem->data=x;
tem->next=NULL;
int ads=x%L.len;
if(L.Head[ads]) //已经有了就往后放
Rear[ads]->next=tem;
else
L.Head[ads]=tem;
Rear[ads]=tem; //更新尾节点地址
}

int Search(int x)
{
int ads=x%L.len,Count=1;
Hnode *tem=L.Head[ads];
if(tem==NULL)
return -1;
while(tem!=NULL&&tem->data!=x)
{
tem=tem->next;
Count++;
}
return tem==NULL? -1:Count;
}

void Ac()
{
int n,x;
cin>>n; L.len=n;
for(int i=0; i<n; i++) L.Head[i]=Rear[i]=NULL;
cin>>n; L.n=n;
while(n--){
cin>>x;
Insert(x);
}
cin>>x;
int ans=Search(x);

if(ans!=-1) cout<<x%L.len<<",";
cout<<ans;
}

int main()
{
Ac();
return 0;
}


[1013] 哈希表(开放定址法处理冲突)

传送门

描述

采用除留余数法(H(key)=key %n)建立长度为n的哈希表,处理冲突用开放定址法的线性探测。

输入

第一行为哈希表的长度n; 第二行为关键字的个数; 第三行为关键字集合; 第三行为要查找的数据。

输出

如果查找成功,输出关键字所哈希表中的地址和比较次数;如果查找不成功,输出-1。

样例输入

1
2
3
4
13
11
16 74 60 43 54 90 46 31 29 88 77
16

样例输出

1
3,1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,-1,sizeof(a))
int main()
{
int a[105];
CRL(a);
int n,m,num,k,cont=0;
cin>>n>>m;
for(int i=0; i<m; i++)
{
cin>>num;
int t=num%n;
while(a[t]!=-1)
t=(t+1)%n;

a[t]=num;
}
cin>>k;
int t=k%n;
for(int i=0; i<n; i++)
{
cont++;
if(a[t]==k)
{
cout<<t<<","<<cont;
return 0;
}
else
t=(t+1)%n;
}
cout<<"-1";
return 0;
}


[1014] 交换排序算法的设计与实现——冒泡排序

祝愿大家都能抽到这题

传送门

描述

编程实现冒泡排序,按照非递减排序,测试数据为整数。

输入

第一行是待排序数据元素的个数;
第二行是待排序的数据元素。

输出

第一行输出第一趟冒泡排序的结果。

样例输入

1
2
10
50 36 41 19 23 4 20 18 12 22

样例输出

1
36 41 19 23 4 20 18 12 22 50
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[1000],n,tem;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];

for(int i=0;i<n-1;i++)
if(a[i]>a[i+1])
swap(a[i],a[i+1]);

for(int i=0;i<n;i++) cout<<a[i]<<' ';
return 0;
}

[1015] 堆排序算法

每次在双亲节点,左儿子,右儿子间选最小的与根节点交换即可。

传送门

描述

编写程序堆排序算法。按照从小到大的顺序进行排序,测试数据为整数。

输入

第一行是待排序数据元素的个数; 第二行是待排序的数据元素。(提示:用小根堆)

输出

一趟堆排序的结果。

样例输入

1
2
10
50 36 41 19 23 4 20 18 12 22

样例输出

1
4 12 20 18 22 41 50 36 19 23
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;

void sift(int R[],int low,int high)
{
int i=low,j=i<<1,tem=R[i]; //i<<1==i*2,位运算快一点
while(j<=high)
{
if(j<high&&R[j]>R[j+1])
++j;
if(tem>R[j]){
R[i]=R[j];
i=j;
j=i<<1;
}
}
R[i]=tem;
}

int main()
{
int R[1000],n;
cin>>n;
for(int i=1; i<=n; ++i)
cin>>R[i];
for(int i=n/2; i>=1; --i)
sift(R,i,n); //建堆
for(int i=1; i<=n; ++i)
cout<<R[i]<<" ";
return 0;
}


[1016] 插入排序算法实现

一趟而已。。。骚起来。

传送门

描述

插入排序算法实现。

输入

第一行是待排序数据元素的个数;
第二行是待排序的数据元素。

输出

一趟直接插入排序算法结果。

样例输入

1
2
10
50 36 41 19 23 4 20 18 12 22

样例输出

1
36 50 41 19 23 4 20 18 12 22
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int main()
{
int R[1000],n;
cin>>n;
for(int i=0; i<n; ++i) cin>>R[i];

if(R[1]<R[0]) swap(R[0],R[1]);

for(int i=0; i<n; ++i) cout<<R[i]<<" ";
return 0;
}


[1051] 输出利用先序遍历创建的二叉树中的指定结点的孩子结点

。。。

传送门

描述

利用先序递归遍历算法创建二叉树并输出该二叉树中指定结点的儿子结点。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符”#”时表示该结点不需要创建,否则创建该结点。最后再输出创建完成的二叉树中的指定结点的儿子结点。注意输入数据序列中的”#”字符和非”#”字符的序列及个数关系,这会最终决定创建的二叉树的形态。

输入

输入用例分2行输入,第一行接受键盘输入的由大写英文字符和”#”字符构成的一个字符串(用于创建对应的二叉树),第二行为指定的结点数据。

输出

用一行输出该用例对应的二叉树中指定结点的儿子结点,格式为:L:,R:。若相应儿子不存在则以”#”。

样例输入

1
2
3
4
A##
A
ABC####
B

样例输出

1
2
3
4
A##
A
ABC####
B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
struct node{
char data;
node *Lchild,*Rchild;
};

node *Built(){
node *T;
char tem=getchar();
if(tem=='#') return T=NULL;
T=new node;
T->data=tem;
T->Lchild=Built();
T->Rchild=Built();
return T;
}

void Ac(node *tem,char x)
{
if(tem==NULL) return;
if(tem->data==x) {
cout<<"L:"<<(tem->Lchild? tem->Lchild->data:'#'); //ÅжÏ×óÓÒ¶ù×ÓÊÇ·ñΪULL
cout<<",R:"<<(tem->Rchild? tem->Rchild->data:'#');
}
else{
Ac(tem->Lchild,x);
Ac(tem->Rchild,x);
}
}

int main()
{
node *root=Built();char a,x;
cin>>x;
Ac(root,x);
return 0;
}


[1052] 输出利用先序遍历创建的二叉树中的指定结点的双亲结点

每个节点保存双亲节点。

传送门

描述

利用先序递归遍历算法创建二叉树并输出该二叉树中指定结点的双亲结点。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符“#”时表示该结点不需要创建,否则创建该结点。最后再输出创建完成的二叉树中的指定结点的双亲结点。注意输入数据序列中的“#”字符和非“#”字符的序列及个数关系,这会最终决定创建的二叉树的形态。

输入

输入用例分2行输入,第一行接受键盘输入的由大写英文字符和“#”字符构成的一个字符串(用于创建对应的二叉树),第二行为指定的结点数据。

输出

用一行输出该用例对应的二叉树中指定结点的双亲结点。若相应双亲结点不存在则以“#”代替。

样例输入

1
2
3
4
A##
A
ABC####
B

样例输出

1
2
#
A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
struct node{
char data;
node *Lchild,*Rchild,*parents;
};

node *Built(node *&R){
node *T;
char tem=getchar();
if(tem=='#') return T=NULL;
T=new node;
T->data=tem;
T->parents=R;
T->Lchild=Built(T);
T->Rchild=Built(T);
return T;
}

void Ac(node *tem,char x)
{
if(tem==NULL) return;
if(tem->data==x)
{
node *T=tem;int ans=0;
while(T->Rchild!=NULL){
ans++;
T=T->Rchild;
}
cout<<(tem->parents==NULL? ans:ans+1);
}
else
Ac(tem->Lchild,x);
Ac(tem->Rchild,x);
}

int main()
{
node *root,*tem;
root=Built(root);
root->parents=NULL;
char x;
cin>>x;
Ac(root,x);
return 0;
}


[1053] 输出利用先序遍历创建的二叉树中的指定结点的度

传送门

描述

利用先序递归遍历算法创建二叉树并输出该二叉树中指定结点的度。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符“#”时表示该结点不需要创建,否则创建该结点。最后再输出创建完成的二叉树中的指定结点的度。注意输入数据序列中的字符“#”和非“#”字符的序列及个数关系,这会最终决定创建的二叉树的形态。

输入

输入用例分2行输入,第一行接受键盘输入的由大写英文字符和“#”字符构成的一个字符串(用于创建对应的二叉树),第二行为指定的结点数据。

输出

用一行输出该用例对应的二叉树中指定结点的度。

样例输入

1
2
3
4
A##
A
ABC####
B

样例输出

1
2
0
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
struct node{
char data;
node *Lchild,*Rchild,*parents;
};

node *Built(node *&R){
node *T;
char tem=getchar();
if(tem=='#') return T=NULL;
T=new node;
T->data=tem;
T->parents=R;
T->Lchild=Built(T->Lchild);
T->Rchild=Built(T->Rchild);
return T;
}

int Ac(node *tem,char x)
{
if(tem==NULL) return 0;
if(tem->data==x)
{
node *T=tem->Rchild;int ans=0;
while(T!=NULL){
ans++;
T=T->Rchild;
}
return tem->parents? ans+1:ans;
}
else
Ac(tem->Lchild,x);
Ac(tem->Rchild,x);
}

int main()
{
node *root,*tem;
root=Built(root);
root->parents=NULL;
char x;
cin>>x;
cout<<Ac(root,x);
return 0;
}


[1055] 邻接矩阵到邻接表

传送门

描述

假设无向图G采用邻接矩阵存储,编写一个算法输出邻接表。

输入

第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1),接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,1表示邻接。

输出

输出图G的邻接表。第一行表示顶点0可直接到达的顶点编号。其他行定义相同。

样例输入

1
2
3
4
5
6
5
0 1 0 1 1
1 0 1 1 0
0 1 0 1 1
1 1 1 0 1
1 0 1 1 0

样例输出

1
2
3
4
5
134
023
134
0124
023
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
struct node
{
int date;
node *next;
};
node L[100],*rear[100];

void Insert(node *&t,int k)
{
node *tem=new node;
t->next=tem;
tem->date=k;
tem->next=NULL;
t=tem;
}

void Show(int n)
{
node *p;
for(int i=0; i<n; i++)
{
p=L[i].next;
while(p!=NULL)
{
cout<<p->date;
p=p->next;
}
cout<<endl;
}
}

int main()
{
int n,x;
cin>>n;
for(int i=0; i<n; i++)
{
L[i].date=i;
L[i].next=NULL;
rear[i]=&L[i];
}

for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
cin>>x;
if(x) Insert(rear[i],j);

}

Show(n);
return 0;
}


[1056] 邻接表到邻接矩阵

注意读入数据的方法。

传送门

描述

假设无向图G采用邻接表存储,编写一个算法输出邻接矩阵。

输入

第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1)。第二行表示顶点0可直接到达的顶点编号,其他行定义相同。

输出

输出图G的邻接矩阵。整数矩阵大小为n*n,表示图的邻接关系。数字为0表示不邻接,1表示邻接。

样例输入

1
2
3
4
5
6
5
1 3 4
0 2 3
1 3 4
0 1 2 4
0 2 3

样例输出

1
2
3
4
5
01011
10110
01011
11101
10110
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int main()
{
int Map[100][100]={0},n,x;char t;
cin>>n;
for(int i=0;i<n;++i)
{
do{
scanf("%d%c",&x,&t);
Map[i][x]=1;
}while(t==' ');
}

for(int i=0;i<n;++i){
for(int j=0;j<n;++j)
printf("%d",Map[i][j]);
printf("\n");
}
return 0;
}


[1057] 有向图的出度计算

头结点保存结点数。

传送门

描述

假设有向图G采用邻接表存储,设计算法求出图G中每个顶点的出度。

输入

第一行为图中顶点的个数n 第二行为图的边的条数e 第三行为依附于一条边的两个顶点的数据信息。

输出

图G中每个顶点的出度。第一行表示顶点0的出度,其他行定义相同。

样例输入

1
2
3
4
5
6
7
8
5
6
0 1
0 3
1 2
1 3
4 0
4 3

样例输出

1
2
3
4
5
2
2
0
0
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;

struct node {
int data;
node *next;
};

node L[100],*Rear[100];

void Insert(int a,int b){
node *tem=new node;
Rear[a]->next=tem;
tem->data=b;
tem->next=NULL;
Rear[a]=tem;
L[a].data++;
}

int main()
{
int n,edg,a,b;
cin>>n>>edg;
for(int i=0;i<n;i++){
L[i].data=0; //头结点保存结点数
L[i].next=NULL;
Rear[i]=&L[i];
}
while(edg--)
{
cin>>a>>b;
Insert(a,b);
}
for(int i=0;i<n;i++) cout<<L[i].data<<endl;//输出结点数
return 0;
}


[1058] 无向图顶点度的计算

传送门

描述

假设无向图G采用邻接矩阵存储,设计算法求出图G中每个顶点的度。

输入

第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1)。接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,1表示邻接。

输出

图G中每个顶点的度。第一行表示顶点0的度,其他行定义相同。

样例输入

1
2
3
4
5
6
5
0 1 0 1 1
1 0 1 1 0
0 1 0 1 1
1 1 1 0 1
1 0 1 1 0

样例输出

1
2
3
4
5
3
3
3
4
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int main()
{
int sum=0,n,x;
cin>>n;
for(int i=0;i<n;i++){
sum=0;
for(int j=0;j<n;j++){
cin>>x;
if(x) sum++;
}
cout<<sum<<endl;
}
return 0;
}

[1059] 有向图的最大出度计算

传送门

描述

假设有向图G采用邻接表存储,求出图G中出度最大的顶点,并输出顶点的编号(有多个结果的都要输出)。(顶点的数据元素为整型数据。)

输入

第一行为图中顶点的个数n; 第二行为图的边的条数e; 第三行为依附于一条边的两个顶点信息。邻接。

输出

图G中出度的最大值以及顶点编号。第一行表示最大出度,第二行表示所有顶点的编号。

样例输入

1
2
3
4
5
6
7
8
5
6
0 1
0 3
1 2
1 3
4 0
4 3

样例输出

1
2
2
014
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;

struct node {
int data;
node *next;
};

node L[100],*Rear[100];

void Insert(int a,int b){
node *tem=new node;
Rear[a]->next=tem;
tem->data=b;
tem->next=NULL;
Rear[a]=tem;
L[a].data++;
}

int main()
{
int n,edg,a,b,Max=0,Mi=0;
cin>>n>>edg;
for(int i=0;i<n;i++){
L[i].data=0; //头结点保存结点数
L[i].next=NULL;
Rear[i]=&L[i];
}
while(edg--)
{
cin>>a>>b;
Insert(a,b);
}

for(int i=0;i<n;i++) Max=max(Max,L[i].data);
cout<<Max<<endl;
for(int i=0;i<n;i++)
if(L[i].data==Max)
cout<<i;
return 0;
}


[1060] 无向图的最大度计算

传送门

描述

假设无向图G采用邻接矩阵存储,求出图G最大度值并输出顶点的编号(有多个结果的都要输出)。

输入

第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1)。接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,1表示邻接。

输出

图G中度的最大值以及顶点编号。第一行表示最大度值,第二行表示所有顶点的编号。

样例输入

1
2
3
4
5
6
5 
0 1 0 1 1
1 0 1 1 1
0 1 0 1 1
1 1 1 0 1
1 1 1 1 0

样例输出

1
2
4
134
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int main()
{
int sum[100]={0},n,x,Max=0;
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>x;
if(x) sum[i]++;
}
Max=max(sum[i],Max);
}
cout<<Max<<endl;
for(int i=0;i<n;i++)
if(sum[i]==Max) cout<<i;
return 0;

[1061] 有向图的k出度计算

传送门

描述

假设有向图G采用邻接矩阵存储,计算图G中出度为k的顶点数量,并输出顶点的编号。

输入

第一行第一个整数n表示顶点的个数(顶点编号为0到n-1),第二个数表示出度k,接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,1表示不邻接。

输出

图G中出度为k顶点数量以及顶点编号。第一行表示出度为k顶点数量,第二行表示顶点的编号。

样例输入

1
2
3
4
5
6
5 2
0 1 0 1 0
0 0 1 1 0
0 0 0 0 0
0 0 0 0 0
1 0 0 1 0

样例输出

1
2
3
014
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main()
{
int sum[100]={0},n,x,Sum=0,k;
cin>>n>>k;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>x;
if(x) sum[i]++;
}
if(sum[i]==k) Sum++;
}
cout<<Sum<<endl;
for(int i=0;i<n;i++)
if(sum[i]==k) cout<<i;
return 0;
}

[1062] 有向图的边存在判断

祝愿大家也能抽到这道题。

传送门

描述

假设有向图G采用邻接矩阵存储,判断图G中是否存在边。

输入

第一行第一个整数n表示顶点的个数(顶点编号为0到n-1),第二行表示顶点i和j,接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,1表示不邻接。

输出

yes(存在),no(不存在)。

样例输入

1
2
3
4
5
6
7
5
0 2
0 1 0 1 0
0 0 1 1 0
0 0 0 0 0
0 0 0 0 0
1 0 0 1 0

样例输出

1
no
1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int main()
{
int Map[100][100],n,a,b;
cin>>n>>a>>b;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>Map[i][j];
cout<<(Map[a][b]? "yes":"no");
return 0;
}

[1063] 带权有向图计算

传送门

描述

假设带权有向图G采用邻接矩阵存储,计算图的最大权值、最小权值以及对应的有向边。

输入

第一行第一个整数n表示顶点的个数(顶点编号为0到n-1),第二行表示顶点i和j,接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为大于0表示邻接值,-1表示不邻接,对角线为0。

输出

第一行为最大权值,第二行为有向边。第三行为最小权值,第四行为有向边。

样例输入

1
2
3
4
5
6
5 
0 5 -1 23 -1
-1 0 31 56 -1
-1 -1 0 -1 -1
-1 -1 -1 0 -1
56 -1 -1 19 0

样例输出

1
2
3
4
6
<1 3><4 0>
5
<0 1>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
int main()
{
int Map[100][100],n,Max=0,Min=0xfffffff;
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
cin>>Map[i][j];
if(Map[i][j]>0){
Max=max(Max,Map[i][j]);
Min=min(Min,Map[i][j]);
}
}
cout<<Max<<endl;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(Map[i][j]==Max) printf("<%d %d>",i,j);

cout<<endl<<Min<<endl;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(Map[i][j]==Min) printf("<%d %d>",i,j);
return 0;
}

[1064] 带权无向图存储判定

传送门

描述

假设无向图G采用邻接矩阵存储,判断输入数据格式是否正确(即是否为对称矩阵)。

输入

第一行第一个整数n表示顶点的个数(顶点编号为0到n-1),接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为大于0表示邻接值,-1表示不邻接,对角线为0。

输出

yes(正确),no(错误)。

样例输入

1
2
3
4
5
6
5
0 6 -1 22 1
6 0 1 1 -1
-1 1 0 1 1
22 1 1 0 9
1 -1 1 9 0

样例输出

1
yes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main()
{
int Map[100][100],n,Flag=0;
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
cin>>Map[i][j];
if(i>j&&Map[i][j]!=Map[j][i])
Flag=1;
}
cout<<(Flag? "no":"yes");
return 0;
}

[1065] 无向图的连通分量计算

  • 用并查集做。
  • 把一个联通分支的点当做一个集合,两个点有边就合并他们所在的集合,最后看有几个集合,就是有几个联通分支。
  • 这道题后台给的好像都是联通图,所以直接输出1也可以。太水了

传送门

描述

假设无向图G采用邻接矩阵存储,编写一个算法求连通分量的个数。

输入

第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1),接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,1表示不邻接。

输出

连通分量的个数。

样例输入

1
2
3
4
5
6
5
0 1 0 1 1
1 0 1 1 0
0 1 0 1 1
1 1 1 0 1
1 0 1 1 0

样例输出

1
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;

int Fa[1000];

int Find(int x) //找x所在的集合代表
{
return Fa[x]==x? x:Fa[x]=Find(Fa[x]);
}

void Union(int a,int b){ //合并a,b所在的集合
int fa=Find(a);
int fb=Find(b);
if(fa!=fb)
Fa[b]=fa;
}

int main()
{
int n,x,ans=0;
cin>>n;

for(int i=0;i<n;i++) Fa[i]=i;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
cin>>x;
if(x) Union(i,j);
}
for(int i=0;i<n;i++) if(Fa[i]==i)ans++;
cout<<ans;
}


[1067] 有向图的邻接表存储强连通判断

传送门

描述

假设有向图G采用邻接表存储,设计一个算法,判断图G是否是强连通图。若是则返回yes;否则返回no。(图中顶点信息为整型数据。)

输入

第一行为图中顶点的个数n;
第二行为图的边的条数e;
接下来e行,每行是一条边依附的两个顶点信息。

输出

强连通图输出yes,否则输出no.

样例输入

1
2
3
4
5
6
7
8
9
5
7
0 1
1 2
1 3
2 3
3 0
3 4
4 0

样例输出

1
yes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int main()
{
int Map[100][100]={0},n,m,Flag=0,a,b;
cin>>n>>m;
while(m--){
cin>>a>>b;
Map[a][b]=1;
}

for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++){
if(Map[j][i]&&Map[i][k])
Map[j][k]=1;
}

for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
if(Map[i][j]!=Map[j][i]) Flag=1;
cout<<(Flag? "no":"yes");
return 0;
}

[1068] 图的按录入顺序深度优先搜索

普通dfs,注意标记一下用过的点就行了。

传送门

描述

图的深度优先搜索类似于树的先根遍历,即从某个结点开始,先访问该结点,然后深度访问该结点的第一棵子树,依次为第二顶子树。如此进行下去,直到所有的结点都访问为止。在该题中,假定所有的结点以“A”至“Z”中的若干字符表示,且要求结点的访问顺序根据录入的顺序进行访问。如果结点录入的顺序为HUEAK,从H开始进行深度优先搜索,则可能的搜索结果为:H->A->K->U>E.

输入

第一行为一个整数n,表示顶点的个数,第二行为n个大写字母构成的字符串,表示顶点,接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,否则为相应的边的长度。最后一行为一个字符,表示要求进行深度优先搜索的起始顶点。

输出

用一行输出深度优先搜索结果,起始点为给定的顶点。

样例输入

1
2
3
4
5
6
7
8
5
HUEAK
0 0 2 3 0
0 0 0 7 4
2 0 0 0 0
3 7 0 0 1
0 4 0 1 0
H

样例输出

1
HEAUK
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;

char Node[1000];
int Mark[1000]={0},Map[1000][1000],n;

void dfs(int x){
cout<<Node[x];
for(int i=0;i<n;i++){
if(Map[x][i]&&!Mark[i]){
Mark[i]=1;
dfs(i);
}
}
}

int main()
{
char S;
cin>>n;
scanf("%s",Node);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>Map[i][j];
cin>>S;
int i=0;
while(Node[i]!=S)i++;
Mark[i]=1;
dfs(i);
return 0;
}


[1069] 图的按录入顺序广度优先搜索

用队列写bfs。

传送门

描述

图的广度优先搜索类似于树的按层次遍历,即从某个结点开始,先访问该结点,然后访问该结点的所有邻接点,再依次访问各邻接点的邻接点。如此进行下去,直到所有的结点都访问为止。在该题中,假定所有的结点以“A”—“Z”中的若干字符表示,且要求结点的访问顺序根据录入的顺序进行访问。如果结点录入的顺序为HUEAK,要求从H开始进行广度优先搜索,则可能的搜索结果为:H->E->A->U->K

输入

第一行为一个整数n,表示顶点的个数,第二行为n个大写字母构成的字符串,表示顶点,接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,否则为相应的边的长度。最后一行为一个字符,表示要求进行广度优先搜索的起始顶点。

输出

用一行输出广度优先搜索结果,起始点为给定的顶点。

样例输入

1
2
3
4
5
6
7
8
5
HUEAK
0 0 2 3 0
0 0 0 7 4
2 0 0 0 0
3 7 0 0 1
0 4 0 1 0
H

样例输出

1
HEAUK
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;

char Node[1000];
int Mark[1000]={0},Map[1000][1000],n;
queue<int> S;

void bfs(int x){
S.push(x);
while(!S.empty()){
int tem=S.front();
for(int i=0;i<n;i++){
if(!Mark[i]&&Map[tem][i]){
S.push(i);
Mark[i]=1;
}
}
cout<<Node[tem]; S.pop();
}
}

int main()
{
char s;
cin>>n;
scanf("%s",Node);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>Map[i][j];
cin>>s;
int i=0;
while(Node[i]!=s)i++;
Mark[i]=1;
bfs(i);
return 0;
}


[1070] 邻接矩阵存储简单路径

dfs,注意标记回溯。

传送门

描述

假设无向图G采用邻接矩阵存储,设计一个算法,输出图G中从顶点u到v的所有简单路径。

输入

简单路径是指路径上的顶点不重复。第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1),第二行表示顶点u和v的编号,接下来是为一个n*n大小的矩阵,表示图的邻接关系。数字为0表示不邻接,1表示不邻接。

输出

输出图G中从顶点u到v的所有简单路径。

样例输入

1
2
3
4
5
6
7
5
0 3
0 1 0 1 1
1 0 1 1 0
0 1 0 1 1
1 1 1 0 1
1 0 1 1 0

样例输出

1
2
3
4
5
6
7
0123
01243
013
03
04213
0423
043
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;

int n,way[1005],Flag[1005],star,end; bool Map[1005][1005];

void dfs(int node,int fill){
if(node==end){
way[fill]=end;
for(int i=0;i<=fill;i++)
printf("%d",way[i]);
printf("\n");
return;
}

for(int j=0;j<n;j++){
if(Map[node][j]&&!Flag[j]){
way[fill]=node;
Flag[node]=1;
dfs(j,fill+1);
Flag[node]=0;
}
}
return;
}

int main()
{
cin>>n>>star>>end;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>Map[i][j];
dfs(star,0);
return 0;
}

[1071] 有向图的邻接矩阵存储顶点删除

传送门

描述

假设有向图G采用邻接矩阵存储,要求删除某一个顶点i(包括与其相关连的边)。

输入

第一行第一个整数n表示顶点的个数(顶点编号为0到n-1),第二个数表示被删除的顶点编号,接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,1表示邻接。

输出

新的邻接矩阵,第一行表示顶点的个数;
第二行是剩余的结点编号;
接下来是为一个(n-1)*(n-1)大小的整数矩阵。

样例输入

1
2
3
4
5
6
5 2
0 1 0 1 0
0 0 1 1 0
0 0 0 0 0
0 0 0 0 0
1 0 0 1 0

样例输出

1
2
3
4
5
6
4
0134
0110
0010
0000
1010
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,a,x;
cin>>n>>a;cout<<n-1<<endl;
for(int i=0;i<n;i++)
if(i!=a) cout<<i;cout<<endl;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>x;
if(i!=a&&j!=a) cout<<x;
}
if(i!=a)cout<<endl;
}
return 0;
}

[1072] 有向图的邻接矩阵存储根计算

暴力出奇迹啊,floyd变形,简单易懂,详见代码。

传送门

描述

若有向图中存在一个顶点v,从v可以通过路径到达图中其他所有顶点,那么称v为该有向图的根。假设图G采用邻接矩阵存储,求有向图的所有根。

输入

第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1),接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。

输出

有向图的所有根。

样例输入

1
2
3
4
5
6
5
0 1 0 0 0
0 0 1 1 0
0 0 0 1 0
1 0 0 0 1
1 0 0 0 0

样例输出

1
01234
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int main()
{
int Map[100][100]={0},n,m,Flag=0,a,b;
cin>>n;

for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>Map[i][j];

for(int i=0;i<n;i++) //floyd算法变形
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
if(Map[j][i]&&Map[i][k]) //如果j->i,i->k那么 j->k。
Map[j][k]=1;


for(int i=0;i<n;i++){
int sum=0;
for(int j=0;j<n;j++)
if(Map[i][j]&&i!=j) sum++;
if(sum==n-1)cout<<i;
}
return 0;
}

[1075] 求最小生成树(Prim算法)

书上有详细解释,这里就不多赘述。

传送门

描述

求出给定无向带权图的最小生成树。图的定点为字符型,权值为不超过100的整形。在提示中已经给出了部分代码,你只需要完善Prim算法即可。

输入

第一行为图的顶点个数n第二行为图的边的条数e接着e行为依附于一条边的两个顶点和边上的权值

输出

最小生成树中的边。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
6
10
ABCDEF
A B 6
A C 1
A D 5
B C 5
C D 5
B E 3
E C 6
C F 4
F D 2
E F 6

样例输出

1
(A,C)(C,F)(F,D)(C,B)(B,E)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<stdio.h>
using namespace std;
#define INF 0xfffffff
typedef struct{
int n;
int e;
char data[500];
int edge[500][500];
} Graph;
typedef struct{
int index;
int cost;
} mincost;
typedef struct{
int x;
int y;
int weight;
} EDGE;

typedef struct{
int index;
int flag;
} F;
void create(Graph &G,int n,int e){
int i,j,k,w;
char a,b;
for(i=0; i< n; i++)
cin>>G.data[i];
for(i=0; i< n; i++)
for(j=0; j< n; j++)
{
if(i==j)
G.edge[i][j]=0;
else
G.edge[i][j]=100;
}
for(k=0; k< e; k++){
cin>>a;
cin>>b;
cin>>w;
for(i=0; i< n; i++)
if(G.data[i]==a)
break;
for(j=0; j< n; j++)
if(G.data[j]==b)
break;
G.edge[i][j]=w;
G.edge[j][i]=w;
}
G.n=n;
G.e=e;
}
void Prim(Graph &G,int v,int n){
int lowcost[n],Min,closest[n],k;
for(int i=0;i<G.n;i++){
lowcost[i]=G.edge[v][i];
closest[i]=v;
}

for(int i=1;i<G.n;i++){
Min=INF;
for(int j=0;j<G.n;j++)
if(lowcost[j]&&lowcost[j]<Min){
Min=lowcost[j];
k=j;
}
printf("(%c,%c)",G.data[closest[k]],G.data[k]);
lowcost[k]=0;
for(int j=0;j<G.n;j++)
if(lowcost[j]&&G.edge[k][j]<lowcost[j]){
lowcost[j]=G.edge[k][j];
closest[j]=k;
}
}
}
int main(){
Graph my;
int n,e;
cin>>n>>e;
create(my,n,e);
Prim(my,0,n);
return 0;
}

[1076] 判断给定有向图是否存在回路

还是floyd变形,暴力出奇迹。

传送门

描述

判断给定有向图是否存在回路。

输入

第一行为图中顶点的个数n; 第二行为途中弧度条数e;
第二行为顶点信息;接着e行为e条弧依附的两个顶点。

输出

该图是否存在回路,是输出yes;,不是输出no。

样例输入

1
2
3
4
5
6
7
4
4
A B C D
A B
A C
B D
C D

样例输出

1
no
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
int main()
{
map<char,int> M;
int Map[100][100]={0},n,e,Flag=0;char tem,a,b;
cin>>n>>e;
for(int i=0;i<n;i++){
cin>>tem;
M.insert(make_pair(tem,i));
}

while(e--){
cin>>a>>b;
Map[M[a]][M[b]]=1;
}

for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
if(Map[j][i]&&Map[i][k]) //如果j->i,i>k
Map[j][k]=1; //那么就可以j->k


for(int i=0;i<n;i++)
if(Map[i][i]) Flag=1;

cout<<(Flag? "yes":"no");
return 0;
}


[1077] 平衡二叉树的判定

找有没有哪个树的左右儿子生成的子树深度之差大于1。

传送门

描述

编写程序判断给定的二叉树是否是平衡二叉树。

输入

二叉树的先序序列。

输出

如果是平衡二叉树,输出yes!,否者输出no!

样例输入

1
AB##C##

样例输出

1
yes!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
int Flag=0;
typedef struct node{
char data;
node *Lchild,*Rchild;
} TreeNode;

TreeNode * Built(){
TreeNode *T;
char ch;
cin>>ch;
if(ch=='#')
T=NULL;
else{
T=new node;
T->data=ch;
T->Lchild=Built();
T->Rchild=Built();
}
return T;
}

int Deep(TreeNode *&Tem){
if(Tem==NULL) return 0;
int dl=Deep(Tem->Lchild);
int dr=Deep(Tem->Rchild);
if(abs(dl-dr)>1) Flag=1;
return 1+max(dl,dr);
}

int main(){
TreeNode *Root;
Root=Built();
Deep(Root);
cout<<(Flag? "no!":"yes!");
return 0;
}

[1098] 堆的判断

找是否存在一个节点的值小于它双亲结点的值。

传送门

描述

编写程序判断以下给出的整数序列是否为最小堆。

输入

第一行是元素的个数n;
第二行是n个整数序列。

输出

如果是小根堆,输出Yes,否者输出No。

样例输入

1
2
10
100 86 48 73 35 39 42 57 66 21

样例输出

1
No
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

int main(){
int n,a[100],Flag=0;

cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];

for(int i=1;i<=n/2;i++)
if(i*2<n&&a[i*2]<a[i]){
Flag=1;
break;
}

cout<<(Flag? "No":"Yes");
return 0;
}

[1099] 希尔排序算法实现

只要一趟,滑稽.jpg

传送门

描述

编程实现希尔排序算法,按照非递减排序,测试数据为整数。

输入

第一行是待排序数据元素的个数n;
第二行是待排序的数据元素。

输出

一趟希尔排序后的结果。

样例输入

1
2
10
50 36 41 19 23 4 20 18 12 22

样例输出

1
4 20 18 12 22 50 36 41 19 23
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int a[1000],n;

int main() {
cin>>n;

for(int i=0; i<n; i++) cin>>a[i];

int i=0,d=n/2; //一趟,所以增量为n/2
while(i<d){
if(a[i]>a[i+d]) //a[i]和a[i+d]为一组,前大于后就换
swap(a[i],a[i+d]);
i++;
}

for(int i=0; i<n; i++) cout<<a[i]<<" ";
return 0;
}


[1105] 交换二叉树的孩子结点

递归交换即可。

传送门

描述

编程程序实现将二叉树中所有结点的左右孩子互换。

输入

二叉树的先序序列(输入先序序列建立二叉树)。

输出

第一行为交换后的二叉树的中序序列
第二行为交换后的二叉树的先序序列

样例输入

1
ABD###C###

样例输出

1
2
CABD
ACBD
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define NewNode (TreeNode *) malloc (sizeof(TreeNode))

typedef struct node
{
char data;
node *Lchild,*Rchild;
} TreeNode;

TreeNode * Built()
{
TreeNode *T;
char ch;
cin>>ch;
if(ch=='#')
T=NULL;
else
{
T=NewNode;
T->data=ch;
T->Lchild=Built();
T->Rchild=Built();
}
return T;
}

void Change(TreeNode *&Tem)
{
if(Tem==NULL) return;
swap(Tem->Lchild,Tem->Rchild);
Change(Tem->Lchild);
Change(Tem->Rchild);
}

void Put1(TreeNode *&Tem)
{
if(Tem==NULL) return;
Put1(Tem->Lchild);
cout<<Tem->data;
Put1(Tem->Rchild);
}

void Put2(TreeNode *&Tem)
{
if(Tem==NULL) return;
cout<<Tem->data;
Put2(Tem->Lchild);
Put2(Tem->Rchild);
}

int main()
{
TreeNode *Root;
Root=Built();
Change(Root);
Put1(Root);cout<<endl;
Put2(Root);
return 0;
}

-------------本文结束 感谢您的阅读-------------

本文标题:swust oj 数据结构后40

文章作者:Armin

发布时间:2018年06月08日 - 22:06

最后更新:2019年05月20日 - 13:05

原始链接:http://x-armin.com/swustoj-数据结构后40/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

小礼物走一波