BYR Achieve · 镜像论坛

代码如下，输入图的节点和边文件，用邻接表存储，图比较大建图的那几个函数感觉没什么问题，用过很多次了就是最后的那个clustering_coefficient函数，有一个2万多的数组直接声明 int flag[]运行时会堆栈溢出，new一个后运行内存就飙升，我在函数的最后delete了的，大牛们帮我看下：万分感谢啊 #include<string.h> #include<malloc.h> #include<stdio.h> #include<stdlib.h> #include <iostream> /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAX_NAME 7 /* 顶点字符串的最大长度+1 */ #define MAX_VERTEX_NUM 21000 typedef char VertexType[MAX_NAME]; /* 字符串类型 */ using namespace std; //图的邻接表存储表示 typedef struct ArcNode { int adjvex; /* 该弧所指向的顶点的位置 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ }ArcNode; /* 表结点 */ typedef struct { VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */ }VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */ typedef struct { AdjList vertices; int vexnum,arcnum; /* 图的当前顶点数和弧数 */ }ALGraph; //图的邻接表存储的基本操作 int LocateVex(ALGraph 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; } int CreateGraph(ALGraph *G) { /* 采用邻接表存储结构,构造没有相关信息的图G */ int i,j,k; VertexType va,vb; ArcNode *p; char filename[15]; FILE *fpInputVertex,*fpInputArc; //输入节点文件 printf("Please input the name of vertex file：\n"); scanf("%s",filename); if((fpInputVertex=fopen(filename,"r"))==NULL) { printf("Can't open vertex file!"); exit(0); } //输入边文件 printf("Please input the name of arc file：\n"); scanf("%s",filename); if((fpInputArc=fopen(filename,"r"))==NULL) { printf("Can't open arc file!"); exit(0); } fscanf(fpInputVertex,"%d",&(*G).vexnum); fscanf(fpInputArc,"%d",&(*G).arcnum); for(i=0;i<(*G).vexnum;i++) /* 构造顶点向量 */ { fscanf(fpInputVertex,"%s",(*G).vertices[i].data); (*G).vertices[i].firstarc=NULL; } for(k=0;k<(*G).arcnum;k++) /* 构造表结点链表 */ { fscanf(fpInputArc,"%s%s",va,vb); i=LocateVex(*G,va); /* 弧尾 */ j=LocateVex(*G,vb); /* 弧头 */ p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */ (*G).vertices[i].firstarc=p; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=i; p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */ (*G).vertices[j].firstarc=p; } fclose(fpInputVertex); fclose(fpInputArc); return OK; } VertexType* GetVex(ALGraph G,int v) { /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */ if(v>=G.vexnum||v<0) exit(ERROR); return &G.vertices[v].data; } int FirstAdjVex(ALGraph G,VertexType v) { /* 初始条件: 图G存在,v是G中某个顶点 */ /* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */ ArcNode *p; int v1; v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */ p=G.vertices[v1].firstarc; if(p) return p->adjvex; else return -1; } int NextAdjVex(ALGraph G,VertexType v,VertexType w) { /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */ /* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */ /* 若w是v的最后一个邻接点,则返回-1 */ ArcNode *p; int v1,w1; v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */ w1=LocateVex(G,w); /* w1为顶点w在图G中的序号 */ p=G.vertices[v1].firstarc; while(p&&p->adjvex!=w1) /* 指针p不空且所指表结点不是w */ p=p->nextarc; if(!p||!p->nextarc) /* 没找到w或w是最后一个邻接点 */ return -1; else /* p->adjvex==w */ return p->nextarc->adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */ } double clustering_coefficient(ALGraph G,int source) { /* 初始条件：图G存在，source是G中某个顶点的序号 /* 操作结果：返回与source对应的节点的聚类系数（即相邻的节点之间实际存在的边数与最多可能边数之比）*/ int i = 0; int* flag = new int[MAX_VERTEX_NUM]; int count = 0; //所有邻接节点实际存在的边数 int num = 0; //邻接节点数 double clu_co = 0.0; VertexType source1; VertexType i1; ArcNode *p; strcpy(source1,*GetVex(G,source)); for(i = 0; i < G.vexnum; i++) { flag[i] = FALSE; //初始化 } for(i = FirstAdjVex(G,source1);i >= 0;i = NextAdjVex(G,source1,strcpy(i1,*GetVex(G,i)))) { flag[i] = TRUE; num++; } if(num == 1) return 0.0; //源节点只有一个邻接节点 else { for(i = FirstAdjVex(G,source1);i >= 0;i = NextAdjVex(G,source1,strcpy(i1,*GetVex(G,i)))) { p = G.vertices[i].firstarc; while(p) { if(flag[p->adjvex] == TRUE ) //与source邻接的节点i与其他的邻接节点有边相连 { count++; } p=p->nextarc; } } } double temp = 0.5 * num * (num -1); //总的可能边数 clu_co = 0.5 * count / temp; //无向图，边有重复计算，要除以2 free(p); delete [] flag; return clu_co; } void main() { ALGraph g; double all = 0.0; double clu_co = 0.0; CreateGraph(&g); for(int source = 0; source < g.vexnum; source++) { double temp = clustering_coefficient(g,source); all = all + temp; } clu_co = all / g.vexnum; printf("clustering coefficient is : %f\n",clu_co); }

[求助]版上的牛牛们帮我看下这个程序，传说中的内存溢出