数据结构:栈和递归求两顶点所有简单路径
添加时间: 2007-4-9 0:57:35 作者: 程序员认证参考 阅读次数:131 来源: http://www.d9soft.com
栈和递归在程序设计中的应用是非常广的，比如对于迷宫的求解、表达式的求解，等都可以用栈来解决，典型的hanoi塔问题，树和图的遍历等都可以用递归来解决，在数据结构等很多书中都有介绍，如果对此不了解，可去参考。递归算法的设计实际上就是对问题的抽象的过程，如果抽象到每个小问题都有相同特征时，那就形成了递归，递归算法简明易懂，下面我就介绍一种利用到栈与递归求解两顶点所有简单路径的问题。
先说明一下什么叫“两顶点的所有简单路径”的概念，“两顶点的所有简单路径”的意思通熟的讲就是在图中有若干点，点与点之间可有边相连（在数据结构中叫“图”），任意设个起点和终点，现在要求的是从起点到终点所有可能通过的边序列的集合。（注：是简单有序边，也就是说简单路径，所谓简单路径就是序列中顶点不重复出现的路径。）举个例子：从上海到北京，我可以直接到达，也可以先到四川，再到北京，或者先到广东，再到北京，等等。如：上海->四川->上海->北京，这就不是简单路径了，显然，不是简单的路径有无数条。
为了描述方便，我用了简单的二维数组来做存储结构。（当然，完全可以用邻接矩阵、邻接表、十字链表、邻接多重表等来表示）
* * *
* * *
* * *
如上图左上角的坐标为(1,1)，右上角的坐标为(3,1)，左下角的坐标为(1,3)，右下角的坐标为(3,3)，点与点之间都可相通，假设从点(1,1)要到(3,3)，有多少种走法？
对这个问题的求解先要认识到它的本质，其本质是一个点有四个方向（各边特殊处理），依次探索四个方向上的点，判断是不是最后的目的地，如果是，则进栈并返回，如果不是则进栈，将此点同样上述处理。显然这个过程是一个递归的过程，直到是最后的目的地，才层层返回。
当然，解决此问题不是只有栈与递归才能解决，经我自己摸索，用生成树的方法访问其双亲结点，也可解决，如果有更好的方法，请多多指教。
注意:当运行程序时,输入的maxx,maxy的数最好小等于3,不然效率很低!
//用栈和递归求解两顶点的所有简单路径
//borland c++ 3.1下编译通过
#include <stdlib.h>
#include <iostream.h>
#define SIZE 100
#define STACK_INIT_SIZE 1
#define STACKINCREMENT 1
typedef struct pos{
int x,y;
}pos;
typedef struct{
pos *base,*top;
int stacksize;
}sqstack;
sqstack s;
pos pstack[SIZE][SIZE];
int m=0,maxx,maxy;
int initstack(sqstack &s){
s.base=(pos *)malloc(STACK_INIT_SIZE*sizeof(pos));
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return 1;
}
int push(sqstack &s,pos e){
if(s.top-s.base>=s.stacksize){
s.base=(pos *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(pos));
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;
}
*s.top++=e;
return 1;
int pop(sqstack &s,pos &e){
if(s.top==s.base) return 0;
e=*--s.top;
return 1;
}
int stacktraverse(sqstack s,pos e){
int i;
for(i=0;(s.base+i)<=(s.top-1);i++)
if(((s.base+i)->x==e.x) && ((s.base+i)->y==e.y)) return 0;
return 1;
}
void list(int maxx,int maxy,pos a,pos b)
{
int fx,n;pos c;
push(s,a);
if(a.x==b.x && a.y==b.y)
{
for(n=0;(s.base+n)<=(s.top-1);n++) pstack[m][n]=*(s.base+n);m++;
pop(s,c);
return;
}
for(fx=1;fx<=4;fx++)
{
switch(fx)
{
case 1:
{if(a.x<maxx) {c.x=a.x+1;c.y=a.y;break;} else continue;}
case 2:
{if(a.y<maxy) {c.x=a.x;c.y=a.y+1;break;} else continue;}
case 3:
{if(a.x>1) {c.x=a.x-1;c.y=a.y;break;} else continue;}
case 4:
{if(a.y>1) {c.x=a.x;c.y=a.y-1;break;} else continue;}
}
if(stacktraverse(s,c)) list(maxx,maxy,c,b);
}
pop(s,c);
}
main()
{
int i,j;
pos a,b;
cout<<"max x=";
cin>>maxx;
cout<<"max y=";
cin>>maxy;
cout<<"start x=";
cin>>a.x;
cout<<"start y=";
cin>>a.y;
cout<<"end x=";
cin>>b.x;
cout<<"end y=";
cin>>b.y;
initstack(s);
list(maxx,maxy,a,b);
for(i=0;i<=m-1;i++){
for(j=0;j<=SIZE;j++)
{cout<<'('<<pstack[i][j].x<<','<<pstack[i][j].y<<')'<<" ";
if(pstack[i][j].x==b.x && pstack[i][j].y==b.y) break;}
cout<<" ";}
return 1;
上一篇文章: 数据结构：快速排序算法(新) 下一篇文章: 水滴石穿·C语言之代码检查工具
相关文章: