数据结构实验--图.doc

#include#include #include #define MAX_NUM 20bool visitedMAX_NUM;/访问标致数组bool found;int fomer=0;char v1,v2;int tfind;typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 / InfoType *info; / 该弧相关信息的指针 ArcNode;typedef struct VNode char data; / 顶点信息 int data2; int sngle; ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_NUM;typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;void DFS(ALGraph G,int v);typedef struct qnode /队列类型int data;qnode *next;qnode,*queueptr;typedef struct queueptr front;queueptr rear;linkqueue;typedef struct stack/用栈存储路径char *base;char *top;int stacksize;int size;Stack;Stack s;int initstack(Stack &s)s.base=(char*)malloc(40*sizeof(char);s.top=s.base;s.stacksize=40;s.size=0;return 1;int push(Stack &s,char e) *s.top+=e; s.size+; return 1;int pop(Stack &s,char &e)if(s.base=s.top)e=*-s.top;else e=*-s.top;s.size-;return 1;void printstack(Stack s)while(s.base!=s.top)printf(%c ,*s.base);s.base+;printf(n);void printstack2(Stack s)while(s.base!=s.top)printf(%c ,*-s.top);printf(n);int intitqueue(linkqueue &q)/初始化队列 q.front=q.rear=(queueptr)malloc(sizeof(qnode);q.front-next=NULL;return 1;int emptyqueue(linkqueue q)/判断对了是否为空 if (q.front=q.rear) return 1;return 0;int enqueue(linkqueue &q,int e)/元素入队queueptr p;p=(queueptr)malloc(sizeof(qnode);if(!p) exit(0);p-data=e; p-next=NULL;q.rear-next=p;q.rear=p;return 1;int dequeue(linkqueue &q,int &e)/元素出队queueptr p;if(q.front=q.rear) return 0;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear=p) q.rear=q.front;free(p);return 1;int LocateVex(ALGraph &G,char v)int i; for(i=0;iadjvex;return -1;int NextAdjVex(ALGraph G,int v,int w)while (G.verticesv.firstarc-nextarc!=NULL)if(G.verticesv.firstarc-adjvex=w)return G.verticesv.firstarc-nextarc-adjvex;else G.verticesv.firstarc=G.verticesv.firstarc-nextarc;return -1;void Create(ALGraph &G)int i,j,k;char v1,v2;ArcNode *p,*q,*h;q=NULL;h=NULL;printf(输入节点个数和弧的个数:n); scanf(%d%d,&G.vexnum,&G.arcnum); for(i=0;iG.vexnum;i+) fflush(stdin); printf(输入节点名称:n); scanf(%c,&G.verticesi.data); G.verticesi.firstarc=NULL; G.verticesi.data2=i; for(k=0;kadjvex=j; p-nextarc=NULL; if (G.verticesi.firstarc=NULL) G.verticesi.firstarc=p; else q=G.verticesi.firstarc; while(q-nextarc!=NULL) q=q-nextarc; q-nextarc=p; void DFSTraverse(ALGraph G)/深度遍历int v; for(v=0;v=0)&(tfind=0);w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w); void DFSTree(ALGraph G)/广度遍历int w,u,v;linkqueue q;intitqueue(q);for (v=0;v0;w=NextAdjVex(G,u,w)if (!visitedw)visitedw=true;printf(%c ,G.verticesw.data);if(w0)enqueue(q,w);printf(n);void DFS2(ALGraph G,int v)/用深度遍历算法实现搜索简单路径int w;char e;visitedv=true;push(s,G.verticesv.data);for(w=FirstAdjVex(G,v);(w=0)&(!found);w=NextAdjVex(G,v,w)if(G.verticesw.data=v2)found=true;push(s,G.verticesw.data);else if(!visitedw) DFS2(G,w);if(!found) pop(s,e);void Simplepath(ALGraph G)/搜索简单路径 printf(输入要搜索路径的两点：n); fflush(stdin); scanf(%c,&v1); fflush(stdin); scanf(%c,&v2); DFS2(G,LocateVex(G,v1); if (!found) printf(can not found zhe path!n); else printstack(s);void DFSTree2(ALGraph G,int v)/用广度优先求最短路径int w,u;linkqueue q;intitqueue(q); if (!visitedv)visitedv=true;G.verticesv.sngle=-1;enqueue(q,v);while (!emptyqueue(q)dequeue(q,u);for (w=FirstAdjVex(G,u);(w0)&(!found);w=NextAdjVex(G,u,w)if (!visitedw)visitedw=true;G.verticesw.sngle=u;if(w0)enqueue(q,w);if(G.verticesw.data=v2)found=true;while (G.verticesw.sngle!=-1)push(s,G.verticesw.data);w=G.verticesw.sngle;printf(n);void shortcut(ALGraph G)/搜索最短路径 printf(输入要搜索路径的两点：n); fflush(stdin); scanf(%c,&v1); fflush(stdin); scanf(%c,&v2); DFSTree2(G,LocateVex(G,v1); push(s,v1); printstack2(s);printf(n);void main()int v;ALGraph G;found=false; initstack(s); Create(G); while(1) for(v=0;vG.vexnum;v+) visitedv=false; G.verticesv.sngle=-2; tfind=0;system(cls); printf(-n); printf(1、深度优先遍历n); printf(2、广度优先遍历n);