wangyinshiwo 发布留言 2008-7-16 10:55 递归算法的内部运行问题/* Note:Your choice is C IDE */ #include "stdio.h" #define MAX 100 #include
/*以下定义邻接矩阵类型*/
typedef struct node
{
int info;
int value;
}vtype;
typedef struct
{
int vexnum,arcnum;
vtype vexs[MAX];
int edges[MAX][MAX];
}adjmatrix;
/*一下定义邻接表类型*/
typedef struct qnode
{
int adjvex;
int value;
struct qnode *next;
}arcnode;
typedef struct
{
char data;
arcnode *firsthead;
}headone;
typedef struct
{
int n,e;
headone adjlist[MAX];
}graphlist;
int visited[MAX];
void pathall(graphlist *g,int u,int v,int path[],int i)
{
arcnode *p;
int j,n;
p=g->adjlist[u].firsthead;
while(p)
{
n=p->adjvex;
if(n==v)
{
path=v;
for(j=0;j<=i+1;j++)
printf("%3d",path[j]);printf("\n");
}
else if(visited[n]==0)
{
path=n;
pathall(g,n,v,path,i+1);
}
p=p->next;
}
visited[u]=0;
}
void pathall2(graphlist *g,int u,int v,int l,int path[],int d)
{
int m,i;
arcnode *p;
visited[u]=1;
d++;
path[d]=u;
if(u==v&&d==l)
{
for(i=0;i<=d;i++)
printf("%3d",path.firsthead;
while(p)
{
m=p->adjvex;
if(visited[m]==0)
pathall2(g,m,v,l,path,d);
p=p->next;
}
visited[u]=0;
d--;
}
int shortpath(graphlist *g,int u,int v,int path[])
{
struct
{
int vno;
int level;
int parent;
}qu[MAX];
int front=-1,rear=-1,k,lev,i,j;
arcnode *p;
visited[u]=1;
rear++;
qu[rear].vno=u;
qu[rear].level=0;
qu[rear].parent=-1;
while(front {
front++;
k=qu[front].vno;
lev=qu[front].level;
if(k==v)
{
i=0;
j=front;
while(j!=-1)
{
path[lev-i]=qu[j].vno;
j=qu[j].parent;
i++;
}
return lev;
}
p=g->adjlist[k].firsthead;
while(p)
{
if(visited[p->adjvex]==0)
{
visited[p->adjvex]=1;
rear++;
qu[rear].vno=p->adjvex;
qu[rear].level=lev+1;
qu[rear].parent=front;
}
p=p->next;
}
}
return 0;
}
void mattolist(graphlist *G,adjmatrix *g)
{
int i,j,n=g->vexnum;
arcnode *p;
for(i=0;i G->adjlist[j])
{
p=(arcnode *)malloc(sizeof(arcnode));
p->adjvex=j;p->value=g->edges;
p->next=G->adjlist.firsthead=p;
}
G->n=n;G->e=g->arcnum;
}
void displaylist(graphlist *G)
{
arcnode *p;
int i;
for(i=0;in;i++)
{
printf("头顶点为[%d]=>",i);
p=G->adjlist;
adjmatrix g;
graphlist *G;
int a[MAX][6]={{0,1,0,1,0,0},
{0,0,1,0,0,0},
{1,0,0,0,0,1},
{0,0,1,0,0,1},
{0,0,0,1,0,0},
{1,1,0,1,1,0}};
g.vexnum=6;g.arcnum=10;
for(i=0;i for(j=0;j g.edges=a;
G=(graphlist *)malloc(sizeof(graphlist));
mattolist(G,&g);
printf("图G的邻接矩阵:\n");
displaylist(G);printf("\n");
for(i=0;i visited=u;visited[u]=1;
pathall(G,u,v,path,0);printf("\n");
printf("从%d到%d的所有长度为%d路径:\n",u,v,d);
pathall2(G,u,v,d,path,-1);printf("\n");
for(i=0;i visited=0;
j=shortpath(G,u,v,path);
for(i=0;i<=j;i++)
printf("%3d",path=0;从新开始使用u顶点时，系统怎么知道以前那个输入过。如，5 0 1 2
第二路径:5 0 3 2 ，系统怎么判定5 0 1 2 访问过，递归的时候到底开辟了多少个栈，能解释一下栈的运行情况吗？
页: [1]
特别说明：如网页特效代码中有引用图片文件等，请自己下载到本地调试！ |
