数据结构实验--图.doc

《数据结构实验--图.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#include#defineMAX_NUM20boolvisited[MAX_NUM];//访问标致数组boolfound;intfomer=0;charv1,v2;inttfind;typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针//InfoType*info;//该弧相关信息的指针}ArcNode;typedefstructVNode{chardata;//顶点信息int

2、data2;intsngle;ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;//图的种类标志}ALGraph;voidDFS(ALGraphG,intv);typedefstructqnode//队列类型{intdata;qnode*next;}qnode,*queueptr;typedefstruct{queueptrfront;queueptrrear;}linkqueue;typedefst

3、ructstack//用栈存储路径{char*base;char*top;intstacksize;intsize;}Stack;Stacks;intinitstack(Stack&s){s.base=(char*)malloc(40*sizeof(char));s.top=s.base;s.stacksize=40;s.size=0;return1;}intpush(Stack&s,chare){*s.top++=e;s.size++;return1;}intpop(Stack&s,char&e){if(s.base==s.top)e=*--s.top;else{e

4、=*--s.top;s.size--;}return1;}voidprintstack(Stacks){while(s.base!=s.top){printf("%c",*s.base);s.base++;}printf("");}voidprintstack2(Stacks){while(s.base!=s.top){printf("%c",*--s.top);}printf("");}intintitqueue(linkqueue&q)//初始化队列{q.front=q.rear=(queueptr)malloc(sizeof(qnode));q.fron

5、t->next=NULL;return1;}intemptyqueue(linkqueueq)//判断对了是否为空{if(q.front==q.rear)return1;return0;}intenqueue(linkqueue&q,inte)//元素入队{queueptrp;p=(queueptr)malloc(sizeof(qnode));if(!p)exit(0);p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;return1;}intdequeue(linkqueue&q,int&e)//元素出队{queueptr

6、p;if(q.front==q.rear)return0;p=q.front->next;e=p->data;q.front->next=p->next;if(q.rear==p)q.rear=q.front;free(p);return1;}intLocateVex(ALGraph&G,charv){inti;for(i=0;i

7、turnG.vertices[v].firstarc->adjvex;return-1;}intNextAdjVex(ALGraphG,intv,intw){while(G.vertices[v].firstarc->nextarc!=NULL){if(G.vertices[v].firstarc->adjvex==w)returnG.vertices[v].firstarc->nextarc->adjvex;elseG.vertices[v].firstarc=G.vertices[v].firstarc->nextarc;}return-1;}v