b2-6.txt

数据结构168个实验程序,很全面

# include "stdio.h"
# include "stdlib.h"
# define Max 20
# define FALSE 0
# define true 1
typedef struct
{
	char name;
	char message;
}VertexType;
/*顶点类型*/
typedef struct
{
	 int lengh;
     struct EdgeType *ivex,*jvex;
}EdgeType;
/*边的类型*/
typedef struct EdgeNode
{
    int elem;
    struct EdgeNode * ilink, * jlink;
}EdgeNode; 
/*边的结点类型，指向边的指针*/
typedef struct
{
    int data;
    struct EdgeNode *firstEdge;
}VNode;
/*顶点类型*/
typedef struct
{
    char Adjmulist[Max];
	int vexNum,edgeNum;
}GraphType;
 /*图的类型*/
void *NextEdge(GraphTyope *g,int vi,EdgeNode * p,int vj,EdgeNode * q)
{
    if(p->elem->ivex==vi)
    {  
		vj=p->elem->jvex;
	}
    else  
	{  
		q=p->jlink;  
		vj=p->elem->ivex;
	}
}
void *InsertEdge(GraphType *g,EdgeType *e)
{
	p=(EdgeNode*)malloc(sizeof(EdgeNode));
    p->elem=e;
    p->ilink=FistEdge(g,e,ivex);
    p->jlink=FistEdge(g,e,jvex);
    g->Adjmulist[e->ivex].firstedge=g->Adjmulist[e->jvex].firstedge=p;
}
//2.路径类型
typedef struct
{
    int vx,vy;
}Edge;
typedef struct
{
    int edges[Max];  /*路径中边的序列*/
    int len;  /*路径中边的数目*/
}PathType;
typedef struct
{
    char vertices[Max];
    int num;
}PType;
void *copyPath(PathType *p1,PathType *p2)
{  /*复制路径p1=p2*/
    int i;
    for(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;
}
void *InsertPath(PathType *pa,int v,int w)
{ /*在路径中插入一条边（v，w）*/
    pa->edges[pa->len]->vx=v;
    pa->edges[pa->len]->vy=w;
    pa->len++;
}
void *OutPath(GraphType *g,pathType *pa,PType *vtxes)
{/*将路径转换为景点名称的序列*/
    m=0;
    for(i=0;i<pa->len;i++)
    {
	    GetVex(g,pa->edges[i],vx,vtx);
	    vtxes[m++]=vtx->name;
	}
	GetVex(g,pa,edges[pa->len].vy,vtx);
	vtxes[m]=vtx->name;
	vtxes->num=m;
}
//3.主程序及其他
void main()
{
    Initialization();
    do
    {
		ReadCommand(cmd);
		Interpret(cmd)
	} 
    while(cmd!='q'&&cmd!='Q');
}
void Initialization()
{   
	char filename;
    scanf(filename);
    fin=fopen(filename,'r');
    CreatGraph(ga,fin);
 }
void ReadCommande(char cmd)
{         
    do
	{
		cmd=getche();
	}
    while(cmd!='s'&&cmd!='S'&&cmd!='v'&&cmd!='V'&&cmd!='q'&&cmd!='Q');
}
* Interpret(char cmd)
{
    switch(cmd)
    {
	    case's','S'://显示以串的形式键入景点名称的提示信息；
	                scanf("%c",sname);/*景点名称*/
				    PrintScenery(name);
					break;
	    case'v','V'://显示以串的形式键入始点名称和终点名称的提示信息； 
	                scanf("%c,%c",sname，tname);
			 	    GetShortestPath(ga,sname,tname,pathlen,spath);
		       	    PrintPath(spath,pathLen);/*输出最短路径及其长度*/
	 				break;
        case'q','Q':
	}
}
 Creat(Graphtype *g,int *f)
{
	int i,k;
	int *v;
    INitGraph(g);
    scanf("%c,%c,%c",f,g->vexNum,g->edge3Num);
	for(i=0;i<g->vexNum;i++)
	{
	    scanf("%c,%c,%c",f,e->name,v->info);
		InsertVex(g,v);
	}
    for(k=0;k<g->edgeNum;k++)
	{
	    scanf("%c,%c,%c,%c",&f,e->ivex,e->jvex,e->length);
	    if (e->length)
			InsertEdge(g,e);
    }
}
void *GetshortestPath(GraphType *g,char sname,char tname,int pathLength,PType *PathInfo)
{
	char sv,tv;
    LocateVex(g,sname,sv);
    Locate(g,tname,tv);
    ShortestPath(g,sv,tv,pathLength,PathInfo);
}
void *ShortestPath(GraphType *g,int st,int nd,int pathLength,PType *PathInfo)
{
	int min,maxadjvex;
	int i,v,w,st,ss,q;
    int dist[Max];
	PathType *path[Max];
    for(i=0;i<g->vexNum;i++)
    {
		dist[i]=max;
		InitPath(path[i]);
	}
    p=Firstedge(g,st);
    while(p)
    {
	    NextEdge(g,p,st,q,adjvex);
	    dist[adjvex]=p->length;
	    InsertPath(path[adjvex],st,adjvex);
	    p=q;
	}
	found=FALSE;
	InitSet(ss);
	PutInSet(st,ss);
	while(!found)
	{
	    min=minval(dist);
	    if (min==nd)
	        found=true;
	    else 
	    {
		    v=min;
			PutInSet(v,ss);
		    p=Firstedge(g,v);
		    while(p)
			{
		        NextEdge(g,p,v,q,w);
			    if (!Insert(w,ss)&&(dist[v]+p->length)<dist[w])
				{
			        dist[w]=dist[v]+p->length;
				    copyPath(path[w],path[v]);
                    InsertPath(path[w],v,w);
				}
			    p=q;
			}
		}
	}     
    pathLength=dist[nd];
	OutPath(g,path[nd],PathVal);
}