数据结构课设)"/>
神秘国度的爱情故事(C++数据结构课设)
目录
1、题目
2、代码
3、运行图
4、说明书
1、题目
2、代码
#include<iostream>
using namespace std;
#define MAXNODE 10000 //小村最大个数
int visited[MAXNODE]; //标志数组typedef struct Edge //边结点
{int index; //顶点在顶点数组中的位置struct Edge* nextedge; //指向下一个边结点
}EdgeNode;typedef struct VNode //顶点信息
{int data; //顶点数据EdgeNode* firstedge; //指向第一条边的指针
}Link;typedef struct //定义邻接表
{int vertexnum, edgenum;//总顶点数和总边数Link vertics[MAXNODE]; //顶点数组
}Graph;void CreateGraph(Graph& g)
{//采用邻接表表示法建立无向村落图cout << "小主，请输入神秘国度中的小村个数N：";while (true){cin >> g.vertexnum;while(!cin.good()){cin.clear();cin.sync();system("COLOR 01");cout << "小主莫急，请重新输入：";cin >> g.vertexnum; }if (1 <= g.vertexnum && g.vertexnum <= MAXNODE) break;system("COLOR 01");cout << "小主莫急，请重新输入：";}system("COLOR F4");g.edgenum = g.vertexnum - 1;//道路数是村子数-1int i;for (i = 0; i < g.vertexnum; i++){g.vertics[i].data=i; //每个小村从0开始编号g.vertics[i].firstedge = NULL;}cout << "------------------------------------------\n" ;for (i = 0; i < g.edgenum; i++){int m, n;cout << "请输入第" << i + 1 << "条道路的两个端点小村的编号：";while (true){cin >> m >> n;while (!cin.good()){cin.clear();cin.sync();system("COLOR 01");cout << "小主莫急，请重新输入：";cin >> m >> n;}if (m >= 0 && m < g.vertexnum && n >= 0 && n < g.vertexnum) break;system("COLOR 01");cout << "小主莫急，请重新输入：";}system("COLOR F4");if(i<g.edgenum-1)cout << "---------------------------\n" ;EdgeNode* p1 = new Edge; //头插法,先建立一个Edge类型的结点p1p1->index = n; //将n村的编号赋值给p1的数据域p1->nextedge = g.vertics[m].firstedge;//将p1的指针域赋为空值g.vertics[m].firstedge = p1; //将第m个表头结点的指针域指向p1EdgeNode* p2 = new Edge; //建立无向图p2->index = m;p2->nextedge = g.vertics[n].firstedge;g.vertics[n].firstedge = p2;}
}void BfsTree2(Graph g, int C , int B)
{//广度优先遍历邻接表,并查询B是否在C到所有未访问结点的路径上int k, Q[MAXNODE], front = 0, rear = 0;//使用队列int i = 0;EdgeNode* p; //指向边结点的指针visited[C] = 1; //C村开始所有访问过的村子标志为1rear = (rear + 1) % MAXNODE; //计算队尾所在位置Q[rear] = C; //从C村开始while (front != rear) //判断队空{front = (front + 1) % MAXNODE;//计算队头所在位置k = Q[front];p = g.vertics[k].firstedge;while (p != NULL && i != 1) //是否为最后一个边结点{if (!visited[p->index]) //结点是否被访问过{visited[p->index] = 1;//标记已访问if (p->index == B) //如果遍历到B{cout << " YES 千里姻缘一路牵，一生甜蜜两村间" << endl;i = 1;rear = front;}if (i == 0){rear = (rear + 1) % MAXNODE;Q[rear] = p->index;}}//访问结束 p = p->nextedge;} //判断指针为空结束} //判断队列为空结束if (i != 1)cout << " NO 此情可待成追忆，只是当时已惘然" << endl;
}void BfsTree1(Graph g, int A, int B, int C)
{//广度优先遍历邻接表,并查询C是否在A和B之间的路径上int k, Q[MAXNODE], front = 0, rear = 0;//使用队列int i = 0;EdgeNode* p; //指向边结点的指针visited[A] = 1; //A村开始所有访问过的村子标志为1rear = (rear + 1) % MAXNODE; //计算队尾所在位置Q[rear] = A; //从A村开始while (front != rear) //判断队空 {front = (front + 1) % MAXNODE;//计算队头所在位置k = Q[front];p = g.vertics[k].firstedge;while (p != NULL && i != 1) //是否为最后一个边结点{if (!visited[p->index]) //结点是否被访问过{visited[p->index] = 1;//标记已访问if (p->index == B) //如果遍历到B{cout << " NO 此情可待成追忆，只是当时已惘然" << endl;i = 1;front = rear;}else{if (p->index == C)//如果遍历到C{BfsTree2(g, C, B);i = 1;front = rear;}}if (i == 0){rear = (rear + 1) % MAXNODE;Q[rear] = p->index;}}//访问结束p = p->nextedge;} //判断指针为空结束} //判断队列为空结束
}void test(Graph g)
{//测试int M, i, j;int test1[MAXNODE], test2[MAXNODE], test3[MAXNODE];//用于存放测试组数据cout << "------------------------------------------\n";cout << "请输入测试组个数M：";while (true){cin >> M;while (!cin.good()){cin.clear();cin.sync();system("COLOR 01");cout << "小主莫急，请重新输入：";cin >> M;}if (1 <= M && M <= MAXNODE) break;system("COLOR 01");cout << "小主莫急，请重新输入：";}system("COLOR F4");cout << "------------------------------------------\n";for (i = 0; i < M; i++){cout << "请输入第"<<i+1<<"组要测试的A B C三村的编号：";while (true){cin >> test1[i] >> test2[i] >> test3[i];while (!cin.good()){cin.clear();cin.sync();system("COLOR 01");cout << "小主莫急，请重新输入：";cin >> test1[i] >> test2[i] >> test3[i];}if ((test1[i] >= 0 && test1[i] < g.vertexnum) &&(test2[i] >= 0 && test2[i] < g.vertexnum) &&(test3[i] >= 0 && test3[i] < g.vertexnum))break;system("COLOR 01");cout << "小主莫急，请重新输入：";}system("COLOR F4");if(i<M-1)cout << "---------------------------\n";}cout << "------------------------------------------\n";cout << "测试后的结果为：\n" ;for (i = 0; i < M; i++){if (test1[i] == test3[i] || test2[i] == test3[i])cout << " YES 千里姻缘一路牵，一生甜蜜两村间" << endl;else{for (j = 0; j < g.vertexnum; j++)visited[j] = 0;//所有未访问村子标志为0BfsTree1(g, test1[i], test2[i], test3[i]);}}
}int main()
{system("COLOR F4");cout << " ****** ****** " << endl;cout << " ********** ********** " << endl;cout << " ************************* " << endl;cout << " ***神秘国度的爱情故事**** " << endl;cout << " ************************* " << endl;cout << " *********************** " << endl;cout << " ***************** " << endl;cout << " ************* " << endl;cout << " ******* " << endl;cout << " * " << "\n\n\n";Graph g;CreateGraph(g);test(g);cout << "\n\n";system("pause");return 0;
}3、运行图
4、说明书
哈哈，说明书需要加我QQ：2059718410领取哦，因为我暂时不能上传资源。
更多推荐
神秘国度的爱情故事(C++数据结构课设)
发布评论