数据结构C语言版-无向图的邻接多重表存储表示和实现.doc

数据结构C语言版 无向图的邻接多重表存储表示和实现.txt只要你要，只要我有，你还外边转什么阿老实在我身边待着就行了。听我的就是,问那么多干嘛，我在你身边,你还走错路!跟着我!不能给你幸福是我的错，但谁让你不幸福，我TMD去砍了他/*数据结构C语言版 无向图的邻接多重表存储表示和实现P166 编译环境：Dev-C+ 4.9.9.2日期：2011年2月15日 */#include #include #define MAX_NAME 3 / 顶点字符串的最大长度+1 #define MAX_INFO 80 / 相关信息字符串的最大长度+1 typedef char InfoType;typedef char VertexTypeMAX_NAME; / 字符串类型 / AMLGraph.h 无向图的邻接多重表存储表示 #define MAX_VERTEX_NUM 20typedef enumunvisited,visitedVisitIf;typedef struct EBoxVisitIf mark; / 访问标记 int ivex,jvex; / 该边依附的两个顶点的位置 struct EBox *ilink,*jlink; / 分别指向依附这两个顶点的下一条边 InfoType *info; / 该边信息指针 EBox;typedef structVertexType data;EBox *firstedge; / 指向第一条依附该顶点的边 VexBox;typedef structVexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum; / 无向图的当前顶点数和边数 AMLGraph;typedef int QElemType;/ 单链队列队列的链式存储结构 typedef struct QNodeQElemType data;/数据域struct QNode *next;/指针域QNode,*QueuePtr;typedef structQueuePtr front,/队头指针，指针域指向队头元素rear; /队尾指针，指向队尾元素LinkQueue;/ 若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1int LocateVex(AMLGraph G,VertexType u) int i;for(i=0;iG.vexnum;+i)if(strcmp(u,G.adjmulisti.data)=0)return i;return -1;/ 采用邻接多重表存储结构,构造无向图Gint CreateGraph(AMLGraph *G) int i,j,k,l,IncInfo;char sMAX_INFO;VertexType va,vb;EBox *p;printf(请输入无向图G的顶点数,边数,边是否含其它信息(是:1，否:0): );scanf(%d,%d,%d,&(*G).vexnum,&(*G).edgenum,&IncInfo);printf(请输入%d个顶点的值(%d个字符):n,(*G).vexnum,MAX_NAME);for(i=0;i(*G).vexnum;+i) / 构造顶点向量 scanf(%s,(*G).adjmulisti.data);(*G).adjmulisti.firstedge=NULL;printf(请顺序输入每条边的两个端点(以空格作为间隔):n);for(k=0;kmark=unvisited; / 设初值 p-ivex=i;p-jvex=j;p-info=NULL;p-ilink=(*G).adjmulisti.firstedge; / 插在表头 (*G).adjmulisti.firstedge=p;p-jlink=(*G).adjmulistj.firstedge; / 插在表头 (*G).adjmulistj.firstedge=p;if(IncInfo) / 边有相关信息 printf(请输入该弧的相关信息(info=(char*)malloc(l+1)*sizeof(char);strcpy(p-info,s);return 1;/ 返回v的值VertexType* GetVex(AMLGraph G,int v) if(v=G.vexnum|v0)exit(0);return &G.adjmulistv.data;/ 对v赋新值valueint PutVex(AMLGraph *G,VertexType v,VertexType value) int i;i=LocateVex(*G,v);if(i0) / v不是G的顶点 return 0;strcpy(*G).adjmulisti.data,value);return 1;/ 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 int FirstAdjVex(AMLGraph G,VertexType v) int i;i=LocateVex(G,v);if(iivex=i)return G.adjmulisti.firstedge-jvex;elsereturn G.adjmulisti.firstedge-ivex;elsereturn -1;/ 返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个邻接点,则返回-1 int NextAdjVex(AMLGraph G,VertexType v,VertexType w) int i,j;EBox *p;i=LocateVex(G,v); / i是顶点v的序号 j=LocateVex(G,w); / j是顶点w的序号 if(i0|jivex=i&p-jvex!=j) / 不是邻接顶点w(情况1) p=p-ilink; / 找下一个邻接顶点 else if(p-jvex=i&p-ivex!=j) / 不是邻接顶点w(情况2) p=p-jlink; / 找下一个邻接顶点 else / 是邻接顶点w break;if(p&p-ivex=i&p-jvex=j) / 找到邻接顶点w(情况1) p=p-ilink;if(p&p-ivex=i)return p-jvex;else if(p&p-jvex=i)return p-ivex;if(p&p-ivex=j&p-jvex=i) / 找到邻接顶点w(情况2) p=p-jlink;if(p&p-ivex=i)return p-jvex;else if(p&p-jvex=i)return p-ivex;return -1;/ 在G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)int InsertVex(AMLGraph *G,VertexType v) if(*G).vexnum=MAX_VERTEX_NUM) / 结点已满，不能插入 return 0;if(LocateVex(*G,v)=0) / 结点已存在,不能插入 return 0;strcpy(*G).adjmulist(*G).vexnum.data,v);(*G).adjmulist(*G).vexnum.firstedge=NULL;(*G).vexnum+;return 1;/ 在G中删除弧int DeleteArc(AMLGraph *G,VertexType v,VertexType w) int i,j;EBox *p,*q;i=LocateVex(*G,v);j=LocateVex(*G,w);if(i0|jjvex=j) / 第1条边即为待删除边(情况1) (*G).adjmulisti.firstedge=p-ilink;else if(p&p-ivex=j) / 第1条边即为待删除边(情况2) (*G).adjmulisti.firstedge=p-jlink;else / 第1条边不是待删除边 while(p) / 向后查找弧 if(p-ivex=i&p-jvex!=j) / 不是待删除边 q=p;p=p-ilink; / 找下一个邻接顶点 else if(p-jvex=i&p-ivex!=j) / 不是待删除边 q=p;p=p-jlink; / 找下一个邻接顶点 else / 是邻接顶点w break;if(!p) / 没找到该边 return 0;if(p-ivex=i&p-jvex=j) / 找到弧(情况1) if(q-ivex=i)q-ilink=p-ilink;elseq-jlink=p-ilink;else if(p-ivex=j&p-jvex=i) / 找到弧(情况2) if(q-ivex=i)q-ilink=p-jlink;elseq-jlink=p-jlink;/ 以下由另一顶点起找待删除边且删除之 p=(*G).adjmulistj.firstedge; / p指向顶点w的第1条边 if(p-jvex=i) / 第1条边即为待删除边(情况1) (*G).adjmulistj.firstedge=p-ilink;if(p-info) / 有相关信息 free(p-info);free(p);else if(p-ivex=i) / 第1条边即为待删除边(情况2) (*G).adjmulistj.firstedge=p-jlink;if(p-info) / 有相关信息 free(p-info);free(p);else / 第1条边不是待删除边 while(p) / 向后查找弧 if(p-ivex=j&p-jvex!=i) / 不是待删除边 q=p;p=p-ilink; / 找下一个邻接顶点 else if(p-jvex=j&p-ivex!=i) / 不是待删除边 q=p;p=p-jlink; / 找下一个邻接顶点 else / 是邻接顶点v break;if(p-ivex=i&p-jvex=j) / 找到弧(情况1) if(q-ivex=j)q-ilink=p-jlink;elseq-jlink=p-jlink;if(p-info) / 有相关信息 free(p-info);free(p);else if(p-ivex=j&p-jvex=i) / 找到弧(情况2) if(q-ivex=j)q-ilink=p-ilink;elseq-jlink=p-ilink;if(p-info) / 有相关信息 free(p-info);free(p);(*G).edgenum-;return 1;/ 删除G中顶点v及其相关的边 int DeleteVex(AMLGraph *G,VertexType v) int i,j;VertexType w;EBox *p;i=LocateVex(*G,v); / i为待删除顶点的序号 if(i0)return 0;for(j=0;j(*G).vexnum;j+) / 删除与顶点v相连的边(如果有的话) if(j=i)continue;strcpy(w,*GetVex(*G,j); / w是第j个顶点的值 DeleteArc(G,v,w);for(j=i+1;j(*G).vexnum;j+) / 排在顶点v后面的顶点的序号减1 (*G).adjmulistj-1=(*G).adjmulistj;(*G).vexnum-; / 顶点数减1 for(j=i;jivex=j+1)p-ivex-;p=p-ilink;elsep-jvex-;p=p-jlink;return 1;void DestroyGraph(AMLGraph *G)int i;for(i=(*G).vexnum-1;i=0;i-)DeleteVex(G,(*G).adjmulisti.data);/ 在G中增添弧int InsertArc(AMLGraph *G,VertexType v,VertexType w) int i,j,l,IncInfo;char sMAX_INFO;EBox *p;i=LocateVex(*G,v); / 一端 j=LocateVex(*G,w); / 另一端 if(i0|jmark=unvisited;p-ivex=i;p-jvex=j;p-info=NULL;p-ilink=(*G).adjmulisti.firstedge; / 插在表头 (*G).adjmulisti.firstedge=p;p-jlink=(*G).adjmulistj.firstedge; / 插在表头 (*G).adjmulistj.firstedge=p;printf(该边是否有相关信息(1:有 0:无): );scanf(%d%*c,&IncInfo); / 吃掉回车符 if(IncInfo) / 边有相关信息 printf(请输入该边的相关信息(info=(char*)malloc(l+1)*sizeof(char);strcpy(p-info,s);(*G).edgenum+;return 1;int visiteMAX_VERTEX_NUM; / 访问标志数组(全局量) int(*VisitFunc)(VertexType v);void DFS(AMLGraph G,int v)int j;EBox *p;VisitFunc(G.adjmulistv.data);visitev=1;p=G.adjmulistv.firstedge;while(p)j=p-ivex=v?p-jvex:p-ivex;if(!visitej)DFS(G,j);p=p-ivex=v?p-ilink:p-jlink;/ 算法7.4 / 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit void DFSTraverse(AMLGraph G,int(*visit)(VertexType)int v;VisitFunc=visit;for(v=0;vG.vexnum;v+)visitev=0;for(v=0;vnext=NULL;/队头指针指向空，无数据域，这样构成了一个空队列return 1;/ 若Q为空队列,则返回1,否则返回0 int QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return 1;elsereturn 0;/ 插入元素e为Q的新的队尾元素int EnQueue(LinkQueue *Q,QElemType e) QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p) / 存储分配失败 exit(0);/生成一个以为e为数据域的队列元素p-data=e;p-next=NULL;/将该新队列元素接在队尾的后面(*Q).rear-next=p;(*Q).rear=p;return 1;/ 若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0 int DeQueue(LinkQueue *Q,QElemType *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;/ 从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数 / Visit一次且仅一次。使用辅助队列Q和访问标志数组visite void BFSTraverse(AMLGraph G,int(*Visit)(VertexType) int v,u,w;VertexType w1,u1;LinkQueue Q;for(v=0;vG.vexnum;v+)visitev=0; / 置初值 InitQueue(&Q); / 置空的辅助队列Q for(v=0;v=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w)if(!visitew) / w为u的尚未访问的邻接顶点的序号 visitew=1;Visit(G.adjmulistw.data);EnQueue(&Q,w);printf(n);/ 置边的访问标记为未被访问 void MarkUnvizited(AMLGraph G)int i;EBox *p;for(i=0;imark=unvisited;if(p-ivex=i)p=p-ilink;elsep=p-jlink;/ 输出无向图的邻接多重表Gvoid Display(AMLGraph G) int i;EBox *p;MarkUnvizited(G); / 置边的访问标记为未被访问 printf(%d个顶点：n,G.vexnum);for(i=0;iG.vexnum;+i)printf(%s ,G.adjmulisti.data);printf(n%d条边:n,G.edgenum);for(i=0;iivex=i) / 边的i端与该顶点有关 if(!p-mark) / 只输出一次 printf(%s%s ,G.adjmulisti.data,G.adjmulistp-jvex.data);p-mark=visited;if(p-info) / 输出附带信息 printf(相关信息: %s ,p-info);p=p-ilink;else / 边的j端与该顶点有关 if(!p-mark) / 只输出一次 printf(%s%s ,G.adjmulistp-ivex.data,G.adjmulisti.data);p-mark=visited