- #include<stdio.h>
- #include<string.h>
- #include "stdlib.h"
- #define MAX_VERTEX_NUM 20//顶点个数
- #define MAX_NAME 10 /* 顶点字符串的最大长度+1 */
- typedef char VertexType[MAX_NAME];
- #define OK 1
- #define ERROR 0
- #define TRUE 1
- #define FALSE 0
- typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
- typedef struct ArcNode
- {
- int posvex;//顶点位置
- VertexType adjvex;//该弧所指向的顶点
- struct ArcNode *nextarc;//指向下一条弧的指针
- bool visited;
- }ArcNode;
- typedef struct VNode
- {
- VertexType data;//顶点信息
- ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
- }VNode,AdjList[MAX_VERTEX_NUM];
- typedef struct
- {
- AdjList vertices;
- int vexnum,arcnum;// 图的当前顶点数和弧数
- }MGraph;
- int LocateVex(MGraph G,VertexType u)
- { /* 初始条件:图G存在,u和G中顶点有相同特征 */
- /* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
- int i;
- for(i=0;i<G.vexnum;++i)
- if(strcmp(u,G.vertices [i].data )==0)
- return i;
- return -1;
- }
- void CreateUDL(MGraph *G)//创建邻接表
- {
- int i,k;
- VertexType va,vb;
- printf("请输入无向网G的顶点数,弧数: ");
- scanf("%d%*c%d",&(*G).vexnum,&(*G).arcnum);
- printf("请输入%d个顶点的值(<%d个字符):\\n",(*G).vexnum,MAX_NAME);
- for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
- {
- scanf("%s",(*G).vertices [i].data);
- (*G).vertices [i].firstarc =NULL;
- }
- for(k=0;k<(*G).arcnum;++k)
- {
- printf("请输入第%d条弧的弧尾、弧头: \\n",k+1);
- scanf("%s%s%*c",va,vb); /* %*c吃掉回车符 */
- for(int count=0;count<(*G).vexnum ;count++)
- {
- if(strcmp(va,(*G).vertices [count].data )==0)
- {
- ArcNode *tpArcNode =new ArcNode;
- strcpy(tpArcNode->adjvex ,vb);
- tpArcNode->posvex =LocateVex((*G),vb);
- tpArcNode->nextarc =NULL;
- tpArcNode->visited=false;
- if(!(*G).vertices [count].firstarc )
- {
- (*G).vertices [count].firstarc =tpArcNode;
- }
- else
- {
- ArcNode *tp=(*G).vertices [count].firstarc;
- while(tp->nextarc )
- {
- tp=tp->nextarc ;
- }
- tp->nextarc =tpArcNode;
- }
- }
- }
- }
- printf("邻接表为:\\n");
- for(i=0;i<(*G).vexnum ;i++)
- {
- printf("%4s",(*G).vertices [i].data );
- ArcNode *tp=(*G).vertices [i].firstarc;
- while(tp)
- {
- printf("%4s",tp->adjvex );
- tp=tp->nextarc ;
- }
- printf("\\n");
- }
- }
- void solveClosure(MGraph G)//求属性集X关于函数依赖集F的闭包
- {
- int oldLen,newLen;
- VertexType x;
- VertexType f;
- printf("请输入所求关于函数依赖集F的闭包的属性集X:\\n");
- scanf("%s%*c",x);
- strcpy(f,x);//X0=X
- ArcNode *tp=G.vertices [0].firstarc;
- int count=LocateVex(G,x);
- tp=G.vertices [count].firstarc;
- if(tp)
- {
- strcat(f,tp->adjvex);
- tp->visited=true;
- }//X1=X0^(X->?)
- //printf("x=%d\\n",strlen(x));
- do
- {
- strcpy(x,f);
- oldLen=strlen(f);//X0
- for(int i=0;i<strlen(x);i++)
- {
- VertexType temp={' ','\\0'};
- temp[0]=x[i];
- for(int count=0;count<G.vexnum ;count++)//标记已存在于f中的属性
- {
- tp=G.vertices [count].firstarc;
- if(strcmp(temp,tp->adjvex )==0)
- tp->visited=true;
- }
- //printf("temp=%s,x=%s\\n",temp,x);
- for(count=0;count<G.vexnum ;count++)
- {
- tp=G.vertices [count].firstarc;
- if(strcmp(temp,G.vertices [count].data )==0)
- {
- if(!tp->visited)
- {
- strcat(f,tp->adjvex);
- tp->visited=true;//标记添加的属性
- }
- }
- }
- }
- newLen=strlen(f);//X1
- //printf("oldlen=%d,newlen=%d\\n",oldLen,newLen);
- }while(oldLen<newLen);//X0=X1时 算法结束
- printf("属性集X关于函数依赖集F的闭包为:%s\\n",f);
- }
- void main()
- {
- MGraph g;
- CreateUDL(&g);
- solveClosure(g);
- system("pause");
- }
- //该片段来自于http://www.codesnippet.cn/detail/1710201410660.html
来源: http://www.codesnippet.cn/detail/1710201410660.html