linjiejuzhen.rar_邻接多重表

#include <stdio.h> #include <malloc.h> #define MAX_VERTEX_NUM 30 typedef enum{FALSE,TRUE}Boolean;//FALSE为0，TRUE为1 Boolean visited[MAX_VERTEX_NUM];//访问标志向量是全局量 typedef int datatype; typedef int status; typedef struct Arcnode { int adjvex;//该弧所指向的顶点的位置 struct Arcnode *nextarc;//指向下一条弧的结构体指针 }ArcNode; ArcNode *nextnode=NULL;//全局变量 typedef struct Vnode { char data; ArcNode *firstarc;//指向第一条依附该点的弧的指针 }Vnode, AdjList [MAX_VERTEX_NUM]; typedef struct ALGraph { AdjList vertices;//顶点数组 int vexnum,arcnum;//图的当前顶点数和弧数 }ALGraph; typedef struct CSNode { char data; struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree; /*--------确定所要插入边的顶点的位置---------------*/ int LocatedVex(ALGraph *G,char c) { int i; for(i=0;i<G->vexnum;i++) { if(G->vertices[i].data==c) { return i; } } return -1; } /*----------创建图---------*/ void CreateGraph(ALGraph *G) { char v,w; int i,m,n; ArcNode *p; printf("请输入顶点个数，弧数:"); scanf("%d,%d",&G->vexnum,&G->arcnum); getchar();//截获上面的回车 printf("请输入顶点信息:\n"); for(i=0;i<G->vexnum;i++) { G->vertices[i].data=getchar(); getchar(); G->vertices[i].firstarc=NULL; } printf("请输入边的信息：\n"); for(i=0;i<G->arcnum;i++) { scanf("%c,%c",&v,&w); getchar(); m=LocatedVex(G,v); n=LocatedVex(G,w); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=n; p->nextarc=G->vertices[m].firstarc;//将p插到vertices[m]链表的前面 G->vertices[m].firstarc=p; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=m; p->nextarc=G->vertices[n].firstarc; G->vertices[n].firstarc=p; } } /*------------输出顶点的度-----------*/ void Count(ALGraph *G) { int i,count; ArcNode *q; for(i=0;i<G->vexnum;i++) { count=0; q=G->vertices[i].firstarc; while(q!=NULL) { count++; q=q->nextarc; } printf("顶点%c的度为：%d\n",G->vertices[i].data,count); } } /*--------往无向图的邻接表表示中插入一个顶点--------*/ void AddVNodeALGraPh(ALGraph *G,char x) { char n; if (G->vexnum>=MAX_VERTEX_NUM) { printf("顶点数超过最大限度了!"); } printf("请输入要插入的顶点:\n"); scanf("%c",&n); getchar(); G->vertices[G->vexnum].data=x;//将新顶点输入顶点表 G->vertices[G->vexnum].firstarc=NULL;//边表置为空表 G->vexnum++;//顶点数加1 printf("插入顶点成功!:\n"); } /*-----往无向图的邻接表中插入边(x,y)------*/ void AddArcNodeALGraPh(ALGraph *G,char x,char y) { int i,j,k; ArcNode *s; //i=-1;j=-1; printf("请输入要插入边的顶点(顶点1，顶点2):\n"); scanf("%c,%c",&x,&y); i=LocatedVex(G,x); j=LocatedVex(G,y); if (i==-1||j==-1) { printf("结点不存在!\n"); } else { s=G->vertices[i].firstarc; while((s)&&(s->adjvex!=j)) {//判断邻接表中有是否有边(x,y) s=s->nextarc; } if (!s)//当邻接表中无边(x,y),插入边(x,y) { s=(ArcNode *)malloc(sizeof(ArcNode)); //生成边表结点 s->adjvex=j; //邻接点序号为j s->nextarc=G->vertices[i].firstarc; G->vertices[i].firstarc=s;//将新结点*s插入顶点x的边表头部 s=(ArcNode *)malloc(sizeof(ArcNode)); s->adjvex=i; //邻接点序号为i s->nextarc=G->vertices[j].firstarc; G->vertices[j].firstarc=s; //将新结点*s插入顶点y的边表头部 G->arcnum++;//边数加1 } } } /*--------删除顶点-----------*/ void DelVer(ALGraph *G){ int k;//所要删除顶点的值 int i,j,m; ArcNode *s,*p,*q; printf("请输入所要删除的顶点。\n"); scanf("%d",&k); s=G->vertices[m].firstarc; while (s) {//删除与m相关联的其他结点边表中表结点 p=G->vertices[s->adjvex].firstarc;//找到要删除顶点的头指针所指向的顶点 if (p->adjvex==m)//找到以顶点k为头指针，并删除k； { G->vertices[s->adjvex].firstarc=p->nextarc; free(p); } else {//顶点k不为头指针时的删除 while (p->nextarc->adjvex!=m) { p=p->nextarc; } q=p->nextarc; p->nextarc=q->nextarc; free(q); } q=s; s=s->nextarc; free(q);//删除以顶点k为弧尾的结点 G->arcnum--; for (j=m;j<G->vexnum-1;j++)//调整顶点表 { G->vertices[j].firstarc=G->vertices[j+1].firstarc; G->vertices[j].data=G->vertices[j+1].data; } G->vexnum--; for (j=0;j<G->vexnum;j++)//对所有adjvex域大于所删除结点的adjvex进行修改 { p=G->vertices[j].firstarc; while (p) { if (p->adjvex>m) { p->adjvex=p->adjvex-1; } p=p->nextarc; } } } getchar(); } /*---------邻接表删除一条边---------*/ void Delarc(ALGraph *G){//删除无向图中的一条边 int v1,v2; ArcNode *p,*s; int i,j,m; i=-1;j=-1; printf("请输入所要删除的边所依附的两个顶点值。\n"); scanf("%d%d",&v1,&v2); for (m=0;m<G->vexnum;m++) {//找到所要删除的两个顶点的位置 if (G->vertices[m].data==v1) { i=m; } if (G->vertices[m].data==v2) { j=m; } } if (i==-1||j==-1) { printf("顶点不存在"); } s=G->vertices[i].firstarc; //删除以i为弧尾的一条边 if ((s)&&(s->adjvex==j)) { G->vertices[i].firstarc=s->nextarc; free(s); } else{ while ((s)&&(s->nextarc)&&(s->nextarc->adjvex!=j)) { s=s->nextarc; if ((s->nextarc==NULL)||(s==NULL)) { printf("无此边。\n"); } else { p=s->nextarc; s->nextarc=p->nextarc; free(p); } } } s=G->vertices[j].firstarc; //删除以i为弧尾的一条边 if ((s)&&(s->adjvex==i)) { G->vertices[j].firstarc=s->nextarc; free(s); } else{ while ((s)&&(s->nextarc)&&(s->nextarc->adjvex!=i)) { s=s->nextarc; if ((s->nextarc==NULL)||(s==NULL)) { printf("无此边。\n"); } else { p=s->nextarc; s->nextarc=p->nextarc; free(p); } } } G->arcnum--; getchar(); } /*-----------输出图--------*/ void PrintALGraph(ALGraph *G){ ArcNode *p; int i; printf("图中有%d个顶点，%d条弧：\n",G->vexnum,G->arcnum); for(i=0;i<G->vexnum;i++){ p=G->vertices[i].firstarc; printf("%c\t",G->vertices[i].data); while(p){ printf("<%c,%c>\t",G->vertices[i].data,G->vertices[p->adjvex].data); p=p->nextarc; } printf("\n"); } } /*-----------深度优先遍历---------*/ void DFS(ALGraph *G,char i){ ArcNode *p; visited[i]=1; printf(" %c ",G->vertices[i].data); p=G->vertices[i].firstarc; while(p){ if(visited[p->adjvex]==0) DFS(G,p->adjvex); p=p->nextarc; } } void DFSTraverse(ALGraph *G){ int i; for(i=0;i<G->vexnum;i++) visited[i]=0; for(i=0;i<G->vexnum;i++) if(visited[i]==0) DFS(G,i); } /*----------深度优先生成树-------------*/ void DFSTree(ALGraph *G,int i,CSTree T,int visited[]){ ArcNode *m; CSTree p,q; int first; //int visited[MAX]; visited[i]=1; first=1; m=G->vertices[i].firstarc; while(m){ if(visited[m->adjvex]==0){ p=(CSNode*)malloc(sizeof(CSNode)); p->data=G->vertices[m->adjvex].data; p->firstchild=NULL; p->nextsibling=NULL; if(first){ T->firstchild=p; first=0; } else{ q->nextsibling=p; } q=p; DFSTree(G,m->adjvex,q,visited); } m=m->nextarc; } } CSTree DFSForest(ALGraph *G){ //ArcNode *p; int i; CSTree p,q; //CSNode *T; int visited[MAX_VERTEX_NUM];//用来标记顶点是否已被访问 CSTree T=NULL; for (i=0;i<G->vexnum;i++) { visited[i]=0; } for (i=0;i<G->vexnum;i++) { if(visited[i]==0){ p=(CSTree)malloc(sizeof(CSNode)); p->data=G->vertices[i].data; p->firstchild=NULL; p->nextsibling=NULL; if(!T) T=p; else q->nextsibling=p; q=p; DFSTree(G,i,q,visited); } } return T; } void Preorder(CSTree T){ //int visited[MAX]; if (T) { Preorder(T->