//main.cpp
#define MaxVertices 10000
#define MaxQueueSize 10000
#define FALSE 0
#define TRUE 1
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "CreatAdjLGraph.h"
#include "SeqCQueue.h"
void main()
{int count=0,j=0;
int s[MaxVertices];
int visited[500];
for(int i=0;i<=500;i++)visited[i]=FALSE;
AdjLGraph G;
AdjInitiate(&G);
int n,c,menu=1;
while(menu)
{
printf("修道士与野人各有n人，请输入n:\n");
scanf("%d",&n);
if(n<=0)break;
printf("船只可容纳c人，请输入c:\n");
scanf("%d",&c);
if(c<=1)break;
CreatGraph(&G, n,c);
BFSTraverse(G,G.numOfVerts/2,G.numOfVerts/2+1);
if(count==0)printf("无");


printf("按 1 继续，按 0 退出 请输入c:\n");
scanf("%d",&menu);
}
}

//CreatAdjLGraph.h

typedef struct
{int mon; //修道士人数
int sav; //野人人数
int pos; //船的位置
}DataType; //定义Data结构体类型(三元组)

typedef struct Node
{
int dest;
struct Node *next;
} Edge; //邻接边单链表结构体

typedef struct
{
DataType data;
int sorce;
Edge *adj;
} AdjLHeight; //邻接表数组的结构体

typedef struct
{
AdjLHeight a[MaxVertices];
int numOfVerts;
int numOfEdges;
} AdjLGraph; //邻接表结构体


void CreatData(int n,DataType* pos1,DataType* pos0)//创建所有只保证初始岸保险的Data(三元组)
{
int a,b;//n为人数，a代表修道士人数，b代表野人人数
int i=0;
for(a=0;a<=n;a++)
{
for(b=0;(a==0||b<=a)&&b<=n;b++)

{
pos1[i].mon=a;
pos1[i].sav=b;
pos1[i].pos=1;
pos0[i].mon=a;
pos0[i].sav=b;
pos0[i].pos=0;
i++;
}
}
pos1[i+1].mon=-1;
pos0[i+1].mon=-1;
}//两个数组分别储存两种状态的合法Data，除了（0,0.1）（3,3,0），前者是pos1的第一个元素，后者是pos0的最后一个元素

void InsertVertex(AdjLGraph *G, int i, DataType vertex)//插入顶点的功能函数
{
if(i >= 0 && i < MaxVertices)
{
G->a[i].data = vertex;
G->numOfVerts++;
}
else printf("顶点越界");
}

void CreatVertex(AdjLGraph* G,DataType* pos1,DataType* pos0,int n)//创建所有保险顶点，n为人数
{ int i=0;//i为顶点序号//l、m分别为pos1和pos0的序列数
for(int l=1;pos1[l].mon!=-1;l++)//排除第一个
{if(n-pos1[l].mon>=n-pos1[l].sav)//筛选所有同时使船在彼岸Data也保险的初始岸Data
InsertVertex(G,i,pos1[l]);
i++;
}
for(int m=0; pos0[m+1].mon!=-1;m++)//排除最后一个
{if(n-pos0[m].mon>=n-pos0[m].sav)
InsertVertex(G,i,pos1[m]);
i++;
}

}
//a[numOfVerts/2].data前是船在初始岸，后边是船在彼岸
//起始结点(n,n,1)的序号为numOfVerts/2，最终结点(0,0,0)的序号为numOfVerts/2+1



//以上是创建顶点，以下是创建边


void InsertEdge(AdjLGraph *G, int v1, int v2)//插入边的功能函数
{
Edge *p;

if(v1 < 0 || v1 > G->numOfVerts || v2 < 0 || v2 > G->numOfVerts)
{
printf("参数v1或v2越界出错!");
exit(0);
}

p = (Edge *)malloc(sizeof(Edge));
p->dest = v2;

p->next = G->a[v1].adj;
G->a[v1].adj = p;

G->numOfEdges++;
}


void CreatEdge(AdjLGraph *G,int c)//创建边,c为船可容纳的人数//边是建立在船在初始岸和船在彼岸两种状态之间的
{int i,j;
for(i=0;i<=G->numOfVerts/2;i++)//a[numOfVerts/2].data前是船在初始岸，后边是船在彼岸
{
for(j=G->numOfVerts/2+1;j<=G->numOfVerts;j++)
{ if(G->a[i].data.mon-G->a[j].data.mon>=0&&G->a[i].data.sav-G->a[j].data.sav>=0)//船在初始岸人多，船在彼岸人少（因为在向彼岸送人）
{
if((G->a[i].data.mon-G->a[j].data.mon)+(G->a[i].data.sav-G->a[j].data.sav)<=c)//船上人数不可超过限制也不可为零)
{if((G->a[i].data.mon-G->a[j].data.mon)+(G->a[i].data.sav-G->a[j].data.sav)<=c)
{if(G->a[i].data.mon-G->a[j].data.mon>=G->a[i].data.sav-G->a[j].data.sav||G->a[i].data.mon-G->a[j].data.mon==0)//船上修道士人数不少于野人，或者修道士人数为零
InsertEdge(G,i,j);//建立序号为i,j的顶点的边<i,j>
InsertEdge(G,j,i);//建立序号为i,j的顶点的边<j,i>
}
}}

}
}
}


//以上是创建边，以下是创建图
void AdjInitiate(AdjLGraph *G)//初始化图
{
int i;

G->numOfVerts = 0;
G->numOfEdges = 0;
for(i = 0; i < MaxVertices; i++)
{
G->a[i].sorce = i;
G->a[i].adj = NULL;
}
}
void CreatGraph( AdjLGraph *G, int n,int c)//创建图
{DataType pos1[500];
DataType pos0[500];
CreatData(n,pos1,pos0);//创建数据CreatData(int n,DataType* pos1,DataType* pos0)
CreatVertex(G,pos1,pos0,n);//创建顶点CreatVertex(AdjLGraph* G,DataType* pos1,DataType* pos0,int n)
CreatEdge(G,c);//创建边CreatEdge(AdjLGraph *G,int c)
}

//SeqCQueue.h


typedef struct
{
DataType queue[MaxQueueSize];
int rear; /*队尾指针*/
int front; /*队头指针*/
} SeqCQueue;

void QueueInitiate(SeqCQueue *Q) /*初始化顺序循环队列Q*/
{
Q->rear = 0; /*定义初始队尾指针下标值*/
Q->front = 0; /*定义初始队头指针下标值*/
}
int QueueNotEmpty(SeqCQueue Q)
/*判顺序循环队列Q非空否，非空则返回1，否则返回0*/
{
if(Q.front == Q.rear) return 0;
else return 1;
}

int QueueAppend(SeqCQueue *Q, DataType x)
/*把数据元素值x插入顺序循环队列Q的队尾，成功返回1，失败返回0 */
{
if((Q->rear+1) % MaxQueueSize == Q->front)
{
printf("队列已满无法插入! \n");
return 0;
}
else
{
Q->queue[Q->rear] = x;
Q->rear = (Q->rear + 1) % MaxQueueSize;
return 1;
}
}
int QueueDelete(SeqCQueue *Q,DataType *d)
/*删除顺序循环队列Q的队头元素并赋给d ，成功返回1，失败返回0*/
{
if(Q->front == Q->rear)
{
printf("循环队列已空无数据元素出队列! \n");
return 0;
}
else
{
*d = Q->queue[Q->front];
Q->front = (Q->front + 1) % MaxQueueSize;
return 1;
}
}
void BFSTraverse(AdjLGraph G,int v,int w) //图的广度优先遍历算法求v与w之间所有可行路径
{ extern int count,j;
extern int s[MaxVertices];
extern int visited[500];

int u;
Edge *q;
SeqCQueue Q;
QueueInitiate(&Q); // 置空的辅助队列
visited[v]=TRUE; // 设置访问标志为TRUE(已访问)，在函数外面定义并初始化，s[]初始化为-1
s[j]=v; // 用于保存路径
QueueAppend( &Q, v); //将v入队列以求它的邻接点
while(!QueueNotEmpty(Q))//队列不为空的情况下进行操作
{
QueueDelete(&Q,&u); //删除队头，并用u取出队头的数据
for(q=G.a[u].adj; q ;q=q->next) //若有邻接节点，则执行下面操作
{
if( !visited[q->dest]) //在它的邻接结点没有访问过的前提下进行操作
{ j++;
if(q->dest!= w)BFSTraverse(G,q->dest,w); //当邻接点不为终点时，递归求改点的邻接点
else //当找到终点时，输出该条路径a[i]
s[j]=q->dest;

printf("渡河方案为:\n");
for(int i=0;s[i]=G.numOfVerts/2+1;i++)
{
printf("( %d , %d , %d )\n",G.a[s[i]].data.mon,G.a[s[i]].data.sav,G.a[s[i]].data.pos);
count++; //count为定义在外面的全局变量，是方案的数目
}
}
else
visited[q->dest]=FALSE; //找到终点或该路径全部访问时，将最后访问的a[c]=-1; //标记为未访问并删除保存的路径及路程
j--;

}

}
}

果然够复杂

好吧，只能说静下心来，理清头绪慢慢找...
楼主，加油

学习楼主精神

加油。

给力啊！

有点大了...能不能先把错的地方的那个函数单独放出来啊，
或者直接去问百度小姐这个题目，弄懂后再将自己的改造一下

-------------------配置：J - Win32调试--------------------
编译...
J.C
C：\文件和设置\管理员\桌面\ JC（9）：致命错误C1083：无法打开包括文件：“CreatAdjLGraph.h”：没有这样的文件或目录
执行cl.exe时时出错。

j.obj（S） - 1个错误，0个警告（S）

有点复杂，有点头大。静下心来