用C、C++写旅游区景点导游系统(使用文件存储，DFS，DIJ算法，附详细说明）

旅游区景点导游系统

！！！！注意，源代码在此：
Main函数文件
Function函数文件
Head头文件

1、数据格式

使用TXT文件形式存储景点信息:

VerTex.txt文件

5 <—-G.vexnum 顶点个数（景点个数）

A <—-G.vexs[i].name 顶点名称（景点名称）

1 <—-G.vexs[i].id 顶点编号（景点编号）

AAAA <—-G.vexs[i].intro 顶点介绍（景点介绍）

ArcCell.txt文件

6 <—-G.arcnum 边个数（路径个数）

1 2 <—-G.arcs[起点] [终点] 边两端（路径两端）

20 <—-G.arcs[起点] [终点].adj 边权值（路径长度）

2、数据结构（读文件创建图）

//头文件Head.h结构体信息typedef struct VerTexSet{//顶点信息` `int id;` `char name[32];``char intro[256];``}Vertex;``typedef struct ArcCell{//边信息`  `int adj;``}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];``typedef struct {//无向图信息`  `Vertex vexs[MAX_VERTEX_NUM];` `AdjMatrix arcs;` `int vexnum;``int arcnum;``}MGraph;````typedef struct PathStack {// 定义用于记录路径的栈结构``int data[MAX_VERTEX_NUM];``int top;``}PathStack;`

使用typedef定义VerTexSet（顶点）、ArcCell（边）、PathStack（栈）三个基础结构，组合VerTexSet和ArcCell建立MGraph（图）结构。

围绕MGraph完成读文件创建图功能、读图创建文件功能：

void CreatFG(MGraph &G){//根据文件中的数据创建一个图。//其中，VerTex.txt 文件包含顶点的信息，ArcCell.txt 文件包含边的信息。FILE *fp1 = fopen("VerTex.txt","r");if(fp1==NULL){printf("FILE Open Failed!\n");return;}int i;fscanf(fp1,"%d",&G.vexnum);for(i=1;i<=G.vexnum;i++){fscanf(fp1,"%s %d %s",G.vexs[i].name,&G.vexs[i].id,G.vexs[i].intro);}FILE *fp2 = fopen("ArcCell.txt","r");if(fp2==NULL){printf("FILE Open Failed\n");return;}fscanf(fp2,"%d",&G.arcnum);int j,k;for(i=0;i<=MAX_VERTEX_NUM-1;i++){for(j=0;j<=MAX_VERTEX_NUM-1;j++){G.arcs[i][j].adj=Infinity;G.arcs[j][i].adj=Infinity;}}int va,vb,adj;for(k=1;k<=G.arcnum;k++){fscanf(fp2,"%d %d %d",&va,&vb,&adj);G.arcs[LocateVex(G,va)][LocateVex(G,vb)].adj=G.arcs[LocateVex(G,vb)][LocateVex(G,va)].adj=adj;}}void SaveG(MGraph G){//将图的数据保存到文件中。//其中，VerTex.txt 文件保存顶点的信息，ArcCell.txt 文件保存边的信息FILE *fp1 = fopen("VerTex.txt","w");if(fp1==NULL){printf("FILE Write Failed!\n");return;}fprintf(fp1,"%d",G.vexnum);int i;for(i=1;i<=G.vexnum;i++){fprintf(fp1,"\n%s %d %s",G.vexs[i].name,G.vexs[i].id,G.vexs[i].intro);}FILE *fp2 = fopen("ArcCell.txt","w");if(fp2==NULL){printf("FILE Write Failed\n");return;}fprintf(fp2,"%d",G.arcnum);int va,vb;for(va=0;va<=MAX_VERTEX_NUM-1;va++)for(vb=0;vb<=MAX_VERTEX_NUM-1;vb++){if(G.arcs[va][vb].adj!=Infinity&&va<vb)fprintf(fp2,"\n%d %d %d",va,vb,G.arcs[va][vb].adj);}CreatFG(G);}

函数CreatFG(G)重点调用函数fscanf()，完成图对数据文件VerTex.txt和ArcCell.txt的读取。首先，读得vernum和arcnum数据，先对0至（MAX_VERTEX_NUM-1）的顶点和0至（MAX_VERTEX_NUM-1）的边进行初始化，再对1至vernum的顶点和1至arcnum的边进行数据填充。

函数SaveG(G)重点调用函数fprintf(),完成图的数据保存到VerTex.txt和ArcCell.txt文件。首先，分别将vernum和arcnum打印到VerTex.txt和ArcCell.txt的首行，然后将1至vernum的顶点信息按名称 编号 介绍的格式按行打印至VerTex.txt，将1至arcnum的边信息按顶点1 顶点2 边权值的格式按行打印至ArcCell.txt。最后将顶点和边初始化。

3、查询、编辑景点信息

使用六个函数：AddVertex(G)、DeleteVertex(G)、AmendVertex(G)、AddArcCell(G)、DeleteArcCell(G)、AmendArcCell(G)完成六个基础景点编辑操作：增加景点、删除景点、修改景点、增加路径、删除路径、修改路径。

最后使用Modification(G)函数整合六个操作。

void AddVertex(MGraph &G){//向图中添加节点//函数首先通过用户输入节点的名称和介绍，将节点信息存储在G.vexs中//然后更新节点数量，并通过SaveG函数将更改保存到文件中//最后询问用户是否继续添加节点，若继续则再次执行函数，否则退出函数char name[32];char intro[256];int flag=0;do{if(G.vexnum>=MAX_VERTEX_NUM){printf("Vertex is already full!\n");return;}G.vexnum++;printf("Please input Vertex's name:");scanf("%s",G.vexs[G.vexnum].name);printf("Please input Vertex's introduction:");scanf("%s",G.vexs[G.vexnum].intro);G.vexs[G.vexnum].id=G.vexnum;SaveG(G);printf("Add Vertex Success!");printf("Do you want to add a Vertex more" />);scanf("%d",&flag);}while(flag);}void DeleteVertex(MGraph &G){//从图中删除节点//函数首先通过用户输入节点的id，定位节点在G.vexs数组中的位置i//然后遍历整个邻接矩阵，将与该节点有关的所有边删除，并将节点在G.vexs中的位置后面的所有节点向前移动一位//最后更新节点数量，并通过SaveG函数将更改保存到文件中//最后询问用户是否继续删除节点，若继续则再次执行函数，否则退出函数int k;int flag=0;do{printf("\nPlease input the Vertex's id:");scanf("%d",&k);int i=LocateVex(G,k);if(i){int j;for(j=1;j<=G.vexnum;j++){if(G.arcs[i][j].adj!=Infinity){G.arcnum--;G.arcs[i][j].adj=Infinity;G.arcs[j][i].adj=Infinity;}}for(j=i+1;j<=G.vexnum;j++){G.vexs[j-1]=G.vexs[j];}G.vexnum--;SaveG(G);printf("Delete Vertex Success!");printf("Do you want to delete a Vertex more?(0 for no,1 for yes)\n");scanf("%d",&flag);}else{printf("VerTex not exists!");}}while(flag);}void AmendVertex(MGraph &G){//修改节点的信息//函数首先通过用户输入节点的id//定位节点在G.vexs数组中的位置i，然后通过用户输入修改后的节点名称和介绍，更新节点信息//最后通过SaveG函数将更改保存到文件中//最后询问用户是否继续修改节点，若继续则再次执行函数，否则退出函数int flag=0;do{int k;printf("\nPlease input the Vertex's id:");scanf("%d",&k);int i=LocateVex(G,k);if(i!=-1){printf("Please input the new name:");scanf("%s", G.vexs[i].name);printf("Please input the new introduction:");scanf("%s", G.vexs[i].intro);SaveG(G);printf("Amend Vertex Success!");printf("Do you want to amend a Vertex more?(0 for no,1 for yes)\n");scanf("%d",&flag);}else{printf("Vertex not exists!\n");}} while(flag);}void AddArcell(MGraph &G){//向图中添加边 //函数首先通过用户输入边的两个顶点，将边信息存储在G.arcs中//然后更新边数量，并通过SaveG函数将更改保存到文件中//最后询问用户是否继续添加边，若继续则再次执行函数，否则退出函数int va,vb,adj;int flag=0;do{printf("Please input the origin:");scanf("%d",&va);printf("Please input the end:");scanf("%d",&vb);if(!LocateVex(G,va)||!LocateVex(G,vb)){printf("There are no attractions numbered va or vb!\n");continue;}printf("\nPlease input the distance:");scanf("%d",&adj);if(adj<=0||adj==Infinity){printf("Wrong input!\n");printf("\nPlease input the distance:");scanf("%d",&adj);}G.arcnum++;G.arcs[va][vb].adj=G.arcs[vb][va].adj=adj;SaveG(G);printf("Add ArcCell Success!");printf("Do you want to add an Arcell more?(0 for no,1 for yes)\n");scanf("%d",&flag);}while(flag);}void DeleteArcCell(MGraph &G){//从图中删除边//函数首先通过用户输入边的两个顶点，确定边是否存在 //若边存在，将这条边初始化 //最后更新边数量，并通过SaveG函数将更改保存到文件中//最后询问用户是否继续删除边，若继续则再次执行函数，否则退出函数int flag=0;int va,vb;do{printf("Please input the origin:");scanf("%d",&va);printf("Please input the end:");scanf("%d",&vb);if(!LocateVex(G,va)&&!LocateVex(G,vb)){printf("There are no attractions numbered va or vb!\n");continue;}G.arcnum--;G.arcs[va][vb].adj = G.arcs[vb][va].adj = Infinity;SaveG(G);printf("Delete ArcCell Success!");printf("Do you want to delete another ArcCell? (0 for no, 1 for yes)\n");scanf("%d",&flag);}while(flag);}void AmendArcCell(MGraph &G){//修改边的信息//函数首先通过用户输入边的两个顶点 //若边存在，改变其权值，更新边信息//最后通过SaveG函数将更改保存到文件中//最后询问用户是否继续修改边，若继续则再次执行函数，否则退出函数int va,vb,adj;int flag=0;do{printf("Please input the origin:");scanf("%d",&va);printf("Please input the end:");scanf("%d",&vb);if(LocateVex(G,va)==-1||LocateVex(G,vb)==-1){printf("There are no attractions numbered va or vb!\n");continue;}printf("Please input the new distance:");scanf("%d",&adj);if(adj<=0||adj==Infinity){printf("Wrong input!\n");printf("\nPlease input the distance:");scanf("%d",&adj);}G.arcs[va][vb].adj=G.arcs[vb][va].adj=adj;SaveG(G);printf("Amend ArcCell Success!");printf("Do you want to amend another Arcell?(0 for no, 1 for yes)\n");scanf("%d",&flag);}while(flag);}void Modification(MGraph G){//对景点信息，景点之间路径信息进行选择修改 int choice;do{printf("1.添加景点\n");printf("2.添加景点之间路径\n");printf("3.删除景点\n");printf("4.删除景点之间路径\n");printf("5.修改景点\n");printf("6.修改景点之间路径\n");printf("0.返回\n");printf("您的选择是:");scanf("%d",&choice);switch(choice){case 1:AddVertex(G);break;case 2:AddArcell(G);break;case 3:DeleteVertex(G);break;case 4:DeleteArcCell(G);break;case 5:AmendVertex(G);break;case 6:AmendArcCell(G);break;case 0:SaveG(G);break;default:printf("您的输入异常，请输入指定数字\n");break;}}while(choice);}

初始数据文件内容：

为了美观，重新更改VerTex.txt文件内容：

然后进行景点添加和路径添加：

结果截图：

再进行景点的删除测试：

删除景点6号时，会连同删除所有以景点6号为一端的路径：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-

可以看到，景点6号已经删除，与1号的路径也被删除。

提供showall(G)函数查看所有景点信息。

//查看所有景点信息void showall(MGraph G){int i;printf("\n\n\n");printf("编号 景点名称介绍\n");printf("------------------------------------------------------------------------------------------------------------------------\n");for(i=1;i<=G.vexnum;i++){printf("%-8d%-25s%-125s\n",G.vexs[i].id,G.vexs[i].name,G.vexs[i].intro);}printf("------------------------------------------------------------------------------------------------------------------------\n");}

结果截图：

4、旅游区景点显示

还可以编写shownow(G)函数，利用for循环得到相邻有路径的景点。

![1](F:\大学\数据结构课程设计\旅游区景点导游系统-C(初稿)\旅游区景点导游系统\1.png)//查看当前景点信息（结构相似）void shownow(mgraph k){int now;printf("您当前所在景点编号为：");scanf("%d",&now);if(now>=1&&now<=10){printf("\n\n\n");printf("您当前所在景点信息为：\n");printf("编号景点名称介绍\n");printf("%-5d%-20s%-125s\n",k.vexs[now].position,k.vexs[now].name,k.vexs[now].introduction);printf("您附近景点信息为：\n");int i;for(i=1;i<=k.vexnum;i++)if(k.arcs[now][i].adj<Infinity)printf("%-5d%-20s%-125s\n",k.vexs[i].position,k.vexs[i].name,k.vexs[i].introduction);}else{printf("您的输入异常！\n");}}

例如：

5、查询从每个景点出发到其他任一景点的最短简单路径及距离

查询任意两景点之间简单路径:

这个问题可以通过深度优先搜索（DFS）来解决。具体步骤如下：

1.定义一个visited数组，用于记录各个顶点是否已被访问。
2.定义一个path数组，用于记录从起点到终点的路径。
3.定义一个find_path变量，用于记录是否已找到一条路径。
4.从起点开始进行DFS搜索，每次访问一个未被访问的邻接点。
5.如果当前节点是终点，将path中的顶点打印出来，设置find_path为true，表示已找到一条路径。
6.如果当前节点不是终点，继续对它的邻接点进行DFS搜索。
7.如果已找到一条路径，直接返回；否则返回到上一层，尝试其他未被访问的邻接点。

函数PrintPath(G)将内容打印输出。

函数searchPath(G)将调用DFSPath(G)函数和PrintPath(G)函数，完成简单路径和距离的查询。

// DFS查找路径void DFSPath(MGraph G, int v, int w, Boolean visit[], PathStack &S, Boolean &found) {if (v == w) { // 找到终点found = TRUE;Push(S, v);return;}visit[v] = TRUE; // 标记已访问Push(S, v); // 入栈for (int i = 1; i <= G.vexnum; i++) {if (G.arcs[v][i].adj != Infinity && !visit[i]) { // 如果v和i之间有边且i未被访问DFSPath(G, i, w, visit, S, found); // 递归查找路径if (found) { // 如果找到了路径return;}}}Pop(S, &v); // 如果路径被阻断，则当前节点出栈visit[v] = FALSE; // 取消标记}// 打印栈中存储的路径void PrintPath(PathStack S, MGraph G) {printf("Path: ");while (!StackEmpty(S)) {int i;Pop(S, &i);printf("%s", G.vexs[i].name);if (!StackEmpty(S)) {printf(" -> ");}}printf("\n");}//查询任意两景点之间简单路径void searchPath(MGraph G) {int start, end;printf("Please input the start vertex id: ");scanf("%d", &start);printf("Please input the end vertex id: ");scanf("%d", &end);// 检查起点和终点是否合法if (LocateVex(G, start) == -1 || LocateVex(G, end) == -1) {printf("Invalid vertex id!\n");return;}// 初始化visited数组Boolean visit[MAX_VERTEX_NUM];for (int i = 1; i <= G.vexnum; i++) {visit[i] = FALSE;}// 初始化栈PathStack S;InitStack(S);// 查找路径Boolean found = FALSE;DFSPath(G, LocateVex(G, start), LocateVex(G, end), visit, S, found);if (found) {printf("Path found!\n");PrintPath(S, G);} else {printf("Path not found!\n");}// 清空栈ClearStack(S);}

下列是运行截图：

6、查询任意两个景点之间所有简单路径及距离、最短简单路径及距离

查询任意两景点之间最优路径:

这个问题可以通过Dijkstra算法来解决。具体步骤如下：

1. 初始化 final 数组和 ShortPathtable 数组，其中 final 数组表示已经加入最短路径的顶点集合，ShortPathtable 数组表示从起点 start 到每个顶点 v 的最短路径长度。
2. 将起点 start 标记为已经加入最短路径的顶点集合。
3. 循环遍历每个顶点，每次从未加入最短路径的顶点中选择距离起点最近的顶点 k，并将其标记为已经加入最短路径的顶点集合。
4. 针对每个未加入最短路径的顶点 w，若从起点 start 到顶点 k 再到顶点 w 的路径长度更小，则更新 ShortPathtable[w] 和 Patharc[w] 的值。
5. 输出从起点 start 到终点 end 的最短路径长度和路径信息，其中 Patharc[w] 表示从起点 start 到顶点 w 的最短路径经过的前一个顶点。

void searchShortestPath(MGraph G) {int start, end;printf("请输入起点编号：");scanf("%d", &start);printf("请输入终点编号：");scanf("%d", &end);//检查起点和终点是否合法if (start <= 0 || start > G.vexnum || end <= 0 || end > G.vexnum) {printf("无效的顶点id！\n");return;}int v, w, k, min;int final[MAX_VERTEX_NUM];int Patharc[MAX_VERTEX_NUM];int ShortPathtable[MAX_VERTEX_NUM];// 初始化 final 数组和 ShortPathtable 数组for (v = 1; v <= G.vexnum; v++) {final[v] = 0;ShortPathtable[v] = G.arcs[start][v].adj;Patharc[v] = start;}final[start] = 1; // 标记 start 已经加入到最短路径中for (v = 1; v <= G.vexnum; v++) {min = Infinity;for (w = 1; w <= G.vexnum; w++) {if (!final[w] && ShortPathtable[w] < min) {k = w;min = ShortPathtable[w];}}final[k] = 1; // 标记顶点 k 已经加入到最短路径中for (w = 1; w <= G.vexnum; w++) {if (!final[w] && (min + G.arcs[k][w].adj) < ShortPathtable[w]) {ShortPathtable[w] = min + G.arcs[k][w].adj;Patharc[w] = k;}}}// 输出最短路径信息printf("从景点%s到景点%s的最短路径长度为:%d，路径为：", G.vexs[start].name, G.vexs[end].name, ShortPathtable[end]);int path[MAX_VERTEX_NUM], i = 0;path[i++] = end;int p = Patharc[end];while (p != start) {path[i++] = p;p = Patharc[p];}path[i++] = start;while (i > 0) {printf("%s", G.vexs[path[--i]].name);if (i != 0) {printf("->");}}printf("\n");}void shortestPath_DIJ(MGraph G) {int v0, v, w, k, min;int final[MAX_VERTEX_NUM];int Patharc[MAX_VERTEX_NUM];int ShortPathtable[MAX_VERTEX_NUM];// 读入起始景点编号，若输入无效则要求重新输入printf("请输入一个起始景点的编号：");scanf("%d", &v0);while (v0 <= 0 || v0 > G.vexnum) {printf("您输入的景点编号不存在，请重新输入：");scanf("%d", &v0);}printf("\n");// 初始化 final 数组和 ShortPathtable 数组for (v = 1; v <= G.vexnum; v++) {final[v] = 0;ShortPathtable[v] = G.arcs[v0][v].adj;Patharc[v] = v0;}final[v0] = 1; // 标记 v0 已经加入到最短路径中for (v = 1; v < G.vexnum; v++) {min = Infinity;for (w = 1; w <= G.vexnum; w++) {if (!final[w] && ShortPathtable[w] < min) {k = w;min = ShortPathtable[w];}}final[k] = 1; // 标记顶点 k 已经加入到最短路径中for (w = 1; w <= G.vexnum; w++) {if (!final[w] && (min + G.arcs[k][w].adj) < ShortPathtable[w]) {ShortPathtable[w] = min + G.arcs[k][w].adj;Patharc[w] = k;}}}// 输出最短路径信息printf("最短路径如下：\n");for (v = 1; v <= G.vexnum; v++) {if (v != v0) {printf("%s到%s的最短路径长度为：%d，路径为：", G.vexs[v0].name,G.vexs[v].name, ShortPathtable[v]);printf("%s", G.vexs[v].name);w = v;while (Patharc[w] != v0) {printf("<--%s", G.vexs[Patharc[w]].name);w = Patharc[w];}printf("<--%s\n", G.vexs[v0].name);}}}

下列是运行截图：

7、最佳游览路线推荐

查询最佳游览路线:

贪心策略为：在当前路径栈中选取距离最近的未访问节点加入路径栈，直到所有节点都被访问过。

具体实现过程为：

1. 读入起点景点的编号，判断其是否合法。
2. 初始化visit数组，表示每个节点是否被访问过。
3. 初始化路径栈S和总距离totalDist，并将起点start入栈并标记已访问。
4. 循环遍历路径栈中的每个节点current，选择距离最近的未访问相邻节点加入路径栈，并将其标记为已访问，同时累加总距离。
5. 若所有相邻节点都已访问过，则将当前节点弹出路径栈。
6. 输出起点景点和最佳游览路线以及总距离。

该贪心策略的正确性基于贪心选择性质和最优子结构性质，即每次选择距离最近的相邻节点可以得到最优解，并且每次选择最优节点后剩余子问题仍然是最优的。

然而，该算法并不一定能够得到全局最优解，因为其每次只考虑了当前节点的相邻节点，而没有考虑更远的节点对路径的影响。因此，在实际应用中，可以采用其他算法来求解全局最优解，如动态规划或分支定界算法等。

// 查找最佳游览路线void findBestPath(MGraph G) {int start;printf("请输入起始景点：");scanf("%d",&start);if(start<=0||start>G.vexnum){printf("您输入的景点编号不存在！\n");scanf("%d",&start);}// 初始化visit数组int i, j;for (i = 1; i <= G.vexnum; i++) {visit[i] = FALSE;}// 初始化路径栈和总距离PathStack S;S.top = -1;int totalDist = 0;// 将起点入栈并标记已访问S.top++;S.data[S.top] = start;visit[start] = TRUE;// 当路径栈不为空时，循环遍历所有相邻节点，选择距离最近的节点加入路径栈while (S.top != -1) {int current = S.data[S.top];int minDist = Infinity;int next = -1;for (i = 1; i <= G.vexnum; i++) {if (G.arcs[current][i].adj < minDist && !visit[i]) {minDist = G.arcs[current][i].adj;next = i;}}// 若找到了未访问过的相邻节点，则将其入栈并标记已访问，同时累加总距离if (next != -1) {S.top++;S.data[S.top] = next;visit[next] = TRUE;totalDist += G.arcs[current][next].adj;} else {// 若所有相邻节点都已访问过，则将栈顶节点弹出S.top--;}}// 打印起点景点和最佳游览路线以及总距离printf("最佳游览路线为：%s->",G.vexs[start].name);for (i = 1; i <= G.vexnum; i++) {printf("%s", G.vexs[S.data[i]].name);if (i < G.vexnum-1) {printf("->");}}printf("\n");printf("总距离为：%d\n", totalDist);}

下列是运行截图：

8、设计总结

设计时遇到的问题

数据文件的存储和读取

最开始时，并未决定采取文件数据存储和读取。而是选择在缓存内加载图数据。

mgraph campus;//图变量（大学校园）int d[20];int visited[20];int shortest[MaxVertexNum][MaxVertexNum]; //定义全局变量存储最小路径int pathh[MaxVertexNum][MaxVertexNum];//定义存储路径mgraph initgraph(){int i=0,j=0;mgraph k;k.vexnum=10;//10个顶点k.arcnum=18;//18条边for(i=1;i<=k.vexnum;i++)//设置顶点编号k.vexs[i].position=i;strcpy(k.vexs[1].name,"恒大楼\0");strcpy(k.vexs[1].introduction,"武汉科技大学恒大楼原名教一楼，位于武汉科技大学黄家湖校区，是武汉科技大学的主教学楼，分三个教学区域。2017年6月，恒大集团赞助并冠名，教一楼更名为恒大楼。\0");strcpy(k.vexs[2].name,"教三楼\0");strcpy(k.vexs[2].introduction,"教三楼是武汉科技大学计算机学院的教学楼，计算机学院是武汉科技大学的王牌专业之一，里面的学生都勤奋好学。\0");strcpy(k.vexs[3].name,"南苑食堂\0");strcpy(k.vexs[3].introduction,"武汉科技大学南苑食堂是武汉科技大学两个食堂中的一个，略逊于北苑食堂，排在武汉科技大学食堂第二位。\0");strcpy(k.vexs[4].name,"南苑操场\0");strcpy(k.vexs[4].introduction,"武汉科技大学南苑操场是住在南苑所有学子的运动圣地，篮球、足球、乒乓球，这里什么都有！\0");strcpy(k.vexs[5].name,"图书馆\0");strcpy(k.vexs[5].introduction,"武汉科技大学图书馆是武汉科技大学学子向更高的学府冲击的天梯，这里不仅有书，还有所有学生的梦想。\0");strcpy(k.vexs[6].name,"沁湖\0");strcpy(k.vexs[6].introduction,"沁湖是武汉科技大学黄家湖校区的绝美自然风景，鸟语花香，树木丛生。\0");strcpy(k.vexs[7].name,"北苑食堂\0");strcpy(k.vexs[7].introduction,"武汉科技大学北苑食堂排名武汉科技大学食堂第一位，无论是味道，还是环境，通通碾压南苑食堂。究其原因，可能是北苑住的女同学更多，所以质量更高吧。\0");strcpy(k.vexs[8].name,"梅园\0");strcpy(k.vexs[8].introduction,"梅园，仿造武汉大学梅园而成，环境优美，意境通达。\0");strcpy(k.vexs[9].name,"北四宿舍\0");strcpy(k.vexs[9].introduction,"北四宿舍，可能有大量女同学出没。\0");strcpy(k.vexs[10].name,"校医院\0");strcpy(k.vexs[10].introduction,"校医院，没怎么去过，应该有很多医学院专业的同学在这里出没。\0");for(i=1;i<=k.vexnum;i++)for(j=1;j<k.vexnum;j++)k.arcs[i][j].adj=Infinity;//初始化图的邻接矩阵k.arcs[1][2].adj=20;k.arcs[1][3].adj=30;k.arcs[1][8].adj=45;k.arcs[1][10].adj=42;k.arcs[2][3].adj=15;k.arcs[2][5].adj=40;k.arcs[2][8].adj=45;k.arcs[3][4].adj=40;k.arcs[4][5].adj=37;k.arcs[5][6].adj=38;k.arcs[5][8].adj=40;k.arcs[6][7].adj=32;k.arcs[6][8].adj=43;k.arcs[7][8].adj=45;k.arcs[8][9].adj=30;k.arcs[8][10].adj=43;k.arcs[9][10].adj=48;for(i=1;i<=k.vexnum;i++)for(j=1;j<=k.vexnum;j++)k.arcs[j][i].adj=k.arcs[i][j].adj; //是无向图，所以对称赋值return k;}//initgraph

这是第一次的代码。后来发现需要用到文件存储，故全部推倒，开始第二次编程。

第二次参考Bo7-1.cpp的算法，用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图G。

Status CreateFAG(MGraph &G){//采用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图Gint i,j,k;char filename[20];VertexType va,vb;FILE *graphlist;printf("请输入数据文件名:");scanf("%s",filename);graphlist= fopen(filename,"r");fscanf(graphlist,"%d",&G.vexnum);fscanf(graphlist,"%d",&G.arcnum);for(i=0;i<G.vexnum;++i) //构造顶点向量fscanf(graphlist,"%s",G.vexs[i]);for(i=0;i<G.vexnum;++i) //初始化邻接矩阵for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj=0; //图G.arcs[i][j].info=NULL; //无相关信息}for(k=0;k<G.arcnum;++k){fscanf(graphlist,"%s%s",va,vb);i=LocateVex(G,va);j=LocateVex(G,vb);G.arcs[i][j].adj=G.arcs[j][i].adj=1;//无向图}fclose(graphlist);G.kind=AG;return OK;}

但是中途发现此方法不便于实现图对文件数据的读取，故再次推倒，进入最后一次编程，既第二部分的读文件创建图。

编辑景点信息时，容易造成文件损坏和数据丢失

编写AddVertex(G)、DeleteVertex(G)、AmendVertex(G)、AddArcCell(G)、DeleteArcCell(G)、AmendArcCell(G)六个函数时，发现VerTex.txt和ArcCell.txt内的数据会异常清零。

原VerTex.txt内容：

5
A 1 AAAA
B 2 BBB
C 3 CCCCC
D 4 DD
E 5 EEE

运行函数后：
5
A 1 AAAA
B 2 BBB
C 3 CCCCC
D 4 DD

ArcCell.txt内数据也类似。

后续发现问题所在：

int LocateVex(MGraph G,int u){ // 初始条件:图G存在,u和G中顶点有相同特征 // 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1int i;for(i=0;i<G.vexnum;++i)if(u==G.vexs[i].id)return i;return -1;}

LocateVex函数第五行for函数的作用域是从0号景点到4号景点，而原图内的景点编号从1开始，储存在1到5中。

改进为：

int LocateVex(MGraph G,int u){ // 初始条件:图G存在,u和G中顶点有相同特征 // 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1int i;for(i=1;i<=G.vexnum;++i)if(u==G.vexs[i].id)return i;return -1;}

现有问题

findBestPath()的缺陷

此函数并不允许经过同一个景点，故对于某些不流通的景点，无法遍历所有景点的同时，又不能重复浏览同一个景点，故造成死循环。且该函数使用的贪心算法并不一定能够得到全局最优解，因为其每次只考虑了当前节点的相邻节点，而没有考虑更远的节点对路径的影响。因此，在实际应用中，可以采用其他算法来求解全局最优解，如动态规划或分支定界算法等。

收获与感想

C 文件读写

C 语言不仅提供了访问顶层的函数，也提供了底层（OS）调用来处理存储设备上的文件。从这次项目中，自己从各大网站和平台逐层学到了关于文件读写的几大函数。

fopen()函数和fclose()函数

用 **fopen()函数创建一个新的文件或者打开一个已有的文件，这个调用会初始化类型 FILE 的一个对象，类型 FILE 包含了所有用来控制流的必要的信息。下面是这个函数调用的原型：

FILE *fopen( const char *filename, const char *mode );

用fclose()关闭文件。函数的原型如下：

int fclose( FILE *fp );

如果成功关闭文件，fclose( ) 函数返回零，如果关闭文件时发生错误，函数返回 EOF。这个函数实际上，会清空缓冲区中的数据，关闭文件，并释放用于该文件的所有内存。EOF 是一个定义在头文件 stdio.h 中的常量。

fprintf ()函数和fscanf()函数

fprintf(FILE *fp,const char *format, …) 函数把一个字符串写入到文件中。

fscanf(FILE *fp, const char *format, …) 函数来从文件中读取字符串，但是在遇到第一个空格和换行符时，它会停止读取。

typedef用法

typedef是C语言中的一个关键字，用于给一个已经存在的数据类型或结构体类型取一个新的名字。typedef通常用于简化代码、提高代码可读性、以及使代码更易于维护。

1.为已有数据类型取一个新的名字

typedef unsigned int uint;

上述代码定义了一个新的类型uint，其实际上是unsigned int类型的别名。这样，以后我们在代码中使用uint时，就等价于使用unsigned int。

2.为已有结构体类型取一个新的名字

typedef struct person {char name[20];int age;} Person;

上述代码定义了一个结构体类型person，并且通过typedef将其重命名为Person。这样，在代码中使用Person时，就等价于使用struct person。

3.为指针类型取一个新的名字

typedef char* String;

上述代码定义了一个新的类型String，其实际上是char* 类型的别名。这样，以后我们在代码中使用String时，就等价于使用char*。

4.定义函数指针类型

typedef int (*compare_func)(const void*, const void*);

上述代码定义了一个新的类型compare_func，其实际上是一个指向函数的指针类型。该函数接受两个const void* 类型的参数，返回一个int类型的值。这样，以后我们在代码中使用compare_func时，就等价于使用该函数指针类型。

总之，typedef可以用来给任何已有类型或结构体类型定义一个新的别名，这样就可以方便地使用这些类型。
st char *format, …)** 函数把一个字符串写入到文件中。

fscanf(FILE *fp, const char *format, …) 函数来从文件中读取字符串，但是在遇到第一个空格和换行符时，它会停止读取。

typedef用法

typedef是C语言中的一个关键字，用于给一个已经存在的数据类型或结构体类型取一个新的名字。typedef通常用于简化代码、提高代码可读性、以及使代码更易于维护。

1.为已有数据类型取一个新的名字

typedef unsigned int uint;

上述代码定义了一个新的类型uint，其实际上是unsigned int类型的别名。这样，以后我们在代码中使用uint时，就等价于使用unsigned int。

2.为已有结构体类型取一个新的名字

typedef struct person {char name[20];int age;} Person;

上述代码定义了一个结构体类型person，并且通过typedef将其重命名为Person。这样，在代码中使用Person时，就等价于使用struct person。

3.为指针类型取一个新的名字

typedef char* String;

上述代码定义了一个新的类型String，其实际上是char* 类型的别名。这样，以后我们在代码中使用String时，就等价于使用char*。

4.定义函数指针类型

typedef int (*compare_func)(const void*, const void*);

上述代码定义了一个新的类型compare_func，其实际上是一个指向函数的指针类型。该函数接受两个const void* 类型的参数，返回一个int类型的值。这样，以后我们在代码中使用compare_func时，就等价于使用该函数指针类型。

总之，typedef可以用来给任何已有类型或结构体类型定义一个新的别名，这样就可以方便地使用这些类型。