地铁换乘系统

地铁换乘系统 地铁换乘系统 地铁换乘系统 地铁换乘系统C++

#include “graph.h“
#include “linklist_path.h“
#include 
#include 
#include 


//创建邻接表//
void create_graph（alGraph *AG）
{
	arcNode * p;
	int ijkweight;
	FILE *fp;
	fp=fopen（“path.txt““r“）;
	fscanf（fp“%d%d“&AG->vexnum&AG->arcnum）;
	for（i=1;i<=AG->vexnum;i++）
	{
		fscanf（fp“%s“AG->vertices[i].name）;
		AG->vertices[i].id=i;
		AG->vertices[i].firstArc=NULL;
	}

	//权值相同的边在同一条轨道线上//
	for （k=1;k<=AG->arcnum;k++）
	{
		fscanf（fp“%d %d %d“&i&j&weight）;
		p=（arcNode *）malloc（sizeof（*p））;
		p->adjvex=j;
		p->weight=weight;
		p->nextarc=AG->vertices[i].firstArc;
		AG->vertices[i].firstArc=p;
		p=（arcNode *）malloc（sizeof（*p））;
		p->adjvex=i;
		p->weight=weight;
		p->nextarc=AG->vertices[j].firstArc;
		AG->vertices[j].firstArc=p;

	}
	fclose（fp）;
}


//根据所给的站名定位到站的号码//
int vertex_locate（alGraph *AGchar *a）
{
	int i=1;
	while（strcmp（AG->vertices[i].namea）&&i<=AG->vexnum）
		i++;
	if（i<=AG->vexnum）
		return i;
	else return 0;
}


//读取信息并准备好调用allsearch//
void search（alGraph *AG）
{
	char from[20]to[20];
	int ft;
	route *r;
	path_rec pa;
	int  visited[MAX_VERTEX_NUM]={0};


	create_path（&pa）;//创建保存路径的链表//
	r=（route *）malloc（sizeof（route））;
	printf（“Please tell me where you are:\n“）;
	scanf（“%s“from）;
	printf（“And then tell me where you are going:\n“）;
	scanf（“%s“to）;
	f=vertex_locate（AGfrom）;
	t=vertex_locate（AGto）;

	if（f==0||t==0）
	{
		printf（“You may enter the wrong place!!\nPlease retry!\n\n\n“）;
		return;
	}
	r->top=1;

	search_all_path（AGr->pathvisitedftr->top&pa）;
	print_path（AG&pa）;


}


//利用深度搜索的递归找出所有的路径//
void search_all_path（alGraph *AGint *path int *visitedint vint des int toppath_rec *pa）
{
	int jixyflag;
	arcNode *p;
	all_path *pall;
	if（visited[v]）
		return;
	path[top-1]=v;
	if（v==des）
	{
		flag=0;
		for （x=0;x		{
			for （y=x+1;y				if（path[x]==path[y]）
					flag=1;
		}

		if（flag==0）
		{
			pall=（all_path *）malloc（sizeof（all_path））;
			pall->times=0;
			pall->top=top;
			for（i=0;i			{	
				pall->change_point[i]=0;
				pall->path[i]=path[i];
			}
			get_times（AGpall）;
			insert_path（papall）;
		}

	}
	else
		visited[v]=1;
	for（p=AG->vertices[v].firstArc;p;p=p->nextarc）
	{
		j=p->adjvex;
		if（!visited[j]）
			search_all_path（AGpathvisitedjdestop+1pa）;

	}
	visited[v]=0;
}



//输出路径//
void print_path（alGraph *AGpath_rec *pa）
{
	int m=100k;
	all_path *p;
	for（p=pa->head->next;p!=NULL;p=p->next）
		if（p->times<=m）
			m=p->times;
	for（p=pa->head->next;p!=NULL;p=p->next）
		if（p->times==m）
		{
			printf（“\n\nThis way can be the way best:\n“）;
			for（k=0;k<（p->top）-1;k++）
			{
				if（p->change_point[k]）
					printf（“%s（在此转乘）---->“AG->vertices[p->path[k]].name）;
				else
					printf（“%s-->“AG->vertices[p->path[k]].name）;
			}
			printf（“%s\n\n“AG->vertices[p->path[（p->top）-1]].name）;
			printf（“You need

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3637  2011-11-09 21:57  地铁换乘系统\graph.c

     文件       1064  2011-11-05 20:08  地铁换乘系统\graph.h

     文件        451  2011-11-05 20:03  地铁换乘系统\linklist_path.c

     文件        538  2011-11-04 21:10  地铁换乘系统\linklist_path.h

     文件        818  2011-11-09 21:56  地铁换乘系统\main.c

     文件       3079  2011-11-01 20:03  地铁换乘系统\path.txt

     目录          0  2012-03-10 09:05  地铁换乘系统

----------- ---------  ---------- -----  ----

                 9587                    7