创建景点后,检测效果图 路径全替换为最大值,游客界面也无法查询线路,求指导一下谢谢
源代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MaxSize 100
#define Max 32767
//////////////////////邻接表
typedef struct ArcNode
{
int adjvex;
int info; ///////标志是否被访问过
int weight;
struct ArcNode *nextarc;
}ANode;
typedef struct
{
int info; ///////标志是否被访问过
char name[50];
ANode *firstarc;
}VNode, AdjList[MaxSize];
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
////////////////////////邻接矩阵
typedef struct
{
int weight;
int info; ///////0,表示无路径,1表示有路径
} AdjMatrix[MaxSize][MaxSize];
typedef struct
{
char names[MaxSize][50];
AdjMatrix arcs;
int vexnum, arcnum;
}MGrph;
//////////////////////////////最短路径结点
typedef struct
{
int info;
int weight;
}MinW;
///////////////////////////拓扑排序用栈
typedef struct
{
VNode *Topo[MaxSize];
int top;
}TP;
//////////////////深度遍历生成树
typedef struct csnode
{
int num;
struct csnode *firstchild, *nextsibling;
}csnode, *cstree;
int visited[MaxSize];
////////////////////////函数部分
void Create(ALGraph *tu)//建立邻接链表
{
int i;
int shi, zhong, weight;
ANode *p;
printf("请输入景点数:");
scanf("%d", &tu->vexnum);
printf("请输入道路数:");
scanf("%d", &tu->arcnum);
for (i = 0; i<tu->vexnum; i++)
{
printf("请输入第个%d景点名:", i + 1);
scanf("%s", tu->vertices[i].name);
tu->vertices[i].firstarc = NULL;
}
for (i = 0; i<tu->arcnum; i++)
{
printf("请选择输入路径,形如(1 3)(从景点一到景点三):");//一条路径的起点和终点
scanf("%d%d", &shi, &zhong);
printf("请输入该条路径的长度:");
scanf("%d", &weight);
p = (ANode *)malloc(sizeof(ANode));
p->adjvex = zhong;
p->weight = weight;
p->nextarc = tu->vertices[shi].firstarc;
tu->vertices[shi].firstarc = p;
p = (ANode *)malloc(sizeof(ANode));
p->adjvex = shi;
p->weight = weight;
p->nextarc = tu->vertices[zhong].firstarc;
tu->vertices[zhong].firstarc = p;
}
printf("创建完成!\n");
}
void Rclear(MGrph *Ttu)//初始化邻接矩阵,(路径数与景点数已知)将矩阵路径长度初始化为Max,标志位初始化为0
{
int i, j;
for (i = 0; i<Ttu->vexnum; i++)
for (j = 0; j<Ttu->vexnum; j++)
{
Ttu->arcs[i][j].weight = Max;
Ttu->arcs[i][j].info = 0;
}
}
void Turn(ALGraph *tu, MGrph *Ttu)//将邻接链表转换成邻接矩阵
{
int i, j;
ANode *p;
Ttu->arcnum = tu->arcnum;
Ttu->vexnum = tu->vexnum;
Rclear(Ttu);
for (i = 0; i<Ttu->vexnum; i++)
strcpy(Ttu->names[i], tu->vertices[i].name);
for (j = 0; j<tu->vexnum; j++)
{
p = tu->vertices[j].firstarc;
while (p != NULL)
{
Ttu->arcs[j][p->adjvex].weight = p->weight;
Ttu->arcs[j][p->adjvex].info = 1;
p = p->nextarc;
}
}
/* for(i=0;i<tu->vexnum;i++)
{
for(j=0;j<tu->vexnum;j++)
printf("%d\t",Ttu->arcs[i][j].weight);
printf("\n");
}*/
for (i = 0; i <= tu->vexnum; i++)
{
for (j = 0; j <= tu->vexnum; j++)
{
if (i == 0 && j == 0)
{
printf("\t");
}
if (i == 0)
{
if (j != 0)
{
printf("景点%s\t", tu->vertices[j - 1].name);
}
}
else
{
if (j == 0)
{
printf("景点%s\t", tu->vertices[i - 1].name);
}
else
printf("%d\t", Ttu->arcs[i - 1][j - 1].weight);
}
}printf("\n");
}
}
void Rset(ALGraph *tu)//将邻接表中结点的标志以及边的标志初始化为0(路径数与景点数已知)
{
int i, j;
ANode *p;
for (i = 0; i<tu->vexnum; i++)
tu->vertices[i].info = 0;
for (j = 0; j<tu->vexnum; j++)
{
p = tu->vertices[j].firstarc;
while (p != NULL)
{
p->info = 0;
p = p->nextarc;
}
}
}
void Rbuild(ALGraph *tu)//景点规划(最小生成树)
{
int n, i, j, Min;
ANode *p, *qin;
MGrph GG;
GG.arcnum = 0;
GG.vexnum = 0;
int min[MaxSize];
ALGraph *MinTree;
MinTree = (ALGraph *)malloc(sizeof(ALGraph));
MinTree->vexnum = tu->vexnum;
MinTree->arcnum = tu->vexnum - 1;
Rset(tu);
for (i = 0; i<tu->vexnum; i++)
{
min[i] = Max;
strcpy(MinTree->vertices[i].name, tu->vertices[i].name);
MinTree->vertices[i].firstarc = NULL;
}
printf("请选择做为入口的景点标号(1— %d):", tu->vexnum);
scanf("%d", &n);
for (i = 0; i<tu->vexnum; i++)
{
tu->vertices[n - 1].info = 1;
Min = Max;
p = tu->vertices[n - 1].firstarc;
while (p != NULL)
{
if (min[p->adjvex]>p->weight)
{
min[p->adjvex] = p->weight;
qin = (ANode *)malloc(sizeof(ANode));
qin->adjvex = n - 1;
qin->weight = p->weight;
qin->nextarc = NULL;
MinTree->vertices[p->adjvex].firstarc = qin;
}
p = p->nextarc;
}
for (j = 0; j<tu->vexnum; j++)
if (Min>min[j] && (tu->vertices[j].info != 1))
{
Min = min[j];
n = j + 1;
}
}
Turn(MinTree, &GG);
}
void DFSTree(ALGraph *tu, int v, cstree &T)
{
int first, w = -1;
ANode *d;
d = NULL;
cstree p, q;
visited[v] = 1;
first = 1;
T->num = v;
if (tu->vertices[v].firstarc)
d = tu->vertices[v].firstarc;
for (; d; d = d->nextarc)
{
w = d->adjvex;
if (!visited[w])
{
p = (cstree)malloc(sizeof(csnode));
p->num = w;
p->firstchild = NULL;
p->nextsibling = NULL;
if (first)
{
T->firstchild = p;
first = 0;
}
else
q->nextsibling = p;
q = p;
DFSTree(tu, w, q);
}
}
}
int Gshow(cstree T, int &f)
{
if (T)
{
printf("%d\n", T->num);
if (T->nextsibling)
{
printf("有回路,下面进入人工选择!");
f = 1;
return 0;
}
else if (T->firstchild)
Gshow(T->firstchild, f);
}
return 1;
}
void minway(MGrph *Ttu)
{
MinW min[MaxSize];
int flags[MaxSize];
int i, mi, n, j, pre;
printf("请输入您当前所在景点位置标号:\n");
scanf("%d", &n);
for (i = 0; i<Ttu->vexnum; i++)
{
flags[i] = 0;
min[i].info = n;
min[i].weight = Ttu->arcs[n][i].weight;
}
flags[n] = 1;
int k = n;
for (i = 1; i<Ttu->vexnum; i++)
{
mi = Max;
for (j = 0; j<Ttu->vexnum; j++)
if (flags[j] == 0 && mi>min[j].weight)
{
mi = min[j].weight;
pre = j;
}
min[pre].info = k;
flags[pre] = 1;
k = pre;
for (j = 0; j<Ttu->vexnum; j++)
if (flags[j] == 0 && (min[pre].weight + Ttu->arcs[pre][j].weight<min[j].weight))
{
min[j].weight = min[pre].weight + Ttu->arcs[pre][j].weight;
min[j].info = pre;
}
}
printf("请输入目标位置:\n");
scanf("%d", &n);
printf("您距离目标%d,您将由%d位置走向目标。\n", min[n].weight, min[n].info);
}
void Guide(ALGraph *tu, MGrph *Ttu)
{
int n;
int f = 0;
cstree T;
T = (cstree)malloc(sizeof(csnode));
T->firstchild = NULL;
T->nextsibling = NULL;
Rset(tu);
printf("请选择您所在景点(1 — %d):", tu->vexnum);
scanf("%d", &n);
DFSTree(tu, n - 1, T);
Gshow(T, f);
if (f == 1)
minway(Ttu);
}
void main()
{
ALGraph G;
MGrph TG;
int f = 0;
int key = 0;
int ch;
G.arcnum = 0;
G.vexnum = 0;
TG.arcnum = 0;
TG.vexnum = 0;
while (key != 3)
{
f = 0;
printf("→→→欢迎进入旅游管理系统\n");
printf(" ↓↓↓ 请确认身份\n");
printf("1 → 管理员\n");
printf("2 → 游客\n");
printf("3 → 退出\n");
scanf("%d", &key);
if (key>3 || key<1)
{
printf("错误选项!\n");
continue;
}
while (f == 0 && key == 1)
{
printf(" 管理系统为您服务!\n");
printf(" ☆ 请选择(1-4):\n");
printf("1 创建景点分布图\n");
printf("2 检测创建效果图\n");
printf("3 最低造价路线图\n");
printf("4 退出→管理系统\n");
scanf("%d", &ch);
switch (ch)
{
case 1:Create(&G); break;
case 2:Turn(&G, &TG); break;
case 3:Rbuild(&G); break;
case 4:f = 1; break;
default:printf("错误选项!请重新选择!\n"); break;
}
}
while (f == 0 && key == 2)
{
printf("机器人乐乐为您服务:\n");
printf(" ^ ^\n");
printf("1线路 0 0 导游\n");
printf(" 6\n");
printf("2捷径 + + 引领\n");
printf("3→退出导游系统\n");
scanf("%d", &ch);
switch (ch)
{
case 1:Guide(&G, &TG); break;
case 2:minway(&TG); break;
case 3:f = 1; break;
default:printf("错误选项!请重新选择!\n"); break;
}
}
}
}