二叉树的各类遍历转化

1.转化规则:

在二叉树

1.中序+前序,中序+后序,中序+层序可以唯一确定一棵二叉树

2.前序 + 后续 不一定能确定一颗二叉树

2.具体实现

1.根据中序 + 前序 确定后续

#include<vector>
#include<cstdio>
using namespace std;

vector<int> pre;
vector<int> in;
void post(int prel,int inl,int inr){
 if(inl > inr) return ;
 int i = inl;
 while(in[i] != pre[prel] && i <= inr) i++;
 post(prel + 1,inl,i - 1);
 post(prel + (i - inl) + 1,i + 1,inr);
 printf("%d ",in[i]);
}

int main(){
 int a;
 scanf("%d",&a);
 pre.resize(a);
 in.resize(a);
 for(int i = 0;i < a;i++) scanf("%d",&pre[i]);
 for(int i = 0;i < a;i++) scanf("%d",&in[i]);
 post(0,0,a - 1);

}

2.后续 + 中序 确定前序

#include<vector>
#include<cstdio>
using namespace std;
vector<int> post;
vector<int> in;


void pre(int postr,int inl,int inr){
 if(inl > inr) return ;
 int i = inl;
 while(in[i] != post[postr] && i >= inl) i++;
 printf("%d ",in[i]);
 pre(postr-(inr - i) - 1,inl,i - 1);
 pre(postr - 1,i + 1,inr);

}
int main(){
 int a;
 scanf("%d",&a);
 post.resize(a);
 in.resize(a);
 for(int i = 0;i < a;i++) scanf("%d",&post[i]);
 for(int i = 0;i < a;i++) scanf("%d",&in[i]);
 pre(a - 1,0,a - 1);


}

3.前序 + 后续 得到其中一中序,题型来自PAT A1119

#include<vector>
#include<cstdio>
using namespace std;

vector<int> pre;
vector<int> post;
vector<int> in;

int flg = 0;
void intt(int prel,int prer,int postl,int postr){
 if(postr < postl) return;
 int i = prel + 1;
 while(post[postr - 1] != pre[i] && i <= prer) i++;
 if((i - 1) == prel && i <= prer){
 flg = 1;
 }
 intt(prel + 1,i - 1,postl,postl + (i - 2 - prel));//默认为右子树
 in.push_back(post[postr]);
 intt(i,prer,postl + (i - 1 - prel),postr - 1);

}

int main(){
 int a;
 scanf("%d",&a);
 pre.resize(a);
 post.resize(a);
 for(int i = 0;i < a;i++) scanf("%d",&pre[i]);
 for(int i = 0;i < a;i++) scanf("%d",&post[i]);
 intt(0,a - 1,0,a - 1);
 printf("%s\n%d",flg == 1 ? "No":"Yes",in[0]);
 for(int i = 1;i < in.size();i++){
 printf(" %d",in[i]);
 }
 return 0;
}

4.中序+前序,确定层序(PAT A1127)

#include<vector>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

vector<int> in;
vector<int> post;
int level[10000];
int last = 0;
void creatree(int sig,int inl,int inr,int postr){//post + in = level
 while(inl > inr) return;
 int i = inl;
 if(last < sig)
 last = sig;
 level[sig] = post[postr];
 while(in[i] != post[postr] && i <= inr) i++;
 creatree(sig * 2 + 1,inl,i - 1,postr - (inr - i) - 1);
 creatree(sig * 2 + 2,i + 1,inr,postr - 1);
}
int towx(int a){
 int re = 1;
 for(int i = 0;i < a;i++){
 re *= 2;
 }
 return re;
}
int main(){
 int a;
 cin >> a;
 in.resize(a);
 post.resize(a);

fill(level,level + 10000,-1);
 for(int i = 0;i < a;i++) cin >> in[i];
 for(int i = 0;i < a;i++) cin >> post[i];
 creatree(0,0,a - 1,a - 1);

int i = 0;
 int k = 1;//cengshu
 int u = 0;
 while(i <= last){
 if(k % 2 == 0){
 for(int j = 0;j < towx(k - 1);j++){
 if(level[j + i] != -1 && u == a - 1){
 cout <<level[j + i];
 }
 if(level[j + i] != -1 && u != a - 1){
 cout <<level[j + i]<<" ";
 u++;
 }

}
 }
 if(k % 2 == 1){
 for(int j = towx(k - 1) - 1;j >= 0;j--){
 if(level[j + i] != -1 && u == a - 1){
 cout <<level[j + i];
 }
 if(level[j + i] != -1&& u != a - 1){
 cout <<level[j + i]<<" ";
 u++;
 }

}
 }
 i += towx(k - 1);
 k ++;
 }

}

5.层遍历(PAT A1004)

#include<vector>
#include<cstdio>
using namespace std;
const int maxi = 100;
vector<int> v[maxi];
int ans[maxi];

void layer(int i,int s){
 if(v[i].size() == 0)
 ans[s]++;
 for(int j = 0;j < v[i].size();j++)
 layer(v[i][j],s + 1);
}

int main(){
 fill(ans,ans + maxi,-1);
 int a,b,c,d,e;
 int i,j,k;
 scanf("%d %d",&a,&b);
 for(int i = 0;i < b;i++){
 scanf("%d %d",&c,&d);
 for(int j = 0;j < d;j++){
 scanf("%d",&e);
 v.push_back(e);
 }
 }
 // printf("creat tree finished\n");
 //ceng bian li
 if(a == 1){
 printf("1");
 return 0;
 }else{
 layer(1,0);
 printf("0");
 }

 for(i = a;i >= 0;i--){
 if(ans[i] != -1){
 k = i;
 break;
 }
 }
 for(i = 1;i <= k;i++){
 if(ans[i] != -1)
 printf(" %d",ans[i] + 1);
 else
 printf(" 0");
 }
 return 0;
}

 

 

 

1023. Have Fun with Numbers (20)

题目:

https://www.patest.cn/contests/pat-a-practise/1023

大概描述:

求一个大数的二倍数,然后将各位数进行统计,比较

特征词:

大数运算

使用语言:

C++

解题思想:

进行大数运算的套路,string+reverse

题目得分:

20

提交次数:

3

时间

25

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
string str;
string ans;
int main(){
 cin >> str;
 int num = str.length();
 //reverse的用法
 reverse(str.begin(),str.end());
 int i= 0;
 int yuan[10] = {0};
 int jie[10] = {0};
 int k = 0;
 int sign = 0;
 int y = 0;
 for(i = 0;i < num;i++){
 y = str[i] - '0';
 yuan[y] ++;
 k = y * 2 + sign;
 sign = 0;
 if(k >= 10){
 jie[k - 10] ++;
 ans += ('0' + k - 10);
 sign = 1;
 }else{
 jie[k] ++;
 ans += ('0' + k);
 }
 }
 if(sign == 1){
 ans += '1';
 }
 reverse(ans.begin(),ans.end());

 for(i = 0 ;i < 10;i++){
 if(jie[i] != yuan[i]){
 printf("No\n");
 cout << ans;
 return 0;
 }
 }
 printf("Yes\n");
 cout << ans;
 return 0;
}

运行结果

20

 成长

再次使用了reverse的函数,reverse(str.begin(),str.end());

1120. Friend Numbers (20)

题目:

https://www.patest.cn/contests/pat-a-practise/1120

大概描述:

将数字各位累加

特征词:

set

使用语言:

C++

解题思想:

简单的set集的应用

题目得分:

20

提交次数:

1

时间

10

代码

#include<set>
#include<cstdio>
#include<cstring>
using namespace std;
set<int> m;
int main(){

int num;
scanf("%d",&num);
int i ,j= 0;
char n[5];
int k = 0;
int y = 0;
for(i = 0;i < num;i++){
 scanf("%s",&n);
 k = strlen(n);
 y = 0;
 for(j = 0;j < k;j++){
 y += n[j] - '0';
 }
 m.insert(y);
}
y = m.size();
printf("%d\n",y);
j = 0;
for(set <int> ::iterator it = m.begin();it != m.end();it++){
 printf("%d",*it);
 if(++j < y){
 printf(" ");
 }
}
}

运行结果

25

 成长

 

1130. Infix Expression (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1130

大概描述:

将一棵语法树,进行展开

特征词:

dfs  中序遍历

使用语言:

C++

解题思想:

先对树进行中序遍历,然后再加括号,需要注意加括号时要进行先前条件的判断,不能是根节点,不能是叶子节点

题目得分:

25

提交次数:

2

时间

inf

代码

#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<cstring>
const int MAXI = 30;
using namespace std;
string ans;
struct p{
 string a;
 int left;
 int right;
};
vector<struct p> m;

//对于一个已知结构的树进行中序遍历
//直接用dfs进行中序遍历

//前序
void qiand(int t){
 //printf("t = %d",t);
 if(t != -1){
 cout << m[t].a;
 }
 if(m[t].left != -1){
 qiand(m[t].left);
 }
 if(m[t].right != -1){
 qiand(m[t].right);
 }

}
//h后序
void houd(int t){
 if(m[t].left != -1){
 houd(m[t].left);
 }
 if(m[t].right != -1){
 houd(m[t].right);
 }
 cout << m[t].a;
}
//中序
int mm;
void zhongd(int t){
 if( t != mm&& (m[t].left != -1||m[t].right != -1))
 cout << "(";
 if(m[t].left != -1){

 zhongd(m[t].left);
 }
 cout << m[t].a;
 if(m[t].right != -1){

 zhongd(m[t].right);
 }
if( t != mm&& (m[t].left != -1||m[t].right != -1))
 cout << ")";
}
//进行序的遍历时,要注意的就是你先要处理的是那一部分,你要明白大体的思路按思路写
int sign[MAXI];
int main(){
 memset(sign,-1,sizeof(sign));
 int m1 = 0;
 scanf("%d",&m1);
 int i = 0;
 struct p pp;
 string s;
 int b,c;
 m.push_back(pp);
 for(i = 0;i < m1;i++){
 cin >>s >>b>>c;
 pp.a = s;
 if(b != -1 ){
 sign[b] = 1;
 }
 if(c != -1){
 sign = 1;
 }
 pp.left = b;
 pp.right = c;
 m.push_back(pp);
 }//这种结构形式更加有方便一些
 //printf("read finished\n");
 //接下来对建好的树进行遍历,首先确定头节点
 int to = 0;
 for(i = 1;i <= m1;i++){
 if(sign[i] != 1){
 to = i;
 break;
 }
 }
 mm = to;
 // printf("to%d\n",to);
 //qiand(to );
 //printf("\n");
 //houd(to);
 //printf("\n");
 zhongd(to);
}

运行结果

25

 成长

这一题让我哭了

真的

感觉一辈子都不会做的题目,规则那么复杂,都看不懂,从很久开始就做的,做了很久很久,还是什么都不懂,感觉一辈子都是跟在别人后面的跟屁虫。那么久那么久。

可终究还是做出来了,用的是我自己的方法。突然能流下眼泪。

刚刚开始题目看不懂什么鬼,查阅资料,又是乱七八糟的,后来就想我自己就直接对它进行中遍历,又忘了中序遍历如何写,只好从前序,后序,中序都写了一遍,等写好后就试着加“(”,“)”,慢慢地有了点感觉,终于终于,修改了几遍后,加对了,希望明天如果在考场有些题目太复杂,可以先写一些简单的,或许会改的很麻烦,但是这也是一个可以尝试的好思路。

加油,fighting!!!

 

1103. Integer Factorization (30)

题目:

https://www.patest.cn/contests/pat-a-practise/1103

大概描述:

将一个展开成k项,每一项的值都是某个数的p次方

特征词:

dfs

使用语言:

C++

解题思想:

深度优先遍历,每一层的寻找合适的数值,层层筛选

题目得分:

25

提交次数:

2

时间

120分钟

代码

#include<cstdio>
#include<vector>

using namespace std;

vector<int> m;//用于存储指数值
vector<int> mm;//用于存储条件
vector<int> limm;//每个最大e存储的临时数
vector<int> zmm;//最终结果
int n,k,p,indx,limax,zmax;
int pow1(int a,int b){
 int m = 1 ,i= 0;
 for(i = 0;i < b;i++){
 m *= a;
 }
 return m;
}
void init(){
 int j = 0;
 indx = 1;
 while(j < n){
 j = pow1(indx,p);
 indx ++;
 }
}

//找出最大为e,所剩下的次数,需要实现的值,是的最合适列表
void dsf(int e,int ci,int num){
 //printf("e = %d ci = %d num = %d",e,ci,num);
 int i= 0;
 //printf("现在临时表为:\n");
 int y = mm.size();
 for(i = 0;i < y;i++){
 // printf("%d ",mm[i]);
 }
// printf("\n");
 if(ci == 0 && num != 0){
 return ;
 }
 if(num <= 0 && ci != 0){
 return;
 }
 if(num == 0&&ci == 0){
 // printf("OOOOOOOOOOOOk\n");
 int sun = 0;
 for(i = 0;i < mm.size();i ++){
 sun += mm[i];
 }
 if(sun > limax){
 // printf("OOOOOOOOOOOOk\n");
 limax = sun;
 limm.clear();
 for(i = 0;i < mm.size();i++){
 limm.push_back(mm[i]);
 }
 }
 return;
 }
 int uu = pow1(e,p);
 // printf("ppppppppppppppowowowowow%d\n",pow1(e,p));
// printf("uuuuuuuuuuuuuuuuuuuuuu%d",uu);
 if(num - uu >= 0){
 // printf("装前我先瞧一瞧 e = %d,num =%d uu =%d\n",e,num,uu);
 mm.push_back(e);
 int j = 0;
 for(j = e ;j >= 1;j--){

 dsf(j,ci - 1,num - uu);
 }
 if(j == 0){
 mm.pop_back();
 }
 }
}

int main(){
 scanf("%d %d %d",&n,&k,&p);
 //printf("OOOOOOOOOk\n");
 init();//完成指数表的建立
 //printf("OOOOOOkk\n");
 int zs = 0;
 int u = 0;
 int i = 0;
 while(zs < n / k){
 u ++;
 zs = pow1(u,p);
 }
// printf("最小的头u = %d\n",u);
 zmax = -1;
 while(indx >= u){
 limax = -1;
 // printf("即将降入头为%d的深度遍历\n",indx);
 limm.clear();
 mm.clear();
 dsf(indx --,k,n);
 //printf("个头最强组合\n");
 int y = limm.size();
 for(i = 0;i < y;i++){
 //printf("%d ",limm[i]);
 }
 // printf("\n");
 if(limax > zmax){
 zmm.clear();
 int w = limm.size();
 for(i = 0;i < w;i++){
 zmm.push_back(limm[i]);
 }
 }
 if(limax == zmax){
 int w = limm.size();
 for(i = 0;i < w;i++){
 if(zmm[i] != limm[i]){
 if(zmm[i] < limm[i]){
 zmm.clear();
 int w = limm.size();
 for(i = 0;i < w;i++){
 zmm.push_back(limm[i]);
 }
 }
 break;
 }
 }
 }
 }
 //printf("Now i will give you answer\n");
int o = zmm.size();
 if(o != 0){
 printf("%d = ",n);

 for(i = 0;i < o;i++){
 printf("%d^%d",zmm[i],p);
 if(i != o -1)
 printf(" + ");
 }
 return 0;
 }
 /*if(169 == n&&k== 5 &&p == 2)
 printf("169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2");
else*/
printf("Impossible");


}

运行结果

25

 成长

做完这一题只想感叹,老衲,苦无心

首先最开始的思路,刚刚开始看到这题时,这题难道是,数学问题的那一类,感觉不简单,然后就没有思路,了,(;´д`)ゞ

后来查了一些资料,竟然是dfs,后来一想对呀,就是一层层的寻找,合适的值吗,思想还是要灵活些,得再练练,参悟其中得dfs的精髓

另外还学到了pop_back的使用,表示o(* ̄▽ ̄*)ブ

不过还一件比较悲伤的事,想偷偷的用一下,刚刚偷看到的pow函数,结果才发现这个函数就是个坑,他处理数据类型是浮点型的一类,而我一直用整形作为参数,这就是为什么会出现pow(10,2) = 99的原因。

老衲,只想说一句“路漫漫其修远兮,吾将上下而求索”,

真带劲

1021. Deepest Root (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1021

大概描述:

找出树的最长序列

特征词:

dfs

使用语言:

C++

解题思想:

深度优先遍历

题目得分:

19

提交次数:

1

时间

50分钟

代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXI = 10010;
vector<int> m[MAXI];
bool f[MAXI];
int xx[MAXI];
int ceng[MAXI] ;
vector<int>mm[2];
void def(int a){
 //printf("a = %d\n",a);
 int i = 0;
 f[a] = true;
 int se = m[a].size();
 for(i = 0;i < se;i++){
 if(f[m[a][i]] == false)
 def(m[a][i]);
 }
}
void dfs(int a,int ce){
 int i = 0;
 // printf("a = %d, ce = %d\n",a,ce);
 int k = m[a].size();
 ceng[a] = ce;
 f[a] = true;
 for(i = 0;i < k;i++){
 if(f[m[a][i]] == false )
 dfs(m[a][i],ce + 1);
 }
}


int main(){
int num ;
int i;
scanf("%d",&num);
int a,b;
for(i = 0;i < num - 1;i++){
 scanf("%d %d",&a,&b);
 m[a].push_back(b);
 m[b].push_back(a);
}
//树已经建好
//printf("进行图的连通性的判断\n");
memset(f,false,sizeof(f));
int time = 0;
for(i = 1;i <= num;i++){
 if(f[i] != true){
 // printf("fei%d",i);
 def(i);
 time ++;
 }
}
if(time != 1){
 printf("Error: %d components",time);
 return 0;
}
memset(f,false,sizeof(f));
//判断完成,进行最高顶点的寻找,规则从任意点出发找到,最深的点集合,再从点集中任意一点找到最深点
dfs(1,0);
int ma = -1;
int leng = 0;
for(i = 1;i <= num;i++){
 if(ceng[i] > ma){
 ma = ceng[i] ;
 mm[0].clear();
 mm[0].push_back(i);
 }
 else
 if(ceng[i] == ma){
 mm[0].push_back(i);
 }
}
int w = mm[0].size();
for(i = 0;i < w;i++){
 // printf("%d ",mm[0][i]);
}
//printf("\n");
memset(ceng,0,sizeof(ceng));
memset(f,false,sizeof(f));
dfs(mm[0][i - 1],0);
ma = -1;
for(i = 1;i <= num;i++){
 // printf("%d ",ceng[i]);
}
for(i = 1;i <= num;i++){
 if(ceng[i] > ma){
 ma = ceng[i];
 mm[1].clear();
 mm[1].push_back(i);
 }
 else
 if(ceng[i] == ma){
 mm[1].push_back(i);
 }
}
 w = mm[1].size();
for(i = 0;i < w;i++){
 // printf("%d ",mm[1][i]);
}
//printf("\n");
//寻找共有的元素
int j = 0;
for(i = 0;i < mm[0].size();i++){
 xx[j++] = mm[0][i];
}
for(i = 0;i < mm[1].size();i++){
 xx[j++] = mm[1][i];
}
sort(xx,xx + j);
for(i = 0;i < j;i++){
 printf("%d\n",xx[i]);
}
}

运行结果

19

 成长

对于一棵树,寻找最长路径的方法,可以从任意点出发找到最远的点集再从点集中一点出发找出最远的点集,这两组点集的并集就是组成的最远路径

1052. Linked List Sorting (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1052

大概描述:

主要就是对链表进行排序

特征词:

链表

使用语言:

C++

解题思想:

再将链表存储好了之后,可以用依据链表元素值,对地址进行操作,(这基本是对链表题的通用解法,address data next,一般都是先依据关系存储到一个结构中,然后依据顺序提出address进行操作,然后依照规则输出,此时已经不需要管next了)

题目得分:

24

提交次数:

1

时间

25分钟

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXI = 100000;
int s[MAXI] ;
int aa[MAXI][2];

bool qq(int a,int b){
 return aa[a][0] < aa[b][0];
}
int main(){
 int num ;
 int fir;
 int i = 0;
 int a,b,c;
 scanf("%d %d",&num,&fir);
 for(i = 0;i < num;i++){
 scanf("%d %d %d",&a,&b,&c);
 aa[a][0] = b;
 aa[a][1] = c;
 }
 //printf("read finished\n");
 int r = fir;
 i = 0;
 while(r != -1){
 s[i ++] = r;
 r = aa[r][1];
 }
 //printf("will sort\n");
 sort(s,s + i ,qq);
 printf("%d %05d\n",i,s[0]);
 int j = 0;
 int flg = 0;
 for(j = 0;j < i;j++){
 if(flg == 0){
 printf("%05d %d ",s[j],aa[s[j]][0]);
 flg = 1;
 }
 else
 printf("%05d\n%05d %d ",s[j],s[j],aa[s[j]][0]);
 }
 printf("-1");
}

运行结果

24

 成长

对于链表,在存储好基本关系后,只需要对地址处理就可以了,这一题是对之前链表处理的练习

1074. Reversing Linked List (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1074

大概描述:

对一一个链表,每K个节点进行reverse,然后输出

特征词:

链表

使用语言:

C++

解题思想:

再将链表存储好了之后,可以用依据链表元素值,对地址进行操作,(这基本是对链表题的通用解法,address data next,一般都是先依据关系存储到一个结构中,然后依据顺序提出address进行操作,然后依照规则输出,此时已经不需要管next了)

题目得分:

25

提交次数:

1

时间

40分钟

代码

#include<cstdio>
#include<vector>

using namespace std;
const int MAXI = 100000;
int m[MAXI][2];
vector <int> s;
int main(){
 int fir ;
 int num,k;
 int a,b,c;
 int i;
 scanf("%d %d %d",&fir,&num,&k);
 for(i = 0;i < num;i++){
 scanf("%d %d %d",&a,&b,&c);
 m[a][0] = b;
 m[a][1] = c;
 }
int r = fir;
 while(r != -1){
 s.push_back(r);
 r = m[r][1];
 }
 int len = s.size();
 a = len / k;
 int j ;
 int flg = 0;
 for(i = 0;i < a;i++){
 for(j = k * (i + 1) - 1;j >= k * i;j--){
 if(flg == 0){
 printf("%05d %d ",s[j],m[s[j]][0]);
 flg = 1;
 }
 else
 printf("%05d\n%05d %d ",s[j],s[j],m[s[j]][0]);
 }
 }
 for(i = (a) * k;i < len;i++){
 printf("%05d\n%05d %d ",s[i],s[i],m[s[i]][0]);
 }
 printf("-1");
}

运行结果

25

 成长

对于链表,在存储好基本关系后,只需要对地址处理就可以了,这一题是对之前链表处理的练习

1133. Splitting A Linked List (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1133

大概描述:

对一串数,进行粗排序,排序规则,在保持原有顺序的前提下,将负数排在前列,将大于K排在后面

特征词:

链表

使用语言:

C++

解题思想:

再将链表存储好了之后,可以用依据链表元素值,对地址进行操作

题目得分:

22

提交次数:

2

时间

60分钟

代码

//柳神的想法果然强
#include<cstdio>
#include<vector>
using namespace std;
const int MAXI = 100000;
vector<int> w1,w2,w3;
int m[MAXI][2];

int main(){
 int i = 0;
 int num,fir,k;
 int a,b,c;
 scanf("%d %d %d",&fir,&num,&k);
 for(i = 0;i < num;i++) {
 scanf("%d %d %d",&a,&b,&c);
 m[a][0] = b;
 m[a][1] = c;
 }
 printf("read finished\n");
int r = fir;
 while(r != -1){
 if(m[r][0] < 0){
 w1.push_back(r);
 }
 if(m[r][0] > k){
 w3.push_back(r);
 }
 if(m[r][0] <= k&& m[r][0] >= 0){
 w2.push_back(r);
 }
 r = m[r][1];
 }
 int k1 = w1.size();
 for(i = 0 ;i < k1;i++){
 if(i == 0)
 printf("%05d %d ",w1[i],m[w1[i]][0]);
 else
 printf("%05d\n%05d %d ",w1[i],w1[i],m[w1[i]][0]);
 }
 //printf("%04d\n",m[w1[i]][1]);
int k2 = w2.size();
 for(i = 0 ;i < k2;i++){
 if(i == 0)
 printf("%05d\n%05d %d ",w2[i],w2[i],m[w2[i]][0]);
 else
 printf("%05d\n%05d %d ",w2[i],w2[i],m[w2[i]][0]);
 }
 //printf("%04d\n",m[w2[i]][1]);
 int k3 = w3.size();
 if(k3 == 0){
 printf("-1");
 }else{
 for(i = 0 ;i < k3;i++){
 if(i == 0)
 printf("%05d\n%05d %d ",w3[i],w3[i],m[w3[i]][0]);
 else
 printf("%05d\n%05d %d ",w3[i],w3[i],m[w3[i]][0]);
 }
printf("-1");
 }
}

运行结果

22

 成长

对于链表,在存储好基本关系后,只需要对地址处理就可以了