[求助]憋了一个礼拜,还是没调通
我刚开始学数据结构,下定决心一定要自己编,整了一个多礼拜还是没弄出来。眼看老师逼着交报告的时间要到了,我又不愿意下别人的,请大家帮帮忙吧!题目是:用临接多重表实现图的遍历,输出节点和遍历成树的边,两种遍历,深度优先和广度优先
我的程序是深度优先随着输入不一样,遍历出的点有的时候不全;广度优先遍历不知道为什么无法实现
先谢谢各位大侠了!!!!!!!!!
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define MAX_VERTEX_NUM 30
//定义节点与边结构
typedef struct Ebox{
int ivex,jvex;
struct Ebox *ilink,*jlink;
}Ebox,*Ep;
typedef struct Vexbox{
char data[20];
struct Ebox *firstedge;
}Vexbox,*Vp;
typedef struct AML{
Vp list[MAX_VERTEX_NUM];
int vexnum,arcnum;
}AML;
//定义队列结构
typedef struct Qnode1{
Ep p;
struct Qnode1 *next;
}Qnode1,*Queueptr1;
typedef struct Qnode2{
int v;
struct Qnode2 *next;
}Qnode2,*Queueptr2;
typedef struct Linkq1{
Queueptr1 front;
Queueptr1 rear;
}Linkq1;
typedef struct Linkq2 {
Queueptr2 front;
Queueptr2 rear;
}Linkq2;
//队列操作函数
Initq1(Linkq1 &Q1)
{
Q1.front=Q1.rear=(Queueptr1)malloc(sizeof(Qnode1));
Q1.front->next=NULL;
return 1;
}
Initq2(Linkq2 &Q2){
Q2.front=Q2.rear=(Queueptr2)malloc(sizeof(Qnode2));
Q2.front->next=NULL;
return 1;
}
Enqueue1(Linkq1 &Q1,Ep e){
Queueptr1 p;
p=(Queueptr1)malloc(sizeof(Qnode1));
if(!p)return 0;
p->p=e; p->next=NULL;
Q1.rear->next=p;
Q1.rear=p;
return 1;
}
Enqueue2(Linkq2 &Q2,int m){
Queueptr2 p;
p=(Queueptr2)malloc(sizeof(Qnode2));
if(!p)return 0;
p->v=m; p->next=NULL;
Q2.rear->next=p;
Q2.rear=p;
return 1;
}
Deq1(Linkq1 &Q1,Ep e){
if(Q1.front==Q1.rear) return 0;
Queueptr1 p;
p=Q1.front->next;
e=p->p;
Q1.front->next=p->next;
if(Q1.rear==p) Q1.rear=Q1.front;
free(p);
return 1;
}
Deq2(Linkq2 &Q2,int n){
if(Q2.front==Q2.rear) return 0;
Queueptr2 p;
p=Q2.front->next;
n=p->v;
Q2.front->next=p->next;
if(Q2.rear==p) Q2.rear=Q2.front;
free(p);
return 1;
}
//深度优先遍历
int visited[MAX_VERTEX_NUM];
void DFS(struct AML G,int v,Linkq1 Q){
visited[v]=1; printf("%s ",G.list[v]->data);
Ep p;
int m=v;
p=G.list[v]->firstedge;
while(p){
(p->ivex==m)?(v=p->jvex):(v=p->jvex);
if(!visited[v]){
Enqueue1(Q,p);
DFS(G,v,Q);
}
(p->ivex==m)?(p=p->ilink):(p=p->jlink);
}
}
DFSearch(struct AML G,int v){
int i;
Ep p=0;
for(i=0;i<=G.vexnum;++i) visited[i]=0;
printf("深度优先遍历的结点序列:\n");
Linkq1 Q;
Initq1(Q);
DFS(G,v,Q);
printf("生成树边集 :\n");
while((Q.front)!=(Q.rear)){
Deq1(Q,p);
printf("%s----%s ",G.list[p->ivex]->data,G.list[p->jvex]->data);
}
return 1;
}
//广度优先遍历
void BFSearch(struct AML G,int v){
Linkq2 Q2;
Linkq1 Q1;
Initq1(Q1);
Initq2(Q2);
Ep p=0;
for(int i=0;i<=G.vexnum;++i) visited[i]=0;
printf("广度优先遍历的节点序列:\n");
visited[v]=1; printf("%s ",G.list[v]->data);
Enqueue2(Q2,v);
int m;
while((Q2.front)!=(Q2.rear)){
Deq2(Q2,m);
p=G.list[m]->firstedge;
while(p){
(p->ivex==m)?(v=p->jvex):(v=p->ivex);
if(!visited[v]){
visited[v]=1; printf("s% ",G.list[v]->data);
Enqueue1(Q1,p);
Enqueue2(Q2,v);
}
(p->ivex==m)?(p=p->ilink):(p=p->jlink);
}
printf("/n");
printf("生成树边集:\n");
while(!(Q1.front=Q1.rear)){
Deq1(Q1,p);
printf("%s----%s ",G.list[p->ivex]->data,G.list[p->jvex]->data);
}
}
}
//邻接链表初始化
Creat(struct AML &A){
printf("请输入图的结点数:\n");
scanf("%d",&(A.vexnum));
printf("请输入图的边数:\n");
scanf("%d",&(A.arcnum));
printf("请输入结点名称:\n");
Vp v;
for(int i=1;i<=A.vexnum;++i){
v=(Vp)malloc(sizeof(struct Vexbox));
printf("结点%2d:",i);
scanf("%s",v->data);//输入字符串函数
printf("\n");
v->firstedge=NULL;
A.list[i]=v;
}//for点初始化
printf("请输入边的信息:\n");
for(i=0;i<A.arcnum;++i){
Ep p;
p=(struct Ebox *)malloc(sizeof(struct Ebox));
printf("邻接点i的序号:"); scanf("%2d",&(p->ivex));printf("邻接点j的序号:"); scanf("%2d",&(p->jvex));printf("\n");
p->ilink=A.list[p->ivex]->firstedge; A.list[p->ivex]->firstedge=p;
p->jlink=A.list[p->jvex]->firstedge; A.list[p->jvex]->firstedge=p;
}//for边初始化
return 1;
}//Creat
main(){
AML A;
Creat(A);
int i,j;
printf("请输入深度优先遍历的初始点序号:");
scanf("%d",&i);
DFSearch(A,i);
printf("请输入广度优先遍历的初始点序号:");
scanf("%d",&j);
BFSearch(A,j);
return 1;
}