{ p = G.vertices[j].firstarc; q = p->nextarc; if(p->adjvex == i) { G.vertices[j].firstarc = q; p = q; q = q->nextarc; continue; } else if(p->adjvex > i) p->adjvex--; while(q != NULL) { if(q->adjvex == i) { p->nextarc = q->nextarc; free(q); q = p->nextarc; } else if(q->adjvex > i) q->adjvex--; else { p = p->nextarc; q = q->nextarc; } } } else if( (G.vertices[j].firstarc->nextarc (G.vertices[j].firstarc != NULL) ) if( G.vertices[j].firstarc->adjvex == i ) { G.vertices[j].firstarc = NULL; } } } == NULL) &&
1. 实验目的 通过上机实验进一步掌握图的存储结构及基本操作的实现。 2. 实验内容与要求 要求： ⑴能根据输入的顶点、边/弧的信息建立图； ⑵实现图中顶点、边/弧的插入、删除； ⑶实现对该图的深度优先遍历； ⑷实现对该图的广度优先遍历。 备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。 3. 数据结构设计 逻辑结构：图状结构 存储结构：顺序存储结构、链式存储结构 4. 算法设计
printf("第%d个\n",i+1); scanf("%s",&G.vertices[i]); G.vertices[i].firstarc = NULL; } //这里开始构造边 printf("请输入边的信息\n"); printf("例如:v1 v2\n"); for(i = 0 ; i < G.arcnum ; i++) { printf("第%d条边\n",i+1); scanf("%s %s",&node1,&node2); j = LocateVex(G,node1); k = LocateVex(G,node2); p = (ArcNode *)malloc(sizeof(ArcNode)); q = (ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = k; q->adjvex = j; p->nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = p; q->nextarc = G.vertices[k].firstarc; G.vertices[k].firstarc = q; } PrintUDG(G); return 1; } int DeleteUDG(ALGraph &G) { int i,j; ArcNode *p,*q; char node[2]; int LocateVex(ALGraph G,char node[2]); void PrintUDG(ALGraph G); if(G.arcnum == 0) { printf("请先生成图\n");
return 0; } printf("请输入要删除的节点\n"); scanf("%s",&node); i = LocateVex(G,node); if(i == -1) { printf("无此节点\n"); return 0; } else { G.vexnum--; if((p = q = G.vertices[i].firstarc) != NULL) { G.arcnum--; p = p->nextarc; G.vertices[i].firstarc = p; free(q); q = p; while(p != NULL) { G.arcnum--; p = p->nextarc; G.vertices[i].firstarc = p; free(q); q = p; } } for(j = 0 ; j < G.vexnum ; j++ ) { if(j >= i) { strcpy(G.vertices[j].data , G.vertices[j+1].data); G.vertices[j].firstarc = G.vertices[j+1].firstarc; } if(G.vertices[j].firstarc->nextarc != NULL)
int t; t=q.data[q.front]; q.front++; return(t); } int empty() { if(q.front==q.rear) return 1; return 0; } int LocateVex(ALGraph G,char node[2]) { int i; for(i = 0 ; i < G.vexnum ; i++) { if(strcmp(G.vertices[i].data,node)==0) return i; } return -1; } int CreateUDG(ALGraph &G) { int LocateVex(ALGraph G,char node[2]); void PrintUDG(ALGraph G); int i,j,k; char node1[2],node2[2]; ArcNode *p,*q; printf("请输入顶点数和弧数\n"); printf("例如:5,6\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); printf("请输入各顶点\n"); for(i = 0 ; i < G.vexnum ; i++) {
#include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX_VERTEX_NUM 20 typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode { char data[2]; //顶点就设置和书上V1等等一样吧 ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph; typedef struct { int data[MAX_VERTEX_NUM+10]; int front; int rear; }queue; int visited[MAX_VERTEX_NUM]; queue q; int main() { ALGraph G; int CreateUDG(ALGraph &G); int DeleteUDG(ALGraph &G); int InsertUDG(ALGraph &G); void BFSTraverse(ALGraph G, int (*Visit)(ALGraph G,ArcNode v)); int PrintElement(ALGraph G,ArcNode v);
Hale Waihona Puke p->adjvex = k; q->adjvex = l; p->nextarc = G.vertices[l].firstarc; G.vertices[l].firstarc = p; q->nextarc = G.vertices[k].firstarc; G.vertices[k].firstarc = q; } PrintUDG(G); return 1; } void depthfirstsearch(ALGraph *g,int vi) { ArcNode *rear; printf("%s\t",g->vertices[vi].data); visited[vi]=1; rear=g->vertices[vi].firstarc; while((rear!=NULL)&&(!visited[rear->adjvex])) { depthfirstsearch(g,rear->adjvex); rear=rear->nextarc; } } void travel(ALGraph *g) { int v; for(v=0;v<g->vexnum;v++) if(!visited[v]) depthfirstsearch(g,v); } void breadfirstsearch(ALGraph *g) { int v,t,i; ArcNode *rear; for(i = 0 ; i <g->vexnum ; i++) visited[i] = 0; for(v=0;v<g->vexnum;v++) {
void menu(); void depthfirstsearch(ALGraph *g,int vi); void travel(ALGraph *g); void breadfirstsearch(ALGraph *g); int i; G.arcnum = G.vexnum = 0; while(1) { menu(); do { printf ( "请输入要进行的操作\n" ); scanf ("%d",&i); if (i<1||i>6) printf("错误数字，请重新输入\n"); }while (i<1||i>6); switch (i) { case 1: CreateUDG(G); system("pause"); system("cls"); break; case 2: DeleteUDG(G); system("pause"); system("cls"); break; case 3: InsertUDG(G); system("pause"); system("cls"); break; case 4: travel(&G); system("pause"); system("cls"); break; case 5: breadfirstsearch(&G); system("pause"); system("cls"); break; case 6: exit(0); break; } } return 1; } void enterqueue(int v) { q.data[q.rear]=v; q.rear++; } int deletequeue() {