[分享]缔结特斯拉算法

Forever紫月

#include <iostream.h>
#include <cstring>
#include <stdlib.h>
#include<stdio.h>
#include <conio.h>
#include <ctype.h>
#define MAXVTXNUM 20 //图中顶点数的最大值
#define MAXSIZE 1000
#define MAX 30
#ifndef x
#define x 1
typedef struct
{
char *name; //该顶点的名称
char *info; //景点信息
}VertexType; //顶点类型
#endif
#ifndef xx
#define xx 1
typedef struct
{
int lengh; //边的权值
int ivex,jvex; //边两端的顶点号
}EdgeType; // 变的类型
#endif
#ifndef xxx
#define xxx 1
typedef struct EdgeNode
{
EdgeType elem;
EdgeNode *ilink,*jlink;
}EdgeNode, *EdgePtr; //边的结点类型
#endif
#ifndef xxxx
#define xxxx 1
typedef struct
{
VertexType data;
EdgePtr firstEdge; //指向第一条依附于该顶点的边的指针类型
}VNode; //顶点类型
#endif
#ifndef xxxxx
#define xxxxx 2
typedef struct
{
VNode Adjmulist[MAXVTXNUM]; //邻接多重表
int vexNum, edgeNum; //图中的顶点数和边数
}GraphType; //图的类型
#endif
#ifndef xxxxxx
#define xxxxxx 3
typedef struct
{
int vx, vy;
}Edge;
typedef struct
{
Edge edges[MAXVTXNUM]; //路径中边的序列
int len; //路径中边的数目
}PathType;
#endif
#ifndef xxxxxxx
#define xxxxxxx 4
typedef struct
{
char *Vertices[MAXSIZE]; //路径中景点的序列
int num;
}PType;
#endif
void InitGraph(GraphType &g); //初始化邻接多重表，表示一个空图
//在途中查找其景点名和uname相同的顶点。若存在，则以i返回其在临界多重表中的位置并返回TURE；
bool LocateVex(GraphType &g, char *uname, int &i);
void GetVex(GraphType g, int i, VertexType &v);
EdgePtr FirstEdge(GraphType g, int vi);
void NextEdge(GraphType g, int vi, EdgePtr p, int &vj, EdgePtr &q);
void InsertVex(GraphType &g, VertexType v);
void InsertEdge(GraphType &g, EdgeType e);
void DeleteVex(GraphType &g, VertexType v);
void DeleteEdge(GraphType &g, EdgeType e);
void InitPath(PathType &pa); //初始化pa为一条空路径
void CopyPath(PathType &p1, PathType &p2); //复制路径p1=p2
void InsertPath(PathType &pa, int v, int w); //在路径pa中插入一条边（v,w）
int PathLength(PathType pa); //返回路径pa的长度
void OutPath(GraphType g, PathType pa, PType &vtxes); //将路径转化为景点的名序列
void Initialization();
void ReadCommand(char &cmd);
void Interpret(char cmd);
void CreatGraph(GraphType &g, FILE *f);
void GetShortestPath(GraphType g, char *sname, char *tname,
int &pathLength, PType &PathInfo);
void ShortestPath(GraphType g, int st, int nd,
int &pathLength, PType &PathInfo)；
//#include<string>
/////////////////////////////////////////////////////////////
////////////////////// 图设计部分 ///////////////////////
/////////////////////////////////////////////////////////////
void InitGraph(GraphType &g)
{
g.vexNum = g.edgeNum = 0;
}//InitGraph
bool LocateVex(GraphType &g, char *uname, int &i)
{
for(i=0; i<g.vexNum; i++)
if(!strcmp(uname, g.Adjmulist[i].data.name))
{
return true;
break;
}
return false;
}//LocateVex
EdgePtr FirstEdge(GraphType g, int vi)
{//返回图g中指向依附于顶点vi的第一条边的指针g.Adjmulist[i].data
return
g.Adjmulist[vi].firstEdge;
}//FirstEdge
void GetVex(GraphType g, int i, VertexType &v)
{
if(i<0)
cout<<"这两点间无路径可通！"<<endl;
else
v = g.Adjmulist[i].data;
}//GetVex
void NextEdge(GraphType g, int vi, EdgePtr p, int &vj, EdgePtr &q)
{
if(p->elem.ivex==vi )
{
q = p->ilink;
vj = p->elem.jvex;
}
else
{
q = p->jlink;
vj = p->elem.ivex;
}
}//NextEdge
void InsertEdge(GraphType &g, EdgeType e)
{

EdgePtr p;
p = (EdgePtr)malloc(sizeof(EdgeNode));
p->elem =e;
p->ilink = FirstEdge(g,e.ivex);
p->jlink = FirstEdge(g, e.jvex);
g.Adjmulist[e.ivex].firstEdge = g.Adjmulist[e.jvex].firstEdge = p;
}//InsertEdge
void InsertVex(GraphType &g, VertexType v, int i)
{
//在图g的邻接多重表中添加一个顶点v
g.Adjmulist[i].data.name = new char[MAXSIZE];
g.Adjmulist[i].data.info = new char[MAXSIZE];
strcpy(g.Adjmulist[i].data.name,v.name);
strcpy(g.Adjmulist[i].data.info,v.info);
g.Adjmulist[i].firstEdge = NULL;
}
///////////////////////////////////////////////////////////////////////
///////////////////////// 路径类型 ////////////////////////////////
///////////////////////////////////////////////////////////////////////
void InitPath(PathType &pa)
{
pa.len = 0;
}//InitPath
int PathLengh(PathType pa)
{
return pa.len;
}//PathLengh
void CopyPath(PathType &p1, PathType &p2)
{
//复制路径p1=p2
for(int i =0; i<p2.len; i++)
{
p1.edges[i].vx = p2.edges[i].vx;
p1.edges[i].vy = p2.edges[i].vy;
}
p1.len = p2.len;
}//CopyPath
void InsertPath(PathType &pa, int v, int w)
{
//在路pa径中插入一条边（v，w）
pa.edges[pa.len].vx = v;
pa.edges[pa.len].vy = w;
pa.len++;
}//InsertPath
void OutPath(GraphType g, PathType pa, PType &vtxes)
{
//将路径转化为景点的名序列
int m = 0;
VertexType vtx;
vtx.info = new char[MAXSIZE];
vtx.name = new char[MAXSIZE];
for(int i=0; i<pa.len; i+