#pragma once#include<stdio.h>#include<stdlib.h>#define StackSize 100typedef int DataType; //栈元素类型定义typedef struct{ DataType stack[StackSize]; int top;}SeqStack;//将栈初始化为空栈只需要把栈顶指针top置为void InitStack(SeqStack *S){ S->top=0;//把栈顶指针置为0}//判断栈是否为空,栈为空返回1,否则返回0int StackEmpty(SeqStack S){ if(S.top==0) return 1; else return 0;}//取栈顶元素,DataStructureCImpl:求图G中从顶点u到顶点v的一条
。将栈顶元素值返回给e,并返回1表示成功;否则返回0表示失败。int GetTop(SeqStack S,DataType *e){ if(S.top<=0){ //在取栈顶元素之前,判断栈是否为空 printf(栈已经空!); return 0; }else{ *e=S.stack[S.top-1]; //在取栈顶元素 return 1; }}//将元素e进栈,元素进栈成功返回1,否则返回0int PushStack(SeqStack *S,DataType e){ if(S->top>=StackSize){ //在元素进栈前,判断是否栈已经满 printf(栈已满,不能进栈!); return 0; }else{ S->stack[S->top]=e; //元素e进栈 S->top++; //修改栈顶指针 return 1; }}//出栈操作。将栈顶元素出栈,并将其赋值给e。出栈成功返回1,否则返回0int PopStack(SeqStack *S,DataType *e){ if(S->top<=0){ //元素出栈之前,判断栈是否为空 printf(栈已经没有元素,不能出栈!); return 0; }else{ S->top--; //先修改栈顶指针,即出栈 *e=S->stack[S->top]; //将出栈元素赋值给e return 1; }}//求栈的长度,即栈中元素个数,栈顶指针的值就等于栈中元素的个数int StackLength(SeqStack S){ return S.top;}//清空栈的操作void ClearStack(SeqStack *S){ S->top=0;}</stdlib.h></stdio.h>
#include<stdio.h>#include<stdlib.h>#include<string.h>#includeSeqStack.htypedef char VertexType[4];typedef char InfoPtr;typedef int VRType;#define MaxSize 50 //最大顶点个数typedef enum{DG,DN,UG,UN}GraphKind; //图的类型:有向图、有向网、无向图和无向网//边结点的类型定义typedef struct ArcNode{ int adjvex; //弧指向的顶点的位置 InfoPtr *info; //弧的权值 struct ArcNode *nextarc; //指示下一个与该顶点相邻接的顶点}ArcNode;//头结点的类型定义typedef struct VNode{ VertexType data; //用于存储顶点 ArcNode *firstarc; //指示第一个与该顶点邻接的顶点}VNode,AdjList[MaxSize];//图的类型定义typedef struct{ AdjList vertex; //头结点 int vexnum,arcnum; //图的顶点数目与弧的数目 GraphKind kind; //图的类型}AdjGraph;//求图G中从顶点u到顶点v的一条简单路径void BriefPath(AdjGraph G,int u,int v){ int k,i; SeqStack S; ArcNode *p; int visited[MaxSize]; int parent[MaxSize]; //存储已经访问顶点的前驱顶点 InitStack(&S); for(k=0;k<g.vexnum;k++) 1="" p="G.vertex[k].firstarc;" p-="">adjvex==v){ //如果找到顶点v parent[p->adjvex]=k; //顶点v的前驱顶点序号是k printf(顶点%s到顶点%s的路径是:,G.vertex[u].data,G.vertex[v].data); i=v; do{ //从顶点v开始将路径中的顶点依次入栈 PushStack(&S,i); i=parent[i]; }while(i!=u); PushStack(&S,u); while(!StackEmpty(S)){ //从顶点u开始输出u到v中路径的顶点 PopStack(&S,&i); printf(%s ,G.vertex[i].data); } printf(); }else if(visited[p->adjvex]==0){ //如果未找到顶点v且邻接点未访问过,则继续寻找 visited[p->adjvex]=1; parent[p->adjvex]=k; PushStack(&S,p->adjvex); } p=p->nextarc; } }}//返回图中顶点对应的位置int LocateVertex(AdjGraph G,VertexType v){ int i; for(i=0;i<g.vexnum;i++) :="" adjgraph="" arcnode="" g-="" int="" n="" return="" vertextype="" void="">vexnum); for(i=0;i<g->vexnum;i++) /*将顶点存储在头结点中*/ { scanf(%s,G->vertex[i].data); G->vertex[i].firstarc=NULL; /*将相关联的顶点置为空*/ } printf(请输入边的两个顶点(以空格作为分隔):); for(k=0;k<g->arcnum;k++) /*建立边链表*/ { scanf(%s%s,v1,v2); i=LocateVertex(*G,v1); j=LocateVertex(*G,v2); /*j为入边i为出边创建邻接表*/ p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=(InfoPtr*)malloc(sizeof(InfoPtr)); /*将p指向的结点插入到边表中*/ p->nextarc=G->vertex[i].firstarc; G->vertex[i].firstarc=p; /*i为入边j为出边创建邻接表*/ p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=i; p->info=NULL; p->nextarc=G->vertex[j].firstarc; G->vertex[j].firstarc=p; } (*G).kind=UG;}//销毁无向图Gvoid DestroyGraph(AdjGraph *G){ int i; ArcNode *p,*q; for(i=0;i<g->vexnum;++i) /*释放图中的边表结点*/ { p=G->vertex[i].firstarc; /*p指向边表的第一个结点*/ if(p!=NULL) /*如果边表不为空,则释放边表的结点*/ { q=p->nextarc; free(p); p=q; } } (*G).vexnum=0; /*将顶点数置为0*/ (*G).arcnum=0; /*将边的数目置为0*/}//图G的邻接表的输出void DisplayGraph(AdjGraph G){ int i; ArcNode *p; printf(该图中有%d个顶点:,G.vexnum); for(i=0;i<g.vexnum;i++) :="" i="0;i<G.vexnum;i++)" p="G.vertex[i].firstarc;" p-="" s="">adjvex].data); p=p->nextarc; } printf(); }}void main(){ AdjGraph G; CreateGraph(&G); /*采用邻接表存储结构创建图G*/ DisplayGraph(G); /*输出无向图G*/ BriefPath(G,0,4); /*求图G中从顶点a到顶点e的简单路径*/ DestroyGraph(&G); /*销毁图G*/ system(pause);}</g.vexnum;i++)></g-></g-></g-></g.vexnum;i++)></g.vexnum;k++)></string.h></stdlib.h></stdio.h>