Java——成语接龙——递归算法——SpringJDBC+c3p0

 

这个例子，是我练习SpringJdbc+c3p0时所写。实现了输入一个成语，得到一颗不完整的接龙树。因为我数据库里有3W多个成语，在排除了接龙树成语重复的情况下，依然不能得到全部的结果，我感觉应该不是递归进入死循环了，因为 我这个递归是有结束条件的，当给出的成语，没有接龙了，就返回。具体看看代码就知道了。

 

这个例子，让我晓得了有时，跟代码去解决问题可能再百度也无具体的办法时可以试试。再我遇到c3p0报没有找到合适的驱动的时候，开始是百度，很久都没能解决，我就跟代码，发现 再driverManger那要传String的url，可是我传的是空，c3p0的配置文件也写了的，里面的内容也都正确无误，c3p0的配置文件名 我是复制网上的，看着和要求的名称类似，但当我改了一下这个配置文件名称后，我就能打印一个连接了。这个问题也就解决了。

 

之后，再写查找成语递归的时候，我卡再了一个问题上，就是当我从根节点到尾节点递归完后，也就是找到了一条成语接龙链之后，我开始是想，怎么再返回到根节点的下一个节点，当我再 Loop（）里用return Loop()的时候，只能得到一条记录。后来再我的重新思考后，我就想，当完成一条接龙后，我把这条接龙复制下来，并去掉末尾的值，这里我不知道怎么表达了，我贴上代码再来说。

private List<List<String>>Loop(String word,List<String>listOne,List<List<String>>bigList,int m ){
if(listOne==null){
listOne=new ArrayList<String>();
}
if(bigList==null){
bigList=new ArrayList<>();
}
if(word.equals("")||word==null){
return bigList;
}
Object []args=new Object[1];
args[0]=word.substring(word.length()-1);
List<ChengYu>words=myDb.QueryForBean(selSql,args);
if(words==null||words.isEmpty()){
bigList.add(listOne);
return bigList;
}
for (int i=0;i<words.size();i++) {
ChengYu cy = words.get(i);
Boolean flag=false;
for (List<String> ll:bigList){
if(ll.contains(cy.getWord())){
flag=true;
break;
}
}
if (listOne != null && !listOne.contains(cy.getWord())&&!flag)
{ listOne.add(cy.getWord());}
else{
continue;
}
//因为情况太多了，所以当超过3就返回
if(m==3){
return bigList;
}
Loop(cy.getWord(), listOne, bigList,m++);
ArrayList copy2 =new ArrayList<String>();
copy2.addAll(listOne);
listOne=null;
listOne=copy2;
listOne.remove(listOne.size()-1);
}
return bigList;
}

每个listOne代表一条接龙，bigList代表已经得到的接龙。words代表当前成语下有好多个成语能接龙，如果这个words为空或null就代表listOne已经是完整的一条接龙了，这个时候，就把listOne加入到bigList，之后再return 代码return之后，就走到ArrayList copy2 =new ArrayList<String>();这句，这个递归没递归一次就把函数里的变量打包整体入栈一次，return就从栈定取出一个LooP，所以，再完成一条成语连之后，我能从倒数第二个成语接龙组里获得第二个成语 B，我需要从成语B继续递归，这时我需要创建一条新的成语连，并把B之前的成语节点给事先加入，然后就有了之后的

ArrayList copy2 =new ArrayList<String>();

 

因为再得到B之后，又会从B开始递归，我这样做就是把B之前的lujing给保留起来。

我的意思就是这样

a1->b1->c1

a1->b1->c2

a1->b2->d3

 

a3->q3->m4->e5

假如 a标记是根节点的后接成语组, 那么根节点下就有a1和a3两个成语可以接龙。

同理 a1有b1，b2两个成语可以接龙，b1有c1,c2...

当 listOne（a1,b1,c1）之后，Loop出栈，这个时候执行

copy2.addAll(listOne);

listOne=null;

listOne=copy2;

listOne.remove(listOne.size()-1);

就能得到listOne(a1,b1)，for循环是停留再c这个组层面上循环，for循环到开始地方，这个时候

就变成了listOne(a1,b1,c2);再继续就没有子节点了，Loop出栈，listOne(a1,b1),，这个时候for在b层，Loop(b1)也结束了，继续出栈，就继续复制，listOne就变成了listOne(a1)，for b回到循环开始的地方，listOne(a1,b2) ，就开始Loop(b2)，b2的后继成语组有d3，for循环d3所在那层，listOne(a1,b2,d3),Loop(d3) 因为d3无后继节点，Loop(d3)出栈，listOne(a1,b2),此时Loop（b2）所属的调用栈全部结束， Loop(b2) 出栈，listOne(a1),这个时候Loop(a1)的调用栈结束，Loop(a1)出栈，listOne()，for循环停留到a层，list(a3),Loop(a3),list(a3,q3），Loop(q3),list(a3,q3,m4),Loop(m4),list(a3,q3,m4,e5),Loop(e5),words集合为空 Loop(e5)出栈，listOne(a3,q3,m4).........

最后退回到Loop（a3)出栈，listOne();

调用栈全部清空，return bigList ;至此整个过程就完成了。

 

我也是第一次表达递归 调用栈，肯定表达得不清楚，想了解递归可以去网上搜索一下函数调用堆栈也许会明白些。

下载

代码及sql脚本json文件下载

提取码：801w