西安旅游查询系统数据结构.docx
《西安旅游查询系统数据结构.docx》由会员分享，可在线阅读，更多相关《西安旅游查询系统数据结构.docx（33页珍藏版）》请在冰点文库上搜索。
西安旅游查询系统数据结构
/*-----------------------用邻接链表建立图----------------------------*/
#include
#include
#include
#include
#include
#include
#defineINFINITY32768
#defineMAX_VERTEX_NUM20//最大定点数
#defineERROR0
#defineTRUE1
#defineM50
#defineLEN50
#defineMAX10000//文件的最大容量
/*------------------------------------邻接链表的参数----------------------------------------*/
typedefcharVertexData;//顶点类型
typedeffloatAdjType;//边得权值不晓得
typedefcharOtherInfo;//边的其他类型不晓得
typedefenum{DG,DN,UDG,UDN}GraphKind;//图的枚举
typedefstructArcNode
{
intadjvex;//所在数组中位置
AdjTypeadj;//边的权值
OtherInfoinfo;//边的其他类型
structArcNode*nextarc;//下一个邻接点
}ArcNode;
typedefstructVertexNode
{
VertexDatavertexdata[M];//顶点数据
charfilename[LEN];//顶点的文件名
ArcNode*firstarc;//顶点的第一个邻接点
}VertexNode;
typedefstruct
{
VertexNodevertex[MAX_VERTEX_NUM];//顶点数组信息
intvernum,arcnum;//顶点数边数
GraphKindkind;//图的种类
}AdjList;
/*-----------------------------------------对的参数---------------------------------------------*/
typedefstructQnode
{
intdata;
structQnode*next;
}LinkQueueNode;
typedefstruct
{
LinkQueueNode*rear;
LinkQueueNode*front;
}LinkQueue;
/*-----------------------------------------栈的参数---------------------------------------------*/
typedefstructnode
{
intdata;
structnode*next;
}LinkList;
voidMenu（）;//菜单函数
voidStart（）;//开始函数
voidPlane_Graph（）;//平面图
//图的函数
voidAll_Scenic（AdjList*G）;//所有景点名称
intLocateVex（AdjList*G,charv[M]）;//确定元素v所在下表
voidCreatDN_Num_N（AdjList*G）;//初始化表（不追加）
AdjList*CreatDN_Num_Y（AdjList*G）;//初始化表（追加）
voidCreatDN（AdjList*G）;//建表（图）
voidPrint_DN（AdjList*G）;//输出图
intFirstAdjVertex（AdjList*G,intv）;//寻找以v为下标的节点的第一个有效邻接点
intNextAdjVertex（AdjList*G,intv,intw）;//下一个有效邻接点
voidVisitVertex（AdjList*G,intv）;//访问以v为下标的节点
voidOne_Adj（AdjList*G,floatweight）;//建立两个节点间关系
voidSearch_Good（）;//两点间最优路径
voidAll_Good（）;//一点到其他点的最优路径
voidBreadth_first_Search（AdjList*G,intv1,intpre[M]）;//广度优先搜索最佳路径（中专次数最少）
voidPrint_Path（AdjList*G,intv1,intv2,intpre[M]）;//打印最佳路径
voidShortest_Path（）;//最短路径
//对的函数
voidInitQueue（LinkQueue*Q）;//初始化对
intIsEmpty（LinkQueue*Q）;//判断对是否为空
voidGetTopQueue（LinkQueue*Q,int*data）;//得到对头
intDeletQueue（LinkQueue*Q,int*data）;//删掉对头
intEnterQueue（LinkQueue*Q,intdata）;//进队
//栈的相关函数
voidPush（LinkList*L,intm）;//头插法进栈
voidPop（LinkList*L,int*m）;//头删栈
//文件的相关函数
voidCreat_file（）;//将邻接表创建为文件
AdjList*Creat_Link（）;//将文件转化为链表
voidRead_inf（）;//读文件
//voidAdd_file（）;//追加文件信息
voidCreat_Scenic（AdjList*G）;//建立景点信息（简介）
voidPrint_Scenic（AdjList*G）;//景点描述
//---------------------------文件的相关函数----------------------
voidCreat_file（）//将邻接表创建为文件
{
FILE*fp;
inti;
intt;
charfilename[LEN];
charm;
ArcNode*p;
AdjList*G;
G=（AdjList*）malloc（sizeof（AdjList））;
printf（"请输入关于旅游信息的文件名（建议a.txt）：
"）;
flushall（）;
gets（filename）;
//fp=fopen（filename,"wt"）;
printf（"\n是否追加文件（n键否定，其他任意键为追加文件）"）;
flushall（）;
scanf（"%c",&m）;
if（m=='n'||m=='N'）
{
fp=fopen（filename,"wt"）;
if（fp==NULL）
{
printf（"\n输入文件名错误，按任意键重新输入"）;
getch（）;
system（"cls"）;
Creat_file（G）;
}
system（"cls"）;
CreatDN_Num_N（G）;
}
else
{
G=CreatDN_Num_Y（G）;
fp=fopen（filename,"wt"）;
if（fp==NULL）
{
printf（"\n输入文件名错误，按任意键重新输入"）;
getch（）;
system（"cls"）;
Creat_file（G）;
}
}
CreatDN（G）;
for（i=1;i<=G->vernum;i++）
{
fprintf（fp,"\n%-20s%-20s",G->vertex[i].filename,G->vertex[i].vertexdata）;
for（p=G->vertex[i].firstarc;p!
=NULL;p=p->nextarc）
fprintf（fp,"%-4d%-10.2f",p->adjvex,p->adj）;
t=-1;//每一行的结束标志
fprintf（fp,"%-4d",t）;
}
fclose（fp）;
//printf（"\n是否读出新文件yorn：
"）;
//flushall（）;
//scanf（"%c",&m）;
//if（m=='y'||m=='Y'）
//Read_inf（）;
}
//--------------------------------------------将文件转化为链表
AdjList*Creat_Link（）
{
FILE*fp;
inti;
intt=0;//判断每一行是否结束
charfilename[LEN];
//charm;
AdjList*G;
ArcNode*p,*s;
G=（AdjList*）malloc（sizeof（AdjList））;
printf（"\n请输入关于旅游信息的文件名（建议a.txt）：
"）;
flushall（）;
gets（filename）;
fp=fopen（filename,"rt"）;
if（fp==NULL）
{
printf（"\n输入文件名错误，按任意键重新输入"）;
getch（）;
system（"cls"）;
G=Creat_Link（）;
}
for（i=1;!
feof（fp）;i++）//文件未结束
{
fscanf（fp,"%s",G->vertex[i].filename）;//读出景点文件名
fscanf（fp,"%s",G->vertex[i].vertexdata）;//读出景点名
G->vertex[i].firstarc=NULL;
fscanf（fp,"%d",&t）;//存入第一个元素
for（p=G->vertex[i].firstarc;t!
=-1;）//判断一行是否结束，结束为-1
{
s=（ArcNode*）malloc（sizeof（ArcNode））;
s->adjvex=t;//t有效则为下标
fscanf（fp,"%f",&s->adj）;//得到权值
s->nextarc=p;
G->vertex[i].firstarc=s;
p=s;
fscanf（fp,"%d",&t）;
}
//p->nextarc=NULL;
}
i--;
G->vernum=i;
//G->vertex[i].vertexdata=0;//错啦
fclose（fp）;
returnG;
}
//---------------------------------------------读文件（输出文件信息）
voidRead_inf（）
{
AdjList*G;
system（"cls"）;
printf（"\n原文件为"）;
G=Creat_Link（）;
Print_DN（G）;//有待改正
//fclose（fp）;
//returnG;
}
//-----------------------------------------景点描述
voidPrint_Scenic（AdjList*G）
{
FILE*fp;
charfilename[LEN];
charstr[MAX],v[M];
intm;
printf（"请输入所要查询的景点名称:
"）;
flushall（）;
gets（v）;
m=LocateVex（G,v）;
strcpy（filename,G->vertex[m].filename）;
fp=fopen（filename,"rt"）;
if（fp==NULL）
{
printf（"\n文件不存在"）;
getch（）;
//system（"cls"）;
}
/*switch（m）
{
case1:
fp=fopen（"1.txt","rt"）;break;
case2:
fp=fopen（"2.txt","rt"）;break;
case3:
fp=fopen（"3.txt","rt"）;break;
case4:
fp=fopen（"4.txt","rt"）;break;
case5:
fp=fopen（"5.txt","rt"）;break;
case6:
fp=fopen（"6.txt","rt"）;break;
case7:
fp=fopen（"7.txt","rt"）;break;
case8:
fp=fopen（"8.txt","rt"）;break;
case9:
fp=fopen（"9.txt","rt"）;break;
case10:
fp=fopen（"10.txt","rt"）;break;
case11:
fp=fopen（"11.txt","rt"）;break;
case12:
fp=fopen（"12.txt","rt"）;break;
case13:
fp=fopen（"13.txt","rt"）;break;
case14:
fp=fopen（"14.txt","rt"）;break;
case15:
fp=fopen（"15.txt","rt"）;break;
default:
fp=fopen（"其他.txt","rt"）;break;
*/
while（!
feof（fp））
{
fscanf（fp,"%s",str）;
puts（str）;
}
}
//------------------------------------------所有景点名称
voidAll_Scenic（AdjList*G）
{
inti;
for（i=1;ivernum;i++）
{
printf（"%-2d.",i）;
puts（G->vertex[i].vertexdata）;
}
}
//-----------------------------------------建立景点信息（简介）
voidCreat_Scenic（AdjList*G）
{
FILE*fp;
charfilename[LEN];
charname[M],str[MAX],m;
inti;
printf（"\n请输入要描述的景点名称：
"）;
flushall（）;
gets（name）;
i=LocateVex（G,name）;
//printf（"请输关于景点描述的入文件名：
"）;
//scanf（"%s",filename）;
strcpy（filename,G->vertex[i].filename）;
printf（"\n是否重新介绍（yorn）:
"）;
flushall（）;
scanf（"%c",&m）;
if（m=='y'||m=='Y'）
fp=fopen（filename,"wt"）;
else
fp=fopen（filename,"a+"）;
//fp=fopen（filename,"rt"）;
if（fp!
=NULL）
{
printf（"请输入关于%s的描述信息\n\n",name）;
system（"cls"）;
strcpy（G->vertex[i].filename,filename）;
printf（"请输入关于%s的描述信息\n\n",name）;
flushall（）;
gets（str）;
fprintf（fp,"\n%s",str）;
fclose（fp）;
}
printf（"\n按任意键继续"）;
getch（）;
}
/***********************************寻找v1所在位置****************************************/
intLocateVex（AdjList*G,charv[M]）
{
inti,m;
for（i=1;ivernum;i++）
{
if（（strcmp（v,G->vertex[i].vertexdata））==0）
break;
}
if（i==G->vernum&&（strcmp（v,G->vertex[i].vertexdata））!
=0）
m=-1;
else
m=i;
returnm;
}
/**************************************用邻接链表建立图*************************************/
voidCreatDN_Num_N（AdjList*G）//（不追加）建立节点
{
intt;//用于计数
charstr[M],filename[LEN];
printf（"请输入景点名称（ok结束）:
"）;
flushall（）;
gets（str）;
//gets（str）;
for（t=1;（strcmp（str,"ok"））!
=0;t++）
{
strcpy（G->vertex[t].vertexdata,str）;
printf（"请输入关于景点的文件名：
"）;
flushall（）;
gets（filename）;
strcpy（G->vertex[t].filename,filename）;
G->vertex[t].firstarc=NULL;
printf（"请输入景点名称:
"）;
flushall（）;
gets（str）;
}
t--;
G->vernum=t;
//G->vertex[t]=0;
}
AdjList*CreatDN_Num_Y（AdjList*G）//（追加）建立节点
{
intt;//用于计数
charstr[M],filename[LEN];
/*链表顶点赋值与顶点的初始化*/
G=（AdjList*）malloc（sizeof（AdjList））;
G=Creat_Link（）;//printf（"测试"）;puts（G->vertex[1].vertexdata）;
t=G->vernum;
printf（"景点名称（“ok”结束）"）;
flushall（）;
gets（str）;
for（t;（strcmp（str,"ok"））!
=0;t++）
{
strcpy（G->vertex[t].vertexdata,str）;
printf（"请输入关于景点的文件名：
"）;
flushall（）;
gets（filename）;
strcpy（G->vertex[t].filename,filename）;
G->vertex[t].firstarc=NULL;
printf（"请输入景点名称:
"）;
flushall（）;
gets（str）;
}
t--;//t--;
G->vernum=t;
returnG;
}
/*---------------------------------根据节点间信息建立链表--------------------------------*/
//------------------------------------------建立两个节点间关系
voidOne_Adj（AdjList*G,floatweight）//双向的
{
inti,j;
//floatweight;
charv1[M],v2[M];
ArcNode*p,*q;
ArcNode*s,*r;
printf（"第一个景点名称:
"）;
flushall（）;
gets（v1）;
printf（"第二个景点名称:
"）;
gets（v2）;
i=LocateVex（G,v1）;//LocateVex中若找不着返回-1
j=LocateVex（G,v2）;//找到v1，v2所在位置
if（i==-1||j==-1）
{
printf（"输入两个景点名称错误,按任意键重新输入\n"）;
getch（）;
system（"cls"）;
printf（"两景点间距离（-1结束）:
%f\n",weight）;
One_Adj（G,weight）;
}
else
{//i在j之前
p=G->vertex[i].firstarc;
q=G->vertex[j].firstarc;
s=（ArcNode*）malloc（sizeof（ArcNode））;
r=（ArcNode*）malloc（sizeof（ArcNode））;
s->adjvex=j;//头插法
s->nextarc=p;
s->adj=weight;
G->vertex[i].firstarc=s;
r->adjvex=i;
r->nextarc=q;
r->adj=weight;
G->vertex[j].firstarc=r;
}
}
voidCreatDN（AdjList*G）
{
升级会员 