多于话就不说了，因为这个项目是紧接着huffman编码解码器的，是这次实习的第二个题目。今天是我们实习的最后一天，我也刚刚通过了老师的检查与答辩，一切都很顺利。
经过这次实习，我似乎觉得开发也没有那么难。以前总觉得编码很难，一向对自己要求比较严格又追求十全十美的我，总是不爱动手编程。后来渐渐的离编程也越来越远，朝着另外一个方向发展。但是作为一个IT人员，不会编程应该是一件很可笑的事情。所以接下来还是要加强一下自己的动手编程能力，下学期开学去报一个C语言培训班，我同学去过了，听说效果不错。现在姑且这样计划着吧！下面是校园导游系统。
实现功能：1,从文件读入景点信息道路信息，然后用邻接表建立校园图，用邻接矩阵存放边的信息。
2,查看景点信息，道路信息。
3,查找两点之间最短路径，采用弗洛依德算法。
4,采用深度优先递归调用的方法遍利图。
程序代码：
//***********************************
// 程序名称:校园导游系统
// 作者:陈 翔
// 时间:2009-06-05
//***********************************
#define MAX 20 //图中顶点数的最大值
#define MAXedg 30 //图中边数的最大值
#include
#include
#include
#include
typedef struct edgenode
{
int adjvex; //临接点序号
int length; //道路长度
char info[20]; //景点名称
char info2[100]; //景点详细信息
struct edgenode *next;
}edgenode, *Node ;
typedef struct
{
char data[20]; //存储景点的名称.
char str[100]; //具体的介绍此景点
struct edgenode *link; //指向下一个景点
}vexnode; //景点及其信息.
typedef struct Edge
{
int lengh; //边的权值，表示路径长度.
int ivex, jvex; //边的两端顶点号
struct Edge *next; //指向下一条边
} EdgeType;
//边及其信息.
typedef struct
{
int num; //顶点编号,没有使用。
char data[20]; //顶点名称
} vertex;
typedef struct
{
vertex vexs[MAX]; //顶点集合
int edges[MAX][MAX]; //临街矩阵
}adjmax; //adj
FILE *fp; //文件的读取
void clrscr() //清屏
{
system("cls");
}
void creatgraph(vexnode g[],int *n, EdgeType e[],adjmax *adj) //创建校园图
{
int b,i,j,s,d,len;
struct edgenode *p,*q; //定义图的结构体
if((fp = fopen("file.txt","r")) == NULL) //打开文件
{
printf("文件打开错误！\n");
getchar();
exit(0);
}
fscanf(fp,"%d %d\n",n,&b); //读入景点个数和边数
for(i = 1; i <= *n; i++) //读入景点名称和详细介绍信息
{
fscanf(fp,"%s %s\n",&g[i].data,&g[i].str);
strcpy(adj->vexs[i].data,g[i].data);
g[i].link = NULL; //初始化
}
for(i = 1; i <= *n; i++) //为邻接矩阵中的权值赋初值1000
{
for(j = 1; j <= *n; j++)
{
adj->edges[i][j] = 1000; //初始值为1000，所以在佛洛依德算法中就没定义最大值！
}
}
for(i = 1; i <= b; i++) //输入道路信息
{
fscanf(fp,"%d %d %d\n",&e[i].lengh,&e[i].ivex,&e[i].jvex); //读入道路长度和起始点
s = e[i].ivex; //s是起点，d是终点。
d = e[i].jvex;
len = e[i].lengh;
adj->edges[s][d] = e[i].lengh; //为邻接矩阵中相应的边赋值
adj->edges[d][s] = e[i].lengh;
p = (Node)malloc(sizeof(edgenode)); //申请一个弧节点。
p->next = NULL;
q = (Node)malloc(sizeof(edgenode));
q->next = NULL;
p->adjvex = d; // 弧p指向的定点
p->length = len;
strcpy(p->info,g[d].data); //为景点赋名称
strcpy(p->info2,g[d].str); //为景点赋介绍信息
q->adjvex = s; // 弧q指向的定点
q->length = len;
strcpy(q->info,g[s].data); //为景点赋名称
strcpy(q->info2,g[s].str); //为景点赋介绍信息
p->next = g[s].link; //头插法建立邻接表
g[s].link = p;
q->next = g[d].link;
g[d].link = q;
}
printf("恭喜你，校园旅游图已经建立！\n");
getchar();
}
void travgraph(vexnode g[],int n,adjmax adj) //查找指定景点信息
{
int i = 1,flag = 1,len; //len存储要查询的景点的序号
char ch;
edgenode *p;
printf("请输入您要查询的景点序号:\n");
scanf("%d",&len);
getchar();
while(i <= n) //遍历邻接表
{
p = g[i].link;
if(i == len && flag == 1)
{
printf("此景点的名称是: %s\n",g[i].data);
printf("此景点的介绍是: %s\n",g[i].str);
printf("是否继续? Y/N");
scanf("%c",&ch);
getchar();
if(ch == 'Y' || ch == 'y') //继续
{
flag = 1;
i = 1;
printf("请输入您要查询的景点序号:\n");
scanf("%d",&len);
getchar();
}
else
flag = 0; //不继续了
}
else
i++;
}
}
void Find_way(vexnode g[],EdgeType e[]) //查询道路信息
{
int i; //要查询的道路序号
char ch = 'a'; //继续与否
do
{
printf("请输入您要查询的道路序号:\n");
scanf("%d",&i);
getchar();
printf("此道路长度是:%d米\n",e[i].lengh);
printf("此道路连接的两个景点是:%s—%s\n",g[e[i].ivex].data,g[e[i].jvex].data);
printf("是否要继续查询(Y/N)?\n");
scanf("%c",&ch);
} while(ch == 'Y' || ch == 'y');
}
void Ppath(int path[][MAX],int i,int j,vexnode g[]) //
{
int k;
k = path[i][j]; //记录最后一次最短路径的节点数
if(k == -1)
return;
Ppath(path,i,k,g); //依次向前一个最短路径节点递推
printf("%s,",g[k].data);
Ppath(path,k,j,g); //依次向前一个最短路径节点递推
}
void Dispath(int A[][MAX],int path[][MAX],int n,vexnode g[])
{
int i,j;
int a,b; //a：起始景点序号，b：终止景点序号。
printf("请输入您要查询的起始景点和终止景点序号（逗号隔开）:\n");
scanf("%d,%d",&a,&b);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
if(A[i][j] != 1000 && A[i][j] != 0 && i == a && j == b)
{
printf("从%s到%s最短路径顺序为: ",g[a].data,g[b].data);
printf("%s,",g[a].data);
Ppath(path,a,b,g);
printf("%s",g[b].data);
printf("\n路径长度为: %d\n",A[i][j]);
}
}
}
void Floyd(adjmax adj,int n,vexnode g[]) //计算所有两个景点间最短路径
{
int A[MAX][MAX],path[MAX][MAX]; //A是路径长度，path是路径。
int i,j,k;
for(i = 1; i <= n; i++) //初始化
for(j = 1; j <= n; j++)
{
A[i][j] = adj.edges[i][j]; //i j之间长度
if(i == j)
{
A[i][j] = 0;
}
path[i][j] = -1; //初始化
}
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
if(A[i][j] > (A[i][k] + A[k][j]))
{
A[i][j] = A[i][k]+A[k][j]; //修改最短路径长度值
path[i][j] = k; //将最短路径的节点号保存
}
}
Dispath(A,path,n,g); //用户输入，查找任意两个景点间的最短路径。
}
void Deep_Find_View(vexnode g[],int v,int n,int visted[]) //深度优先递归调用遍历,v起始顶点。
{
edgenode *p;
int flag = 0;
if(flag == 0 && visted[v] == 0)
{
printf("%s",g[v].data);
flag = 1;
visted[v] = 1;
}
p = g[v].link;
while(p != NULL)
{
if(visted[p->adjvex] == 0) //未被访问，则访问。
{
printf("—%s",p->info);
visted[p->adjvex] = 1;
Deep_Find_View(g,p->adjvex,n,visted); //递归调用
}
p = p->next;
}
}
void bianli(int n,vexnode g[]) //深度递归遍历，找出参观全部景点的最佳路线。
{
int i,v;
int visted[MAX]; //访问标志数组
for(i = 1; i <= n; i++)
{
visted[i] = 0; //为visited[]数组赋初值,0表示没访问。
}
printf("请输入起始景点:\n");
scanf("%d",&v);
printf("The route is: ");
Deep_Find_View(g,v,n,visted);
}
int main()
{
int n = 0; //景点数目
vexnode g[MAX]; //保存顶点及其信息
EdgeType e[MAXedg]; //保存边及其信息
adjmax adj; //保存边和定点
char choice = 'x';
while(1)
{
clrscr();
printf("\n\n\t\t\t***校园导游系统***");
printf("\n\t\t*************************************\n\n");
printf("\t\t\t1. 文件读入并创建校园图:\n\n");
printf("\t\t\t2. 查询景点详细信息:\n\n");
printf("\t\t\t3. 查询道路详细信息:\n\n");
printf("\t\t\t4. 查找两景点间最短路径:\n\n");
printf("\t\t\t5. 查找最佳参观路线:\n\n");
printf("\t\t\t0. 退出\n\n");
printf("\t\t\tWrite By ");
printf("\n\t\t************************************\n\n");
printf("Please enter your choice(0-5):\n ");
choice = getchar();
switch(choice)
{
case '1':
clrscr();
creatgraph(g,&n,e,&adj); //创建图(景点，景点数，边，边和景点)
printf("\n*******按任意键返回********\n");
getchar();
break;
case '2':
clrscr();
travgraph(g,n,adj); //查找指定景点信息（景点，景点数，边和景点）
printf("\n*******按任意键返回********\n");
getchar();
break;
case '3':
clrscr();
Find_way(g,e); //查询道路信息（景点，边）
printf("\n*******按任意键返回********\n");
getchar();
break;
case '4':
clrscr();
Floyd(adj,n,g); //查找两个景点间最短路径（边和景点，景点数，景点）
getchar();
printf("\n*******按任意键返回********\n");
getchar();
break;
case '5':
clrscr();
bianli(n,g); //找出参观全部景点的最佳路线
getchar();
printf("\n");
printf("\n*******按任意键返回********\n");
getchar();
break;
case '0':
clrscr();
printf("\n*******按任意键退出********\n");
getchar();
exit(0);
break;
default:
printf("\n输入错误,请重新输入:\n");
getchar();
break;
}
}
return 0;
}
